JPH05224927A - Processor - Google Patents

Abstract

(57) [Summary] [Object] The present invention provides a processor that speculatively processes an instruction while a condition corresponding to a conditional branch instruction is not fixed, has a small interlock, and executes a program at high speed. The purpose is to do. The instruction decoding unit 7 determines the type of conditional branch instruction included in the instruction sequence before execution, and the instruction units of the branch destination and the instruction sequence of the branch destination are given to the arithmetic units 8 to 11 according to the determined type of instruction. / Or the instruction of the subsequent instruction sequence is issued in parallel to the execution unit as speculative execution. Arithmetic units 8-11
The result of performing the pottery is temporarily stored in the arithmetic unit management table 12. Instruction execution consistency maintaining circuit 1
When the success or failure of the conditional branch instruction is judged by 8,
The execution order management circuit 17 identifies whether the execution result of the instruction sequence is valid or invalid, stores the valid execution result in the register file 19, and invalidates the invalid execution result.
Erase from 3.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to high-speed processing of conditional branch instructions in a processor having a plurality of arithmetic processing units capable of parallel execution.

[0002]

2. Description of the Related Art In recent years, high performance processors
A method of preparing multiple arithmetic units called perscalar or VLIW and executing multiple instructions at once in parallel has come to be adopted. Microcomputers such as the MC88100 manufactured by MOTOROLA are known as those commercialized by these methods (the MC88100 MICROPROCESSOR U manufactured by MOTOROLA).
SER'S MANUAL SECOND EDITION ").
By using these methods, it becomes possible for an instruction sequence that has been conventionally executed sequentially to execute a plurality of instructions at once.

Regarding the order of execution of the instructions, the instructions are not executed in the order in which the instruction strings are arranged, but the instructions having no data dependency are executed from the executable one, that is,
A speed-up method called out-of-order execution is also known. For information on these speed-up techniques, see IEICE Technical Report CPSY-90-54 ('90.
7) "Improvement policy of superscalar processor based on SIMP (single instruction stream / multiple instruction pipeline) method"
(`` An Extended Superscalar Processor Prototype Ba
sed on the SIMP (Sngle Instruction stream / Multipl
e instruction Pipelining) Architecture ").

The processor of the prior art described above predicts which branch the conditional branch instruction will branch to, and executes the instruction in advance (called speculative execution) even if the branch of the conditional branch instruction is not fixed. It was trying to speed up. The prediction method includes, for example, predicting that the same conditional branch instruction that has appeared previously will branch to the same side as the previous one.

[0005]

However, according to the above conventional technique, there are the following problems. Generally, when a plurality of instructions are executed simultaneously, the frequency of occurrence of branch instructions per processing cycle increases. In the case of a conditional branch instruction, the condition is fixed (usually PS
It cannot be decided whether or not to branch until R: Program Status Register is changed). For this reason, the instruction flow is interlocked for each conditional branch instruction, and the performance reaches a level. (The dependency relationship due to these branches is called control dependence.) In addition, in the method of predicting whether to branch or not and processing the instruction in advance (called speculative execution), the prediction is performed for each conditional branch instruction. When hits, the speedup is achieved, but when the prediction is wrong, the instruction sequence is returned to the other instruction sequence and the instruction is re-executed. Furthermore, speeding up of execution of the entire program is not always achieved.

An object of the present invention is to provide a processor which speculatively processes an instruction even if the condition corresponding to the conditional branch instruction is not fixed, has a small interlock, and executes a program at high speed. ..

[0007]

In order to solve the above problems, a processor of the present invention is a processor which has a plurality of execution units and which processes instructions of an instruction sequence in a memory in parallel. Of the conditional branch instruction included in the instruction sequence of No. 1, which determines the type of the conditional branch instruction whose condition depends on another instruction, and the execution depending on the type of the conditional branch instruction until the success or failure of the branch is determined. An instruction parallel issue means for issuing a branch destination instruction sequence and / or a subsequent instruction sequence instruction to the execution unit in parallel to the unit, and a condition when another instruction on which the conditional branch depends is executed. A branch determination unit that determines whether or not the branch of the branch instruction is successful, and an execution result management unit that determines whether the execution result of the instruction sequence is valid or invalid based on the result of the success or failure of the branch of the conditional branch instruction.

The instruction type discriminating means discriminates between a first type instruction whose branch probability is about the same as a non-branch probability and a branch instruction other than that, and the instruction issuing parallel means
When the conditional branch instruction is the first type instruction, both the branch target instruction sequence and the instruction sequence subsequent to the conditional branch instruction are issued in parallel to the execution unit, and the conditional branch instruction is the first type instruction. If the instruction is an instruction other than the instruction, one of them is issued in parallel to the execution unit, and the execution result management means determines whether or not the branch is successful if the conditional branch instruction is the instruction of the first type. According to the decision result of the success or failure of the branch, if the conditional branch instruction is other than the instruction of the first type, all the execution results of the instruction sequence are made valid while the execution result of one instruction sequence is made valid and the other is invalidated. May be enabled or disabled.

The instruction type discrimination means has a high probability of branching an instruction other than the first branch instruction from the first branch instruction and a second branch instruction having a higher probability of branching than the first branch instruction. In the case of the second type instruction, the instruction parallel issue means issues the instruction of the branch destination instruction sequence in parallel to the execution unit, and determines the third type instruction. In this case, the instruction of the instruction sequence following the conditional branch instruction may be issued in parallel to the execution unit.

The processor further temporarily stores a first instruction fetch buffer for temporarily storing an instruction of an instruction sequence subsequent to the conditional branch instruction and an instruction of an instruction sequence of a branch destination of the conditional branch instruction. The second instruction fetch buffer and the instruction stored in the memory are read, and the first and second instructions are fetched.
And an instruction fetch means for storing the instruction in the instruction fetch buffer.

The instruction fetch means outputs a read address to the memory and increments the contents of the program counter, a conditional branch instruction detecting means for detecting a conditional branch instruction from the instruction read from the memory, and a conditional branch instruction. A first instruction fetch unit that calculates the address of the branch destination based on the conditional branch instruction detected by the detection unit, and normally increments the contents of the program counter each time the instruction is read from the memory. When an instruction is stored in the buffer and a conditional branch instruction is detected, the instruction of the subsequent instruction sequence is stored in the first instruction fetch buffer, the branch destination address obtained by the calculating means is written in the program counter, and the branch destination is written. And a fetch control means for storing the instructions of the instruction sequence in the second instruction fetch buffer. .

The instruction parallel issuing means decodes the instructions and generates a control signal to the execution unit, and one instruction from the first or second instruction fetch buffer to all the decoding means. Transfer control means for transferring each instruction, and to each instruction transferred by the transfer control means, a mode indicating which instruction sequence the instruction belongs to is added, and an instruction sequence subsequent to the branch instruction and a branch destination instruction. It may have a mode adding means for changing the mode depending on the row.

The mode added by the mode adding means is:
This is 2-bit information, and the mode of the instruction sequence following the conditional branch instruction is the value obtained by adding the first value to the mode of the conditional branch instruction itself, and the mode of the instruction sequence of the branch destination is It may be a value obtained by adding the second value. The other instruction on which the conditional branch instruction depends is an instruction that changes the PSR (Program Status Register), and the branch determination means detects that the instruction that changes the PSR has been executed and refers to the execution result. It may be configured to do so.

The processor further refers to a plurality of decryption results decrypted by the decryption means to determine a data dependency relationship between a plurality of decrypted instructions, and a data dependency relationship determining means. Regarding the scoreboard management means for managing which register is used by the instruction being executed in the unit, the empty state detecting means for detecting the empty state of the execution unit, and each instruction decoded by the decoding means , Permitting issuance of an issuable instruction from the instruction parallel issuance means to the execution unit based on the determination result of the data dependency determination means, the scoreboard management means, and the detection result of the empty state detection means, and When the instruction decoded by the decoding means is a conditional branch instruction, it may have an instruction issue permission means for permitting the instruction parallel issue means to issue to the branch determination means.

The instruction issue permitting means has no data dependency relation with the preceding instruction from the detection result of the data dependence detecting means for each of the decoding results of the plurality of decoding means, and the information of the scoreboard managing means is used. It is satisfied that the register specified by the operand of the instruction is not used for the instruction being executed by the execution unit, and the execution unit that can execute the instruction is free from the detection result of the free state detection means. 10. The processor according to claim 9, wherein the processor determines that the instruction can be issued.

The processor further holds information indicating whether or not an instruction is being executed for each execution unit, and the execution unit management table referred to by the empty state detecting means.
And the information indicating which register is used by the instruction being executed in the execution unit.
A scoreboard referred to by the card management means may be provided.

The execution result managing means initializes the mode of the conditional branch instruction issued by the instruction parallel issuing means.
Initial mode holding means for holding as a mode, speculative execution type holding means for holding the type of conditional branch instruction issued by the instruction parallel issuing means, and condition judgment of the conditional branch instruction issued by the instruction parallel issuing means. The instruction parallel issuing means issues a conditional branch instruction to the branch determining means, and at the same time, the speculative execution state instruction means for holding a flag indicating that the conditional branch instruction is not determined. The initial mode holding means may output the type of the conditional branch instruction to the speculative execution type holding means and set the flag of the speculative execution state instructing means.

As described above, the execution result management means temporarily stores the execution result of the instruction in the execution unit, the mode of the instruction, and the information of the storage destination where the execution result is originally stored. You may have a memory | storage means. The temporary storage means is configured to store, as the storage destination information, a register number when the original storage destination is a register and a memory address when the original storage destination is a memory. May be.

The branch judging means clears the flag of the speculative execution state instructing means when judging whether or not to branch, and the execution result managing means, based on the judgment result of the branch judging means, holds the initial mode holding means, The speculative execution type holding means may be referred to to identify whether the execution result of the temporary storage means is valid or invalid, transfer the valid execution result to the original storage destination, and clear the invalid execution result. ..

[0020]

With the above means, the processor of the present invention determines the type of the conditional branch instruction included in the instruction sequence before execution by the instruction type determining means. Depending on the type of the determined instruction, the instruction parallel issue unit issues the instruction of the branch destination instruction sequence and / or the instruction of the subsequent instruction sequence to the execution unit in parallel to the execution unit. When the branch determination means determines whether or not the branch of the conditional branch instruction is successful, the execution result management means identifies whether the execution result of the instruction sequence is valid or invalid.

Further, the instruction type managing means discriminates between the first type of instructions whose branching probability is about the same as the probability of not branching and the other instructions. For other instructions, a second type of branch instruction that has a higher probability of branching than the first type of branch instruction and a third type of branch instruction that has a higher probability of not branching than the first type of branch instruction. Determine. The instruction fetch unit stores the instructions from the normal memory into the first instruction fetch unit, and when the conditional branch instruction detection unit detects the conditional branch instruction, the instruction of the instruction sequence subsequent to the conditional branch instruction is the first instruction. The instruction of the branch destination instruction string is stored in the second instruction fetch buffer in the second instruction fetch buffer. With respect to the instructions stored in these instruction fetch buffers, the instruction parallel issuing means adds the mode by the mode adding means, and at the same time, the transfer control means instructs the plurality of decoding means from the two instruction fetch buffers. Take in.

Further, the command issuance permitting means is based on the judgment result of the data dependency judging means, the scoreboard managing means, and the detection result of the empty state detecting means for each instruction decoded by the plurality of decoding means. Issuance of an issuable instruction from the instruction parallel issuance means to the execution unit, and when the instruction decoded by the decoding means is a conditional branch instruction, the instruction parallel issuance means issues to the branch determination means. Allow At this time, when the conditional branch instruction is the first type of instruction, the instruction issuance enabling means permits both the branch destination instruction string and the instruction string subsequent to the conditional branch instruction to be issued in parallel to the execution unit. In the case of the second type instruction, the instruction of the branch destination instruction string is issued in parallel to the execution unit, and in the case of the third type instruction, the instruction string instruction subsequent to the conditional branch instruction is executed. Allow parallel issuance.

The instruction parallel issuing means issues a conditional branch instruction to the branch judging means, and at the same time, the mode of the conditional branch instruction is held in the initial mode holding means, and the kind of the conditional branch instruction is held as the speculative execution kind. And outputs the flag to the speculative execution state instructing means. When the branch determination means determines whether or not to branch, the execution result management means refers to the initial mode holding means and the speculative execution type holding means on the basis of the result of the determination to determine the execution result of the temporary storage means. It identifies valid / invalid, transfers the valid execution result to the original storage destination, and clears the invalid execution result.

[0024]

1 is a block diagram of a processor of the present invention.
In FIG. 1, reference numeral 1 denotes a memory, which stores an instruction string and operand data which form a program. An instruction fetch unit 2 prefetches instructions from the memory 1 and stores them in the instruction fetch buffer A3 or the instruction fetch buffer B.
Write to 4. The instruction fetch unit 2 detects whether the fetched instruction is a conditional branch instruction, and switches the write destination instruction fetch buffer according to the detection result.

The branch instruction detected by the instruction fetch unit 2 will be described. For example, programming language C
If, it is generally uncertain whether to branch or not.
-Then-else system, the case of a loop with a high probability of branching, and the case of a high probability of not branching.
In case of switch statement, it depends on the implementation method, but if-then-
Think of it like else. Therefore, in this embodiment, depending on the probability of branching in advance, a loop-type branch instruction that operates at high speed when the probability of branching is high, and if-then that operates at high speed when the probability of branching is unknown. -else branch instructions,
Three types of branch instructions that operate at high speed when the probability of not branching are high are provided in the machine language instruction. A loop-type branch instruction is an instruction with a high probability of branching with a loop-oriented branch instruction (hereinafter abbreviated as Bcc_l), and whether or not the if-then-else type branch instruction branches. It is a definite branch instruction (hereinafter abbreviated as Bcc_i). In addition, there is an instruction that has a high probability of not branching (hereinafter abbreviated as Bcc_n).

When a branch instruction is detected by the instruction fetch unit 2, an instruction string following the branch instruction (an instruction string executed when the branch is not executed) and a branch destination instruction string (an instruction string executed when the branch is executed) ) Is read, and the instruction sequence following the branch instruction is stored in the same instruction fetch buffer as before.
The branch destination instruction string is stored in another instruction fetch buffer. This read operation always fills the instruction fetch buffer A3 or the instruction fetch buffer B4 asynchronously with the decoding and execution of the instruction.

