JP2677482B2 - Computer language processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a computer language processing method for optimizing a program running on a computer having a hierarchical memory when translating it into an object program.

Recent hardware generally has a hierarchical memory structure in which a faster memory (hereinafter referred to as cache memory) is mounted in addition to the main memory. Data that is frequently accessed is stored in the cache memory and is accessed at high speed. Generally, the difference between the cache memory and the access to the main memory is said to be several to several tens machine cycles, and the memory access cost of the main memory is overwhelmingly higher.

Therefore, when compiling a program written in a high-level language, if the cache memory is optimized so as to be used as effectively as possible, the execution performance of the program is improved. Appropriate technical means for that purpose are required.

[0004]

2. Description of the Related Art In a conventional optimizing compiler, a source program written by a user is processed by reducing the number of instructions / rearranging instructions to reduce memory access / reduce pipeline delay. Has been improved.

However, in most cases, the method of holding data such as array data, which requires frequent memory access, in the cache memory is left to the management method of the cache memory of hardware. In the cache memory control method realized by hardware, even if the cache memory mishit can be recognized in the source program, the data allocation / update to the cache memory is uniquely processed. Therefore, it is an important problem from the viewpoint of improving the performance to arrange the data on the cache memory according to the characteristics of the user program by the software.

As a means for solving the above problems by software, there is an optimization technique called blocking. The purpose of blocking optimization is to divide the array used in the innermost loop into a cache size for a loop structure composed of multiple loops so that the array data is always retained in the cache memory. To transform the loop like this.

FIG. 10A shows an example of a loop to which blocking optimization can be applied. In this loop, the array b
(K, j) accesses the same array element every time the index i is updated. Therefore, as the locus of memory access to the array b in the innermost loop, the same locus is repeated as shown in (b) of FIG.

If the size of the array b of the innermost loop exceeds the cache size, mishits will occur on the cache memory at regular intervals. In order to effectively use the cache memory, it is necessary to divide the array b into a size that can be stored in the cache size and generate a loop instructing the division outside the outermost loop.

In the current optimization by blocking, there are the following problems. (1) In a normal user program, it is very rare that blocking optimization can be performed without performing loop transformation. Therefore, in order to apply this optimization function to a wider range, it is necessary to combine it with optimization of various loop transformations such as index exchange / loop division.
Depending on this order of application, there may or may not be a loop to which blocking can be applied. However, in the conventional technology, since the processing considering these is not performed, the optimization cannot be applied to a wide range.

(2) When blockingable data is detected, the determination of which index the array is divided into has a great influence on the performance improvement. The index at which the array data is divided depends on the size of the array data, the number of target candidates, and the loop execution order relationship. However, in conventional processing systems, a heuristic method is used, so it is appropriate. Sometimes the division was not done.

(3) It is necessary to determine the optimum division value (or block length) from the cache size mounted on the hardware and the array data to be blocked. However, there is a case where an optimal division value cannot be obtained because the optimal division value determination method has not been established, including the case where a plurality of array data are divided.

[0012]

DISCLOSURE OF THE INVENTION The present invention solves the above problems, extensively optimizes a program to be translated for high-speed access to data in multiple loops, and appropriately divides it. The purpose is to improve the execution performance of the program by enabling.

[0013]

FIG. 1 is a diagram for explaining the principle of the present invention. In FIG. 1, 10 is a source program to be compiled, and 11 is a CP on which the compiler operates.
A processing device including U and a memory, 12 is a syntax / semantic analysis unit that inputs the source program 10 and performs syntax analysis and semantic analysis, and 13 is an optimization of an intermediate text according to a processing result of the syntax / semantic analysis unit 12. An optimization processing unit, 14 performs instruction scheduling and register allocation, and generates and outputs an object code. An object generation and output unit, 15 represents an object program as a compilation result.

In the present invention, when compiling a source program 10 targeting a computer having a hierarchical memory of a main memory and a cache memory, the optimization processing unit 1
In 3, the following processing is performed.

Detecting a loop having a tight structure,
Recognize blocking loops. A tight structure means that there are no loop regression variables other than loop control variables.
There is no jump out of the loop and there are no procedure calls.

