Correlation-Based Branch Target Buffer Design
Original Publication Date: 1993-Apr-01
Included in the Prior Art Database: 2005-Mar-19
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.
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
...