JPH0812662B2 - Instruction processing order control method - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an instruction processing order control method, and particularly issues an instruction regardless of the instruction execution order designated by a program in a vector computer (a computer that performs vector processing) ( The present invention relates to an instruction processing order control method for performing control of inputting and executing.

[Conventional technology]

Traditionally, a scalar computer (a computer that performs scalar processing)
In order to speed up the instruction processing, the instruction processing order control that dynamically determines the instruction processing order and inputs the instructions to the arithmetic unit and the memory control unit in an order that does not depend on the instruction execution order specified by the program The scheme is used.

Such a conventional instruction processing order control method detects a conflict between a register address (register number) that is an input / output operand of an instruction and a memory address, determines the usage status of an arithmetic unit and a memory control unit, and based on this determination. And a means for deciding the order of inputting instructions to the arithmetic unit and the memory control unit (the order which does not depend on the instruction execution order specified by the program).

This means can be applied not only to the scalar computer but also to the instruction processing order control method in the vector computer, but in the vector computer, a plurality of memory access vector instructions (vector store instruction and vector load instruction, etc.) are specified by the program. Whether the instructions may be input to the memory control unit in an order that does not depend on the executed instruction order (the preceding vector store instruction (this instruction generally takes a long time) is followed by the vector load instruction (this instruction Is generally short in execution time), but it is difficult to determine whether it is possible to overtake.

That is, the store start origin address of the vector store instruction is basel, the distance between vector elements in the main storage device stored by the vector store instruction is dist1, and the vector length (the number of vector elements) stored by the vector store instruction is len1. (Len1 ≧ 1), the load start origin address of the vector load instruction that is specified in the program to be executed after the store instruction is base2, and the vector element on the main storage device loaded by the vector load instruction If the distance is dist2 and the vector length loaded by the vector load instruction is len2 (len2 ≧ 1), it is a set of addresses stored by the vector store instruction {base1, base1 + dist1 × 1, base1 + d
ist1 × 2, ..., Base1 + dist1 × (len1-1)} and the set of addresses loaded by the vector load instruction {base2, base2 + dist2 × 1, base2 + dist2 × 2, ..., bas
The vector load instruction may precede the vector store instruction (pass the vector store instruction) and perform the memory access only when the intersection set with e2 + dist2 × (len2-1)} is an empty set. It is determined that any base1, dist1, len1 (len1 ≧ 1), base2, dist2
And whether or not the vector load instruction can pass the vector store instruction for all vector elements specified by the combination of len2 and len2 (len1 ≧ 2) (detection of memory address conflict, etc.) is short. It was difficult to do in time.

[Problems to be Solved by the Invention]

In the conventional instruction processing order control method described above, an arbitrary ba
Short for the combination of the vector element of the vector store instruction specified by se1, dist1 and len1 (len1 ≥ 1) and the vector element of the vector load instruction specified by bast2, dist2 and len2 (len1 ≥ 1) Since it is difficult to detect whether the vector load instruction can overtake the vector store instruction by detecting the memory address conflict in time, it is possible to use the instruction processing order control method even if the instruction processing order control method is adopted. There is a drawback that it is not possible to achieve high-speed processing (thus, the instruction processing order control method as described above in the scalar computer cannot be adopted in the vector computer).

In view of the above points, an object of the present invention is to speed up instruction processing in a vector computer by, for example, determining the relationship between base1 and dist1 of vector store instructions and base2 and dist2 of vector load instructions. It is to provide an instruction processing order control system.

[Means for solving the problem]

The instruction processing order control method of the present invention is a vector arithmetic unit having a plurality of vector registers and one or more pipelined arithmetic units, and input / output of vector data transmitted / received between a main memory and a vector register. In an instruction processing order control method in a vector computer having a memory control section for controlling the execution, an execution waiting queue for holding an instruction group input to the vector arithmetic unit and the memory control section based on an instruction execution order specified by a program, and an execution State holding unit that holds the states of the vector register, the arithmetic unit, and the memory control unit that are used by the internal instruction, the preceding vector store instruction in the instruction group held in the execution waiting queue, and the vector store instruction. And a vector load instruction in the instruction group that is held in the execution queue that follows Then, the absolute value of the distance between one vector element is an integer multiple of 2 or more of the absolute value of the distance between the other vector elements, and the difference between both memory access start origin addresses is not 0 and the absolute value of the difference is When the absolute value of the distance between both vector elements is smaller than the smaller one and there is no register conflict relationship, the vector load instruction is changed to the vector store instruction at the timing based on the state held in the state holding unit. It has a vector operation unit and an instruction input control unit which inputs the information to the memory control unit in advance.

[Action]

According to the instruction processing order control method of the present invention, the execution waiting queue holds a group of instructions to be input to the vector computing unit and the memory control unit based on the instruction execution order designated by the program, and the state holding unit uses the instruction being executed. The state of the used vector register, arithmetic unit, and memory control unit is held, and the instruction injection control unit executes the subsequent vector store instruction in the instruction group held in the execution queue and the subsequent vector store instruction. Regarding the vector load instruction in the instruction group held in the wait queue, the absolute value of the distance between one vector element is an integer multiple of 2 or more of the absolute value of the distance between the other vector elements, and both memory accesses start. Register when the difference of the origin address is not 0 and the absolute value of the difference is smaller than the smaller absolute value of the distance between both vector elements. The timing or the like based on the state held in the state holding unit when the engagement relationship does not exist in advance the vector load instruction to the vector store instruction is put into vector calculator and memory controller.

〔Example〕

 Next, the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of the instruction processing order control system of the present invention. In the instruction processing order control method of the present embodiment, the program holding unit 1 that stores a program and the instructions in the program in the program holding unit 1 that is input to the vector computing unit 5 and the memory control unit 6 are held and held. Execution queue 2, a state holding unit 3 that holds the states of the vector registers and arithmetic units in the vector arithmetic unit 5 used by the instruction being executed, and the memory control unit 6, the vector arithmetic unit 5 and An instruction input control unit 4 for controlling the order of inputting instructions to the memory control unit 6; a vector arithmetic unit 5 having a plurality of vector registers and one or more pipelined arithmetic units;
A memory controller 6 for controlling access to the main memory (memory) (input / output of vector data transmitted / received between the main memory and the vector register), and data lines 10 to 19
(Data lines 15 and 16 exist in the instruction input control unit 4 (see FIG. 2)).

The execution queue 2 holds two instructions, an instruction (1) and an instruction (2), and holds an instruction preceding in the instruction execution order specified by the program in the program holding unit 1 as the instruction (1). However, the subsequent instruction is held as the instruction (2).

Referring to FIG. 2, the instruction input control unit 4 includes an instruction input determination unit 7, a register conflict check unit 8, and a memory access conflict check unit 9.

Referring to FIG. 3, the memory access conflict check unit 9 determines that the vector access start point address of the instruction (1) (base1. If the instruction (1) is a vector store instruction, it is the store start point, and the instruction (1) If the is a vector load instruction, the register 21 that stores the load start origin) and the vector access start origin address of the instruction (2) (base2. At the store start origin if the instruction (2) is a vector store instruction) Yes, if the instruction (2) is a vector load instruction, the register 22 that stores the load start point) and the vector element distance (dist1) of the instruction (1)
, A register 23 for storing the distance (dist2) between the vector elements of the instruction (2), and a subtraction circuit 25.
A remainder circuit 26, an AND circuit 27, and comparators 28 to 30.

Next, the operation of the instruction processing order control system of this embodiment configured as described above will be described.

First, the first instruction is sent from the program holding unit 1 via the data line 10 to the instruction execution order designated by the program in the program holding unit 1 as the instruction (1) of the execution queue 2, and the instruction of the execution queue 2 is sent. The following command is sent as (2).

The two instructions in these execute queues 2 are data lines 11
And 12 are sent to the instruction input control unit 4, respectively.

The instruction input control unit 4 performs the following processing (see FIG. 2).

First, the two instructions sent via the data lines 11 and 12 include the instruction input determination unit 7 and the register conflict check unit 8.
And the memory access conflict check unit 9, respectively.

In the register conflict check unit 8 in the instruction input control unit 4, there is a register conflict relationship between a preceding instruction (1) and a succeeding instruction (2) in the program (a relationship in which the same vector register is used in competition. ) Exists, it is judged (check), and the check result is the data line.
It is sent to the instruction input determination unit 7 via 15.

The memory access conflict check unit 9 in the instruction input control unit 4 performs the following processing (see FIG. 3).

First, the vector access start origin address (base1) of the instruction (1) sent via the data line 11 is stored in the register 21, and between the vector elements of the instruction (1) sent via the data line 11 The instruction (2) in which the distance (dist1) is stored in the register 23 and sent via the data line 12
Vector access start origin address (base2) is stored in the register 22, and the vector element distance (dist2) of the instruction (2) sent via the data line 12 is registered in the register 24.
Stored in.

The base1 stored in the register 21 and the base2 stored in the register 22 are sent to the subtraction circuit 25.

The subtraction circuit 25 calculates and outputs the difference (distance) between the absolute values of base1 and base2.

The dist1 stored in the register 23 and the dist2 stored in the register 24 are sent to the remainder circuit 26.

In the remainder circuit 26, division is performed between dist1 and dist2 and the remainder and divisor are output (the smaller absolute value of dist1 and dist2 is the divisor. When the divisor is “0” or dist1 and If dist2 matches, the remainder is “AL
L1 (all bits are output as "1") ".

The distance output from the subtraction circuit 25 and "0" are compared with each other.
The data is input to and compared with each other, and the comparator 28 outputs “1” if the two comparison targets do not match, and outputs “0” if the two match.

The distance that is the output of the subtraction circuit 25 and the divisor that is the output of the remainder circuit 26 are input to the comparator 29 and compared. If the distance is smaller than the divisor, "1" is output and the distance is smaller than the divisor. If it is not smaller, "0" is output.

The remainder output from the remainder circuit 26 and "0" are comparators.
The data is input to and compared with each other, and the comparator 30 outputs “1” if the both comparison targets match, and outputs “0” if the both do not match.

The comparison results of the comparators 28 to 30 are input to the AND circuit 27. In the AND circuit 27, the AND of the three inputs (comparison result) is the check result of the memory access conflict relationship (indicates that there is no conflict by "1", and conflicts. Is shown as “0”) and sent to the command input determination unit 7 via the data line 16.

In the instruction input determination unit 7 in the instruction input control unit 4, the check result of the register conflict check unit 8 sent via the data line 15 and the memory access conflict check unit 9 sent via the data line 16 are sent. Check result and the state information of the vector register and the arithmetic unit in the vector arithmetic unit 5 and the memory control unit 6 sent from the state holding unit 3 via the data line 14 (in the state holding unit 3, the data line
The state of the vector register and the arithmetic unit in the vector arithmetic unit 5 acquired via 19 and the state of the memory control unit 6 acquired via the data line 20 are held). And the instruction (command (1) or command (2)) to be input to the memory control unit 6 and the timing of the input (the instruction whose input has been determined is transmitted through the data line 17 at a predetermined timing). It is input to the vector operation unit 5 and input to the memory control unit 6 via the data line 18). In addition, in the instruction input determination unit 7,
Prior to the above-mentioned decision, "instruction (1) is a vector store instruction and instruction (2) is a vector load instruction based on the instruction (1) sent through the data lines 11 and 12 and the instruction code of the instruction. It is checked whether or not the condition "Yes" is satisfied, and if this condition is not satisfied, the instruction (1) is determined to be input without referring to the data lines 14-16.

In the instruction input determination unit 7, a signal indicating which of the instruction (1) and the instruction (2) has been input to the vector operation unit 5 and the memory control unit 6 (a signal used for entry management of the execution waiting queue 2). Is sent to the waiting queue 2 via the data line 13.

Next, a specific operation of the instruction processing order control system of this embodiment will be described. The operation when the program shown in FIG. 4 is held in the program holding unit 1 will be described with reference to FIGS. 1 to 5.

In the program shown in FIG. 4, "VLOAD" indicates the instruction code of the vector load instruction, "VADD" indicates the instruction code of the vector addition instruction, and "VSTORE"
Indicates the instruction code of the vector store instruction.
ULT "indicates the instruction code of the vector multiplication instruction.

The instruction operands “VR0” to “VR3” indicate vector registers, and each vector register VR0 to VR3 has 256
It shall be possible to store 3 vector elements.

Further, the instruction operand "(a, b, c)" indicated by the set of three elements a, b and c indicates the main memory operand of the vector load instruction / vector store instruction. Here, the element a indicates the vector access start origin address, the element b indicates the inter-vector element distance, and the element c indicates the vector length.

For example, the first instruction "VLOAD VR0 ← (base, 5,25
6) ”is an instruction to load a vector element whose memory access start address (load start address) is“ base ”, vector element distance is“ 5 ”and vector length is“ 256 ”into vector register VR0. Is shown.

