Systems and methods for processing machine learning algorithms in a MapReduce environment

• US 8,612,368 B2
• Filed: 03/01/2011
• Issued: 12/17/2013
• Est. Priority Date: 03/01/2011
• Status: Active Grant

• Current Assignee: SINOEAST CONCEPT LIMITED (Tencent Holdings Limited)
• Original Assignee: International Business Machines Corporation
• Inventors: Burdick, Douglas Ronald, Ghoting, Amol, Krishnamurthy, Rajasekar, Pednault, Edwin Peter Dawson, Reinwald, Berthold, Sindhwani, Vikas, Tatikonda, Shirish, Tian, Yuanyuan, Vaithyanathan, Shivakumar
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/038,086
• Publication Number:
  US 20120226639A1
• Time in Patent Office: 1,022 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

Systems and methods for processing Machine Learning (ML) algorithms in a MapReduce environment are described. In one embodiment of a method, the method includes receiving a ML algorithm to be executed in the MapReduce environment. The method further includes parsing the ML algorithm into a plurality of statement blocks in a sequence, wherein each statement block comprises a plurality of basic operations (hops). The method also includes automatically determining an execution plan for each statement block, wherein at least one of the execution plans comprises one or more low-level operations (lops). The method further includes implementing the execution plans in the sequence of the plurality of the statement blocks.

Claims

1. A computer implemented method for processing Machine Learning (ML) algorithms in a MapReduce environment, comprising:

receiving a ML algorithm to be executed in the MapReduce environment;

parsing the ML algorithm into a plurality of statement blocks in a sequence, wherein each statement block comprises a plurality of basic operations (hops);

automatically determining an execution plan for each statement block, wherein at least one of the execution plans comprises one or more low-level operations (lops), and wherein determining an execution plan for each statement block comprises translating a hop into at least one lop; and

implementing the execution plans in the sequence of the plurality of the statement blocks.

2. The computer implemented method of claim 1, wherein determining the execution plan for at least one of the statement blocks comprises:

analyzing the statement block to determine interconnections between the plurality of hops; and

using the interconnections to create a directed acyclic graph of the plurality of hops over at least one of matrices and scalars (HOPDag).

3. The computer implemented method of claim 2, wherein determining the execution plan for each statement block further comprises translating the HOPDag into at least one low-level physical execution plan (LOPDag) comprising a plurality of lops.

4. The computer implemented method of claim 3, wherein the LOPDag further comprises representations for scalar operations.

5. The computer implemented method of claim 1, wherein translating the hop into at least one lop comprises:

determining a plurality of groups of lops equivalent to the hop; and

using a cost-based optimization to select a group of lops from the plurality of groups of lops with an associated cost lower than an associated cost of at least one of the groups of lops.

6. The computer implemented method of claim 3, wherein determining the execution plan for each statement block further comprises converting the LOPDag into a representative workflow of MapReduce jobs, wherein converting the LOPDag comprises determining if a plurality of lops may be represented by one MapReduce job.

7. The computer implemented method of claim 6, wherein determining the execution plan for each statement block further comprises optimizing the HOPDag, wherein optimization of the HOPDag comprises at least one of algebraic rewrites and selection of physical representation for a plurality of intermediate matrices.

8. The computer implemented method of claim 6, wherein determining the execution plan for each statement block further comprises optimizing a LOPDag during translation of a HOPDag into the LOPDag by using cost-based optimization.

9. The computer implemented method of claim 1, wherein implementing the execution plans comprises managing execution of scalar operations by a control program and a plurality of workflows of MapReduce jobs on a cluster.

10. The computer implemented method of claim 9, wherein execution of the plurality of workflows of MapReduce jobs comprises using the type of statement block from which the workflow was created to determine if the workflow should be skipped in execution or repeated in execution.

11. The computer implemented method of claim 1, further comprising determining if a plurality of lops may be represented by one MapReduce job, wherein such determination comprises piggybacking lops into one MapReduce job based on the characteristics of the lops.

12. The computer implemented method of claim 11, further comprising creating the MapReduce job, wherein the MapReduce job is instantiated from a generic MapReduce job that is divided into at least three phases, each phase parameterized to execute multiple lops as per the piggybacking method.

