Static profitability control for speculative automatic parallelization

• US 8,677,337 B2
• Filed: 05/01/2008
• Issued: 03/18/2014
• Est. Priority Date: 05/01/2008
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Song, Yonghong, Kalogeropulos, Spiros, Tirumalai, Partha P.
• Primary Examiner(s): Nahar, Qamrun
• Application Number:
  US12/113,716
• Publication Number:
  US 20090276758A1
• Time in Patent Office: 2,147 Days
• Field of Search: 717/159, 717/160, 717/152
• US Class Current: 717/159
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

A compilation method and mechanism for parallelizing program code. A method for compilation includes analyzing source code and identifying candidate code for parallelization. Having identified one or more suitable candidates, the profitability of parallelizing the candidate code is determined. If the profitability determination meets a predetermined criteria, then the candidate code may be parallelized. If, however, the profitability determination does not meet the predetermined criteria, then the candidate code may not be parallelized. Candidate code may comprises a loop, and determining profitability of parallelization may include computing a probability of transaction failure for the loop. Additionally, a determination of an execution time of a parallelized version of the loop is made. If the determined execution time is less than an execution time of a non-parallelized version of said loop by at least a given amount, then the loop may be parallelized. If the determined execution time is not less than an execution time of a non-parallelized version of said loop by at least a given amount, then the loop may not be parallelized.

Claims

1. A method for compilation comprising:

analyzing source code;

identifying candidate code for parallelization, wherein said candidate code comprises a loop;

determining a profitability of parallelizing the candidate code, wherein determining the profitability comprises;

computing an execution time of a parallelized version of the loop without executing a parallelized version of the loop; and

computing an execution time of a non-parallelized version of the loop;

parallelizing the loop, in response to determining the execution time of a parallelized version of the loop is less than the execution time of a non-parallelized version of said loop by at least a given amount; and

forgoing parallelization of the loop, in response to determining the execution time of said parallelized version is not less than the execution time of the non-parallelized version of said loop by at least the given amount.

2. The method of claim 1, further comprising foregoing parallelization of said loop, in response to determining said loop comprises a transaction that will fail on each iteration of the loop.

3. The method of claim 1, wherein analyzing said code comprises traversing identified loops from outer loops to inner loops.

4. The method of claim 3, further comprising receiving as input profiling feedback data corresponding to said source code prior to said analyzing.

5. The method of claim 3, further comprising generating input for use in said analyzing, wherein said generating comprises:

identifying a fail block set;

removing dominated blocks from the fail block set to create a reduced fail block set; and

considering code of said reduced fail block set to be one or more candidates for parallelization.

6. The method of claim 1, wherein in response to determining said loop does not comprise a transaction that will fail on each iteration of the loop, the method further comprises:

forgoing parallelization of said loop, in response to determining a resource limitation will be reached on a single iteration of said loop; and

computing a sub-group size, in response to determining a resource limitation will not be reached on a single iteration of said loop, such that work with such a sub-group size will be shared among a plurality of threads.

15. The computing system of claim 1, wherein determining the profitability further comprises computing a probability of transaction failure for the candidate code.

7. A computer readable storage medium comprising program instructions operable for compilation, wherein the program instructions are executable to:

analyze source code;

identify candidate code for parallelization, wherein said candidate code comprises a loop;

determine a profitability of parallelizing the candidate code, wherein to determine the profitability the program instructions are operable to;

compute an execution time of a parallelized version of the loop without executing a parallelized version of the; and

compute an execution time of a non-parallelized version of the loop;

parallelize the loop, in response to determining the execution time of a parallelized version of the loop is less than the execution time of a non-parallelized version of said loop by at least a given amount; and

forgo parallelization of the loop, in response to determining the execution time of said parallelized version is not less than the execution time of the non-parallelized version of said loop by at least the given amount.

8. The computer readable storage medium of claim 7, wherein the program instructions are further executable to forgo parallelization of said loop, in response to determining said loop comprises a transaction that will fail on each iteration of the loop.

9. The computer readable storage medium of claim 7, wherein analyzing said code comprises traversing identified loops from outer loops to inner loops.

10. The computer readable storage medium of claim 9, wherein the program instructions are further executable to receive as input profiling feedback data corresponding to said source code prior to said analyzing.

11. The computer readable storage medium of claim 9, wherein the program instructions are further executable to generate input for use to analyze the source code, wherein to generate the input the program instructions are executable to:

identify a fail block set;

remove dominated blocks from the fail block set to create a reduced fail block set; and

consider code of said reduced fail block set to be one or more candidates for parallelization.

12. The computer readable storage medium of claim 7, wherein in response to determining said loop does not comprise a transaction that will fail on each iteration of the loop, the program instructions are executable to:

forgo parallelization of said loop, in response to determining a resource limitation will be reached on a single iteration of said loop; and

compute a sub-group size, in response to determining a resource limitation will not be reached on a single iteration of said loop, such that work with such a sub-group size will be shared among a plurality of threads.

13. A computing system comprising:

a processor;

a storage medium configured to store application source code; and

a storage medium comprising program instructions, wherein the program instructions are executable by the processor to;

analyze said source code;

identify candidate code of the source code for parallelization, wherein said candidate code comprises a loop;

determine a profitability of parallelizing the candidate code, wherein to determining the profitability the program instructions are executable to;

compute an execution time of a parallelized version of the loop without executing a parallelized version of the candidate code; and

compute an execution time of a non-parallelized version of the loop;

parallelize the loop, in response to determining the execution time of a parallelized version of the loop is less than the execution time of a non-parallelized version of said loop by at least a given amount; and

forgo parallelization of the loop, in response to determining the execution time of said parallelized version is not less than the execution time of the non-parallelized version of said loop by at least the given amount.

14. The computing system of claim 13, wherein the program instructions are further executable to forgo parallelization of said loop, in response to determining said loop comprises a transaction that will fail on each iteration of the loop.