Browse Prior Art Database

Simplifying a Branch History Table

IP.com Disclosure Number: IPCOM000106777D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 76K

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+2]

Abstract

A branch history table (BHT) is a prefetching mechanism that directs the prefetching to the target of taken branches so as to create the necessary I-Fetching for the processor. A delay ensues in processor organizations that have determined that the next instruction based on the action of a decoded branch is not available and the fetching of that instruction causes the decoder of the processor to be delayed. A related delay associated with processors that use a BHT is to find that the action of the branch has been mispredicted and the wrong instruction prefetched.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Simplifying a Branch History Table

      A branch history table (BHT) is a prefetching mechanism that
directs the prefetching to the target of taken branches so as to
create the necessary I-Fetching for the processor.  A delay ensues in
processor organizations that have determined that the next
instruction based on the action of a decoded branch is not available
and the fetching of that instruction causes the decoder of the
processor to be delayed.  A related delay associated with processors
that use a BHT is to find that the action of the branch has been
mispredicted and the wrong instruction prefetched.  The result is
that following the resolution of the branch an I-FETCH to acquire the
correct target causes all the cycles of decoding following the branch
and the idle cycles associated with the fetching of the correct
target to be penalty cycles for the Branch Wrong Guess.

      Branches can be thought of as TYPE-B, branches with variable
action/target and TYPE-A, branch which are taken and have constant
action/target.  All BHT errors are associated with TYPE-B branches
and TYPE-B branches can best be handled by the decoder in terms of
generating a hedge-fetch to their target assuming for decode purposes
that they are not taken.  The resulting penalty for a decoder-guess
is smaller and balances out with the BHT advantage when they are
taken once the BHT error rate on such branches are brought into
consideration.  TYPE-A branches once discovered have a direct benefit
when handled on an error free basis within the processor.

      To accomplish all this it is necessary to keep a list of TYPE-A
branches and their targets which we shall call a TYPE-A BHT and a
list of TYPE-B branches.  The list of TYPE-B branches is needed:

o   to avoid contaminating the TYPE-A BHT once the nature of the
    branch is determined, and

o   as input to the decoder to prompt hedge fetching once the target
    of the branch is determined.

It is necessary for the decoder to identify TYPE-B branches
explicitly as there are a class of branches, branches which are...