Computer-aided parallelizing of computation graphs

Patent metadata

Field	Value
Publication number	US-9569189-B2
Application number	US-201113295216-A
Country	US
Kind code	B2
Filing date	Nov 14, 2011
Priority date	Jun 25, 2003
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

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.

First claim

What is claimed is:

1. A computer-implemented method for processing data that is sorted according to a sort order, including:
partitioning, by a parallel partition element of a computer system, sorted data among a plurality of parallel flows to generate a plurality of partitioned subsets of the sorted data, the sorted data including work elements, each work element including a sort key value, wherein the sorted data are sorted based on the sort key values, the partitioned subsets of the sorted data are provided at a plurality of outputs of the parallel partition element, each partitioned subset of the sorted data is provided to one of the outputs of the parallel partition element, different partitioned subsets of the sorted data are provided to different outputs of the parallel partition element, and each output of the parallel partition element is associated with a respective one of the plurality of parallel flows;
providing a sort value indicator for each of the parallel flows, the sort value indicator indicating a value in the sort order that has been reached by at least one of the outputs of the parallel partition element;
passing, by the computer system, the sort value indicator on each of the plurality of parallel flows associated with the outputs of the parallel partition element; and
merging, by a sorted merge element of the computer system, work elements from at least two of the parallel flows to generate a merged output, including determining whether a work element from a first one of the parallel flows can be passed to the merged output based on at least one sort value indicator in a second one of the parallel flows,
wherein the sort value indicator identifies a place in the sort order for the data such that subsequent data in the second one of the parallel flows occur no earlier than the identified place in the sort order.

2. The method of claim 1 , wherein the plurality of flows include outputs of work elements from each of multiple instances of a first component, wherein the work elements are sorted according to the sort key.

3. The method of claim 2 , wherein a second component is downstream of the first component and requires that inputs of the second component be sorted according to a second key and partitioned according to the sort key.

4. The method of claim 3 , wherein an inter-component link between the first component and the second component includes a partition element that partitions according to the sort key and at least one sorted gather element that sorts according to the second key.

5. The method of claim 2 , wherein the plurality of flows are included in an inter-component link between the first component and a second component downstream of the first component.

6. The method of claim 5 , wherein passing a sort value indicator on each of the plurality of flows includes repeatedly sending different sort value indicators at different respective times on each of the plurality of flows to indicate a value in the sort order that has been reached by a work element on at least one of the flows at each respective time.

7. The method of claim 6 , wherein the sort value indicator is repeatedly sent on each of the flows by a partition element within the inter-component link that partitions according to the sort key.

8. The method of claim 6 , wherein the sort value indicator signals the second component that no work element with an earlier value in the sort order will be provided over the inter-component link.

9. The method of claim 6 , wherein the sort value indicator is repeatedly sent according to the number of work elements processed.

10. The method of claim 6 , wherein the sort value indicator is repeatedly sent according to time.

11. A computer program, stored on a non-transitory computer-readable medium, for processing data that is sorted according to a sort order, the computer program including instructions for causing a computer system to:
partition, by a parallel partition element, sorted data among a plurality of parallel flows to generate a plurality of partitioned subsets of the sorted data, the sorted data including work elements, each work element including a sort key value, wherein the sorted data are sorted based on the sort key values, the partitioned subsets of the sorted data are provided at a plurality of outputs of the parallel partition element, each partitioned subset of the sorted data is provided to one of the outputs of the parallel partition element, different partitioned subsets of the sorted data are provided to different outputs of the parallel partition element, and each output of the parallel partition element is associated with a respective one of the plurality of parallel flows;
provide a sort value indicator for each of the parallel flows, the sort value indicator indicating a value in the sort order that has been reached by at least one of the outputs of the parallel partition element;
pass the sort value indicator on each of the plurality of parallel flows associated with the outputs of the parallel partition element; and
merge, by a sorted merge element, work elements from at least two of the parallel flows to generate a merged output, including determining whether a work element from a first one of the parallel flows can be passed to the merged output based on at least one sort value indicator in a second one of the parallel flows;
wherein the sort value indicator identifies a place in the sort order for the data such that subsequent data in the second one of the parallel flows occur no earlier than the identified place in the sort order.

12. The computer program of claim 11 , wherein the plurality of flows include outputs of work elements from each of multiple instances of a first component, wherein the work elements are sorted according to the sort key.

13. The computer program of claim 12 , wherein a second component is downstream of the first component and requires that inputs of the second component be sorted according to a second key and partitioned according to the sort key.

14. The computer program of claim 13 , wherein an inter-component link between the first component and the second component includes a partition element that partitions according to the sort key and at least one sorted gather element that sorts according to the second key.

15. The computer program of claim 12 , wherein the plurality of flows are included in an inter-component link between the first component and a second component downstream of the first component.

16. The computer program of claim 15 , wherein passing a sort value indicator on each of the plurality of flows includes repeatedly sending different sort value indicators at different respective times on each of the plurality of flows to indicate a value in the sort order that has been reached by a work element on at least one of the parallel flows at each respective time.

17. The computer program of claim 16 , wherein the sort value indicator is repeatedly sent on each of the flows by a partition element within the inter-component link that partitions according to the sort key.

18. The computer program of claim 16 , wherein the sort value indicator signals the second component that no work element with an earlier value in the sort order will be provided over the inter-component link.

19. The computer program of claim 16 , wherein the sort value indicator is repeatedly sent according to the number of work elements processed.

20. The computer program of claim 16 , wherein the sort value indicator is repeatedly sent according t

Assignees

• Stanfill Craig W
• Ab Initio Technology Llc

Inventors

• Stanfill Craig W

Classifications

• G06F8/45 Primary

  Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions · CPC title