Stream-based accelerator processing of computational graphs

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.

What is claimed is: 
     
         1 - 40 . (canceled) 
     
     
         41 . 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 system comprising a plurality of hardware streams, cause the system to perform program operations comprising:
 for each of a plurality of operations represented in a computational graph, assigning the operation to a respective stream in the plurality of streams of the system, each stream configured to queue operations assigned to the stream and to execute the queued operations in a defined order on a respective hardware resource for the stream;   configuring a first stream of the plurality of streams to stall performance of a first operation assigned to the first stream until all inputs to the first operation have been computed, wherein a first input to the first operation comprises an output of a second operation assigned to a second, different stream of the plurality of streams; and   performing, by each stream in the plurality of streams, the operations that were assigned to the stream in a defined order, including performing at least one operation by the first stream in parallel with at least one operation by the second stream.   
     
     
         42 . The computer program product of  claim 41 , the program operations further comprising:
 receiving, from a client, a request identifying one or more particular outputs from one or more operations represented in the computational graph; and   providing the one or more particular outputs to the client.   
     
     
         43 . The computer program product of  claim 41 , the program operations further comprising:
 receiving data that identifies a group of operations represented in the computational graph that are connected to each other by following one directed edge from operation to operation represented in the computational graph; and   assigning the group of operations to one stream.   
     
     
         44 . The computer program product of  claim 41 , wherein the assigning comprises:
 receiving data identifying a representation of a first operation in the computational graph having a plurality of directed edges as outputs; and   assigning, for each of the directed edges, a target operation to which the directed edge points to a unique hardware stream of the system, each target operation being assigned to a different unique hardware stream.   
     
     
         45 . The computer program product of  claim 41 , the program operations further comprising determining, for each of a plurality of nodes in the computational graph that represent respective ones of the plurality of operations, a respective amount of memory resources consumed by the operation represented by the node based on information about directed edges to the node, wherein assigning the operation represented by each node in the computational graph to a respective hardware stream is based at least on the respective amount of memory resources consumed by the operation represented by the node. 
     
     
         46 . The computer program product of  claim 41 , the program operations further comprising:
 determining a particular operation represented represented in the computational graph has finished at a particular hardware 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 operations, a respective estimated amount of memory that will be consumed by the unassigned operation;   determining, from the group of unassigned operations and using the respective estimated amount of memory that will be consumed by the unassigned operation, a first unassigned operation with the estimated amount of memory that maximizes usage of the first amount of memory; and   based on determining that the first unassigned operation maximizes usage of the first amount of memory, assigning the first unassigned operation to the particular hardware stream.   
     
     
         47 . The computer program product of  claim 42 , the program operations further comprising causing the system to store the one or more particular outputs in memory of a hardware accelerator. 
     
     
         48 . The computer program product of  claim 41 , the program operations further comprising:
 determining that a particular operation represented assigned to a particular hardware stream has finished execution; and   in response to determining that the particular operation has finished execution:
 identifying at least one subsequent operation that uses the output of the particular operation as input, and 
 reusing memory allocated for the output of the particular operation after the at least one subsequent operation has executed. 
   
     
     
         49 . The computer program product of  claim 41 , wherein assigning each operation in the computational graph to a respective stream in the plurality of streams comprises assigning operations so as to minimize a number of cross-stream directed edges, wherein a cross-stream directed edge is an instance of an input to an operation in one stream being received from an output of an operation in another stream. 
     
     
         50 . The computer program product of  claim 41 , wherein performing the operations represented by the nodes in the computational graph comprises:
 identifying, at a point immediately preceding performance of the first operation in the first stream, that the output of the second operation assigned to the second stream has not yet been computed; and   stalling performance of the first operation in the first stream until the output of the second operations from the second stream is available as input to the first operation in the first stream.   
     
     
         51 . The computer program product of  claim 50 , wherein stalling performance of the first operation in the first stream further stalls performance of additional operations downstream of the first operation in the first stream. 
     
     
         52 . The computer program product of  claim 41 , wherein the computational graph is a subgraph corresponding to a portion of a larger computational graph. 
     
     
         53 . A method performed by a system comprising a plurality of hardware streams, comprising:
 for each of a plurality of operations represented in a computational graph, assigning the operation to a respective stream in the plurality of streams of the system, each stream configured to queue operations assigned to the stream and to execute the queued operations in a defined order on a respective hardware resource for the stream;   configuring a first stream of the plurality of streams to stall performance of a first operation assigned to the first stream until all inputs to the first operation have been computed, wherein a first input to the first operation comprises an output of a second operation assigned to a second, different stream of the plurality of streams; and   performing, by each stream in the plurality of streams, the operations that were assigned to the stream in a defined order, including performing at least one operation by the first stream in parallel with at least one operation by the second stream.   
     
     
         54 . The method of  claim 53 , comprising:
 receiving, from a client, a request identifying one or more particular outputs from one or more operations represented in the computational graph; and   providing the one or more particular outputs to the client.   
     
     
         55 . The method of  claim 53 , comprising:
 receiving data that identifies a group of operations represented in the computational graph that are connected to each other by following one directed edge from operation to operation represented in the computational graph; and   assigning the group of operations to one stream.   
     
     
         56 . The method of  claim 53 , wherein the assigning comprises:
 receiving data identifying a representation of a first operation in the computational graph having a plurality of directed edges as outputs; and   assigning, for each of the directed edges, a target operation to which the directed edge points to a unique hardware stream of the system, each target operation being assigned to a different unique hardware stream.   
     
     
         57 . The method of  claim 53 , comprising determining, for each of a plurality of nodes in the computational graph that represent respective ones of the plurality of operations, a respective amount of memory resources consumed by the operation represented by the node based on information about directed edges to the node, wherein assigning the operation represented by each node in the computational graph to a respective hardware stream is based at least on the respective amount of memory resources consumed by the operation represented by the node. 
     
     
         58 . The method of  claim 53 , comprising:
 determining a particular operation represented in the computational graph has finished at a particular hardware 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 operations, a respective estimated amount of memory that will be consumed by the unassigned operation;   determining, from the group of unassigned operations and using the respective estimated amount of memory that will be consumed by the unassigned operation, a first unassigned operation with the estimated amount of memory that maximizes usage of the first amount of memory; and   based on determining that the first unassigned operation maximizes usage of the first amount of memory, assigning the first unassigned operation to the particular hardware stream.   
     
     
         59 . The method of  claim 54 , comprising causing the system to store the one or more particular outputs in memory of a hardware accelerator. 
     
     
         60 . A system comprising:
 a plurality of hardware streams; and   one or more non-transitory computer storage media encoded with instructions that, when executed, cause performance of operations comprising:
 for each of a plurality of operations represented in a computational graph, assigning the operation to a respective stream in the plurality of streams of the system, each stream configured to queue operations assigned to the stream and to execute the queued operations in a defined order on a respective hardware resource for the stream; 
 configuring a first stream of the plurality of streams to stall performance of a first operation assigned to the first stream until all inputs to the first operation have been computed, wherein a first input to the first operation comprises an output of a second operation assigned to a second, different stream of the plurality of streams; and 
 performing, by each stream in the plurality of streams, the operations that were assigned to the stream in a defined order, including performing at least one operation by the first stream in parallel with at least one operation by the second stream.