The instruction fetch buffer A3 stores the instructions read by the instruction fetch unit 2 in a FIFO (First In F
irst Out) Memory. Instruction fetch buffer B4
Is a FIFO memory, like 3. Reference numeral 5 is a selector, which switches the instructions output from the two instruction fetch buffers. The switching instruction is given by the instruction decoding unit 7.

Reference numeral 6 denotes an instruction decoding buffer, which stores an instruction to be decoded and has a storage capacity of 6 instructions in this embodiment. It is desirable that the storage capacity is at least equal to or larger than that of the arithmetic units 8 to 11. Instruction decoding unit 7
Controls the transfer of instructions from the instruction fetch buffer to the instruction decoding buffer 6, decodes the instruction in the instruction decoding buffer, and issues the instruction to the arithmetic unit.

Reference numeral 8 denotes an arithmetic unit A, which executes a load instruction and a store instruction, and it is assumed that the execution of the load instruction takes two cycles for convenience of explanation. An arithmetic unit B 9 processes integer arithmetic. An arithmetic unit C 10 processes integer arithmetic. An arithmetic unit D 11 processes a floating point arithmetic. Arithmetic unit A
In this embodiment, 8 to D11 are assumed to complete the instruction execution in one cycle (the load instruction is two cycles) in order to simplify the description. Further, the number of pipeline stages of the unit is not defined here because it is not related to the gist of the present invention.

Reference numeral 12 is an arithmetic unit management table,
Information (bit) indicating that it is in use is stored for each arithmetic unit. This bit is set by each arithmetic unit at the start of instruction execution of the arithmetic unit and cleared at the end of instruction execution of the arithmetic unit. An execution order management buffer 13 stores the operation result of speculatively executed instructions, the register number in which the result should be originally stored, and the mode of the instruction. The storage format of the execution order management buffer 13 has an area for storing the mode, the register number, and the operation result, as shown in FIG.

An initial mode holding circuit 14 holds the mode added to the branch instruction processed by the instruction decoding unit as an initial mode. A speculative execution type holding circuit 15 holds the type of branch instruction currently being executed (whether it is Bcc-l or Bcc-i). Reference numeral 16 is a speculative execution state instruction circuit, which holds a flag indicating whether or not the speculative execution state is currently being executed.

Reference numeral 17 denotes an execution order management circuit, which is the above-mentioned 14
16 to 16 depending on the information obtained from
The calculation result of 1 is stored in the register file 19 or the execution order management buffer 13. Specifically, when the speculative execution is not in progress, the calculation result is written to the register file. When the speculative execution is in progress, the mode and the register number of the operation result (operand) write destination are associated with the speculative execution instruction. And stores it in the execution order management buffer 13.
When the speculative execution is completed, the operation result is transferred to the register file based on the operation result and the register number stored in the execution order management buffer.

Reference numeral 18 denotes an instruction execution consistency maintaining circuit, P
Whether the condition of the conditional branch instruction is satisfied or not is determined from the SR determination result, and the instruction decoding unit 7 is instructed to redo the instruction execution, the execution order management buffer 13 is invalidated,
The execution order management circuit 17 issues a transfer instruction. More specifically, the following cases are classified according to the type of conditional branch instruction.