The waiting queue 2 in the initial state during execution of this program is 1 in this program as an instruction (1).
The second instruction, the vector load instruction “VLOAD VR0 ← (b
ase, 5,256) ”is set, and the vector load instruction“ VLOAD VR1 ← (base +
1,5,256) ”is set (see FIG. 5 (a)).

In this state, the register conflict check unit 8 in the instruction input control unit 4 uses the vector register VR0 used for the first instruction which is the instruction (1) and the vector register used for the second instruction which is the instruction (2). It is checked that there is no register conflict relationship with VR1, and a check result indicating that instruction (1) and instruction (2) can pass the register conflict relationship is issued via the data line 15 to the instruction input determination unit. Notify 7.

The register 23 in the memory access conflict check unit 9 holds the vector element distance "5" of the instruction (1), and the register 24 holds the vector element distance "5" of the instruction (2). Since these are equal, the remainder circuit 26 sets the output of the remainder to "ALL1". As a result, the comparator 30 becomes "0".
And the AND circuit 27 outputs “0”.

In this way, the memory access conflict check unit 9
Is a check result indicating that the instruction (1) cannot pass the instruction (1) regarding the memory access conflict relationship via the data line 16 to the instruction input determination unit 7 (the overpass is impossible). Signal, which outputs "0" output of AND circuit 27).

