Inducing concurrency in software code

• US 7,765,532 B2
• Filed: 10/22/2002
• Issued: 07/27/2010
• Est. Priority Date: 10/22/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Kumar, Ajay, Dutt, Bala, Susarla, Hanumantha R.
• Primary Examiner(s): MITCHELL, JASON D
• Application Number:
  US10/277,503
• Publication Number:
  US 20040078779A1
• Time in Patent Office: 2,835 Days
• Field of Search: 717140-167, 717124-135, 711/158, 711/168
• US Class Current: 717/149
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

An Induced Multi-threading (IMT) framework may be configured to induce multi-threaded execution in software code. In one embodiment, the IMT framework may include a concurrent code generator configured to receive marked code having one or more blocks of code marked for concurrent execution. Software code initially intended for sequential execution may have been automatically marked by an automated code marker and/or marked manually to generate the marked code. The concurrent code generator may be configured to generate concurrent code from the marked code. The concurrent code may include one or more tasks configured for concurrent execution in place of the one or more marked blocks of code. In one embodiment, the IMT framework may also include a scheduler configured to schedule one or more of the tasks for multi-threaded execution.

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 framework to induce multi-threading, wherein the framework comprises;

a concurrent code generator configured to receive marked code comprising sequential code having one or more blocks of code marked for concurrent execution, wherein each marked block of code is marked by including a marker method call within the code to suggest the block for potential concurrent execution, wherein the concurrent code generator is configured to generate concurrent code from the marked code, wherein the concurrent code comprises one or more tasks configured for concurrent execution in place of the one or more marked blocks of code; and

a scheduler configured to schedule one or more of the tasks for multi-threaded execution.

2. The system as recited in claim 1, wherein one of the blocks of code marked for concurrent execution is a portion of a program method of the sequential code so that the concurrent code generator transforms a block of the sequential code that is less than an entire method of the sequential code into a task configured for concurrent execution.

3. The system as recited in claim 1, wherein the concurrent code generator is configured to perform an analysis of the marked code to estimate performance benefits of concurrent execution of the marked blocks of code, wherein the concurrent code generator does not transform one of the marked blocks into one of the concurrently executable tasks if the analysis indicates no performance benefit is estimated to result from concurrent execution.

4. The system as recited in claim 3, wherein for one or more of the marked blocks not transformed into one of the concurrently executable tasks due to the analysis, the concurrent code generator is configured to remove one or more marker method calls in the concurrent code.

5. The system as recited in claim 3, wherein the concurrent code generator is configured to perform the analysis based on an estimated execution time of each marked block compared to an overhead for scheduling concurrent threads.

6. The system as recited in claim 1, wherein the framework further comprises an automated code marking tool configured to:

receive the sequential code;

analyze the sequential code to identify potentially concurrently executable blocks of the sequential code; and

insert markers into the sequential code to suggest the identified blocks for concurrent execution.

7. The system as recited in claim 1, wherein the marked code comprises a marker for each block of code marked for concurrent execution, and wherein the scheduler is configured to schedule one of the tasks for multi-threaded execution according to priority information included with the marker for the corresponding marked block.

8. The system as recited in claim 1, wherein the marked code comprises a marker for each block of code marked for concurrent execution, and wherein the scheduler is configured to schedule one of the tasks for multi-threaded execution according to dependency information included with the marker for the corresponding marked block.

9. The system as recited in claim 1, wherein the framework further comprises a thread pool manager configured to manage a thread pool to provide threads for multi-threaded execution of the task of the concurrent code, wherein the scheduler is configured to request a thread from the thread pool for each task scheduled for multi-threaded execution.

10. The system as recited in claim 1, wherein the framework further comprises a tracking tool configured to be called for each concurrently executable task, wherein the tracking tool is configured to log information to trace or profile execution of the tasks.

11. A method, comprising:

receiving marked code comprising sequential code having one or more blocks of code marked for concurrent execution, wherein each marked block of code is marked by including a marker within the code to suggest the block for potential concurrent execution;

generating concurrent code from the marked code, wherein the concurrent code comprises one or more tasks configured for concurrent execution in place of the one or more marked blocks of code, and wherein the concurrent code comprises one or more tasks transformed from a class in the marked code into a derived class; and

scheduling one or more of the tasks for multi-threaded execution.

12. The method as recited in claim 11, wherein one of the blocks of code marked for concurrent execution is a portion of a program method of the sequential code, wherein said generating comprises transforming a block of the sequential code that is less than an entire method of the sequential code into a task configured for concurrent execution.

