PREPROCESSOR TO IMPROVE THE PERFORMANCE OF MESSAGE-PASSING-BASED PARALLEL PROGRAMS ON VIRTUALIZED MULTI-CORE PROCESSORS

• US 20070038987A1
• Filed: 08/09/2006
• Published: 02/15/2007
• Est. Priority Date: 08/10/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Komatsu, Hideaki, Ohara, Moriyoshi, Inoue, Hiroshi, Moriyama, Takao, Sohda, Yukihiko
• Granted Patent: US 7,503,039 B2
• Time in Patent Office: Days
• US Class Current: 717/151
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions

Abstract

Provided is a complier which optimizes parallel processing. The complier records the number of execution cores, which is the number of processor cores that execute a target program. First, the compiler detects a dominant path, which is a candidate of an execution path to be consecutively executed by a single processor core, from a target program. Subsequently, the compiler selects dominant paths with the number not larger than the number of execution cores, and generates clusters of tasks to be executed by a multi-core processor in parallel or consecutively. After that, the compiler computes an execution time for which each of the generated clusters is executed by the processor cores with the number equal to one or each of a plurality natural numbers selected from the natural numbers not larger than the number of execution cores. Then, the compiler selects the number of processor cores to be assigned for execution of each of the clusters based on the computed execution time.

Claims

1. A compiler apparatus, which optimizes execution of a target program to be compiled by a multi-core processor, comprising:

a recording section for recording the number of execution cores, which is the number of processor cores for execution of the target program, among processor cores included in the multi-core processor;

a path detecting section for detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a single processor core, from the target program;

a cluster generating section for selecting dominant paths with the number not larger than the number of execution cores, and for thereby generating clusters of tasks to be executed by a multi-core processor any one of in parallel and in a sequential manner;

a time computing section for computing execution times for which each of the generated clusters is executed by the processor cores with the numbers equal to one or each of a plurality of natural numbers selected from the natural numbers not larger than the number of the execution cores; and

a core number selecting section for selecting the number of the processor cores to be assigned for the execution of each of the generated clusters based on the computed execution times in order to reduce the total execution time of the target program.

2. The compiler apparatus according to claim 1,

wherein the time computing section computes execution times for which each of the generated clusters is executed by the processor cores with the number equal to each of the natural numbers from one to the number of the execution cores, and

wherein the core number selecting section selects the number of processor cores to be assigned for the execution of each of the generated clusters based on the computed execution times.

3. The compiler apparatus according to claim 1,

wherein the cluster generating section combines at least two of the clusters, which can be executed any one of in a sequential manner and in parallel, into a cluster group of an upper-level hierarchy of the clusters, and combines at least two cluster groups of the upper-level hierarchy, which can be executed any one of in a sequential manner and in parallel, into a cluster group of a further upper-level hierarchy, thereby generating a series-parallel graph indicating dependency relations in a hierarchical execution order of the plurality of clusters, and

wherein the core number selecting section computes execution times for which the cluster groups of the lower-level hierarchy are executed by the processor cores with the number equal to one or each of a plurality of natural numbers selected from the natural numbers not larger than the number of processor cores, in order from the cluster group of the lowest-level hierarchy, and selects the number of the processor cores to be assigned respectively to any one of at least two of the clusters executable in parallel and the cluster groups, which are positioned in a upper-level hierarchy than the clusters, based on the computed execution times in order to reduce the total execution times of the cluster groups of the lower-level hierarchy, thereby selecting the number of processor cores to be assigned to each of the clusters.

4. The compiler apparatus according to claim 1,

wherein the cluster generating section uses each of the plurality of clusters as a node, generates a node indicating a sequential execution part, where the plurality of clusters should be sequentially executed, in an upper-level hierarchy of the plurality of nodes corresponding to the multiple clusters having the dependency relations in an execution order, and generates a node indicating a parallel execution part, where the plurality of clusters can be executed in parallel, in the upper-level hierarchy of the plurality of nodes corresponding to the plurality of clusters which can be executed in parallel,

wherein the cluster generating section further generates a node indicating that the plurality of parallel execution parts or the sequential execution parts are further sequential execution parts, in the upper-level hierarchy of the multiple nodes corresponding to the multiple parallel execution parts or the sequential execution parts having the dependency relation in the execution order, or generates a node indicating that the multiple parallel execution parts or the sequential execution parts are further parallel execution parts, in the upper-level hierarchy of the multiple nodes corresponding to the multiple parallel execution parts where parallel execution is possible or the sequential execution parts, thereby forming a series-parallel graph, and

