Mechanism to control the sequencing of partially ordered instructions in a parallel data processing system

Claim 1

A sequencing control unit for use in a parallel processing system with algorithmic means for automatically determining the presence of parallelism within and between statements of programs being executed by the processing system and means in association with said algoRithmic means for providing output signals denoting incidents of such parallelism, said sequencing control unit comprising matrix means for indicating the presence of said parallelism and connected to receive the output signals of the output means, and a plurality of vector registers coupled to said matrix for applying individually and solely each of the following vectors: executed vectors to simultaneously search the stored contents of said matrix means; initiation vectors to initiate the processing of a further instruction within those programs being executed by the processing system when all predecessor instructions have been executed; in progress vectors for preventing initiation of a further instruction within those programs being executed by the processing system while a previous one is being executed; and allowable vectors for indicating the results of a simultaneous search of said matrix.

Claim 4

A system for controlling the sequencing of partially ordered instructions in a parallel processing system comprising means for automatically detecting parallelism in the programs being executed by said processing system, matrix storage means for simultaneously storing the output signals from said detection means and thereby representing the output therefrom, an executed vector register connected to said matrix storage means for simultaneously searching the contents thereof, an allowable vector of signal lines connected to said matrix storage means for receiving the results of said simultaneous search, an in progress vector register further coupled to said matrix storage means for preventing reinitiation of an instruction contained in the programs being executed by the processing system that is already being processed, and an initiation vector register also coupled to said matrix for initiating the processing of further instructions also contained in said programs when all predecessor instructions have been executed.

Claim 5

A system for controlling the sequencing of partially ordered instructions in a parallel processing system comprising means for automatically detecting parallelism in the programs being executed by said processing system, matrix storage means for simultaneously storing the output signals from said detection means and thereby representing the output therefrom, an executed vector register connected to said matrix storage means for simultaneously searching the contents thereof, an allowable vector of signal lines connected to said matrix storage means for receiving the results of said simultaneous search, an in progress vector register further coupled to said matrix storage means for preventing reinitiation of an instruction contained in the programs being executed by the processing system that is already being processed, and an initiation vector register also coupled to said matrix for initiating the processing of further instructions also contained in said programs when all predecessor instructions have been executed.

Claim 9

A method for the detection of parallelism based on input/output set intersections between statements of programs being executed on a data processing system by providing a partial order statement matrix, said method comprising the steps of obtaining a table of availability from statement outputs, initial statement order and given essential order said table being a two dimensional Boolean array with statement outputs as the row dimension and statement numbers as the column dimension, such that a binary 1 at position (i,j) of the table indicates that output i is available at statement j; next from statement inputs obtain an input requirement table similar to the availability table, such that a binary 1 at position (i,j) of the input requirement table also indicates that output i is required as an input to statement j; next, obtain the given essential order from the conditional statements; thereafter AND gate together, intersection by intersection, the availability table and the input requirement table, to provide an input/output statement intersection table; and finally OR gate together, the corresponding elements of the input/output statement intersection table and the given essential order to provide the partial order statement matrix.

Claim 10

A method for the detection of parallelism based on input/output set intersections between statements of programs being executed on a data processing system by providing a partial order statement matrix, said method comprising the steps of obtaining a table of availability from statement outputs, initial statement order and given essential order said table being a two dimensional Boolean array with statement outputs as the row dimension and statement numbers as the column dimension, such that a binary 1 at position (i,j) of the table indicates that output i is available at statement j; next from statement inputs obtain an input requirement table similar to the availability table, such that a binary 1 at position (i,j) of the input requirement table also indicates that output i is required as an input to statement j; next, obtain the given essential order from the conditional statements; thereafter AND gate together, intersection by intersection, the availability table and the input requirement table, to provide an input/output statement intersection table; and finally OR gate together, the corresponding elements of the input/output statement intersection table and the given essential order to provide the partial order statement matrix.