(1) When speculative execution is performed for the Bcc-l instruction, only the instruction at the branch destination is executed. Therefore, when it is determined from the definite result that the branch does not occur, the instruction previously executed is executed. The result is deleted from the execution order management buffer, and the instruction decoding unit is instructed to execute the instruction on the side that does not branch again. (2) When speculative execution is performed for the Bcc-i instruction, the branch destination instruction and the subsequent instruction are executed. Therefore, when the branch direction is determined, the subsequent instruction or the branch destination is accordingly The result of the instruction is deleted from the execution order management buffer.

(3) When speculative execution is performed for the Bcc-n instruction, only the instruction subsequent to the branch instruction is executed. Therefore, when it is found from the definite result that the branch is made, the branch instruction is executed first. The instruction decoding unit is instructed to erase the result of the executed instruction from the execution order management buffer and execute the branching side instruction again. Reference numeral 19 is a register file, which has 32 registers and PSR, and stores the execution result of the instruction.

Reference numeral 20 is a score board, which has a 2-bit flag for each register of the register file 19.
One is that an instruction being executed which is not speculative execution uses (reads or writes) the corresponding register.
The other indicates that the instruction being executed by speculative execution uses the corresponding register. FIG. 2 is a block diagram showing a detailed configuration of the instruction fetch unit 2 of FIG. In the figure, 21 is a program counter, which is a memory 1
The address of the instruction to be read from is output, and the content is incremented each time the instruction is read.

Reference numeral 22 denotes a branch instruction detection circuit, which is a memory 1
The conditional branch instruction is detected from the instruction read from. Two
An arithmetic circuit 3 calculates a branch destination address based on the detected conditional branch instruction. 24 is a selector,
The outputs of the program counter 21 and the arithmetic circuit 23 are selected and output to the memory 1.

Reference numeral 25 is a fetch control unit, which reads instructions from the memory 1 and the instruction fetch buffer A3.
Alternatively, the instruction writing to the instruction fetch buffer B4 is controlled. In detail, it is usually the program counter 2
Control is performed so that the address is sequentially output while 1 is incremented, and the instruction is stored in one of the instruction fetch buffers. When the branch instruction detection circuit 22 detects a conditional branch instruction, the information of the branch destination address of the conditional branch instruction is input to the arithmetic circuit 23 to calculate the branch destination address so that the branch destination instruction can be read. Control and store the instruction in the other instruction fetch buffer.

FIG. 3 is a block diagram showing a detailed structure of the instruction decoding unit 7 of FIG. In the figure, 31 is a branch instruction detection circuit, which detects branch instructions (Bcc_l instruction and Bcc_i instruction from the output of the selector 5 in FIG. 1. 32 is a transfer control circuit, which is the instruction fetch buffer A3 or the instruction fetch buffer B4. Is transferred to the instruction decoding buffer 6 via the selector 5. The operation of this transfer differs depending on the detection result of the branch instruction detection circuit 31.

First, when the branch instruction is not detected, the transfer control circuit 32 causes the selector 5 to select the output of the instruction fetch buffer A3 or the instruction fetch buffer B4 which contains the instruction. Then, the instruction is transferred to the instruction decoding buffer 6. Second, when a Bcc_l type instruction (a branch instruction for a loop and a high probability of branching) is detected, the instruction fetch buffer that is currently reading the instruction is switched to the other instruction fetch buffer, and the instruction decoding buffer is switched. Transfer the instruction to. Only the instruction at the branch destination is transferred to the instruction decoding buffer 6.

Thirdly, when a Bcc_i type instruction (if-then-else type branch instruction, the branch probability is uncertain) is detected,
Alternately transfer instruction reads from the currently used instruction fetch buffer and the other instruction fetch buffer.
A subsequent instruction (an instruction executed when a branch is not performed) and a branch destination instruction are mixed (alternately) transferred to the instruction fetch buffer.

Fourthly, when a Bcc_n type instruction (which has a high probability of not branching) is detected, the instruction is continuously transferred from the instruction fetch buffer which is currently reading the instruction to the instruction decoding buffer. Only the instruction on the non-branching side is transferred to the instruction decoding buffer 6. A mode addition circuit 33 adds a mode to each instruction and stores it in the instruction decoding buffer 6 so that the control flow of the instruction by the branch instruction can be understood during the above transfer by the transfer control circuit 32.

This mode setting rule is as follows: (1) In the mode of the instruction sequence following the branch instruction, "+01" is added to the current mode. (2) The mode of the instruction sequence at the branch destination is "+" in the current mode.
10 "is added.

FIG. 4 is a mode explanatory diagram showing an example of the flow of modes and instructions. In the figure, a solid arrow (↓) indicates an instruction string, a circle (○) indicates a conditional branch instruction, and a broken arrow () indicates a loop return destination (Bcc_l instruction branch destination).
The numbers in "" indicate the mode. Circled numbers (,,) are the number of times the loop is repeated (repeated three times in FIG. 2).

For example, the mode of the current instruction sequence is "00".
Then, the mode of the instruction sequence following the branch instruction is “+0
"1" is added by 1 ", and the mode of the instruction sequence at the branch destination is"
It is set as "10" by adding +10 ".
In the loop processing, the mode changes each time the loop is repeated because the mode is set relatively.

If this mode setting rule is used, it is possible to easily discriminate the instruction sequence up to the branch instruction, the subsequent instruction sequence, and the instruction sequence of the branch destination. It is possible to discriminate the control flow even when branching. 34 is an instruction decoding circuit, which is a decoder 3
4a to 34f, and simultaneously decodes 6 instructions input from the instruction decoding buffer 6 of FIG. The number of DEC is
Here, the number is the same as the number of stages of the instruction decoding buffer 6, and it is desirable that the number is equal to or more than that of the arithmetic units 8 to 11.

Reference numeral 35 is a PSR change instruction detection circuit, which receives the decoding results of the decoders 34a to 34f and detects whether or not each instruction changes the contents of the PSR (Program Status Register). When the content of the PSR is determined, the success or failure of the condition of the conditional branch instruction is determined, and the detection result is notified to the instruction execution consistency maintaining circuit 18. 36
Is a data dependency detection circuit, and the decoders 34a to 34a
Based on the decoding result input from 4f, it is detected whether or not there is a data dependency relationship that the execution result of one instruction is used by another instruction. Specifically, the data dependency relationship detection circuit 36 compares the decoded decoded register fields of the six decoded instructions, and the execution register of the previous instruction has the execution address of the previous instruction. , The source register is determined to have a data dependency relationship.

Regarding the range for checking the data dependency,
The data dependency between the instruction in the instruction decoding buffer 6 and the instruction not yet fetched in the instruction decoding buffer 6 is as follows.
No need to look up. The former and latter instructions are never executed at the same time. Only for the instructions in the instruction decoding buffer 6, the data dependency may be checked. This is because they can be executed simultaneously. However, even if the instruction is in the instruction decoding buffer 6, as shown in Table 1, the instruction between the instruction (B) in the instruction sequence of the branch destination and the instruction (c) in the instruction sequence subsequent to the branch instruction is -Data dependency is not checked. This is because (B) and (C) have an exclusive relationship. Table 1 shows the presence / absence of the check of the data dependency of the instruction sequence in the embodiment of the present invention.

[0049]

[Table 1]

Reference numeral 37 is a scoreboard management circuit, which refers to the scoreboard 20 to judge the status of the register used in the execution of the instruction, and the decoders 34a to 34f.
If there is an instruction to change the contents of the register by looking at the result of decoding, the flag of the scoreboard 20 corresponding to the register is set. An empty state detection circuit 38 refers to the arithmetic unit management table 12 and determines which arithmetic unit is empty (not in use). .

Reference numeral 39 is an instruction issuing circuit, which is a selector 39.
a-39d, according to the instruction of the instruction issue control circuit 40, select an issuable instruction among the instructions decoded by the instruction decoding circuit 34 and issue it in parallel to the arithmetic units 8-11. At the same time, the instruction issuing circuit 39 stores, for each instruction to be issued, an identifier indicating whether it is speculative execution in the arithmetic unit. In this embodiment, this identifier is "0" to indicate that the speculative execution is not in progress, and "1" to indicate that the speculative execution is in progress.

The instruction issue control circuit 40 uses the above 36 to 38.
Based on the information obtained from the above, the issuable instruction is discriminated among the instructions decoded by the instruction decoding circuit 34, and an instruction to issue is issued to the instruction issuing circuit 39. Whether or not the instruction is an issuable instruction, the following conditions are checked for each instruction, and it is determined that an instruction that satisfies all the conditions can be issued. Between the 6 instructions, there is no data dependency with the previous instruction. (Check based on the detection result of the data dependency detection circuit 36.) The register specified by the operand of the instruction is not used for the instruction being executed in the arithmetic unit.
(Check based on the information from the scoreboard management circuit 37.) The operation unit that can execute the instruction is free. (Check based on the detection result of the empty state detection circuit 38.) Further, at the same time as the instruction issuance, the instruction issuance control circuit 40
The issued instruction is deleted from the instruction decoding buffer 6 and the corresponding bit in the arithmetic unit management table 12 is set (in use).

When the instruction that can be issued is a conditional branch instruction, the instruction is not issued to the arithmetic unit, the mode of the branch instruction is sent to the initial mode holding circuit 14, and the speculation execution type holding circuit 15 is set to Bcc-i. An instruction, a Bcc-l instruction, or a Bcc-n instruction is provided to the speculative execution state instruction circuit 16 with a flag indicating that speculative execution is in progress, and the instruction execution consistency maintaining circuit 18 is provided with a condition of the instruction. set. In this case, the speculative execution state is set thereafter.

With respect to the branch processing device in the embodiment of the present invention configured as described above, the operation will be described with reference to FIGS. 5 to 9 and Table 2 in the case where the Bcc-i instruction is included first. FIG. 5 is an example of an instruction flow for explaining the operation of this embodiment for processing a Bcc-i instruction at high speed.
In FIG. 5, the arrow indicates the instruction execution order, and the instruction N-3
The arrow between and the instruction N-2 indicates that there is a data dependency, LD in () indicates a load instruction, INT indicates an integer operation instruction, and FPU indicates a floating point operation instruction. Command N-2
Is an instruction that changes the PSR that is the basis of the branch instruction.

First, the operation of the instruction fetch unit 2 will be described. The instruction fetch unit 2 operates asynchronously with the processing following the instruction decoding. The instruction fetch unit 2 reads an instruction from the memory 1 using the program counter 21,
Store in the instruction fetch buffer A3. When the branch instruction detection circuit 22 detects a branch instruction at the time of reading from the memory 1, the instruction subsequent to the branch instruction is stored in the instruction fetch buffer A3, and the arithmetic circuit 23 calculates the branch destination address to calculate the branch destination address. The instruction is stored in another instruction fetch buffer B4.

The operation of the instruction fetch unit 2 is continued until one of the instruction fetch buffers is full when there is no branch instruction, or until both instruction fetch buffers are full when there is a branch instruction. Be done. The instruction fetch buffer A3 and the instruction fetch buffer B4 are equivalent, and either one may be used first. In the following description, it is assumed that the instruction fetch buffer is always full.

In FIG. 5, the instructions executed before the instruction N-3 are irrelevant to the description of the present invention and will not be described. Further, the instruction fetch unit 2 stores the instruction sequence up to the branch instruction and the instruction sequence subsequent to the branch instruction in the instruction sequence of FIG. 3 in the sequential instruction fetch buffer A3, and the branch destination instruction sequence in the instruction fetch buffer B4. It is stored. Hereinafter, description will be made step by step.

(1) The instruction decoding unit 7 reads an instruction from the instruction fetch buffer A3, adds a mode to the instruction, and stores it in the instruction decoding buffer 6. The instructions from N-3 to N + 2 in FIG. 6 stored in the instruction fetch buffer A3 are read by the instruction decoding unit 7 and the mode "
00 "is added and stored in the instruction decoding buffer 6.
The contents held in the instruction decoding buffer 6 at this point are shown in FIG.

(2) In the instruction decoding unit 7, the data dependency detecting circuit 36 checks the data dependency between instructions, the scoreboard management circuit 37 checks the register in use, and the empty state detecting circuit 38 The computing unit management table 12 determines the availability of the computing unit. Based on these results, the instruction issuance control circuit 40 determines an issuable instruction, causes the instruction issuance circuit 39 to issue an instruction with an identifier indicating whether it is speculative execution, and decodes the instruction. Delete from buffer 6.

In FIG. 6, instruction N-2 is instruction N-3.
Since it has a data dependency with, it is not issued at first. N-
Four of 3, N-1, N, N + 1 are issued. Since it is not speculative execution, the identifier of each instruction is "0". The state of the arithmetic unit after issuing these instructions is shown in the first line of Table 2. When an instruction is input, each arithmetic unit sets the corresponding bit of the arithmetic unit management table 12.
Table 2 shows the situation of instruction execution in the arithmetic unit when the instruction flow of FIG. 5 is executed.

[0061]

[Table 2]

(3) The operation unit outputs the operation result to the execution order management circuit 17 after executing the instruction. Since it is not a speculatively executing instruction (the identifier is 0), the execution order management circuit directly writes the operation result to the register file 19. Usually, the instruction sequence without branch instructions is (1)-
It is executed as in (3). (4) The instruction decoding buffer 6 has the instruction N-2 in FIG.
And the instruction N + 2 remains. Instruction decoding unit 7
The transfer control circuit 32 reads the new instruction from the instruction fetch buffer A3 in sequence and stores it in the instruction decoding buffer 6. At this time, when the branch instruction detection circuit 31 detects that the instruction read is the Bcc_i instruction, the transfer control circuit 3
2 alternately reads the instruction following the branch instruction from the instruction fetch buffer A3 (the instruction to be executed subsequently when no branch occurs) and the branch destination instruction from the instruction fetch buffer B4 alternately by switching the selector 5 Store in decryption buffer. At the same time, the mode addition circuit 33 sets the current mode to "00" to indicate whether the instruction is a branch target instruction, and sets "+01" to the subsequent instruction.
Is added and "01" is added to the branch destination instruction, and "+10" is added to the branch destination instruction to set it as "10". Then, the instruction decoding buffer stores the instruction as shown in FIG.

(5) The instruction decoding unit 7 determines an issuable instruction in the same manner as described in (2). Of the instructions issued in the previous cycle, the instruction N-3 issued to the arithmetic unit A8 is a load instruction that takes two cycles, so its execution has not been completed yet. Therefore, the issue of the instruction N-2, which has a data dependency relationship with this instruction, is delayed by another cycle. In this processing cycle, instructions N + 2, Bcc_i,
It is determined that the instruction N + 3 and the instruction M can be issued. The instruction issue control circuit 40 sends the instruction N + 2 to the arithmetic unit D11, the Bcc_i instruction to the instruction execution consistency maintaining circuit 18, and the instruction N + 3 to the arithmetic unit B via the instruction issue circuit 39.
9, the instruction M is issued to the arithmetic unit C10 with an identifier added, and is deleted from the instruction decoding buffer 6. The identifiers added to these commands are 0,
0, 1, 1. The state of each arithmetic unit after the instruction is issued is shown in the second line of Table 2. Each issued instruction is
-1) to (6-4) are executed.

