JPH054712B2 - - Google Patents

Description

[Detailed Description of the Invention] [Summary] When compiling a program to be automatically vectorized, data dependencies in the outer loop regarding vector operation sequences after vectorization are grasped, and according to the results, data dependencies in the outer loop are By setting the rotation speed to 1/N and expanding the vector operation sequence N times, the execution performance of the compiled program is improved.

[Industrial application field]

The present invention relates to a processing method for compiling a program executed by a data processing device having a vector computer, and more particularly to a vector operation string loop unrolling processing method for unrolling a vector operation string in a loop.

[Conventional technology]

For example, in order to execute a program written in the FORTRAN language or the like using a vector computer, a compiler is used that automatically generates vector operation sequences for DO loop arrays and the like. Increasing the vectorization rate of objects generated by this compiler is considered an important issue in order to improve the execution performance of vector computers. However, in order to make the most effective use of a vector computer, which is a hardware resource, it is also necessary to optimally schedule the vector operation sequence after vectorization.

Optimal scheduling refers to arranging vector operation sequences in a way that increases the density of data flowing through the load/store pipeline, addition pipeline, multiplication pipeline, etc. in a vector computer, and reduces the waiting time for execution. It is.

In order to achieve this optimal scheduling, programs have conventionally been manually tuned by users using source-level scalar images.

[Problem that the invention seeks to solve]

However, when a user manually tunes a source program, the following problems occur.

A source program tuned to a vector version using a scalar image may have lower execution performance on a general-purpose computer that does not have vector processing capabilities.

Tuning requires a great deal of effort and time.

The descriptive nature of the source program is impaired.

Performance decreases due to user tuning,
It may have the opposite effect.

In order to solve the above problems, the present invention performs loop unrolling on a vector operation sequence.
The purpose is to provide a method for automatically generating optimized objects from a source program.

[Means for solving problems]

FIG. 1 shows a block diagram of an example of the basic configuration of the present invention.

In FIG. 1, 10 is a source program written in a high-level language, 11 is a processing unit consisting of a CPU, memory, etc., 12 is a compiler that translates the source program 10 into machine language objects, 13 is a program input unit, and 14 is a 15 is a data dependency analysis unit; 16 is an unrolling execution condition determination unit; 17 is an unrolling processing unit; 18 is an object generation unit; 19 is an object consisting of a machine code string corresponding to the source program 10; represents an actual program.

The program input section 13 includes a source program 1
Enter the source statement to be processed starting from 0. By parsing this input program,
Intermediate text is generated. The compiler 12 is
It has an automatic vectorization function, and the vectorization processing unit 14 decodes the intermediate text, detects what can be vectorized, and generates a vector operation sequence.

When the inner loop in the multiple loop is vectorized by the vectorization processing section 14, the data dependence analysis section 15 analyzes the data dependence relation in the outer loop of the vectorized vector operation sequence. It is something to do.

The unrolling execution condition determining unit 16 determines whether or not unrolling is possible by searching a table in which unrolling permission information is registered in advance for each data dependency relationship based on the analysis result by the data dependency relationship analysis unit 15. judge. Unrolling the loop means reducing the number of rotations of the outer loop by 1/
N (N is an integer of 2 or more), and the vector operation sequence is expanded N times.

When the unrolling execution condition determining unit 16 determines that unrolling is possible, the unrolling processing unit 17 decomposes the vector operation sequence,
Perform loop unrolling. The number of rotations in the outer loop is reduced to 1/N, but if a fraction occurs, a processing instruction sequence based on the remaining vector operation sequence is added to the outside of the loop.

The vectorized and unrolled intermediate text is further optimized by other means as necessary. The object generation unit 18 finally generates an object program 19.

[Effect]

The operation of the present invention will be explained below using loop unrolling of a FORTRAN program as an example.

For example, DO 10 J=1,100 DO 10 I=1,10000 A(I,J)=B(I,J)+C(I,J)*
In the double-loop program D(I,J) 10 CONTINUE, the vectorization processing unit 14 vectorizes the inner loop as follows.

DO 10 J=1,100 A(*,J)=B(*,J)+C(*,J)*
D(*,J) 10 CONTINUE Here, "*" in the array is a vector parameter that takes a value from 1 to 10,000, and the vector length is 10,000.

Regarding this, the unrolling processing unit 17
Perform loop unrolling as follows.

DO 10 J=1,100,2 A(*,J)=B(*,J)+C(*,J)*
D(*,J) A(*,J+1)=B(*,J+1)+C(*,
J+1)*D(*,J+1) 10 CONTINUE In other words, by doubling the increment value of the loop control variable, the loop rotation speed of the outer loop is halved,
Decomposes the internal vector operation sequence and doubles it. 3
The same applies to double expansion and above. The expanded vector operation sequence is individually processed by the pipeline in the vector calculator, making it possible to increase the processing density of the pipeline and optimizing pipeline scheduling. .

