JPH046983B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to an instruction prefetch method that prefetches the next instruction while predicting a decision result prior to execution of a branch condition decision step included in a step of an instruction sequence of a data processing system. Regarding equipment.

Prior Art In a data processing system in which a group of instructions including at least one branch instruction is stored in a storage device in the form of an instruction sequence, such an instruction sequence is executed as follows.

First, a branch instruction is stored at a branch source address in the storage device. Next, the instruction to be executed following this branch instruction is prefetched. After this, a branch instruction is executed, and the result of this execution reveals the next instruction to be executed. Such a system is proposed in US Pat. No. 4,200,927. but,
In this system, if the branch instruction prefetch control is stopped until the execution result is determined, speeding up of processing will be hindered.

In order to eliminate this drawback, a method has been proposed in which the execution result of a branch instruction is predicted in advance and instructions are prefetched in accordance with this prediction. When this prediction is made correctly, the data processing system operates with little delay in processing time. For example, there are the following three methods as such conventional prediction methods. 1st
In the above prediction method, the branch destination direction of all branch instructions is predicted to be either the successful side or the unsuccessful side.

Another prediction method predicts the branch destination direction based on past facts. That is, by using the fact that the branch destination has already been revealed in the past execution results of the same branch instruction and making predictions based on these results, the prediction accuracy rate is increased. Such a prediction method was introduced in April 1978 IEEE
COMPUTER “Component Progress; Its
Effecton High-Speed Computer
The idea is shown in "Arvhitecture and Machine Organization", and Japanese Patent Application Laid-open No. 76638/1983 shows a specific structure.

In yet another prediction method, a large number of branch instruction flags are prepared to predict the branch direction in response to a branch instruction, and the branch destination is predicted by referring to these branch instruction flags in response to the occurrence of a branch instruction. . For details of this example, refer to Japanese Patent Application Laid-Open No. 74857/1983. However, in all three prediction methods described above, reading and decoding of branch instructions are essential, and there is a drawback that processing is delayed by the amount of these read and decoding operations even if the prediction is correct.

A prediction method that eliminates this drawback was developed in JP-A-57-
It is shown in Publication No. 59253. In this method, the branch destination address of a branch instruction contained in a block in the instruction cache memory, which is a copy of the instruction part of the main memory, is set as the address of the block to be fetched next after the block. It is retained in the storage means as . In the instruction prefetching operation, the storage device means is accessed at the same time as the instruction cache memory is accessed to read the branch destination address, and the address of the instruction to be prefetched is determined based on the read branch destination address. , this method is different from the three conventional prediction methods described above and is effective in speeding up the processing. but,
In this method, prediction is made in correspondence with blocks in the instruction cache memory, so when a plurality of branch instructions exist in the block, prediction cannot be made in correspondence with each branch instruction. As a result, there is a drawback that only a prediction hit rate with low accuracy can be obtained.

OBJECTS OF THE INVENTION It is an object of the invention to provide an instruction prefetching device which eliminates the above-mentioned drawbacks.

Composition of the Invention The instruction prefetching device of the present invention combines instruction execution means for sequentially executing read instructions, and branch information including information specifying the address of a branch instruction and a branch destination address of the branch instruction. A branch history table means for storing a plurality of pairs, and when performing an instruction prefetch operation, checking to check whether information specifying the address of a branch instruction to be prefetched in the instruction prefetch operation is registered in the branch history table means. means, instruction prefetch control means for reading corresponding branch information from the branch history table means in response to confirmation of registration by the checking means, and controlling the instruction prefetch operation to continue in accordance with the branch information; a first determining means for determining whether an execution result matches the branch information of the branch history table means corresponding to the branch instruction; and a first determining means for determining whether the branch instruction is a counting branch instruction. a second determining means, a third determining means for determining whether or not the counting branch instruction has executed a branch in the instruction execution means; a first control that does not change branch information corresponding to the branch instruction of the history table means;
and according to the third determination result, the first determination result indicates a mismatch, the second determination result indicates a counting branch instruction, and the third determination result indicates that the counting branch instruction does not branch in the instruction execution means. A second control that does not change the branch information corresponding to the counting branch instruction of the branch history table means and a first determination result indicating a mismatch and a second determination result indicating that the counting branch instruction a third control for updating the branch information corresponding to the branch instruction in the branch history table means based on the execution result of the branch instruction; When the determination result indicates a counted branch instruction and the third determination result indicates that the counted branch instruction executed a branch in the instruction execution means, the branch information corresponding to the counted branch instruction in the branch history table means is retrieved. and update control means for performing update control based on the execution result of the count branch instruction.

