JPS6186844A - Shift system for sequential instruction - Google Patents

Abstract

PURPOSE:To extend a parallel executable part of an object program by comparing the arrangement of sequential items with that of intermediate texts and shifting the POST and WAIT instructions independently of each other. CONSTITUTION:The arrangement of sequential items is added to a WAIT instruction (VWT) to know the relation of dependence with a block B. Then the VWT can be shifted to a spot 2 from a spot 1 as long as no relation of dependence exists with the block B (range of alpha). Thus a part of beta is newly defined as a parallel executable part. For the shifts of both POST and WAIT instruction within a block, the POST instruction (VPT) set as shown in (a) is shifted in the direction opposite to the flow of control. While the VWT is shifted in the direction (IS) equal to the flow of control as shown in (b), and a part 1 is newly defined as a parallel executable part.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention provides a method for moving serialization instructions (POST instructions and WAIT instructions) in a compiler that generates object programs containing scalar instructions and vector instructions. This invention relates to a method for moving serialized instructions that can expand the number of instructions that can be executed in parallel.

[Prior art and problems]

FIG. 8 is a diagram showing an outline of the compiler. Note that this compiler is a VP compiler that generates an object program to be executed on a system including a vector computer. In FIG. 8, ■ indicates a source analysis section, 2 indicates a structure analysis section, 3 indicates a data allocation section, 4 indicates an optimization section, and 5 indicates a code generation section. The source analysis unit 1
It detects inconsistencies between arrays and variables defined in declaration statements and their handling in the procedure division of a source program, and checks whether undefined arrays or variables are defined or referenced. The structure analysis unit 2 converts sources and programs into blocks. The data allocation section 3 allocates memory areas for data and provides initial values to arrays and variables. The optimization unit 4
o Optimization after small loop vectorization and vectorization, register allocation, etc. The code generator 5 converts intermediate text into machine language instructions.

In a hector computer, increasing the speed of the arithmetic unit and improving the ability to supply data commensurate with the arithmetic unit are important keys to improving execution efficiency. For this reason, recent hector calculators use
Two load/store pipelines that can operate in parallel are provided to increase data supply capacity. However, with multiple load/store pipelines operating in parallel, it has become necessary to synchronize memory access instructions. As a method of synchronizing memory access instructions,
A method using POST/WAIT instructions is known.

By using this method, the memory access instructions before the PO8T instruction and the memory access instructions after the WAIT instruction can be synchronized. For example, Do 20 i=1. IOQ ＾(i)-A(i)+B(i) C(i)=A (i-1) 20 The source program called C0NTINLIE is: VL VO,A(1:100) VL Vl,B(1:100 ) VADD V3. VO, VI VST V3. A (1:100) VL V4. A (0:99) VST V4. C(1:100), but if the 4th vector instruction and the 5th vector instruction are executed at the same time, the correct operation result will not be obtained, so the 4th vector instruction and the 5th vector instruction POST instruction and W between the fifth vector instruction
It is necessary to place an AIT instruction.

By the way, in the conventional ■P compiler, the source
If a program has a complex block structure, optimization to move serialized instructions is not performed, so parts that can be executed in parallel are also serialized, which causes a decrease in execution efficiency. There is.

[Purpose of the invention]

The present invention is based on the above considerations, and is based on the following: ■The P compiler recognizes connections between blocks, moves POST instructions and WAIT instructions for serialization independently, and parallelizes object programs. The purpose of this invention is to provide a method for moving serialized instructions that allows the executable part to be expanded.

[Means to achieve the purpose]

Therefore, the serialization instruction movement method of the present invention is useful for a compiler that generates an object program to be executed on a vector computer.
Add a sequence of serialization items to the T command, compare the sequence of serialization items with the sequence of intermediate text, move the POST command in the opposite direction to the flow of control, and move the WAIT command to the flow of control. It is characterized by moving in the same direction.

[Embodiments of the invention]

Hereinafter, the present invention will be explained with reference to the drawings.

FIG. 1 is a diagram showing an overview of the present invention. VWT is WAI
Indicates the T command. The present invention enables POST to list serialized items.
By adding /WAIT command, POST/WA
This is to check the movement of IT instructions. In the case of FIG. 1, the dependency relationship with block B can be known by adding the sequence of serialized items to the VWT. In Figure 1, the sequence of serialization items indicated by VWT and block B (α
range), if there is no dependency, WAI from point ■ to ■
The T instruction VWT can be moved, and the part β becomes a new part that can be executed in parallel. The sequence of serialization items indicates what must be serialized, for example, A, B, C.
If there is an array or variable, A needs to be serialized and B and C do not need to be serialized, then the sequence of serialized items is expressed as BC, such as the bit string associated with the item. can do. Furthermore, definitions and references of data that appear within a block can also be expressed as bit strings associated with the data, and by comparing these, it is possible to know whether there is a data dependency relationship.

