The Prior Art Database and Publishing service will be updated on Sunday, February 25th, from 1-3pm ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Means for Achieving Optimum of Cache Among Data and

IP.com Disclosure Number: IPCOM000099286D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 3 page(s) / 127K

Publishing Venue


Related People

Stone, HS: AUTHOR [+2]


A method is described that shows how to control a so that it automatically partitions storage between and data in a near-optimal fashion.

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

Means for Achieving Optimum of Cache Among Data and

       A method is described that shows how to control a so that
it automatically partitions storage between and data in a
near-optimal fashion.

      Background: is shown in * that the optimum way to partition
storage among two or more processes is to allocate an of storage to
each process such that the miss-rate with respect to a change in
storage space is the value for all processes competing for cache
storage. is shown here that a cache operating under normal rules
tends in time to operate around a stable that is not an optimal space
allocation for data and  The method is a new replacement rule that
tend in time to operate around a stable state that is optimal
allocation.  Moreover, if the data and processes change their
characteristics, the will automatically alter its allocation of
memory instruction and data to converge to a near-optimal for the new

      The Method: a cache that receives a combination of two one of
which is the instruction-fetch process, the other of which is the
data-access process.  Assume these are interlaced so that an
instruction fetch is by a data fetch, and this in turn is followed by
a fetch.  This assumption can be altered to permit small in the way
the processes are intermixed so that a data fetches or a few
instruction fetches can occur in a sequence.  The results obtained
here are not when a large number of accesses of one process occur any
intervening accesses of the other process, which not a usual case for
the intermingling of instructions data.

      Let M1(x) be the miss-rate for the instruction-fetch as a
function of cache memory size x.  Similarly, MD(x) be the miss- rate
for the data-access process.  It shown in [*] that for a cache of
size C, the optimal of memory between instructions and data is an of
memory x to instructions that satisfies = dMD(C-x)/dx. (1).

      This allocation minimizes the total number of misses. the data
process accesses at a rate that is not equal to the instruction
process, say, at a rate times as fast, then the right- hand side of
Eq. (1) should the multiplier r as a factor.

      When a miss occurs in a conventional cache memory, the replaced
is the least recently used item, or is an item is approximately the
least recently used item.  It is shortly that this scheme does not
converge to the allocation of cache among data and instructions.
following strategy does converge to the optimal  Replacement On a
cache miss due to an fetch, replace the least recently used data  On
a cache miss due to a data fetch, replace the recently used
instruction cell.

      To show that this scheme tends in time to operate around stable
state that is the optimum allocation, model the as being in one of C
+ 1 states 0,1,...,C, where State indicates that i cells of cache are
allocated to  The cache will move...