Method and apparatus for parallel execution of computer programs using information providing for reconstruction of a logical sequential program

摘要

A computer system with multiple execution units operates by treating a logical program as a tree structure with segments which include several computer instructions. Segments of the tree structure are connected by nodes which represent decisional instructions in the logical program. Serial numbers are assigned to each instruction within each of the tree structure. The instructions and then rearranged into a set of instructions which are no longer linearly dependent. The original serial numbers assigned to each instruction are retained with the instructions after rearrangement. During rearrangement, path information is added to each instruction to indicate its commit point. The serial numbers and path information allow reconstruction of the original set of instructions from the rearranged set of instructions. The path codes represent a path through the tree structure to a particular one of the segments in which all of the instructions in the associated subset will be committed in logical terms. The information added to the rearranged instructions allows several instructions to be executed in parallel while producing the same results as would have been produce had the instructions been executed one at a time by a sequential processor.