Browse Prior Art Database

Allocation of Cache Memory Among Competing Processes

IP.com Disclosure Number: IPCOM000034368D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 6 page(s) / 69K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

A method is described relative to how to apportion memory in a cache among N competing processes. The optimal allocation can be constructed quickly in real time by one of two methods described in this article. 1. Background A cache-design problem that frequently arises in computers is that of partitioning 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 33% of the total text.

Page 1 of 6

Allocation of Cache Memory Among Competing Processes

A method is described relative to how to apportion memory in a cache among N competing processes. The optimal allocation can be constructed quickly in real time by one of two methods described in this article. 1. Background A cache-design problem that frequently arises in

computers is that of partitioning 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 method 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 method proposes, in effect, that cache memory

should be allocated in such a way as to make the

derivatives of the miss rates (weighted by the number

of total references) as equal as possible for all

processes. This is made more precise as set forth

below.

Suppose that N processes are to use a cache of size C.

Let ri denote the miss rate for process i as a function

of allocated cache. Suppose that each process i

generates Pi references, giving total of T =

references in all. If each process i is

allocated a portion of the cache of size ci, then the overall miss

rate is then given by . This function is minimized

subject to the constraint that .

All studies known support the claim that cache miss

rates are (decreasing) strictly convex functions of

cache size. Thus, the functions Fi = Piri(c)/T, the

fraction of the total miss rate attributed to Process

i, i = 1,2,...,N, are also (decreasing) strictly convex

functions of cache size c allocated to a process. To

minimize the sum of N such functions, two essentially

similar algorithms are set forth.

The first algorithm solves the (discrete) problem of allocating a

total of C = units of cache among N competing processes in such

a way that the overall miss rate is minimized. Each value ci

is required to be an integer between 0 and C, and each function Fi is required to be a convex function defined on those integers. The second algorithm solves the continuous version of

1

Page 2 of 6

the same problem. In this case, C and each ci e [O,C]

are real numbers, and each Fi is a differentiable

convex function defined on [O,C]. A model of memory

references based on a fractal representation has been

proposed [1]. To make the exposition of the second

algorithm concrete, the approach will be demonstrated

assuming that the functions Fi are based on this model.

Discrete algorithm:

A greedy algorithm [2] solves such problems in time O(N

+ C log N). While the discussion is based on this

work, it is noted that the subsequent algorithm due to

[3] is based on [2] and has complexity O(N log C).

This bound was shown in [3] to be optimal to within a

cons...