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

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.