Browse Prior Art Database

Scheme for Producing Miss-Rate As a Function of Cache Size By Means of Traces Produced by Observing Misses From a Cache Of Fixed Size

IP.com Disclosure Number: IPCOM000120214D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 181K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

Given a trace of misses produced by a processor operating on a cache of a fixed size, we describe how to estimate the miss rates for all sizes of cache of the same line size. Cache analysis is conventionally done by trace-driven means in which a trace of all address references is simulated on a variety of cache structures to determine the ratio of cache misses to total references. The analysis techniques in use today and examples of their use are summarized in (1,2).

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

Scheme for Producing Miss-Rate As a Function of Cache Size By Means
of Traces Produced by Observing Misses From a Cache Of Fixed Size

      Given a trace of misses produced by a processor operating
on a cache of a fixed size, we describe how to estimate the miss
rates for all sizes of cache of the same line size. Cache analysis is
conventionally done by trace-driven means in which a trace of all
address references is simulated on a variety of cache structures to
determine the ratio of cache misses to total references.  The
analysis techniques in use today and examples of their use are
summarized in (1,2).

      The problem is that as caches become large, the length of
address traces required for cache analysis become excessively long.
They are very expensive to produce from program simulation and too
long to capture in real time by hardware monitoring.  Our objective
is to show how to use a hardware monitor to capture just the misses
produced by a processor with a cache of some fixed size to yield
sufficient information to analyze caches of a variety of sizes and
structures.  The only limitation is that the cache data will be
caches whose line size is equal to the line size of the cache that
produced the original data.
THE METHOD

      The outline of the proposed method is the following:
1.  Build a hardware monitor to record the misses produced
    by a processor with a cache of some fixed size.
2.  Load the workload to be measured into the processor.
3.  Flush the cache so that all entries are invalid.
4.  Start the workload.
5.  Record the misses and the time at which each miss occurs.  (Other
alternative ways of recording data are acceptable, and some
alternatives are cited below.)
6.  From the recorded data, determine the footprint function for the
trace as described below.
7.  Find the second derivative of the footprint function and use this
in an integral formula to find the miss rate of a cache structure.
The parameters in the integral formula are the number of sets in the
cache and the set associativity of the cache.
THE FOOTPRINT FUNCTION

      The footprint function for a workload, u(t), is the number of
unique references as a function of time (3).  That is, u(t) gives the
number of distinct lines referenced at time t.   The footprint
function typically has the form
   u(t) = atb                                 (1)

      As shown in (3), which also shows that the miss-rate of a fully
associative cache with C lines can be obtained from the derivative of
the footprint function as follows:
                           du(t)   @
           Miss rate(C) = [[[[[[[[ @          (2)
                            dt     @
                                    u(t) = C
                      = b a1/b C1-1/b .       (3)

      This re...