Automatic conversion of sequential array-based programs to parallel map-reduce programs

1. A computer program product comprising a physical memory configured for automatic conversion of a sequential array-based program to a parallel program, the program code of the computer program product executable by at least one computer to perform a method comprising:

obtaining an Array static single assignment (SSA) representation of the sequential array-based program;

transforming the Array SSA representation into a Lambda Calculus representation that includes a construct for representing loops; and

replacing the loop construct with a plurality of operators to generate a plurality of unoptimized parallel programs comprising a plurality of operations;

generating a plurality of optimized and executable parallel programs based upon the unoptimized parallel programs, wherein the plurality of optimized and executable parallel programs are configured for accessing a plurality of memory locations including at least two overlapping memory locations;

grouping a plurality of operations performed by the optimized and executable parallel programs based upon the plurality of memory locations;

ranking the optimized and executable parallel programs by applying the grouped plurality of operations to a customizable cost function; and

performing a heuristic search to select one of the optimized and executable parallel programs from the plurality of optimized and executable parallel programs.

2. The computer program product of claim 1 , wherein the program code of the computer program product, when executing, further performs the step of:

translating the selected optimized and executable parallel program to another language.

3. The computer program product of claim 1 , wherein, the replacing of the loop construct uses a plurality of MapReduce operators to generate a plurality of unoptimized Lambda Calculus MapReduce programs.

4. The computer program product of claim 3 , wherein the program code of the computer program product, when executing, further performs:

generating a plurality of optimized and executable MapReduce programs based upon the unoptimized Lambda Calculus MapReduce programs;

selecting one of the optimized and executable MapReduce programs; and

translating the selected optimized and executable MapReduce program to another language.

5. The computer program product of claim 4 , wherein:

(a) the translating translates the selected optimized and executable MapReduce program back to a high-level language; and

(b) the translating translates the selected optimized and executable MapReduce program in a form for use in a hardware circuit.

6. A computer-implemented system for automatic conversion of a sequential array-based program to a parallel program, the system comprising a memory operatively coupled to a processor and configured to provide:

an obtaining element configured to obtain an Array static single assignment (SSA) representation of the sequential array-based program;

a transforming element configured to transform the Array SSA representation into a Lambda Calculus representation that includes a construct for representing loops; and

a replacing element configured to replace the loop construct with a plurality of operators to generate a plurality of unoptimized parallel programs comprising a plurality of operations;

a generating element configured to generate a plurality of optimized and executable parallel programs based upon the unoptimized parallel programs, wherein the plurality of optimized and executable parallel programs are configured for accessing a plurality of memory locations including at least two overlapping memory locations;

a grouping element configured to group a plurality of operations performed by the optimized and executable parallel programs based upon the plurality of memory locations;

a ranking element configured to rank the optimized and executable parallel programs by applying the grouped plurality of operations to a customizable cost function; and

a selecting element configured to perform a heuristic search to select one of the optimized and executable parallel programs from the plurality of optimized and executable parallel programs.

7. The system of claim 6 , further comprising:

a translating element configured to translate the selected optimized and executable parallel program to another language.

8. The system of claim 6 , wherein, the replacing of the loop construct uses a plurality of MapReduce operators to generate a plurality of unoptimized Lambda Calculus MapReduce programs.

9. The system of claim 8 , wherein:

the generating element is further configured to generate a plurality of optimized and executable MapReduce programs based upon the unoptimized Lambda Calculus MapReduce programs;

the selecting element is further configured to select one of the optimized and executable MapReduce programs; and

a translating element is configured to translate the selected optimized and executable MapReduce program to another language.

10. The system of claim 9 , wherein:

(a) the translating element is configured to translate the selected optimized and executable MapReduce program back to a high-level language; and

(b) the translating element is configured to translate the selected optimized and executable MapReduce program in a form for use in a hardware circuit.