Splitting the computation space to optimize parallel code

An article of manufacture, comprising a machine-accessible medium including instructions that, if executed by a machine, will cause the machine to perform operations comprising:

• performing linear transformations of statements in code to generate linear expressions associated with the statements in code, wherein the statements in code are included in a plurality of outer-to-inner loops and comprise a computation-space;
• and
• generating parallel code using the linear expressions, wherein generating the parallel code includes
• splitting the computation-space of the statements in code into intervals using the linear expressions, wherein splitting the computation-space of the statements includes
• finding a leading induction variable for each of the statements, the leading induction variable comprising the induction variable for the statement with deepest depth,
• sorting the leading induction variables for each of the statements in topological order from outer-to-inner loops, and
• for each sorted leading induction variable,
• solving each linear expression associated with a statement that includes the sorted leading induction variable to generate one or more corresponding T-expressions, wherein the one or more T-expressions represent a solution of said linear expression,
• sorting the one or more T-expressions, and
• partitioning values of the sorted leading induction variable into intervals using the sorted one or more T-expressions, and
• generating parallel code for the intervals, each interval to be assigned to a processor core;
• and
• performing optimizations on the parallel code.

A computer system, comprising:

• a processor;
• a Dynamic Random Access Memory (DRAM) coupled to the processor;
• and
• a storage unit coupled to the processor, wherein the storage unit including instructions which when loaded into the DRAM and executed by the processor perform operations comprising:
• performing linear transformations of statements in code to generate linear expressions associated with the statements in code, wherein the statements in code are included in a plurality of outer-to-inner loops and comprise a computation-space;
• and
• generating parallel code using the linear expressions, wherein generating the parallel code includes
• splitting the computation-space of the statements in code into intervals using the linear expressions, wherein splitting the computation-space of the statements includes
• finding a leading induction variable for each of the statements, the leading induction variable comprising the induction variable for the statement with deepest depth,
• sorting the leading induction variables for each of the statements in topological order from outer-to-inner loops, and
• for each sorted leading induction variable,
• solving each linear expression associated with a statement that includes the sorted leading induction variable to generate one or more corresponding T-expressions, wherein the one or more T-expressions represent a solution of said linear expression,
• sorting the one or more T-expressions, and
• partitioning values of the sorted leading induction variable into intervals using the sorted one or more T-expressions, and
• generating parallel code for the intervals, each interval to be assigned to a processor core;
• and
• performing optimizations on the parallel code.