Patent ID: 8572590

Claim:
A method of scheduling the operations of a program on a multi-execution unit computing apparatus, the method comprising: receiving a computer program in a memory on a first computing apparatus, the first computing apparatus comprising the memory, a storage medium and at least one processor, the at least one processor comprising at least one multi-stage execution unit, the computer program comprising at least one arbitrary loop nest; optimizing the computer program for execution on a second computing apparatus, the second computing apparatus comprising at least two execution units, the optimization comprising optimizing a selective tradeoff of parallelism and locality costs of operations on the at least two execution units; and producing an optimized computer program for execution on the second computing apparatus, wherein optimizing the selective tradeoff comprises: assigning a first cost to at least one loop, the at least one loop contained within the at least one arbitrary loop nest, the first cost being related to a difference between execution speeds where operations of the loop are executed in parallel on the second computing apparatus and where the operations of the loop are executed sequentially on the second computing apparatus; assigning a second cost to at least one pair of loops, the at least one pair of loops contained within the at least one arbitrary loop nest, the second cost being related to a difference between execution speeds where operations of the pair of loops are executed together on the second computing apparatus, and where operations of the pair of loops are not executed together on the second computing apparatus; assigning each loop within the at least one arbitrary loop nest a first decision variable that specifies if the loop is executed in parallel in the optimized program; assigning each pair of loops within the at least one arbitrary loop nest a second decision variable that specifies if the loops are executed together in the optimized program; and optimizing a global weighted parametric function of the first cost, the second cost, the first decision variable and the second decision variable; determining a set of conditions that preserve a semantic correctness of the program; representing the set of conditions preserving semantic correctness in the form of a generalized dependence graph; and deriving at least one multidimensional piecewise affine function to schedule operations in the optimized program, the multidimensional piecewise affine function optimizing the global weighted parametric function and enforcing the set of conditions for semantic correctness in the optimized program.