13. The method as recited in claim 11, wherein said generating comprises analyzing the marked code to estimate performance benefits of concurrently executing the marked blocks of code, wherein one of the marked blocks is not transformed into one of the concurrently executable tasks if said analyzing indicates no performance benefit is estimated to result from concurrent execution.

14. The method as recited in claim 13, wherein for one or more of the marked blocks not transformed into one of the concurrently executable tasks due to the analysis, said generating comprises removing one or more markers in the concurrent code.

15. The method as recited in claim 13, wherein said analyzing comprises comparing an estimated execution time of each marked block to an overhead for scheduling concurrent threads.

16. The method as recited in claim 11, further comprising marking the sequential code to suggest one or more blocks of the sequential code for concurrent execution.

17. The method as recited in claim 16, wherein said marking comprises:

receiving the sequential code;

analyzing the sequential code to identify potential concurrently executable blocks of the sequential code; and

inserting markers into the sequential code to suggest the identified blocks for concurrent execution.

18. The method as recited in claim 11, further comprising marking one or more blocks of the sequential code with a marker method call to suggest blocks for potential concurrent execution.

19. The method as recited in claim 11, wherein the marked code comprises a marker for each block of code marked for concurrent execution, and wherein said scheduling comprises scheduling one of the tasks for multi-threaded execution according to priority information included with the marker for the corresponding marked block.

20. The method as recited in claim 11, wherein the marked code comprises a marker for each block of code marked for concurrent execution, and wherein said scheduling comprises scheduling one of the tasks for multi-threaded execution according to dependency information included with the marker for the corresponding marked block.

21. The method as recited in claim 11, further comprising managing a thread pool to provide threads for multi-threaded execution of the task of the concurrent code, wherein said scheduling comprises requesting a thread from the thread pool for each task scheduled for multi-threaded execution.

22. The method as recited in claim 11, further comprising tracking each concurrently executable task, wherein said tracking comprises logging information to trace or profile execution of the tasks.

23. A tangible, computer accessible storage medium comprising program instructions, wherein the program instructions are executable to implement:

receiving marked code comprising sequential code having one or more blocks of code marked for concurrent execution, wherein the marked code comprises a marker for each block of code marked for concurrent execution;

generating concurrent code from the marked code, wherein the concurrent code comprises one or more tasks configured for concurrent execution in place of the one or more marked blocks of code; and

scheduling one or more of the tasks for multi-threaded execution according to priority information included with the marker for the corresponding marked block.

24. The computer accessible medium as recited in claim 23, wherein one of the blocks of code marked for concurrent execution is a portion of a program method of the sequential code, wherein said generating comprises transforming a block of the sequential code that is less than an entire method of the sequential code into a task configured for concurrent execution.

25. The computer accessible medium as recited in claim 23, wherein said generating comprises analyzing the marked code to estimate performance benefits of concurrently executing the marked blocks of code, wherein one of the marked blocks is not transformed into one of the concurrently executable tasks if said analyzing indicates no performance benefit is estimated to result from concurrent execution.

26. The computer accessible medium as recited in claim 25, wherein for one or more of the marked blocks not transformed into one of the concurrently executable tasks due to the analysis, said generating comprises removing markers in the concurrent code.

27. The computer accessible medium as recited in claim 25, wherein said analyzing comprises comparing an estimated execution time of each marked block to an overhead for scheduling concurrent threads.

28. The computer accessible medium as recited in claim 23, wherein the program instructions are further executable to provide an application programming interface (API) for marking the sequential code to suggest one or more blocks of the sequential code for concurrent execution.

29. The computer accessible medium as recited in claim 28, wherein said marking comprises:

receiving the sequential code;

analyzing the sequential code to identify potential concurrently executable blocks of the sequential code; and

inserting markers into the sequential code to suggest the identified blocks for concurrent execution.

30. The computer accessible medium as recited in claim 23, wherein the program instructions are further executable to provide an application programming interface (API) for marking one or more blocks of the sequential code with a marker method call to suggest blocks for potential concurrent execution.

31. The computer accessible medium as recited in claim 23, wherein the marked code comprises a marker for each block of code marked for concurrent execution, and wherein said scheduling comprises scheduling one of the tasks for multi-threaded execution according to dependency information included with the marker for the corresponding marked block.

32. The computer accessible medium as recited in claim 23, wherein the program instructions are further executable to implement managing a thread pool to provide threads for multi-threaded execution of the task of the concurrent code, wherein said scheduling comprises requesting a thread from the thread pool for each task scheduled for multi-threaded execution.

33. The computer accessible medium as recited in claim 23, wherein the program instructions are further executable to implement tracking each concurrently executable task, wherein said tracking comprises logging information to trace or profile execution of the tasks.