JPH0233188B2 - - Google Patents

Description

Detailed Description of the Invention [Technical Field of the Invention] The present invention relates to a vector load instruction for loading an area-invariant vector into a part of a program that constitutes a nested loop, particularly an inner loop, and an area-invariant vector operation. The present invention relates to an area-invariant vector allocation method for optimizing a portion constituting a nested loop having vector operation instructions for storing area-invariant vectors and vector store instructions for storing area-invariant vectors.

[Prior art and problems]

Figure 1 shows an overview of a computer system that executes vector instructions, where MSU is the main memory, MCU is the memory control unit, and VP is the vector instruction.
Processor, CHP is channel processor, DA
indicate DASD.

The vector processor VP has a memory access pipeline, an addition/subtraction pipeline, a multiplication pipeline, a division pipeline, and a mask pipeline. vector processor
When the VP issues a memory access request, the storage control unit MCU executes this memory access request.

Figure 2 shows the register architecture of the vector processor VP.
or FRng is a general-purpose register, VR0 or VRnv
is a vector register, MR0 to MRnv are mask registers, and VL is a vector length. Vector register VR0 to VRnv
Each of the mask registers MR0 to MRnv stores a mask vector.
The operation vector length is set in the vector length register VL. The range of vector commands that can be operated by setting the vector length once is called the VL control range. VL
The maximum number of vector registers used in a control range is called the busy number, but the number of vector registers and the length (number of elements) of the vector register are different depending on the busy number. For example, the busy number is 1 to 8.
, the total vector register is 8 of length 1024
vector registers. Note that the total vector register has 1024×8 elements, and one element is 8 bytes. If the busy number is between 9 and 16, the total vector register is divided into 16 vector registers of length 512,
If the busy number is 17 to 32, the total vector register is divided into 32 vector registers of length 256; if the busy number is 33 to 64, the total vector register is divided into 64 vector registers of length 128. The vector of
If the busy number is between 65 and 128, the total vector register is divided into 128 vector registers of length 64 and the busy number is between 65 and 128.
If greater than or equal to 129, all vector registers are of length
Divided into 32 256 vector registers.
The busy number indicates how many vector registers are required to perform a certain operation, and is determined by the compiler.

FIG. 3 is a diagram showing an overview of the FORTRAN compiler for VP, and CMP indicates the FORTRAN compiler for VP. This compiler CMP is
Source interpretation section, storage allocation section, vectorization section,
It has an intermediate code optimization section, a register use determination section, and a target program output section. The source interpreter inputs the source program from DASD, interprets the sentences, and develops it into intermediate code.
The storage allocation section allocates addresses within the storage area to various data that appear in the program, and the vectorization section detects the loop structure of the program, stores parts that can be executed in parallel, and changes intermediate code. The intermediate code optimization section performs optimization to effectively utilize the VP hardware at the intermediate code level, and the register usage determination section allocates actual resources (registers) to data appearing in the intermediate code. The purpose program output section outputs machine command words to DASD and performs optimization at the machine language level.

Figure 4 shows a nested loop, which adds arrays B and C to the inner loop, and adds array A to the inner loop.
This is an example of an intermediate text having a vector instruction sequence for performing the following. The vector instruction sequence of the inner loop is to store vector B in vector register vt
1 and vector C into the vector register.
This is to load the vector into vt2, add the vector in vector register vt1 and the vector in vector register vt2, set the addition result in vector register vt3, and store the vector in vector register vt3 to vector A. . After executing this inner loop m times, the value of the control variable J is updated. When the value of the control variable J reaches a predetermined value,
This means that the nested loop has finished processing. When vectors A, B, and C are unrelated to control variable J, they are called domain-invariant vectors.

FIG. 5 explains the process of adding arrays B and C to create array A. Now, array A,
Let the number of elements of B and C be n, the length of the vector register be 512, the quotient when n is divided by 512 be S, and the remainder be x. In this case, the vector length register VL
is set to 512, and the rotation speed m is set to S+1.
becomes. First, extract the vectors from address 0 (start) to x-1 of array B and create the vector
Load it into register vt1, take out the vector from the 0th address to the vt3 and stored at addresses 0 to x-1 of vector array A in vector register vt3. Next, vectors at addresses x to x+511 of array B are loaded into vector register vt1, vectors from address x to x+511 of array C are loaded to vector register vt2, and vector register vt1 and The addition result in vector register vt2 is set in vector register vt3, and the vector in vector register vt3 is stored in addresses x to x+511 of array A. Thereafter, similar processing is performed until the number of repetitions reaches m.

