Granted Patent B2

US 12,547,468 · App. 17/957,646 · Granted Feb 10, 2026

Inventor: Garth Allen Dickie (Framingham, MA)

Assignee: Ab Initio Technology LLC

G06F9/5066G06F9/5038

Abstract

Claims (87)

1 . A method, comprising:

using at least one computer hardware processor to perform:

obtaining information specifying a dataflow graph, the dataflow graph comprising nodes and edges connecting the nodes, the edges representing flows of data among the nodes, the nodes comprising:

a first set of one or more nodes, each node in the first set of one or more nodes representing a respective input dataset in a set of one or more input datasets;

a second set of one or more nodes, each node in the second set of one or more nodes representing a respective output dataset in a set of one or more output datasets; and

a third set of nodes representing data processing operations, each node in the third set of nodes representing at least one of the data processing operations;

obtaining a first set of one or more processing layouts for the set of one or more input datasets and a second set of one or more processing layouts for the set of one or more output datasets, the first set of one or more processing layouts including processing layouts having different degrees of parallelism and/or the second set of one or more processing layouts having different degrees of parallelism, wherein each processing layout in the first and second sets of one or more processing layouts specifies, for a particular node in the first or second set of one or more nodes, a respective degree of parallelism to be used for performing an operation represented by the particular node;

determining processing layouts for nodes in the third set of nodes using: (a) the first set of one or more processing layouts, (b) the second set of one or more processing layouts, (c) one or more layout determination rules including at least one rule for selecting among processing layouts having different degrees of parallelism, and (d) information indicating that data generated by at least one node in the first set of one or more nodes and/or third set of nodes is not used by any nodes in the dataflow graph downstream from the at least one node, wherein determining the processing layouts for the nodes in the third set of nodes comprises:

identifying the at least one node whose data is not used by any nodes in the dataflow graph downstream from the at least one node during a forward pass starting from nodes in the first set of one or more nodes or a backward pass starting from nodes in the second set of one or more nodes; and

after determining the processing layout for each node in the dataflow graph, executing the dataflow graph in accordance with processing layouts determined for each node in the dataflow graph, the executing comprising:

reading input data from the set of the one or more input datasets represented by the first set of one or more nodes in accordance with the first set of one or more processing layouts;

processing the input data using the data processing operations represented by the third set of nodes in accordance with the processing layouts determined for the nodes in the third set of nodes; and

writing output data obtained as a result of performing the data processing operations to the set of one or more output datasets represented by the second set of one or more nodes in accordance with the second set of one or more processing layouts.

2 . The method of claim 1 , wherein determining the processing layouts is performed using two layout propagation passes by:

in the forward pass starting from nodes in the first set of one or more nodes and in accordance with structure of the dataflow graph, determining one or more initial processing layouts for one or more nodes in the third set of nodes by using the first set of one or more processing layouts, the one or more layout determination rules, and the information indicating that the data generated by the at least one node is not used by any nodes in the dataflow graph downstream from the at least one node; and

in the backward pass, starting from nodes in the second set of one or more nodes and in accordance with the structure of the dataflow graph, determining the processing layouts for one or more nodes in the third set of nodes, by using the second set of one or more processing layouts, the one or more initial processing layouts, and the one or more layout determination rules.

3 . The method of claim 2 , wherein a processing layout associated with the at least one node whose data is not used by any nodes in the dataflow graph downstream from the at least one node is not propagated, during the forward pass, to one or more nodes downstream from the at least one node in the dataflow graph.

4 . The method of claim 3 , wherein a processing layout associated with the at least one node whose data is not used by any nodes in the dataflow graph downstream from the at least one node is not propagated, during the backward pass, to one or more nodes upstream from the at least one node in the dataflow graph.

5 . The method of claim 1 , further comprising:

determining, based on processing layouts for nodes in the first set of one or more nodes, the second set of one or more nodes, and the third set of nodes, whether the dataflow graph is to be processed as a micrograph,

wherein determining whether the dataflow graph is to executed as a micrograph comprises: determining to execute the dataflow graph as a micrograph when the processing layouts for the first set of one or more nodes, the second set of one or more nodes, and the third set of nodes have a same degree of parallelism.

6 . The method of claim 2 , wherein the third set of nodes comprises a first node, wherein the edges comprise a first edge between the first node and a second node preceding the first node in the dataflow graph, and wherein determining the one or more initial processing layouts for the one or more nodes in the third set of nodes during the forward pass comprises:

determining a first initial processing layout for the first node based on a second initial processing layout determined for the second node.

7 . The method of claim 6 , wherein the edges comprise a second edge between the first node and a third node preceding the first node in the dataflow graph, wherein a third initial processing layout is associated with the third node, and wherein determining the first initial processing layout for the first node comprises:

selecting, as the first initial processing layout, either the second initial processing layout determined for the second node or a third initial processing layout determined for the third node.

8 . The method of claim 7 , wherein the second initial processing layout specifies a first degree of parallelism, wherein the third initial processing layout specifies a second degree of parallelism different from the first degree of parallelism, and wherein the selecting comprises:

selecting the second initial processing layout when the first degree of parallelism is greater than the second degree of parallelism; and

selecting the third initial processing layout when the first degree of parallelism is less than the second degree of parallelism.

9 . The method of claim 7 , wherein the second initial processing layout and the third initial processing layout each specifies a parallel processing layout with a same or different degree of parallelism, wherein the first edge represents a data flow for a first number of data records, wherein the second edge represents a data flow for a second number of data records, and wherein the selecting comprises:

selecting the second initial processing layout when the first number of data records is greater than the second number of data records; and

selecting the third initial processing layout when the first number of data records is less than the second number of data records.

10 . The method of claim 1 ,

wherein, during the determining, a first processing layout is determined for a first node in third set of nodes, the first processing layout specifying a first degree of parallelism,

wherein a second processing layout for a second node immediately preceding the first node in the dataflow graph specifies a second degree of parallelism different from the first degree of parallelism, and

wherein the method further comprises configuring at least one node of the dataflow graph to perform at least one repartitioning operation.

11 . The method of claim 1 ,

wherein, during the determining, a first processing layout is determined for a first node in third set of nodes, the first processing layout specifying a first degree of parallelism,

wherein a second processing layout for a second node immediately preceding the first node in the dataflow graph specifies a second degree of parallelism different from the first degree of parallelism, and

wherein the method further comprises adding, to the dataflow graph, a new node between the first node and the second node, the new node representing at least one repartitioning operation.

12 . The method of claim 1 , wherein a processing layout for a node representing an operation specifies a degree of parallelism to be used for performing the operation.

13 . The method of claim 1 , wherein the determining of the processing layouts for nodes in the third set of nodes comprises:

determining an initial processing layout for each particular node of at least some of the third set of nodes in the forward pass performed starting from nodes in the first set of one or more nodes in accordance with structure of the dataflow graph and using the first set of one or more processing layouts and the one or more layout determination rules, such that, for each particular node, a processing layout of a node preceding the particular node in the dataflow graph is selected during the forward pass as the initial processing layout for the particular node, wherein in case of multiple nodes preceding the particular node in the dataflow graph:

a parallel processing layout of one of the multiple preceding nodes is selected during the forward pass as the initial processing layout of the particular node if the processing layouts of other nodes of the multiple preceding nodes are serial, or

the processing layout of the one of the multiple preceding nodes being used to process a largest number of records is selected during the forward pass as the initial processing layout of the particular node,

as indicated by the at least one rule.

14 . The method of claim 13 , wherein the processing layout of the one of the multiple preceding nodes being used to process the largest number of records is selected during the forward pass as the initial processing layout, if the multiple nodes preceding the particular node in the dataflow graph only have serial processing layouts or only have multiple parallel processing layouts with the same or different degree of parallelism among each other.

15 . The method of claim 13 , wherein a processing layout associated with the at least one node is disregarded when selecting the initial processing layout of the particular node during the forward pass.

16 . The method of claim 13 , wherein the determining of the processing layouts for nodes in the third set of nodes further comprises:

determining a final processing layout for each particular node of at least some of the third set of nodes in the backward pass performed starting from nodes in the second set of one or more nodes in accordance with the structure of the dataflow graph, the initial processing layouts, and the one or more layout determination rules, such that, for each particular node, wherein:

the parallel processing layout according to one of the initial processing layout of the particular node or of the processing layout of the node succeeding the particular node is selected during the backward pass as the final processing layout of the particular node if the other one of the processing layouts of the initial processing layout of the particular node and the processing layout of the node succeeding the particular node is serial, or

the processing layout among the initial processing layout of the particular node and the processing layout of the node succeeding the particular node that is used to process the largest number of records is selected during the backward pass as the final processing layout of the particular node,

as indicated by the at least one rule.

17 . The method of claim 16 , wherein the processing layout among the initial processing layout of the particular node and the processing layout of the node succeeding the particular node that is used to process the largest number of records is selected during the backward pass as the final processing layout of the particular node if the initial processing layout of the particular node and the processing layout of the node succeeding the particular node both have serial processing layouts or both have multiple parallel processing layouts but with the same or different degree of parallelism among each other.

18 . The method of claim 17 , wherein a processing layout associated with the at least one node is disregarded when selecting the final processing layout of the particular node during the backward pass.

19 . The method of claim 16 , further comprising:

after performing the forward pass and/or the backward pass, configuring the dataflow graph to perform a repartitioning operation on data to be processed by adjacent nodes in the dataflow graph having processing layouts with different degrees of parallelism.

20 . The method of claim 16 , wherein a processing layout for a node representing an operation further specifies one or more computing devices to be used for performing the operation in accordance with the specified degree of parallelism, the processing layout also specifying how many computing devices are to be used for performing the operation and identifying one or more particular computing devices to be used for performing the operation.

21 . The method of claim 20 , wherein the third set of nodes includes a first node, the first node representing a first data processing operation; and after performing the forward pass and/or the backward pass,

executing the dataflow graph in accordance with the processing layouts determined for each node in the dataflow graph, including:

performing a repartitioning operation on data processed by adjacent nodes in the dataflow graph having processing layouts with different degrees of parallelism; and

