JPH04130926A - Instruction supplying system - Google Patents

Abstract

PURPOSE:To easily obtain the predictive order instruction address of each control instruction and to execute a rapid parallel processing by holding a predictive order instruction address to be executed next in an instruction string and supplying an instruction to a parallel processing part. CONSTITUTION:An instruction (i) and the predictive order instruction address are read out by an address register 11 in an instruction storage device 1 and outputted to a router 7 through a path A. When the identification(ID) flag of input data inputted from a path B is '0' the router 7 decides the data is an instruction and supplies the data to a parallel processor 13 through a path D. When the ID flag of the input data is '1', the predictive order instruction address is outputted to a selector 9 through a path C, and when the data from the path A is a normal instruction, the value of the predictive order instruction address register is increased. When the data from the path A is the predictive order instruction address, the value of the address concerned is set up in the address register 11. After determining a control instruction, the processor 13 outputs an address to be branched through a path F, and when the prediction is failed, a correct instruction set up in the register 11 is refetched.

Description

DETAILED DESCRIPTION OF THE INVENTION [Object of the Invention] (Industrial Application Field) The present invention relates to an instruction supply method for a computer that performs parallel execution at the instruction level in order to execute programs at high speed.

(Prior Art) In general, most computers employ an instruction-level parallel execution method in order to execute programs at high speed. The pipeline method is the most popular among the above parallel execution methods. In order to operate the pipelined computer at maximum efficiency, instructions must be supplied to the processing unit without interruption. However, if there is a process such as a data reference relationship between instructions, the instructions cannot be continuously supplied, which impedes pipeline parallel execution and reduces processing speed. In particular, control instructions such as branch instructions that are present in a program change the execution order of instructions, and thus become a major hindrance to the continuous supply of instructions.

Several countermeasures have been implemented to reduce the speed reduction effects of the control commands described above.

The above-mentioned countermeasure is a method of performing static scheduling of the order of instruction execution called delayed branching using software, and a method of performing dynamic scheduling of the order of instruction execution called branch prediction using hardware.

The above specific example will be explained using FIG. 2, which schematically shows an instruction formula including a control instruction.

For example, an IF statement in a program written in a high-level language such as FORTRAN is generally converted into a control instruction as a conditional branch instruction by a compiler.

There are 11 control instructions above, and 4 basic blocks (B
BI to BB4). The above-mentioned basic block is a unit in which a program is viewed from the point of view of execution control. When program control is transferred to the first instruction of any basic block (specifically, for example, when the value of the program counter indicating the address of the instruction being processed indicates the address of the first instruction of the basic block) ), all instructions constituting the basic block are always executed. Further, the basic block is determined by the destination of a control instruction (for example, the jump destination address of a branch instruction) in the instruction string. Therefore, the number of instructions constituting a basic block depends on the nature of the program and can be any number.

The execution order of the above basic blocks will be explained using FIG.

Since the basic block BBI includes a conditional branch instruction, the basic block to be executed next changes depending on whether the condition is satisfied or not. Therefore, the process proceeds from basic block BBI to basic block BB2 or basic block BB3, and then to basic block BB4.

When the above instruction sequence is executed by a pipelined computer, the pipeline consists of four stages: an instruction decoding (D) stage, an operand reading (0) stage, an execution (E) stage, and a writing (W) stage. The calculation of the jump destination address of the branch instruction and the condition determination are processed in the E stage.

Next, a case in which scheduling of the instructions in the instruction sequence is not executed at all will be described with reference to FIG. 3, which shows changes in instruction time in the pipeline.

The above instructions are input into the pipeline in the order in which they are arranged in the memory, and the passage of time is shown in the horizontal axis direction in the figure. There is an interruption in the supply of instructions during the processing of the above pipeline, and this interruption occurs as a result of the control being transferred to basic block BB3 instead of basic block BB2 in the program order due to a conditional branch instruction included in basic block BBI. It is something that

In other words, the branch destination instruction of basic block BBI is executed (E)
The "2" instruction of basic block BB2, which has already been input into the pipeline by the time the stage processing is completed, is an instruction that should not actually be executed.

(Problems to be Solved by the Invention) By the way, the above-mentioned scheduling using delayed instructions changes the execution order of the instructions in the basic block BBl and moves the instructions that are always executed to the next one after the conditional branch instruction. This eliminates the need to include instructions that will not be executed into the pipeline, increasing processing efficiency. However, as shown in FIG. 2, when scheduling is impossible, the effect of delayed branching is reduced. Another problem is that it becomes difficult to develop a pipeline scheduler.

On the other hand, branch prediction predicts the branch destination of a control instruction based on the history of branches when the control instruction was executed in the past, and inserts an instruction with a higher probability of being executed into the pipeline. Therefore, when a specific control instruction is executed for the first time, there is no history of past branches, so in many cases the next instruction in the program of the control instruction is input into the pipeline with the prediction that the branch will not occur. , high-speed processing can be achieved as long as branch predictions are correct. However, in reality, there are some control instructions that have no bias in the direction of branching, and there are also disadvantages such as it is difficult to maintain branch history for each control instruction. In particular, since conventional branch prediction requires a large amount of hardware such as a branch table, it has a cost performance problem when compared to software scheduling methods such as delayed branching.

The present invention has been made in view of the above, and an object of the present invention is to easily obtain the predicted next instruction address of each control instruction, and to quickly perform scheduling of the order of instruction execution. The purpose of this invention is to provide an instruction supply method that realizes execution of parallel processing.