Principle and Operation of the Invention The present invention is characterized by the fact that in addition to the branch direction in the execution of a branch instruction, the branch destination address can be predicted with a relatively high accuracy rate by understanding the past results of the same branch instruction; The same counting branch instruction (hereinafter referred to as BCT instruction) is used to manage the number of loops.
In a program that configures a loop that repeats many times, the BCT instruction when exiting from the loop has a different branch direction from the BCT instruction in the middle, and the BCT instruction when re-entering the loop that exited from the loop The BCT instruction when escaping means that the device operates based on the fact that the branch directions are different.

Embodiment of the Invention Next, an embodiment of the present invention will be described in detail with reference to the drawings. Referring to FIG. 1, one embodiment of the present invention is an operand reading circuit having an instruction address generation circuit 401, an instruction address conversion circuit 402, an instruction decoding circuit 403, an operand address generation circuit 404, an operand address conversion circuit 405, and an operand storage circuit. Circuit 406, instruction execution circuit 40
7, instruction storage circuit 408, instruction buffer 409,
Branch history table (BHT) 410, instruction address register 411, instruction address addition circuit 4
12, branch information buffer 413, instruction alignment circuit 4
14. Consists of a branch information switching circuit 415, branch information registers 416, 417, 418, and 419, a prediction confirmation circuit 420, an address generation circuit 421, a selection circuit 422, a register 423, an instruction prefetch control circuit 424, and a flip-flop 425. .

Both the instruction storage circuit 408 and the operand storage circuit in the operand readout circuit 406 may be main memory itself; further, an instruction cache memory in which the instruction storage circuit 408 is a copy of a portion of the instruction portion of the main memory; The operand storage circuit may be configured as an operand cache memory that is a copy of a portion of the operand portion of the main memory. For details of the instruction cache memory and operand cache memory, refer to Japanese Patent Laid-Open No. 87282/1982.

The present invention does not necessarily have a device configuration corresponding to the above-mentioned instruction processing units; for example, an instruction address generation circuit 401, an operand address generation circuit 404, an instruction address conversion circuit 405, an instruction storage circuit 408, and an operand readout circuit 406.
The present invention can also be applied to computer systems in which memory circuits are shared.

In FIG. 1, the branch history table (BHT) 410 pairs information specifying the address of a branch instruction, a branch success/failure flag as a prediction of execution of the branch instruction, and a branch destination address as shown in FIG. I remember. The instruction storage circuit 408
The instruction address register (IAR) 41 for
1 holds the instruction read request address and executes the instruction read operation.

Furthermore, the instruction address register 411
(IAR) is branch history table 410 (BHT)
and the signal line 10 to the instruction address addition circuit 412.
1. The register 411
The contents of the branch history table 410 (BAT)
A signal indicating whether the address of the instruction to be indexed and read is registered in the signal line 106
Output to. If registered, the corresponding branch destination address is read out to the signal line 105. If it is not registered, the instruction address addition circuit 412 generates an address for prefetching the instruction of the subsequent instruction word.

The instruction address addition circuit 412 is a circuit that generates "IAR+8" at the output 107 when it is assumed that the instruction word read in one request is 8 bytes. The instruction buffer 409 stores 8-byte prefetched instruction words read from the instruction storage circuit 408 and forms a queue for supplying instructions to the instruction processing section. The instruction alignment circuit 414
is the signal line 102 when the command buffer 409 is empty.
is read from the instruction storage circuit 408 via
In response to the 8-byte command word, the command buffer 40
9 is not empty, this circuit extracts an instruction in response to the 8-byte instruction word stored in the instruction buffer via the signal line 103 and supplies the instruction to the instruction decoding circuit 403 via the signal line 104.

The instruction decoding circuit 403 has a function of reporting the instruction word length and whether or not the instruction word is a BCT instruction to the branch information register 417 via the signal line 126 when an instruction word is given via the signal line 104. have The branch information buffer 413 is prepared for the instruction word stored in the instruction buffer 409, and if there is a branch instruction predicted to be a successful branch in the instruction word, the branch information buffer 413 is prepared for the instruction word stored in the instruction buffer 409. The branch instruction address is set via the signal line 101, and the branch destination address and V bit as branch information are set from the branch history table 410 (BHT) via the signal line 105. , if there is no branch instruction predicted as a successful branch, the V bit becomes 0;
The address of each branch instruction is set via signal line 101. The branch information switching circuit 415
When the command buffer 409 is empty, the signal line 101
and 105, otherwise the branch information provided via the branch information buffer 413 is output, respectively. The registers 416, 417, and 418 correspond to each processing stage of instruction decoding, instruction address generation, and address translation of a branch instruction, and hold branch information thereof. The branch information register 41
A register 9 replaces the branch destination address field with an actual branch address generated by executing the branch instruction. register 417,4
18 and 419 hold branch information shown in FIG. The prediction confirmation circuit 420 stores the actual branch destination address and branch success/failure result generated by executing the branch instruction, and the branch information register 418.
This circuit matches prediction information of the branch instruction held in the branch instruction. The address generation circuit 421 adds the address of the branch instruction held in the branch information register 419 and the instruction word length of the branch instruction itself to generate an instruction address of the instruction on the branch NOGO side. The selection circuit 422 responds to the state of the branch instruction success/failure signal line 110 to determine whether the state of the signal line is branched.
When indicating GO, the output of the branch destination address part held in the branch information register 419 given via line 115 is selected, and the state of the signal line is changed to branch.
When indicating NOGO, the output of the address generation circuit 421 given through the signal line 116 is selected, and the output of the selection circuit 422 is supplied to the register 423 and the instruction address register (IAR) 411 through the signal line 113. . The register 42
3 is for updating the branch history table 410 (BHT) when prediction of a branch instruction fails, and also inputs a new address for instruction prefetching to the instruction address register 411 (IAR) via the signal line 117. supply The instruction prefetch control circuit 424 controls the instruction address register 411 (IAR) based on the branch prediction signal provided from the branch history table 410 (BHT) via line 106 and the prediction success/failure signal provided from the prediction confirmation circuit via line 112. This is a circuit that controls the input of the