If the detected loop does not have a tight structure, processing is performed. By using the overlap analysis of data, the range of the loop where the index exchange is possible is identified, and the outer loop and the innermost loop are exchanged so that the access distance of the array data in the innermost loop is shortened, and the index exchange is performed. carry out.

Based on the relationship between the loop depth and the index and the relationship between the index that accesses the innermost loop array and the loop, a blocking candidate array is extracted, and the division target array and the division target index are selected from the candidate arrays. decide.

The block length for division is determined based on the size of the cache memory and the number of loop rotations so that the array after division fits within the size of the cache memory. Based on the array data to be divided, the index to be divided, and the block length of division, a loop indicating the number of divisions is generated outside the original loop, and the loop is transformed.

If the detected loop is not a tight structure, it is reconstructed into a tight loop structure by loop division. If the reconstruction to the tight loop structure is successful,
Process Perform the following. If it fails, give up the optimization of the loop and detect the next loop.

By modifying the loop due to the processing, mishits in the cache memory can be reduced and the execution performance can be improved.

[0021]

The present invention, by adopting the following method,
The problem of blocking by the prior art is improved.

(1) When recognizing a blockable array, optimization of loop transformation such as loop division and index exchange is used to widen the applicable range of blocking. (2) Determine the optimal division value (or block length).

When dividing the array data which can be blocked, the division value is determined so that it can be divided by the number of rotations of the loop and can be sufficiently accommodated in the cache memory. In addition, even when there are a plurality of block data that can be blocked, the optimum division value is determined so that the plurality of array data can fit within the cache size.

This makes it possible to generate an efficient object program with less access to the main memory.

[0025]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The processing of the embodiment of the part related to the present invention in the optimization processing section 13 shown in FIG. 1 will be described in detail below.

1) Recognizing a loop that can be blocked The condition that the execution result does not change due to blocking is that (1) there is no loop regression variable other than the loop control variable, and (2) outside the loop. No jumping out, (3)
It has a tight loop structure that satisfies the three requirements that there are no procedure calls. In addition to this condition, in order to be able to perform blocking optimization processing, in multiple loops, the operation of the array of the innermost loop does not depend on the index of the outermost loop, and the index of the outermost loop is Even if it changes, in the innermost loop, it is necessary that the law of data access does not always change.

As described above, the target loop for blocking is executed only for a tight loop. Therefore, when the target multiple loop is not a tight loop, reconfiguration to a tight loop structure is executed. By this processing, the applicable range of the loop capable of blocking can be expanded.

FIG. 2 shows an example of loop reconstruction by the loop division. Loop division is a process of dividing one loop into a plurality of loops each having the same loop control variable, as shown in FIG. In the present invention, a tight loop can be optimized by dividing a non-tight multiple loop into a plurality of tight loops. A tight multiple loop is a multiple loop in which loops are nested in series and an executable statement appears only in the innermost loop.

The loop division is performed by the following procedure. (1) Tight loop detection Loops are detected from the innermost loop to the outermost loop, and a loop in which an executable statement exists only in the innermost loop is recognized as a tight loop. Other loops cannot be detected as tight loops, so it is necessary to divide the non-tight multiple loops into multiple tight loops.

(2) Retrieval of non-tight multiple loops and retrieval of division target loops Retrieval is performed from the innermost loop to the outer loop, and a loop satisfying any of the following conditions is set as an object of loop division.

-Execution statements (excluding instructions for loop control) exist between the innermost loop and the outer loop. -There are tight sibling loops of the same depth.

There is no jump out of the loop. (3) Loop division For example, in the multiple loop shown in (a) of Fig. 2 (b), the executable statement A exists between the innermost loop and the outer loop. If you search from the loop of
Since it is known that there exists, is the target of loop division. Due to this loop division, the loop is
(b).

The multiple loop shown in (a) of FIG. 2C is an example in which there are tight sibling loops having the same depth. Search from the loop. , Loops are not subject to splitting. After searching for both, and comparing with, you can see that they are tight sibling loops of the same depth.
Loop division is performed as shown in (b) of FIG.

