Self-scheduling parallel computer system and method

Claim 1

A method of distributing the instructions of an execution sequence among a plurality of processing elements for execution in parallel, comprising the steps of: creating a pseudo-schedule of said instructions, said pseudo-schedule having the same number of partitions as the number of said processing elements, each of said instructions having an assigned particular partition in said pseudo-schedule and each of said instructions having an assigned particular decode time, said decode times being based upon the anticipated availability times of needed input values for each said instruction, and said partition assignments being based upon the assigned decode time of each said instruction as well as the assigned decode times of all prior instructions in said execution sequence; and distributing instructions having the same assigned partition for execution on the same one of said processing elements, but without any of said decode times used to form said pseudo-schedule.

Claim 4

A method of distributing the instructions of an execution sequence into a plurality of partitions for execution of each said partition on a separate one of a corresponding plurality of processing elements in parallel, comprising the steps of: (a) assigning the first instruction in said execution sequence to one of said processing elements; (b) establishing an arbitrary decode time for said first instruction for partitioning purposes with respect to which all other times are referenced for partitioning purposes; (c) determining the time when the output of said first instruction would be available for use as an input by other ones of said instructions if said first instruction were decoded by its assigned processing element at said arbitrary decode time and then executed by its assigned processing element; (d) for the next instruction in said execution sequence, determining the earliest decode time when decoding of said next instruction could begin and not wait for any input needed by said next instruction for decoding and execution; (e) determining an availability time for each processing element when said each processing element would be available to decode and execute said next instruction if each previously assigned instruction in said execution sequence were decoded by its assigned processing element at the later of either said determined earliest decode time for said previously assigned instruction or said determined availability time for its assigned processing element; (f) assigning said next instruction to one of said processing elements using a criterion which is a function of said availability times determined in step (e) and said decode time determined in step (d); (g) determining the time when the output of said next instruction would be available for use as an input by other ones of said instructions if said next instruction were decoded and then executed by its assigned processing element at the later of either its earliest decode time or the determined availability time for its assigned processing element; (h) repeating steps (d) through (g) for each successive instruction in said execution sequence of instructions, each collection of said instructions assigned to the same processing element being a partition of said instructions.

Claim 9

A method as defined in one of Claims 4 to 8 and further comprising the steps of: identifying said processing element which corresponds to the earliest determined availability time and resolving ties in accordance with a predetermined priority order; identifying the latest availability time when one of said processing elements is expected to be available to decode an additional instruction; determining the number of processing elements having an availability time which is lagging said identified latest availability time by more than a predetermined amount; if said determined number of lagging processing elements is not greater than a predetermined number and the difference between said time determined in step (c) and said determined latest availability time is not greater than said predetermined amount, scheduling said next instruction on said identified processing element having the earliest availability time.