Patent ID: 7076777

Claim:
A method in a computer system for scheduling iterations of a loop in a computer program for parallel execution, in which the loop has an irregular memory access pattern involving multiple arrays, the computer program being stored on tangible media of a storage device of the computer system, the method comprising the steps of: reading the computer program from the storage device by the computer system; and performing steps by the computer system responsive to the instructions of the computer program, the steps including: reading and writing loop variables v (v=1 . . . nv) of a loop of the computer program that has iterations i (i=1 . . . niter) respectively from and to a data file that maintains values of said loop variables v; recording, for each of said loop variables v, a respective loop variable array x v (ae) (ae=1 . . . na(v)); calculating, for each loop iteration i, (i) a read variable set R(i) that has as members elements of said loop variable arrays x v (ae) that we read, for iteration i, from said data tile, and (ii) a write variable set W(i) that has as members elements of said loop variable arrays x v (ae) that are written, for iteration i, to said data file, wherein multiple variables with multiple array elements are read from each variable during each iteration; calculating, for each iteration i, a predecessor iteration j (j=prd(i)) as the maximum iteration for which the intersection of the read variable set R(i) for iteration i and the write variable set W(j) for predecessor iteration j is not a null set Ã˜; determining a last write access array lwa(p, v, ae), which represents a most recent iteration performed on processor p that writes array element ae of variable v, such that only a latest write access of such an element of R(i) is considered rather than both read and write accesses of such an element of R(i) and W(i); assigning in a first wavefront (wf(i)=1) each of said iterations i that do not have a predecessor iteration j, and assigning to a successive wavefront (wf(i)>1) each of said iterations i that do have a predecessor iteration j; and scheduling each of said iterations i into one of said scheduled wavefronts; wherein iterations in parallelizable loops having arbitrary data access patterns, defined by said recorded loop variable arrays x v (ae), are inspected and scheduled for execution.