(6-1) The operation unit D11 sends the instruction N
When +2 is issued, the corresponding bit in the arithmetic unit management table 12 is set and the instruction is executed. When the execution of the instruction is completed in the arithmetic unit D11, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since the instruction N + 2 is not executed in the speculative execution mode (the identifier is 0), the execution order management circuit 17 does not store the operation result in the execution order management buffer 13 but writes it in the register file 19. (6-2) The Bcc-i instruction is not issued to the arithmetic unit, and the instruction issue control circuit 40 causes the initial mode holding circuit 14 to hold the mode "00" of the branch instruction itself and hold the speculative execution type. The flag indicating that the Bcc-i instruction is the circuit 15 is set in the speculative execution state instruction circuit 16 and the condition of the instruction is set in the instruction execution consistency maintaining circuit 18. After this, the speculative execution state is entered.

(6-3) The operation unit B9 sends the instruction N +
When 3 is issued, the corresponding bit in the arithmetic unit management table 12 is set and the instruction is executed. When the execution of the instruction is completed in the arithmetic unit B9, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since this instruction is a speculatively executed instruction (identifier is 1), the execution order management circuit 17 writes the register number of the write destination to the execution order management buffer 13 and the mode "01".
Write. (6-4) When the instruction M is issued, the arithmetic unit C10 sets the corresponding bit in the arithmetic unit management table 12 and executes the instruction. When the execution of the instruction is completed in the arithmetic unit B9, the execution result is the execution order management circuit 17
Is output to. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since this instruction is an instruction under speculative execution (the identifier is 1), the execution order management circuit 17 writes the register number of the write destination to the execution order management buffer 13 and the mode "10".
Write. (7) At this point, the execution order management buffer 13 is stacked up to the second line in FIG.

(8) The instruction decoding buffer is as shown in FIG. In the next cycle, since the instruction N-3 is completed, the instruction decoding unit 7 performs a series of processes and then the instruction N-2,
Issues N + 4 and M + 1. The state of each arithmetic unit after the instruction is issued is shown in the third line of Table 2. When the execution of these instructions is completed, the execution order management buffer 13 is stacked up to the fourth line in FIG.

(9) As described above, the arithmetic unit executes the input instruction and clears the corresponding bit of the arithmetic unit management table 12 when a new instruction can be processed. When the instruction decoding unit 7 can process a new instruction, it restarts the instruction issuing process. (10) The instruction N-2 for changing the PSR is executed by the arithmetic unit B as shown in the third line of Table 2. When the instruction N-2 is completed and the PSR is confirmed, the arithmetic unit B clears the flag of the speculative execution state instruction circuit 16. Even if the instruction N-2 is completed, the speculative execution is executed up to the fourth line in Table 2, and the execution-order management buffer 13 registers the speculatively executed command up to the sixth line in FIG.

