Browse Prior Art Database

Technique for Minimizing Branch Delay Due to Incorrect Branch History Table Predictions

IP.com Disclosure Number: IPCOM000049475D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Rao, GS: AUTHOR

Abstract

A Branch History Table (BHT) is a mechanism used for predicting the outcome and target address of branches before the branch is decoded, so that the appropriate instruction stream can be fetched ahead of the time it is needed at the decoder. For easy and economical implementation a BHT keeps information pertaining only to the taken branches encountered. When an instruction fetch is initiated, the BHT is accessed with the address of the instruction parcel (usually double word or quad word) that is being fetched. The BHT predicts the target address of the next taken branch instruction in the parcel (assuming that the outcome of a branch decision is the same as that on the previous occurrence of that branch).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Technique for Minimizing Branch Delay Due to Incorrect Branch History Table Predictions

A Branch History Table (BHT) is a mechanism used for predicting the outcome and target address of branches before the branch is decoded, so that the appropriate instruction stream can be fetched ahead of the time it is needed at the decoder. For easy and economical implementation a BHT keeps information pertaining only to the taken branches encountered. When an instruction fetch is initiated, the BHT is accessed with the address of the instruction parcel (usually double word or quad word) that is being fetched. The BHT predicts the target address of the next taken branch instruction in the parcel (assuming that the outcome of a branch decision is the same as that on the previous occurrence of that branch). This target address determines the address of the next instruction parcel to be fetched and the appropriate instruction fetch is initiated. If no taken branch is predicted in a parcel the next sequential parcel is fetched.

When the branch action is determined at execution time, the BHT is corrected, if necessary: if the branch was predicted to be taken but actually was not taken, the corresponding entry is removed from the table; if the branch was predicted not taken but the branch was actually taken, then a new entry is made in the table.

When the branch prediction by the BHT is correct, there is no delay due to that branch (assuming that there is no delay in the cache). Associated with every incorrect prediction made by the BHT there is a delay because the correct instruction stream has to be fetched. In present schemes the verification of the BHT's prediction of the branch outcome is done at the time of execution of the predicted branch. Thus, knowing the branch outcome before the branch is executed results in reduced overall branch delay. The proposed solution for reducing branch delay is as follows:

(a) to introduce a very accurate decode-time branch

prediction mechanism so that the outcome of a branch

is known with a high degree of accuracy before the

branch is resolved at execution time, and

(b) to use an appropriate algorithm for the coordination of

the two predictions (one by the mechanism and the other

by the BHT) to minimize the impact of wrong predictions

by either.

Such a decode-time prediction mechanism should be able to predict with a high degree of accuracy the branches th...