Furthermore, in the following cases, vector text optimization becomes possible by optimizing common expressions in vector operations. For example, assume that the vector operation sequence after vectorization is DO 10 J=1,100 A(*, J+1)=B(*, J)+A(*, J) 10 CONTINUE. Here, "*" in the array is a vector parameter that takes values from 1 to 10,000, as in the previous example.

Regarding this, the unrolling processing unit 17
Perform loop unrolling as follows.

DO 10 J=1,100,2 A(*,J+1)=B(*,J)+A(*,J)
... A(*, J+2)=B(*, J+1)+A(*,
J+1) ... 10 CONTINUE The second term on the right side of this vector operation sequence is
Takes the same value as the left side of the vector operation sequence. When the vector calculation sequence is executed by the vector computer, A(*, J+1) is obtained in the vector register, so there is no need to load A(*, J+1) when executing the next vector calculation sequence.
This enables fast execution and optimization of vector text.

〔Example〕

FIG. 2 is a diagram illustrating a process of an embodiment of the present invention, FIG. 3 is an example of an unrolling availability table, and FIG. 4 is a diagram illustrating the relationship between data dependency values and the number of unrolling expansions.

The loop unrolling process according to the present invention is performed, for example, as shown in FIG. Note that this process is called when a vectorized operation sequence exists in the loop to be processed. Processing numbers ~ in the following explanation are numbers shown in Figure 2 ~
corresponds to

Based on the data dependency value, an unrolling possibility table as shown in FIG. 3 is searched.

Note that the data dependency value and the unrolling possibility table will be described in detail later.

Based on the result of searching the unrolling possibility table, it is determined whether unrolling is possible or not.
If unrolling is not possible, the process proceeds to the next optimization process without performing the optimization process by unrolling.

Other unrolling execution conditions are also determined. These conditions include, for example, that the number of rotations of the loop is 2 or more (if it is explicitly known), that the loop has one exit, that there is no change in the vector length within the loop, etc. It also determines the conditions as to whether or not unrolling improves execution efficiency. If each of these conditions is not satisfied, proceed to the next optimization process.

For loop unrolling, the rotation speed of the outer loop is set to 1/N. Note that to simplify the explanation, the case where N=2 will be explained below.

Double the vector operation sequence. That is, a vector operation sequence is generated and added by incrementing the value of the subscript expression of the array to the original vector operation sequence.

Determine whether the loop rotation speed is constant. If it is not a constant, control is transferred to processing.

Determine whether the original loop rotation number is even or odd. If the number is even, proceed to the next optimization process; if the number is odd, execute the process.

The part of the vector operation sequence that is executed last in the original loop is added to the outside of the new loop, and the process proceeds to the next optimization process.

If the loop rotation speed is a variable, a text that dynamically determines the rotation speed is generated and added.

Corresponding to the determination of the number of rotations, a vector operation sequence corresponding to the fraction of the halved number of rotations is added to the outside of the loop. After that, proceed to the next optimization process.

When unrolling a vector operation sequence in a loop, the unrolling may cause the vector computer to execute the array definitions/references in an unintended order, making it impossible to obtain correct results. Therefore, in the present invention, the following data dependency relationship value is obtained in advance, and based on this, it is determined whether or not unrolling is possible.

The data dependency value can be considered to indicate the relative value relationship between the preceding and following array subscript expressions within the loop. For example, when the array that appears before is A(I) and the array that appears after is A(I+2), the data dependency value is set as I=0 because the control variable I is common. It is calculated as follows.

(0)-(0+2)=-2 Examples of the types of data dependency values are as follows.

(Symbol) (Meaning) φ: No overlap (no data dependence). +: There is a forward data dependency. -: There is a data dependency in the opposite direction. *: Control variable does not appear. ? : Data dependencies are unknown. +OR-: There is a forward data dependency. (scalar and vector) 0: Accessing the same location. + value: Indicates the amount of shift in the forward direction. - value: Indicates how much it is shifted in the opposite direction. Whether or not unrolling is possible is determined by the data dependency value as described above. Therefore, for example, an unrolling possibility table as shown in FIG. 3 is used.

In the unrolling possibility table shown in FIG. 3, ◯ indicates that unrolling is possible, × indicates that unrolling is impossible, and △ indicates whether unrolling is possible or not. The vertical columns represent first-dimensional data dependency relationship values, and the horizontal columns represent second-dimensional data dependency relationship values.

DO 10 J=1,N DO 10 I=1,M A(I,J)=…… 10 CONTINUE In this case, I is the first dimension and J is the second dimension.
It is the dimension.

In FIG. 3, in cases corresponding to the x marks, unrolling is considered impossible because unrolling will result in a data dependency relationship that did not exist before. If it falls under the △ mark, whether or not it is possible is determined based on the data dependency relationship value shown in FIG. 4 and the number of unrolling expansions. For example, if the data dependency value is ±2, unrolling is possible when there is double expansion (i.e., N=2), but unrolling is impossible when triple expansion or more (N≧3) occurs. .

Next, a concrete example of loop unrolling will be shown using an example FORTRAN program.