In the nested loop shown in FIG. 4, when the number of rotations of the control variable J is N, the number of loads is N×m×2, and the number of stores is N×m. In order to improve the processing efficiency of the vector processor VP, it is desirable to reduce the number of times the main memory is accessed as much as possible.

[Purpose of the invention]

The present invention is based on the above considerations, and includes:
It is an object of the present invention to provide an area-invariant vector allocation method that converts a program having a nested structure and vector instructions for loading/storing area-invariant vectors into inner loops into an efficient program.

[Structure of the invention]

Therefore, the area-invariant vector allocation method of the present invention configures a nested loop, and the inner loop includes a vector load instruction for loading an area-invariant vector into a vector register, and an area-invariant vector in the vector register. In an area-invariant vector allocation method that optimizes a program that has a vector instruction to operate on a vector instruction and a vector store instruction to store an area-invariant vector in a vector register, all elements of the area-invariant vector to be operated on are Vector number
When dividing by the vector length of the register, the quotient is m and the remainder is x.Then, the back target of the outer loop is an instruction to set the value x in the vector length register, and the domain-invariant vector is made permanent in the loop. Place an instruction to load into the allocatable register gvt, and in the inner loop, an instruction to set the value x in the vector length register, an instruction to perform the above-mentioned operation on the permanently allocatable register gvt,
Instruction to set the number of revolutions to m, instruction to set the vector length of the vector register in the vector length register, vector load instruction to load an area-invariant vector into the vector register, area-invariant vector in the vector register Place a vector operation instruction to operate on and a vector store instruction to store an area-invariant vector in the vector register, and set the forward target of the outer loop to the value x in the vector length register, which can be permanently allocated. This is characterized by arranging a store instruction for storing an area-invariant vector in register gvt.

[Embodiments of the invention]

Hereinafter, the present invention will be explained with reference to the drawings. FIG. 6 is a diagram showing an overview of the present invention. In the present invention, first, a domain-invariant vector is converted into a gvt. gvt means GLOBAL VECTOR
It is an abbreviation for TEMPORARY, and the gvt register means a vector register (hereinafter simply referred to as gvt) that can be permanently allocated in a loop. After converting the domain-invariant vector to GVT, mod the VL control range
Divide into section and loop section. mod is an abbreviation for Modulus, which refers to remainder. After dividing the VL control range into a mod part and a loop part, the region invariant vector of the mod part is moved. Note that the present invention relates to the intermediate code optimization section shown in FIG.

The region-invariant vector GVT conversion is performed in the following procedure.

(1) Select region-invariant vectors that are reference-only within an SCR (Strongly Connected Region) as candidates for GVT conversion (corresponding to load instructions). In addition, SCR
can be thought of as corresponding to DO Lupo.

(2) gvt defined area invariant vector in SCR
(corresponds to a store instruction).

(3) The selected GVT candidates are ordered in descending order of frequency of use.

(4) Determine gvt from gvt candidates.

(5) Allocate gvt and replace vt references corresponding to area-invariant vectors with gvt.

Figure 7 shows a nested structure containing vector addition instructions.
It shows a DO loop and its corresponding intermediate text. Arrays A, B, and C are invariant to J. * in B(*), C(*), and A(*) means all of 1 to n. In Figure 7, B
(*), C(*), and A(*) are domain-invariant vectors.

FIG. 8 explains the allocation of gvt and the replacement of vt with gvt for area-invariant vectors. vt1 to gvt1, vt2 to gvt2, vt3 to gvt
Replaced by 3.

Next, divide the VL control range into a mod part and a loop part. Now, assume that the number of elements in arrays A, B, and C is 1500, and the length of the vector register is 512. The remainder x is x = mod (1500, 512) = 476, and the quotient S is S = (1500/512) = 2. Note that the rotation speed m is equal to S, which is 2. The number of elements in arrays A, B, and C is 1500, and the vector
If the length of the register is 512, the intermediate text converted to gvt in Figure 8 is modified as shown in Figure 9.
It is divided into a loop part and a loop part.

