Methods and apparatus for joint parallelism and locality optimization in source code compilation

A custom computing apparatus comprising:

• at least one multi-stage processor;
• a memory coupled to the at least one multi-stage processor;
• and
• a storage medium coupled to the memory and the at least one multi-stage processor the storage medium comprising a set of processor executable instructions sufficient that when executed by the at least one multi-stage processor configure the custom computing apparatus to optimize a computer program for execution on a second computing apparatus, the computer program comprising at least one arbitrary loop nest, the second computing apparatus comprising at least two execution units, the configuration comprising a configuration to:
• receive a computer program in the memory;
• optimize the computer program for execution on the second computing apparatus, the optimization comprising optimizing a selective tradeoff of parallelism and locality costs of operations on the at least two execution units;
• and
• produce an optimized computer program for execution on the second computing apparatus,
• wherein the configuration for optimizing the selective tradeoff comprises a configuration to;
• assign 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;
• assign 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;
• assign 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;
• assign 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
• optimize a global weighted parametric function of the first cost, the second cost, the first decision variable and the second decision variable;
• determine a set of conditions that preserve the semantic correctness of the program;
• represent the set of conditions preserving semantic correctness in the form of a generalized dependence graph;
• and
• derive 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.