System and method for block-based concurrentization of software code

• US 7,346,902 B2
• Filed: 10/22/2002
• Issued: 03/18/2008
• 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): An; Meng-Al T.
• Assistant Examiner(s): MITCHELL, JASON D
• Application Number:
  US10/277,504
• Publication Number:
  US 20040078780A1
• Time in Patent Office: 1,974 Days
• Field of Search: 717136-137, 717/140, 717/144, 717149-161, 718100-104
• US Class Current: 717/149
• CPC Class Codes: G06F 8/456 Parallelism detection

Abstract

A method for inducing multi-threading in software code may use blocks of code as the basis for scheduling and to suggest concurrent execution for each block. The method may comprise marking one or more blocks of code in an application coded for sequential execution to generate marked code. The marking may comprise inserting a marker at each of the one or more blocks to suggest that block for potential concurrent execution. Concurrent code may be generated from the marked code. Generating the concurrent code may comprise analyzing the marked code to estimate performance benefits of concurrently executing the marked blocks of code and determine which marked blocks would meet a performance benefit threshold if executed concurrently. Generating the concurrent code may also comprise transforming one or more of the marked blocks into corresponding concurrently executable tasks. The method may include scheduling one or more of the concurrently executable tasks.

Claims

1. A computer-implemented method, comprising:

automatically marking a plurality blocks of code in an application coded for sequential execution to provide a marked code, wherein said marking comprises inserting a marker at each of the blocks to suggest that block for potential concurrent execution with other parts of the code, wherein each of the markers comprises a block duration weight for estimating an execution time of the corresponding block, wherein the block duration weight indicates a predetermined approximate execution duration for the corresponding block;

generating concurrent code from the marked code, wherein said generating comprises;

analyzing the marked code, according to at least the corresponding block duration weight of one or more of the marked blocks, to estimate performance benefits of concurrently executing the marked blocks of code and determining which marked blocks would meet a performance benefit threshold if executed concurrently; and

transforming two or more of the marked blocks into corresponding concurrently executable tasks, wherein one of the marked blocks is not transformed into one of the concurrently executable tasks if said analyzing indicates that the performance benefit threshold would not be met for that block; and

scheduling two or more of the concurrently executable tasks for concurrent multi-threaded execution, wherein a thread for one of the two or more concurrently executable tasks executes concurrently with a thread for another of the two or more concurrently executable tasks corresponding to a different one of the blocks.

2. The method as recited in claim 1, wherein said analyzing comprises estimating an execution time of each marked block.

3. The method as recited in claim 2, wherein said estimating an execution time comprises estimating the execution time of one of the marked blocks according to the block duration weight of the marker and a path length of the block.

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

5. The method as recited in claim 1, wherein said marking comprises marking a sub-method portion of a program method of the application as one of the blocks marked for concurrent execution, wherein said generating comprises transforming the marked sub-method block into a task configured for concurrent execution.

6. The method as recited in claim 1, wherein said marking comprises:

receiving the application code;

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

wherein said inserting a marker comprises inserting a marker into the sequential code to suggest the identified blocks for concurrent execution.

7. The method as recited in claim 1, wherein said marker comprises a method call.

8. The method as recited in claim 7, wherein said method call is compatible with a programming language of the application.

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

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

11. The method as recited in claim 1, wherein said marking a plurality of blocks of code in an application comprises marking Java byte-code for the application.

12. The method as recited in claim 1, wherein said marking a plurality of blocks of code in an application comprises marking Java source code for the application.

13. The method as recited in claim 1, wherein said marking comprises marking each block so that no block crosses the boundary of another unless the respective blocks are fully nested.

14. 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 for suggestive multi-threading, wherein the framework comprises;

an automated code marker tool configured to receive the sequential code;

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

insert a plurality of markers into the sequential code to suggest the identified blocks for concurrent execution;

a concurrent code generator configured to receive marked code comprising sequential code having a plurality of markers inserted in the sequential code to suggest blocks of code for concurrent execution with other parts of the code, wherein each of the markers comprises a block duration weight for estimating an execution time for the corresponding block, wherein the block duration weight indicates a predetermined approximate execution duration for the corresponding block, wherein the concurrent code generator is configured to;

perform an analysis of the marked code, according to at least the corresponding block duration weight of one or more of the marked blocks, to estimate performance benefits of concurrently executing the marked blocks of code and determine which marked blocks would meet a performance benefit threshold if executed concurrently; and

transform two or more of the marked blocks into corresponding concurrently executable tasks, wherein one of the marked blocks is not transformed into one of the concurrently executable tasks if the analysis indicates that the performance benefit threshold would not be met for that block; and

