JP3431503B2 - Information processing apparatus and program control 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 program control method for controlling conditional branching in an information processing apparatus that pipelines instructions.

[0002]

2. Description of the Related Art In an information processing apparatus that pipelines instructions, the speed of instruction execution is increased by overlapping execution of instructions when the instructions are sequentially sent to the pipeline and sequentially executed. However, when branching by a conditional branch instruction, the branch destination instruction is fetched from the time when the condition is judged, that is, the branch address is set in the program counter after the branch judgment is made, so that there is no waste in the pipeline. There is a vacancy, that is, a branch hazard.

Such branch hazards are greater when the condition is met than when the condition is not met. 1 instruction fetch stage
In the case of stages, the branch hazard is one cycle more. Also,
If there are two instruction fetch stages, the branch hazard is two cycles longer. Furthermore, if the instruction fetch stage is N
In the case of stages (N is an arbitrary positive integer), the branch hazard is N
There are many cycles.

As one of means for solving this problem, conventionally, an instruction at a subsequent address of a branch instruction is executed in a delay slot to reduce a branch hazard of a pipeline.
A branching method called so-called delayed branching is adopted.
An example of the conventional branching method described above is disclosed in, for example, Japanese Patent Laid-Open No.
It is disclosed in Japanese Patent No. 127237.

[0005]

In the conventional method as described above, since the instruction in the delay slot is executed in the cycle of the branch hazard, the execution cycle of the branch instruction is apparently reduced. However, in the branch method using the above-described delay branch, there are restrictions on the instructions that can be placed in the delay slot, or it becomes difficult to properly distribute the instructions to the delay slot when the number of cycles of the branch hazard is large. Therefore, there is a problem that the branching hazard cannot be effectively reduced in all cases.

An object of the present invention is to effectively reduce branch hazards in conditional branch control in an information processing apparatus that pipelines instructions without being restricted by the pipeline configuration, instruction content, and the like. A program control method is provided.

[0007]

Information processing apparatus of the present invention
Has a plurality of instruction decoding stages and instruction execution stages.
Before the instruction decoding stage.
Process instructions in a pipeline with two or more stages
Information processing device that is executed by the information processing device.
Code storing means for storing an instruction to be executed as an instruction code
And an instruction code fetched from the instruction code storage means.
First address holding means for designating an address of the mode,
Based on the address designated by the first address holding means,
The instruction code fetched from the instruction code storage means.
A first command holding means for storing a code, and the first command
The instruction code stored in the holding means is a conditional branch instruction
Branch determination means for determining whether or not the first instruction holding
Decoding hand to decode the instruction code stored in the means
Stage and the decoding result in the decoding means
Means for executing the calculation by means of
The result is the instruction code stored in the first instruction holding means.
Code indicates a conditional branch instruction,
Before the branch judgment of the conditional branch instruction,
Second address holding means for saving the subsequent address of the command
And the decision result of the branch decision means is the first instruction protection
The instruction code stored in the holding means is a conditional branch instruction.
, The branch of the conditional branch instruction
Before the judgment, the instruction code following the conditional branch instruction is saved.
A second instruction holding means for
The determination result is the instruction stored in the first instruction holding unit.
If the code indicates a conditional branch instruction
The branch destination instruction in advance to the pipeline.
Type, if the conditions are satisfied in the conditional branch instruction, the branch
When the previous instruction is executed and the condition of the conditional branch instruction is not satisfied
Is stored in the second address holding means
The subsequent address is returned to the first address holding means,
The succeeding instruction code saved in the second instruction holding means.
By decoding the code with the decoding means,
It is characterized in that the instruction subsequent to the conditional branch instruction is executed.
Also, the first program processing method of the present invention is
Multiple stages, including an instruction decoding stage and an instruction execution stage.
And n before the instruction decoding stage.
Pipeline having (n: integer of 2 or more) stages
Instructions that are processed in the pipeline and input to the pipeline
Address holding means for indicating the address of the
Store the instruction to be decoded in the decode stage
1 instruction holding means and the first address holding means
Different second address holding means and the first instruction holding
Information processing including second instruction holding means different from the means
Control method for controlling conditional branching in device
And is decoded in the instruction decoding stage
If the specified instruction is a conditional branch instruction, the conditional branch instruction
Instruction at the instruction execution stage, the conditional branch instruction
As the pipeline information of the subsequent instruction of
The address of the instruction n + 1 after the instruction is the second address
The instruction of the instruction after the conditional branch instruction is sent to the holding means.
Instruction code is saved to the second instruction holding means, and the branch destination
Prior to charged into the pipeline instructions, the condition min
If the condition of the branch instruction is satisfied, the branch destination instruction remains unchanged.
Run, if the condition is not established in the conditional branch instruction, the
The conditional branch instruction saved to the second address holding means
The address of the instruction n + 1 after the instruction is the first address
It is returned to the holding means and saved in the second instruction holding means.
The instruction code of the instruction one instruction after the conditional branch instruction
By decoding, the subsequent instruction of the conditional branch instruction
It is characterized by executing. Furthermore, the second aspect of the present invention
The program processing method includes a first instruction decoding stage.
A plurality of instruction decoding stages and instruction execution stages.
Number of stages, the first instruction decoding stage
Before n has a stage of n (n: integer of 2 or more) stages
Ipline processes the instruction and puts it into the pipeline.
First address holding means for indicating an address of an instruction to be executed,
Decode the one of the plurality of instruction decoding stage
First instruction holding means for storing an instruction to be stored;
A second address holder different from the first address holder
And a second instruction storage different from the first instruction storage means.
Control of conditional branching in an information processing apparatus including a holding unit
And a program control method for executing the first command solution
The instruction decoded in the read stage is a conditional branch instruction
Then the next scan of the first instruction decode stage.
Pipe of the instruction subsequent to the conditional branch instruction
As line information, the instruction n + 1 later than the conditional branch instruction
The address of the command to the second address holding means,
The instruction code of the instruction one instruction after the conditional branch instruction is the second code.
To the instruction holding means of the branch destination instruction
When the condition of the conditional branch instruction is satisfied , it is input to the pipeline.
If executes the branch target instruction as the condition min
When the condition of the branch instruction is not satisfied, the second address is retained
Command n + 1 later than the conditional branch instruction saved to the means
The address of the command to the first address holding means,
The conditional branch instruction saved to the second instruction holding unit
To decode the instruction code of the instruction one instruction after
Therefore, the instruction subsequent to the conditional branch instruction is executed.
To collect.

