PROCESSING COMPUTATIONAL GRAPHS

• US 20170124452A1
• Filed: 10/28/2016
• Published: 05/04/2017
• Est. Priority Date: 10/28/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Tucker, Paul A., Dean, Jeffrey Adgate, Ghemawat, Sanjay, Yu, Yuan
• Granted Patent: US 10,860,925 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/045 Combinations of networks
• CPC Class Codes: G06N 3/063 using electronic means
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 3/098 Distributed learning, e.g. federated learning
• CPC Class Codes: G06N 5/048 Fuzzy inferencing

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for receiving a request from a client to process a computational graph; obtaining data representing the computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, wherein each directed edge connects a respective first node to a respective second node that represents an operation that receives, as input, an output of an operation represented by the respective first node; identifying a plurality of available devices for performing the requested operation; partitioning the computational graph into a plurality of subgraphs, each subgraph comprising one or more nodes in the computational graph; and assigning, for each subgraph, the operations represented by the one or more nodes in the subgraph to a respective available device in the plurality of available devices for operation.

Claims

1. A method comprising:

receiving a request from a client to process a computational graph;

obtaining data representing the computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, wherein each directed edge connects a respective first node to a respective second node that represents an operation that receives, as input, an output of an operation represented by the respective first node;

identifying a plurality of available devices for performing the requested operation;

partitioning the computational graph into a plurality of subgraphs, each subgraph comprising one or more nodes in the computational graph; and

assigning, for each subgraph, the operations represented by the one or more nodes in the subgraph to a respective available device in the plurality of available devices for processing.

2. The method of claim 1, wherein the request specifies one or more particular outputs from one or more respective nodes, further comprising:

receiving, from a device to which the one or more respective nodes are assigned, the one or more particular outputs; and

providing the one or more particular outputs to the client.

3. The method of claim 1, wherein the operations represented by the one or more nodes in the computational graph are inference or training operations for a neural network.

4. The method of claim 1, wherein the request comprises labels partitioning the computational graph into a plurality of predetermined subgraphs, and wherein partitioning the computational graph comprises partitioning the computational graph into the plurality of predetermined subgraphs.

5. The method of claim 1, wherein each device in the plurality of available devices is a hardware resource that performs operations independent of other devices in the plurality of available devices.

6. The method of claim 1, wherein assigning, for each subgraph, the operations represented by the one or more nodes in the subgraph to a respective device comprises assigning the operations to a device having a computational capability necessary to perform the operations represented by the nodes in the subgraph.

7. The method of claim 1, further comprising:

analyzing the computational graph to identify groups of nodes arranged in a chain structure;

wherein the partitioning comprises generating, for each identified group, a respective subgraph including the identified group of nodes.

8. The method of claim 1, further comprising:

analyzing the computational graph to identify groups of nodes that operate on shared data flowing on directed edges to the group of nodes;

wherein the partitioning comprises generating, for each identified group, a respective subgraph including the identified group of nodes.

9. The method of claim 1, further comprising:

determining an initial assignment of operations represented by one or more nodes in subgraphs to devices;

monitoring the devices to determine statistics;

adjusting the initial assignment using the statistics; and

reassigning the operations of the subgraphs to the devices based on the adjusted initial assignment.

10. The method of claim 9, further comprising repeating the monitoring, adjusting, and reassigning until a threshold amount of improvement has been achieved.

11. The method of claim 9, wherein the statistics comprise a respective operation time or a respective idle time for each subgraph.

12. A system comprising:

one or more computers; and

computer-readable medium coupled to the one or more computers and having instructions stored thereon, which, when executed by the one or more computers, cause the one or more computers to, for each of the neural network layers, perform operations comprising;

receiving a request from a client to process a computational graph;

obtaining data representing the computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, wherein each directed edge connects a respective first node to a respective second node that represents an operation that receives, as input, an output of an operation represented by the respective first node;

identifying a plurality of available devices for performing the requested operation;

partitioning the computational graph into a plurality of subgraphs, each subgraph comprising one or more nodes in the computational graph; and

assigning, for each subgraph, the operations represented by the one or more nodes in the subgraph to a respective available device in the plurality of available devices for processing.

13. The system of claim 12, the operations further comprising:

analyzing the computational graph to identify groups of nodes that operate on shared data flowing on directed edges to the group of nodes;

wherein the partitioning comprises generating, for each identified group, a respective subgraph including the identified group of nodes.

14. The system of claim 12, the operations further comprising:

determining an initial assignment of operations represented by one or more nodes in subgraphs to devices;

monitoring the devices to determine statistics;

adjusting the initial assignment using the statistics; and

reassigning the operations of the subgraphs to the devices based on the adjusted initial assignment.

15. The system of claim 14, the operations further comprising repeating the monitoring, adjusting, and reassigning until a threshold amount of improvement has been achieved.

16. The system of claim 14, wherein the statistics comprise a respective operation time or a respective idle time for each subgraph.

17. A computer-readable medium having instructions stored thereon, which, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving a request from a client to process a computational graph;

obtaining data representing the computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, wherein each directed edge connects a respective first node to a respective second node that represents an operation that receives, as input, an output of an operation represented by the respective first node;

identifying a plurality of available devices for performing the requested operation;

partitioning the computational graph into a plurality of subgraphs, each subgraph comprising one or more nodes in the computational graph; and

assigning, for each subgraph, the operations represented by the one or more nodes in the subgraph to a respective available device in the plurality of available devices for processing.

18. The computer-readable medium of claim 17, the operations further comprising:

determining an initial assignment of operations represented by nodes in subgraphs to devices;

monitoring the devices to determine statistics;

adjusting the initial assignment using the statistics; and

reassigning the operations to the devices based on the adjusted initial assignment.

19. The computer-readable medium of claim 18, the operations further comprising repeating the monitoring, adjusting, and reassigning until a threshold amount of improvement has been achieved.

20. The computer-readable medium of claim 18, wherein the statistics comprise a respective operation time or a respective idle time for each subgraph.

21. A method for processing a computational graph using a plurality of devices, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, wherein each directed edge connects a respective first node to a respective second node that represents an operation that receives, as input, an output of an operation represented by the respective first node, wherein the method comprises, for each of the plurality of devices:

receiving data representing a subgraph of the computational graph assigned to the device, the subgraph comprising a plurality of nodes representing operations and directed edges from the computational graph; and

performing the operations represented by the nodes in the subgraph.

22. The method of claim 21, further comprising:

receiving a request identifying one or more particular outputs from one or more respective nodes in the subgraph; and

providing the one or more particular outputs to a client.

23. The method of claim 21, further comprising:

monitoring statistics; and

providing the statistics to a client.

24. The method of claim 23, wherein the statistics comprise a respective operation time or a respective idle time for each subgraph.

25. The method of claim 21, wherein performing the operations represented by the nodes in the subgraph comprises performing the operations asynchronously.

26. The method of claim 25, wherein performing operations asynchronously comprises performing the operations using queues, non-blocking kernels, or both.