STREAM-BASED ACCELERATOR PROCESSING OF COMPUTATIONAL GRAPHS

• US 20170124451A1
• Filed: 10/27/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: Vasudevan, Vijay, Barham, Paul Ronald
• Granted Patent: US 11,151,446 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

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for receiving, by a computational graph system, a request to process a computational graph; obtaining data representing a subgraph of 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, the subgraph assigned to a first device by a placer in the computational graph system; determining that the first device comprises a hardware accelerator having a plurality of streams; in response to determining, generating instructions that when executed by the first device cause the first device to: assign the operation represented by each node in the subgraph to a respective stream; and perform the operations represented by the nodes in the subgraph in accordance with the assignment.

Claims

1. A method comprising:

receiving, by a computational graph system, a request to process a computational graph;

obtaining data representing a subgraph of 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, the subgraph assigned to a first device by a placer in the computational graph system;

determining that the first device comprises a hardware accelerator having a plurality of streams;

in response to determining that the first device comprises a hardware accelerator having a plurality of streams, generating instructions that when executed by the first device cause the first device to;

assign the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

perform the operations represented by the nodes in the subgraph in accordance with the assignment; and

providing the instructions and the data to the first device.

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

receiving, from the first device, 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 instructions further cause the first device to store the one or more particular outputs in memory of the first device.

4. The method of claim 1, wherein the operations for the subgraph comprise partial inference or training computations for a neural network.

5. The method of claim 1, further comprising:

analyzing the subgraph to identify a group of nodes in the subgraph in a chain structure;

wherein the instructions cause the first device to assign the group of nodes to one stream.

6. The method of claim 1, wherein the assigning comprises:

analyzing the subgraph to identify a first node in the subgraph having a plurality of directed edges as outputs;

wherein the instructions cause the first device to assign, for each of the directed edges, a node to which the directed edge points to a disjoint stream of the hardware accelerator.

7. The method of claim 1, wherein the instructions cause the first device to determine, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

8. The method of claim 1, wherein the instructions cause the first device to determine a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished;

determine a first amount of memory consumed by the particular operation that will be freed;

determine, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by an operation that is represented by the unassigned node;

determine, from the group of unassigned nodes, a first unassigned node that represents an operation, which executes on a stream of the hardware accelerator, with the estimated amount of memory that maximizes usage of the first amount of memory; and

assign an operation represented by the first unassigned node to the particular stream.

9. The method of claim 1, wherein the instructions cause the first device to determine a particular operation represented by a node has finished at a particular stream:

in response to determining the particular operation has finished;

determine at least one subsequent operation that uses the output of the particular operation as input; and

reuse memory allocated for the output of the particular operation after the at least one subsequent operation has executed.

10. The method of claim 9, wherein determining at least one subsequent operation that uses the output of the particular operation as input includes:

determining that at least two subsequent operations, a first operation in a first stream and a second operation in a second stream, use the output of the particular operation as input;

placing a first marker in a first stream that indicates when the first operation has used the particular operation as input;

placing a second marker in a second stream that indicates when the second operation has used the particular operation as input;

determining that both operations have used the particular operation upon indication from the first and second markers.

12. The system of claim 9, wherein the request specifies identifying one or more particular outputs from one or more respective nodes in the subgraph, further comprising:

receiving, from the first device, the one or more particular outputs; and

providing the one or more particular outputs to the client.

13. The system of claim 9, further comprising:

analyzing the subgraph to identify a group of nodes in the subgraph in a chain structure;

wherein the instructions cause the first device to assign the group of nodes to one stream.

14. The system of claim 9, wherein the assigning comprises:

analyzing the subgraph to identify a first node in the subgraph has a plurality of directed edges as outputs;

wherein the instructions cause the first device to assign, for each of the directed edges, a node to which the directed edge points to a unique stream of the hardware accelerator.

15. The system of claim 9, wherein the instructions cause the first device to determine, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

16. The system of claim 9, wherein the instructions cause the first device to determine a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished;

determine a first amount of memory consumed by the particular operation that will be freed;

determine, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by the unassigned node;

determine, from the group of unassigned nodes, a first unassigned node with the estimated amount of memory that maximizes usage of the first amount of memory; and

assign an operation represented by the first unassigned node to the particular stream.

18. The computer program product of claim 15, wherein the request specifies identifying one or more particular outputs from one or more respective nodes in the subgraph, further comprising:

receiving, from the first device, the one or more particular outputs; and

providing the one or more particular outputs to the client.

19. The computer program product of claim 15, further comprising:

analyzing the subgraph to identify a group of nodes in the subgraph in a chain structure;

wherein the instructions cause the first device to assign the group of nodes to one stream.

20. The computer program product of claim 15, wherein the assigning comprises:

analyzing the subgraph to identify a first node in the subgraph has a plurality of directed edges as outputs;

wherein the instructions cause the first device to assign, for each of the directed edges, a node to which the directed edge points to a unique stream of the hardware accelerator.

21. The computer program product of claim 15, wherein the instructions cause the first device to determine, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

22. The computer program product of claim 15, wherein the instructions cause the first device to determine a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished;

determine a first amount of memory consumed by the particular operation that will be freed;

determine, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by the unassigned node;

