Computeraided parallelizing of computation graphs
First Claim
Patent Images
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.
4 Assignments
0 Petitions
Accused Products
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.
67 Citations
39 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.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)


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.  View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)


23. A computer program, stored on a computerreadable medium, for processing a specification of a graphbased 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 graphbased 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 intercomponent link corresponding to the serial link and having parallel characteristics based at least upon the specified degree of parallelism.  View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 35, 36)


33. A computer program, stored on a computerreadable medium, for processing a specification of a graphbased 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 intercomponent 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 intercomponent 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 computerreadable 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 intercomponent 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 computerreadable 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.

1 Specification