2) Loop replacement processing 2.1) Judgment of index exchangeable loop For example, when the control variable of the innermost loop refers to a dimension other than the first dimension in a multiple loop where the multidimensional array is tight, The process of swapping loops so that the outer loop that refers to the original array element becomes the innermost loop is called loop index exchange. By executing the index exchange, the continuous area on the memory is accessed, and the memory access efficiency is improved.

For example, in the loop shown in FIG.
Each element of the array A is accessed in the order of (b) ,. Therefore, the access is to the discontinuous area. The same applies to array B. The data access interval is called the array data access distance.

When the innermost loop and the outer loop are exchanged by the index exchange as shown in FIG. 3C, the access order is as shown in (D), ... Loop sequences A (I, J), B (I,
J) is a continuous area access.

The purpose of the index exchange is to minimize the access distance of array data in this way. Whether index exchange is possible depends on the dependency of array elements in the loop. Therefore, the range of loops in which the index can be exchanged is identified by "data overlap analysis", and the index is exchanged.

The data overlap analysis is the following processing. In general, optimizations that greatly transform the structure of a loop, such as index exchange of multiple loops and loop division,
You need to be aware of the array element dependencies in the loop. At this time, if the behavior of the array elements in the loop is simplified from the relationship between the subscript and the control variable, the data overlap (dependency) relationship can be examined and the optimization processing described above can be performed. Determine whether The data overlap analysis is a process performed in such a case, and specifically, a process of analyzing the following information.

(1) Order relation of definition / reference in the index space of array elements. In this information analysis, in addition to the definition / reference information of each array element, information about whether different array elements that perform operations in the innermost loop access the same area with each other is also collected.

(2) Preceding order relation in the operation of simple variables. The above-described data overlap analysis process may be similar to the data dependency analysis adopted by the vectorizing compiler, and is well known, so the description here will be limited to this.

If the loop is such that the index cannot be exchanged, it is judged whether or not blocking is possible with the current arrangement of indexes. By extending this method in the following order, it is possible to perform index exchange after the sequence for blocking is determined.

(1) The index exchange part is replaced with an exchangeable index space. (2) Obtain a candidate set of “blocking sequence data”.

(3) The index is exchanged in the "exchangeable index space". By performing steps (1) to (3) repeatedly, more detailed blocking processing can be realized.

3) Detection of Blockable Sequence Data 3.1) Analysis of Sequence Data Reuse A blockable sequence is determined by the relationship between the loop depth and the index, and the index that accesses the array of the innermost loop and the loop. decide.

This analysis method does not collect any information such as whether the definition and reference data accessed in the main memory in the innermost loop overlap, as in "data overlap analysis".
For the analysis of the data dependency required for blocking, it suffices to check whether or not there is an access to the array in the same order when the value of X changes in the innermost loop with respect to the index X being analyzed. .

For a detailed description of the analysis processing of this sequence data reuse, [supplementary explanation 1] is given after the explanation of the present embodiment.
It is described as. 3.2) Determining the array to be divided and the index to be divided Figure 4 shows the process of deciding which array to perform blocking and which index to perform.

(A) In determining the index to be divided, first, a candidate sequence that can be blocked and a candidate index are extracted. (b) Next, the size of the cache memory is compared with the size of the blocking target data.

(C) The access distance of array data is calculated. (d) From the above results, the partition index is determined by considering the dimensionality of the array. The above processes (a) to (d) are repeated. The points to be noted at this time are as follows.

(1) If the number of rotations of the loop is not fixed at the time of translation, reference is made to the array declaration and all elements are considered to be accessed for calculation. (2) When the shape of the sequence data to be blocked is not fixed at the time of translation, for example, “b (i * 8, k * 8)” or “b
In the case of (c (i, k)) ", an accurate division value cannot be obtained during translation. In this case, blocking is not performed.

(3) Considering the number of dimensions, the one-dimensional array, the two-dimensional array, and the N-dimensional (N> = 3) array are considered separately. The consideration of the number of dimensions will be described in detail later in [Supplementary Explanation 2].