According to this structure, the instruction is decoded, and if the instruction is a conditional branch instruction, the branch of the conditional branch instruction is executed.
Since the branch destination instruction is inserted into the pipeline in advance before the judgment , at least the first stage of the pipeline processing for the branch destination instruction is completed when the condition is satisfied, and after the condition is satisfied, the second and subsequent stages are completed. Since the pipeline information about the branch destination instruction will be continued from any stage of, the branch destination instruction is executed as compared with the case where the branch destination instruction is input to the pipeline after the branch determination of the conditional branch instruction. In this case, the branching hazard can be reduced.

On the other hand, when the instruction is decoded and the instruction is a conditional branch instruction, the subsequent address and the subsequent instruction code are saved as pipeline information of the subsequent instruction of the conditional branch instruction before the branch determination of the conditional branch instruction. Therefore, when the condition is not satisfied, by returning the pipeline information of the instruction subsequent to the saved conditional branch instruction to the pipeline,
The instruction subsequent to the conditional branch instruction can be executed without increasing the branch hazard.

Therefore, as a whole, the branch hazard when the branch is taken can be reduced without increasing the branch hazard when the branch is not taken, the program can be efficiently executed, and the processing time is shortened. It becomes possible.

Further, if the instruction is simply decoded and the instruction is a conditional branch instruction, the subsequent address and the subsequent instruction code are saved as pipeline information of the instruction subsequent to the conditional branch instruction before the branch determination of the conditional branch instruction. However, since the branch destination instruction is only put into the pipeline in advance, the branch hazard can be effectively reduced without being restricted by the pipeline configuration, the instruction content, and the like.

[0012]

BEST MODE FOR CARRYING OUT THE INVENTION (First Embodiment) A program control method and apparatus for conditional branching processing according to a first embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the basic arrangement of a program control device according to the first embodiment of the present invention. Figure 1
2, the program counter unit 1 serves as an address generating unit for reading an instruction code, and inputs a branch signal 14 indicating a conditional branch instruction and a branch address 15 corresponding to the address of a branch destination instruction from the branch determiner 4. ,
Address 11 is output. The memory 2 serves as an instruction code storage means for storing an instruction code, receives the address 11 from the program counter unit 1 and outputs the first instruction code 12 corresponding to the address 11. Instruction register unit 3
Serves as an instruction control unit, which inputs the first instruction code 12 from the memory 2, inputs the branch signal 14 from the branch determiner 4, and outputs the second instruction code 13. Branch decision device 4
Is a branch determining means, which inputs the second instruction code 13 from the instruction register unit 3 and the condition flag signal 17 from the arithmetic unit 6 and determines whether the second instruction code 13 is a conditional branch instruction. When it is a conditional branch instruction, the branch signal 14 and the address of the branch target instruction included in the conditional branch instruction, that is, the branch address 15 are output. The decoder unit 5 serves as a means for decoding an instruction, receives the second instruction code 13 from the instruction register unit 3, and outputs the control signal 1
6 is output. The arithmetic unit 6 serves as an arithmetic means, receives the control signal 16 from the decoder unit 5, executes an arithmetic operation, and outputs a condition flag signal 17. The configuration of FIG. 1 is described below .
This is common to the second embodiment.

FIG. 2 is a block diagram showing the configuration of the program counter section 1 according to the first embodiment of the present invention. In FIG. 2, the first program counter 101
Serves as a first address holding means, inputs the address selector output 113, and outputs the address 11. The address adder 102 serves as an address adding unit that increments the address 11, inputs the address 11, and outputs an address adder output 114.

The second program counter 104 decodes the instruction, and when the instruction is a conditional branch instruction, it is one of the pipeline information of the instruction subsequent to the conditional branch instruction before the branch judgment of the conditional branch instruction. It becomes the second address holding means for saving the address of the instruction subsequent to the conditional branch instruction, receives the address adder output 114 and the second program counter branch signal 112, outputs the second program counter output 115, and outputs the address. The adder output 114 corresponds to the address of the subsequent instruction that is saved and the second program counter output 115 corresponds to the address of the subsequent instruction that is returned to the pipeline.

The address selector 103 serves as address selecting means, and the branch address 15 and the address adder output 11
4 and the second program counter output 115 and the address selector branch signal 111 are input, and the address selector output 1
13 is output. As the address selector 103,
Based on the address selector branch signal 111, the branch address 15 is selected as the next address in the case of a conditional branch instruction, and the address adder output 114 is selected as the next address in the case of an instruction other than the conditional branch instruction. When the conditional branch instruction is not satisfied, the second program counter output 115 is selected as the next address in the execution stage of the conditional branch instruction.

Note that the branch deciding unit 4 determines that the condition is not satisfied when the condition flag signal 17 is "0" at the execution stage when it is a conditional branch instruction, and the address selector branch signal 111 and the first instruction register. Branch signal 3
11 is output.