Next, the branch history table 410
(BHT) The operation of this embodiment will be described in detail with reference to detailed block diagrams and time charts of the prediction confirmation circuit 420 and the instruction prefetch control circuit 424.

Referring to FIG. 2, the branch history table 410 (BHT) is stored in the directory storage unit 50.
1. Data storage section 502, test circuit 503, 5
04, 505, and 506, a priority circuit 507, a level selection circuit 508, and an OR circuit 509. The storage units 501 and 502 are storage units with the number of sets m and the number of levels n, in which the unit of the instruction word read from the instruction storage circuit 408 in response to one request is the unit of block.

Referring to FIG. 3, a part of the instruction address of a branch instruction and a V bit indicating whether or not the contents are valid are stored in a storage unit 501, and a real address of a branch destination address is stored in a storage unit 502. There is. The V bit indicates the validity of the word in the corresponding branch history table (BHT) 410, and at the same time functions as a branch success/failure flag as a prediction of execution of the branch instruction.

Indexing into the branch history table (BHT) 410 is performed by the set associative method as described below.

The test circuits 503, 50 shown in FIG.
4, 505, and 506 are instruction address registers 411 corresponding to each level of the table 410.
A signal indicating whether the request address held in (IAR) is registered in BHT-AAi of each level (i indicates the suffix corresponding to the level) is output to signal lines 130, 131, 132, and 133. . Referring to FIG. 4, the test circuit 50
3,504, 505 and 506 are each
It consists of a match circuit 701 and a magnitude comparison circuit 702.

In the matching circuit 701, the contents of each level of the storage section 501 and the contents of the register 411 are read out using part IAR (:18-28) of the request address held in the instruction address register (IAR) 411 as a set address. IAR(:4-17) is compared to detect whether an equal address exists. The branch history table (BHT) is already in the 8-byte block of the instruction word to be read at the request address held in the instruction address register (IAR) 411 by the output of the matching circuit 701.
It is determined whether a branch instruction registered in 410 exists. However, the above-mentioned coincidence detection alone is not sufficient to establish a correspondence between the request address and the branch instruction from which it should be read. Referring to FIG. 5, in the block of 8-byte instruction words read in one request, 2-byte instructions BC ₀ , A, BC ₁ ,
There are four instructions with BC ₂ . Instructions BC ₀ , BC ₁ ,
When both BC ₂ are branch instructions predicted to be branch successes, part of the address of each branch instruction is registered in the storage unit (BHT-AA) 501. At this time, when branching to instruction A from another branch instruction and the address <A> of instruction A is held in the instruction address register (IAR) 411 as a request address for reading the block of the instruction word, the branch history table (BHT)41
The information of the branch instruction to be read from 0 must be the information of the branch instruction _BC1 from the instruction execution path.

Therefore, the request address held in the register (IAR) 411 and the storage unit (BHT-
AAi) When the following relationship with the address of the branch instruction held in 501 holds together with the above matching condition, a BHT-HITi signal of the corresponding level is generated. This signal is applied to the OR circuit 509 via lines 130-133, and the OR signal of the BHT-HITi signal is output via line 106 to become a branch prediction signal (BHT-HIT).

BHT−HITi={IAR(:4−17)=BHT−AAi (:4−17)} ∩{IAR(:29, 30)≦BHT−AAi (:29,30)} ∩BHT−AAi(V) Referring again to FIG. 4, the magnitude comparison circuit is a circuit that realizes this condition.