identifying, based on the initial or final processing layout determined for the first node of the third set of nodes, a set of one or more computing devices and performing, by using the identified set of computing devices, the first data processing operation in accordance with the degree of parallelism specified by the initial or final processing layout determined for the first node of the third set of nodes.

22 . At least one non-transitory computer readable storage medium storing processor executable instructions that, when executed by at least one computer hardware processor, cause the at least one computer hardware processor to perform a method comprising:

obtaining information specifying a dataflow graph, the dataflow graph comprising nodes and edges connecting the nodes, the edges representing flows of data among the nodes, the nodes comprising:

a first set of one or more nodes, each node in the first set of one or more nodes representing a respective input dataset in a set of one or more input datasets;

a second set of one or more nodes, each node in the second set of one or more nodes representing a respective output dataset in a set of one or more output datasets; and

a third set of nodes representing data processing operations, each node in the third set of nodes representing at least one of the data processing operations;

obtaining a first set of one or more processing layouts for the set of one or more input datasets and a second set of one or more processing layouts for the set of one or more output datasets, the first set of one or more processing layouts including processing layouts having different degrees of parallelism and/or the second set of one or more processing layouts having different degrees of parallelism, wherein each processing layout in the first and second sets of one or more processing layouts specifies, for a particular node in the first or second set of one or more nodes, a respective degree of parallelism to be used for performing an operation represented by the particular node;

determining processing layouts for nodes in the third set of nodes using: (a) the first set of one or more processing layouts, (b) the second set of one or more processing layouts, (c) one or more layout determination rules including at least one rule for selecting among processing layouts having different degrees of parallelism, and (d) information indicating that data generated by at least one node in the first set of one or more nodes and/or third set of nodes is not used by any nodes in the dataflow graph downstream from the at least one node, wherein determining the processing layouts for the nodes in the third set of nodes comprises:

identifying the at least one node whose data is not used by any nodes in the dataflow graph downstream from the at least one node during a forward pass starting from nodes in the first set of one or more nodes or a backward pass starting from nodes in the second set of one or more nodes; and

after determining the processing layout for each node in the dataflow graph, executing the dataflow graph in accordance with processing layouts determined for each node in the dataflow graph, the executing comprising:

reading input data from the set of the one or more input datasets represented by the first set of one or more nodes in accordance with the first set of one or more processing layouts;

processing the input data using the data processing operations represented by the third set of nodes in accordance with the processing layouts determined for the nodes in the third set of nodes; and

writing output data obtained as a result of performing the data processing operations to the set of one or more output datasets represented by the second set of one or more nodes in accordance with the second set of one or more processing layouts.

23 . A data processing system, comprising:

at least one computer hardware processor; and

at least one non-transitory computer readable storage medium storing processor executable instructions that, when executed by the at least one computer hardware processor, cause the at least one computer hardware processor to perform a method comprising:

obtaining information specifying a dataflow graph, the dataflow graph comprising nodes and edges connecting the nodes, the edges representing flows of data among the nodes, the nodes comprising:

a first set of one or more nodes, each node in the first set of one or more nodes representing a respective input dataset in a set of one or more input datasets;

a second set of one or more nodes, each node in the second set of one or more nodes representing a respective output dataset in a set of one or more output datasets; and

a third set of nodes representing data processing operations, each node in the third set of nodes representing at least one of the respective data processing operations;

obtaining a first set of one or more processing layouts for the set of one or more input datasets and a second set of one or more processing layouts for the set of one or more output datasets, the first set of one or more processing layouts including processing layouts having different degrees of parallelism and/or the second set of one or more processing layouts having different degrees of parallelism, wherein each processing layout in the first and second sets of one or more processing layouts specifies, for a particular node in the first or second set of one or more nodes, a respective degree of parallelism to be used for performing an operation represented by the particular node;

determining processing layouts for nodes in the third set of nodes using: (a) the first set of one or more processing layouts, (b) the second set of one or more processing layouts, (c) one or more layout determination rules including at least one rule for selecting among processing layouts having different degrees of parallelism, and (d) information indicating that data generated by at least one node in the first set of one or more nodes and/or third set of nodes is not used by any nodes in the dataflow graph downstream from the at least one node, wherein determining the processing layouts for the nodes in the third set of nodes comprises:

identifying the at least one node whose data is not used by any nodes in the dataflow graph downstream from the at least one node during a forward pass starting from nodes in the first set of one or more nodes or a backward pass starting from nodes in the second set of one or more nodes; and

after determining the processing layout for each node in the dataflow graph, executing the dataflow graph in accordance with processing layouts determined for each node in the dataflow graph, the executing comprising:

reading input data from the set of the one or more input datasets represented by the first set of one or more nodes in accordance with the first set of one or more processing layouts;

processing the input data using the data processing operations represented by the third set of nodes in accordance with the processing layouts determined for the nodes in the third set of nodes; and

writing output data obtained as a result of performing the data processing operations to the set of one or more output datasets represented by the second set of one or more nodes in accordance with the second set of one or more processing layouts.

Assignments (3)

Continuity (2)

References Cited (116)