Method and system for dynamically parallelizing application program

• US 8,650,384 B2
• Filed: 04/27/2010
• Issued: 02/11/2014
• Est. Priority Date: 04/29/2009
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd., University of Southern California
• Original Assignee: Samsung Electronics Co. Ltd., University of Southern California
• Inventors: Lee, Seung Won, Lee, Shi Hwa, Kang, Dong-In, Kang, Mikyung
• Primary Examiner(s): Miller, Alan S
• Application Number:
  US12/662,657
• Publication Number:
  US 20100281489A1
• Time in Patent Office: 1,386 Days
• Field of Search: None
• US Class Current: 712/203
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Provided is a method and system for dynamically parallelizing an application program. Specifically, provided is a method and system having multi-core control that may verify a number of available threads according to an application program and dynamically parallelize data based on the verified number of available threads. The method and system for dynamically parallelizing the application program may divide a data block to be processed according to the application program based on a relevant data characteristic and dynamically map the threads to division blocks, and thereby enhance a system performance.

Claims

1. A system for dynamically parallelizing an application program, the system comprising:

a block generator to generate a data block having a size corresponding to a data area to be processed by the application program, using a block function;

a multi-core controller including at least one processing device to assign, according to a thread allocation scheme and the generated data block, a unique operation of each of a number of available threads that are generated while running the application program;

a monitoring unit to monitor the multi-core controller to determine, after a performance of at least one of the unique operations, the number of available threads, during the running of the application program; and

a decision unit to selectively divide the data block using a map function and change the thread allocation scheme based on the determined number of available threads, during the running of the application program.

2. The system of claim 1, wherein the decision unit determines a division type of the data block and the thread allocation scheme based on a characteristic of data stored in the data block and the determined number of available threads.

3. The system of claim 1, wherein the thread allocation scheme corresponds to any one of a block allocation scheme of allocating a same thread to an adjacent division block, and a cycling scheme of alternately allocating a thread according to a round-robin scheme.

4. The system of claim 1, further comprising:

a scatter unit to generate threads of performing a same operation using a distribution, and to allocate the threads to division blocks, respectively, according to the determined thread allocation scheme; and

a gather unit to combine the threads using a combination function.

5. The system of claim 4, further comprising:

a view unit to read data from a corresponding division block in response to a request of each of the threads, and to provide the read data to a corresponding thread, or to store a result of the thread in the corresponding division block using a view function.

6. The system of claim 4, further comprising:

a change unit to selectively increase or decrease the number of threads using a change function when a change in the number of available threads is detected by the monitoring unit.

7. The system of claim 1, further comprising:

a performance measurement unit to measure or predict a performance of the thread allocation system according to a division type of the data block and the thread allocation scheme,

wherein the decision unit determines the thread allocation scheme and the division type of the data block having a determined optimum performance based on the measurement or prediction of the performance measurement unit.

8. A system for dynamically parallelizing an application program, the system comprising:

a multi-core controller including at least one processing device to assign a unique operation of each of plural threads that are generated while running the application program;

a block generator to generate a data block having a size corresponding to a data area to be processed by the application program, using a block function;

a monitoring unit to monitor the multi-core controller to determine a number of available threads; and

a decision unit to divide the data block using a map function, and to dynamically determine a thread allocation scheme, further comprising;

a performance measurement unit to measure or predict a performance of the thread allocation system according to a division type of the data block and the thread allocation scheme,

wherein the decision unit dynamically determines the thread allocation scheme and the division type of the data block having a determined optimum performance based on the measurement or prediction of the performance measurement unit.

9. A system for dynamically parallelizing an application program, the system comprising:

a multi-core controller including at least one processing device to assign a unique operation of each of plural threads that are generated while running the application program;

a block generator to generate a data block having a size corresponding to a data area to be processed by the application program, using a block function;

a monitoring unit to monitor the multi-core controller to determine a number of available threads;

a decision unit to divide the data block using a map function, and to dynamically determine a thread allocation scheme;

a scatter unit to generate threads of performing a same operation using a distribution, and to allocate the threads to division blocks, respectively, according to the determined thread allocation scheme;

a gather unit to combine the threads using a combination function; and

a change unit to selectively increase or decrease the number of threads using a change function when a change in the number of available threads is detected by the monitoring unit.

10. The system of claim 9, wherein, when a change in the number of available threads is detected by the monitoring unit, the change unit requests the decision unit to change a division type of the data block and the thread allocation scheme.

11. A method for dynamically parallelizing an application program in a system, the method comprising:

generating, using at least one processing device, a data block having a size corresponding to a data area to be processed by the parallel application program, using a block function;

assigning, according to a thread allocation scheme and the generated data block, a unique operation of each of a number of available threads that are generated while running the application program;

determining, after a performance of at least one of the unique operations, the number of available threads, during the running of the application program;

selectively dividing the data block using a map function and changing the thread allocation scheme based on the determined number of available threads, during the running of the application program; and

generating threads according to the selectively changed thread allocation scheme to allocate the threads to the selectively divided data blocks, respectively.

12. The method of claim 11, wherein the selective dividing of the data block and changing of the thread allocation scheme further comprises determining a division form of the data block and the thread allocation scheme based on a characteristic of data stored in the data block and the determined number of available threads.

13. The method of claim 11, wherein the thread allocation scheme corresponds to any one of a block allocation scheme of allocating a same thread to an adjacent division block, and a cycling scheme of alternately allocating a thread according to a round-robin scheme.

14. The method of claim 11, wherein the selective dividing of the data block and changing of the thread allocation scheme further comprises:

measuring or predicting a performance of the thread allocation system according to a division type of the data block and the thread allocation scheme; and

determining the thread allocation scheme and the division form of the data block having a determined optimum performance based on the measured or predicted performance.

15. The method of claim 11, wherein the generating of the threads further comprises:

generating threads of performing a same operation using a scatter function, to allocate the threads to division blocks, respectively, according to the selectively changed thread allocation scheme;

reading data from a corresponding division block in response to a request of each of the threads, to provide the read data to a corresponding thread using a view function;

performing a unique operation in each of the threads;

storing a result of the thread in a corresponding division block using the view function; and

combining the threads using a gather function.

16. The method of claim 15, wherein the generating of the threads further comprises:

selectively increasing or decreasing the number of threads using a change function when a change in the determined the number of available threads is detected.

17. The method of claim 16, wherein the generating of the threads further comprises:

changing a division type of the data block and the thread allocation scheme using the map function when the change in the determined number of available threads is detected.