JP3269639B2 - Method of parallel execution of program loop - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to, for example, FORTRAN
The present invention relates to a loop parallel execution processing method of a program for executing each rotation of a loop on each computer in order to execute one loop in a program or the like in parallel by a plurality of computers.

2. Description of the Related Art In science and technology calculations using FORTRAN, a DO loop is used very often when processing an array. Therefore, if the rotation of the DO loop is shared by a plurality of computers and executed in parallel, the processing time can be reduced. Such parallel processing is called a loop slicing method. If the technology associated with the loop slicing method can be further improved, the program can be executed more efficiently.

[0003]

2. Description of the Related Art FIG. 4 is an explanatory diagram of the prior art. Assuming that there are two computers that can be executed in parallel, in the loop slicing method, for example, as shown in FIG.
The loop of the program 40 described in TRAN is parallelized, and the procedures 41-1 and 41- as shown in FIG.
It is divided into two and executed on two computers.

[0004] In the example shown in FIG.
And the even-numbered rotations are executed in parallel by the second computer. Here, the variable A used in the loop of (a) is used as temporary data for each rotation of the loop. When this is executed in parallel, it is necessary to prepare an area of A for each computer as in A1 and A2 shown in FIG. This is because if data being processed by the first computer is used by the second computer, inconsistency arises. The same applies to the opposite case.

[0005]

In a general program, a variable such as A shown in FIG. 4 is rarely used only in this loop, and usually the same variable is used in various parts in the program. Are used (in separate sense).

At this time, if the use of the variable A is closed in a loop by data flow analysis by the optimization function of the compiler, that is, if the use of the variable A can be treated as a variable separate from the use of other A, 4, it can be seen that a correct result can be obtained without substituting a value for the original variable A, so that parallelization is easily possible.

However, when there is a possibility that the value of the variable A used in this loop is used outside the loop (even if it is not actually referenced), it is necessary to substitute the value for the original variable A. Parallelization as shown in FIG. 4B is not possible, and complicated processing must be performed to guarantee the value of A.

Actually, in the example shown in FIG. 4, if the value of the variable A is used after the end of the loop, either the value of A1 of the processing result by the first computer or the value of A2 of the second processing result Complicated processing of checking whether the result is the final result and substituting the value into the original variable A at the end of the loop is required.

The present invention solves the above-mentioned problem. Even when the value of a variable substituted in a loop may be used outside the loop, parallelization can be performed and unnecessary processing can be performed. It is intended to be able to run.

[0010]

FIG. 1 is a diagram illustrating the principle of the present invention. As in the program 10 shown in FIG.
It is assumed that a value is substituted for the variable A in the loop, and the same variable A is referred to after the end of the loop.

[0011] The compiler 11 performs D processing for parallel processing.
An object program obtained by dividing the rotation of the O loop is output. The execution image of the object program is as follows. It is assumed that there are N computers capable of parallel processing constituting the multiprocessor 12. The computer 13-1 has one DO divided by dividing the rotation of the DO loop.
The loop execution image 14-1 is allocated, and the computer 13-
2 is assigned to another DO loop execution image 14-2 obtained by dividing the rotation of the DO loop.
Is assigned to another DO loop execution image 14-N obtained by dividing the rotation of the DO loop, and is executed in parallel by each computer.

If it is assumed that the computer 13-N is in charge of the final rotation of the loop, the DO loop execution image 14-N of the computer 13-N has a location for storing the value of the variable A. The area of the original variable A is used as it is. Other computers 13-1, 13-2, ...
Now, the replication area A1 of the variable A prepared for each computer
A2,... Are used. This guarantees the value of the variable A outside the loop.

[0013]

For example, when the loop slicing method described as the prior art is adopted, if the execution order in each computer does not break the rotational relationship in the original loop, the original at the end of execution in any one computer The value of the variable corresponding to the variable (A1 or A2 shown in FIG. 4B) is equal to the value to be taken by the original variable A.

Utilizing this, the area of the original variable A is directly used instead of the duplicate (A1 or A2) of A which is equal to the value to be taken of the original variable A. That is, as shown in FIG. 1, N computers 13-1 to 13-
If there is N, the variable of the computer that controls the final rotation in the N is used as it is as the original variable A instead of the replication area AN. As a result, at the end of all revolutions,
The final result is guaranteed as it is, and parallel processing can be performed at high speed.

[0015]

FIG. 2 shows an example of a language processing system for implementing the present invention, and FIG. 3 shows an embodiment of the present invention. In FIG. 2, reference numeral 20 denotes a source program described in, for example, FORTRAN; 21, a computer including a CPU and a memory; 22, a source program analyzing unit in the FORTRAN compiler 11; 23, an optimizing unit for optimizing the program; Is a loop detector that detects a DO loop, 24 is a data flow analyzer that analyzes the flow of data in the program, and 25 is whether a certain part of the program can be executed in parallel when an object program for a multiprocessor is output. A parallelism analyzing unit for analyzing, 27 is a parallel intermediate code generating unit for generating intermediate code for each computer when it can be executed in parallel, and 28 is a code for allocating registers and allocating areas and generating code of an object program. The generation unit, 29 is the compiler 11 Representing the object program is output.

