Patent ID: 7865886

Claim:
A computer implemented method comprising: receiving a computer code segment and storing the computer code segment in a random access memory, the segment including a first inner loop and a second outer loop, the first loop being within the second loop and having an one-dimensional iteration space that is independent of the outer loop, the first loop further being indexed by a variable I over the one-dimensional iteration space, the first loop addressing one or more data arrays with a shift in the index I; and automatically transforming the computer code segment using a processor to block nested loops of the segment by: dividing a two-dimensional iteration space for the first loop and the second loop into a plurality of contiguous windows, the second loop using only one window of the plurality of windows during each iteration of the second loop, the plurality of windows covering the two-dimensional iteration space, and modifying the computer code segment by adding a third outer loop outside the second loop of the segment, the third loop encompassing the first loop and the second loop, the third outer loop providing for iteration over all of the plurality of windows, wherein each window of the plurality of windows is shifted during the second loop to maintain correctness of data accesses, each window of the plurality of windows using a constant shift throughout the second loop, the wherein a constant shift value S is computed based at least in part on an indexing scheme used for the first loop; and wherein the constant shift value S is calculated as: S =min( LRâˆ’UW,LWâˆ’UR ) where: each of the inner loops reads or writes a set of arrays array 1 , array 2 , . . . and the K-th assignment within this system is of the form arrayM K (I+LWK)=F[array 1 {I+LR 1 , . . . , I+UR 1 }, . . . , arrayX{I+LRX, . . . , I+URX}] LW is the minimum of all LWK write shifts, UW is the maximum of all LWK write shifts, LR is the minimum of all LRK read shifts, and UR is the maximum of all URK read shifts.