4) Determining Block Length In blocking, the factor that greatly affects the performance is "how many blocks to be divided into blocks". The block length of division is called STRIDE, and finding the optimum STRIDE is the key to blocking optimization. A method of determining this STRIDE will be described later as [Supplementary Explanation 3].

The largest factor in determining the block length is the size of the data cache of the hardware. If the data cache is large, a larger amount of data can be retained on the data cache (STRIDE
Can be made large), and conversely, when only a small amount of data can be held on the cache, S
It is necessary to reduce TRIDE. Below, S
The determinants of TRIDE are shown.

(1) When the number of rotations of the loop is fixed at the time of translation: Select STRIDE that allows the array after division to fit within the cache size and is divisible by the number of rotations of the loop. When there are two blocking target loops and the rotation speeds are different from each other, STRIDE is determined according to the rotation speed of the innermost loop. If the rotation number is a prime number, STRIDE is set to the maximum value that the array elements can fit.

(2) When the number of rotations of the loop is not fixed at the time of translation Blocking can be performed even when the number of rotations is not fixed at the time of translation. The point to be noted at this time is "ST
It is always necessary to consider "when the sum of RIDE exceeds the number of revolutions." In this case, STRIDE is determined by the following procedure.

I) When the number of rotations is not fixed at the time of translation, it is considered that all the elements of the array are accessed, and STRIDE that can be stored in the cache size is determined. The method is the same as when the rotation speed is known.

Ii) After STRIDE is determined, a new loop is generated. Since the number of rotations of the loop is unknown, S
Code needs to be generated for the comparison of TRIDE with the speed. At this time, in the hardware having the conditional transfer instruction, the comparison between STRIDE and the rotation speed is replaced with the conditional transfer instruction. By this replacement, the branch overhead can be reduced.

FIG. 5 shows the relationship between the sum of STRIDE and the rotation speed (N) of the loop. As is clear from this figure, if the number of rotations of the loop is unknown, an instruction for comparison and judgment is required.

FIG. 6 shows an example of an instruction for determining a loop end condition therefor. For example, "do i
= ii, min (ii + istride-1, n) ”, if the loop rotation speed (variable n) is not fixed during translation, STRID
The smaller one of the total value of E (variable isride) and the number of revolutions (n) is selected, and the smaller one is used as the end condition of the loop. 5) Loop transformation After the array data to be divided, the index to be divided, and the block length (STRIDE) are determined, a loop indicating the division number is generated outside the original loop. When blocking is performed, the loop becomes deeper than the original loop, but the overhead of the newly created loop can be ignored considering that the data that was the target of blocking in the innermost loop does not hit the cache. . [Supplemental Explanation 1] Reuse Analysis of Sequence Data In the reuse analysis of sequence data, data of “in which index space the sequence data used in the innermost loop is used” is collected. Index this data
Index dependence vector
Call.

For example, explaining with the example shown in FIG. 7A, the Index dependence vector is as follows.
The indices j, k, i of the array data of the innermost loop,
The relationship with the loop depth is as shown in FIG. The loop depth corresponding to each index is In
It is a sequence of dex vectors. In this case Index vect
or is in the order of {j, k, i}. Here, the index dependence vector is defined by defining “1” as the index-related one and “0” as the index-independent one.

As a result, the Index dependence vector is
As shown in FIG. 7C, c (i, j) = {1,0,1}: a (i, k) = {0,1,1}: b (k,
j) = {1,1,0}.

Based on this, reuse for the outermost loop
(Reuse) Find possible array data. Index index of each loop is defined, and Index dependence vec
Perform subtraction with tor. The result of subtraction is the result Vector
Is stored in

