US 12,217,177 B1Granted

Processing loops in computational graphs

AssigneeGoogle Inc.

InventorsYuan Yu, Jeffrey Adgate Dean

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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 one or more sets of nodes in the computational graph that (i) represent a respective control flow statement, (ii) include one or more respective first nodes assigned to a first device that represent one or more respective first operations of the control flow statement that are to be conditionally executed, (iii) include one or more respective second nodes assigned to a second device that represent one or more respective second operations that determine whether or not or how many times the one or more respective first operations are to be recursively or iteratively executed;
for each identified set of nodes:
generating a control flow state structure that includes one or more third nodes representing operations determined based on the one or more respective second operations and that provides, as output, a current state of recursion or iteration in the control flow statement;
inserting the control flow state structure between the one or more respective first nodes and one or more respective second nodes in the computational graph;
and
modifying the allocation to assign the control flow state structure to the respective first device while leaving the one or more respective second nodes assigned to the second device;
and
determining, by the first device, whether to execute the one or more respective first operations of the control flow statement based on the output of the control flow state structure.

7 more elements

A method comprising:

identifying, by a first device, an augmented version of a first portion of a computational graph, wherein:
the computational graph comprises a plurality of nodes that represent respective operations and directed edges that respectively connect pairs of nodes from the plurality of nodes and that represent a flow of data between the connected pairs of nodes,
the first portion of the computational graph is allocated to the first device and a second portion of the computational graph is allocated to a second device,
a control flow statement in the computational graph includes (i) a first set of nodes assigned to the first device as part of the allocation of the first portion of the computational graph to the first device, the first set of nodes representing a first set of operations that are to be conditionally executed and (ii) a second set of nodes assigned to the second device as part of the allocation of the second portion of the computational graph, the second set of nodes representing a second set of operations that determine whether or not or how many times the one or more respective first operations are to be recursively or iteratively executed;
and
the augmented version of the first portion of the computational graph includes a control flow state structure inserted between the first set of nodes and the second set of nodes in the computational graph, the control flow state structure allocated to the first device while the second set of nodes is assigned to the second device, the control flow state structure including a third set of nodes assigned to the first device that represent operations determined based on the second set of operations and that provide, as output, a current state of recursion or iteration in the control flow statement;
and
determining, by the first device, whether to execute the first set of operations of the control flow statement based on the output of the control flow state structure.

5 more elements

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:
identifying, by a first device, an augmented version of a first portion of a computational graph, wherein:
the computational graph comprises a plurality of nodes that represent respective operations and directed edges that respectively connect pairs of nodes from the plurality of nodes and that represent a flow of data between the connected pairs of nodes,
the first portion of the computational graph is allocated to the first device and a second portion of the computational graph is allocated to a second device,
a control flow statement in the computational graph includes (i) a first set of nodes assigned to the first device as part of the allocation of the first portion of the computational graph to the first device, the first set of nodes representing a first set of operations that are to be conditionally executed and (ii) a second set of nodes assigned to the second device as part of the allocation of the second portion of the computational graph, the second set of nodes representing a second set of operations that determine whether or not or how many times the one or more respective first operations are to be recursively or iteratively executed;
and
the augmented version of the first portion of the computational graph includes a control flow state structure inserted between the first set of nodes and the second set of nodes in the computational graph, the control flow state structure allocated to the first device while the second set of nodes is assigned to the second device, the control flow state structure including a third set of nodes assigned to the first device that represent operations determined based on the second set of operations and that provide, as output, a current state of recursion or iteration in the control flow statement;
and
determining, by the first device, whether to execute the first set of operations of the control flow statement based on the output of the control flow state structure.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 18/232,635Filed 10 Aug 2023 · continuation
Priority: 9 Nov 2015
Granted: 4 Feb 2025
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06N 3/08
Neural networks: learning methods
G06N 3/098
Learning methods: distributed learning, e.g. federated learning
G06F 9/5061
Allocation of resources, e.g. of the central processing unit [CPU]: partitioning or combining of resources
G06N 3/10
Neural networks: interfaces, programming languages or software development kits, e.g. for simulating neural networks

Family

Application62/253,075Us provisional application · filed 9 Nov 2015
Application15/346,626Parent of this continuation · filed 8 Nov 2016
Application16/986,974Parent of this continuation · filed 6 Aug 2020
US 10,769,521 B1Parent of this continuation · filed 8 Sep 2020
US 11,763,146 B1Parent of this continuation
US 12,217,177 B1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key