FIG. 4 is a block diagram showing the configuration of the instruction register unit 3 in the first embodiment of the present invention. Figure 4
In, the first instruction register 301 serves as a first instruction holding unit, inputs the first instruction code 12 and the first instruction register branch signal 311, and outputs the first instruction register output 314. In this case, the first instruction register 3
01 normally stores the first instruction code 12 while updating it every cycle, but the first instruction register branch signal 3
When 11 is input, the instruction code of the previous cycle is held.

The second instruction register 303 stores the second instruction
It serves as a holding means and serves as a first instruction code 12 and a second instruction record.
Input the branch signal 313 for the register to the second instruction register
The output 316 is output. The above second instruction register 30
3 saves the instruction code of the subsequent instruction of the conditional branch instruction
Have a function.

The instruction selector 302 serves as an instruction selecting means, and outputs the first instruction register output 314 and the second instruction register.
Data output 316, the NOP code 315, and the instruction selector branch signal 312 are input, and the second instruction code 13 is output. In this case, the instruction selector 302 is a branch for the instruction selector.
In response to the signal 312, the first instruction register output 314 and the first instruction register output 314
2 instruction register output 316 and NOP code 315
Select one. When the branch is not taken, the instruction selector 302
Saved by selecting the second instruction register output 316
To return the instruction code of the succeeding instruction to the pipeline
Have the ability.

As described above, the first embodiment is similar to FIG.
The program counter section 1 of the configuration of the basic structure as in Figure 2 of the one in which the configuration of the instruction register unit 3 as in FIG. The branch signal 14 is the address selector branch signal 111 and the second program counter branch signal 11
2, the first instruction register branch signal 311, the instruction selector branch signal 312, and the second instruction register branch signal 31.
It consists of three.

The operation of the program control device configured as described above will be described below with reference to FIGS. 6 and 7 .

FIG. 6 shows conditional branching in the case of a four-stage pipeline (first instruction fetch stage IF1, second instruction fetch stage IF2, instruction decoding stage DEC, instruction execution stage EX) when two stages are provided for instruction fetch. 6 shows a control flow when an instruction is executed. In this case, the address of the conditional branch instruction is N and the address of the branch target instruction is M. In addition, FIG. 7
Is a timing chart at that time, (a) is when the condition is satisfied, and (b) is when the condition is not satisfied. The operation of each pipeline stage will be described below. The description of the first instruction fetch stage and the second instruction fetch stage is omitted. (1) Instruction decoding stage of conditional branch instruction The stage branch determiner 4 decodes the second instruction code 13 and determines that it is a conditional branch instruction, and outputs a branch signal 14 and a branch address 15. (2) Execution stage of conditional branch instruction By the second program counter branch signal 112, the address (N + 3) three addresses after the conditional branch instruction is set in the second program counter 104. As a result, the address (N + 3) of the instruction three instructions after the conditional branch instruction is saved.

By the address selector branch signal 111,
The address selector 103 selects the branch address 15 and sets the branch address 15 in the first program counter 101, and the address 11 becomes the address M. As a result, the branch destination instruction is inserted into the pipeline in advance before the time point when the branch determination is performed (the end of the execution stage of the conditional branch instruction).

The instruction code (N + 1) immediately after the conditional branch instruction is set in the second instruction register 303 by the second instruction register branch signal 313. As a result, the instruction code (N + 1) immediately after the conditional branch instruction is saved.

The instruction selector 302 selects the NOP code (unprocessed code) 315 by the instruction selector branch signal 312, and the second instruction code 13 becomes a NOP instruction. When the condition is satisfied (3) The instruction selector 302 is operated by the branch signal 312 for the instruction selector of the next stage of the execution stage of the conditional branch instruction.
Selects the NOP code (unprocessed code) 315 and the second
The instruction code 13 of is a NOP instruction.

(4) After the execution stage of the conditional branch instruction, the next stage branch signal 14 is released and the normal operation is resumed, and the second instruction code 13 becomes the instruction at the address M. As a result, after the conditional branch instruction at the address N, a two-cycle branch hazard is inserted, but the instructions at the address M and thereafter are executed in order. When the condition is not satisfied (3) The address selector 103 selects the second program counter output 115 by the branch signal 111 for the next stage address selector of the execution stage of the conditional branch instruction, and the first program counter 101 receives the second program counter output 115. Set the value of the program counter 104, and the address 11 is N + 3
It becomes the address. As a result, the saved address of the subsequent instruction is returned to the pipeline.

The instruction selector branch signal 312 causes the instruction selector 302 to output the second instruction register output 316.
And the second instruction code 13 becomes the instruction at the address N + 1. As a result, the instruction code of the saved subsequent instruction is returned to the pipeline.

(4) Successive stage after execution of conditional branch instruction By the first instruction register branch signal 311, the first instruction register 301 holds the instruction at address N + 2 and the second instruction code 13 becomes N + 2. It becomes an instruction of the address.

As a result, after the conditional branch instruction at address N,
Although a one-cycle branch hazard is entered, instructions from address N + 1 onward will be executed in order.

[0031] Figure 1 2 is a four-stage pipeline (first instruction fetch stage IF1, the second instruction fetch stage IF
1, instruction decoding stage DEC, instruction execution stage EX)
In the case of, the time chart of the conventional example in the case of executing the conditional branch instruction is shown, (a) is when the condition is satisfied, and (b) is when the condition is not satisfied. In this case, the address of the conditional branch instruction is N and the address of the branch target instruction is M.

[0032] Comparing FIGS. 7 and 1 2, it can be seen that the branch hazard when the condition is met is reduced by one cycle.

