Browse Prior Art Database

Correlation-Based Branch Target Buffer Design

IP.com Disclosure Number: IPCOM000104329D
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 122K

Publishing Venue

IBM

Related People

Pan, ST: AUTHOR [+2]

Abstract

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.

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

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
 ...