Furthermore, when the condition of the signal BHT-HITi is satisfied at two or more levels, the address within the 8-byte block of the branch instruction address held at the corresponding level (BHT-AAi) in the storage unit 501.
The level with the smallest value of BHT−AAi (:29, 30) needs to be selected. Referring again to FIG. 5, the signal BHT-HITi conditions are both satisfied at the level of the branch history table 410 in which branch instruction related information of instructions BC ₁ and BC ₂ is stored. At this time, the level for instruction BC ₁ needs to be selected from the instruction execution path.

The priority circuit 507 receives the signal
This is for the establishment of two or more BHT-HITi, and by this output, the branch destination address of the entry indicated by the set address IAR (:18-28) of the storage unit BHT-DA502 is read out via the level selection circuit 508. Ru.

Referring to FIG. 6, the priority circuit 507 is composed of a group of AND circuits 601-604 and a group of OR circuits 605-608. The n+1 AND circuit groups 601 to 604 are arranged in parallel. The n level selection signals of the level selection circuit 508 in FIG. 2 are given by the signals V ₀ , V ₁ , V ₂ , and V ₃ in FIG. 6 as follows.

When V ₀ , V ₀ L ₀ , V ₀ L ₁ , ..., V ₀ L _{o 0 ・}V 1, V ₁ L ₀ , V ₁ L ₁ , ..., V ₁ L _{o 0}・₁・V ₂ When V ₂ L ₀ , V ₂ L _{1 ,} ..., V ₂ L _{o 0}・₁・₂・V ₃ V 3 L ₀ , V ₃ L ₁ , ...,
V _{3 Lo} The branch information read out from the level selection circuit 508 in FIG. 2 as described above can be associated with the instruction read out from the instruction storage circuit 408 in FIG. 1.

FIG. 10 shows the above-mentioned correspondence between instructions in the instruction storage circuit 408 and branch information in the branch history table (BHT) 410. The instruction execution order is instruction A ₀ , branch instructions BC ₀ , B ₁ ,
This is a case where BC ₁ , B ₂ , B ₃ , BC ₂ , C ₁ , C ₂ . . . are predicted. In addition, <A> is the address of the A instruction,
BCj each indicates a branch instruction.

Referring to FIG. 11, the instruction prefetching operation by the branch history table BHT 410 shown in FIG. 10 is performed as follows. An instruction word is read from the instruction storage circuit 408 in response to the setting of the instruction address register 411 of the request address.
At the same time, table BHT410 is indexed.
When the BHT-HIT signal is output via the signal line 106, the branch destination address <B ₁ > of the storage unit BHT-DA 502 is set in the address register 411, and the next instruction is prefetched. The signal line 10
When the BHT-HIT signal is not output through 6, the 8-byte boundary valve address <A> of instruction A is given to the instruction address addition circuit 412, and the address added by 8 is output, and the next instruction is prefetched sequentially. It will be done.

According to the above instruction preemption, the instruction storage circuit 40
The instruction word read from 8 is table BHT41
The instructions are sequentially read out according to the prediction based on the contents of 0, and can be stored in the instruction buffer 409 in the predicted execution order of the instructions.

At this time, even if the signal BHT-HIT is output, the instruction prefetching operation in the branch prediction direction may be performed after a part of the instruction prefetching operation in the opposite direction to the branch prediction direction is performed.

When the instruction prefetched as described above is a branch instruction and is guided to the instruction decoding circuit 403 by the instruction alignment circuit 414 in FIG.
It is set to 6 (QR ₀ ).

Thereafter, as the branch instruction progresses, the instruction is decoded,
The branch information is transferred to second and third branch information registers 417 (QR ₁ ) and 418 (QR ₂ ) in response to address conversion. Then, the prediction confirmation circuit 420 checks whether the actual branch instruction generation result generated by the execution of the branch instruction matches the prediction information of the branch instruction held in the branch information register 418 (QR ₂ ). Ru. Referring to FIG. 9, the prediction confirmation circuit 420 includes a coincidence circuit 801, flip-flops 802 and 803,
Truth/false circuits 804-807, AND circuits 808-8
13 and an OR circuit 814. The matching circuit 801 is given the real address of the branch destination address generated by the execution of the branch instruction from the instruction address conversion circuit 402 via the signal line 109, and the branch information register 418
The branch destination predicted from (QR ₂ ) is given via signal line 108. The coincidence circuit 801 determines whether the two match or do not match, and the determination result is set in the flip-flop 802. The V bit provided on line 108 from the register 418 is set in the flip-flop 803.

