JPS61175733A - Control system of branch estimation - Google Patents

Abstract

PURPOSE:To reduce the deterioration of performance of a branch instruction due to the failure of branch prediction by preventing the invalidation of an entry corresponding to a branch predicting buffer in a branch failure mode with a branch instruction for loop control. CONSTITUTION:An instruction extracting address set at a virtual address register 1 is sent to the extracting instruction address registers 9 and 10 which hold the address range of the extracted instruction. When the contents already set to the branch predicting buffers 4 and 5 go to wrong owing to the fact that a branch instruction does not exist any more due to the rewriting of instruction, that the branching destination address is changed and that the success of branch is changed to the failure, etc., the effective display bits in a branching predicting buffer K3 are reset. Then, the corresponding entry is invalidated. However the corresponding entry is never reset even though the branch fails with a control branch instruction of a DO loop used by an FORTRAN program, etc. since the same loop is used many times.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a branch prediction control method for increasing the speed of branch instructions.

[Conventional technology]

As a technique for speeding up branch instructions, there is a method of storing a history of branch instructions and predicting branch success/failure and branch destination based on past results. (For example, I BEECOMPUTE&
1984 January issue P6-P22) [Problems to be solved by the invention] The above-mentioned branch prediction uses an instruction word address containing a branch instruction,
A branch history buffer is provided to hold the branch destination address of the branch instruction, and when an instruction is fetched and the fetched instruction includes a branch instruction, the branch destination address is obtained. In this branch prediction buffer, the contents are modified based on the result every time a prediction fails when a branch instruction is executed.

However, with a loop control branch instruction used in a DO loop of a 7 autorun program, if the loop is used again, the probability of a successful branch is high. Therefore, when exiting the loop, the branch prediction fails (predicted success but actually failed), and if the branch prediction buffer is updated, the prediction will fail again if this loop is executed again. There is.

[Means for solving problems]

That is, in the branch prediction control method of the present invention, in a branch instruction for loop control, when a branch fails.

The feature is that the content of the corresponding entry in the branch prediction buffer is not invalidated.

〔Example〕

Next, the present invention will be explained in detail with reference to the drawings.