The instruction input determination unit 7 checks the instruction codes of the instruction (1) and the instruction (2) sent via the data lines 11 and 12 and confirms that “the instruction (1) is a vector store instruction and the instruction (2) Is a vector load instruction ”(therefore, the check results by the register conflict check unit 8 and the memory access conflict check unit 9 described above are not referred to), and the instruction of the instruction (1) (fourth The first instruction in the program shown in the figure) is sent to the vector operation unit 5 and the memory control unit 6 via the data lines 17 and 18 at a predetermined timing based on a signal from the state holding unit 3 via the data line 14. Throw in. Further, the instruction input determination unit 7 notifies the execution waiting queue 2 via the data line 13 that the instruction (1) has been input.

The execution waiting queue 2 in the state after the first instruction is input sets the second instruction as the instruction (1) and the vector addition instruction “VR” which is the third instruction as the instruction (2).
Set 0 ← VR0, VR1 "(see FIG. 5 (b)).

In this state, the register conflict check unit 8 in the instruction input control unit 4 reads the vector register VR1 used by the second instruction (1) by the third instruction (2) (vector The register VR1 is checked for a register conflict relationship, and a check result indicating that the instruction (2) cannot pass the instruction (1) regarding the register conflict relationship is issued via the data line 15 to the instruction input determination unit 7 To notify.

The memory access conflict check unit 9 does not check because the third instruction, which is the instruction (2), is a vector addition instruction that does not access the memory.

The memory input determination unit 7 checks the instruction codes of the instruction (1) and the instruction (2) sent via the data lines 11 and 12 and confirms that "instruction (1) is a vector store instruction and instruction (2) Is a vector load instruction ”(therefore, the check result by the register conflict check unit 8 described above is not referred to), and based on the signal from the state holding unit 3 via the data line 14. The memory controller 6 inputs the vector load instruction of the second instruction, which is the instruction (1), into the vector calculator 5 and the memory controller 6 via the data lines 17 and 18 at the timing when the next instruction can be processed. . Further, the instruction input determination unit 7 notifies the execution waiting queue 2 via the data line 13 that the instruction (1) has been input.

The execution queue 2 in the state after the second instruction is input sets the third instruction as the instruction (1) and the vector store instruction “VSTORE VR0 → (4) which is the fourth instruction as the instruction (2). base, 10,256) ”(fifth
See FIG. (C)).