determine, from the group of unassigned nodes, a first unassigned node with the estimated amount of memory that maximizes usage of the first amount of memory; and

assign an operation represented by the first unassigned node to the particular stream.

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

25. The method of claim 21, further comprising:

receiving data identifying a group of nodes in the subgraph in a chain structure; and

assigning the group of nodes to one stream.

26. The method of claim 21, wherein the assigning comprises:

receiving data identifying a first node in the subgraph having a plurality of directed edges as outputs; and

assigning, for each of the directed edges, a node to which the directed edge points to a unique stream of the hardware accelerator.

27. The method of claim 21, further comprising determining, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

28. The method of claim 21, further comprising determining a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished, determining a first amount of memory consumed by the particular operation that will be freed;

determining, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by the unassigned node;

determining, from the group of unassigned nodes, a first unassigned node with the estimated amount of memory that maximizes usage of the first amount of memory; and

assigning an operation represented by the first unassigned node to the particular stream.

30. The computer program product of claim 27, 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 the client.

31. The computer program product of claim 27, further comprising:

receiving data identifying a group of nodes in the subgraph in a chain structure; and

assigning the group of nodes to one stream.

32. The computer program product of claim 27, wherein the assigning comprises:

receiving data identifying a first node in the subgraph having a plurality of directed edges as outputs; and

assigning, for each of the directed edges, a node to which the directed edge points to a unique stream of the hardware accelerator.

33. The computer program product of claim 27, further comprising determining, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

34. The computer program product of claim 27, further comprising determining a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished, determining a first amount of memory consumed by the particular operation that will be freed;

determining, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by the unassigned node;

determining, from the group of unassigned nodes, a first unassigned node with the estimated amount of memory that maximizes usage of the first amount of memory; and

assigning an operation represented by the first unassigned node to the particular stream.

36. The system of claim 33, 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 the client.

37. The system of claim 33, further comprising:

receiving data identifying a group of nodes in the subgraph in a chain structure; and

assigning the group of nodes to one stream.

38. The system of claim 33, wherein the assigning comprises:

receiving data identifying a first node in the subgraph having a plurality of directed edges as outputs; and

assigning, for each of the directed edges, a node to which the directed edge points to a unique stream of the hardware accelerator.

39. The system of claim 33, further comprising determining, for each node, a respective amount of memory resources in the hardware accelerator consumed by the operation represented by the node based on the directed edges to the node, wherein the assigning is based at least on the respective amount of memory resources.

40. The system of claim 33, further comprising determining a particular operation represented by a node has finished at a particular stream;

in response to determining the particular operation has finished, determining a first amount of memory consumed by the particular operation that will be freed;

determining, for each of a group of unassigned nodes, a respective estimated amount of memory consumed by the unassigned node;

determining, from the group of unassigned nodes, a first unassigned node with the estimated amount of memory that maximizes usage of the first amount of memory; and

assigning an operation represented by the first unassigned node to the particular stream.

11. 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, by a computational graph system, a request to process a computational graph;

obtaining data representing a subgraph of 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, the subgraph assigned to a first device by a placer in the computational graph system;

determining that the first device comprises a hardware accelerator having a plurality of streams;

in response to determining that the first device comprises a hardware accelerator having a plurality of streams, generating instructions that when executed by the first device cause the first device to;

assign the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

perform the operations represented by the nodes in the subgraph in accordance with the assignment; and

providing the instructions and the data to the first device.

17. A computer program product encoded on one or more non-transitory computer storage media, the computer program product comprising instructions that when executed by a hardware accelerator having a plurality of streams cause the hardware accelerator to perform operations comprising:

receiving, by a computational graph system, a request to process a computational graph;

obtaining data representing a subgraph of 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, the subgraph assigned to a first device by a placer in the computational graph system;

determining that the first device comprises a hardware accelerator having a plurality of streams;

in response to determining that the first device comprises a hardware accelerator having a plurality of streams, generating instructions that when executed by the first device cause the first device to;

assign the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

perform the operations represented by the nodes in the subgraph in accordance with the assignment; and

providing the instructions and the data to the first device.

23. A method comprising:

receiving, by a hardware accelerator having a plurality of streams, data representing a subgraph of a 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, the subgraph assigned to a hardware accelerator by a placer in a computational graph system;

assigning, by the hardware accelerator, the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

performing, by the hardware accelerator, the operations represented by the nodes in the subgraph in accordance with the assignment.

29. A computer program product encoded on one or more non-transitory computer storage media, the computer program product comprising instructions that, when executed by a computer comprising a hardware accelerator having a plurality of streams, cause the computer to perform operations comprising:

receiving data representing a subgraph of a 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, the subgraph assigned to a hardware accelerator by a placer in a computational graph system;

assigning the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

performing the operations represented by the nodes in the subgraph in accordance with the assignment.

35. A system comprising a hardware accelerator, wherein the hardware accelerator comprises a plurality of streams, and wherein the system is configured to perform operations comprising:

receiving data representing a subgraph of a 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, the subgraph assigned to a hardware accelerator by a placer in a computational graph system;

assigning the operation represented by each node in the subgraph to a respective stream in the plurality of streams of the hardware accelerator; and

performing the operations represented by the nodes in the subgraph in accordance with the assignment.