Method and system for dynamically parallelizing application program

• US 9,189,277 B2
• Filed: 07/22/2013
• Issued: 11/17/2015
• 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:
  US13/947,629
• Publication Number:
  US 20130312003A1
• Time in Patent Office: 848 Days
• Field of Search: None
• US Class Current: 1/1
• 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 including at least one processing device to assign an operation to each of threads that are generated while running the application program;

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

a change unit to change the number of threads based on the determined number of available threads, during the running of the application program,

wherein the change unit selectively increases or decreases the number of threads when a change in the determined number of available threads is detected.

2. The system of claim 1, further comprising:

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

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

assigning, using at least one processing device, a unique operation to each of threads that are generated while running the application program;

determining the number of available threads, during the running of the application program; and

changing the number of threads based on the determined number of available threads, during the running of the application program,

wherein the changing of the number of threads comprises selectively increasing or decreasing the number of threads when a change in the determined number of available threads is detected.

4. The method of claim 3, further comprising:

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.

5. The method of claim 3, further comprising:

dividing a data block and determining a thread allocation scheme based on the determined number of available threads during the running of the application program; and

generating threads based on the thread allocation scheme and allocating the generated threads to the divided data blocks.

6. The method of claim 5, wherein the dividing of the data block and determining of the thread allocation scheme further comprise:

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.

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

8. The method of claim 5, wherein the dividing of the data block and determining of the thread allocation scheme further comprise:

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

determining the thread allocation scheme and the division type of the data block based on the measured or predicted performance.

9. The method of claim 5, further comprising:

generating threads of performing a same operation using a scatter function and allocating the generated threads to division blocks, respectively, according to the 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 an 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.

10. The method of claim 3, further comprising:

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

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

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

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

a change unit to change the number of threads based on the determined number of available threads, during the running of the application program; and

a decision unit to divide a data block, and to determine a thread allocation scheme based on the determined number of available threads.

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

13. The system 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 system of claim 11, further comprising:

a performance measurement unit to measure or predict a performance of the 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 based on the measurement or prediction of the performance measurement unit.

15. The system of claim 11, further comprising:

a scatter unit to generate threads 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.

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

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