Figure 2 shows the POST command and WAI within one block.
It is a figure which shows each movement of T command.

VPT indicates POST command. If the VPT arranged as shown in Fig. 2 (a) is moved in the opposite direction to the control flow (in the IP force direction) and the VWT is moved in the same direction as the control flow (in the Is force direction), Fig. 2 (b) The part marked ■ becomes a new part that can be executed in parallel. For example, VL VO, A (1:100) VL Vl, B (1:100) VADD V2.Vl, VO VST V2.A (1 :100) VST Vl, C (1; 100) VPT V cut T LGφ, A (50) If there is a block, array A is a serialization item, but VPT is used as the fourth and fifth instruction. You can move between vector registers ■2.
A vector store instruction that sets the i-th element data of vector register ■1 to the i-th element of array A, and
The vector store instruction for the second element can be executed in parallel. Note that x indicates a vector register, and GX indicates a general-purpose register.

FIG. 3 is a diagram illustrating movement of a WAIT command when a block moves in two directions. In the illustrated example, the VWT in block A can move in two directions: pro-7ri B and block C. As a result, the parts ``■'' and ``■'' become parts that can be executed in parallel.

FIG. 4 is a diagram illustrating the movement of a WAIT instruction when branching from two programs (two directions). As shown, even if there is control flow from block A and block B to block C, the VWT becomes one in block C and further movement is possible. As a result, the parts ``■'' and ``■'' become parts that can be executed in parallel.

Figure 5 shows PO when looping within one block.
FIG. 3 is a diagram illustrating movement of an ST command and a WAIT command.

FIG. 5(A) shows the arrangement of the conventional VPT and VWT, and FIG. 5(B) shows the movement of the VPT and VWT according to the present invention.

As shown in FIG. 5(b), the VPT above block B is moved to block A, and the VWT below block B is moved to block C. As a result, the parts ``■'' and ``■'' become parts that can be executed in parallel.

FIG. 6 is a diagram illustrating a processing procedure for moving serialized instructions (POST and WAIT instructions).

SL, collect the following information in the unprocessed block.

a. Understand the dependencies of connections between blocks.

b. Collect information on the text within the block.

S2. Movement of serialized instructions Serialized instructions (POST and WAIT instructions) are moved, with the POST instruction moving in the IP force direction and the WAIT instruction moving in the Is force direction.

S3: Possibility of serialization instruction movement? Collect blocks to be moved and compare them with bit strings indicating definition/reference information of vectorized data.

S4. For text that has a movement memory operand in units of text, it is checked whether the operand overlaps with the vectorized range to know whether movement is possible.

Note that these processes are performed by the optimization section of the compiler shown in FIG.

FIG. 7 is a diagram illustrating how to obtain serialized items. The serialization item is the sum (OR) of bit strings that expresses the definition/reference of all data in the range from one serialization instruction to other serialization instructions that exist in the direction of movement of that serialization instruction.
It is found by taking .

In Figure 7, the serialization item in range A is
Add to VPT of T and ■. The serialization items in the range B are added to the VWT (■) and the VPT (■).

〔Effect of the invention〕

As is clear from the above description, according to the present invention, a wider range of instructions can be executed in parallel than ever before, and execution efficiency can be improved.

[Brief explanation of drawings]

Fig. 1 is a diagram showing an overview of the present invention, Fig. 2 is a diagram showing the movement of the POST instruction and WAIT instruction within one block, and Fig. 3 is a diagram showing the movement of the WAIT instruction when the block moves in two directions. Figure 4 is a diagram explaining WA I T when branching from two blocks (two directions).
A diagram explaining the movement of instructions. Figure 5 is a diagram explaining the movement of POST and WAIT instructions when looping within one block. Figure 6 is a diagram explaining the movement of serialized instructions (POST and WAIT instructions). FIG. 7 is a diagram illustrating a procedure for determining serialization items, and FIG. 8 is a diagram illustrating an overview of a compiler. 1... Source analysis section, 2... Structural analysis section, 3...
Data allocation section, 4... Optimization section, 5... Code generation section. Tsubo 1 Figure 2 Ban 41 Kaimo 5 Figure

Claims (1)

[Claims] In a compiler that generates an object program to be executed on a vector computer, the POST instruction and W
Add a sequence of serialization items to the AIT command, compare the sequence of serialization items with the intermediate text sequence, and create the above POS
Move the T instruction in the opposite direction of the control flow and perform the above WAIT
A serialized instruction movement method characterized by moving instructions in the same direction as the flow of control.