A branch success/failure signal given from the instruction execution circuit 407 via the signal line 110, a BCT bit given from the register 419 via the signal line 130,
and said flip-flops 802 and 803
From truth/false circuits 804-807, AND circuit 808
-813, the V bit is 0, that is, the branch NOGO prediction and the actual branch success/failure result is GO.
The predicted NOGO failure signal when the V bit is 1, that is, the predicted GO when the actual branch success/failure result is NOGO even though it was a branch GO prediction and the branch destination address also matched. A failure signal and a predicted address failure signal for a branch GO prediction in which the branch destination addresses do not match are generated by AND circuits 808, 809, and 810, respectively, for the BCT instruction.
Branch instructions other than BCT instructions are generated by AND circuits 811, 812, and 813, respectively. Furthermore, AND circuits 808, 810, 81
The prediction failure signals generated by branch prediction failure signals 1, 812, and 813 are logically summed by an OR circuit 814, and outputted to the signal line 112 as a branch prediction failure signal. The prediction failure signal generated by the AND circuit 809 is BCT
It is output to the signal line 131 as a GO prediction failure signal. Therefore, if the BCT instruction predicts a branch GO and the predicted GO fails even though the branch destination addresses match, the signal line 13
A BCTGO prediction failure signal is output to the signal line 112, and a branch failure signal is output to the signal line 112 in the case of other prediction failures.

Referring to FIGS. 1 and 12, the branch destination address newly generated from the instruction address conversion circuit 402 is set in the branch destination address field of the branch information register 419 (QR ₃ ). Also, the branch instruction BC ₁ of the branch information register 419 (QR ₃ )
The contents of the address field of the branch instruction _BC1 and the contents of the instruction word length field of the branch instruction BC1 itself are added by the address generation circuit 421 to generate the instruction address of the instruction on the branch NOGO side.

And branch by actual execution of branch instruction BC ₁
If GO, the branch information register 419 (QR ₃ )
If the output <D ₁ > of the branch destination address field given via line 115 is branch NOGO, line 116
The address generation circuit 421 given via
The output <B ₂ > of is selected by the selection circuit 422. Branch prediction failure signal 112 of the branch instruction BC ₁
is generated from the prediction confirmation circuit 420, the output <D ₁ > of the selection circuit 422 is set to the register 423 (WR) via the line 113.

On the other hand, the branch instruction address <BC ₁ > of the branch information register 419 (QR ₃ ) is set to the instruction address register 411 (IAR) via the signal line 114. This address is supplied as a write address to the branch history table 410 (BHT) corresponding to the branch instruction via line 101 for updating the table 410 (BHT). The branch prediction failure signal 1
12 is provided to flip-flop 425, which output is provided as an instruction pulse to branch history table 401 via line 119. In response to this output, branch prediction information for prefetching the next instruction of the branch instruction is updated. In this embodiment, this update is performed with a new branch destination address held in the register 423 (WR) when the predicted NOGO fails, and when the predicted GO fails, the V bit is reset, but the branch prediction information It is also possible to use other methods to update the algorithm.

When prediction fails, all operations of instructions following the prediction side are canceled, and the register 423
After updating the branch history table 410 (BHT), the new request address held in the branch history table 410 (BHT) is supplied to the instruction address register 411 (IAR), and instruction fetching is started again.

Referring to FIG. 13, the actual branch destination address of the BCT instruction BCT ₁ is generated by the instruction address conversion circuit 402 and set in the branch information register 419, similar to the branch instruction BC ₁ in FIG.
Furthermore, the address of BCT ₁ itself held in the register 419 and the instruction word length are the address generation circuit 4
21 to generate the address <B3> of the next instruction of BCT ₁ on the branch NOGO side.

The register 419 holds data according to the branch success/failure signal output from the instruction execution circuit 407 to the signal line 110 upon actual execution of the BCT instruction BCT ₁ .
The GO side branch destination address <D2> or the NOGO side branch destination address <B3> output from the address generation circuit 421 is selected by the selection circuit 422.

From the prediction confirmation circuit 420, the signal line 131 is
When the BCT GO prediction failure signal is output, the output of the selection circuit 422 is sent to the register 423 and the instruction address register (2AR) via the signal line 113.
411 at the same time. However, the instruction pulse to the branch history table 410 is
9, the prediction information in the table 410 is not updated, and the failed instruction is immediately retrieved.

Referring to FIG. 14, the instruction prefetch control circuit 424 is comprised of a flip-flop 1201, truth/false circuits 1202-1205, and an AND circuit 1206. The flip-flop 120
1 is a flip-flop for holding the branch prediction failure signal 112 for one machine cycle. The output of this circuit 424 becomes a selection instruction signal for the selector in the stage preceding the address register 411. This selection instruction signal is transmitted to the instruction address addition circuit 41.
2, the output of the register 423, the output of the table 410, the output of the branch information register 419, and the output of the selection circuit 422.

Note that when the branch prediction is correct under the control of this instruction prefetch control circuit 424, the 18th
The instruction processing shown in the figure is performed, and if the branch GO prediction of the BCT instruction fails, the instruction processing shown in Fig. 20, which will be described later, is performed, and if any other branch prediction fails, the instruction processing shown in Fig. 19, which will be described later, is performed. . The instruction address addition circuit 412 branches
Generates an address to prefetch the NOGO side instruction. At this time, since the address is added as a real address, for example, in a computer system that performs paging, if the address addition exceeds a page boundary, it is necessary to perform address conversion again.

