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

1. A method for automatic conversion of a sequential array-based program to a parallel program, the method comprising:

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

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

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

generating, by the processor, 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, by the processor, a plurality of operations performed by the optimized and executable parallel programs based upon the plurality of memory locations;

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

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

2. The method of claim 1 , further comprising:

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

3. The method of claim 2 , wherein the sequential array-based program of which the processor obtains an Array SSA representation is in a first high-level language and the optimized and executable parallel programs are translated back to the first high-level language.

4. The method of claim 2 , wherein the sequential array-based program of which the processor obtains an Array SSA representation is in a first high-level language and the optimized and executable parallel programs are translated back to a second high-level language that is different from the first high-level language.

5. The method of claim 2 , wherein the selecting is performed via: (a) analysis of parallelism; or (b) performance testing; or (c) any combination thereof.

6. The method 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.

7. The method of claim 6 , further comprising:

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

selecting, by the processor, one of the optimized and executable MapReduce programs; and

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

8. The method of claim 7 , 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.

9. The method of claim 7 , wherein the generating comprises applying optimizations comprising loop fusion to the unoptimized Lambda Calculus MapReduce programs.

10. The method of claim 1 , further comprising receiving, by the processor, the sequential array-based program.

11. The method of claim 10 , wherein the obtaining comprises transforming, by the processor, the received sequential array-based program into the Array SSA representation of the sequential array-based program.

12. The method of claim 1 , wherein the replacing is performed using term rewrite rules.