Parallelizing non-countable loops with hardware transactional memory

• US 8,739,141 B2
• Filed: 05/19/2008
• Issued: 05/27/2014
• Est. Priority Date: 05/19/2008
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Song, Yonghong, Kalogeropulos, Spiros, Tirumalai, Partha P.
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US12/123,176
• Publication Number:
  US 20090288075A1
• Time in Patent Office: 2,199 Days
• Field of Search: None
• US Class Current: 717/150
• 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, wherein the non-countable loop includes a first function that uses a loop index variable as a parameter, wherein the first function performs input/output and modifies data, wherein identifying the non-countable loop pattern comprises determining whether the non-countable loop pattern meets a set of conditions including;

a) an iteration count of the non-countable loop pattern cannot be determined by a compiler;

b) an exit condition function of the non-countable loop pattern does not modify the loop index variable; and

c) the first function that uses the loop index variable as a parameter does not modify the loop index variable;

if the non-countable loop pattern is determined to meet the set of conditions, 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; and

if the non-countable loop pattern is determined to not meet the set of conditions, compiling the non-countable loop to execute in a serial manner.

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 parallelized 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 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.

4. The method as recited in claim 2, 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.

5. The method as recited in claim 2, 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.

6. The method as recited in claim 5, 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 a value of the loop index of the parallelized loop pattern to a value of a loop index of a last thread without a transaction failure to commit its results.

7. The method as recited in claim 2, 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 a loop body of the non-countable loop pattern.

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

9. A system comprising:

one or more processors; and

memory storing program instructions that implement a compiler, wherein the compiler is executable by the one or more processors to;

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

identify a non-countable loop pattern, wherein the non-countable loop pattern includes a first function that uses a loop index variable as a parameter, wherein the first function performs input/output and modifies data, wherein identifying the non-countable loop pattern comprises determining whether the non-countable loop pattern meets a set of conditions including;

a) an iteration count of the non-countable loop pattern cannot be determined by the compiler;

b) an exit condition function of the non-countable loop pattern does not modify the loop index variable; and

c) the first function that uses the loop index variable as a parameter does not modify the loop index variable;

if the non-countable loop pattern is determined to meet the set of conditions, 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; and

if the non-countable loop pattern is determined to not meet the set of conditions, compile the non-countable loop to execute in a serial manner.

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

store one or more speculative values of a loop index of the parallelized 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.

11. The system as recited in claim 10, 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.

12. The system as recited in claim 10, 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.

13. The system as recited in claim 10, wherein the compiler is executable by the one or more processors 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.

14. The system as recited in claim 13, 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 a value of the loop index of the parallelized loop pattern to a value of a loop index of a last thread without a transaction failure to commit its results.

15. The system as recited in claim 10, 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 a loop body of the non-countable loop pattern.

16. A non-transitory computer readable storage medium storing program instructions that implement a compiler, wherein the compiler is executable by one or more processors to:

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

identify a non-countable loop pattern, wherein the non-countable loop pattern includes a first function that uses a loop index variable as a parameter, wherein the first function performs input/output and modifies data, wherein identifying the non-countable loop pattern comprises determining whether the non-countable loop pattern meets a set of conditions including;

a) an iteration count of the non-countable loop pattern cannot be determined by the compiler;

b) an exit condition function of the non-countable loop pattern does not modify the loop index variable; and

c) the first function that uses the loop index variable as a parameter does not modify the loop index variable;

if the non-countable loop pattern is determined to meet the set of conditions, 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; and

if the non-countable loop pattern is determined to not meet the set of conditions, compiling the non-countable loop to execute in a serial manner.

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

store one or more speculative values of a loop index of the parallelized 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.

18. The storage medium as recited in claim 17, 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.

19. The storage medium as recited in claim 17, 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.

20. The storage medium as recited in claim 17, 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.

21. The storage medium as recited in claim 20, 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 a value of the loop index of the parallelized loop pattern to a value of a loop index of a last thread without a transaction failure to commit its results.

22. The storage medium as recited in claim 17, 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 a loop body of the non-countable loop pattern.

23. The storage medium as recited in claim 17, wherein the compiler is executable by one or more processors to generate instructions to set a number of software threads to concurrently execute by a number of available hardware threads.