Browse Prior Art Database

Optimal Allocation of Cache Memory Among Competing Processes

IP.com Disclosure Number: IPCOM000034184D
Original Publication Date: 1989-Jan-01
Included in the Prior Art Database: 2005-Jan-26
Document File: 5 page(s) / 33K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

A method describes how to apportion cache memory among competing processes in order to produce the least possible cache-miss rate. An example of the application is to apportion cache memory between instruction streams and data streams. 1. Background A cache-design problem that frequently arises in computers is the problem of allocating a fixed amount of cache memory among competing processes. For example, many systems have separate instruction and data caches.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 46% of the total text.

Page 1 of 5

Optimal Allocation of Cache Memory Among Competing Processes

A method describes how to apportion cache memory among competing processes in order to produce the least possible cache-miss rate. An example of the application is to apportion cache memory between instruction streams and data streams. 1. Background A cache-design problem that frequently arises in computers is the

problem of allocating a fixed amount of cache memory among

competing processes. For example, many systems have separate

instruction and data caches. Given a fixed number of bits of

cache (or a fixed silicon area), how do you apportion the bits (or

silicon area) to achieve a minimum overall miss rate? The

application of the invention need not be limited to instructions

and data, as it can also be applied to systems in which some

processes, such as interrupt handlers and operating systems, are

allocated private caches. 2. The Method

The basic principle is that cache memory should be allocated such

that the derivative of miss rate with respect to memory size is

equal for all processes. The method is presented in four steps,

each with more general assumptions. The basic step is for two

processes, each interlaced in a single trace so that each process

contributes half of the trace. The second step extends the result

to two processes such that one process occurs k times as fre quently as the other, for any constant k. The third step extends the result to the allocation of resources other than memory bits.

The example given is in terms of silicon area, and it is shown for

two equally frequent processes. The last result extends the

results from two to N processes. The last section of the

description sets forth how to obtain the necessary data to make

the allocation.

Two processes, equal frequency.

For a trace of size 2t, approximately t references are produced

from each process, and the references are interlaced more or less

evenly. This is a model of a trace produced for an architecture

that has one instruction fetch and one data fetch for every

instruction. Let r1(x) and r2(x) be the miss rates for Processes

1 and 2, respectively, for cache size x. Suppose there are C bits

of cache, and the allocation of the cache must be fixed to the two

processes. This is equivalent to designing separate caches

for the instruction and data streams, and the problem is to

1

Page 2 of 5

determine how many of the C bits are available to put into each

cache. The method is the application of the following principle:

The optimal allocation of cache gives c1 bits to Process 1

and c2 bits to Process 2 such that the two following

equations hold.

C1 + C2 = C (1)

dr1 ¯ = dr2 ¯

_____¯ _____¯ (2)

dx ¯ x=c1 dx ¯ x=c2

Proof of optimality: The total misses for a trace of any length

is given by

Total misses = Process 1 misses + Process 2 misses (3)

and the miss rate for the trace is the total misses divided by the

trace length. For a trace of length 2t, approximately t refer

ences are produced by ea...