In this state, the register conflict check unit 8 in the instruction input control unit 4 reads out the vector register VR0 written by the third instruction which is the instruction (1) by the fourth instruction which is the instruction (2) (the vector register The existence of a register conflict relationship for VR0 is checked, and a check result indicating that the instruction (1) and the instruction (2) cannot pass the register conflict relationship is sent to the instruction input determination unit 7 via the data line 15. Notice.

The memory access conflict check unit 9 does not perform the check because the third instruction, which is the instruction (1), is a vector addition instruction that does not access the memory.

The memory input determination unit 7 checks the instruction codes of the instruction (1) and the instruction (2) sent via the data lines 11 and 12 and confirms that "instruction (1) is a vector store instruction and instruction (2) Is a vector load instruction (therefore, the check result by the register conflict check unit 8 described above is not referred to), and based on the signal from the state holding unit 3 via the data line 14, At the timing when the vector register VR0 and the vector register VR1 can be read, the vector addition instruction of the third instruction which is the instruction (1) is input to the vector arithmetic unit 5 and the memory control unit 6 via the data lines 17 and 18. .
Further, the instruction input determination unit 7 notifies the execution waiting queue 2 via the data line 13 that the instruction (1) has been input.

The execution queue 2 in the state after the third instruction is input sets the fourth instruction as the instruction (1) and the vector load instruction “VR2 ← (base + 2) which is the fifth instruction as the instruction (2). , 5,256) ”(see FIG. 5 (d)).

