Patent ID: 8146071

Claim:
A computer-implemented method for preparing a loop in a set of loops in computer code for parallel processing, the computer-implemented method comprising: identifying the loop by identifying which loop in the set of loops will, during execution thereof, have an iteration vector bounded by an iteration space of the loop, wherein all data dependencies are contained within the loop; representing each data dependency as a corresponding dependency vector D k having elements (d k 1 , d k 2 , . . . d k n ), wherein a set of dependency vectors are formed; using the set of dependency vectors to compute a result vector C having elements c 1 , c 2 , . . . c n ); for each corresponding dependency vector in the set of dependency vectors that satisfies the equation: C → = ( C ⁡ [ 1 ] C ⁡ [ 2 ⁢ ⁢ … ⁢ ⁢ n ] ) ⁢ ⁢ = ( g ⁢ ⁢ c ⁢ ⁢ d ⁡ ( d 1 1 , d 1 2 , … ⁢ ⁢ d 1 k ) max_vect ⁢ ( D 1 ⁡ [ 2 ⁢ ⁢ … ⁢ ⁢ n ] , D 2 ⁡ [ 2 ⁢ ⁢ … ⁢ ⁢ n ] , … ⁢ ⁢ D k [ 2 ⁢ ⁢ … ⁢ ⁢ n ) ] ) inserting into the loop a call to a WAIT(wI) primitive immediately prior to a lexically earliest sink statement in the loop, wherein: “I” will represent a current value of the loop iteration vector for the loop; (wI) is computed as wI=(I−C); invocation of the WAIT(wI) primitive, where (wI) is within the iteration space of the loop, will, during execution of the loop, cause a first thread which processed the WAIT(wI) instruction to suspend until invocation by a second thread of a POST(pI) primitive for which pI is equal to or greater than wI for a value of (wI for which the WAIT(wI) primitive was invoked by the first thread; invocation of the WAIT(wI) primitive, where (wI) is outside the iteration space of the loop, will be ignored; and inserting into the loop the POST(pI) primitive immediately following a lexically latest source statement in the loop, wherein pI=I.