Browse Prior Art Database

Entering a Joint Predictor

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

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+3]

Abstract

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 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.

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

Entering a Joint Predictor

      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 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.

      A simple mechanism can be used to monitor the actions of the
branch and to determine a marginal predictor for all these TYPE-B
branches.  At the same time a determination can be made concerning a
set of close-in branches that form a set of joint recursively used
branches.  These actions can be analyzed to determine a bit string
that may qualify as a JOINT RECURSIVE BRANCH PREDICTION bit string.
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 branches encountered once the
action at the first TYPE-B branch is specified.  There may be any
number of intervening TYPE-A branches but the name of next TYPE-B
branch is determined totally by the action at the last TYPE-B branch.
Thus a correct prediction of a TYPE-B branch specifies the TYPE-B
branch that a single bit-string is predicting as long as all TYPE-A
branches are handled by some other agency.

A Joint Recursive Branch Predictor, JRBP, has the following set of
properties:

o   It should continue with the prediction scheme if the prior
    prediction is correct.

o   It should wrap around so that a finite length predictor can
    continue to predict indefinitely as long as it is correct.

o   It need not synch with addresses of the branches, except at a
    error, because

    -   A recursive predictor of a branch is defined as a sequence of
        the actions of branches and can be used to predict the next
        action of the next branch in conjunction with a BHT which
        will supply the rela...