Browse Prior Art Database

Multiple Entry Joint Recursive Branch Predictor

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

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

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.

Multiple Entry Joint Recursive Branch 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 potential for a JRBP to outpredict a marginal predictor is
based on the superior handling of a BWG.  If the JRBP is perfect,
then a marginal predictor based on the pattern of branch/action for
one branch within the branch set will also be perfect.  The nature of
the superiority of the JRBP, when different branch are correlated, is
twofold,

o   a single JRBP error establishes a pattern of several other
    branches and with different re-entry points, based on the branch
    occurrence that incurred a BWG, multiple potential correlated
    patterns are available, and

o   these re-entry points are more easily discernible in the overall
    pattern as the predictor involves multiple branches.

MULTIPLE ENTRY JOINT RECURSIVE BRANCH PREDICTOR - The means of
implementing multiple-entry points that recover from BWGs is
straightforward.  Consider a branch with variable action within the
branch set associated with a JRBP.  Let this branch be B sub 1.
Within the predictor, B sub 1 occurs N sub 1  times.  Of these, it
has the "first action" n sub 11 times and the "second action" n sub
12 times.  The "first action" and "second action" refer canonically
to the associated entries within the BHT which contains the targets
for t...