Result (k1, ..., kn) = Idv (j1, ..., jn)
-Iv (i1, ..., in) (n: depth of loop) Obtain the result of subtraction for each index. Result
(1) = {r1, ..., rn}, data that can be reused with index In (1 <in <n) has the corresponding Index Vector column ('-
1 '). If the value is any other value ('0'), the array to be accessed contains the index to be checked, and cannot be reused for the outermost loop.

Explaining with the example of FIG. 7, first, Index Dependence Vector: c (i, j) = (1,0,1) a
Find (i, k) = (0,1,1) b (k, j) = (1,1,0) and then collect reusable data for Index j. Index Vector of index'j 'is Iv
(j) = (1,0,0).

Index Dependence Vector and Index Vector
Is subtracted. c (i, j): (1,0,1) − (1,0,0) ＝ (0,0,1) a (i, k): (0,1,1) − (1,0,1) 0) ＝ (-1,1,1) ★ Reusable b (k, j): (1,1,0) − (1,0,0) ＝ (0,1,0) At this time, the index ' For j ', the array a (i,
k) means that there is reuse, index'i ',
Blocking is possible for'k '.

As described above, the reusable array data and the target index can be obtained by the simple vector subtraction. [Supplementary explanation 2] Considering the number of dimensions of blocking target data [In the case of one-dimensional array] When the array to be divided is one-dimensional,
There is only one index to be divided. If the index of the reusable array data does not depend on the index of the innermost loop, blocking will not be performed. Split only when it depends on the index of the innermost loop.

[In the case of a two-dimensional array] If each element of the target array data is accessed by the index of the innermost loop and the loop immediately outside thereof, blocking is performed for both indexes. If only the innermost loop is included, split only by the innermost loop index. If both indexes are not included, blocking is not performed.

[In the case of an array of three or more dimensions] Blocking is performed by focusing on the innermost loop. Blocking focusing on the outer loop is not implemented in terms of translation cost.

-When the index exchange is necessary for blocking, blocking is not performed. Only the array accessed by the index of the innermost loop is subject to blocking. [Supplementary explanation 3] Determination of STRIDE (division length) If the rotation number of the loop is fixed at the time of translation, select the STRIDE (division length) that the array after division fits into the cache size and is divisible by the rotation number of the loop. .

(1) Dividing into squares If the cache size is C (Byte), N pieces of array data to be blocked exist, and the size of one element of the array is E (Byte), one array The cache size that can be distributed in the following manner is obtained by the formula STRIDE = SQRT ((C / E) / N). Note that SQRT is a function for obtaining a square root.

Since the rotation speed is fixed at the time of translation, the optimum STRIDE value is close to the division value and divisible by the rotation speed of the loop. If there are two blocking target loops and their rotation speeds are different, the optimal STRID is based on the rotation speed of the innermost loop.
Determine the E value. The determination of the number of rotations of the outer loop generates a determination whether the number of rotations is exceeded.

When the rotation number is a prime number, division is performed by STRIDE obtained by the above formula. STRID
A determination is made as to whether the E value exceeds the rotational speed.

(2) Blocking only the innermost loop Letting X be the optimum STRIDE value of the innermost loop, the rotation speeds of the other N-1 loops are Ic (i) {1≤i≤N-
1}, where B is the size of one element of the target array, the cache size that can be distributed to one array element can be obtained by the formula STRIDE = C / B * (Π Ic (N-1)). This is the maximum STRIDE length that fits in the cache. Hereinafter, the optimum STRIDE length is determined in the same manner as the method of dividing into squares. Next, a specific application example of the present invention will be described with reference to FIGS.

The FORTRAN source program shown in FIG. 8A is to be optimized according to the present invention. Actually, the source program is converted into an intermediate text and optimization is performed, but here, in order to make the explanation easy to understand, the source program format is used.

If the loop of this program is detected and it is found that it has a tight loop structure, after collecting the information of the data dependency, the array elements of the innermost loop are accessed as continuously as possible. Then, exchange the index.

The loop is transformed so that the index I becomes the index of the innermost loop and the index J becomes the index of the outermost loop. As a result, it is transformed as shown in FIG.

Index depe for each array element
Find the ndence vector. From the relationship between the index and the depth of the loop, the Index dependence vector is as shown in (c) of FIG.

