Browse Prior Art Database

Anticipating Most-Recently-Used Change in MRU Caches

IP.com Disclosure Number: IPCOM000105741D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 71K

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

An MRU cache provides a one-cycle access to a line that is determined to be MRU in its congruence class. If no line movement is involved in this expedited service, then a convenient way to improve the action of such a cache is to anticipate the MRU change. A means of anticipating a change in the MRU indicator for a given congruence class allows an MRU cache to provide expedited service for a non-MRU line. The prompting of the change uses an I X D sub 1 -> D sub 2 mechanism where the MRU indicator for the CC associated with D sub 2 is changed to the position occupied by line D sub 2 when it was last brought into the cache.

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

Anticipating Most-Recently-Used Change in MRU Caches

      An MRU cache provides a one-cycle access to a line that is
determined to be MRU in its congruence class.  If no line movement is
involved in this expedited service, then a convenient way to improve
the action of such a cache is to anticipate the MRU change.  A means
of anticipating a change in the MRU indicator for a given congruence
class allows an MRU cache to provide expedited service for a non-MRU
line.  The prompting of the change uses an I X D sub 1   ->  D sub 2
mechanism where the MRU indicator for the CC associated with D sub 2
is changed to the position occupied by line D sub 2 when it was last
brought into the cache.

DEFINITION OF MRU CACHE -  The term MRU cache is used to describe a
multiplicity 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.

      Let us assume that for each Congruence Class (CC) within the
cache, a set of bits, B sub CC , is 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.

NO LOSS ASPECT OF MRU CHANGE ON CACHE MISS - An interesting feature
of an MRU cache is that no real penalty accrues to the processor if
the line accessed is not in the cache.  Clearly, a cache miss is a
non-MRU hit, as such an infinite cache simulation of an MRU cache
...