# US 10,769,521 B1 · Processing loops in computational graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,769,521 B1 - Document ID: US10769521B1 - Status: Granted - Kind: B1 - Application number: 15/346,626 - Filed: 2016-11-08 - Granted: 2020-09-08 - Earliest claimed: 2015-11-09 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Yuan Yu; Jeffrey Adgate Dean - Web page: https://patentgrep.com/patent/US10769521B1 ## CPC - G06N 3/08: Learning methods - G06N 3/098: Distributed learning, e.g. federated learning - G06F 9/5061: {Partitioning or combining of resources} - G06N 3/10: Interfaces, programming languages or software development kits, e.g. for simulating neural networks - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems and methods for processing loops in computational graphs representing machine learning models are disclosed. An example method begins with obtaining data representing a computational graph. Data identifying an allocation of the computational graph across devices is obtained. Additionally, one or more nodes in the computational graph that represent a respective control flow statement are identified. For each identified node, a structure of nodes and edges that represents an operation that provides a current state of recursion or iteration in the respective control flow statement is generated. This structure is inserted into the computational graph and the allocation of nodes to devices is modified to assign the structure to a device. ## Claims ### Claim 1 A method comprising: obtaining data representing a computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, and 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; obtaining data identifying an allocation of the computational graph across a plurality of devices, wherein the allocation assigns each node in the computational graph to a respective device of the plurality of devices; identifying a set of nodes in the computational graph that: (i) represents a control flow statement, (ii) includes one or more first nodes assigned to a first device that represent one or more first operations of the control flow statement that are to be conditionally executed, and (iii) includes one or more second nodes assigned to a second device that represent one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed; generating a control flow state structure of nodes and directed edges, wherein generating the control flow state structure comprises: generating nodes representing the one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed, and that are assigned to the second device, and adding the nodes into the control flow state structure; inserting the control flow state structure between the one or more first nodes and the one or more second nodes in the computational graph; and modifying the allocation to assign the one or more first nodes and the control flow state structure to the first device while still assigning the one or more second nodes that represent the one or more second operations to the second device. ### Claim 2 (depends on 1) The method of claim 1, wherein the one or more second operations represented by the one or more second nodes provide a Boolean value as output. ### Claim 3 (depends on 2) The method of claim 2, wherein the Boolean value indicates whether recursion or iteration of the control flow statement is to continue or terminate. ### Claim 4 (depends on 2) The method of claim 2, further comprising: inserting a directed edge between the one or more second nodes and the control flow state structure that enables the operations represented by the nodes of the control flow state structure to receive, as input, the Boolean value output by the one or more second operations represented by the one or more second nodes. ### Claim 5 (depends on 1) The method of claim 1, further comprising: executing the computational graph across the plurality of devices, wherein as a consequence of executing the computational graph, the first device and the second device independently perform the one or more second operations. ### Claim 6 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 data representing a computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, and 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; obtaining data identifying an allocation of the computational graph across a plurality of devices, wherein the allocation assigns each node in the computational graph to a respective device of the plurality of devices; identifying a set of nodes in the computational graph that: (i) represents a control flow statement, (ii) includes one or more first nodes assigned to a first device that represent one or more first operations of the control flow statement that are to be conditionally executed, and (iii) includes one or more second nodes assigned to a second device that represent one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed; generating a control flow state structure of nodes and directed edges, wherein generating the control flow state structure comprises: generating nodes representing the one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed, and that are assigned to the second device, and adding the nodes into the control flow state structure; inserting the control flow state structure between the one or more first nodes and the one or more second nodes in the computational graph; and modifying the allocation to assign the one or more first nodes and the control flow state structure to the first device while still assigning the one or more second nodes that represent the one or more second operations to the second device. ### Claim 7 (depends on 6) The system of claim 6, wherein the one or more second operations represented by the one or more second nodes provide a Boolean value as output. ### Claim 8 (depends on 6) The system of claim 6, wherein a Boolean value indicates whether recursion or iteration of the control flow statement is to continue or terminate. ### Claim 9 (depends on 6) The system of claim 6, the operations further comprising: inserting a directed edge between the one or more second nodes and the control flow state structure that enables the operations represented by the nodes of the control flow state structure to receive, as input, the Boolean value output by the one or more second operations represented by the one or more second nodes. ### Claim 10 (depends on 6) The system of claim 6, wherein the operations further comprise: executing the computational graph across the plurality of devices, wherein as a consequence of executing the computational graph, the first device and the second device independently perform the one or more second operations. ### Claim 11 A non-transitory computer-readable storage medium comprising instructions stored thereon that are executable by a processing device and upon such execution cause the processing device to perform operations comprising: obtaining data representing a computational graph, the computational graph comprising a plurality of nodes and directed edges, wherein each node represents a respective operation, and 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; obtaining data identifying an allocation of the computational graph across a plurality of devices, wherein the allocation assigns each node in the computational graph to a respective device of the plurality of devices; identifying a set of nodes in the computational graph that: (i) represents a control flow statement, (ii) includes one or more first nodes assigned to a first device that represent one or more first operations of the control flow statement that are to be conditionally executed, and (iii) includes one or more second nodes assigned to a second device that represent one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed; generating a control flow state structure of nodes and directed edges, wherein generating the control flow state structure comprises: generating nodes representing the one or more second operations that determine how many times the one or more first operations are to be recursively or iteratively executed, and that are assigned to the second device, and adding the nodes into the control flow state structure; inserting the control flow state structure between the one or more first nodes and the one or more second nodes in the computational graph; and modifying the allocation to assign the one or more first nodes and the control flow state structure to the first device while still assigning the one or more second nodes that represent the one or more second operations to the second device. ### Claim 12 (depends on 11) The non-transitory computer readable storage medium of claim 11, wherein the one or more second operations represented by the one or more respective second nodes provide a Boolean value as output. ### Claim 13 (depends on 11) The non-transitory computer readable storage medium of claim 11, wherein a Boolean value indicates whether recursion or iteration of the control flow statement is to continue or terminate. ### Claim 14 (depends on 11) The non-transitory computer readable storage medium of claim 11, the operations further comprising: inserting a directed edge between the one or more second nodes and the control flow state structure that enables the operations represented by the nodes of the control flow state structure to receive, as input, the Boolean value output by the one or more second operations represented by the one or more second nodes. ### Claim 15 (depends on 11) The non-transitory computer readable storage medium of claim 11, wherein the operations further comprise: executing the computational graph across the plurality of devices, wherein as a consequence of executing the computational graph, the first device and the second device independently perform the one or more second operations.