wherein the core number selecting section defines, as partial problems, problems with selection of the number of processor cores to be assigned to any one of the clusters constituting the sequential execution part, or the parallel execution part, and any one of the sequential execution parts and the parallel execution parts, in order to optimize an execution time of each of the sequential execution parts and the parallel execution parts, and solves each of the partial problems by a dynamic programming method, thereby selecting the number of processor cores to be assigned to each of the clusters to optimize the execution time of the target program.

5. The compiler apparatus according to claim 1, further comprising:

a cyclic dependency detecting section for detecting a cyclic dependency in each of the detected dominant paths, the cyclic dependency meaning that any one of the tasks in each of the detected dominant paths depends on processing of a task in another execution path including a task which further depends on any one of the tasks in the dominant path,

wherein the cluster generating section selects the detected dominant path having less cyclic dependencies by giving priority over the other dominant paths, and generates a cluster including the selected dominant path and the other tasks.

6. The compiler apparatus according to claim 5, further comprising:

an adjacent path selecting section for selecting an adjacent path of each of the detected dominant paths, the adjacent path being another dominant path including a task directly transmitting data between any of the tasks in each of the detected dominant paths,

wherein the cluster generating section selects a dominant path having fewer adjacent paths by giving priority over the other dominant paths and generates a cluster including the selected dominant path and the other tasks, on condition that the numbers of detected cyclic dependencies in each of the dominant paths are the same.

7. The compiler apparatus according to claim 1, wherein the cluster generating section comprises:

a candidate selecting section for selecting a candidate task, which is a candidate of a task to be included in the cluster together with the dominant path, in at least one dominant path;

a path number computing section for computing the total number of dominant paths included in the cluster when the candidate task is included in the cluster together with the dominant path; and

a task adding section for generating the cluster including the candidate task, on condition that the total number of computed dominant paths is not larger than the number of the execution cores,

wherein the candidate selecting section further selects another task as another candidate task to be included in the cluster, on condition that the candidate task is added to the cluster.

8. The compiler apparatus according to claim 7, further comprising:

a communication traffic volume computing section for computing a sum of communication traffic volumes in which the candidate task communicates with each of the multiple tasks in the cluster,

wherein the task adding section generates the cluster including the selected candidate task, on further condition that the sum of the communication traffic volumes is larger than a predetermined reference value.

9. The compiler apparatus according to claim 7, further comprising:

an idle rate computing section for computing a time rate at which the processor is in an idle state in executing the task in the cluster by the processor cores with the number corresponding to the number of the execution cores when the selected candidate task is included in the cluster together with the dominant path,

wherein the task adding section generates a cluster including the selected candidate task on further condition that the time rate at which the processor is in the idle state is smaller than a predetermined reference value.

10. The compiler apparatus according to claim 1, wherein the execution time computing unit computes execution times of each of the clusters by estimating that a preestimated maximum required time is needed for any one of task switching from an inside of the cluster to an outside thereof and task switching from the outside of the cluster to the inside thereof.

11. The compiler apparatus according to claim 1, further comprising:

a task selecting section for selecting at least one second task of a first task in the target program, the second task depending on a processing result of a first task; and

a reduced amount computing section for computing a reduced amount of a task switching time to be reduced when the second task is executed after the first task by the same processor core in comparison with a task switching time when the first task and the selected second task are executed by different processor cores,

wherein the path detecting section detects the second task and the first task inclusive in the dominant path, the second task having a maximum reduced amount to be computed.

12. A compiler apparatus for detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a same processor core from a target program to be compiled, comprising:

a task selecting section for selecting at least one second task of the first task in the target program, the second task depending on a processing result of a first task in the target program;

a reduced amount computing section for computing a reduced amount of a task switching time to be reduced when the second task is executed after the first task by the same processor core in comparison with a task switching time when the first task and the selected second task are executed by different processor cores; and

a path detecting section for detecting a second task and the first task inclusive in the dominant path, the second task having a maximum reduced amount to be computed.

13. The compiler apparatus according to claim 12,