(a) When the number of rotations of the loop is explicitly known and the number of rotations is an even number [before loop unrolling] DO 10 J=1,4 A(*, J)=B(*, J)+C(*,J) 10 CONTINUE [After loop unrolling] DO 10 J=1,4,2 A(*,J)=B(*,J)+C(*,J) A(*,J+1) =B(*,J+1)+C(*,
J+1) 10 CONTINUE (b) When the number of rotations is odd [before loop unrolling] DO 10 J=1,5 A(*,J)=B(*,J)+C(*,J) 10 CONTINUE [Loop After unrolling] DO 10 J=1,3,2 A(*,J)=B(*,J)+C(*,J) A(*,J+1)=B(*,J+1)+C(*,
J+1) 10 CONTINUE A(*,5)=B(*,5)+C(*,5) Finally, a vector operation sequence of J=5 is added.

(c) When the rotation speed is unknown [Before loop unrolling] DO 10 J=1,NA A(*,J)=B(*,J)+C(*,J) 10 CONTINUE [After loop unrolling] IF (N.EQ.1) GOTO 20 DO 10 J=1,N-1,2 A(*,J)=B(*,J)+C(*,J) A(*,J+1)=B(*, J+1)+C(*,
J+1) 10 CONTINUE IF (MOD(N,2).EQ.0) GOTO 30 20 CONTINUE A(*,N)=B(*,N)+C(*,N) 30 CONTINUE In the above example, loop unrolling The number of expansions of is set to 2, but for example, if the number of rotations of the loop is explicitly 3
In this case, multiple expansion is also possible, such as triple expansion. The user may be able to specify the number of unrolling expansions from the outside using a so-called optimization control line. In this case, the user writes, for example, the following optimization control line in the source program.

"*VOCL LOOP, UNROL (4)" Here, *VOCL indicates that this line is an optimization control line. LOOP indicates that optimization is effective for loops. UNROL (4)
indicates that it should be expanded into four layers. In the case of quadruple expansion, for example, it is as follows.

[Before loop unrolling] *VOCL LOOP, UNROL (4) DO 10 J=1,NA A(*,J)=B(*,J)+C(*,J) 10 CONTINUE [After loop unrolling] IF( N.LT.4) GOTO 20 DO 10 J=1,N-1,4 A(*,J)=B(*,J)+C(*,J) A(*,J+1)=B(*,J+1 )+C(*,
J+1) A(*, J+2)=B(*, J+2)+C(*,
J+2) A(*, J+3)=B(*, J+3)+C(*,
J + 3) 10 CONTINUE 20 M = MOD (N, 4) IF (M.EQ.0) GOTO 50 IF (M.EQ.1) GOTO 40 IF (M.EQ.2) GOTO 30 A (*, N-2 )=B(*,N-2)+C
(*, N-2) 30 A (*, N-1) = B (*, N-1) + C (*,
N-1) 40 A(*,N)=B(*,N)+C(*,N) 50 CONTINUE In this example, unrolling is performed in quadruple expansion using the optimization control line specified by the user, and , since the control variable is N and the loop rotation speed is unknown at the time of compilation, a rotation speed determination text is generated and added after the loop.

〔Effect of the invention〕

As explained above, according to the present invention, by understanding data dependencies, loop unrolling of vector operation sequences is automatically performed, thereby optimizing pipeline scheduling. becomes possible. It also allows optimization of vector text. Therefore, execution performance is improved and the user's tuning time can be shortened. Further, the descriptive nature of the FORTRAN program and the like can be maintained for the source program, and compatibility with general-purpose computers at the source level can be maintained.

[Brief explanation of the drawing]

Fig. 1 is a block diagram of an example of the basic configuration of the present invention;
FIG. 3 shows an example of an unrolling possibility table, and FIG. 4 shows a diagram illustrating the relationship between data dependency values and the number of unrolling expansions. In the figure, 10 is a source program, 11 is a processing device, 12 is a compiler, 13 is a program input section, 14 is a vectorization processing section, 15 is a data dependency analysis section, 16 is an unrolling execution condition determination section, and 17 is an unrolling execution condition determination section. 18 is a rolling processing section, 18 is an object generation section, and 19 is an object program.

Claims (1)

[Claims] 1. In a data processing system having a compile processing function that performs automatic vectorization, a program input unit 13 inputs a source program 10 to be compiled, and analyzes the program to be compiled input by the program input unit 13. a vectorization processing unit 14 that decodes the resulting intermediate text, detects vectorizable text, and generates a vector operation sequence; and an inner loop of a multiple loop in a program to be compiled is a data dependency relationship analysis unit 15 that analyzes data dependencies related to unrolling in the outer loop of the vectorized vector operation sequence when the vectorization is vectorized by the data dependency relationship analysis unit 15; An unrolling execution condition determination unit 16 that determines whether or not unrolling is possible according to the analysis result; and the unrolling execution condition determination unit 16,
and an unrolling processing unit 17 that sets the number of rotations of the outer loop to 1/N (N is an integer of 2 or more) and expands the vector operation sequence N times when it is determined that unrolling is possible. Features a vector operation sequence loop unrolling processing method.