Computer-aided parallelizing of computation graphs

• US 20050034112A1
• Filed: 06/22/2004
• Published: 02/10/2005
• Est. Priority Date: 06/25/2003
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Stanfill, Craig W.
• Granted Patent: US 8,059,125 B2
• Time in Patent Office: Days
• US Class Current: 717/149
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

An approach to automatically specifying, or assisting with the specification of, a parallel computation graph involves determining data processing characteristics of the linking elements that couple data processing elements of the graph. The characteristics of the linking elements are determined according to the characteristics of the upstream and/or downstream data processing elements associated with the linking element, for example, to enable computation by the parallel computation graph that is equivalent to computation of an associated serial graph.

Claims

1. A method for automated specification of a parallel computation graph including:

accepting a specification of a computation graph in which data processing elements are joined by linking elements, each of the linking elements being associated with a data flow from an associated upstream one of the data processing elements to an associated downstream one of the data processing elements; and

for each of one or more of the linking elements of the computation graph, determining data processing characteristics of the linking element according to characteristics of the upstream and/or the downstream data processing element associated with the linking element.

2. The method of claim 1 wherein each data processing element of the computation graph is represented as a vertex and each linking element is represented as an arc of the computation graph.

3. The method of claim 1 further including, for each of the one or more linking elements, representing said linking element using a data processing element on a data path joining the upstream and the downstream data processing element associated with that linking element.

4. The method of claim 3 wherein representing the linking element using a data processing element includes configuring said data processing element according to the data processing characteristics of said linking element.

5. The method of claim 4 wherein the data processing element includes an element from the group consisting of a partition element, a gather element, and a sorting element.

6. The method of claim 1 further including forming a serial computation graph wherein at least some of the data processing elements of the computation graph are each represented as multiple instances of serial data processing elements, and each of the one or more linking elements are each represented using one or more serial data processing elements coupled by data flows to the instances of the serial data processing elements.

7. The method of claim 1 wherein the characteristics of the upstream and/or downstream data processing elements include a degree of parallelism for at least some of the data processing elements.

8. The method of claim 1 wherein the characteristics of the upstream and/or downstream data processing elements include a data characteristic for data provided on an output port by an upstream data processing element and/or for data received on an input port by a downstream data processing element.

9. The method of claim 8 wherein the data characteristic includes a sorting characteristic.

10. The method of claim 8 wherein the data characteristic includes a partitioning characteristic.

11. A method for automated specification of a computation graph with one or more parallel components including:

accessing metadata characterizing an input requirements for a data flow of a downstream parallel component of the one or more parallel components; and

specifying at least one functional element for processing the data flow to satisfy the input requirements of the downstream parallel component.

12. The method of claim 11 wherein at least one functional element includes a partition element.

13. The method of claim 12 wherein the partition element includes a hash partition element.

14. The method of claim 12 wherein the partition element includes a round-robin partition element.

15. The method of claim 12 wherein the partition element includes a broadcast element.

16. The method of claim 11 wherein at least one functional element includes a gather element.

17. The method of claim 16 wherein the gather element includes a sorting element.

18. The method of claim 11 wherein specifying at least one functional element includes specifying an interconnection network coupling two or more function elements.

19. The method of claim 11 further including:

determining characteristics of an output data flow of a component based on metadata for the component.

20. The method of claim 19 wherein determining the characteristics of the output data flow is also based on characteristics of one or more of the input flows for the component.

21. The method of claim 19 wherein determining the characteristics of the output data flow includes applying one or more rules.

22. The method of claim 19 wherein determining the characteristics of the output data flow includes executing one or more procedural statements.

23. A computer program, stored on a computer-readable medium, for processing a specification of a graph-based computations, the computer program including instructions for causing a computer system to:

accept a specification of a computation graph in which data processing elements are joined by linking elements, each of the linking elements being associated with a data flow from an associated upstream one of the data processing elements to an associated downstream one of the data processing elements; and

for each of one or more of the linking elements of the computation graph, determine data processing characteristics of the linking element according to characteristics of the upstream and/or the downstream data processing element associated with the linking element.

