# US 2019/0317782 A1 · Parallel Processing of Data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0317782 A1
- Document ID: US20190317782A1
- Status: Published application
- Kind: A1
- Application number: 16/449,987
- Filed: 2019-06-24
- Published: 2019-10-17
- Earliest claimed: 2010-05-04
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: Craig D. Chambers; Ashish Raniwala; Frances J. Perry; Stephen R. Adams; Robert R. Henry; Robert Bradshaw; Nathan Weizenbaum
- Web page: https://patentgrep.com/patent/US20190317782A1

## CPC

- G06F 9/45504: {Abstract machines for program code execution, e.g. Java virtual machine [JVM], interpreters or emulators}
- G06F 8/314: {Parallel programming languages (G06F8/313 takes precedence)}
- G06F 8/34: Graphical or visual programming
- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead
- G06F 9/3851: {from multiple instruction streams, e.g. multistreaming}
- G06F 9/3885: {using a plurality of independent parallel functional units}
- G06F 9/44: Arrangements for executing specific programs
- G06F 9/445: Program loading or initiating (bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57)
- G06F 9/45533: {Hypervisors; Virtual machine monitors}
- G06F 9/4843: {by program, e.g. task dispatcher, supervisor, operating system}
- G06F 21/577: {Assessing vulnerabilities and evaluating computer system security}
- G06F 21/62: Protecting access to data via a platform, e.g. using keys or access control rules
- G06F 21/6218: {to a system of files or objects, e.g. local or distributed file system or database}
- G06F 9/30: Arrangements for executing machine instructions, e.g. instruction decode (for executing microinstructions G06F9/22)
- G06F 9/4494: {data driven}
- G06F 16/24532: {of parallel queries}
- G06F 16/24547: {Optimisations to support specific applications; Extensibility of optimisers}
- G06F 2221/034: Test or assess a computer or a system
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

(canceled)

### Claim 2

A computer-implemented method comprising:
obtaining multiple, parallel map operations and multiple, parallel reduce operations;
determining indexes for each of multiple map workers and each of multiple reduce workers;
generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations,
wherein the map function specifies which map operation of the multiple, parallel map operations to perform by map workers based on the indexes of the map workers and specifies which reduce operation of the multiple, parallel map operations to perform by reduce workers based on the indexes of the reduce workers; and
executing the single mapreduce operation based on the map function, the reduce function, and the indexes.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein executing the single mapreduce operation based on the map function, the reduce function, and the indexes comprises:
providing the map function to the map workers, wherein each of the map workers determines which of the map operations to perform based on the index of the map worker; and
providing the reduce function to the reduce workers, wherein each of the reduce workers determines which of the reduce operations to perform based on the index of the reduce worker.

### Claim 4 (depends on 2)

The computer-implemented method of claim 2, wherein determining indexes for each of multiple map workers and each of multiple reduce workers comprises:
for each of the map workers, assigning a unique number to the map worker.

### Claim 5 (depends on 2)

The computer-implemented method of claim 2, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the map function includes an if-then statement with the indexes as decision points to select one of the map operations.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, wherein indexes for two or more map workers correspond to a same map operation of the multiple, parallel map operations.

### Claim 7 (depends on 2)

The computer-implemented method of claim 2, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the reduce function includes an if-then statement with the indexes as decision points to select one of the reduce operations.

### Claim 8 (depends on 2)

The computer-implemented method of claim 2, wherein determining indexes for each of multiple map workers and each of multiple reduce workers comprises:
determining a number of the map workers to execute the single mapreduce operation based on a size of data associated with the single mapreduce operation.

### Claim 9

A system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
obtaining multiple, parallel map operations and multiple, parallel reduce operations;
determining indexes for each of multiple map workers and each of multiple reduce workers;
generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations,
wherein the map function specifies which map operation of the multiple, parallel map operations to perform by map workers based on the indexes of the map workers and specifies which reduce operation of the multiple, parallel map operations to perform by reduce workers based on the indexes of the reduce workers; and
executing the single mapreduce operation based on the map function, the reduce function, and the indexes.

### Claim 10 (depends on 9)

The system of claim 9, wherein executing the single mapreduce operation based on the map function, the reduce function, and the indexes comprises:
providing the map function to the map workers, wherein each of the map workers determines which of the map operations to perform based on the index of the map worker; and
providing the reduce function to the reduce workers, wherein each of the reduce workers determines which of the reduce operations to perform based on the index of the reduce worker.

### Claim 11 (depends on 9)

The system of claim 9, wherein determining indexes for each of multiple map workers and each of multiple reduce workers comprises:
for each of the map workers, assigning a unique number to the map worker.

### Claim 12 (depends on 9)

The system of claim 9, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the map function includes an if-then statement with the indexes as decision points to select one of the map operations.

### Claim 13 (depends on 9)

The system of claim 9, wherein indexes for two or more map workers correspond to a same map operation of the multiple, parallel map operations.

### Claim 14 (depends on 9)

The system of claim 9, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the reduce function includes an if-then statement with the indexes as decision points to select one of the reduce operations.

### Claim 15 (depends on 9)

The system of claim 9, wherein determining indexes for each of multiple map workers and each of multiple reduce workers comprises:
determining a number of the map workers to execute the single mapreduce operation based on a size of data associated with the single mapreduce operation.

### Claim 16

A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:
obtaining multiple, parallel map operations and multiple, parallel reduce operations;
determining indexes for each of multiple map workers and each of multiple reduce workers;
generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations,
wherein the map function specifies which map operation of the multiple, parallel map operations to perform by map workers based on the indexes of the map workers and specifies which reduce operation of the multiple, parallel map operations to perform by reduce workers based on the indexes of the reduce workers; and
executing the single mapreduce operation based on the map function, the reduce function, and the indexes.

### Claim 17 (depends on 16)

The medium of claim 16, wherein executing the single mapreduce operation based on the map function, the reduce function, and the indexes comprises:
providing the map function to the map workers, wherein each of the map workers determines which of the map operations to perform based on the index of the map worker; and
providing the reduce function to the reduce workers, wherein each of the reduce workers determines which of the reduce operations to perform based on the index of the reduce worker.

### Claim 18 (depends on 16)

The medium of claim 16, wherein determining indexes for each of multiple map workers and each of multiple reduce workers comprises:
for each of the map workers, assigning a unique number to the map worker.

### Claim 19 (depends on 16)

The medium of claim 16, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the map function includes an if-then statement with the indexes as decision points to select one of the map operations.

### Claim 20 (depends on 19)

The medium of claim 19, wherein indexes for two or more map workers correspond to a same map operation of the multiple, parallel map operations.

### Claim 21 (depends on 16)

The medium of claim 16, wherein generating, based on the indexes, a single mapreduce operation that includes a map function that implements the multiple, parallel map operations and a reduce function that implements the multiple, parallel reduce operations comprises:
generating the mapreduce operation such that the reduce function includes an if-then statement with the indexes as decision points to select one of the reduce operations.