The operation of the 5-stage pipeline will be described below with reference to FIGS. 8 and 9 .

FIG. 8 shows a 5-stage pipeline (first instruction fetch stage IF) when two stages are used for instruction fetch.
1, a second instruction fetch stage IF2, a first instruction decoding stage DEC1, a second instruction decoding stage DEC2, an instruction execution stage EX), a control flow for executing a conditional branch instruction is shown. in this case,
The address of the conditional branch instruction is N, and the address of the branch destination instruction is M. Further, FIG. 9 is a timing chart at that time, where (a) is when the condition is satisfied and (b) is when the condition is not satisfied. The operation of each pipeline stage will be described below. The description of the first instruction fetch stage, the second instruction fetch stage, and the first instruction decoding stage is omitted. (1) Second instruction decoding stage of conditional branch instruction The branch decision unit 4 decodes the second instruction code 13 and determines that it is a conditional branch instruction, and outputs a branch signal 14 and a branch address 15.

Second branch signal for program counter 11
2, the address after the conditional branch instruction (N + 3)
Is set in the second program counter 104. As a result, the address (N +
3) is saved.

With the branch signal 111 for the address selector,
The address selector 103 selects the branch address 15 and sets the branch address 15 in the first program counter 101, and the address 11 becomes the address M. As a result, the branch destination instruction is inserted into the pipeline in advance before the time point when the branch determination is performed (the end of the execution stage of the conditional branch instruction).

The instruction code (N + 1) immediately after the conditional branch instruction is set in the second instruction register 303 by the second instruction register branch signal 313. As a result, the instruction code (N + 1) immediately after the conditional branch instruction is saved.

The instruction selector 302 selects the NOP code (unprocessed code) 315 by the instruction selector branch signal 312, and the second instruction code 13 becomes a NOP instruction. (2) By the branch signal 312 for the execution stage instruction selector of the conditional branch instruction, the instruction selector 302
Selects the NOP code (unprocessed code) 315 and the second
The instruction code 13 of is a NOP instruction. When the condition is satisfied (3) The next stage branch signal 14 of the execution stage of the conditional branch instruction is released and the normal operation is resumed, and the second instruction code 13 becomes the instruction at the address M.

As a result, after the conditional branch instruction at address N,
Although a two-cycle branch hazard is entered, the instructions after the address M will be executed in order. When the condition is not satisfied (3) The address selector 103 selects the second program counter output 115 by the branch signal 111 for the next stage address selector of the execution stage of the conditional branch instruction, and the first program counter 101 receives the second program counter output 115. The program counter 104 also sets a value, and the address 11 is N + 3.
It becomes the address. As a result, the saved address of the subsequent instruction is returned to the pipeline.

By the first instruction register branch signal 311, the first instruction register 301 holds the instruction at address N + 2 and the second instruction code 13 becomes the instruction at address N + 2.

The instruction selector 302 selects the second instruction register output 316 by the instruction selector branch signal 312, and the second instruction code 13 becomes the instruction at the address N + 1.
As a result, the instruction code of the saved subsequent instruction is returned to the pipeline.

(4) Successive stages after execution of conditional branch instruction By the first instruction register branch signal 311, the first instruction register 301 holds the instruction at address N + 2 and the second instruction code 13 becomes N + 2. It becomes an instruction of the address.

As a result, after the conditional branch instruction at address N,
Although a two-cycle branch hazard is entered, instructions from address N + 1 onward will be executed in sequence.

The program control method shown in FIG. 1, FIG. 2, FIG. 4, FIG. 6, FIG. 7, FIG. 8 and FIG. 9 can be summarized as follows. That is, when the instruction code of the address 11 output from the program counter unit 1 is fetched from the memory 2 to the instruction register unit 3 and the instruction is executed, the conditional branching control for pipeline processing the instruction is performed. To decode the instruction,
If the instruction is a conditional branch instruction, the minute of the conditional branch instruction
Before the branch determination , the program counter section 1 saves the address of the instruction three instructions after the conditional branch instruction, sets the branch address 15 in the program counter section 1, and the instruction register section 3 sets the branch address one instruction after the conditional branch instruction. The instruction code of the instruction is saved, and the instruction register unit 3 replaces the instruction code with the unprocessed instruction code. When the condition is satisfied, the instruction code is executed as it is, and when the condition is not satisfied, the instruction three instructions after the saved conditional branch instruction is executed. The address is set in the program counter unit 1, the instruction code is replaced in the instruction register unit 3 with the instruction code of the instruction immediately after the conditional branch instruction that was saved, and then the instruction of the instruction two instructions after the conditional branch instruction. This means that the code is held in the first instruction register 301 and executed. In the case of FIGS. 8 and 9, there are two steps for replacing the instruction code with the non-processing instruction code.

The above Figures 1, 2, 4, 6, 7,
8 and the program controller shown in FIG. 9 are configured as follows. That is, it controls a conditional branch when an instruction is pipelined, and inputs a branch address 15 and a branch signal 14 to generate an address 11, and a program counter section 1 corresponding to the address 11 Memory 2 for storing or outputting the instruction code 12 of
And input the first instruction code 12 and the branch signal 14,
An instruction register unit 3 that outputs a second instruction code 13,
A branch determiner 4 that decodes the second instruction code 13 to determine a branch and outputs a branch signal 14 and a branch address 15.
Is equipped with.

In this case, the program counter section 1 is the first
It is also composed of second program counters 101 and 104, an address selector 103, and an address adder 102. Then, the first program counter 101 receives the address selector output 113 as an input and outputs the address 11. Further, the address selector 103 receives the branch address 15, the address adder output 114 and the second program counter output 115 as input, and the branch signal 14 causes the branch address 15, the address adder output 114 and the second program counter output 115. And either of them are output. Further, the address adder 102 increments the address 11. In addition, the second program counter 1
04 receives the address adder output 114, and holds the address adder output 114 by the branch signal 14.

