JPH0367363A - Vector operational sequence unrolling processing system - Google Patents

Abstract

PURPOSE:To improve the effective efficiency of an object program by dividing an input text for vectorization into a loop which meets specific requirements and other loops by a division condition decision processing part and processing them respectively by an arithmetic column division processing part and a normal unrolling part. CONSTITUTION:The intermediate text for vectorization 8 is divided into two parts of a reference side and a definition side by the division condition decision processing part 10 to decide the vector group wherein the same elements are referenced and defined except specific numbers of elements at the head of the reference side and at the tail of the definition side and other groups. Then the referenced and defined group is processed by the scaler processing and unrolling processing of an operational sequence division processing part 11 and other groups are processed by a normal unrolling processing part 5 to generate an optimized intermediate text. Vectors meeting the requirements are processed by the scaler processing to expand the possibility of unrolling at the time of the generation of the object vector program, thereby improving the effective efficiency of the object program.

Description

[Detailed Description of the Invention] [Summary] Regarding the unrolling process of a compiler that generates a vectorized target program in a computer, a vector operation that expands the possibility of unrolling vector operations and improves the execution efficiency of the target program. Aiming at a column unrolling processing method, it has a division condition determination processing section and an operation column division processing section, and the division condition determination processing section performs necessary vector operations on a loop to be unrolled including vector operations. When a sequence is expanded into two sets of vector operation sequences, one or more vectors that are referenced in one of the vector operation sequences and then defined in the other, the beginning of the reference side and the end of the definition side. Detects a vector in which the same element is referenced and defined except for the specified number of elements of Configure unrolling to remove it from the column and replace it with a scalar operation column.

[Industrial application field]

The present invention relates to a vector operation string unrolling processing method for a compiler that generates a target program vectorized from a source program in a computer.

[Problems to be solved by the prior art and the invention] A so-called vectorization compiler executed on a computer is, for example, an FO
When a computer source program written in the RTRAN programming language is analyzed to generate a target program, the required part of the target program is generated as a vector operation sequence, so-called vectorization, and the purpose can be executed by a vector processor. Make it into a program.

For such parts to be vectorized, optimization is performed to improve execution efficiency by performing a well-known so-called unrolling process, which expands operations to reduce the number of loop iterations for loops containing vector operation sequences. .

FIG. 3 is a block diagram showing an example of the configuration of a computer. A program analysis section 3 of a compiler 1 inputs and analyzes a source program 2, and based on the result, a vectorization processing section 4
vectorizes a predetermined portion to be vectorized, and produces a vectorized intermediate text 8 expressed, for example, in a predetermined intermediate language.

The unrolling processing unit 5 processes this vectorized intermediate text 8 and unrolls the vectorized program to produce an optimized intermediate text 9, and the object generation unit 6 converts the result. Output the target program 7.

Figure 4 is a diagram explaining vectorization and unrolling using a program example. Figure 4(a) is an example of a source program written in FORTRAN language, in which the inner loop of a double DO loop is vectorized. By doing so, (b)
becomes the text. In (b), the main body of the DO loop with J as the control variable represents a vector operation, and A (book,
Indicates a vector consisting of elements within the range of * specified separately by J) etc.

The result of unrolling this text by setting the number of expansions to 2, that is, expanding the number of repetitions using the control variable J by half, is shown in (C).

However, if this example is expanded directly as shown in (C),
Such unrolling is generally not possible because of the problems described below. That is, Fig. 5(a) shows, for example, the vector represented by A (book, 1) in the row J = 1, and the horizontal direction is the range of elements specified by * (the range of ■ in the loop of the source program). range). If expressed like this, the first and second rows represent the first
In the operation of the vector operation instruction statement, vector A (*, J) on the left side and vector 8 (umbrella - 1, J + 1) on the right side
), and the result of adding 8 (*, J) elements to the elements in the row of J=2 in the figure defines the element on the right side of the row of J=1.

Similarly, the third and fourth lines in the figure show the A vectors on the left and right sides in the operation of the second vector operation instruction statement (hereinafter referred to as a statement) at J=1, and the elements in the line J=3 The result of the calculation becomes a relationship that defines the element on the right side of the row J=2 above.

In this case, if all elements of each vector shown in the figure are processed at once, the vector operation according to the first sentence in Figure 4 (C) will be executed in the first row shown in Figure 5 (a). is executed for the vector in the second row, and then the vector operation in the second sentence is applied to the third row shown in Figure 5(a) (actually, the range of elements is only one element apart from the second row). The same vector) and the vector in the fourth row are executed without any problem.

However, due to the limited capacity of the vector register of the vector processor, all the required elements of the vector are
If the vector cannot be loaded into the vector register at once, it is necessary to divide the vector into several ranges and perform vector operations.

For example, as shown by the vertical line near the center of the vector shown in Figure 5(a), if it is necessary to process the vector by dividing it into two parts, the left and right parts, The vector operation of the first sentence is performed for the part, the vector operation of the second sentence is performed for the left part of the third and fourth lines, and then the vector operation of the first sentence is performed for the right part of the first and second lines. Vector operation: The vector operation of the second sentence is performed on the right portions of the third and fourth lines.

As a result, for the elements at the left and right boundaries, which are shown shaded in Figure 5(a), after the definitions are updated with the results of the vector operation in the second sentence on the left, the elements on the right are updated. It will be referenced for the vector operation in the first sentence. Therefore, there is a problem in that the order of references and definitions is reversed from the content described in the source program, and correct results cannot be guaranteed.

In the example of this explanation, the reference and definition elements are shifted by one element, but the same thing will happen even if there is a shift of two or more elements within the range of the number of shifted elements.