(11) The instruction execution consistency maintaining circuit 18
Since the flag of the speculative execution state instruction circuit 16 has been cleared, the speculative execution type holding circuit 15 determines whether or not to branch based on the Bcc_i instruction and the value of PSR. In this example it is assumed that there is a branch. Since the instruction execution consistency maintaining circuit 18 is a Bcc_i instruction, the operation result of the subsequent instruction sequence (instruction sequence on the non-branching side) in the execution order management buffer 13 is not necessary anymore, so that the initial mode holding circuit 14 "+01" is added to the initial mode "00" to invalidate the operation result of the instruction whose mode is "01". In FIG. 9, the instructions N + 3, N + 4, N + 5 are invalidated (cleared). Further, the instruction decoding unit 7 is notified of branching, and only the instruction at the branch destination is fetched into the instruction decoding buffer 6 thereafter.

(12) The execution order management circuit 17 is notified by the instruction execution consistency maintaining circuit 18 that the branch has been decided and the speculative execution mode has ended. Then, with respect to the branch destination instruction string (instruction whose mode is “10”) existing in the execution order management buffer 13, the operation result is stored in the register of the corresponding register file 19. As described above, the processing performed by the speculative execution in the case of the conditional branch instruction Bcc_i is the processing after the branch is confirmed,
Maintains continuity. Moreover, about half of the speculative execution result is valid, and therefore the processing is performed at a high speed.

Then, in the case of including the Bcc-l instruction,
The operation will be described with reference to FIGS. 10 to 14 and Table 3. FIG. 10 is an example of an instruction flow for explaining the operation of the present embodiment for processing the Bcc_l instruction at high speed. The instruction execution order is as shown by the arrow. Also, instruction N + 4 and instruction N + 7
And have a data dependency. The instruction N + 7 is an instruction for changing the PSR that is the basis of the branch determination of the conditional branch instruction. In the figure, there is an instruction executed up to the instruction N, but since it is not related to the description of the present invention, the description will not be added. Further, the instruction fetch unit 2 stores the instruction sequence up to the branch instruction and the subsequent instruction sequence in the instruction sequence of FIG. 10 sequentially in the instruction fetch buffer A3, and the branch destination instruction sequence in the instruction fetch buffer B4. ing. Hereinafter, the steps will be described in order.

(1) The instruction decoding unit 7 reads an instruction from the instruction fetch buffer A3, adds a mode to the instruction, and stores it in the instruction decoding buffer 6. The stored instruction mode is “01”. Now, the instruction decoding buffer 6 is shown in FIG.
It is assumed that the state is 1. (2) In the instruction decoding unit 7, the data dependency detection circuit 36 checks the data dependency between instructions, the scoreboard management circuit 37 checks the register in use, and the empty state detection circuit 38 manages the arithmetic unit. The availability of the arithmetic unit is determined from the table 12. Based on these results, the instruction issuance control circuit 40 determines an issuable instruction, causes the instruction issuance circuit 39 to issue an instruction with an identifier indicating whether it is speculative execution, and decodes the instruction. Delete from buffer 6.

In FIG. 11, the instruction N + 7 is the instruction N +
It is not issued at first because it has a data dependency relationship with 4. N
Four of +4, N + 5, N + 6 and N + 8 are issued. Since it is not speculative execution, the identifier of each instruction is "0". The state of the arithmetic unit after issuing these instructions is shown in the first row of Table 3. Table 3 shows the situation of instruction execution in the arithmetic unit when the instruction flow of FIG. 8 in the embodiment is executed.

[0076]

[Table 3]

When an instruction is input to each arithmetic unit,
The corresponding bit in the arithmetic unit management table 12 is set. After executing the instruction, the operation unit outputs the operation result to the execution order management circuit 17. Since the instruction is not speculatively executing (the identifier is 0), the execution order management circuit 17 directly writes the calculation result to the register file 19.

(3) The instruction decoding buffer 6 is in a state where the instruction N + 7 and the instruction Bcc_l remain in FIG. The transfer control circuit 32 of the instruction decoding unit 7 reads a new instruction sequence from the instruction fetch buffer A3. When it detects that the read instruction is a Bcc_l instruction, the selector 5
, And only the branch destination instruction is read from the instruction fetch buffer B4 and stored in the instruction decoding buffer 6. At the same time, the mode addition circuit 33 adds "+10" to the branch destination instruction to add "+10" to the branch destination instruction in order to indicate whether or not the branch destination instruction is "01". Set as. Then, the instruction decoding buffer is stored as shown in FIG.

(4) The instruction decoding unit 7 determines an issuable instruction in the same manner as described in (2). Of the instructions issued in the previous cycle, the instruction N + 4 issued to the arithmetic unit A8 is a load instruction that takes two cycles and its execution is not completed yet. Therefore, the issue of the instruction N + 7 having a data dependency relationship with this instruction is delayed by another cycle. In this processing cycle, Bcc_l, instruction N, instruction N
It is determined that +1 and the instruction N + 3 can be issued. The instruction issuance control circuit 40, via the instruction issuance circuit 39, Bcc_
l instruction to instruction execution consistency maintaining circuit 18, instruction N to arithmetic unit B9, instruction N + 1 to arithmetic unit C10,
The instruction N + 3 is issued to the arithmetic unit D11 with an identifier added and issued, and is deleted from the instruction decoding buffer 6.
The identifiers added to these commands are 0, 1, and
It is 1, 1.

Table 3 shows the state of each arithmetic unit after the instruction is issued.
It is shown in the second line of. Each issued instruction has the following (5-1)
~ (5-4) is executed. (5-1) The Bcc-l instruction is not issued to the arithmetic unit, and the instruction issue control circuit 40 causes the initial mode holding circuit 14 to hold the mode "01" of the branch instruction itself and hold the speculative execution type. The flag indicating that the Bcc-1 instruction is the circuit 15 is set in the speculative execution state instruction circuit 16 and the condition of the instruction is set in the instruction execution consistency maintaining circuit 18 in the circuit 15. After this, the speculative execution state is entered.

(5-2) When the instruction N is issued, the arithmetic unit B9 sets the corresponding bit in the arithmetic unit management table 12 and executes the instruction. Arithmetic unit B
When the execution of the instruction is completed at 9, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared. Since this instruction is an instruction under speculative execution (the identifier is 1), the execution order management circuit 17 writes the register number of the write destination and the mode “11” in the execution order management buffer 13.

(5-3) The operation unit C10 receives the instruction N
When +1 is issued, the corresponding bit in the arithmetic unit management table 12 is set and the instruction is executed. When the execution of the instruction is completed in the arithmetic unit B9, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since this instruction is an instruction under speculative execution (identifier is 1), the execution order management circuit 17 writes the register number of the write destination to the execution order management buffer 13 and the mode "11".
Write. (5-4) When the instruction N + 3 is issued, the arithmetic unit D11 sets the corresponding bit in the arithmetic unit management table 12 and executes the instruction. When the execution of the instruction is completed in the arithmetic unit D11, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since the instruction N + 2 is an execution under speculative execution (the identifier is 1), the execution order management circuit 17 does not write the operation result in the register file 19 but stores it in the execution order management buffer 13. (6) At this point, the execution order management buffer 13 stores the data in FIG.
It will be stacked up to the 3rd row of 4.

(7) Further, the instruction decoding buffer 6 is shown in FIG.
become that way. In the next cycle, since the instruction N + 4 is completed, the instruction decoding unit 7 performs a series of processes to execute the instruction N + 4.
Issue 7, N + 2. The state of the arithmetic unit after the instruction is issued is shown in the third line of Table 3. When the execution of these instructions is completed, the execution order management buffer is stacked up to the fourth line in FIG.

(8) As described above, the arithmetic unit executes the input instruction and clears the corresponding bit of the arithmetic unit management table 12 when a new instruction can be processed. When the instruction decoding unit 7 can process a new instruction, it restarts the instruction issuing process. (9) The instruction N + 7 for changing the PSR is executed by the arithmetic unit B as shown in the third line of Table 3. When the instruction N + 7 is completed and PSR is confirmed, the arithmetic unit B clears the flag of the speculative execution state instruction circuit 16. Even if the instruction N + 7 is completed, the speculative execution is executed up to the fourth line in Table 3.

(10) The instruction execution consistency maintaining circuit 18
Since the speculative execution state instruction circuit 16 has been cleared, the speculative execution type holding circuit 15 indicates that it is a Bcc_l instruction, PSR
It is determined whether or not to branch based on the value of. Here, it is assumed that branching occurs. (11) The execution order management circuit 17 is notified by the instruction execution consistency maintaining circuit 18 that the branch has been decided and the speculative execution mode has ended. Then, the execution order management buffer 1
For a branch destination instruction sequence (instruction of mode “11”) existing in 3, the operation result is stored in the corresponding register of the register file 19.

