JPH079623B2 - Compile method for multiprocessor - Google Patents

Description

The present invention relates to a processor for efficiently executing, on a multiprocessor, calculation of parallel loops of different types that can be executed in parallel, which is important in technical calculation and the like. It is related to the allocation method.

[Conventional technology]

The algorithm for assigning multiple parallel loops to multiple processors is
Parallel Processing Proceedings (1986), pages 519 to 527 (Proceedings of the Internatiomal
Conference on Parallel Processing, pp.519-527,198
6). In this case, assuming that the number of available processors is n, starting from the innermost parallel loop, sequentially proceeding to the outer parallel loop, 1 to n processors are assigned to the entire parallel loop of that level. Calculate the parallel processing time in each case. The parallel processing time for k units (1 ≦ k ≦ n) is j units for the level parallel rule itself and [k /
j] Of the processing times obtained when the units are allocated, 1 ≦ j ≦
The shortest k is adopted. It is assumed that the allocation when k = n when the outermost parallel loop is reached is the desired processor allocation. An important assumption in this allocation method is that the amount of computation in each level of parallel loops is considered to be constant for loop iterations.

[Problems to be solved by the invention]

In the numerical calculation, there are cases where a parallel structure represented by multiple parallel loops is adopted, but there are also cases where parallel loops with non-uniform computational complexity can further perform parallel processing. The above-mentioned prior art does not consider the parallel structure like the latter, and has a problem that it cannot be used as a processor allocation method when the latter is executed by a multiprocessor.

An object of the present invention is to perform parallel execution of both parallelism of parallel loops of different types and parallelism between parallel loops of different arithmetic operations even in such parallel loop groups. It is to generate object code based on a highly versatile processor allocation method in a multiprocessor system that minimizes time.

[Means for solving problems]

When m different parallel loops that can be executed in parallel with each other are executed in parallel on a multiprocessor system composed of n processors, the objectives are (1) 1 to n processors for each parallel loop. The parallel execution time for each case changed to (2) is calculated, and (2) the minimum processor allocation number giving the minimum parallel execution time is calculated for each parallel loop, and (3) the minimum processor allocation number for m parallel loops. When the sum of the above exceeds n, the number of allocated processors is reduced from any parallel loop, and the allocation that minimizes the parallel execution time under the total number of allocated processors n is determined. 4) It is realized by generating an object code for each processor according to the allocation.

[Action]

Process (1) for obtaining the parallel execution time for each case in which the number of processors is changed from 1 to n for each parallel loop, and the minimum number of processors assigned to give the minimum parallel execution time for each parallel loop The process (2) is a pre-process for the process (3) that minimizes the parallel execution time given to the entire program by n processors. The process (1) enables the process (3) to immediately obtain a parallel execution time evaluation when allocating an arbitrary number of processors to each parallel loop. Since the process (2) operates so as to minimize the number of required processors in advance within the range where the minimum execution time of each parallel loop is not exceeded, the search for the minimum parallel execution time with n units in the process (3) is significantly faster. Can be converted. In the process (3), when the sum of the minimum number of assigned processors for each of the m parallel loops exceeds n, the number of assigned processors is repeated from any of the parallel loops, and finally the total number of processors n It operates to determine the processor allocation that minimizes the parallel execution time under the platform. The allocation information determined by these processes is directly reflected in the object generation of the process (4), and it becomes possible to efficiently perform parallel processing on different types of parallel loop groups by a multiprocessor.

〔Example〕

An embodiment of the present invention will be described below with reference to the drawings. First
The figure shows the overall configuration of an embodiment of the present invention in the case of assigning processors to parallel loop groups capable of different types of parallel execution in a multiprocessor system. Second
The figure is a specific example of a program including a parallel loop group capable of different types of parallel execution. FIG. 3 is a description of a part for calculating the parallel execution time when the number of processors is changed in advance for each parallel loop, and FIG. 4 is a range in which the shortest calculation time is not increased for each parallel loop. The explanation of the process to minimize the number of processors in advance is shown in Fig. 5. When the total number of the minimum number of processors that can execute each parallel loop in the shortest time exceeds the number of available processors, the number of processors from any parallel loop It is an explanation of the processing for repeating the reduction of the above and putting the total into the usable number. FIG. 6 is a detailed explanatory view of the core part of FIG. 7 to 10 are explanations of the results obtained by applying the present embodiment to the program example of FIG. 2 in a four-processor system. FIG. 7 shows the calculation time evaluation result when 1 to 4 processors are assigned to each parallel loop. FIG. 8 shows the result of evaluating the minimum number of processors that gives the shortest calculation time for each parallel loop. FIG. 9 shows a process of reducing the total number of processors in each parallel loop to four. Figure 10 shows the result of the allocation to four units in the image of the actual execution status.

In FIG. 1, there are a source program 1 including a parallel loop group capable of performing parallel processing of different types as inputs and a processor configuration 6. The processor allocation process is a process 2 in which the parallel execution time is calculated in advance when the number of processors is changed for each parallel loop, and the number of processors is calculated in advance for each parallel loop within a range that does not exceed the shortest calculation time. Process 3 for keeping to the minimum, if the total number of the minimum number of processors that can execute the parallel loop in the shortest time exceeds the available number of processors, repeat the process of reducing the number of processors from one of the parallel loops and use the total. Process 4 for storing the available number. As a result, the number of allocated processors for each parallel loop is 5. Process 7 generates a multiprocessor object code from the above information.

