Browse Prior Art Database

Use of Tags to Coordinate Type-A and Type-B Branch History Table

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

Publishing Venue

IBM

Related People

Ekanadham, J: AUTHOR [+2]

Abstract

A Branch History Table (BHT) has an unfortunate characteristic that it combines all aspects of branch behavior within a single entity and relates it to the presence or absence of the branch address. If a branch address is present in the BHT then the branch will be assumed taken to a TARGET ADDRESS associated with the branch address in the table. The frequency of taken branches, as one in every six executed instructions, makes the number of branch addresses large. As the BHT controls the I-FETCHING for the processor and must respond to each successive I-FETCH to make the determination as to the presence of a branch within that I-FETCH unit a BHT is often competing with cache for space within the speed critical area of processors.

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

Use of Tags to Coordinate Type-A and Type-B Branch History Table

      A Branch History Table (BHT) has an unfortunate characteristic
that it combines all aspects of branch behavior within a single
entity and relates it to the presence or absence of the branch
address.  If a branch address is present in the BHT then the branch
will be assumed taken to a TARGET ADDRESS associated with the branch
address in the table.  The frequency of taken branches, as one in
every six executed instructions, makes the number of branch addresses
large.  As the BHT controls the I-FETCHING for the processor and must
respond to each successive I-FETCH to make the determination as to
the presence of a branch within that I-FETCH unit a BHT is often
competing with cache for space within the speed critical area of
processors.

      One can classify branches as to whether they are variable in
action or constant in action and ignore that aspect associated with
TAKEN/NOT TAKEN.  Let us define a branch as TYPE-A if it is constant
in action and always taken to the same target.  Let us define a
branch as TYPE-B if it is sometimes taken and not a TYPE-A branch.
Almost all the errors of prediction of a BHT occur for TYPE-B
branches and such branches are best predicted by a means that
separates the prediction of the branch action from the TABLE that
contains the potential targets of the branch.  The advantage of this
TYPE-B TABLE is that it anticipates the inevitable variability of the
branch and can continue to predict correctly even when an
action/target change has occurred for the branch.

There is now a need for two TABLES:

o   TYPE-B Branch TABLE

o   TYPE-A Branch TABLE

The TYPE-B Branch TABLE may itself be broken up into parts relating
to the predictor that is used.  A branch is said to be predicted
marginally, that is, by itself if the predictor of the branch is
associated with the single branch.  A bit string may specify the
pattern of TAKEN/NOT TAKEN decisions or a mechanism that generates
that decision based on historical action can be part of the TABLE.
The branch may be predicted jointly with other close in branches and
a common bit string or mechanism can be employed to predict the
successive occurrences of branches within a Joint Branch Group.

      The ability to predict a group of branches jointly using a
single bit string while omitting intervening branches can be done if
the omitted branches are all TYPE-A branches.  The best way to
visualize the program behavior is to imagine that the course of a
program is plotted on a two-dimensional graph where the progress of
the program represents the abscissa and the branch last executed
represents the ordinate.  An arrow connects the succession of
branches and we can further distinguish the TYPE-A branches by
coloring them distinctively, red say.  Such a representation is
called the CONVOLUTION OF CODE REPRESENTATION.  From this diagram we
see that there is no variability between TYPE-B...