As described above, the speculative execution of the conditional branch instruction Bcc_l and the processing after the branch determination can be executed with the consistency maintained as in the case where the speculative execution is not executed. Further, when it is determined in (10) that the branch is not made, the following is performed. (11) The instruction execution consistency maintaining circuit refers to the speculative execution type holding circuit 15 after determining that the branch is not to be performed, and therefore the instruction execution consistency maintaining circuit is the Bcc_l instruction. Disable. In FIG. 14, the instructions N, N + 1, N + 3, N + 2 are invalidated (cleared). Further, the instruction decoding unit 7 is notified that the branch is not performed, and the processing is redone to fetch the subsequent instruction remaining in the instruction fetch buffer A into the instruction decoding buffer 6.

(12) The execution order management circuit 17 determines from the instruction execution consistency maintaining circuit 18 that no branch occurs,
You are notified that the speculative execution mode has ended. And
Nothing is done because all the operation results of the instructions in the execution order management buffer are invalidated. As described above, the processing performed by the speculative execution by the conditional branch instruction Bcc_l is not used for the processing after it is determined that the branch is not made, and does not contribute to the speedup. However, since the conditional branch instruction Bcc_l has a low probability of not branching,
The probability of occurrence of such a case is low, and not only one speculative execution but one speculative execution of the entire program is speeded up. Also in this case, the processing before the conditional branch instruction maintains continuity with the processing after it is determined that the branch is not taken.

Finally, in the case of including the Bcc-n instruction,
The operation will be described with reference to FIGS. 15 to 19 and Table 4. FIG. 15 is an example of an instruction flow for explaining the operation of the present embodiment for processing a Bcc-n instruction at high speed. Bcc-l
The description up to (1) and (2) described in the description of the instruction is the same for the Bcc_n instruction, so the description is omitted here.

(3) The instruction decoding buffer 6 is in a state in which the instruction N + 7 and the instruction Bcc-n remain in FIG. The transfer control circuit 32 of the instruction decoding unit 7 reads a new instruction sequence from the instruction fetch buffer A3. When it is detected that the read instruction is the Bcc-n instruction, only the instruction following the branch instruction (on the side not branching) is continuously read from the instruction fetch buffer A3, and the instruction decoding buffer 6 is read.
To store. At the same time, the mode addition circuit 33 sets the current mode to "0" in order to indicate whether or not the instruction is the branch destination.
If it is "1", "+01" is added to the instruction at the branch destination and set as "10." Then, the instruction decoding buffer is stored as shown in FIG.

(4) The instruction decoding section 7 determines an issuable instruction. Of the instructions issued in the previous cycle, the instruction N + 4 issued to the arithmetic unit A8 is a load instruction that takes two cycles and its execution is not completed yet. Therefore, the issue of the instruction N + 7 having a data dependency relationship with this instruction is delayed by another cycle. In this processing cycle, Bcc-n, instruction N + 9, instruction N + 10, instruction N + 1
It is determined that 1 can be issued. Instruction issue control circuit 4
0 is the Bcc-n instruction to the instruction execution consistency maintaining circuit 18 and the instruction N + 9 is the arithmetic unit B via the instruction issuing circuit 39.
9, the instruction N + 10 to the arithmetic unit C10, the instruction N +
11 is issued to the arithmetic unit D11 with an identifier added, and is deleted from the instruction decoding buffer 6. The identifiers added to these commands are 0, 1, 1, 1 in the same order.

Table 4 shows the state of each arithmetic unit after the instruction is issued.
It is shown in the second line of. Table 4 shows the situation of instruction execution in the arithmetic unit when the instruction flow of FIG. 15 in the embodiment is executed.

[0094]

[Table 4]

Each issued instruction has the following (5-1)-
It is executed as in (5-4). (5-1) The Bcc-n instruction is not issued to the arithmetic unit, and the instruction issue control circuit 40 causes the initial mode holding circuit 14 to hold the mode "01" of the branch instruction itself and hold the speculative execution type. The flag indicating that the Bcc-n instruction is the circuit 15 is set in the speculative execution state instruction circuit 16 and the condition of the instruction is set in the instruction execution consistency maintaining circuit 18 in the circuit 15. After this, the speculative execution state is entered.

(5-2) The operation unit B9 sends the instruction N +
When 9 is issued, the corresponding bit in the arithmetic unit management table 12 is set and the instruction is executed. When the execution of the instruction is completed in the arithmetic unit B9, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since this instruction is an instruction under speculative execution (identifier is 1), the execution order management circuit 17 writes the register number of the write destination to the execution order management buffer 13 and the mode "10".
Write. (5-3) When the instruction N + 10 is issued, the arithmetic unit C10 sets the corresponding bit of the arithmetic unit management table 12 and executes the instruction. When the execution of the instruction is completed in the arithmetic unit B9, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since this instruction is an instruction under speculative execution (the identifier is 1), the execution order management circuit 17 writes the register number of the write destination to the execution order management buffer 13 and the mode "10".
Write. (5-4) When the instruction N + 11 is issued, the arithmetic unit D11 sets the corresponding bit in the arithmetic unit management table 12 and executes the instruction. Arithmetic unit D11
When the execution of the instruction is completed at, the execution result is output to the execution order management circuit 17. At the same time, the corresponding bit in the arithmetic unit management table 12 is cleared.

Since the instruction N + 2 is an execution under speculative execution (the identifier is 1), the execution order management circuit 17 stores the operation result in the execution order management buffer 13 without writing it in the register file 19. (6) At this point, the execution order management buffer 13 stores the data in FIG.
It will be stacked up to the 3rd row of 9.

(7) Further, the instruction decoding buffer 6 is shown in FIG.
become that way. In the next cycle, since the instruction N + 4 is completed, the instruction decoding unit 7 performs a series of processes to execute the instruction N + 4.
Issue 7, N + 12 and N + 13. The state of the arithmetic unit after the instruction is issued is shown in the third line of Table 4. When the execution of these instructions is completed, the execution order management buffer stores the data in FIG.
Will be stacked up to the 5th line.

(8) As described above, the arithmetic unit executes the input instruction and clears the corresponding bit of the arithmetic unit management table 12 when a new instruction can be processed. When the instruction decoding unit 7 can process a new instruction, it restarts the instruction issuing process. (9) The instruction N + 7 for changing the PSR is executed by the arithmetic unit B as shown in the third line of Table 4. When the instruction N + 7 is completed and PSR is confirmed, the arithmetic unit B clears the flag of the speculative execution state instruction circuit 16. Even if the instruction N + 7 is completed, the speculative execution is executed up to the fourth line in Table 4.

(10) The instruction execution consistency maintaining circuit 18
Since the speculative execution state instruction circuit 16 has been cleared, the speculative execution type holding circuit 15 indicates that it is a Bcc-n instruction, and the PSR
It is determined whether or not to branch based on the value of. We assume that we do not branch. (11) The execution order management circuit 17 is notified by the instruction execution consistency maintaining circuit 18 that branching has not been decided and the speculative execution mode has ended. Then, with respect to the instruction sequence (instruction whose mode is “10”) following the branch instruction existing in the execution order management buffer 13, the operation result is stored in the register of the corresponding register file 19.

As described above, the processing performed by the speculative execution by the conditional branch instruction Bcc_n maintains continuity with the processing after it is determined that the branch is not taken. Moreover, since all speculative execution results are valid, they can be processed most efficiently and at high speed. Further, when it is determined that the branch is made in (10), the following is performed. (11) The instruction execution consistency maintaining circuit refers to the speculative execution type holding circuit 15 after determining that the instruction is to be branched, and the instruction execution consistency maintaining circuit determines that it is the Bcc-n instruction. Disable all. In FIG. 19, all the commands after the command N + 9 are invalidated (cleared). Further, the instruction decoding unit 7 is notified of branching, and the instruction fetch buffer A is made to perform the processing again so as to fetch the branch destination instruction into the instruction decoding buffer 6.

(12) The execution order management circuit 17 determines from the instruction execution consistency maintaining circuit 18 that no branch occurs,
You are notified that the speculative execution mode has ended. And
Nothing is done because all the operation results of the instructions in the execution order management buffer are invalidated. As described above, the processing performed by the speculative execution by the conditional branch instruction Bcc_n is not used for the processing after it is decided that the branch is made, and does not contribute to the speedup. However, since the conditional branch instruction Bcc_n has a low probability of branching, the probability of occurrence of such a case is also low, and not only one speculative execution is seen, but all speculative executions of the entire program are combined. , Will be faster. Also in this case, the processing before the conditional branch instruction maintains continuity with the processing after it is decided to branch.

In this embodiment, the pipeline of the arithmetic unit has one stage for the sake of simplicity. Even if there are a plurality of stages, only the arithmetic unit management table 12 and the like need be changed, but this is not related to the gist of the present invention. In this embodiment, the instruction decoding buffer 6 is stacked alternately, but the order may be reversed, and it is not necessary to alternate the instructions one by one. Further, the instruction decoding buffer 6 itself does not necessarily have to be provided. In that case, the instruction may be directly transferred from the instruction fetch buffers A3 and B4 to each decoder of the instruction decoding circuit 34 via the selector 5.