On the other hand, the instruction register unit 3 has the first and second
The instruction registers 301 and 303 and the instruction selector 302. Then, the first instruction register 301
Receives the first instruction code 12 and holds the first instruction code 12 by the branch signal 14. Further, the second instruction register 303 receives the first instruction code 12 as an input and holds the first instruction code 12 by the branch signal 14. In addition, the instruction selector 302 outputs the first instruction register output 314.
And second instruction register output 316 and NOP code 315
Is input and the branch signal 14 selects one of the first instruction register output 314, the second instruction register output 316, and the NOP code 315 to select the second instruction code 13
Output as.

According to this structure, the branch judgment of the conditional branch instruction is made.
A constant before, the address of the instruction following three conditional branch instruction second
In the program counter 104, the branch address 15 is set in the first program counter 101, the instruction code of the instruction after the conditional branch instruction is saved in the second instruction register 303, and the instruction selector 302 NOP code 3
When the condition 15 is selected, the condition is satisfied and the condition is satisfied, the condition is satisfied, and when the condition is not satisfied, the address saved in the second program counter 104 is set in the first program counter 101, and the second instruction register is set by the instruction selector 302. 303
Is selected and the instruction code of the instruction two instructions after the conditional branch instruction is held and executed in the first instruction register 301, and when the instruction fetch stage is two stages, the conditional branch instruction The branch hazard when the condition is satisfied can be reduced by 2 cycles.

As described above, according to this embodiment,
Since the branch address 15 is inserted into the pipeline in advance by setting the branch address 15 in the first program counter 101 before the branch judgment of the conditional branch instruction, when the condition is satisfied, the pipeline processing of the branch target instruction is executed. Since the first instruction fetch stage is completed and the pipeline processing for the branch target instruction is continued from the second instruction decoding stage after the condition is satisfied, the branch target instruction is piped after the branch judgment of the conditional branch instruction. It is possible to reduce the branch hazard when executing the branch destination instruction, as compared with the case where the branch target instruction is executed.

On the other hand, by storing the address of the instruction subsequent to the conditional branch instruction in the second program counter 104 before the branch determination of the conditional branch instruction, the address of the instruction subsequent to the conditional branch instruction is saved and the first instruction is saved. By storing the register output 314 in the second instruction register 303, the instruction code of the instruction subsequent to the conditional branch instruction is saved before the branch determination of the conditional branch instruction. Therefore, when the condition is not satisfied, it is saved. Branch hazard by setting the address of the instruction subsequent to the conditional branch instruction to the pipeline by setting the first program counter 101 and returning to the pipeline by outputting the instruction code from the second instruction register 303. The instruction subsequent to the conditional branch instruction can be executed without increasing Therefore, as a whole, it is possible to reduce the branch hazard when the branch is taken without increasing the branch hazard when the branch is not taken, the program can be executed efficiently, and the processing time can be shortened. Becomes

Further, since the address and the instruction code of the instruction subsequent to the conditional branch instruction are simply saved before the branch of the conditional branch instruction is judged , and the branch address 15 is inserted into the pipeline in advance, the pipeline The branch hazard can be effectively reduced without being restricted by the configuration or the content of the instruction.

Particularly, in the case of a four-stage pipeline having two instruction fetch stages, the branch hazard when the condition is satisfied can be reduced by one cycle. Further, in the case of a 5-stage pipeline with two instruction fetch stages,
The branch hazard when the condition is satisfied can be reduced by 2 cycles.

In the above, the instruction fetch stage is set to 2
Although described as a stage, it is clear that the same effect can be obtained even if the number of stages is three or more by adding instruction registers corresponding to the number of stages of the fetch stage. I have shown the instruction decoding stage 1 stage and 2 stages,
The same effect can be obtained with three or more stages. In particular, when the instruction fetch stage is 3 or more, by setting the instruction decoding stage to 3 or more, the number of cycles of branch hazard reduction when the condition is satisfied can be set to 3 or more.

[0054] The program control method and apparatus in conditional branch processing according to the second embodiment (second embodiment) Hereinafter the present invention will be described with reference to the drawings.

FIG . 3 shows the second embodiment of the present invention.
FIG. 3 is a block diagram showing a configuration of a program counter unit 1.
It The difference from FIG. 2 is that the second program counter 10
4 input from address adder output 114 to address 11
It is a point changed to. In FIG. 3, the same function as in FIG.
The same reference numerals are given to those having
Omit it.

FIG. 5 is a block diagram showing the structure of the instruction register unit 3 in the second embodiment of the invention. Figure 4
Is different from the first instruction code 12 to the first instruction code
The instruction register output 314 is changed. 5 , those having the same functions as those in FIG. 4 are designated by the same reference numerals, and detailed description thereof will be omitted.

[0057] The second embodiment is one in which as in Figure 3 the basic configuration of the program counter section 1 of the configuration of FIG. 1, the configuration of the instruction register unit 3 as in FIG. The branch signal 14 is the address selector branch signal 111, the second program counter branch signal 112, the first instruction register branch signal 311, and the instruction selector branch signal 3.
12 and a second instruction register branch signal 313.

[0058] The configuration program controller as above, the operation will be described with reference to FIGS. 1 0 and 1 1 below.

