Parallel processing of data

• US 9,626,202 B2
• Filed: 02/13/2015
• Issued: 04/18/2017
• Est. Priority Date: 05/04/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chambers, Craig D., Raniwala, Ashish, Perry, Frances J., Adams, Stephen R., Henry, Robert R., Bradshaw, Robert, Weizenbaum, Nathan
• Primary Examiner(s): DAO, THUY CHAN
• Application Number:
  US14/622,556
• Publication Number:
  US 20150248304A1
• Time in Patent Office: 795 Days
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 21/577 Assessing vulnerabilities and evaluating computer system security
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06F 8/314 Parallel programming languages G06F8/313 takes precedence
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06F 9/45504 Abstract machines for programme code execution, e.g. Java virtual machine [JVM], interpreters, emulators
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A data parallel pipeline may specify multiple parallel data objects that contain multiple elements and multiple parallel operations that operate on the parallel data objects. Based on the data parallel pipeline, a dataflow graph of deferred parallel data objects and deferred parallel operations corresponding to the data parallel pipeline may be generated and one or more graph transformations may be applied to the dataflow graph to generate a revised dataflow graph that includes one or more of the deferred parallel data objects and deferred, combined parallel data operations. The deferred, combined parallel operations may be executed to produce materialized parallel data objects corresponding to the deferred parallel data objects.

Claims

1. A computer-implemented method executed by one or more processors, the method comprising:

executing a deferred operation included in a dataflow graph for a data parallel pipeline to produce materialized data objects corresponding to the deferred operation, including;

determining an estimated size of data associated with the deferred operation;

determining that the estimated size exceeds a data size threshold;

in response to determining that the estimated size exceeds the data size threshold, executing the deferred operation as a remote parallel operation with the one or more processors,

wherein determining the dataflow graph for the data parallel pipeline includes analyzing sequential programming language instructions associated with the data parallel pipeline, and

wherein the materialized data objects are configured to be accessed during execution of a program corresponding to the sequential programming language instructions associated with the data parallel pipeline.

2. The method of claim 1, wherein the deferred operation is a first deferred operation and the dataflow graph includes a second deferred operation, the method further comprising:

executing the second deferred operation to produce materialized data objects corresponding to the second deferred operation, including;

determining an estimated size of data associated with the second deferred operation;

determining that the estimated size is below the data size threshold;

in response to determining that the estimated size is below the data size threshold, executing the second deferred operation as a sequential local operation.

3. The method of claim 1, wherein the materialized data objects corresponding to the deferred operation include one or more of input data for the deferred operation, intermediary data produced by the deferred operation, or output data produced by the deferred operation.

4. The method of claim 1, wherein

the deferred operation is a generalized mapreduce operation including multiple, parallel map operations and multiple, parallel reduce operations and being translatable to a single mapreduce operation that includes a single map function to implement the multiple, parallel map operations and a single reduce function to implement the multiple, parallel reduce operations;

and

executing the deferred operation includes translating the generalized mapreduce operation to the single mapreduce operation and executing the single mapreduce operation.

5. The method of claim 4, wherein executing the deferred operation as a remote parallel operation includes causing the single mapreduce operation to be copied and executed on multiple, different processing modules in a datacenter.

6. The method of claim 4, wherein translating the generalized mapreduce operation to the single mapreduce operation includes generating a map function that includes the multiple, parallel map operations and a reducer function that includes the multiple, parallel reduce operations.

7. The method of claim 1, wherein determining the estimated size of data associated with the deferred operation includes accessing annotations in the dataflow graph that represent an estimate of the size of the data associated with the deferred operation.

8. The method of claim 1, wherein the sequential programming language instructions include Java programming language instructions.

9. A computer-implemented method executed by one or more processors, the method comprising:

determining a dataflow graph for a data parallel operation, the dataflow graph including at least one deferred operation including a generalized mapreduce operation, the generalized mapreduce operation including multiple, parallel map operations and multiple, parallel reduce operations and being translatable to a single mapreduce operation that includes a single map function to implement the multiple, parallel map operations and a single reduce function to implement the multiple, parallel reduce operations; and

executing the deferred operation to produce materialized parallel data objects corresponding to the deferred parallel data objects, including translating the generalized mapreduce operation to the single mapreduce operation and executing the single mapreduce operation,

wherein executing the single mapreduce operation includes causing multiple map worker processes to be invoked for each of the map operations, wherein each of the multiple map worker processes is assigned an index number.

10. The method of claim 9, wherein translating the generalized mapreduce operation to the single mapreduce operation includes generating a map function that includes the multiple map operations and a reduce function that includes the multiple reduce operations.

11. The method of claim 10, wherein the executing the single mapreduce operation includes executing the single mapreduce operation as a remote, parallel operation.

12. The method of claim 11 wherein executing the single mapreduce operation as a remote, parallel operation includes causing the single mapreduce operation to be executed by multiple worker processes on multiple, different processing modules.

13. The method of claim 9 wherein each of the map worker processes are configured to:

receive the map function that implements the multiple map operations, one or more inputs associated with one of the map operations, and the map worker process'"'"' associated index,

select the map operation associated with the inputs based on the map worker process'"'"' associated index, and

invoke the selected map operation on the one or more inputs.

14. A computer-implemented method executed by one or more processors, the method comprising:

determining a dataflow graph for a data parallel operation, the dataflow graph including at least one deferred operation including a generalized mapreduce operation, the generalized mapreduce operation including multiple, parallel map operations and multiple, parallel reduce operations and being translatable to a single mapreduce operation that includes a single map function to implement the multiple, parallel map operations and a single reduce function to implement the multiple, parallel reduce operations; and

executing the deferred operation to produce materialized parallel data objects corresponding to the deferred parallel data objects, including translating the generalized mapreduce operation to the single mapreduce operation and executing the single mapreduce operation,

wherein executing the single mapreduce operation includes causing multiple reduce worker processes to be invoked for each of the reduce operations, wherein each of the multiple reduce worker processes is assigned an index number.

15. The method of claim 14 wherein each of the multiple reduce worker processes are configured to:

receive the reduce function that implements the multiple reduce operations, one or more inputs associated with one of the reduce operations, and the reduce worker process'"'"' associated index,

select the reduce operation associated with the inputs based on the worker process'"'"' associated index, and

invoke the selected reduce operation on the one or more inputs.

16. The method of claim 14, wherein translating the generalized mapreduce operation to the single mapreduce operation includes generating a map function that includes the multiple map operations and a reduce function that includes the multiple reduce operations.

17. The method of claim 14, wherein the executing the single mapreduce operation includes executing the single mapreduce operation as a remote, parallel operation.

18. The method of claim 17, wherein executing the single mapreduce operation as a remote, parallel operation includes causing the single mapreduce operation to be executed by the multiple worker processes on multiple, different processing modules.