For this purpose, a page boundary crossing detection circuit is provided in the instruction address addition circuit 412, and when the detection circuit detects that a page boundary crossing has occurred, the instruction address generation circuit 1 is activated by the signal line 118, and the instruction address generation circuit ( The IA) 401 and the instruction address translation circuit (IT) 402 may perform the control.

The problem here is which part of the existing instruction address information should be removed when newly registering the instruction address information in the branch history table BHT 410.

This method uses the order of use, that is, the method of expelling from the oldest used LRU
(Least Recently Used), a method of expelling information in the order in which it was entered, that is, in order from the oldest one.
There are FIFO (First In First Out), etc., but either one may be used.

Effects of the Invention Next, the effects of the present invention will be explained in detail with reference to FIGS. 15 to 21.

Referring to FIG. 15, instruction processing is generally divided into the following eight processing units.

(1) IA stage: The instruction address (logical address) of the instruction to be executed is generated.

(2) IT stage: Address translation of the generated instruction address is performed.

(3) IC stage: The instruction is read from the storage device at the translated real address of the instruction.

(4) ID stage: The read instruction is decoded.

(5) OA stage: The operand address (logical address) of the decoded instruction is generated.

(6) OT stage: Address translation of the generated operand address is performed.

(7) OC stage: The operand is read from storage at the translated real address of the operand.

(8) EX stage: Instruction is executed.

If an address translation buffer is provided in the address translation of the IT stage and the OT stage, and the necessary translation table exists in the address translation buffer, the address translation process can be executed at high speed. In addition, a cache memory is provided to hold a copy of part of the data in the main memory during the instruction and operand read operations of the IC stage and OC stage, and if the necessary instructions and operands exist in the cache memory, the IC Stage and OC stage processing can be performed at high speed. The information processing system does not necessarily need to have resources corresponding to each of the above-mentioned processing units. However, for ease of explanation, it is assumed here that each processing unit has a circuit that performs its function. When the above-mentioned IT, OT, IC, and OC stages are capable of high-speed processing, eight-stage pipeline control is possible to efficiently execute the processing flow of multiple instructions.

The flow of processing instructions including branch instructions at this time will be explained with reference to FIGS. 16 and 17.

FIG. 16 shows the flow of instruction processing when it is predicted that all the aforementioned branches will be "GO" in instruction prefetching of a branch instruction. i.e. instruction A ₀
is an instruction that determines the branch condition of branch instruction BC, and the branch condition is the execution result of instruction _A0 , that is, time t7.
Determined in When the branch instruction BC is decoded at time t4, it generates the address of the branch instruction _B1 using the instruction address generation circuit, and thereafter operates to prefetch the _B1 instruction. Time t2, t3,
And at t4, lookbehind instruction A1 on the branch NOGO side,
Address generation for prefetching instructions A2 and A3 is started. At times t6 and t7, subsequent instructions B2 and B on the branch GO side as predicted operations
The instruction prefetch operation of No. 3 is started. Based on the branch condition determination result at time t7, processing continues from time t8 onwards according to the correct instruction processing flow.

In this case, the pipeline loss cycles due to the appearance of a branch instruction are: 3 cycles when the prediction is correct (branch GO) and 3 cycles when the prediction is unsuccessful (branch NOGO).

When the branch GO rate γ and the predicted hit rate are α, in this case, γ=α, and the predicted hit rate is 5 minutes and 5 minutes. Therefore, γ=α=0.5, and the average loss cycle per branch instruction is 3×γ+3×(1−γ)=3 cycles.

On the other hand, FIG. 17 shows the flow of instruction processing when prediction is performed based on the past results of the same branch instruction described above in instruction prefetching of a branch instruction. That is, the branch instruction BC is decoded at time t4, and the address table of the branch instruction is searched, and depending on the presence or absence of the instruction or the prediction of the instruction of the branch instruction flag, the branch instruction B1 on the branch GO side is preempted or the instruction B1 on the branch NOGO side is preempted. Determine whether to prefetch instruction A1. Similarly to the previous time, address generation for prefetching the subsequent instructions A1, A2, and A3 on the branch NOGO side is started at times t2, t3, and t4. At times t6 and t7, generation of addresses for subsequent instructions B1 and B2 or A4 and A5 of instruction prefetching based on prediction is started. At time t7, time t is determined based on the branch condition determination result.
From 8 onwards, processing continues according to the correct instruction processing flow.