Finally, the movement of the area-invariant vector in the mod section will be explained. As shown in Figure 10, the load instruction of the area-invariant vector in the mod section is moved to the back target of the SCR, then the store instruction of the area-invariant vector in the mod section is moved to the forward target of the SCR, and finally, Replace gvt in the loop section with vt. When the intermediate text in FIG. 9 is subjected to the above processing, intermediate text as shown in FIG. 11 is obtained.

FIG. 12 is a diagram illustrating back targets and forward targets. In the figure, → means control (program flow).
SCR(J) is one or more blocks (set of instruction sequences)
The back target is
Indicates the immediately preceding block that is always executed before entering that SCR(J). What is a forward target?
The first block executed after executing SCR(J) is shown. This block has only a flow from SCR(J) and no flow from other blocks.

〔Effect of the invention〕

As is clear from the above description, according to the present invention, the number of executions of load/store instructions can be reduced compared to the conventional method. The reason why the number of main memory accesses can be reduced by the present invention will be explained using FIG. 9 as an example. If you focus on the mod part,
In FIG. 11, the load of B(*), load of C(*), and store of A(*) in the mod section have been moved to the outside of SCR(J). This means that when executing in SCR(J), the load of B(*), the load of C(*), and the store of A(*) are reduced. For example, if the rotation speed of SCR (J) is 10, load B (*) of the mod section, load C (*), and load A (*)
The number of stores is: When the present invention is adopted: 0 times When the present invention is not adopted: 10 times. In other words, the only instructions in the mod section are B(*) + C(*), and main memory access (loading B(*),
This means that the number of times C(*) is loaded and A(*) is stored) is reduced. If the number of revolutions of SCR (J) is 1, there will be an extra load on A (*), but
It doesn't exist in many normal programs. If the number of accesses to the main memory in the mod section is m and the number of rotations of SCR (J) is n, then the number of accesses to the main memory is reduced by m×n - number of stores + m).

[Brief explanation of drawings]

Fig. 1 is a diagram showing an example of a computer system that executes vector instructions, Fig. 2 is a diagram showing the register architecture of a vector processor, and Fig. 3 is a diagram showing an overview of a FORTRAN compiler for VP.
Figure 4 is a diagram showing an example of intermediate text with a nested loop; Figure 5 is a diagram explaining the process of adding arrays B and C to create array A; Figure 6 is an overview of the present invention. Figure 7 is a diagram showing a nested DO loop including a vector addition instruction and the corresponding intermediate text. Figure 8 is a diagram showing gvt allocation and vt
Figure 9 explains the replacement of gvt with mod
Figure 10 is a diagram illustrating the procedure for moving the domain-invariant vector of the mod part. Figure 11 is a diagram of the intermediate text after the domain-invariant vector of the mod part has been moved. FIG. 12, which is a diagram showing one example, is a diagram illustrating a back target and a forward target. MSU: Main memory unit, MCU: Memory control unit, VP: Vector processor, DA
...DASD, FRO or FRng...General purpose register, VL...Vector length register, VRO or
VRnv...vector register, MRO or
MRnv...Mask register.

Claims (1)

[Claims] 1 Construct a nested loop, and use a vector load instruction for loading an area-invariant vector into a vector register in the inner loop, a vector instruction for operating an area-invariant vector in the vector register, and a vector instruction for operating an area-invariant vector in the vector register. A vector to store domain-invariant vectors of
In the area-invariant vector allocation method for optimizing programs with store instructions, when the total number of elements of the area-invariant vector to be operated on is divided by the vector length of the vector register, the quotient is m and the remainder is x. , in the back target of the outer loop, place an instruction to set the value x in the vector length register, and an instruction to load the domain-invariant vector into the permanently allocatable register gvt in the loop, and in the inner loop, value x in vector length register
, an instruction to perform an operation between the permanently allocatable registers gvt, an instruction to set the rotation speed to m, an instruction to set the vector length of the vector register in the vector length register, Places a vector load instruction to load an area-invariant vector into a vector register, a vector operation instruction to operate on an area-invariant vector in a vector register, and a vector store instruction to store an area-invariant vector in a vector register. and an area-invariant vector characterized in that an instruction for setting a value x in a vector length register and a store instruction for storing an area-invariant vector in a permanently allocatable register gvt are placed in the forward target of the outer loop. allocation method.