In this embodiment, the arithmetic units A8 to D11 are used.
For simplification of description, the respective functions are limited, but the units may have the same functions. In the present embodiment, in order to distinguish whether the storage destination of the operation result is the register file 19 or the execution order management buffer 13, it is realized by adding an identifier to the instruction when issuing the instruction. You may use PC value instead of.
Further, the instruction decoding unit 7 may instruct the execution order management circuit 17 to store the instruction without adding the identifier to the instruction.

In this embodiment, an instruction (an instruction whose operand is in a register) for finally storing the operation result of the operation unit in the register of the register file 19 is used for simplification of description, but the present invention is not limited to this. An instruction (an instruction whose operand is in the memory) for finally storing the operation result in the memory may be used. In that case, for example, the execution order management buffer 13 will temporarily store the operation result, the information indicating the address of the memory in which it should be stored, and the mode, and the execution order management circuit 17
Need only have a function of writing the calculation result to the memory.

In this embodiment, since the speculative execution state holding circuit has only one state, only one branch instruction is speculatively executed. Even if plural speculative executions are executed. Good. In this embodiment, a mode is added according to the following rule so that the control flow of the instruction can be understood every time the instruction is generated in the instruction decoding unit. For example, if the current instruction sequence mode is "00", the subsequent instruction sequence mode is "+0".
Add "1" to "01", branch destination instruction mode is "+"
10 "is added and set as" 10 ". By using this rule, it is possible to easily determine the instruction sequence up to the branch instruction, the subsequent instruction sequence, and the branch destination instruction sequence. This is an example, and other methods are possible.

In this embodiment, since the speculative execution type holding circuit 15 is allowed to have only one state, the speculative execution base branch instruction is limited to one. But,
An instruction for changing the PSR by increasing the types of modes for distinguishing the instruction sequence and providing a plurality of initial mode holding circuits 14, speculative execution type holding circuits 15, speculative execution state instruction circuits 16, and instruction execution consistency maintaining circuits 18 Since the correspondence between the branch instruction and the branch instruction becomes clear, it is possible to speculatively execute a plurality of branch instructions.

In the present embodiment, regarding the data dependency, the decoding unit issues the instruction out-of-order, but in
-order does not affect the gist of the present invention. As described above, the information processing apparatus of the present invention is Bcc-l, Bcc-i, Bc
By properly using the three types of branch instructions of cn, the speed can be further increased according to the branch probability. For example, in a program written in the programming language C,
The compiler uses the Bcc_l instruction for for loops with a high branch probability, and if-th
Use the Bcc_i instruction for en-else instructions. Moreover, the effect becomes even greater if the instruction sequences in the loop are scheduled so that they can be executed simultaneously.
Also, in the case of if-then-else type instructions, even if one is predicted, the cost of misalignment is great, and at the same time, even if the branch is predicted and executed speculatively, it depends on the data dependence. In many cases, only one instruction can be executed. In such a case, the parallel execution rate does not increase, and when both are executed, the effect is greater.

[0111]

According to the processor of the present invention, even if the condition of the conditional branch instruction is not fixed, the instruction of the instruction sequence to be speculatively executed is changed according to the type of the conditional branch instruction. A program including branch processing can be executed at high speed with few interlocks. In particular, when a plurality of instructions are executed simultaneously, the time difference between the instruction for changing the branch condition and the conditional branch instruction is reduced, and this effect is great.

Specifically, the following three cases are used properly. In the case of the first type of conditional branch instruction, speculatively issue the branch destination instruction to multiple operation units, temporarily store the operation results, and make sure that the condition is fixed and not branch. If it is found, by executing the instruction sequence on the non-branching side, the preceding processing of the branch instruction becomes possible, and the branch processing can be speeded up. This first type of conditional branch instruction is used when the probability of branching is high.

In the case of the second type of conditional branch instruction, speculatively the branch destination instruction and the non-branch side instruction are issued to a plurality of arithmetic units, and the arithmetic results are temporarily stored. At the same time, when the condition is fixed, only the operation result on the fixed side is validated, so that the branch instruction can be processed in advance, and the branch processing can be speeded up. This second type of conditional branch instruction is used when the probability of branching is unknown.

In the case of the third type of conditional branch instruction, the instruction on the side that does not speculatively branch is issued to a plurality of arithmetic units, the arithmetic results are temporarily stored, and the condition is fixed. If it is found that the branching is performed, the branching side instruction sequence is executed to enable the preceding processing of the branching instruction, which has the effect of speeding up the branching processing. The third conditional branch instruction is used when the probability of not branching is high.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a processor according to an embodiment of the present invention,

FIG. 2 is a block diagram showing a detailed configuration of an instruction fetch unit in the embodiment.

FIG. 3 is a block diagram showing a detailed configuration of an instruction decoding unit.

FIG. 4 is a mode explanatory view showing a mode added to an instruction flow in the embodiment.

FIG. 5 is an instruction flow diagram including a Bcc_i instruction in the embodiment.

FIG. 6 is an explanatory diagram (1) of an instruction decoding buffer when processing the instruction flow of FIG. 5 in the embodiment.

FIG. 7 is the same as above (No. 2).

FIG. 8 is the same as above (3).

FIG. 9 is an explanatory diagram of an execution order management buffer when processing the instruction flow of FIG. 5 in the same embodiment;

FIG. 10 is an instruction flow diagram including a Bcc_l instruction in the embodiment.

FIG. 11 is an explanatory diagram (part 1) of the instruction decoding buffer 6 when processing the instruction flow of FIG. 10 in the embodiment.

FIG. 12 is the same as above (No. 2).

FIG. 13 is the same as above (3).

FIG. 14 is an explanatory diagram of an execution order management buffer when processing the instruction flow of FIG. 10 in the embodiment.

FIG. 15 is an instruction flow diagram including a Bcc_n instruction in the embodiment.

FIG. 16 is an explanatory diagram (1) of the instruction decoding buffer 6 when processing the instruction flow of FIG. 15 in the embodiment.

FIG. 17 is the same as above (No. 2).

FIG. 18 is the same as above (3).

FIG. 19 is an explanatory diagram of an execution order management buffer when processing the instruction flow of FIG. 15 in the example.

[Explanation of symbols]

 1 memory 2 instruction fetch unit 3 instruction fetch buffer A 4 instruction fetch buffer B 5 selector 6 instruction decoding buffer 7 instruction decoding unit 8 arithmetic unit A 9 arithmetic unit B 10 arithmetic unit C 11 arithmetic unit D 12 arithmetic unit management table 13 execution order Management buffer 14 Initial mode holding circuit 15 Speculative execution type holding circuit 16 Speculative execution state instruction circuit 17 Execution order management circuit 18 Instruction execution consistency maintaining circuit 19 Register file 20 Scoreboard 21 Program counter 22 Branch instruction detection circuit 23 Arithmetic circuit 31 Branch instruction detection circuit 32 Transfer control circuit 33 Mode addition circuit 34 Instruction decoding circuit 34a to 34f Decoder 36 Data dependency detection circuit 37 Scoreboard management circuit 38 State detection circuit 39 Instruction issuing circuit 39a to 39 d selector 40 instruction issue control circuit

Claims (16)

