System and method for compiler assisted parallelization of a stream processing operator

• US 9,367,293 B2
• Filed: 06/18/2012
• Issued: 06/14/2016
• Est. Priority Date: 06/18/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Halim, Nagui, Kumar, Vibhore, Wu, Kung-Lung, Wu, Sai
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): Paulino, Lenin
• Application Number:
  US13/525,917
• Publication Number:
  US 20140196017A1
• Time in Patent Office: 1,457 Days
• Field of Search: 717/106, 717/220
• US Class Current: 1/1
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

A method of enabling compiler assisted parallelization of one or more stream processing operators in a stream processing application, which consists of a data flow graph with operators as vertices connected by streams. The method includes specifying a parallelized version of one or more of the operators, with a parameterized degree of parallelism, in the stream application, evaluating whether or not to use the parallelized operator, deciding the degree of parallelism of the parallelized operator, if there is a need for a parallelized operator.

Claims

1. A method of enabling compiler assisted parallelization of one or more stream processing operators in a stream processing application operating on a computer processing device, the method comprising:

creating a theoretical model of one or more operators in a compiler, wherein the theoretical model is based on a plurality of factors comprising an average processing time per tuple, an average number of accesses to a shared state per tuple, and a time to read/write to the shared state;

specifying a parallelized version of the one or more operators in the stream processing application based on the theoretical model;

evaluating whether the theoretical model improves the performance of the one or more operators, wherein evaluating whether the theoretical model improves the performance of the one or more operators comprises;

determining the greater of the throughput of a single operator and the throughput of the parallelized operator at compile time;

computing a degree of parallelism if the theoretical model improves the performance of the one or more operators; and

replacing, by the compiler, the one or more operators with the parallelized version of the one or more operators, in response to computing the degree of parallelism.

2. The method of claim 1, wherein specifying the parallelized version of the one or more operators in the stream processing application based on the theoretical model comprises:

providing the parallelized version of the one or more operators as part of a library associated with the stream processing application.

3. The method of claim 1, wherein the computing of the degree of parallelism occurs at compile time.

4. The method of claim 1, wherein the computing of the degree of parallelism occurs at run time.

5. The method of claim 1, wherein the parallelized version of the one or more operators utilizes a shared state.

6. A non-transitory computer readable storage medium embodying a computer readable program code having computer readable instructions to enable compiler assisted parallelization of one or more stream processing operators in a stream processing application operating on a computer processing device which, when implemented, cause a computer to:

create a theoretical model of one or more operators in a compiler, wherein the theoretical model is based on a plurality of factors comprising an average processing time per tuple, an average number of accesses to a shared state per tuple, and a time to read/write to the shared state;

specify a parallelized version of the one or more operators in the stream processing application based on the theoretical model;

evaluate whether the theoretical model improves the performance of the one or more operators, wherein the computer readable instructions to evaluate whether the theoretical model improves the performance of the one or more operators further causes the computer to;

determine the greater of the throughput of a single operator and the throughput of the parallelized operator at compile time;

compute the degree of parallelism if the theoretical model improves the performance of the one or more operators; and

replace, by the compiler, the one or more operators with the parallelized version of the one or more operators, in response to computing the degree of parallelism.

7. The computer readable storage medium of claim 6, wherein the computer readable instructions to specify the parallelized version of a the one or more operators in the stream processing application based on the theoretical model further causes the computer to:

provide the parallelized version of the one or more processing operators as part of a library associated with the stream processing application.

8. The computer readable storage medium of claim 6, wherein the computer readable instructions to compute the degree of parallelism occurs at compile time.

9. The computer readable storage medium of claim 6, wherein the computer readable instructions to compute the degree of parallelism occurs at run time.

10. The computer readable storage medium of claim 6, wherein the parallelized version of the one or more operators utilizes a shared state.

11. A system of enabling compiler assisted parallelization of one or more stream processing operators in a stream processing application operating comprising

a computer processing device;

and

a memory coupled to the computer processing device, wherein the memory comprises instructions which, when executed by the computer processing device, cause the computer processing device to;

create a theoretical model of one or more operators in a compiler, wherein the theoretical model is based on a plurality of factors comprising an average processing time per tuple, an average number of accesses to a shared state per tuple, and a time to read/write to the shared state;

specify a parallelized version of the one or more operators in the stream processing application based on the theoretical model;

evaluate whether the theoretical model improves the performance of the one or more operators, wherein the instructions to evaluate whether the theoretical model improves the performance of the one or more operators further causes the computer processing device to;

determine the greater of the throughput of a single operator and the throughput of the parallelized operator at compile time;

compute the degree of parallelism for the one or more operators if the theoretical model improves the performance of the one or more operators; and

replace, by the compiler, the one or more operators with the parallelized version of the one or more operators, in response to computing the degree of parallelism.

12. The system of claim 11, wherein the instructions to specify the parallelized version of the one or more operators in the stream processing application based on the theoretical model further causes the computer processing device to:

provide the parallelized version of the one or more operators as part of a library associated with the stream processing application.

13. The system of claim 11, wherein the instructions to compute the degree of parallelism occurs at compile time.

14. The system of claim 11, wherein the instructions to compute the degree of parallelism occurs at run time.

15. The system of claim 11, wherein the parallelized version of the one or more operators utilizes a shared state.