An example in which the compiler 11 inputs, for example, the source program 20 shown in FIG. 3 and compiles it will be described. As a parameter to the compiler 11,
It is assumed that triple parallelization is specified. The source program analysis unit 22 analyzes the source program 20 and passes the analysis result to the optimization unit 23 in the form of an intermediate text. In the optimizing unit 23, the loop detecting unit 24 first detects a DO loop. In this example, the DO loop has the following contents.

[0017] The data flow analysis unit 25 checks the relationship between each variable and the like inside and outside the loop. Based on the result, the parallelism analysis unit 2
Step 6 determines whether parallel execution of this DO loop is possible. If parallel execution is possible, the parallel intermediate code generation unit 27 generates intermediate code for generating an object program obtained by dividing the rotation of the DO loop into three.

In this program, a value is unconditionally substituted for a variable T in a DO loop. In this case, it is clear that the value to be taken for the variable T is the value substituted at the time of the final rotation of the loop. Therefore, the parallel execution part assigned to each computer is fixedly divided in advance, and the computer responsible for the final rotation of the loop uses the area of the original variable T. This makes it possible to easily guarantee the final value of the variable T.

From this, the parallel intermediate code generation unit 27
Then, as shown in (b) of FIG. 3, (a) the first ３ ， of the rotation of the DO loop, (b) the middle ３ ， of the rotation of the DO loop, and (c) the last of the rotation of the DO loop. 1/3 of.

Then, the final rotation is not included (a) and
In (b), the duplicate areas T1 and T2 of the variable T are used, and in (c) including the final rotation, the area of the original variable T is used as it is. In FIG. 3B, the execution image is represented in the form of a source program for the sake of simplicity, but when the program is executed, the contents are expanded into machine language codes handled by the computer. .

When this code is distributed to a plurality of computers and executed, for example, a well-known UNIX system (US AT)
A process control function such as “fork” in an operating system developed by & T Company Bell Laboratories may be used. There are various other distribution methods, but they are not related to the gist of the present invention, and thus the description is omitted.

After executing the execution images (a) to (c) shown in (b) of FIG. 3, if the processing results are summarized by a control function such as “join”, the variable T can be referred to thereafter. Even so, the correct variable value substituted in the final rotation of the loop can be used.

In particular, in the FORTRAN DO loop,
Since the number of rotations of the loop is calculated immediately before execution, it is possible to fix the combination of rotation orders in parallel execution, and this method is effective. When the value of the loop variable i is divided by 3 and the remainder is 1 when the value of the loop variable i is divided by 3 instead of dividing into 3 such as the first part, the middle part, and the last part of the loop. , Loop variable i
The rotation of the loop may be divided and assigned to each computer, for example, when the value of is divisible by 3. However, in the case of such division, the determination process of the computer responsible for the final rotation may be complicated.

In the example shown in FIG. 3, although the rotation of the loop is divided into three, it is needless to say that the division can be performed according to the number of computers that can be executed in parallel. Can be.

[0025]

When a general-purpose program is executed in parallel,
The easiest parallelization is the parallel execution of each rotation of the loop. There are many programs in which variables used in a loop appear to be referenced outside the loop. In such a case, in the related art, it is necessary to suppress automatic parallelization or perform unnecessary synchronization processing. , Execution performance was reduced. According to the present invention, parallel execution can be performed in the same execution time as when a variable is used in a closed loop, so that execution performance is improved.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIG. 2 is a diagram showing an example of a language processing system for implementing the present invention.

FIG. 3 is a diagram showing an embodiment of the present invention.

FIG. 4 is an explanatory diagram of a conventional technique.

[Explanation of symbols]

 10 Program 11 Compiler 12 Multiprocessor 13-1 to 13-N Computer 14-1 to 14-N DO Loop Execution Image

Continuation of the front page (72) Inventor Hideki Nozaki 1015 Uedanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture Inside Fujitsu Limited (56) References JP-A-2-132525 (JP, A) JP-A-1-280862 (JP, A) JP-A-3-91036 (JP, A) JP-A-4-169934 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 9/45 G06F 15/16

Claims (1)

(57) [Claims] 1. A loop parallel execution processing method for a program in which a plurality of computers (13-1 to 13-N) divide a loop in a program (10) by a certain rotation unit and execute the program in parallel. For the variable (A) to which the value is substituted, computers other than the computer that controls the final rotation of the loop use the variable replication area (A1, A2,…) for each computer, and determine the final rotation of the loop. the computer that controls, based on the original variable (a)
A loop parallel execution method for a program, wherein the value of a variable outside a loop is guaranteed by using the same variable area .