For the outermost loop, an array that always draws the same data access locus is obtained. As shown in FIG. 9A, the index vector of J is (1, 0, 0). Based on this, the Index dependence vector of each array
And the J's Index vector. As a result, J
Array element whose index part is "-1", that is, A
It can be seen that (I, K) is data that always draws the same data access locus with respect to the index J.

The process shown in FIG. 9B is performed. That is, the array A (I, K) is compared with the cache size (denoted by C), and when A (I, K) <C, the main optimization is not necessary, so the loop transformation is not executed. A (I, K)>
When C, I and K are divided so that A (I, K) <C.

Here, it is assumed that A (I, K)> C.
The size of the division is calculated by the above-mentioned method, and is set as ISTRIDE and KSTRIDE, respectively. The loop transformation is performed according to the division lengths ISTRIDE and KSTRIDE. That is, the loop that indicates the number of divisions "DO KK = 1, R, KSTRIDE", "DO II = 1, N, ISTRIDE
Is generated outside the original loop. Also, since the rotation speeds of K and J are unknown, the rotation speed R of K and the total number of divisions, and the rotation speed N of I and the total number of divisions are compared. Generates an instruction that determines the loop end condition by.
It is transformed as shown in FIG. If an object program is generated in accordance with the optimization result shown in FIG. 9C, an object program with good performance with few cache memory miss hits can be obtained.

[0080]

As described above, according to the present invention,
By implementing loop transformation such as loop division and index exchange before blocking, it is possible to broaden the range of application of blocking. In addition, due to the blocking effect, it is possible to reduce the miss hit to the cache memory in the innermost loop, which has the highest execution cost, and to reduce the overhead of main memory reference access.

[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 loop reconstruction by loop division according to an embodiment of the present invention.

FIG. 3 is an explanatory diagram of index exchange according to the embodiment of the present invention.

FIG. 4 is an explanatory diagram of a division target index determination process according to the embodiment of the present invention.

FIG. 5 is an explanatory diagram for comparing and determining the total STRIDE and the rotation speed according to the embodiment of the present invention.

FIG. 6 is an explanatory diagram of determination of a loop end condition according to the embodiment of the present invention.

FIG. 7 is a diagram illustrating the relationship between loop depth / index / array access according to an embodiment of the present invention.

FIG. 8 is an explanatory diagram of an application example of the present invention.

FIG. 9 is an explanatory diagram of an application example of the present invention.

FIG. 10 is an explanatory diagram of a locus of memory access of the innermost loop related to the present invention.

[Explanation of symbols]

 10 Source Program 11 Processing Device 12 Syntax / Semantic Analysis Unit 13 Optimization Processing Unit 14 Object Generation Output Unit 15 Object Program

 ─────────────────────────────────────────────────── ─── Continuation of the front page (56) Bibliography "Proceedings of the 44th National Conference of the Information Processing Society of Japan" 5-93 to 5-94 (1992-2), "PROCEEDING OF 16T H ANNNUAL INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITEC TURE" (1989) P. 242-251

Claims (2)

(57) [Claims] 1. A source program including a multiple loop (10)
In a computer language processing method for converting a program into an object program (15) that runs on a computer with hierarchical memory, a process (,) that detects loops with a tight structure and recognizes blocking loops, By using the overlap analysis of data, the range of the loop where the index exchange is possible is identified, and the outer loop and the innermost loop are exchanged so that the access distance of the array data in the innermost loop is shortened, and the index exchange is performed. Blockable candidate sequences are extracted based on the relationship between the processing step () to be performed, the loop depth and the index, and the index to access the innermost loop array and the loop. And the process of determining the partition target index (), and the array after partition is the size of the cache memory Based on the process () to determine the block length of the partition based on the size of the cache memory and the number of rotations of the loop, and the array data to be partitioned, the index to be partitioned, and the block length of the partition so that A computer language processing method characterized in that a loop for instructing the number of divisions is generated outside the original loop, and a processing step () for deforming the loop is performed, and optimization processing of the generated object program is performed. 2. The computer language processing method according to claim 1, further comprising a processing step () for reconstructing a tight loop structure by loop division when the blocking target loop is not a tight loop structure. Computer language processing method.