System and method for goal-based scheduling of blocks of code for concurrent execution

• US 7,222,218 B2
• Filed: 10/22/2002
• Issued: 05/22/2007
• Est. Priority Date: 10/22/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Kumar, Ajay, Dutt, Bala, Susarla, Hanumantha R.
• Primary Examiner(s): Sough; Hyung
• Assistant Examiner(s): Chery; Mardochee
• Application Number:
  US10/277,602
• Publication Number:
  US 20040078538A1
• Time in Patent Office: 1,673 Days
• Field of Search: 711/125, 711/158, 711/168, 710/244, 718/102, 718/103, 718/107, 709/103, 709/104, 712/9
• US Class Current: 711/125
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

A scheduler may be configured to schedule a plurality of blocks of concurrent code for multi-threaded execution. The scheduler may be configured to initiate multi-threaded execution of the blocks of concurrent code in an order determined by block-level performance criteria for the blocks of concurrent code to reduce overall execution time of the concurrent code. In one embodiment, the scheduler may be configured to schedule code blocks having a longer run time ahead of blocks having a shorter run time. The scheduler may be configured to schedule a group of said blocks based on a goal of each of the blocks of the group completing execution at approximately the same time. The scheduler may also be configured to initiate multi-threaded execution of each block of the group at different times according to the block-level performance criteria to the goal.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to the one or more processors, wherein the memory is configured to store program instructions executable by the one or more processors to implement;

a concurrent code generator configured to receive marked code having a plurality of markers each indicating a block of code marked for concurrent execution and block-level performance criteria for that block, wherein the concurrent code generator is configured to generate concurrent code from the marked code; and

a scheduler configured to schedule a plurality of blocks of the concurrent code for multi-threaded execution, wherein the scheduler is configured to initiate multi-threaded execution of the blocks of concurrent code in an order determined by the block-level performance criteria for the blocks of concurrent code to reduce overall execution time of the concurrent code.

2. The system as recited in claim 1, wherein said scheduler is configured to schedule code blocks having a longer run time ahead of blocks having a shorter run time.

3. The system as recited in claim 1, wherein said scheduler is configured to schedule a group of said blocks based on a goal of each of the blocks of the group completing execution at approximately the same time, wherein said scheduler is configured to initiate multi-threaded execution of each block of the group at different times according to the block-level performance criteria to meet said goal.

4. The system as recited in claim 1, wherein the block-level performance criteria comprises an estimated run-time for each block of concurrent code.

5. The system as recited in claim 1, wherein the block-level performance criteria comprises priority information, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to the priority information included with the marker for the corresponding marked block.

6. The system as recited in claim 1, wherein the block-level performance criteria comprises dependency information, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to the dependency information included with the marker for the corresponding marked block.

7. The system as recited in claim 1, wherein the block-level performance criteria comprises a block duration weight, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to an estimated run-time for each block;

wherein the estimated run-time is estimated from a path length of the block and the block duration weight for the block, and wherein blocks having a longer run time are scheduled ahead of blocks having a shorter run time.

8. The system as recited in claim 1, wherein the scheduler is configured to analyze the concurrent code to determine the block-level performance criteria as an estimated run-time for each block of concurrent code to be scheduled for multi-threaded execution.

9. The system as recited in claim 1, wherein the scheduler is configured to determine the block-level performance criteria for each block of concurrent code according to data obtained from prior executions of each respective block.

10. The system as recited in claim 9, wherein said program instructions are further configured to implement a tracking tool configured to be called for each concurrently executable block, wherein the tracking tool is configured to log information to trace or profile execution of the blocks to provide at least part of the block-level performance criteria.

11. A method, comprising:

receiving marked code having a plurality of markers each indicating a block of code marked for concurrent execution and block-level performance criteria for that block;

generating concurrent code from the marked code;

receiving the concurrent code comprising one or more blocks configured for concurrent execution;

determining a block-level performance criterion for each block to be concurrently executed; and

initiating multi-threaded execution of the blocks of concurrent code in an order based on the block-level performance criteria for the blocks of concurrent code to reduce overall execution time of the concurrent code.

12. The method as recited in claim 11, wherein said initiating comprises initiating the one or more blocks having a longer run time ahead of the one or more blocks having a shorter run time.

