Browse Prior Art Database

The Correlation Branch Target Address Cache

IP.com Disclosure Number: IPCOM000117703D
Original Publication Date: 1996-May-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 149K

Publishing Venue

IBM

Related People

Eberly Jr, RC: AUTHOR [+3]

Abstract

PowerPC microprocessors as well as many other current high performance microprocessors perform branch prediction with a Branch Target Address Cache (BTAC) working in conjunction with a Branch History Table (BHT). Ideally the BHT will provide the correct branch direction (taken or not taken), and the BTAC will augment a taken prediction with the correct target address. Since both structures are accessed during the fetch of the branch (before the calculated target address can be obtained), processor cycles are saved. Some machines boost performance further by using what is known as a Correlation BHT.

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

The Correlation Branch Target Address Cache

      PowerPC microprocessors as well as many other current high
performance microprocessors perform branch prediction with a Branch
Target Address Cache (BTAC) working in conjunction with a Branch
History Table (BHT).  Ideally the BHT will provide the correct branch
direction (taken or not taken), and the BTAC will augment a taken
prediction with the correct target address.  Since both structures
are accessed during the fetch of the branch (before the calculated
target address can be obtained), processor cycles are saved.  Some
machines boost performance further by using what is known as a
Correlation BHT.

      "Correlation" or "Adaptive" Branch Prediction is a method that
has been applied to BHTs to improve performance by introducing the
past history of all branches into the prediction along with the
normal current branch fetch address.  Thus, a Correlation BHT is
indexed not just by bits from the fetch address, but also by bits
from the global branch history.  However, a Correlation BHT and a
traditional BTAC often differ on predicted branch direction.  For
example, though the Correlation BHT might predict a branch not taken,
a BTAC hit implies that the branch should be predicted taken.
Further, there are some branches whose targets are different for
different instruction paths to the branch.  The traditional BTAC may
predict the wrong address for these branches because it will predict
whatever address was calculated for the last instance of the branch.
A third problem with the traditional BTAC is the competition for BTAC
space that often arises among multiple branches in the same fetch
packet.  Since a BTAC access is based on fetch address, two or more
branches within a superscalar machine's fetch packet can compete for
the same BTAC entry, degrading performance.

      The Correlation BTAC helps solve the aforementioned problems.
This is done by introducing the element of adaptive branch history
into the BTAC storage structure.  While the traditional BTAC matches
the fetch address to determine hit/miss, the Correlation BTAC must
match first the fetch address, and second the global branch history
to determine hit/miss.  Thus, the BTAC access is now analogous to the
BHT access, and the two should be in agreement more often.  Further,
a single branch may now occupy multiple locations, so for branches
whose target address can vary, different targets may be associated
with different global history vectors.  Finally, since there may be
multiple entries for a single fetch address, the competition between
multiple branches within the same fetch group is reduced.

      The Correlation BTAC is designed for use in superscalar
microprocessors that use branch prediction to improve performance.
The Correlation BTAC complements a Correlation BHT, which is also
expected to be a part of the microarchitecture.  This new BTAC design
should improve overall BTAC hit rate, and decrea...