Programmatic iteration scheduling for parallel processors

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;
• from the mapping and a specified initiation interval, programmatically determining a definition of iteration schedules, where each schedule provides start times for initiating execution of iterations on a processor element such that no more than one iteration is started on a processor element for each initiation interval, wherein the processor elements are physical processor elements, and said determining a definition of iteration schedules including:
• assigning the iterations of the nested loop to a virtual processor space, where virtual processors in the virtual processor space each have a corresponding one-dimensional sub-set of iterations in an iteration space;
• and
• assigning virtual processors to processor elements such that a rectangular cluster of virtual processors is assigned to each physical processor element;
• wherein the definition of schedules is defined as:
• T(I)=(t1 i1+t2 i2+ . . . +tn in);
• and
• t=(k1, k2C1,k3C1C2, . . . , knC1***Cn−1),
• where I is a vector of loop indices whose elements identify an iteration of the loop, T(I) is the start time of iteration I, C=(C1, . . . Cn−1) is a vector defining a rectangular subset of the virtual processors that includes the virtual processors mapped to any one physical processor, and k=(k1, . . . , kn) is a vector of integers that has the property that the greatest common devisor of ki and Ci is one and kn=+1 or −1.

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:

• performing tiling of iteration space of the nested loop to partition the iteration space into tiles of iterations to be initiated sequentially;
• determining a mapping of the iterations of the nested loop to processor elements based on the tiles;
• and
• from the mapping and a specified initiation interval, programmatically determining a definition of iteration schedules and, when a set of schedules does not satisfy data dependence constraints of the nested loop, further comprising expanding size of the tiles and determining new sets of schedules, said expanding and determining new set being performed until at least one new set of schedules satisfies the data dependence constraints.

A method of generating a conflict-free schedule of iterations mapped to processors by projecting iterations along a null direction to form virtual processors, grouping the virtual processors into rectangular clusters, assigning the rectangular clusters to physical processors and determining a definition of schedules defined as:

• T(I)=(t1 i1+t2 i2+ . . . +tn in);
• and
• t=(k1, k2C1, k3C1C2, . . . , knC1***Cn−1),
• where I is a vector of loop indices whose elements identify an iteration of the loop, T(I) is the start time of iteration I, C=(C1, . . . , Cn−1) is a vector defining a rectangular subset of the virtual processors that includes the virtual processors mapped to any one physical processor, and k=(k1, . . . , kn) is a vector of integers that has the property that the greatest common devisor of ki and Ci is one and kn=+1 or −1.