Method and system for dynamically parallelizing application program

• US 20100281489A1
• Filed: 04/27/2010
• Published: 11/04/2010
• Est. Priority Date: 04/29/2009
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd., University of Southern California
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kang, Mikyung, Kang, Dong-In, Lee, Seung Won, Lee, Shi Hwa
• Granted Patent: US 8,650,384 B2
• Time in Patent Office: Days
• US Class Current: 718/106
• 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 multi-core controller 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.

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 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.

5. 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.

6. The system of claim 5, 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.

7. The system of claim 5, 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.

8. The system of claim 7, 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.

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

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

determining a number of available threads;

dividing the data block using a map function, and dynamically determining a thread allocation scheme; and

generating threads according to the thread allocation scheme to allocate the threads to division blocks, respectively.

10. The method of claim 9, wherein the dividing of the data block and the dynamically determining 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.

11. The method of claim 9, 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.

12. The method of claim 9, wherein the dividing of the data block and the dynamically determining 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.

13. The method of claim 9, 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 dynamically determined 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.

14. The method of claim 13, 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.

15. The method of claim 14, 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.