Browse Prior Art Database

# Joint Recursive Branch Prediction - Determining the Predictor

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

IBM

## Abstract

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

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

Joint Recursive Branch Prediction - Determining the Predictor

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 related target address.

The ability to operate within a joint target set of a set of
branches with the same predictor format used for a single
branch is a result of the observation that each branch will
specify a target that dictates the next branch that is
encountered if the target is correct.  Just as joint
distributions contain additional information than marginal
distributions, the use of the joint recursive predictors of
prespecified length can be superior to the operation of
individual recursive predictors on the marginal sequences of
individual branch actions.
o   The predictor needs to have at least one occurrence of each
action of each branch within the loop so that the recovery
mechanism can recover to the position specified by the correct
action following an error.

The success of a JRBP, when it applies, warrants a means to
generate, 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 model this phenomena in a systematic way so
that the model can generate the candidates for the predictor, tens of
thousands of branches.  As yet, another example of analysis of
sequences within an instruction trace affords the opportunity for a
predictor-generating mechanism to determine a joint recursive branch
predictor for a set of branches.  The main idea is to model the loop
and to create the predictor, with a low error rate, based on the
model of the loop.  For a loop with a single closing branch B., the
identity of the B is derived from the stack mechanism that identifies
the loop.  The subsequences of branch actions between occurrences of
B can form the building blocks of the pr...