In this case, the loss cycles in the pipeline due to the appearance of a branch instruction are: 3 cycles when the prediction of branch GO is correct; 3 cycles when the prediction of branch NOGO is correct;
0 cycles: When predicting branch GO and failing 3 cycles: When predicting branch NOGO and failing
It is 6 cycles. Therefore, assuming that the branch GO rate γ = 0.5 and the predicted hit rate α = 0.8, the average loss cycle per branch instruction is 3・γ・α+0・(1-γ)・α+3・γ・(1 -α) +6・(1−γ)・(1−α)=2.1 cycles are obtained.

Therefore, this conventional invention uses the principle that a high prediction accuracy rate can be obtained when predictions are made based on past results of the same branch instruction.
There is some improvement compared to the process shown in FIG. 16, which predicts GO. However, even with this improved invention, in the case of predictive intermediate branch GO, three loss cycles are still required and cannot be reduced any further. Therefore, if a branch instruction occurs, a loss cycle will occur even if the prediction is correct.

18, 19, and 20 show the flow of instruction processing according to the present invention.

In addition to the function of reading instructions from a storage device, the instruction processing unit IC stage in the present invention indexes a branch history table and detects whether the address of the instruction to be read is registered in the branch history table. If it is registered, it reads the corresponding branch information, and if it is not registered, it has a function of generating an address for prefetching a subsequent instruction.

Referring to FIGS. 18 and 19, the operation of branch instruction BC at time t1 is performed as follows. First, the branch history table is indexed at the same time as the branch instruction BC is read from the instruction cache memory. If the instruction address of the branch instruction BC is registered, the corresponding branch information is read. As a result of analyzing the branch information, branch GO
Start pre-fetching the branch destination instruction B1 according to the branch destination address included in the branch information as a side prediction, or branch as a branch NOGO side prediction.
It is determined whether to generate an instruction address for the instruction A1 on the NOGO side and start prefetching the instruction A1. The period from then until time t5 is the prediction period of the branch instruction BC, in which the subsequent instruction on the prediction side is preempted and the branch condition is determined at time t5. When the prediction is correct, the first
As shown in FIG. 6, processing continues without any disturbance in the flow of the pipeline. When prediction fails, the branch history table is updated at time t6, as shown in FIG. 19, and then the instruction is taken out from the correct instruction flow. In this case, the pipeline loss cycles due to the appearance of a branch instruction are: 0 cycles when the prediction is correct and 5 cycles when the prediction fails. In this case, since not only the branch direction but also the branch destination address is predicted, the prediction accuracy rate α is slightly lower than when predicting only the branch direction, but the rate is insignificant. Therefore, prediction accuracy α=
Assuming 0.8, the average loss cycle per branch instruction is 0·α+5(1−α)=1 cycle, which is a significant improvement over the conventional technology.

Referring to FIG. 20, it shows the execution when the branch GO prediction of the BCT instruction fails.
Although it is executed in the same manner as the branch instruction BC in FIG. 19, since the instruction BCT does not update the branch history table at time t6, the extraction of the correct instruction starts from time t6. That is, when branch prediction GO fails, the BCT instruction is executed one cycle earlier than branch instructions other than the BCT instruction.

Referring to FIG. 21, there is shown a flow of instructions of a program forming a loop using the BCT instruction to manage the number of loops. In FIG. 21, while the instruction BCT is being executed in this loop, the instruction BCT uses the GO held in the branch history table.
According to the side branch information, the branch prediction is successful and executed without loss cycles. The instruction BCT when escaping from the loop is a BCT GO prediction failure, and the failed instruction is immediately fetched without updating the branch history table. When this loop is re-entered by the flow of the program, the branch information of the instruction BCT indicates the prediction on the GO side, so the loop can be executed without loss cycles.

If the present invention is not applied, one cycle is lost to update the branch information of the instruction BCT in the branch history table to the branch NOGO side when exiting the loop.
It also takes an extra 5 cycles to enter the loop again and execute BCT for the first time.

In this invention, a branch history table that stores the address of a branch instruction and branch information including the branch destination address of the branch instruction as a pair is indexed when an instruction is prefetched. Thereafter, by prefetching the next instruction at the branch destination address, the instruction word can be prefetched according to the description in the branch history table without decoding the instruction.

Furthermore, by updating the branch information in the branch history table based on the properties of the BCT instructions, an instruction queue is formed in the instruction buffer according to the execution path of the instructions, thereby controlling the pipeline of the information processing system. This has the effect that the BCT instruction can be executed with extremely few loss cycles.

[Brief explanation of drawings]

