Patent ID: 6438747
Filing Date: 2002-08-20
Classification: G06F

Abstract:
A method for determining an iteration schedule for iterations of a nested loop to be executed on an array of processor elements, the method comprising:determining a mapping of iterations of the nested loop to processor elements; and from the mapping and a specified initiation interval, programmatically determining a definition of iteration schedules of the form: T(I)=(t1 i1+t2 i2+ . . . +tn in), where I is a vector of loop indices (i1, i2, . . . in) whose elements identify an iteration of the loop, T(I) is the start time of iteration I, and t=(t1, . . . , tn) is a schedule vector; wherein said determining the definition of schedules comprises obtaining a representation of data dependence constraints expressed as a system of linear inequalities to be satisfied by the schedule vector t; finding upper and lower bounds on elements of the vector t based on the data dependence constraints; and using the bounds as a constraint on the schedule vector t.