Browse Prior Art Database

Improving Instruction Cache Branch Prediction with Target Addresses

IP.com Disclosure Number: IPCOM000105409D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 83K

Publishing Venue

IBM

Related People

Eickenmeyer, RJ: AUTHOR

Abstract

One method of branch prediction is to add one or more prediction bits to each instruction in the instruction cache. The prediction bits maintain a history of the branch. For example, with a single bit per branch instruction, the bit indicates whether the branch was taken or not taken last time. The prediction for the next time is the same as the actual direction last time. If the prediction turns out to be wrong, the bit is changed. Part of the prediction process is determining the address of the target instruction if the branch is predicted taken. A normal address generation can be performed, or to achieve better performance, address generation can be performed early. Early address generation will result in an increase in the number of address generation interlocks (AGI).

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

Improving Instruction Cache Branch Prediction with Target Addresses

      One method of branch prediction is to add one or more
prediction bits to each instruction in the instruction cache.  The
prediction bits maintain a history of the branch.  For example, with
a single bit per branch instruction, the bit indicates whether the
branch was taken or not taken last time.  The prediction for the next
time is the same as the actual direction last time.  If the
prediction turns out to be wrong, the bit is changed.  Part of the
prediction process is determining the address of the target
instruction if the branch is predicted taken.  A normal address
generation can be performed, or to achieve better performance,
address generation can be performed early.  Early address generation
will result in an increase in the number of address generation
interlocks (AGI).

      Another method of branch prediction is the Branch History Table
(BHT).  This contains the target address used for the branch at its
last execution.  For most branches, the target does not change from
one execution to the next.  A BHT is typically organized around
single branch instructions, while an instruction cache is organized
around a cache line, typically 128 bytes, or 32 four-byte
instructions.  Disclosed is a method of keeping target address in an
instruction-cache prediction scheme for those branches where the
address is needed.

      The Figure shows the disclosed mechanism.  Directory sizes are
shown for the example cache size described.  The example shows a
32-bit address divided into three parts for accessing the cache.  The
example uses 128-byte line, so seven low order bits form the byte
offset into the line.  The cache is 32k bytes and four-way
associative, so six bits are used to select the set number.  Each of
four lines in the set are checked for a hit by comparing the stored
tag with the upper bits of the address.  Both the instruction and the
prediction bits are read in this manner.  To improve prediction, a
secondary Branch History Cache (BHC), can be used to save prediction
bits from lines replaces on a miss.  When a new line is loaded, the
prediction bits may be found in the...