13. The method as recited in claim 11, wherein said initiating comprises initiating a group of said blocks based on a goal of each of the blocks of the group completing execution at approximately the same time, wherein said initiating comprises initiating multi-threaded execution of each block of the group at different times according to the block-level performance criteria to meet said goal.

14. The method as recited in claim 11, wherein the block-level performance criterion comprises an estimated run-time for each of the one or more blocks.

15. The method as recited in claim 11, wherein the block-level performance criteria comprises priority information, wherein said initiating further comprises initiating each concurrent code block for multi-threaded execution according to the priority information included with the marker for the corresponding marked block.

16. The method as recited in claim 11, wherein the block-level performance criteria comprises dependency information, wherein said initiating further comprises initiating each concurrent code block for multi-threaded execution according to the dependency information included with the marker for the corresponding marked block.

17. The method as recited in claim 11, wherein the block-level performance criteria comprises a block duration weight, wherein said initiating further comprises initiating each concurrent code block for multi-threaded execution according to an estimated run-time for each block, wherein the estimated run-time is estimated from a path length of the block and the block duration weight for the block, and wherein blocks having a longer run time are scheduled ahead of blocks having a shorter run time.

18. The method as recited in claim 11, wherein said initiating further comprises analyzing the concurrent code to determine the block-level performance criteria as an estimated run-time for each block of concurrent code to be initiated for multi-threaded execution.

19. The method as recited in claim 11, wherein said initiating comprises determining the block-level performance criteria for each block of concurrent code according to data obtained from prior executions of each respective block.

20. The method as recited in claim 19, further comprising executing a tracking tool configured to be called for each concurrently executable block, wherein the tracking tool is configured to log information to trace or profile execution of the blocks to provide at least part of the block-level performance criteria.

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

a scheduler configured to;

determine block-level performance criteria for each block of a plurality of blocks of concurrent code according to data obtained from prior executions of each respective block;

schedule the plurality of blocks of concurrent code for multi-threaded execution; and

initiate multi-threaded execution of the blocks of concurrent code in an order determined by the block-level performance criteria for the blocks of concurrent code to reduce overall execution time of the concurrent code; and

a tracking tool configured to be called for each concurrently executable block, wherein the tracking tool is configured to log information to trace or profile execution of the blocks to provide at least part of the block-level performance criteria.

22. The computer readable storage medium as recited in claim 21, wherein said scheduler is configured to schedule code blocks having a longer run time ahead of blocks having a shorter run time.

23. The computer readable storage medium as recited in claim 21, wherein said scheduler is configured to schedule a group of said blocks based on a goal of each of the blocks of the group completing execution at approximately the same time, wherein said scheduler is configured to initiate multi-threaded execution of each block of the group at different times according to the block-level performance criteria to meet said goal.

24. The computer readable storage medium as recited in claim 21, wherein the program instructions are further executable to implement a concurrent code generator configured to receive marked code having a plurality of markers each indicating a block of code marked for concurrent execution and block-level performance criteria for that block, wherein the concurrent code generator is configured to generate the concurrent code from the marked code.

25. The computer readable storage medium as recited in claim 24, wherein the block-level performance criteria comprises priority information, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to the priority information included with the marker for the corresponding marked block.

26. The computer readable storage medium as recited in claim 24, wherein the block-level performance criteria comprises dependency information, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to the dependency information included with the marker for the corresponding marked block.

27. The computer readable storage medium as recited in claim 24, wherein the block-level performance criteria comprises a block duration weight, wherein the scheduler is configured to schedule each concurrent code block for multi-threaded execution according to an estimated run-time for each block, wherein the estimated run-time is estimated from a path length of the block and the block duration weight for the block, and wherein blocks having a longer run time are scheduled ahead of blocks having a shorter run time.

28. The computer readable storage medium as recited in claim 21, wherein the scheduler is configured to analyze the concurrent code to determine the block level performance criteria as an estimated run-time for each block of concurrent code to be scheduled for multi-threaded execution.

29. The computer readable storage medium as recited in claim 21, wherein the block-level performance criteria comprises an estimated run-time for each block of concurrent code.