a scheduler configured to schedule two or more of the tasks for concurrent multi-threaded execution, wherein a thread for one of the two or more concurrently executable tasks executes concurrently with a thread for another of the two or more concurrently executable tasks corresponding to a different one of the blocks.

15. The system as recited in claim 14, wherein the concurrent code generator is further configured to estimate an execution time of each marked block.

16. The system as recited in claim 15, wherein the concurrent code generator is configured to estimate the execution time of one of the marked blocks according to the block duration weight of that block and a path length of that block.

17. The system as recited in claim 15, wherein the concurrent code generator is further configured to compare the estimated execution time of each marked block to an overhead for scheduling concurrent threads.

18. The system as recited in claim 14, wherein the plurality of markers mark a sub-method portion of a program method of the sequential code as one of the blocks marked for concurrent execution, wherein the concurrent code generator is further configured to transform the marked sub-method block into a task configured for concurrent execution.

19. The system as recited in claim 14, wherein each of the markers comprise a method call.

20. The system as recited in claim 19, wherein the method call is compatible with a programming language of the sequential code.

21. The system as recited in claim 14, wherein the scheduler is further configured to schedule one of the tasks for multi-threaded execution according to priority information included with one of the markers for the corresponding marked block.

22. The system as recited in claim 14, wherein the scheduler is further configured to schedule one of the tasks for multi-threaded execution according to dependency information included with one of the markers for the corresponding marked block.

23. The system as recited in claim 14, wherein the markers mark Java byte-code for the sequential code.

24. The system as recited in claim 14, wherein the markers mark Java source code for the sequential code.

25. The system as recited in claim 14, wherein the markers mark each block so that no block crosses the boundary of another unless the respective blocks are fully nested.

26. A computer accessible storage medium comprising program instructions, wherein the program instructions are executable to implement a framework for suggestive multi-threading, wherein the framework comprises:

an automated code marker tool configured to receive the sequential code;

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

insert two or more markers into the sequential code to suggest the identified blocks for concurrent execution;

a concurrent code generator configured to receive marked code comprising sequential code having a plurality of markers inserted in the sequential code to suggest blocks of code for concurrent execution with other parts of the code, wherein each of the markers comprises a block duration weight for estimating an execution time for the corresponding block, wherein the block duration weight indicates a predetermined approximate execution duration for the corresponding block, wherein the concurrent code generator is configured to;

perform an analysis of the marked code, according to at least the corresponding block duration weight of one or more of the marked blocks, to estimate performance benefits of concurrently executing the marked blocks of code and determine which marked blocks would meet a performance benefit threshold if executed concurrently;

and transform two or more of the marked blocks into corresponding concurrently executable tasks, wherein one of the marked blocks is not transformed into one of the concurrently executable tasks if the analysis indicates that the performance benefit threshold would not be met for that block; and

a scheduler configured to schedule two or more of the tasks for concurrent multi-threaded execution, wherein a thread for one of the two or more concurrently executable tasks executes concurrently with a thread for another of the two or more concurrently executable tasks corresponding to a different one of the blocks.

27. The computer accessible medium as recited in claim 26, wherein the concurrent code generator is further configured to estimate an execution time of each marked block.

28. The computer accessible medium as recited in claim 27, wherein the concurrent code generator is configured to estimate the execution time of one of the marked blocks according to the block duration weight of that block and a path length of that block.

29. The computer accessible medium as recited in claim 27, wherein the concurrent code generator is further configured to compare the estimated execution time of each marked block to an overhead for scheduling concurrent threads.

30. The computer accessible medium as recited in claim 26, wherein the markers mark a sub-method portion of a program method of the sequential code as one of the blocks marked for concurrent execution, wherein the concurrent code generator is further configured to transform the marked sub-method block into a task configured for concurrent execution.

31. The computer accessible medium as recited in claim 26, wherein each of the markers comprises a method call.

32. The computer accessible medium as recited in claim 31, wherein the method call is compatible with a programming language of the sequential code.

33. The computer accessible medium as recited in claim 26, wherein the scheduler is further configured to schedule one of the tasks for multi-threaded execution according to priority information included with one of the markers for the corresponding marked block.

34. The computer accessible medium as recited in claim 26, wherein the scheduler is further configured to schedule one of the tasks for multi-threaded execution according to dependency information included with one of the markers for the corresponding marked block.

35. The computer accessible medium as recited in claim 26, wherein the markers mark Java byte-code for the sequential code.

36. The computer accessible medium as recited in claim 26, wherein the markers mark Java source code for the sequential code.

37. The computer accessible medium as recited in claim 26, wherein the markers mark each block so that no block crosses the boundary of another unless the respective blocks are fully nested.