[0059] Figure 1 0 6-stage pipeline when provided 2-stage as an instruction fetch (first instruction fetch stage IF1, the second instruction fetch stage IF2, the first instruction decode stage DEC1, the second instruction decode stage DEC
2 shows a control flow when a conditional branch instruction is executed in the case of the second, third instruction decoding stage DEC3, and instruction execution stage EX). In this case, the address of the conditional branch instruction is N and the address of the branch target instruction is M. Further, FIG. 1 1 is a timing chart at that time. The operation of each pipeline stage will be described below. The description of the first instruction fetch stage, the second instruction fetch stage, and the first instruction decoding stage is omitted. (1) Second instruction decoding stage of conditional branch instruction The branch decision unit 4 decodes the second instruction code 13 and determines that it is a conditional branch instruction, and outputs a branch signal 14 and a branch address 15.

The instruction selector 302 selects the NOP code (unprocessed code) 315 by the instruction selector branch signal 312, and the second instruction code 13 becomes a NOP instruction. (2) Third instruction decoding stage of conditional branch instruction By the second program counter branch signal 112, the address (N + 3) after three conditional branch instructions is set in the second program counter 104. As a result, the address (N + 3) of the instruction three instructions after the conditional branch instruction is saved.

With the branch signal 111 for the address selector,
The address selector 103 selects the branch address 15 and sets the branch address 15 in the first program counter 101, and the address 11 becomes the address M. As a result, the branch destination instruction is inserted into the pipeline in advance before the time point when the branch determination is performed (the end of the execution stage of the conditional branch instruction).

The instruction code (N + 1) immediately after the conditional branch instruction is set in the second instruction register 303 by the second instruction register branch signal 313. As a result, the instruction code (N + 1) immediately after the conditional branch instruction is saved.

The instruction selector branch signal 312 causes the instruction selector 302 to select the NOP code (unprocessed code) 315, and the second instruction code 13 becomes a NOP instruction. (3) By the branch signal 312 for the execution stage instruction selector of the conditional branch instruction, the instruction selector 302
Selects the NOP code (unprocessed code) 315 and the second
The instruction code 13 of is a NOP instruction. -When the condition is satisfied (4) The next stage branch signal 14 of the execution stage of the conditional branch instruction is released and the normal operation is resumed, and the second instruction code 13 becomes the instruction at the address M.

As a result, after the conditional branch instruction at address N,
Although a branch hazard of 3 cycles is entered, the instructions after the address M will be executed in order. When the condition is not satisfied (4) The address selector 103 selects the second program counter output 115 by the branch signal 111 for the next stage address selector of the execution stage of the conditional branch instruction, and the first program counter 101 receives the second program counter output 115. Set the value of the program counter 104, and the address 11 is N + 3
It becomes the address. As a result, the saved address of the subsequent instruction is returned to the pipeline. Also, the first
The instruction register branch signal 311 causes the first instruction register 301 to hold the instruction at address N + 2.

The instruction selector branch signal 312 causes the instruction selector 302 to select the second instruction register output 316, and the second instruction code 13 becomes the instruction at the address N + 1.
As a result, the instruction code of the saved subsequent instruction is returned to the pipeline.

(5) Successive stages after execution of conditional branch instruction By the first instruction register branch signal 311, the first instruction register 301 holds the instruction at address N + 2 and the second instruction code 13 becomes N + 2. It becomes an instruction of the address.

As a result, after the conditional branch instruction at address N,
Although the branch hazard of 3 cycles is entered, the instructions after the address N + 1 are sequentially executed.

The program control method shown in FIG. 1, FIG. 3, FIG. 6, FIG. 10 and FIG. 11 can be summarized as follows. That is, the instruction code of the address 11 output by the program counter unit 1 is stored in the memory 2
From the instruction register unit 3 to execute the instruction, the instruction is decoded when the conditional branch is controlled when the instruction is pipeline processed, and when the instruction is the conditional branch instruction, Before the branch judgment of the conditional branch instruction, the instruction register unit 3 replaces the instruction code with a non-processed instruction code, and the program counter unit 1 saves the address of the instruction three instructions after the conditional branch instruction. Branch address 15 is set in the instruction register unit 3, the instruction register unit 3 saves the instruction code of the instruction after the conditional branch instruction, the instruction register unit 3 replaces the instruction code with the unprocessed instruction code, and then the conditional branch instruction The instruction code of the instruction two behind is held in the instruction register unit 3, and the instruction register unit 3
Replaces the instruction code with an unprocessed instruction code, and when the condition is satisfied, it is executed as it is. When the condition is not satisfied, the address of the instruction three instructions after the saved conditional branch instruction is set in the program counter unit 1 and the instruction register The unit 3 replaces the instruction code with the instruction code of the instruction after the conditional branch instruction that has been saved, and then holds and executes the instruction code of the instruction after the conditional branch instruction in the instruction register unit 3. It turns out that.

[0069] in the 1, 3, 6, a program control system shown in FIG. 1 0 and 1 1 is configured as follows. That is, it controls a conditional branch when the instruction is pipelined.
And a branch signal 14 to generate an address 11, and a program counter unit 1 for generating an address 11
Memory 2 for storing or outputting the instruction code 12 of No. 1, the instruction register unit 3 for inputting the first instruction code 12 and the branch signal 14 and outputting the second instruction code 13, and the second instruction code 13. A branch judging device 4 for decoding and judging a branch and outputting a branch signal 14 and a branch address 15 is provided.

In this case, the program counter section 1
It is also composed of second program counters 101 and 104, an address selector 103, and an address adder 102. Then, the first program counter 101 receives the address selector output 113 as an input and outputs the address 11. Further, the address selector 103 receives the branch address 15, the address adder output 114 and the second program counter output 115 as input, and the branch signal 14 causes the branch address 15, the address adder output 114 and the second program counter output 115. And either of them are output. Further, the address adder 102 increments the address 11. In addition, the second program counter 1
04 receives the address 11 and holds the address 11 by the branch signal 14.

