Browse Prior Art Database

Joint Recursive Branch Prediction - Screening with Marginals

IP.com Disclosure Number: IPCOM000105792D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 107K

Publishing Venue

IBM

Related People

Ekanadham, K: AUTHOR [+3]

Abstract

Given a program which executes a succession of branches, how can the succession of branches and their actions be systematized so as to formulate a joint recursive branch predictor, if that is an appropriate prediction strategy? The problem of analyzing a trace containing tens of thousands of branches, to determine if an exotic form of branch prediction should be undertaken, involves the same steps that a hardware mechanism could undertake to establish a joint recursive branch predictor. The key link is that a predictor of length m involving all the actions of n branches in a loop would have certain marginal properties with respect to individual branches and their marginal predictors (BHT, Pattern Predictors).

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

Joint Recursive Branch Prediction - Screening with Marginals

      Given a program which executes a succession of branches, how
can the succession of branches and their actions be systematized so
as to formulate a joint recursive branch predictor, if that is an
appropriate prediction strategy?  The problem of analyzing a trace
containing tens of thousands of branches, to determine if an exotic
form of branch prediction should be undertaken, involves the same
steps that a hardware mechanism could undertake to establish a joint
recursive branch predictor.  The key link is that a predictor of
length m involving all the actions of n branches in a loop would have
certain marginal properties with respect to individual branches and
their marginal predictors (BHT, Pattern Predictors).  These marginal
properties are detectable on simpler a basis and thus screen
potential loops so that they need not be considered further.  The
identification that branches share a loop and the efficacy of
marginal predictors determine the potential efficacy of a joint
predictor and some of its length-determining characteristics.

      The success of a joint recursive branch predictor, when it it
is appropriate to apply it, warrants a means to establish, in a
systematic way, a test for a joint recursive predictor when it is
appropriate.  The fundamental idea is that a set of branches within a
loop can exhibit a mutual pattern of behavior that allows their
actions to be predicted with a high degree of accuracy.  It becomes
important to define this phenomena in a systematic way so that the
phenomena can be tested in situations where there are tens of
thousands of branches.

FIRST STEP - DETERMINING THE NUMBER OF BRANCHES - Employed is a
branch stack mechanism to determine that, in a long sequence of
branch executions, only a small number of distinct branches were
executed.  Let lambda represent the LRU branch-stack depth to which
one had to go before all branches in a long sequence could be found.
As both multi-action (TYPE B) branches and single action (TYPE A)
branches are included, a classification of the loop can be made in
terms of lambda.

      If lambda = 1, then we have a simple loop closing branch.  If
lambda = 2 and both branch are TYPE B, then each branch closes the
loop, but the fall-through on one leads to the other.  In the sequel
we shall consider a prediction mechanism for a fixed value of lambda,
say, n.

PREDICTOR FOR A SET OF n BRANCHES IN A LOOP - Let us consider the
branch trajectory of a non-self-modifying program as a sequence of
branches, B sub i, and their actions, A sub i.  Clearly {B sub i, A
sub i} determine B sub <i+1> but they do not determine A sub <i+1>.
The role of the prediction mechanism is to predict A sub <i+1> from
the historic information.

      A predictor must have the following set of properties:

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

o   It shoul...