wherein the reduced amount computing section further computes a reduced amount for each of the precedent tasks, the processing result of which the second task depends on, the reduced amount being reduced by executing the second task after the precedent task by the same processor core, in comparison with the task switching time when the precedent task and the second task are executed by the different processor cores, and

wherein the path detecting section detects the second task so as to be included in the dominant path together with the first task, on further condition that the reduced amount for the first task is the largest among the multiple precedent tasks.

14. The compiler apparatus according to claim 12,

wherein the target program is executed by a multi-core processor, and the multi-core processor includes a plurality of sets of a processor core, a local memory connected to the processor core, and a DMA controller, which transmits a command code or data between a main memory and the local memory, the main memory being connected to an outside of the multi-core processor,

the complier apparatus further comprising a recording section for recording a required time for transmitting a processing result of a precedent task to a following task via the local memory and a processing time for transmitting the processing result via the main memory,

wherein the reduced amount computing section computes the reduced amount based on a difference value between the required time for transmitting the processing result via the local memory and the processing time for transmitting the processing result via the main memory, and

wherein the path detecting section detects a second task and the first task inclusive in the dominant path, the second task having a maximum reduced amount to be computed.

15. The compiler apparatus according to claim 14,

wherein the recording section further records a required time for reading an execution code of the following task, from the main memory into the local memory, in place of an execution code of the precedent task, and

wherein the reduced amount computing section computes a time, as the reduced amount when the first task and the second task execute a same execution code, by adding the required time for reading the execution code from the main memory into the local memory to the reduced amount when the first task and the second task execute different execution codes.

16. A compile method by a compiler apparatus, which optimizes execution of a target program to be compiled by a multi-core processor, wherein the compiler apparatus comprises a recording section which records the number of the execution cores which is the number of processor cores for execution of the target program among processor cores included in the multi-core processor,

the compile method comprising the steps of:

detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a single processor core, from the target program;

selecting dominant paths with the number not larger than the number of the execution cores, thereby generating clusters of the tasks to be executed by the multi-core processor any one of in parallel and in succession;

computing execution times for which each of the clusters is executed by the processor cores with the number equal to one or each of a plurality of natural numbers selected from the natural numbers not larger than the number of the execution cores; and

selecting the number of the processor cores to be assigned for the execution of each of the generated clusters based on the computed execution times, in order to reduce the total execution time of the target program.

17. A compile method for detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a single processor core, from a target program to be compiled,

the compile method comprising the steps of:

selecting at least one second task of a first task in the target program, the second task depending on a processing result of a first task;

computing a reduced amount of a task switching time to be reduced when the second task is executed after the first task by the same processor core in comparison with a task switching time when the first task and the selected second task are executed by different processor cores; and

detecting a second task, which has a maximum reduced amount to be computed, including in the dominant path together with the first task.

18. A compiler program which causes an information processing system to function as a compiler apparatus, which optimizes execution of a target program to be compiled by a multi-core processor,

the compiler program causing the information processing system to function as:

a recording section for recording the number of execution cores which is the number of processor cores for execution of the target program among processor cores included in the multi-core processor;

a path detecting section for detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a single processor core, from the target program;

a cluster generating section for selecting dominant paths with the number not larger than the number of the execution cores, and for generating a cluster of tasks to be executed by the multi-core processor any one of in parallel and in succession;

a time computing section for computing execution times for which each of the clusters is executed by the processor cores with the number equal to one or each of a plurality of natural numbers selected from the natural numbers not larger than the number of the execution cores; and

a core number selecting section for selecting the number of the processor cores to be assigned for the execution of each of the generated clusters, based on the computed execution times in order to reduce the total execution time of the target program.

19. A compiler program which causes an information processing system to function as a compiler apparatus for detecting a dominant path, which is a candidate of an execution path of one or more tasks to be consecutively executed by a same processor core, from a target program to be compiled,

the compiler program causing the information processing system to function as:

a task selecting section for selecting at least one second task of a first task in the target program, the second task depending on a processing result of the first task;

a reduced amount computing section for computing a reduced amount of a task switching time to be reduced when the second task is executed after the first task by the same processor core in comparison with a task switching time when the first task and the selected second task are executed by different processor cores; and

a path detecting section for detecting a second task, which has a maximum reduced amount to be computed, including in the dominant path together with the first task.