Browse Prior Art Database

Assuring that Branch Targets are Most-Recently-Used in a Most-Recently-Used Cache

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

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

An MRU cache that provides a one cycle access to those cache lines which are MRU can be made to assure that Branch Target Fetches will be MRU even if the Branch is guessed wrong by the BHT.

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

Assuring that Branch Targets are Most-Recently-Used in a Most-Recently-Used Cache

      An MRU cache that provides a one cycle access to those cache
lines which are MRU can be made to assure that Branch Target Fetches
will be MRU even if the Branch is guessed wrong by the BHT.

DEFINITION OF MRU CACHE - The term MRU cache is used to describe a
multiplicities of attempts to enhance the performance of a cache by
taking advantage of high hit ratio within the cache to the overall
MRU line and to the MRU line within each congruence class.  The
improved access time to a line can be achieved without movement of
the line.  Rather a bit is set, or a set of bits are set, that
identifies the MRU candidate within the arrays so that it can be
accessed directly without a set of comparisons: DLAT to DIRECTORY
TAGS, that establishes that the requisite line is in the cache.

      Assume that for each Congruence Class, CC, within the cache, a
set of bits, B sub CC , are specified, that in conjunction with the
bits generated by the processor, as part of the virtual address,
completely specify the position of the data within the array.  We
further assume that such a specification can be used to expedite the
cache access.  This will be our definition of an MRU cache.

      Ordinarily the I-FETCH mechanism is sufficiently ahead of the
decoder so that when targets of the I-FETCH, as determined by a BHT,
are not MRU, the cycle lost does not impact performance.  There are
two exceptions to this:

o   on a Branch Wrong Guess, and

o   where correctly guessed taken branches are consecutive and in
    different I-FETCH units.

In the former case, following the determination that a branch has
been guessed incorrectly whose target is not MRU, an additional cycle
is lost prior to the decode of the target instruction.

      In general branches can be classified as constant
action/target, TYPE A, branches and  variable action/target, TYPE B,
branches.  It is only aspects of the TYPE B branches that need
concern us.  For each entry into a cache line, it is possible to
d...