System and method for controlling execution of nested loops in parallel in a computer including multiple processors, and compiler for generating code therefore

Claim 1

A method of compiling a nested loop program structure including an outer loop structure to be processed by a plurality of processors operating in parallel, each of said processors assigned to process a selected one of a plurality of outer loop iterations, and further including an inner loop structure to be processed in a plurality of inner loop iterations, the inner loop iterations corresponding to each said outer loop iteration being processed in series by the processor assigned to process the corresponding outer loop iteration, wherein at least one of the inner loop iterations is dependent upon a computation of another of the inner loop iterations in a preceding iteration of the outer loop iterations, the method comprising the steps, performed in a data processing system, of: A) extracting the outer loop structure from the nested loop structure; B) extracting the inner loop structure from the nested loop structure; C) generating a plurality of control structures each for enabling a corresponding one of said processors to perform a current outer loop iteration of the outer loop iterations and at least a current inner loop iteration of the inner loop iterations, each said control structure comprising a progress counter providing a count representing a number of inner loop iterations performed by the processor corresponding to said counter, said control structures enabling a current processor of the plurality of processors to perform the substeps of: i) waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration that precedes the current outer loop iteration being performed by the current processor, generates a waiting report value indicating that the previous processor has completed performance of an inner loop iteration upon which the current inner loop iteration being performed by the current processor depends; ii) after the waiting step, performing the current inner loop iteration as defined by the inner loop structure; and iii) after the performing step, generating a next report value to indicate to a next processor of the plurality of processors that the current inner loop iteration has been completed by the current processor; D) wherein the waiting report value and the next report value are generated in response to the counts of the counters corresponding respectively to the previous processor and to the current processor.

Claim 2

A method of compiling a nested loop program structure including an outer loop structure to be processed by a plurality of processors operating in parallel, each of said processors assigned to process a selected one of a plurality of outer loop iterations, and further including an inner loop structure to be processed in a plurality of inner loop iterations, the inner loop iterations corresponding to each said outer loop iteration being processed in series by the processor assigned to process the corresponding outer loop iteration, wherein at least one of the inner loop iterations is dependent upon a computation of another of the inner loop iterations in a preceding iteration of the outer loop iterations, the method comprising the steps, performed in a data processing system, of: A) extracting the outer loop structure from the nested loop structure; B) extracting the inner loop structure from the nested loop structure; C) generating a plurality of control structures each for enabling a corresponding one of said processors to perform a current outer loop iteration of the outer loop iterations and at least a current inner loop iteration of the inner loop iterations, each said control structure comprising a progress counter providing a count representing a number of inner loop iterations performed by the processor corresponding to said counter, said control structures enabling a current processor of the plurality of processors to perform the substeps of: i) waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration that precedes the current outer loop iteration being performed by the current processor, generates a waiting report value indicating that the previous processor has completed performance of an inner loop iteration upon which the current inner loop iteration being performed by the current processor depends; ii) after the waiting step, performing the current inner loop iteration as defined by the inner loop structure; and iii) after the performing step, generating a next report value to indicate to a next processor of the plurality of processors that the current inner loop iteration has been completed by the current processor; D) wherein the waiting report value and the next report value are generated in response to the counts of the counters corresponding respectively to the previous processor and to the current processor.

Claim 12

The system of claims 8 wherein the inner loop structure includes a condition expression corresponding to a predetermined number of inner loop iterations which determines the number of inner loop iterations to be processed and which has a value equal to or greater than the dependency distance.

Claim 19

A method of compiling a nested loop program structure including an outer loop structure to be processed by a plurality of processors operating in parallel, each of said processors assigned to process a selected one of a plurality of outer loop iterations, and further including an inner loop structure to be processed in a plurality of inner loop iterations, the inner loop iterations corresponding to each said outer loop iteration being processed in series by the processor assigned to process the corresponding outer loop iteration, one of the inner loop iterations is dependent upon a computation another of the inner loop iterations in a preceding iteration of the outer loop iterations, said one inner loop iteration occurring a number of inner loop iterations after said another inner loop iteration, and wherein a dependency distance is used to measure a number of inner loop iterations between said one inner loop iteration and said another inner loop iteration, the method comprising the steps, performed in a data processing system, of: extracting the outer loop structure from the nested loop structure; extracting the inner loop structure from the nested loop structure; analyzing the extracted outer loop structure and the extracted inner loop structure to determine the dependency distance; generating control structure means for enabling each processor to perform a current outer loop iteration, wherein the current outer loop iteration is one of the outer loop iterations, and at least a current inner loop iteration, said control structure means enabling allocation of a different one of a plurality of counters to each of the processors including a current processor and a previous processor, each said counter for providing a count representing a number of inner loop iterations performed by the processor to which the counter is allocated, said control structure means enabling a current processor of the plurality of processors to perform the substeps of: i) responsive to the dependency distance, waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration, generates a waiting report value indicating that the previous processor has performed the second inner loop iteration and identifying the second inner loop iteration from among the plurality of inner loop iterations, wherein the first inner loop iteration is to be performed by the current processor performing the current outer loop iteration; ii) after the waiting step, performing said first inner loop iteration as defined by the inner loop structure; and iii) after the performing step, generating a next report value to indicate to a next processor that the first inner loop iteration has been performed by the current processor; the waiting report value and the next report value being generated in response to the counts of the counters allocated respectively to the previous processor and to the current processor.

