# US 2020/0401897 A1 · Modifying computational graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401897 A1 - Document ID: US20200401897A1 - Status: Published application - Kind: A1 - Application number: 17/015,196 - Filed: 2020-09-09 - Published: 2020-12-24 - Earliest claimed: 2015-10-28 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Vijay Vasudevan; Jeffrey Adgate Dean; Sanjay Ghemawat - Web page: https://patentgrep.com/patent/US20200401897A1 ## CPC - G06N 3/082: modifying the architecture, e.g. adding, deleting or silencing nodes or connections - 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)} - 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)} - G06F 9/547: {Remote procedure calls [RPC]; Web services} - G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} - G06N 3/04: Architecture, e.g. interconnection topology - G06N 3/045: Combinations of networks - G06N 3/063: using electronic means - G06N 3/084: Backpropagation, e.g. using gradient descent - G06N 3/098: Distributed learning, e.g. federated learning - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods, systems, and apparatus, including computer programs encoded on computer storage media, for modifying a computational graph to include send and receive nodes. Communication between unique devices performing operations of different subgraphs of the computational graph can be handled efficiently by inserting send and receive nodes into each subgraph. When executed, the operations that these send and receive nodes represent may enable pairs of unique devices to conduct communication with each other in a self-sufficient manner. This shifts the burden of coordinating communication away from the backend, which affords the system that processes this computational graph representation the opportunity to perform one or more other processes while devices are executing subgraphs. ## Claims ### Claim 1 (canceled) ### Claim 2 A computer-implemented method comprising: receiving, by a first component from a plurality of components in a system, a request to perform operations represented by two or more nodes in a first subgraph of a computational graph, the computational graph comprising a plurality of nodes and a plurality of directed edges, each node from the plurality of nodes representing a respective operation, each directed edge in the plurality of directed edges connecting 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 plurality of directed edges comprising one or more cross-device directed edges in the computational graph, each cross-device directed edge in the one or more cross-device directed edges being a directed edge that connects a respective first node to a respective second node that is assigned to a different device than the component to which the respective first node is assigned, the one or more cross-device directed edges comprising a first cross-device directed edge that connects a first node in the first subgraph assigned to the first component with a second node in a second subgraph assigned to a second, different component from the plurality of components in the system, and for each cross-device directed edge in the one or more cross-device directed edges, the computational graph includes a) a send node between the respective first node and the respective second node in the computational graph, and b) a receive node between the send node and the respective second node in the computational graph, wherein the second subgraph assigned to the second, different component was modified to comprise a first send node on the first cross-device directed edge between the first node and the second node, the first subgraph for the first component was modified to comprise a first receive node on the first cross-device directed edge between the first node and the first receive node, and the first receive node represents operations of receiving, from the first send node, data output by the second node assigned to the second, different component, and receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, data output by the second node assigned to the second, different component; and providing, using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 3 (depends on 2) The method of claim 2, wherein: the first component comprises a first device from a plurality of devices in the system; the second, different component comprises a second, different device from the plurality of devices in the system; receiving the data comprises receiving, by the first device using the operations represented by the first receive node and from the second, different device that used the operations represented by the first send node, the data output by the second node assigned to the second, different device; and providing the data comprises providing, by the first device using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 4 (depends on 2) The method of claim 2, wherein receiving the data output by the second node comprises receiving, from the second, different component, a tensor that was output by the second node assigned to the second, different component. ### Claim 5 (depends on 2) The method of claim 2, comprising: sending, using the operations represented by the first receive node and to the second, different component, a request for output of the operation represented by the first send node, wherein receiving, from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component is responsive to sending the request for output of the operation represented by the first send node. ### Claim 6 (depends on 2) The method of claim 2, wherein: the first component comprises first hardware resources included in one or more first machines; the second, different component comprises second hardware resources included in one or more second machines; and receiving the data output by the second node comprises receiving, by the first component and from the second, different component and according to a protocol that corresponds to each of the first hardware resources and the second hardware resources, the data output by the second node assigned to the second, different component. ### Claim 7 (depends on 2) The method of claim 2, wherein receiving the data output by the second node comprises receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component independently from operations represented by other send nodes and other receive nodes for cross-device directed edges other than the first cross-device directed edge. ### Claim 8 A system comprising one or more computers in one or more locations, the one or more computers having stored on them instructions operable to cause the system to perform actions comprising: receiving, by a first component from a plurality of components in a system, a request to perform operations represented by two or more nodes in a first subgraph of a computational graph, the computational graph comprising a plurality of nodes and a plurality of directed edges, each node from the plurality of nodes representing a respective operation, each directed edge in the plurality of directed edges connecting 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 plurality of directed edges comprising one or more cross-device directed edges in the computational graph, each cross-device directed edge in the one or more cross-device directed edges being a directed edge that connects a respective first node to a respective second node that is assigned to a different device than the component to which the respective first node is assigned, the one or more cross-device directed edges comprising a first cross-device directed edge that connects a first node in the first subgraph assigned to the first component with a second node in a second subgraph assigned to a second, different component from the plurality of components in the system, and for each cross-device directed edge in the one or more cross-device directed edges, the computational graph includes a) a send node between the respective first node and the respective second node in the computational graph, and b) a receive node between the send node and the respective second node in the computational graph, wherein the second subgraph assigned to the second, different component was modified to comprise a first send node on the first cross-device directed edge between the first node and the second node, the first subgraph for the first component was modified to comprise a first receive node on the first cross-device directed edge between the first node and the first receive node, and the first receive node represents operations of receiving, from the first send node, data output by the second node assigned to the second, different component, and receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, data output by the second node assigned to the second, different component; and providing, using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 9 (depends on 8) The system of claim 8, wherein: the first component comprises a first device from a plurality of devices in the system; the second, different component comprises a second, different device from the plurality of devices in the system; receiving the data comprises receiving, by the first device using the operations represented by the first receive node and from the second, different device that used the operations represented by the first send node, the data output by the second node assigned to the second, different device; and providing the data comprises providing, by the first device using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 10 (depends on 8) The system of claim 8, wherein receiving the data output by the second node comprises receiving, from the second, different component, a tensor that was output by the second node assigned to the second, different component. ### Claim 11 (depends on 8) The system of claim 8, the actions comprising: sending, using the operations represented by the first receive node and to the second, different component, a request for output of the operation represented by the first send node, wherein receiving, from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component is responsive to sending the request for output of the operation represented by the first send node. ### Claim 12 (depends on 8) The system of claim 8, wherein: the first component comprises first hardware resources included in one or more first machines; the second, different component comprises second hardware resources included in one or more second machines; and receiving the data output by the second node comprises receiving, by the first component and from the second, different component and according to a protocol that corresponds to each of the first hardware resources and the second hardware resources, the data output by the second node assigned to the second, different component. ### Claim 13 (depends on 8) The system of claim 8, wherein receiving the data output by the second node comprises receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component independently from operations represented by other send nodes and other receive nodes for cross-device directed edges other than the first cross-device directed edge. ### Claim 14 A non-transitory computer-readable storage device having instructions stored thereon that, when executed by a system of one or more computers, cause the system to perform actions comprising: receiving, by a first component from a plurality of components in a system, a request to perform operations represented by two or more nodes in a first subgraph of a computational graph, the computational graph comprising a plurality of nodes and a plurality of directed edges, each node from the plurality of nodes representing a respective operation, each directed edge in the plurality of directed edges connecting 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 plurality of directed edges comprising one or more cross-device directed edges in the computational graph, each cross-device directed edge in the one or more cross-device directed edges being a directed edge that connects a respective first node to a respective second node that is assigned to a different device than the component to which the respective first node is assigned, the one or more cross-device directed edges comprising a first cross-device directed edge that connects a first node in the first subgraph assigned to the first component with a second node in a second subgraph assigned to a second, different component from the plurality of components in the system, and for each cross-device directed edge in the one or more cross-device directed edges, the computational graph includes a) a send node between the respective first node and the respective second node in the computational graph, and b) a receive node between the send node and the respective second node in the computational graph, wherein the second subgraph assigned to the second, different component was modified to comprise a first send node on the first cross-device directed edge between the first node and the second node, the first subgraph for the first component was modified to comprise a first receive node on the first cross-device directed edge between the first node and the first receive node, and the first receive node represents operations of receiving, from the first send node, data output by the second node assigned to the second, different component, and receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, data output by the second node assigned to the second, different component; and providing, using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 15 (depends on 14) The computer-readable storage device of claim 14, wherein: the first component comprises a first device from a plurality of devices in the system; the second, different component comprises a second, different device from the plurality of devices in the system; receiving the data comprises receiving, by the first device using the operations represented by the first receive node and from the second, different device that used the operations represented by the first send node, the data output by the second node assigned to the second, different device; and providing the data comprises providing, by the first device using the operations represented by the first receive node, the data output by the second node as input to the operations represented by the first node. ### Claim 16 (depends on 14) The computer-readable storage device of claim 14, wherein receiving the data output by the second node comprises receiving, from the second, different component, a tensor that was output by the second node assigned to the second, different component. ### Claim 17 (depends on 14) The computer-readable storage device of claim 14, the actions comprising: sending, using the operations represented by the first receive node and to the second, different component, a request for output of the operation represented by the first send node, wherein receiving, from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component is responsive to sending the request for output of the operation represented by the first send node. ### Claim 18 (depends on 14) The computer-readable storage device of claim 14, wherein: the first component comprises first hardware resources included in one or more first machines; the second, different component comprises second hardware resources included in one or more second machines; and receiving the data output by the second node comprises receiving, by the first component and from the second, different component and according to a protocol that corresponds to each of the first hardware resources and the second hardware resources, the data output by the second node assigned to the second, different component. ### Claim 19 (depends on 14) The computer-readable storage device of claim 14, wherein receiving the data output by the second node comprises receiving, using the operations represented by the first receive node and from the second, different component that used the operations represented by the first send node, the data output by the second node assigned to the second, different component independently from operations represented by other send nodes and other receive nodes for cross-device directed edges other than the first cross-device directed edge.