Browse Prior Art Database

Improving Most Recently User Change Prefetching

IP.com Disclosure Number: IPCOM000105598D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 6 page(s) / 219K

Publishing Venue

IBM

Related People

Pershing, JA: AUTHOR [+2]

Abstract

An analysis of MRU CHANGE prefetching supports an improved approach based on the type of MRU change that has occurred. The efficiency of the cache directory during non-miss MRU changes creates the improvement that is disclosed.

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

Improving Most Recently User Change Prefetching

      An analysis of MRU CHANGE prefetching supports an improved
approach based on the type of MRU change that has occurred.  The
efficiency of the cache directory during non-miss MRU changes creates
the improvement that is disclosed.

Defining MRU Change Prefetching - Let us consider the following
statistics as a means of better visualizing the concept of MRU CHANGE
PREFETCHING.  A sample trace tape involving 8 MILLION INSTRUCTIONS
has:

          UNIQUE I-LINES                    5.2 K (128 Byte)
          NUMBER OF INSTRUCTIONS            8.0 M
          NUMBER OF I-ACCESSES              4.6 M  (.58 DW/I)
          NUMBER OF I-MRU CHANGES           400 K (16 K MRU I&D
CACHE)

The basic idea of MRU CHANGE PREFETCHING is to link successive MRU
changes from a cache with a specific geometry and use that linkage as
a means prefetching lines not currently in the cache when an MRU
CHANGE occurs.  On each MRU CHANGE one prefetches the next MRU
change.  U.S.  Patent #4,807,110, entitled PREFETCHING MECHANISM FOR
A CACHE HAVING A SECOND DIRECTORY FOR SEQUENTIALLY ACCESSED BLOCKS,
has a complete description of the means employed to prefetch based on
MRU CHANGE.  There are three shortcoming of MRU CHANGE PREFETCHING:

o   MRU change depends on the set of lines that are currently MRU.
    This is a form of dependence on the cache contents that can vary
    between times that a line is accessed.
o   Allows for only a single candidate as to what to prefetch next.
    Lines that have multiple exits, and therefore multiple entries
    possess the possibility of bifurcation with respect to MRU CHANGE
    and must select between multiple options.
o   MRU change is not updated with respect to a BWG and for an
    oscillating branch the ability to correct the MRU CHANGE may
    never materialize in a confirmed prefetching approach.  In
    confirmed prefetching a MRU CHANGE must be repeated before it can
    used to prefetch (on the third opportunity).

Despite all these shortcomings, the prefetching of I-lines at all
cache sizes, with the identical set of MRU changes for the 5.2 K
I-Lines is able to recover 60% of the remaining I-Misses with an
accuracy of over 90%.  The implication of this is that within each
doubling of the cache size in terms of set associativity of the
congruence classes there is a residual fraction of MRU CHANGE targets
that is not included.  These targets recover the misses from the
larger cache.

Prefetching Using a Branch History Table (BHT) - In the case of
prefetching using an BHT,the concern of the prefetching mechanisms is
to be sure that what is required next by the processor will be made
available.  The action of the mechanism is to assume that in the
absence of TAKEN BRANCHES the requirements of the processor will be
satisfied by the next sequential a...