Correlation-Based Branch Target Buffer Design

Correlation-Based Branch Target Buffer Design

      Branch delay is a well-known problem in today's high
performance proces sor design.  A conventional method used to
alleviate this problem is to predict the outcome of a branch and
provide the target address using a Branch Target Buffer (BTB).  A BTB
is a table which retains the informa tion of previously executed
branches.  The table is organized similar to a set-associative cache
memory.  In its simplest form, a BTB keeps in each of its entries the
branch address and the target address of a "taken branch".  During
the instruction fetch cycle, the table is searched for a match with
the instruction fetch address (IFA).  If a match is found (hit), a
taken branch is predicted to occur and the corresponding target
address in the BTB is used to redirect the subse quent instruction
fetch.  If there is no match (miss), the instruction fetch continues
with the next sequential address.  Note that an entry is only added
to the table when a taken branch is executed.  It is obvious that a
back-out mechanism must be equipped with the machine in order to
restore the proper state for correct instruction fetch when
misprediction occurs.  There are many variations in the design of a
BTB.  One of the variations is to maintain the information of "not
taken branches" as well.  In this case, certain prediction
information must also be kept along with each entry.  This
information will be used to predict the direction of the branch.

      The current invention describes a novel idea in branch target
buffer design.  The idea is to decouple the branch prediction from
the BTB and independently implement the prediction using
"correlation-based" branch prediction [*].

      In describing the new idea in BTB design, we use a 4-way BTB
and a Branch Prediction Table (BPT) which implements the
correlation-based branch prediction.  A complete discussion of the
operation of the correlation-based branch prediction can be found in
[*].  Note that the figure is only used as a blueprint to explain the
proposed new design.  The actual implementation is certainly not
limited to the one shown in the figure.  The outline of the proposed
method is described as follows.

1.  BTB is used in conjunction with a BPT.  The information kept in
    the BTB is the branch addresses and the corresponding target
    addresses (shown as b@'s and t@'s in the figure) of executed
    branches.  The BPT implements an (M,2) correlation prediction
    scheme where M is the correlation step (please refer to [*]  for
    the definitions).  The figure shows an implementation for M
    equals to 2.  The size of the BPT is irrelevant to that of the
    BTB.

2.  During the instruction fetch cycle, both tables are accessed
 ...