24. A system for processing a specification of a graph-based computations including:

means for accepting a specification of a computation graph in which data processing elements are joined by linking elements, each of the linking elements being associated with a data flow from an associated upstream one of the data processing elements to an associated downstream one of the data processing elements; and

means for determining characteristics of linking elements, including for each of one or more of the linking elements of the computation graph, determining data processing characteristics of the linking element according to characteristics of the upstream and/or the downstream data processing element associated with the linking element.

25. A method for parallelizing a computation graph, including:

accepting a specification of the computation graph, said computation graph including a first component and a second component coupled by a link;

accepting a specification of a degree of parallelism of the first component and/or of the second component; and

forming an inter-component link corresponding to the serial link and having parallel characteristics based at least upon the specified degree of parallelism.

26. The method of claim 25 wherein the computation graph is a serial computation graph, and wherein the link coupling the first component and the second component is a serial link.

27. The method of claim 26 wherein the serial computation graph includes a plurality of serial links coupling components of the computation graph, and wherein the method includes forming a parallelized computation graph from the serial computation graph.

28. The method of claim 27 wherein forming the parallelized computation graph includes for each of the plurality of serial links replacing the serial link with an inter-component link having parallel characteristics.

29. The method of claim 25 wherein the link couples an output flow of the first component to an input flow of the second component.

30. The method of claim 29 wherein the inter-component link has parallel characteristics based upon at least characteristics of the output flow of the first component.

31. The method of claim 29 wherein the inter-component link has parallel characteristics based upon at least characteristics of the input flow of the second component.

32. The method of claim 25 wherein accepting the specification of the degree of parallelism includes accessing metadata associated with a component of the computation graph.

35. The method of claim 25 further including:

(d) inserting a network representation of the inter-component link into the parallelized computation graph.

36. The method of claim 25 where each of (a)-(c) are applied repeatedly in parallelizing the serial computation graph.

33. A computer program, stored on a computer-readable medium, for processing a specification of a graph-based computations, the computer program including instructions for causing a computer system to:

accept a specification of the computation graph, said computation graph including a first component and a second component coupled by a link;

accept a specification of a degree of parallelism of the first component and/or of the second component; and

form an inter-component link corresponding to the serial link and having parallel characteristics based at least upon the specified degree of parallelism.

34. A computer implemented method for processing a serial computation graph to form a parallelized computation graph including:

(a) mapping characteristics of input flows to a component of the parallelized graph into characteristics of one or more output flows of that component;

(b) determining characteristics for functional elements that implement an inter-component link between two components based on required input characteristics of a component that accepts data from that link; and

(c) determining the characteristics of an input flow of a component based on characteristics of an output flow from another component and determined characteristics of functional elements for a link joining that other component and said component.

37. A computer program, stored on a computer-readable medium, for processing a serial computation graph to form a parallelized computation graph, the computer program including instructions for causing a computer system to:

(a) map characteristics of input flows to a component of the parallelized graph into characteristics of one or more output flows of that component;

(b) determine characteristics for functional elements that implement an inter-component link between two components based on required input characteristics of a component that accepts data from that link; and

(c) determine the characteristics of an input flow of a component based on characteristics of an output flow from another component and determined characteristics of functional elements for a link joining that other component and said component.

38. A method for processing data that is sorted according to a sort order in a computation graph, including:

passing sorted data on one or more flows in the computation graph; and

passing one or more indicators related to the sort order on the one or more flows;

wherein at least some of the indicators on corresponding flows each identify a place in the sort order for the data such that subsequent data on the corresponding flow occurs no earlier that the identified place in the sort order.

39. A computer program, stored on a computer-readable medium, for processing data that is sorted according to a sort order in a computation graph, the computer program including instructions for causing a computer system to:

pass sorted data on one or more flows in the computation graph; and

pass one or more indicators related to the sort order on the one or more flows;

wherein at least some of the indicators on corresponding flows each identify a place in the sort order for the data such that subsequent data on the corresponding flow occurs no earlier that the identified place in the sort order.