Controlling and dynamically varying automatic parallelization

• US 8,528,001 B2
• Filed: 12/15/2008
• Issued: 09/03/2013
• 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, Kalogeropulos, Spiros, Tirumalai, Partha P.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, DONG U
• Application Number:
  US12/335,124
• Publication Number:
  US 20100153959A1
• Time in Patent Office: 1,723 Days
• Field of Search: None
• US Class Current: 718/107
• 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 non-transitory computer readable storage medium storing program instructions operable to automatically control run-time parallelization of a multi-threaded software application, wherein the program instructions are executable to:

analyze program instructions of the multi-threaded software application;

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

instrument the software application with instructions executable to;

allocate a buffer in memory for communication between the software application and an operating system;

pass a format and address of the buffer to the operating system, thereby enabling the operating system to read from and write to the buffer;

store preferred resource requests from the software application in the buffer, wherein resources are used for executing the identified parallel region;

read resource availability from the buffer, said resource availability having been stored in the buffer by the operating system, wherein the resource availability is associated with the preferred resource requests; and

determine run-time resources for use in executing the parallel region based at least in part on the resource availability read from the buffer, wherein the instructions are executable to obtain the operating system provided resource availability from the buffer without a system call to the operating system.

2. The storage medium as recited in claim 1, wherein the resource availability and run-time resources include information corresponding to the preferred resource requests, and wherein during execution of the application:

preferred resource requests are read from the buffer by the operating system, in response to detecting an allocation checkpoint;

resource availability corresponding to the read preferred resource requests is computed by the operating system and stored in the buffer; and

run-time resources for use in executing the parallel region are determined by the software application based at least in part on resource availability read from the buffer.

3. The storage medium as recited in claim 2, wherein determining the run-time resources comprises computing an average of one or more numbers of resources in the preferred resource requests and one or more associated numbers of resources in the resource availability.

4. The storage medium as recited in claim 3, wherein the preferred resource requests and the resource availability are associated with one another by a parallel region identifier, wherein the one or more numbers of resources for each 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 by the operating system 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 resource availability 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. A method comprising:

analyzing program instructions of a multi-threaded software application;

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

instrumenting the software application with instructions executable to;

allocate a buffer in memory for communication between the software application and an operating system;

pass a format and address of the buffer to the operating system, thereby enabling the operating system to read from and write to the buffer;

store preferred resource requests from the software application in the buffer, wherein resources are used for executing the identified parallel region;

read resource availability from the operating system from the buffer, said resource availability having been stored in the buffer by the operating system, wherein the resource availability is associated with the preferred resource requests; and

determine run-time resources for use in executing the parallel region based at least in part on the resource availability read from the buffer, wherein the operating system provided resource availability is obtained from the buffer without a system call to the operating system.

9. The method as recited in claim 8, wherein the resource availability and run-time resources include information corresponding to the preferred resource requests, and wherein during execution of the application the method further comprises:

reading preferred resource requests from the buffer, in response to determining an allocation checkpoint;

computing resource availability corresponding to the read preferred resource requests; and

determining run-time resources for use in executing the parallel region based at least in part on the resource availability read from the buffer.

10. The method as recited in claim 9, wherein determining the run-time resources comprises computing an average of one or more numbers of resources in the preferred resource requests and one or more associated numbers of resources in the resource availability.

11. The method as recited in claim 10, wherein the preferred resource requests and the resource availability are associated with one another by a parallel region identifier, wherein the one or more numbers of resources for each includes one or more of the following:

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

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

13. The method as recited in claim 12, wherein computing the resource availability comprises utilizing one or more of the following:

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

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

15. A computer system comprising:

a processor;

a compiler comprising;

code generation instructions executable by the processor; and

optimization instructions executable by the processor to;

analyze program instructions of a multi-threaded software application;

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

instrument the software application with instructions executable to;

allocate a buffer in memory for communication between the software application and an operating system;

pass a format and address of the buffer to the operating system, thereby enabling the operating system to read from and write to the buffer;

store preferred resource requests from the software application in the buffer, wherein resources are used for executing the identified parallel region;

read resource availability from the operating system from the buffer, said resource availability having been stored in the buffer by the operating system, wherein the resource availability is associated with the preferred resource requests; and

determine run-time resources for use in executing the parallel region based at least in part on the resource availability read from the buffer, wherein the operating system provided resource availability is obtained from the buffer without a system call to the operating system.

16. The system as recited in claim 15, wherein the resource availability and run-time resources include information corresponding to the preferred resource requests, and wherein during execution of the application:

preferred resource requests are read from the buffer, in response to determining an allocation checkpoint;

resource availability corresponding to the read preferred resource requests is computed; and

run-time resources for use in executing the parallel region based at least in part on the resource availability read from the buffer are determined.

17. The system as recited in claim 16, wherein determining the run-time resources comprises computing an average of one or more numbers of resources in the preferred resource requests and one or more associated numbers of resources in the resource availability.

18. The system as recited in claim 17, wherein the preferred resource requests and the resource availability are associated with one another by a parallel region identifier, wherein the one or more numbers of resources for each includes one or more of the following:

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