Claim 20

A method of compiling a nested loop program structure including an outer loop structure to be processed by a plurality of processors operating in parallel, each of said processors assigned to process a selected one of a plurality of outer loop iterations, and further including an inner loop structure to be processed in a plurality of inner loop iterations, the inner loop iterations corresponding to each said outer loop iteration being processed in series by the processor assigned to process the corresponding outer loop iteration, one of the inner loop iterations is dependent upon a computation another of the inner loop iterations in a preceding iteration of the outer loop iterations, said one inner loop iteration occurring a number of inner loop iterations after said another inner loop iteration, and wherein a dependency distance is used to measure a number of inner loop iterations between said one inner loop iteration and said another inner loop iteration, the method comprising the steps, performed in a data processing system, of: extracting the outer loop structure from the nested loop structure; extracting the inner loop structure from the nested loop structure; analyzing the extracted outer loop structure and the extracted inner loop structure to determine the dependency distance; generating control structure means for enabling each processor to perform a current outer loop iteration, wherein the current outer loop iteration is one of the outer loop iterations, and at least a current inner loop iteration, said control structure means enabling allocation of a different one of a plurality of counters to each of the processors including a current processor and a previous processor, each said counter for providing a count representing a number of inner loop iterations performed by the processor to which the counter is allocated, said control structure means enabling a current processor of the plurality of processors to perform the substeps of: i) responsive to the dependency distance, waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration, generates a waiting report value indicating that the previous processor has performed the second inner loop iteration and identifying the second inner loop iteration from among the plurality of inner loop iterations, wherein the first inner loop iteration is to be performed by the current processor performing the current outer loop iteration; ii) after the waiting step, performing said first inner loop iteration as defined by the inner loop structure; and iii) after the performing step, generating a next report value to indicate to a next processor that the first inner loop iteration has been performed by the current processor; the waiting report value and the next report value being generated in response to the counts of the counters allocated respectively to the previous processor and to the current processor.

Claim 21

A method of executing a nested loop program structure including an outer loop structure and an inner loop structure, the method comprising the steps, performed by the data processing system, of: A) extracting the outer loop structure and the inner loop structure from the nested loop structure, wherein said outer loop structure can be processed by a plurality of processors operating in parallel; B) assigning each processor at least a corresponding current iteration included in a plurality of iterations of the outer loop structure, and, for processing in series, a plurality of iterations of the inner loop structure, wherein at least one of the inner loop iterations is dependent upon a computation of another of the inner loop iterations in a preceding iteration of the outer loop iterations; C) generating a plurality of progress counters each for use by a corresponding one of said processors during processing of the inner loop iterations assigned to said corresponding processor, each said progress counter providing a count representing a number of inner loop iterations performed by the corresponding processor; D) a current processor of the plurality of processors performing the substeps of: i) waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration that precedes the current outer loop iteration being performed by the current processor, generates a waiting report value indicating that the previous processor has completed performance of an inner loop iteration upon which a current one of the inner loop iterations being performed by the current processor depends; ii) after the waiting step, performing a current one of the assigned inner loop iterations; and iii) after the performing step, generating a next report value to indicate to a next processor of the plurality of processors that the current inner loop iteration has been completed by the current processor; E) wherein the waiting report value and the next report value are generated in response to the counts of the counters corresponding respectively to the previous processor and to the current processor.

Claim 22

A method of executing a nested loop program structure including an outer loop structure and an inner loop structure, the method comprising the steps, performed by the data processing system, of: A) extracting the outer loop structure and the inner loop structure from the nested loop structure, wherein said outer loop structure can be processed by a plurality of processors operating in parallel; B) assigning each processor at least a corresponding current iteration included in a plurality of iterations of the outer loop structure, and, for processing in series, a plurality of iterations of the inner loop structure, wherein at least one of the inner loop iterations is dependent upon a computation of another of the inner loop iterations in a preceding iteration of the outer loop iterations; C) generating a plurality of progress counters each for use by a corresponding one of said processors during processing of the inner loop iterations assigned to said corresponding processor, each said progress counter providing a count representing a number of inner loop iterations performed by the corresponding processor; D) a current processor of the plurality of processors performing the substeps of: i) waiting until a previous processor of the plurality of processors, performing a previous outer loop iteration that precedes the current outer loop iteration being performed by the current processor, generates a waiting report value indicating that the previous processor has completed performance of an inner loop iteration upon which a current one of the inner loop iterations being performed by the current processor depends; ii) after the waiting step, performing a current one of the assigned inner loop iterations; and iii) after the performing step, generating a next report value to indicate to a next processor of the plurality of processors that the current inner loop iteration has been completed by the current processor; E) wherein the waiting report value and the next report value are generated in response to the counts of the counters corresponding respectively to the previous processor and to the current processor.