System and method for block-based concurrentization of software code
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/45
G06F-009/46
출원번호
US-0277504
(2002-10-22)
등록번호
US-7346902
(2008-03-18)
발명자
/ 주소
Dutt,Bala
Kumar,Ajay
Susarla,Hanumantha R.
출원인 / 주소
Sun Microsystems, Inc.
대리인 / 주소
Kowert,Robert C.
인용정보
피인용 횟수 :
15인용 특허 :
35
초록▼
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 marki
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.
대표청구항▼
What is claimed is: 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 c
What is claimed is: 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.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (35)
Kamada, Jun; Yuhara, Masanobu; Ono, Etsuo, Computer system process scheduler determining and executing processes based upon changeable priorities.
Briggs Preston P. (Houston TX) Cooper Keith D. (Houston TX) Kennedy ; Jr. Kenneth W. (Houston TX) Torczon Linda M. (Houston TX), Digital computer register allocation and code spilling using interference graph coloring.
Spix George A. ; Wengelski Diane M. ; Hawkinson Stuart W. ; Johnson Mark D. ; Burke Jeremiah D. ; Thompson Keith J. ; Gaertner Gregory G. ; Brussino Giacomo G. ; Hessel Richard E. ; Barkai David M. ;, Method and apparatus for user side scheduling in a multiprocessor operating system program that implements distributive scheduling of processes.
Beadle Bruce Anthony ; Brown Michael Wayne ; Paolini Michael Anthony ; Rothert Douglas Scott, Method and apparatus to selectively control processing of a method in a java virtual machine.
Cooke, Laurence H.; Phillips, Christopher E.; Wong, Dale, Method for compiling high level programming languages into embedded microprocessor with multiple reconfigurable logic.
Stubbs David D. (Portland OR) Barnett Mark P. (Portland OR) Greenseth William A. (Portland OR), Method of generating instruction sequences for controlling data flow processes.
Spix George A. (Eau Claire WI) Wengelski Diane M. (Eau Claire WI) Hawkinson Stuart W. (Eau Claire WI) Johnson Mark D. (Eau Claire WI) Burke Jeremiah D. (Eau Claire WI) Thompson Keith J. (Eau Claire W, System and method for controlling a highly parallel multiprocessor using an anarchy based scheduler for parallel executi.
Reeve Christopher L. (18 Salisbury Rd. Brookline MA 02146) Shavit Tani (One Seaborn Pl. Lexington MA 02173) Rothnie ; Jr. James B. (47 Monmouth St. Brookline MA 02146) Peters Timothy G. (11 Wilbur St, System for parallel processing that compiles a filed sequence of instructions within an iteration space.
Bell, Jr., Robert H.; Capps, Jr., Louis Bennie; Paolini, Michael A.; Shapiro, Michael Jay, Parallelizing single threaded programs by performing look ahead operation on the single threaded program to identify plurality of instruction threads prior to execution.
Bell, Jr., Robert H.; Capps, Jr., Louis Bennie; Paolini, Michael A.; Shapiro, Michael Jay, Resolving conflicts by restarting execution of failed discretely executable subcomponent using register and memory values generated by main component after the occurrence of a conflict.
Sanchez,Jesus; Garcia,Carlos; Madriles,Carlos; Rundberg,Peter; Marcuello,Pedro; Gonzalez,Antonio, Selection of spawning pairs for a speculative multithreaded processor.
Sager, David J.; Sasanka, Ruchira; Gabor, Ron; Raikin, Shlomo; Nuzman, Joseph; Peled, Leeor; Domer, Jason A.; Kim, Ho-Seop; Wu, Youfeng; Yamada, Koichi; Ngai, Tin-Fook; Chen, Howard H.; Bobba, Jayaram; Cook, Jeffery J.; Shaikh, Omar M.; Srinivas, Suresh, Systems, apparatuses, and methods for a hardware and software system to automatically decompose a program to multiple parallel threads.
Bobba, Jayaram; Sasanka, Ruchira; Cook, Jeffrey J.; Das, Abhinav; Krishnaswamy, Arvind; Sager, David J.; Agron, Jason M., Using control flow data structures to direct and track instruction execution.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.