In this state, the register conflict check unit 8 in the instruction input control unit 4 does not write the fifth instruction, which is the instruction (2) to be read later, to the vector register VR0 read by the fourth instruction, which is the instruction (1). In addition, it is checked that the instruction (1) does not read the vector register VR2 written by the instruction (2) (there is no register conflict relationship between the vector registers VR0 and VR2), and the instruction (1) executes the instruction (2) regarding the register conflict relationship. ) Is notified to the instruction input determination unit 7 via the data line 15 that the check result indicating that it is possible to pass.

The register 21 in the memory access conflict check unit 9 stores the vector access start address “base” of the instruction (1).
The register 22 holds the vector access start point address “base + 2” of the instruction (2). Since they are not equal, the output (distance) of the subtraction circuit 25 and "0" are not equal, and the comparator 28 outputs "1".

The register 23 in the memory access conflict check unit 9 holds the vector element distance “10” of the instruction (1), and the register 24 holds the vector element distance “5” of the instruction (2). Since these are doubled, the remainder circuit 26
The output of the remainder of is equal to "0" and the comparator 30 outputs "1".

Further, since the output "2" of the subtraction circuit 25 is smaller than the divisor output "5" of the remainder circuit 26, the comparator 29 outputs "1".

The output of the above comparators 28 to 30 makes the AND circuit 27
Outputs "1" to the data line 16.

In this way, the memory access conflict check unit 9
Is a check result indicating that the instruction (1) can pass the instruction (1) regarding the memory access competition relationship to the instruction input determination unit 7 via the data line 16 by the circuit configuration shown in FIG. Signal, which outputs "1" of AND circuit 27).

The memory input determination unit 7 checks the instruction codes of the instruction (1) and the instruction (2) sent via the data lines 11 and 12, and determines that "instruction (1) is a vector store instruction (2) Is a vector load instruction. ”, The check result by the register conflict check unit 8 and the memory access conflict check unit 9 described above, and the vector operation unit 5 and the memory control 6 from the state holding unit 3 Refer to the signal indicating the status.

The instruction input determination unit 7 inputs the vector store instruction which is the instruction (1) until the processing result of the vector addition instruction input in the previous state (see FIG. 5 (c)) by the above-mentioned reference is written in the vector register VR0. Knowing that it is not possible, and referring to the above, command (2) is command (1)
Since it is known that the vector load instruction of the fifth instruction which is the instruction (2) can be overtaken, the vector operation unit 5 and the memory control unit 6 precede the instruction (1) via the data lines 17 and 18. Throw in. Also, the instruction input determination unit 7
Notifies the execution waiting queue 2 via the data line 13 that the instruction (2) has been input.