In FIG. 2, the source program 1 is composed of three parallel loops doall and three sequential operation units, and these six operation units form a parallel case in which parallel execution is possible. Of these, case (4) to case (6) can be regarded as a parallel loop with one loop.

In FIG. 3, the evaluation of the parallel execution time for each parallel loop when the number of processors is changed from 1 to n is obtained by the formula 21. This evaluation is performed here for each parallel loop.

In FIG. 4, the initial minimum number of processors calculation process 31 calculates the minimum number of processors within a range not exceeding the shortest calculation time for each parallel loop. Next, the maximum case calculation process 32 for obtaining the maximum value of the parallel execution time of each parallel loop under the minimum number of processors is executed. Subsequently, the minimum number updating process 33 for further reducing the number of processors is executed for each parallel loop within a range not exceeding this maximum value.
From the above, the minimum number of processors that can process the entire parallel loop group in the shortest time is obtained for each parallel loop.

In FIG. 5, if the total number of these minimum number of processors is less than the number of usable units, the allocation ends there. If not, the one that gives the shortest time is obtained from the case where one is removed from the parallel loop having the minimum number of processors of two or more. The execution time at that time is t ₂ . Next, from the parallel loop with the minimum number of processors,
The dedicated processor release process 41 finds the one that gives the shortest calculation time among the cases where the platform is released and the parallel loop is fused with other parallel loops for calculation. The calculation time at that time is t ₁
And And t ₁ to reduce one of the number of processors the parallel loop gave t ₂ if or more greater equal t _2.
If it is the opposite, 1 from the parallel loop where the minimum number was 1
Adopt the case of reducing the number of units. If this is adopted,
Record which parallel loop the parallel loop that released the processor merged with. The above process is repeated until the total number of processors assigned to each parallel loop reaches the available number.

FIG. 6 shows a group of dedicated processor release processes 41 for deciding which parallel loop to reduce one from which the minimum number of processors was one. Here, assuming a virtual processor, the combination of parallel loop fusion that minimizes the calculation time is obtained by applying the critical path method.

FIG. 7 shows the parallel execution time calculation result 211 for each parallel loop, that is, the number of processors 1 to 4 for each case for the program of FIG. This calculation is performed using the calculation amount 29 of each case shown in FIG. FIG. 8 shows a result 311 of minimizing the number of processors, which is executed subsequent to FIG. 7. FIG. 9 shows a process 411 for reducing the number of allocated units, which shows how the total number of allocated units is reduced from 8 to 4 which is the number of usable processors. In FIG. 10, it is the final result of FIG. The parallel execution status 600 for a total of four units is shown as an image during execution. The object code representing the processing content of each processor determined in FIG. 10 is generated in 7.

In the prior art, it was almost impossible to assign a processor to a parallel loop group capable of different types of parallel execution as shown in this embodiment, but according to this embodiment, as shown in FIG. This has the effect of enabling processor allocation that can effectively utilize both parallelism for each and parallelism between parallel loops.

〔The invention's effect〕

According to the present invention, for a parallel structure consisting of a large number of different parallel loop groups appearing in an actual program, the parallel execution time is calculated based on the amount of computation and the number of loops of each parallel loop under the number of available processors. Since the number of processors can be distributed to each parallel loop so as to minimize, there is an effect that general-purpose processor allocation with good execution efficiency in a general multiprocessor system becomes possible.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of one embodiment of the present invention. Second
The figure is a diagram showing a specific example of the target parallel program and the required calculation amount for each case therein. FIG. 3 is a flowchart of parallel execution time evaluation processing, FIG. 4 is a flowchart of minimum processor number evaluation processing, FIG. 5 is a flowchart of processor number reduction processing, and FIG. 6 is a flowchart of dedicated processor release processing. 7th ~
FIG. 10 is an explanatory diagram of a result of applying this embodiment to the parallel program of FIG. 2 in a four-processor system. Explanation of code 2 …… Parallel loop execution time calculation process, 3 …… Processor number minimization process, 4 …… Allocation number reduction process, 31 ……
Initial minimum number calculation process, 32 ... Maximum case calculation process, 33 ...
… Minimum number of units update processing, 41 …… Dedicated processor release processing.

Claims (1)

[Claims] 1. A minimum parallel for each case in which the number of processors is changed from 1 to n in each parallel loop for m different parallel loops that can be executed in parallel in a source program. Find the execution time,
(2) Obtain the minimum number of allocated processors that gives the minimum parallel execution time for each parallel loop, and (3) If the total number of the minimum allocated processors for each of the m parallel loops exceeds n, then 2 or more. When reducing one unit from one of the assigned parallel loops and when changing one of the parallel loops assigned to only one to the processor to which another parallel loop is assigned. By repeatedly adopting the allocation that gives the minimum time, and finally, the allocation that minimizes the parallel execution time under the total number n of processor allocations is determined, and (4) each allocation determination is performed. A compilation method for multiprocessors characterized by generating an object code for each processor.