FIG. 1 is a diagram showing an embodiment of the present invention, FIG. 2 is a diagram showing a detailed configuration of the branch history table 410 in FIG. 1, and FIG. 3 is a diagram showing the storage unit 50 in FIG.
1 and 502, FIG. 4 is a diagram showing the detailed configuration of the test circuits 503 to 506 in FIG. 2, and FIG. 5 is a diagram showing the arrangement of instruction words in the instruction storage circuit 408 in FIG. 1. 6 is a diagram showing the detailed configuration of the priority circuit 507 in FIG. 2, FIG. 7 is a diagram showing the storage format of the branch information buffer 413 and register 416 in FIG. 9 is a diagram showing the detailed configuration of the prediction confirmation circuit 420 in FIG. 1, and FIG. 10 is a diagram showing the storage format of the registers 417 to 419 in FIG. A diagram for explaining the correspondence with branch information in the table 410, FIG. 11 is the table 41 in FIG.
12 is a diagram for explaining the instruction prefetching operation by 0, FIG. 12 is a diagram for explaining the operation up to the start of the instruction prefetching operation when prediction fails, and FIG.
14 is a diagram showing the detailed configuration of the instruction prefetch control circuit 424 shown in FIG. 1, and FIG. 15 is a diagram for explaining the operation up to the start of the instruction prefetch operation when the prediction GO of the BCT instruction fails. FIG. 15 is the instruction processing. 16 and 17 are diagrams showing the flow of instruction processing using the conventional prediction method.
Figure 19 shows the flow of instruction processing when branch instruction prediction is successful; Figure 19 shows the flow of instruction processing when branch instruction prediction fails; Figure 20 shows the flow of instruction processing when branch instruction prediction fails;
21 is a diagram showing the flow of instruction processing when branch GO prediction of a BCT instruction fails in the present invention, and FIG. 21 is a diagram showing the flow of instructions of a program that configures a loop using BCT instructions. . 1 to 21, 401...instruction address generation circuit, 402...instruction address translation circuit, 403...instruction decoding circuit, 404...operand address generation circuit, 405...operand address translation circuit, 406... ...Operand reading circuit, 407...Instruction execution circuit, 408...Instruction storage circuit, 409...Instruction buffer, 410...
Branch history table (BHT), 411...Instruction address register (IAR), 412...Instruction address addition circuit, 413...Branch information buffer, 4
14...Instruction alignment circuit, 415...Branch information switching circuit, 416...Branch information register (QR ₀ ), 4
17...Branch information register (QR ₁ ), 418...
Branch information register ( _QR2 ), 419...Branch information register ( _QR3 ), 420...Prediction confirmation circuit, 4
21...Address generation circuit, 422...Selection circuit, 423...Register (WR), 424...Instruction prefetch control circuit, 425...Flip-flop, 501, 502...Storage unit, 503, 50
4,505,506...Test circuit, 507...
Priority circuit, 508... Selection circuit, 50
9...OR circuit, 601-604...AND circuit, 605-608...OR circuit, 701...matching circuit, 702...large/small comparison circuit, 703...AND circuit, 801...matching circuit, 802-803
...Flip-flop, 804-807...True/false circuit, 808-813...AND circuit, 814...
...OR circuit, 1201...Flip-flop, 1
202-1205...Truth circuit, 1206...AND circuit.

Claims (1)

[Claims] 1. In an instruction prefetch device in an information processing system that counts the count value held in a designated general-purpose register, determines whether or not to branch based on the count result, and executes a count branch instruction, an instruction execution means for sequentially executing instructions; a branch history table means for storing a plurality of pairs of information specifying an address of a branch instruction and branch information including a branch destination address of the branch instruction; and a branch history table means for performing an instruction prefetch operation. checking means for checking whether information specifying the address of a branch instruction to be prefetched in the instruction prefetching operation is registered in the branch history table means; instruction prefetch control means for reading corresponding branch information from the history table means and controlling the instruction prefetch operation to continue in accordance with the branch information; a first determining means for determining whether the branch information matches the branch information, a second determining means for determining whether the branch instruction is a counting branch instruction, and a second determining means for determining whether the branch instruction is a counting branch instruction; a third determining means for determining whether or not the has taken a branch; and when the determination results in the first determining means indicate a match, changing the branch information corresponding to the branch instruction in the branch history table means; Not the first
and a first determination result indicates a mismatch, a second determination result indicates a counting branch instruction, and a third determination result indicates a counting branch instruction according to the determination results of the first, second, and third determination means. A second control that does not change the branch information corresponding to the counted branch instruction in the branch history table means when the instruction execution means indicates that the counted branch instruction did not take a branch, and a first determination result. A third step of updating the branch information corresponding to the branch instruction in the branch history table means based on the execution result of the branch instruction when the second determination result indicates that there is a mismatch and the second determination result indicates that the branch instruction is not a counting branch instruction.
control, when the first determination result indicates a mismatch, the second determination result indicates a counting branch instruction, and the third determination result indicates that the counting branch instruction executed a branch in the instruction execution means. a fourth updating branch information corresponding to the counting branch instruction in the branch history table means based on the execution result of the counting branch instruction;
1. An instruction prefetching device comprising update control means for controlling.