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

Patent metadata

Field	Value
Publication number	US-2016110176-A1
Application number	US-201514820998-A
Country	US
Kind code	A1
Filing date	Aug 7, 2015
Priority date	Oct 21, 2014
Publication date	Apr 21, 2016
Grant date	—

Abstract

The present disclosure relates generally to the field of automatic conversion of sequential array-based programs to parallel MapReduce programs. In various examples, automatic conversion of sequential array-based programs to parallel MapReduce programs may be implemented in the form of systems, methods and/or algorithms.

First claim

What is claimed is:

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 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 an executable parallel program.

2 . The method of claim 1 , wherein the replacing of the loop construct generates a plurality of unoptimized parallel programs.

3 . The method of claim 2 , further comprising:
generating, by the processor, a plurality of optimized and executable parallel programs based upon the unoptimized parallel programs; selecting, by the processor, one of the optimized and executable parallel programs; and translating, by the processor, the selected optimized and executable parallel program to another language.

4 . 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.

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

6 . The method of claim 5 , wherein at least one of:
(a) the translating translates the selected optimized and executable MapReduce program back to a high-level language; (b) the translating translates the selected optimized and executable MapReduce program to machine code; and (c) the translating translates the selected optimized and executable MapReduce program in a form for use in a hardware circuit.

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

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

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

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

11 . The method of claim 3 , 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 parallel programs are translated back to the first high-level language.

12 . The method of claim 3 , 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 parallel programs are translated back to a second high-level language that is different from the first high-level language.

13 . The method of claim 3 , wherein the selecting is performed via at least one of: (a) analysis of parallelism; (b) performance testing; or (c) any combination thereof.

Assignees

• IBM

Inventors

• Fink Stephen
• Rabbah Rodric
• Radoi Cosmin A
• Sridharan Manu

Classifications

• G06F8/51 Primary

  Source to source · CPC title

• G06F8/443

  Optimisation · CPC title

• G06F8/456 Primary

  Parallelism detection · CPC title

• G06F8/314

  Parallel programming languages (G06F8/313 takes precedence) · CPC title