CONTROLLING AND DYNAMICALLY VARYING AUTOMATIC PARALLELIZATION

• US 20100153959A1
• Filed: 12/15/2008
• Published: 06/17/2010
• Est. Priority Date: 12/15/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,528,001 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence

Abstract

A system and method for automatically controlling run-time parallelization of a software application. A buffer is allocated during execution of program code of an application. When a point in program code near a parallelized region is reached, demand information is stored in the buffer in response to reaching a predetermined first checkpoint. Subsequently, the demand information is read from the buffer in response to reaching a predetermined second checkpoint. Allocation information corresponding to the read demand information is computed and stored the in the buffer for the application to later access. The allocation information is read from the buffer in response to reaching a predetermined third checkpoint, and the parallelized region of code is executed in a manner corresponding to the allocation information.

Claims

1. A computer readable storage medium storing program instructions operable to automatically control run-time parallelization of a software application, wherein the program instructions are executable to:

identify a parallel region within program instructions of a multi-threaded software application;

instrument the software application with instructions executable to;

allocate a buffer;

store demand information in the buffer;

read allocation information from the buffer without waiting for an update of the allocation information; and

determine parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer.

2. The storage medium as recited in claim 1, wherein the allocation information and parallelization information include information corresponding to the demand information, and wherein during execution of the application:

demand information is read from the buffer, in response to determining an allocation checkpoint;

allocation information corresponding to the read demand information is computed; and

parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer is determined.

3. The storage medium as recited in claim 2, wherein determining the parallelization information comprises computing an average of the demand information and the allocation information.

4. The storage medium as recited in claim 2, wherein the demand information includes one or more of the following:

a requested number of threads and a preferred assignment for each thread.

5. The storage medium as recited in claim 2, wherein determining the allocation checkpoint comprises detecting at least one of the following:

a predetermined cyclic time duration, when a new process is ready to execute, when a process is ready to be terminated, and when the number of available hardware threads is changed.

6. The storage medium as recited in claim 5, wherein computing the allocation information comprises utilizing one or more of the following:

scheduling policy, process state, and process memory management information.

7. The storage medium as recited in claim 1, wherein identifying a parallel region comprises detecting one or more of the following:

a loop construct instruction, a user-specified directive, a first function call with no data dependencies on a second function call, and a first basic block with no data dependencies on a second basic block.

8. The storage medium as recited in claim 7, wherein determining the demand information comprises computing a loop index count.

9. A method comprising:

identifying a parallel region within program instructions of a multi-threaded software application; and

instrumenting the software application with instructions executable to;

allocate a buffer;

store demand information in the buffer;

read allocation information from the buffer without waiting for an update of the allocation information; and

determine parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer.

10. The method as recited in claim 9, wherein the allocation information and parallelization information include information corresponding to the demand information, and wherein during execution of the application the method further comprises:

reading demand information from the buffer, in response to determining an allocation checkpoint;

computing allocation information corresponding to the read demand information; and

determining parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer.

11. The method as recited in claim 10, wherein determining the parallelization information comprises computing an average of the demand information and the allocation information.

12. The method as recited in claim 10, wherein the demand information includes one or more of the following:

a requested number of threads and a preferred assignment for each thread.

13. The method as recited in claim 10, wherein determining the allocation checkpoint comprises detecting at least one of the following:

a predetermined cyclic time duration, when a new process is ready to execute, when a process is ready to be terminated, and when the number of available hardware threads is changed.

14. The method as recited in claim 13, wherein computing the allocation information comprises utilizing one or more of the following:

scheduling policy, process state, and process memory management information.

15. The method as recited in claim 9, wherein identifying a parallel region comprises detecting one or more of the following:

a loop construct instruction, a user-specified directive, a first function call with no data dependencies on a second function call, and a first basic block with no data dependencies on a second basic block.

16. The method as recited in claim 15, wherein determining the demand information comprises computing a loop index count.

17. A compiler comprising:

code generation instructions; and

optimization instruction configured to;

identify a parallel region within program instructions of a multi-threaded software application;

instrument the software application with instructions executable to;

allocate a buffer;

store demand information in the buffer;

read allocation information from the buffer without waiting for an update of the allocation information; and

determine parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer.

18. The compiler as recited in claim 17, wherein the allocation information and parallelization information include information corresponding to the demand information, and wherein during execution of the application:

demand information is read from the buffer, in response to determining an allocation checkpoint;

allocation information corresponding to the read demand information is computed; and

parallelization information for use in executing the parallel region based at least in part on the allocation information read from the buffer is determined.

19. The compiler as recited in claim 18, wherein determining the parallelization information comprises computing an average of the demand information and the allocation information.

20. The compiler as recited in claim 18, wherein the demand information includes one or more of the following:

a requested number of threads and a preferred assignment for each thread.