On the other hand, the instruction register unit 3 has the first and second instruction registers.
The instruction registers 301 and 303 and the instruction selector 302. Then, the first instruction register 301
Receives the first instruction code 12 and holds the first instruction code 12 by the branch signal 14. Further, the second instruction register 303 receives the first instruction register output 314 as an input, and the branch signal 14 causes the first instruction register output 31.
Hold 4 In addition, the instruction selector 302 outputs the first instruction register output 314, the second instruction register output 316, N
When the OP code 315 is input, any one of the first instruction register output 314, the second instruction register output 316, and the NOP code 315 is selected by the branch signal 14, and the second instruction register output 314 is selected.
Is output as the instruction code 13.

According to this structure, the branch judgment of the conditional branch instruction is made.
To a constant before, select the NOP code 315 in instruction selector 302, and saves the address of the instruction following three conditional branch instruction to the second program counter 104, sets a branch address 15 to the first program counter 101 Then, the instruction code of the instruction after the conditional branch instruction is stored in the second instruction register 3
03, and the NOP code 315 in the instruction selector 302
When the condition is satisfied, the program is executed as it is, and when the condition is not satisfied, the address saved in the second program counter 104 is set in the first program counter 101, and the second instruction register 303 is set by the instruction selector 302. And select the instruction code of the instruction two instructions after the conditional branch instruction as the first
When the instruction fetch stage has two stages, the branch hazard when the condition of the conditional branch instruction is satisfied can be reduced by two cycles by controlling the instruction register 301 to hold and execute the instruction.

As described above, according to this embodiment,
Similar to the above-described first embodiment, in the case of a 6-stage pipeline having two instruction fetch stages, the branch hazard when the condition is satisfied can be reduced by 2 cycles. Further, the number of stages of branch determination can be increased by one stage as compared with the first embodiment.

In the above, the instruction fetch stage is set to 2
Although the description has been given as a stage, it is apparent that the same effect can be obtained by adding the instruction register even if the number of stages is three or more. The same effect can be obtained even if the instruction decoding stage is four stages or more.

Furthermore, the address (N + 3) three times after the conditional branch instruction to the second program counter 104 performed in the above-mentioned third instruction decoding stage and the conditional branch instruction to the second instruction register 303 are set. By setting the instruction code (N + 1), which is one step after, in the second instruction decoding stage, the six-stage pipeline can be realized also in the first embodiment. That is, the difference from the first embodiment lies in the save timing of the instruction subsequent to the conditional branch instruction.

[0076]

According to the program control method of the present invention,
If the instruction is decoded and the instruction is a conditional branch instruction, the branch destination instruction is inserted into the pipeline in advance before the branch judgment of the conditional branch instruction. Since at least the first stage of the pipeline processing has been completed and after the condition is satisfied, the pipeline processing for the branch destination instruction will be continued from any of the second and subsequent stages, the branch determination of the conditional branch instruction is performed. It is possible to reduce the branch hazard when executing the branch destination instruction as compared with the case where the branch destination instruction is input to the pipeline later.

On the other hand, if the instruction is decoded and the instruction is a conditional branch instruction, the subsequent address and the subsequent instruction code are saved as pipeline information of the subsequent instruction of the conditional branch instruction before the branch determination of the conditional branch instruction. Therefore, when the condition is not satisfied, by returning the pipeline information of the instruction subsequent to the saved conditional branch instruction to the pipeline,
The instruction subsequent to the conditional branch instruction can be executed without increasing the branch hazard.

Therefore, as a whole, the branch hazard when the branch is taken can be reduced without increasing the branch hazard when the branch is not taken, the program can be executed efficiently, and the processing time is shortened. It becomes possible.

Further, the instruction is simply decoded, and if the instruction is a conditional branch instruction, the subsequent address and the subsequent instruction code are saved as pipeline information of the instruction subsequent to the conditional branch instruction before the branch determination of the conditional branch instruction. However, since the branch destination instruction is only put into the pipeline in advance, the branch hazard can be effectively reduced without being restricted by the pipeline configuration, the instruction content, and the like.

[Brief description of drawings]

FIG. 1 is a block diagram showing a basic configuration of a program control device according to first and second embodiments of the present invention.

FIG. 2 is a block diagram showing a specific configuration of a program counter section according to the first embodiment of the present invention.

FIG. 3 is a block diagram showing a specific configuration of a program counter section according to the second embodiment of the present invention.

FIG. 4 is an instruction register according to the first embodiment of the present invention .
FIG. 3 is a block diagram showing a specific configuration of an input unit.

FIG. 5 is an instruction register according to the second embodiment of the present invention .
FIG. 3 is a block diagram showing a specific configuration of an input unit.

FIG. 6 is an instruction flag in the first embodiment of the present invention .
Articles for a four-stage pipeline with two stages
It is a flowchart which shows the control flow of case branch.

FIG. 7 is an instruction flag in the first embodiment of the present invention .
Articles for a four-stage pipeline with two stages
It is a timing diagram which shows the timing of case branch.

FIG. 8 is an instruction flag in the first embodiment of the present invention .
Articles for a 5-stage pipeline with two stages
It is a flowchart which shows the control flow of case branch.

FIG. 9 is an instruction flag in the first embodiment of the present invention .
Articles for a 5-stage pipeline with two stages
It is a timing diagram which shows the timing of case branch.

FIG. 10 is an instruction buffer according to the second embodiment of the present invention .
In case of 6 stage pipeline with 2 stages
It is a flowchart which shows the control flow of a conditional branch.