[Structure of the invention]

(Means for Solving the Problems) In order to achieve the above object, the present invention provides a predicted next instruction address that points to an address where an instruction to be executed next in an instruction sequence is stored, and a predicted next instruction address that points to the predicted next instruction address. an instruction storage unit that stores instructions to be supplied to a parallel processing unit that executes parallel processing of the instruction; and a predicted next instruction address and instruction stored in the instruction storage unit, and the read predicted next instruction address. and means for determining an instruction and supplying the instruction to the parallel processing unit.

(Operation) In the instruction supply method having the above configuration, the predicted next instruction address indicating the address where the next instruction to be executed is stored in the instruction string and the predicted next instruction address specified by the predicted next instruction address are supplied to the parallel processing unit. The predicted next instruction address and instruction are read from the instruction storage section in which the instruction to be executed is stored. Since the read predicted next instruction address and instruction are determined and the instructions are supplied to the parallel processing section, rapid parallel processing can be realized.

(Example) Hereinafter, the present invention will be explained in detail using the drawings.

FIG. 1 is a block diagram showing control of an embodiment of the instruction supply system of the present invention.

In the figure, an instruction storage device 1 includes a predicted next instruction address of an instruction address to be executed next in an instruction string and an instruction of the instruction string. Note that the word setting for holding the predicted next instruction address includes a method of setting a word for each instruction, a method of setting a word for each fixed number of instructions, and a method of setting a word for each control instruction. Also,
The instruction storage device 1 includes an identification flag 3 for identifying the above-mentioned instruction and the predicted next instruction address.
The predicted next instruction address is set to "1".

The instruction storage device 1 includes instructions whose identification flags are set and predicted next instruction addresses in the order of the predicted next instruction addresses.

The instruction fetch mechanism 5 includes a router 7, a selector 9, and an address register 11, reads data from the instruction storage device 1, determines an instruction and a predicted next instruction address, and outputs the same to a parallel processing device 13, which will be described later. That is, the router 7 classifies the instruction and predicted next instruction address identification flags read from the instruction storage device 1 via the bus B, and
When the identification flag is "0", it is determined to be a command and is output to a selector 9, which will be described later, via a bus C. On the other hand, when the identification flag is "1", the router 7 determines that it is the predicted next instruction address and outputs it via the bus D to the parallel processing device 13, which will be described later.

The selector 9 determines the value of the address register 11 indicating the address of the instruction storage device 1. When the instruction from the bus A and the predicted next instruction address data are normal instructions, the selector 9 determines the value of the address register 11 indicating the address of the instruction storage device 1. Increment the value of on path E. On the other hand, in the case of the predicted next instruction address, the selector 9 sets the value of the address register 11 in the address register 11 .

The parallel processing device 13 executes parallel processing at the instruction level using a pipeline system or the like based on instructions input via the bus D, and outputs a branch destination address via the bus F when the control instruction is determined.

Next, the operation of this embodiment will be explained.

First, after the power is turned on to the device, the system is started and the data at the address indicated by the address register 11 of the instruction storage device 1, that is, the instruction i and the predicted next instruction address are read out. The read instruction i and predicted next instruction address are output to the router via bus A. When the identification flag of data input via bus B is rOJ, the router 7 determines that the data is a command, and supplies the data via bus D to a parallel processing device 13, which will be described later. When the identification flag of the input data is "1", the predicted next instruction address is output to the selector 9 via the bus C. The selector 9 increments the value of the predicted next instruction address register when the data from the bus A is a normal instruction, and sets the value of the predicted next instruction address in the address register 11 when the data from the bus A is a predicted next instruction address.

Parallel processing device 13 to which instructions are supplied via the path D
outputs the branch destination address via path F when the control instruction is confirmed, and re-fetches the correct instruction set in the address register 11 when pren1 fails. Further, the parallel processing device 13 updates the predicted next address field of the instruction storage device 1 via the path F when the processing is completed.

Thereby, the predicted next instruction address can be easily obtained, and instructions can be supplied to the computer without interruption, thereby quickly realizing parallel processing.

〔Effect of the invention〕

As explained above, according to the present invention, the predicted next instruction address to be executed next is held in the instruction string and the instructions are continuously supplied to the parallel processing unit, so that the predicted next instruction address of each control instruction can be easily determined. In addition, by facilitating the scheduling of instruction execution order, rapid parallel processing can be realized.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing control of an embodiment of the instruction supply system of the present invention, FIG. 2 is a diagram schematically showing an instruction formula including control instructions, and FIG. 3 is a diagram showing the execution order of basic blocks. The illustrated diagram, FIG. 4, is a diagram showing changes in instruction time in the pipeline. 1... Instruction storage device 3... Identification flag 5... Instruction fetch mechanism 7... Router 9... Selector 11... Address register 13... Parallel processing devices A, B, C, D , E, F...Bus fare Hidekazu Fuyoshi, patent attorney for cancer patients

Claims (1)

[Claims] In an instruction supply method that supplies instructions to a parallel processing unit that executes parallel processing of instructions, a predicted next instruction address indicating an address where an instruction to be executed next is stored in an instruction string; an instruction storage unit that stores an instruction to be supplied to the parallel processing unit pointed to by the predicted next instruction address; and a predicted next instruction address and the instruction stored in the instruction storage unit, and the read predicted next instruction address. and means for determining an instruction and supplying the instruction to the parallel processing unit.