Browse Prior Art Database

Branch-Dependent Most-Recently-Used Change Prefetching

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

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

The concept of Most-Recently-Used (MRU) CHANGE prefetching can be extended to include prefetching that is dependent on a branch action. A means is disclosed wherein a MRU CHANGE prefetch will be selected from a multiplicity of MRU CHANGES that relate to the future action of a branch.

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

Branch-Dependent Most-Recently-Used Change Prefetching

      The concept of Most-Recently-Used (MRU) CHANGE prefetching can
be extended to include prefetching that is dependent on a branch
action.  A means is disclosed wherein a MRU CHANGE prefetch will be
selected from a multiplicity of MRU CHANGES that relate to the future
action of a branch.

      DEFINING MRU CHANGE PREFETCHING - Consider the following
statistics as a means of better visualizing the concept of MRU CHANGE
PREFETCHING.  A sample trace tape involving 8 MILLION INSTRUCTION
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)
          PREFETCHES ATTEMPTED              241 K
          PREFETCHES USED                   223 K
          RESIDUALS                         178 K

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.  [*]  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.  Before we can offer a means of improving MRU CHANGE
prefetching, it is necessary to reduce the prefetching strategy to a
more general approach that has none of these shortcomings, a...