FIG. 11 is an instruction buffer according to the second embodiment of the present invention .
In case of 6 stage pipeline with 2 stages
It is a timing diagram which shows the timing of a conditional branch.

FIG. 12 shows a conventional instruction fetch stage having two stages.
Shows the timing of conditional branching for a 4-stage pipeline
It is a timing diagram.

[Explanation of symbols]

1 Program counter section 2 memory 3 Instruction register section 4 Branch decision device 5 Decoder section 6 computing unit 11 addresses 12 First instruction code 13 Second instruction code 14 Branch signal 15 branch address 16 Control signal 17 Condition flag signal 101 first program counter 102 address adder 103 address selector 104 second program counter 111 Branch signal for address selector 112 Second program counter branch signal 113 Address selector output 114 address adder output 115 Second program counter output 301 First instruction register 302 Instruction selector 303 Second instruction register 311 First instruction register branch signal 312 Branch signal for instruction selector 314 Instruction register output 315 NOP code

Continuation of front page (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 9/38

Claims (3)

(57) [Claims] 1. An instruction decoding stage and an instruction execution stage
Is composed of a plurality of stages including
Pipeline with two or more stages in front of
An information processing apparatus for processing instructions, wherein the instructions executed by the information processing apparatus are treated as instruction codes.
Instruction code storage means to be stored and instruction code fetched from the instruction code storage means
It based the address and the first address holding means for specifying, to the address where the first address holding means specifies
The instruction code fetched from the instruction code storage means.
A first instruction holding means for storing a code and an instruction code stored in the first instruction holding means
A branch determination means for determining whether or not the instruction is a branch instruction, and an instruction code stored in the first instruction holding means
Decoding means, and calculation based on the decoding result in the decoding means
And the determination result of the branch determining means is the first instruction holding means.
That the instruction code stored in the column is a conditional branch instruction
If so, the branch decision of the conditional branch instruction
First, the subsequent address of the conditional branch instruction is saved.
The address holding means of No. 2 and the judgment result of the branch judging means are the first instruction holding means.
That the instruction code stored in the column is a conditional branch instruction
If so, the branch decision of the conditional branch instruction
Previously, the instruction code subsequent to the conditional branch instruction is saved.
A second instruction holding unit, wherein the determination result of the branch determination unit is the first instruction holding unit.
That the instruction code stored in the column is a conditional branch instruction
If it is shown, the branch destination instruction is preceded by
If the condition of the conditional branch instruction is satisfied, the branch destination instruction is input to the pipeline.
Is executed, and if the condition is not established in the conditional branch instruction, the second A
Wherein the subsequent address that is removing all to dress holding means
Returning to the first address holding means, holding the second instruction
Means for decoding the subsequent instruction code saved in the means
After the conditional branch instruction by decoding by means
An information processing device, characterized in that it executes a subsequent instruction. 2. An instruction decoding stage and an instruction execution stage.
And a plurality of stages including
N (n: integer of 2 or more) stages before the reading stage
Instructions in a pipeline having
The first address register that shows the address of the instruction
Holding means and decoded in the instruction decoding stage
And a first instruction holding means for storing an instruction to store
Second address holding means different from the dress holding means,
Second instruction holding means different from the first instruction holding means
Controls conditional branching in an information processing device including
A program control method, wherein the instructions decoded in the instruction decoding stage are
If it is a conditional branch instruction, the instruction of the conditional branch instruction
Instruction subsequent to the conditional branch instruction in the instruction execution stage
Pipeline information of n + from the conditional branch instruction
The address of the instruction after 1 is sent to the second address holding means.
And the instruction code of the instruction one instruction after the conditional branch instruction
Saves to the second instruction holding means and precedes the branch destination instruction
To the charged into the pipeline, if the conditions are satisfied in the conditional branch instruction, the branch target instruction
As it executes, if the condition is not established in the conditional branch instruction, the second A
From the conditional branch instruction saved to the dress holding means, n
The address of the instruction after +1 is stored in the first address holding means.
And returned to the second instruction holding means.
Decodes the instruction code of the instruction one instruction after the conditional branch instruction
To execute a subsequent instruction of the conditional branch instruction.
A program control method characterized by the following. 3. A plurality of instructions including a first instruction decoding stage.
Multiple stages, including an instruction decoding stage and an instruction execution stage.
And n before the first instruction decoding stage.
Pipeline having (n: integer of 2 or more) stages
Instructions that are processed in the pipeline and input to the pipeline
First address holding means for indicating the address of the
Is decoded at any of the instruction decoding stages of
First instruction holding means for storing an instruction, and the first add
Address holding means different from the address holding means, and
A second instruction holding means different from the first instruction holding means;
A processor for controlling conditional branching in an information processing device equipped with
A program control method, wherein the instructions decoded in the first instruction decoding stage are
If the instruction is a conditional branch instruction, the first instruction decoding
In the next stage of the stage, the conditional branch instruction
The conditional branch instruction is used as pipeline information of the subsequent instruction.
The address of the instruction n + 1 later than the second address
To the holding means, an instruction of an instruction one after the conditional branch instruction
The code is saved to the second instruction holding means, and the branch destination is designated.
Instruction is put into the pipeline in advance, and if the condition of the conditional branch instruction is satisfied, the branch destination instruction
As it executes, if the condition is not established in the conditional branch instruction, the second A
From the conditional branch instruction saved to the dress holding means, n
The address of the instruction after +1 is stored in the first address holding means.
And returned to the second instruction holding means.
Decodes the instruction code of the instruction one instruction after the conditional branch instruction
To execute a subsequent instruction of the conditional branch instruction.
A program control method characterized by the following.