Browse Prior Art Database

Improving Most Recently Used Change Prefetching with Dias Sequences

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

Publishing Venue

IBM

Related People

Rechtschaffen, R: AUTHOR

Abstract

DIAS (Discrete I-Line Access Sequence) once organized as a switchable entry-exit relationship for I-Lines provides a model for comparison with MRU CHANGE prefetching. A means of improving MRU CHANGE PREFETCHING utilizing aspects of the entry-exit relationships is disclosed.

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

Improving Most Recently Used Change Prefetching with Dias Sequences

      DIAS (Discrete I-Line Access Sequence) once organized as a
switchable entry-exit relationship for I-Lines provides a model for
comparison with MRU CHANGE prefetching.  A means of improving MRU
CHANGE PREFETCHING utilizing aspects of the entry-exit relationships
is disclosed.

      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 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)
          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 a means of improving MRU CHANGE prefetching can
be offered, it is necessary to reduce the prefetching strategy to a
more general approach that has none of these shortcomings, an
approa...