Patent Document ID: 5481723
Application ID: 08395275
Patent Flag: 1

Claim One:
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.