13. The computer implemented method of claim 1, further comprising optimizing the execution plan, comprising optimizing size of a data block representation for implementing the ML algorithm.

14. The computer implemented method of claim 13, wherein the optimizing size of the data block representation relies on the local sparsity of each data block.

15. A computer program product comprising a non-transitory computer useable storage medium to store a computer readable program, wherein the computer readable program, when executed on a computer, causes the computer to perform operations for processing Machine Learning (ML) algorithms in a MapReduce environment, comprising:

receiving a ML algorithm to be executed in the MapReduce environment;

parsing the ML algorithm into a plurality of statement blocks in a sequence, wherein each statement block comprises a plurality of basic operations (hops);

automatically determining an execution plan for each statement block, wherein at least one of the execution plans comprises one or more low-level operations (lops), and wherein determining an execution plan for each statement block comprises translating a hop into at least one lop;

implementing the execution plans in the sequence of the plurality of the statement blocks; and

determining if a plurality of lops may be represented by one MapReduce job, wherein such determination comprises piggybacking lops into one MapReduce job based on the characteristics of the lops.

16. The computer program product of claim 15, wherein the computer readable program causes the computer to perform operations for determining the execution plan for at least one of the statement blocks comprising:

analyzing the statement block to determine interconnections between the plurality of hops; and

using the interconnections to create a directed acyclic graph of the plurality of hops over at least one of matrices and scalars (HOPDag).

17. The computer program product of claim 16, wherein the computer readable program causes the computer to perform operations for determining the execution plan for each statement block comprising translating the HOPDag into at least one low-level physical execution plan (LOPDag) comprising a plurality of lops.

18. The computer program product of claim 17, wherein the LOPDag further comprises representations for scalar operations.

19. The computer program product of claim 18, wherein the computer readable program causes the computer to perform operations for translating the HOPDag into at least one LOPDag comprising, for each hop implemented in the HOPDag, translating the hop into at least one lop.

20. The computer program product of claim 19, wherein the computer readable program causes the computer to perform operations for determining the execution plan for each statement block comprising converting the lops into MapReduce jobs, wherein converting the lops comprises determining if a plurality of lops may be represented by one MapReduce job.

21. The computer program product of claim 20, wherein the computer readable program causes the computer to perform operations for determining if the plurality of lops may be represented by one MapReduce job comprising piggybacking lops into one MapReduce job.

22. The computer program product of claim 19, wherein the computer readable program causes the computer to perform operations for determining the execution plan for each statement block comprising optimizing the HOPDag, wherein optimization of the HOPDag comprises at least one of algebraic rewrites and selection of physical representation for a plurality of intermediate matrices.

23. The computer program product of claim 19, wherein the computer readable program causes the computer to perform operations for determining the execution plan for each statement block comprising optimizing a LOPDag during translation of a HOPDag into the LOPDag, wherein such translation comprises:

determining a plurality of groups of lops equivalent to the hop; and

using a cost-based optimization to select a group of lops from the plurality of groups of lops with an associated cost lower than an associated cost of at least one of the groups of lops.

24. A system for processing Machine Learning (ML) algorithms in a MapReduce environment, comprising:

means for receiving a ML algorithm to be executed in the MapReduce environment;

means for parsing the ML algorithm into a plurality of statement blocks in a sequence, wherein each statement block comprises a plurality of basic operations (hops);

means for automatically determining an execution plan for each statement block, wherein at least one of the execution plans comprises one or more low-level operations (lops);

means for implementing the execution plans in the sequence of the plurality of the statement blocks;

means for optimizing the execution plan comprises means for optimizing size of a data block representation for implementing the ML algorithm.

25. The system of claim 24, wherein:

means for determining the execution plan for each statement block comprises means for creating a directed acyclic graph of the plurality of hops over at least one of matrices, vectors, and scalars (HOPDag);

means for determining the execution plan for each statement block comprises means for translating the HOPDag into at least one low-level physical execution plan (LOPDag) comprising a plurality of lops;

means for translating the HOPDag into at least one LOPDag comprises means for, for each hop implemented in the HOPDag, translating the hop into at least one lop; and

means for determining the execution plan for each statement block comprises means for converting the lops into a plurality of workflows of MapReduce jobs, wherein converting the lops comprises piggybacking a plurality of lops into one MapReduce job.