The pending queue 2 in the state after the fifth instruction is input sets the fourth instruction as the instruction (1) and the vector load instruction “VR3 ← (base + 3) which is the sixth instruction as the instruction (2). , 15, 256) ”(see FIG. 5 (e)).

In this state, the memory access conflict check unit 9 in the instruction input control unit 4 sets the output of the comparator 30 to “0” because the output of the remainder of the remainder circuit 26 is not “0”, and through the data line 16. A check result indicating that the instruction (1) cannot pass the instruction (1) with respect to the memory access conflict relationship with the instruction input determination unit 7 (passing impossible signal).
To notify.

The instruction input determination unit 7 sends the vector store instruction of the fourth instruction, which is the instruction (1), to the vector operation unit 5 and the memory control unit 6 via the data lines 17 and 18 based on the non-overtaking signal. State holding unit 3 via line 14
It is turned on at a predetermined timing based on the signal from. Further, the instruction input determination unit 7 notifies the execution waiting queue 2 via the data line 13 that the instruction (1) has been input.

When the execution queue 2 is in the state shown in FIGS. 5 (f) and 5 (g), the instruction input determination unit 7 in the instruction input control unit 4 checks that "instruction (1) is a vector store instruction Since the condition "(2) is a vector load instruction" is not satisfied, the instruction (1) is input to the vector operation unit 5 and the memory control unit 6 according to the instruction execution order specified by the program.

〔The invention's effect〕

As described above, according to the present invention, by providing the pending queue, the state holding unit, and the instruction input control unit, the vector store instruction that precedes on the program and the vector load instruction that will be read later on one vector element The distance is an integer multiple of 2 or more of the distance between the other vector elements and the absolute value of the difference between the memory access start origin addresses is not 0 and is smaller than the smaller absolute value of the distance between the vector elements. In addition, it can be determined in a short time that the vector load instruction can pass the vector store instruction regarding the memory access conflict relationship, and the vector computer can adopt the same instruction processing order control method as the scalar computer. Therefore, there is an effect that it is possible to speed up the instruction processing.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of an embodiment of the present invention, FIG. 2 is a block diagram showing a detailed configuration of an instruction input control unit in FIG. 1, and FIG. 3 is a memory access in FIG. FIG. 4 is a block diagram showing a detailed configuration of the conflict check unit, FIG. 4 is a diagram showing an example of a program applied to the instruction processing order control system shown in FIG. 1, and FIGS. 5 (a) to 5 (g) are fourth diagrams. It is a figure which shows the transition of the state of the waiting queue in FIG. 1 at the time of execution of the program shown in FIG. In the figure, 1 ... Program holding unit, 2 ... Execution queue, 3 ...
... State holding unit, 4 ... Command input control unit, 5 ... Vector calculator, 6 ... Memory control unit, 7 ... Command input determination unit,
8 ... Register conflict check unit, 9 ... Memory access conflict check unit, 10-20 ... Data line, 21-24 ... Register, 25 ... Subtraction circuit, 26 ... Remainder circuit, 27 ... AND circuit, 28-30 ... Comparator.

Claims (1)

[Claims] 1. A vector arithmetic unit having a plurality of vector registers and one or more pipelined arithmetic units and a memory control for controlling input / output of vector data transmitted / received between a main memory and a vector register. In the instruction processing order control method in a vector computer equipped with a section, it is used by the execution queue and the execution waiting queue that holds the instruction group input to the vector operation unit and the memory control section based on the instruction execution order specified by the program. Vector registers,
A state holding unit that holds the states of the arithmetic unit and the memory control unit; a preceding vector store instruction in the instruction group held in the execution waiting queue; and a holding queue that follows the vector store instruction. With respect to the vector load instruction in the present instruction group, the absolute value of the distance between one vector element is an integer multiple of 2 or more of the absolute value of the distance between the other vector elements, and the difference between both memory access start origin addresses is 0. If the absolute value of the difference is smaller than the smaller absolute value of the distance between both vector elements and there is no register conflict relationship, the vector is held at the timing based on the state held in the state holding unit. And an instruction input control unit for inputting a load instruction to the vector arithmetic unit and the memory control unit prior to the vector store instruction. Instruction processing order control method according to claim.