RUNTIME PROFITABILITY CONTROL FOR SPECULATIVE AUTOMATIC PARALLELIZATION

• US 20090276766A1
• Filed: 05/01/2008
• Published: 11/05/2009
• 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, Tirumalai, Partha P., Kalogeropulos, Spiros
• Granted Patent: US 8,359,587 B2
• Time in Patent Office: Days
• 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. The method includes parallelizing the candidate code, in response to determining said profitability meets a predetermined criteria; and generating object code corresponding to the source code. The generated object code includes both a non-parallelized version of the candidate code and a parallelized version of the candidate code. During execution of the object code, a dynamic selection between execution of the non-parallelized version of the candidate code and the parallelized version of the candidate code is made. Changing execution from said parallelized version of the candidate code to the non-parallelized version of the candidate code, may be in response to determining a transaction failure count meets a pre-determined threshold. Additionally, changing execution from one version to the other may be in further response to determining an execution time of the parallelized version of the candidate code is greater than an execution time of the non-parallelized version of the candidate code.

Claims

1. A method for compilation comprising:

analyzing source code;

identifying candidate code for parallelization;

determining a profitability of parallelizing the candidate code;

parallelizing said candidate code, in response to determining said profitability meets a predetermined criteria; and

generating object code corresponding to the source code, wherein said object code includes both a non-parallelized version of the candidate code and a parallelized version of the candidate code.

2. The method of claim 1, wherein said candidate code comprises a loop.

3. The method of claim 2, wherein determining said profitability comprises:

computing a probability of transaction failure for the loop;

parallelizing the loop, in response to determining a predicted execution time of a parallelized version of the loop is less than an 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 a predicted execution time of said parallelized version is not less than an execution time of the non-parallelized version of said loop by at least the given amount.

4. The method of claim 3, further comprising dynamically selecting between execution of said non-parallelized version of the candidate code and the parallelized version of the candidate code during executing said object code.

5. The method of claim 4, wherein dynamically selecting between execution of said non-parallelized version of the candidate code and the parallelized version of the candidate code comprises:

maintaining a transaction failure count; and

changing execution from said parallelized version of the candidate code to the non-parallelized version of the candidate code, in response to determining the transaction failure count meets a pre-determined threshold.

6. The method of claim 4, wherein said dynamically selecting comprises:

measuring an execution time of each of the non-parallelized version and the parallelized version;

selecting the parallelized version for execution, at least in part responsive to determining the execution time of the parallelized version is less than the non-parallelized version by at least a predetermined amount; and

selecting the non-parallelized version for execution, at least in part responsive to determining the execution time of the non-parallelized version is less than the parallelized version by at least a predetermined amount.

7. The method of claim 5, further comprising resetting said transaction failure count, in response to detecting a change in execution between a non-parallelized version of the candidate code and a parallel version of the candidate code.

8. The method of claim 7, further comprising resetting said transaction failure count, in response to detecting a pre-determined number of executions of said candidate code has been reached.

9. A computer readable storage medium comprising program instructions, wherein the program instructions are executable to:

analyze source code;

identify candidate code for parallelization;

determine a profitability of parallelizing the candidate code;

parallelize said candidate code, in response to determining said profitability meets a predetermined criteria; and

generate object code corresponding to the source code, wherein said object code includes both a non-parallelized version of the candidate code and a parallelized version of the candidate code.

10. The medium of claim 9, wherein said candidate code comprises a loop.

11. The medium of claim 10, wherein in determining said profitability, the program instructions are executable to:

compute a probability of transaction failure for the loop;

parallelize the loop, in response to determining a predicted execution time of a parallelized version of the loop is less than an 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 a predicted execution time of said parallelized version is not less than an execution time of the non-parallelized version of said loop by at least the given amount.

12. The medium of claim 11, wherein said program instructions are further executable to dynamically select between execution of said non-parallelized version of the candidate code and the parallelized version of the candidate code during executing said object code.

13. The medium of claim 12, wherein dynamically selecting between execution of said non-parallelized version of the candidate code and the parallelized version of the candidate code comprises:

maintaining a transaction failure count; and

changing execution from said parallelized version of the candidate code to the non-parallelized version of the candidate code, in response to determining the transaction failure count meets a pre-determined threshold.

14. The medium of claim 12, wherein said dynamically selecting comprises:

measuring an execution time of each of the non-parallelized version and the parallelized version;

selecting the parallelized version for execution, at least in part responsive to determining the execution time of the parallelized version is less than the non-parallelized version by at least a predetermined amount; and

selecting the non-parallelized version for execution, at least in part responsive to determining the execution time of the non-parallelized version is less than the parallelized version by at least a predetermined amount.

15. The medium of claim 13, wherein the program instructions are further executable to reset said transaction failure count, in response to detecting a change in execution between a non-parallelized version of the candidate code and a parallel version of the candidate code.

16. The medium of claim 15, wherein the program instructions are further executable to reset said transaction failure count, in response to detecting a pre-determined number of executions of said candidate code has been reached.

17. 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 source code;

identify candidate code for parallelization;

determine a profitability of parallelizing the candidate code;

parallelize said candidate code, in response to determining said profitability meets a predetermined criteria; and

generate object code corresponding to the source code, wherein said object code includes both a non-parallelized version of the candidate code and a parallelized version of the candidate code.

18. The computing system of claim 17, wherein said candidate code comprises a loop.

19. The computing system of claim 18, wherein in determining said profitability, the program instructions are executable to:

compute a probability of transaction failure for the loop;

parallelize the loop, in response to determining a predicted execution time of a parallelized version of the loop is less than an 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 a predicted execution time of said parallelized version is not less than an execution time of the non-parallelized version of said loop by at least the given amount.

20. The computing system of claim 19, wherein said program instructions are further executable to dynamically select between execution of said non-parallelized version of the candidate code and the parallelized version of the candidate code during execution of said object code.