Referring to FIG. 1, one embodiment of the present invention includes a virtual address register 1 that stores a virtual address given from the outside.
, a switching circuit 2 that selects and outputs either the address from this register 1 or the address obtained by adding the fetch instruction address KrtJ; A branch history buffer (K) 3 that stores the address of the branch instruction, a branch history buffer that holds the branch destination address at the location specified by the lower bit, ("14. Contents of the branch history buffer (K) 3 and Comparing circuits 5 and 6 that compare the address from the register 1; a switching circuit 7 that selects and outputs the output of the branch history buffer (D) 4 in response to detection of a match between either of the comparing circuits 5 and 6;
A store address register 8 that holds the write address to memory by an at-a-toa instruction, a fetch instruction address register 9 that holds the upper limit address of the address range of the fetched instruction, and the lower limit address of at least one set of this address range. a fetch instruction address register 10 holding
Counter 1 that adds rll to the contents of this register 10
1. Comparison circuit l for comparing the address from the register 8 and the address from the register 9. 2. A comparison circuit 13 that compares the address from the register 8 and the address from the register IO, and an AND gate 14 that takes the AND of the outputs of these comparison circuits 12 and 13.
It consists of The register 10 may be composed of a resistor filter.

Next, the operation of one embodiment of the present invention will be explained in detail.

The virtual address generated for fetching the instruction is sent to a cache memory (not shown here) and at the same time the virtual address register IK is set. The output of the virtual address register 1 is passed through the switching circuit 2 to a branch history buffer ([Q3] that holds the address of the branch instruction and a branch history buffer β4 that holds the branch destination address).
supplied to

If the instruction to be fetched according to the contents of the address register 1 includes a branch instruction previously fetched and the branch instruction is a successful conditional branch or an unconditional branch, the branch destination address is obtained from the branch prediction buffer 4. Branch prediction buffers 3 and 4 are configured at two levels. Comparison circuit 5 or 6
Depending on whether a match of the retrieval address was detected,
The output of the branch history bar 77◎ is selected by the switching circuit 7 and sent out together with the branch prediction bit signal. By fetching an instruction using this branch predicted address output, the branch destination instruction word can be fetched at high speed, and the branch instruction can be executed at high speed.

The instruction fetch address set in virtual address register IK is further sent to fetch instruction address registers 9 and 10 which hold the address range of the fetched instruction. When the first instruction of the branch destination is fetched, the fetch address is set in both registers, but in the second and subsequent fetches, only the fetch instruction address register ([J) 9 is set.

On the other hand, each time one fetched instruction is executed, the contents of the fetched instruction address register (L) 10 are incremented by 1 through a counter 11. As a result, the upper and lower limits of the address of the fetched instruction are maintained. Store address register 8
holds the address written to memory by a store instruction. This store address and the range of the fetched instruction are determined by comparison circuits 12 and 13.

It is detected whether the preempted instruction word has been rewritten by the preceding store instruction. If rewriting is detected, processing is restarted from re-fetching the instruction. An instruction bar that holds fetched instructions.

7a and fetch instruction address registers 9 and 10,
Three sets of branch instructions are prepared for speeding up the branch instruction, and each time the instruction stream is changed by a branch instruction, another set is controlled to be used.

Branch instructions that have not been set in the minute history buffer are set as follows. If there is no corresponding entry of a successful conditional branch or an unconditional branch instruction in the branch prediction buffer 9 and IOK, the address of one branch instruction itself is set from the fetch instruction address register (L) 10 to the virtual address register 1 when the branch instruction is executed. Next, by calculating the address of the branch instruction, the fetch instruction address register 10
The branch destination address set in another register in the register file is retrieved and set in the branch prediction buffer (D) 4 specified by the virtual address register l, and the virtual address is also stored in the branch prediction buffer (K) 3. The contents of register 1 are set. A known replacement algorithm is used to determine which level of the two-level prediction buffer to set.

On the other hand, branching side bag 7a9. If the content that has already been set in IOK becomes invalid because it is no longer a multi-branch instruction due to instruction rewriting, the branch destination address has been changed, or a branch success has changed to failure, the branch prediction The validity indicator bit (V bit) in the buffer (K) 3 is reset to invalidate the corresponding entry. But FOR,T
Branch instructions for controlling DO loops used in R, AN programs, etc. do not reset the corresponding entry even if the branch is unsuccessful, since the same loop is used many times.

In other words, branch prediction always fails when exiting a DO loop, but if you invalidate the corresponding entry in the branch history buffer each time, branch prediction will fail even when this loop is used again, which will reduce performance. This is because it decreases.

Referring to FIG. 2, performance during branch prediction is compared with the conventional method. When branch prediction is successful, branch instruction execution time is significantly improved. In the conventional method, the success/failure of a branch is determined in the operation cycle of a conditional branch instruction. Since the address calculation cycle for the branch destination instruction starts from the cycle in which the branch is successful, four machine cycles are required from the completion of execution of the branch instruction (end of the E cycle) to the end of the E cycle of the branch destination instruction. On the other hand, when branch prediction is performed, by indexing the branch prediction buffer using the branch instruction fetch PI pesile, the branch destination address can be obtained if the fetched instruction includes a branch instruction predicted to be a successful branch. . This address is used to fetch and decode the branch destination instruction, and the branch destination instruction is executed in the cycle following the E cycle of the branch instruction. The execution time of a branch instruction is four times faster than that of a branch instruction.

〔Effect of the invention〕

The present invention has the effect that the performance of multi-branch instructions can be improved by not invalidating the corresponding I) of the branch prediction buffer when a branch fails in branch instructions for loop control.

[Brief explanation of drawings]

FIG. 1 is a diagram showing an embodiment of the present invention, and FIG. 2 is a diagram showing the effect of branch prediction. 1 and 2, 1...virtual address register, 2, 7...switching circuit, 3...
...Branch prediction buffer (to), 4...Branch prediction buffer (to), 5゜6.12.13...Comparison circuit, 8...Store address register , 9・
...Fetch command address register (b), lO...
...Scattered instruction address register, 11...
·counter. A: Ato Shimata it Sho "So" I Full I Ni At Shisu + □i + 1 cycle C: Ki 4 shares 7 Seven pronged buoy 1 Noshi E: Martyr's death's' Cycle 4 I 9 2 Glue d

Claims (1)

[Scope of Claims] An information processing device comprising a branch history buffer that holds an address of a branch instruction and a branch destination address of the branch instruction, wherein in a branch instruction for loop control, when the branch fails, the branch A branch prediction control method characterized by not invalidating the contents of a corresponding entry in a history buffer.