[Claims] 1. A conditional branch instruction having a plurality of execution units and processing instructions of an instruction string in a memory in parallel, the conditional branch instruction being included in an instruction string before execution and having a condition dependent on another instruction. And an instruction type determination means for determining the type of the conditional branch instruction until the success or failure of the branch is determined. An instruction parallel issue means for issuing instructions in parallel to an execution unit; a branch determination means for determining success or failure of a conditional branch instruction when another instruction on which the conditional branch depends is executed; A processor comprising: an execution result management means for identifying whether the execution result of an instruction sequence is valid or invalid according to a result of determination of whether or not a branch is successful. 2. The instruction type discriminating means discriminates a first type instruction whose branch probability is about the same as a non-branch probability and a branch instruction other than that, and the instruction parallel issuing means is a conditional branch. When the instruction is the first type instruction, both the branch destination instruction sequence and the instruction sequence subsequent to the conditional branch instruction are issued in parallel to the execution unit, and the conditional branch instruction is other than the first type instruction. If the conditional branch instruction is the instruction of the first type, the execution result management means determines whether the branch is successful or not, While the execution result of one instruction sequence is valid and the other is invalid, if the conditional branch instruction is other than the first type instruction, all execution results of the instruction sequence are valid according to the result of the branch success / failure judgment. Alternatively, it is invalidated. 1. The processor according to 1. 3. The instruction type discriminating means, a second type instruction having a higher probability of branching an instruction other than the first branch instruction from the first branch instruction, and a probability not branching from the first branch instruction. Is determined to be a third type of instruction, the instruction parallel issue means issues a branch destination instruction sequence instruction in parallel to the execution unit in the case of the second type of instruction, 3. The processor according to claim 2, wherein in the case of the instruction, the instruction of the instruction sequence following the conditional branch instruction is issued in parallel to the execution unit. 4. The first processor further comprises: a first instruction fetch buffer for temporarily storing instructions of an instruction sequence subsequent to the conditional branch instruction; and an instruction of an instruction sequence of a branch destination of the conditional branch instruction. 2. The processor according to claim 1, further comprising a second instruction fetch buffer for storing the instruction, and an instruction fetch unit for reading the instruction stored in the memory and storing the instruction in the first and second instruction fetch buffers. 5. The instruction fetch means outputs a read address to a memory and increments the content thereof, a program counter, a conditional branch instruction detecting means for detecting a conditional branch instruction from an instruction read from the memory, and a condition. Based on the conditional branch instruction detected by the branch instruction detecting means, arithmetic means for calculating the address of the branch destination, and usually, the content of the program counter is incremented every time the instruction is read from the memory. When an instruction is stored in the instruction fetch buffer and a conditional branch instruction is detected, the instruction of the subsequent instruction sequence is stored in the first instruction fetch buffer, and the branch destination address obtained by the arithmetic means is written in the program counter, And a fetch control means for storing the instruction of the instruction sequence of the branch destination in the second instruction fetch buffer. The processor according to claim 4, characterized in that 6. The instruction parallel issuing means decodes instructions to generate a control signal to an execution unit, and a plurality of decoding means from the first or second instruction fetch buffer. Transfer control means for transferring one by one, and a mode indicating which instruction sequence the instruction belongs to is added to each instruction transferred by the transfer control means, and an instruction sequence following the branch instruction and a branch destination 5. The processor according to claim 4, further comprising mode adding means for changing the mode depending on the instruction sequence of the above. 7. The mode added by the mode adding means is:
This is 2-bit information, and the mode of the instruction sequence following the conditional branch instruction is the value obtained by adding the first value to the mode of the conditional branch instruction itself, and the mode of the instruction sequence of the branch destination is 7. The processor according to claim 6, which is a value obtained by adding the second value. 8. The other instruction on which the conditional branch instruction depends is:
7. The processor according to claim 6, which is an instruction to change a PSR (Program Status Register), wherein the branch determination unit detects that an instruction to change the PSR has been executed and refers to an execution result thereof. .. 9. The processor further comprises a data dependency relationship determining means for determining a data dependency relationship between a plurality of decoded instructions with reference to a plurality of decoding results decoded by the decoding means. , The scoreboard managing means for managing which register is used by the instruction being executed in the execution unit, the empty state detecting means for detecting the empty state of the execution unit, and each of the decrypted by the decrypting means. Regarding the instruction, based on the determination result of the data dependency determining means, the scoreboard managing means, the detection result of the empty state detecting means, the issuable instruction is permitted to be issued from the instruction parallel issuing means to the execution unit, The instruction issue permitting means for permitting issuance from the instruction parallel issuing means to the branch judging means when the instruction decoded by the decoding means is a conditional branch instruction. On-board processor. 10. The instruction issue permitting means has no data dependency relation with the preceding instruction from the detection result of the data dependence detecting means for each of the decoding results of the plurality of decoding means, and the command issuing permitting means of the scoreboard managing means The register specified by the operand of the instruction from the information is not used for the instruction being executed in the execution unit, and the execution unit that can execute the instruction is free from the detection result of the empty state detection means, 10. The processor according to claim 9, wherein it is determined that an instruction satisfying the condition can be issued. 11. The processor further holds information indicating whether or not an instruction is being executed for each execution unit, and an execution unit management table referred to by an empty state detection means and an execution unit execution. 10. The processor according to claim 9, further comprising a scoreboard which holds information indicating which register is used by the instruction in the inside and which is referred to by the scoreboard management means. 12. The execution result managing means includes an initial mode holding means for holding the mode of the conditional branch instruction issued by the instruction parallel issuing means as an initial mode, and an instruction parallel issuing means. The speculative execution type holding means for holding the type of the conditional branch instruction, and the speculative execution state instruction means for holding the flag indicating that the condition judgment of the conditional branch instruction issued by the instruction parallel issuing means has not been finalized. The instruction parallel issuing means issues a conditional branch instruction to the branch judging means, and at the same time, the mode of the conditional branch instruction is held in the initial mode holding means, and the type of the conditional branch instruction is held as the speculative execution type. 10. The processor according to claim 9, wherein the processor outputs the flag to the speculative execution state instructing means. 13. The execution result management means stores the execution result of an instruction in the execution unit, the mode of the instruction, and the information of the storage destination where the execution result is originally stored. 13. The processor according to claim 12, further comprising a temporary storage unit for executing the operation. 14. The temporary storage means stores, as the storage destination information, a register number when the original storage destination is a register and a memory address when the original storage destination is a memory. 14. The processor according to claim 13, wherein: 15. The branch judging means clears the flag of the speculative execution state instructing means when judging whether or not to branch, and the execution result managing means holds the initial mode based on the judgment result of the branch judging means. Means for identifying whether the execution result of the temporary storage means is valid or invalid by referring to the means and the speculative execution type holding means, transferring the valid execution result to the original storage destination, and clearing the invalid execution result. Item 13. The processor according to Item 13. 16. The instruction fetch means comprises: a first instruction fetch buffer for temporarily storing an instruction of an instruction sequence subsequent to the conditional branch instruction; and a second instruction fetch buffer for temporarily storing an instruction of a branch destination of the conditional branch instruction. Instruction fetch buffer, a program counter that outputs the read address to the memory and increments its contents, a conditional branch instruction detection unit that detects a conditional branch instruction from the instruction read from the memory, and a conditional branch instruction detection unit. An arithmetic means for calculating a branch destination address based on the detected conditional branch instruction, and normally, the content of the program counter is incremented every time the instruction is read from the memory, and the instruction is transferred to the first instruction fetch buffer. And a conditional branch instruction is detected, the instruction of the subsequent instruction sequence is stored in the first instruction fetch buffer, The instruction parallel issue means decodes the instruction by writing the branch destination address obtained by the computing means to the program counter and storing the instruction of the instruction sequence of the branch destination in the second instruction fetch buffer. A plurality of decoding means for generating a control signal to the execution unit, a transfer control means for transferring an instruction from the first or second instruction fetch buffer to all the decoding means one by one, and a transfer control means for transferring the instruction. Mode adding means for adding a mode indicating to which instruction sequence the instruction belongs, and changing the mode between the instruction sequence subsequent to the branch instruction and the instruction sequence at the branch destination. And a processor that references the plurality of decryption results decrypted by the decryption means, determines data dependency between the plurality of decrypted instructions, and executes the execution unit. In fact The scoreboard managing means for managing which register is used by the inside instruction, the empty state detecting means for detecting the empty state of the execution unit, and the data for each instruction decoded by the decoding means Based on the determination result of the data dependency determination means, the scoreboard management means, and the detection result of the empty state detection means, the issuable instruction is permitted to be issued from the instruction parallel issuing means to the execution unit, and the deciphering means is used. When the decoded instruction is a conditional branch instruction, it has an instruction issue permitting means for permitting the instruction parallel issue means to issue to the branch judging means, and the execution result managing means executes the instruction in the execution unit. The result, the mode of the instruction, the temporary storage means for storing the execution result in correspondence with the information of the storage destination where the execution should be originally stored, and the conditional branch instruction issued by the instruction parallel issuing means Is held as an initial mode, an speculative execution type holding means for holding the type of the conditional branch instruction issued by the instruction parallel issuing means, and an instruction parallel issuing means. And a speculative execution state instructing means for holding a flag indicating that the conditional judgment of the conditional branch instruction has not been decided yet, and the instruction parallel issuing means issues the conditional branch instruction to the branch determining means and at the same time, The mode of the conditional branch instruction is output to the initial mode holding means, the type of the conditional branch instruction is output to the speculative execution type holding means, the flag of the speculative execution state instruction means is set, and the execution result management means When the judgment result of the judging means is received, if the speculative execution type holding means holds the first type instruction, and if it is judged to branch, it is temporarily stored by referring to the initial mode. If the execution result of the instruction sequence following the stage is cleared and the execution result of the instruction sequence at the branch destination is transferred to the original storage destination, conversely, if it is determined not to branch, the initial mode is referenced and In the case where the execution result of the instruction sequence at the branch destination is cleared from the storage unit and the execution result of the subsequent instruction sequence is transferred to the original storage destination, and the speculative execution type storage unit holds the second type instruction. If it is determined to branch, the execution result of the instruction sequence of the branch destination is transferred from the temporary storage means to the original storage destination by referring to the initial mode, and conversely, if it is determined not to branch, When the execution result of the instruction sequence at the branch destination is cleared from the temporary storage means, the speculative execution type holding means holds the third type instruction, and when it is determined to branch, the initial mode is set. By referring to the execution result of the subsequent instruction sequence from the temporary storage means Transfer come into storage location, on the contrary, when it is determined not to branch to clear the execution result of the instruction sequence to be followed from the temporary storage means. The processor according to claim 3, wherein: