Adjacent data parallel and streaming operator fusion

• US 20090007116A1
• Filed: 06/27/2007
• Published: 01/01/2009
• Est. Priority Date: 06/27/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Callahan, David, Duffy, John Joseph
• Granted Patent: US 8,201,171 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Various technologies and techniques are disclosed for handling data parallel operations. Data parallel operations are composed together to create a more complex data parallel operation. A fusion plan process is performed on a particular complex operation dynamically at runtime. As part of the fusion plan process, an analysis is performed of a structure of the complex operation and input data. One particular algorithm that best preserves parallelism is chosen from multiple algorithms. The structure of the complex operation is revised based on the particular algorithm chosen. A nested complex operation can also be fused, by inlining its contents into an outer complex operation so that parallelism is preserved across nested operation boundaries.

Claims

1. A method for fusing data parallel operations comprising the steps of:

composing data parallel operations together to create a more complex data parallel operation; and

performing a fusion plan process on a particular complex operation dynamically at runtime, the fusion plan process including analyzing an internal structure of the particular complex operation and removing superfluous merge and partition pairs.

2. The method of claim 1, wherein the fusion plan process is operable to rearrange the internal structure of the particular complex operation.

3. The method of claim 2, wherein adaptive statistics are used to make better decisions on when to rearrange the internal structure of the particular complex operation.

4. The method of claim 2, wherein optimizations are performed to ensure that superfluous repartitioning operations are not incurred when rearranging the particular complex operation.

5. The method of claim 2, wherein the fusion plan process is operable to restructure a complex operation in the presence of one or more order dependent operations comprising the particular complex operation.

6. The method of claim 5, wherein the order dependent operations are selected from the group consisting of zipping, concatenation, reversing, and sorting.

7. The method of claim 2, wherein the fusion plan process is further operable to restructure a complex operation in the presence of one or more grouping operations in the particular complex operation.

8. The method of claim 2, wherein the fusion plan process is further operable to restructure a complex operation in the presence of one or more joining operations in the particular complex operation.

9. The method of claim 2, wherein the fusion plan process is further operable to restructure a complex operation in the presence of one or more set operations in the particular complex operation.

10. The method of claim 2, wherein the fusion plan process is further operable to restructure a complex operation in the presence of one or more select-distinct operations in the particular complex operation.

11. The method of claim 1, wherein a fusion plan is generated as a result of the fusion plan process.

12. The method of claim 1, wherein a fusion plan is generated just-in-time from the fusion plan process.

13. A computer-readable medium having computer-executable instructions for causing a computer to perform the steps recited in claim 1.

14. A computer-readable medium having computer-executable instructions for causing a computer to perform steps comprising:

performing an analysis of a structure of a complex data parallel operation and input data to the complex operation;

choosing from a plurality of algorithms one particular algorithm that best preserves parallelism; and

revising the structure of the complex operation based on the one particular algorithm chosen.

15. The computer-readable medium of claim 14, further having computer-executable instructions for causing a computer to perform steps comprising:

generating a fusion plan after revising the complex operation.

16. The computer-readable medium of claim 15, wherein a just-in-time generation of the fusion plan is performed.

17. A method for fusing nested complex operators comprising the steps of:

composing one or more data parallel operations together to form a complex operation; and

inlining a nested complex operation into an outer complex operation so parallelism is preserved across nested operation boundaries.

18. The method of claim 17, wherein constituent operations comprising the nested complex operation become part of the outer complex operation.

19. The method of claim 17, wherein a just-in-time generation of a fusion plan is performed by analyzing the nested complex operation.

20. A computer-readable medium having computer-executable instructions for causing a computer to perform the steps recited in claim 17.