Browse Prior Art Database

Polymorphic Branch Predictor

IP.com Disclosure Number: IPCOM000113061D
Original Publication Date: 1994-Jul-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 6 page(s) / 193K

Publishing Venue

IBM

Related People

Pan, ST: AUTHOR [+2]

Abstract

Branch delay is a well-known problem in today's high performance superscalar and superpipelined processor designs. A common technique used to alleviate this problem is to predict the direction of a branch prior to its execution. The prediction using an N-bit up-down counter (called counter-based branch prediction) (1) in particular, has been reported as an effective scheme for predicting the direction of a branch. Fig. 1 shows the implementation using a two-bit up-down counter. Its state-transition is also shown in Fig. 1. The accuracy of the counter-based branch prediction is generally limited by branches whose future behavior is also dependent upon the history of other branches, in other words, by "correlated" branches.

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

Polymorphic Branch Predictor

      Branch delay is a well-known problem in today's high
performance superscalar and superpipelined processor designs.  A
common technique used to alleviate this problem is to predict the
direction of a branch prior to its execution.  The prediction using
an N-bit up-down counter (called counter-based branch prediction) (1)
in particular, has been reported as an effective scheme for
predicting the direction of a branch.  Fig. 1 shows the
implementation using a two-bit up-down counter.  Its state-transition
is also shown in Fig. 1.  The accuracy of the counter-based branch
prediction is generally limited by branches whose future behavior is
also dependent upon the history of other branches, in other words, by
"correlated" branches.  The correlation-based branch prediction
scheme reported in (2) enhanced the counter-based scheme by
considering the "branch correlation".  Fig. 2 shows the logical and
the physical implementations of the correlation-based branch
prediction.  Although the correlation scheme outperforms the counter
scheme in most of the benchmark simulations, its accuracy could be
degraded by address conflict when a small branch prediction table is
used.

      The hybrid approach reported recently (3) resolves this problem
by combining the two schemes with small tables.  This scheme
effectively reduces the address conflict by using two separate
prediction tables:  one for the counter-based branch prediction and
the other one for the correlation-based branch prediction.  The
hybrid scheme requires the compiler to set a bit in the branch
instruction at the compile time for directing the hardware to choose
one of the schemes for branch prediction at the run time.

      All the branch prediction schemes mentioned so far are
classfied as "dynamic" branch predictions, since the prediction is
done with the assistance of some prediction hardware at the run time.
"Static" branch prediction 1., on the other hand, does the prediction
at the compile time.  With this approach, the compiler does the
prediction based on its best knowledge about the behavior of a branch
(for example, the profile information of previous program
executions).  Although static branch predictions are not adaptive to
the dynamic behavior of some branches, they do predict well for
branches whose directions are rather steady.  Like, for example,
loop-closing branches or branches based on some exception or error
conditions.  Most of the time a loop-closing branch is taken.  If an
exception or error condition rarely happens, the branch based on its
occurrance will frequently go in one fixed direction.  These kind of
branches commonly appear in scientific or kernal code.  Dynamic
predictions are not necessary for these branches, since static
predictions are good enough to obtain high accuracy.  But, if their
predictions are not managed properly in a dynamic prediction
environment, unnecessary noise like address c...