The present invention aims to provide a vector operation sequence unrolling processing method that expands the possibility of unrolling vector operations and improves the execution efficiency of a target program so that unrolling is possible even in the above cases. do.

[Means for solving wife problems]

FIG. 1 is a block diagram showing the configuration of the present invention.

The figure shows the vector operation sequence unrolling processing method,
The division condition determination processing unit 10 includes a division condition determination processing unit 10 and a calculation string division processing unit 11, and the division condition determination processing unit 10 performs necessary vector operations on the loop of the vectorized intermediate text 8 that is the target of unrolling processing including vector operations. When a sequence is expanded into two sets of vector operation sequences, one or more vectors that are referenced in one of the vector operation sequences and then defined in the other, the beginning of the reference side and the end of the definition side. The operation sequence division processing unit 11 detects a vector in which the same element is referenced and defined except for the specified number of elements of the vector operation sequence, and the operation sequence division processing unit 11 divides the operation part related to the specified number of elements of the vector operation sequence into the vector operation. The optimized intermediate text 12 is generated by removing it from the column and unrolling it so as to replace it with a scalar operation column.

[For production]

With the above processing method, even if unrolling is not possible conventionally, it becomes possible to unroll vector operations on vectors other than those whose portions are replaced with scalar operations.

〔Example〕

In FIG. 1, a division condition determination processing section 10 receives as input the vectorized intermediate text 8 output from the conventional vectorization processing section 4, and detects a loop that meets a predetermined condition as described below regarding the loop to be unrolled. , the loop is passed to the arithmetic sequence division processing unit 11 to execute unrolling, and the other parts are processed, for example, by the conventional unrolling processing unit 5, to make use of the optimized intermediate text 2, and to perform unrolling. Similarly, it is assumed that the object generation unit 6 converts the object program into the target program.

FIG. 2 is a diagram showing an example of the processing flow of the division condition determination processing unit 10 and the operation sequence division processing unit 11. and process step 21.
22, for the two sets of vector operation sequences, one or more vectors that are referenced in the first vector operation sequence and then defined in the second vector operation sequence, the beginning of the reference side and the end of the definition side. In the part excluding the specified number of elements, vectors in which the same elements are referenced and defined are detected.

In the example shown in FIG. 4(C) above, the specified number is 1,
This corresponds to the case where this condition is met.

This condition requires the vector on the reference side of the vector operation sequence (in this example, the right side of the first sentence, ^(*-1, J+1)), and the vector on the definition side (A(*, J+1) on the second friendship side). )
differ only in the subscript indicating the vector, and the difference is the difference between the range of elements of the vector on the referencing side and the defining side (in the example,
This can be analyzed because -1), which is the difference obtained by subtracting the rate from *-1, is negative, and in that case, the designated number is determined as the absolute value of the difference.

In the above condition judgment, if the condition is not met, normal unrolling processing is performed, but if the condition is met, division processing is performed in processing step 23 to separate the calculation parts related to the specified number of elements. Then, convert this part to a scalar operation and unroll it. That is, in the case of the example in Figure 4(C), it is separated into scalar operations as shown in the first and second sentences shown in (d), and for the vector operation string, the elements are divided to remove the corresponding element from the vector. Change the range.

As a result, if the case of executing the calculation of FIG. 4(d) is shown in the same format as the case of FIG. 5(a) above, it is shown in FIG.
The calculation of the reference relationship between the first and second elements in the first and second rows, which are shaded, and the definition relationship between the last elements in the third and fourth lines are executed as scalar operations. Vector operations will now be performed on other elements.

Therefore, even when a vector is divided into left and right sides and calculations are performed twice, as shown by the vertical line near the center of the figure, there is a difference between the range of the reference element in the second row and the range of the definition element in the third row. Since there is no such thing, no reversal of the order of references and definitions occurs.

Note that even if a scalar operation is added as described above, the scalar operation can be executed by a normal processor in parallel with the vector operation by a vector processor, so it hardly affects the execution time.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, when generating a computer vectorization program,
This has the remarkable effect of expanding the possibility of unrolling vector operations and improving the execution efficiency of the target program.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing the configuration of the present invention, Fig. 2 is a flowchart of the processing of the present invention, Fig. 3 is a block diagram showing a conventional configuration example, Fig. 4 is an explanatory diagram of a program example, Fig. 5 FIG. 2 is a diagram illustrating a calculation execution state. In the figure, 1 is a compiler, 2 is a source program, 3 is a program analysis section, 4 is a vectorization processing section, 5 is an unrolling processing section, 6 is an object generation section, 7 is a target program, 8 is a vectorization intermediate text, 9. 12 is an optimized intermediate text; 10 is a division condition determination processing unit; 11 is an arithmetic string division processing unit; 20 to 23 are processing steps; FIG. 1 is a block diagram showing a conventional configuration example. Figure 3: Flowchart of the process of the present invention Figure 2: Explanation diagram of a program example Figure 4:

Claims (1)

[Claims] A division condition determination processing unit (10) and an arithmetic sequence division processing unit (10)
1), and the division condition determination processing unit (10) is configured to perform the following operations when expanding a required vector operation sequence into two sets of vector operation sequences for the loop to be unrolled (8) including vector operations. , a vector that is referenced on one side of the vector operation sequence and then defined on the other side, in which the same elements are included except for one or more specified number of elements at the beginning of the reference side and the end of the definition side. The vector to be referenced and defined is detected, and the operation string division processing unit (11) removes the operation part related to the specified number of elements of the vector operation string from the vector operation string and replaces it with a scalar operation string. A vector operation sequence unrolling processing method characterized by unrolling as follows.