PARALLELIZING NON-COUNTABLE LOOPS WITH HARDWARE TRANSACTIONAL MEMORY

• US 20090288075A1
• Filed: 05/19/2008
• Published: 11/19/2009
• Est. Priority Date: 05/19/2008
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Song, Yonghong, Tirumalai, Partha P., Kalogeropulos, Spiros
• Granted Patent: US 8,739,141 B2
• Time in Patent Office: Days
• US Class Current: 717/160
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/325 for loops, e.g. loop detection or loop counter
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A system and method for speculatively parallelizing non-countable loops in a multi-threaded application. A multi-core processor receives instructions for a multi-threaded application. The application may contain non-countable loops. Non-countable loops have an iteration count value that cannot be determined prior to the execution of the non-countable loop, a loop index value that cannot be non-speculatively determined prior to the execution of an iteration of the non-countable loop, and control that is not transferred out of the loop body by a code line in the loop body. The compiler replaces the non-countable loop with a parallelized loop pattern that uses outlined function calls defined in a parallelization library (PL) in order to speculatively execute iterations of the parallelized loop. The parallelized loop pattern is configured to squash and re-execute any speculative thread of the parallelized loop pattern that is signaled to have a transaction failure.

Claims

1. A method for parallelizing program code of an application, the method comprising:

examining one or more program instructions of a multi-threaded application;

identifying a non-countable loop pattern;

replacing the non-countable loop pattern with a parallelized loop pattern, wherein the parallelized loop pattern is configured to squash and re-execute any speculative thread of the parallelized loop pattern that is signaled to have a transaction failure.

2. The method as recited in claim 1, wherein said parallelized loop pattern is operable to:

store one or more speculative values of a loop index of the loop pattern prior to the execution of any threads;

store load operation addresses and corresponding load operation data values, prior to the execution of any threads; and

signal a transaction failure of an immediate subsequent thread, in response to the load operation data values changing subsequent to execution of a current thread.

3. The method as recited in claim 2, wherein identifying the non-countable loop pattern comprises:

determining a loop index value of the non-countable loop pattern can not be non-speculatively determined prior to execution of an iteration of the non-countable loop pattern.

4. The method as recited in claim 3, wherein prior to the execution of any thread the speculative values include a non-speculative value of the loop index corresponding to an initial value defined in the multi-threaded application.

5. The method as recited in claim 3, wherein the load operation addresses correspond to load operations of qualified function calls receiving the loop index as an input, the qualified function calls comprising function calls defined in the non-countable loop pattern for determining an exit condition for the non-countable loop pattern.

6. The method as recited in claim 3, further comprising signaling a transaction failure of an immediate subsequent thread responsive to detecting a current thread is signaled for a transaction failure by a prior thread.

7. The method as recited in claim 6, wherein re-execution of threads with a transaction failure comprises:

committing results of threads without a transaction failure;

clearing the stored speculative values; and

setting the non-speculative loop index as a loop index of a last thread without a transaction failure to commit its results.

8. The method as recited in claim 3, wherein the parallelized loop pattern replaces function calls in the non-countable loop pattern with outlined function calls to a parallelization library, wherein the outlined function calls comprise:

a first outlined function call configured to utilize function calls defined in the non-countable loop pattern for computing a loop index value for a subsequent iteration and an exit condition; and

a second outlined function call configured to utilize function calls defined in the non-countable loop pattern for computing any break condition and performing the execution of the loop body of the non-countable loop pattern.

9. The method as recited in claim 3, further comprising setting a number of software threads to concurrently execute by a number of available hardware threads.

10. A compiler comprising:

a processor core selection unit configured to assign software threads to waiting hardware threads;

an optimizer; and

a code generator;

wherein the optimizer is configured to;

examine one or more program instructions of a multi-threaded application;

identify a non-countable loop pattern;

replace the non-countable loop pattern with a parallelized loop pattern, wherein the parallelized loop pattern is configured to squash and re-execute any speculative thread of the parallelized loop pattern that is signaled to have a transaction failure.

11. The compiler as recited in claim 10, wherein said parallelized loop pattern is operable to:

store one or more speculative values of a loop index of the loop pattern prior to the execution of any threads;

store load operation addresses and corresponding load operation data values, prior to the execution of any threads; and

signal a transaction failure of an immediate subsequent thread, in response to the load operation data values changing subsequent to execution of a current thread.

12. The compiler as recited in claim 11, wherein the optimizer, in order to identify the non-countable loop pattern, is further configured to:

determine a loop index value of the non-countable loop pattern can not be non-speculatively determined prior to execution of an iteration of the non-countable loop pattern.

13. The compiler as recited in claim 12, wherein prior to the execution of any thread the speculative values include a non-speculative value of the loop index corresponding to an initial value defined in the multi-threaded application.

14. The compiler as recited in claim 12, wherein the load operation addresses correspond to load operations of qualified function calls receiving the loop index as an input, the qualified function calls comprising function calls defined in the non-countable loop pattern for determining an exit condition for the non-countable loop pattern.

15. The compiler as recited in claim 12, wherein the code generator is configured to generate code operable to signal a transaction failure of an immediate subsequent thread in response to detecting a current thread is signaled for a transaction failure by a prior thread.

16. The compiler as recited in claim 15, wherein re-execution of threads with a transaction failure comprises:

committing results of threads without a transaction failure;

clearing the stored speculative values; and

setting the non-speculative loop index as a loop index of a last thread without a transaction failure to commit its results.

17. The compiler as recited in claim 12, wherein the parallelized loop pattern replaces function calls in the non-countable loop pattern with outlined function calls to a parallelization library, the outlined function calls comprising:

a first outlined function call configured to utilize function calls defined in the non-countable loop pattern for computing a loop index value for a subsequent iteration and an exit condition; and

a second outlined function call configured to utilize function calls defined in the non-countable loop pattern for computing any break condition and performing the execution of the loop body of the non-countable loop pattern.

18. A computer readable storage medium storing program instructions operable to parallelize program code of an application, wherein the program instructions are executable to:

examine one or more program instructions of a multi-threaded application;

identify a non-countable loop pattern;

replace the non-countable loop pattern with a parallelized loop pattern, wherein the parallelized loop pattern is configured to squash and re-execute any speculative thread of the parallelized loop pattern that is signaled to have a transaction failure.

19. The storage medium as recited in claim 18, wherein said parallelized loop pattern is operable to:

store one or more speculative values of a loop index of the loop pattern prior to the execution of any threads;

store load operation addresses and corresponding load operation data values, prior to the execution of any threads; and

signal a transaction failure of an immediate subsequent thread, in response to the load operation data values changing subsequent to execution of a current thread.

20. The storage medium as recited in claim 18, wherein in identifying the non-countable loop pattern, the program instructions are executable to:

determine a loop index value of the non-countable loop pattern can not be non-speculatively determined prior to execution of an iteration of the non-countable loop pattern.