Memory-Hierarchy Tradeoffs - Models of Computation: Exploring the Power of Computing - page 529

CHAPTER
Memory-Hierarchy Tradeoffs
Although serial programming languages assume that programs are written for the RAMmodel,
this model is rarely implemented in practice. Instead, the random-access memory is replaced
with a hierarchy of memory units of increasing size, decreasing cost per bit, and increasing
access time. In this chapter we study the conditions on the size and speed of these units when
a CPU and a memory hierarchy simulate the RAM model. The design of memory hierarchies
is a topic in operating systems.
A memory hierarchy typically contains the local registers of the CPU at the lowest level and
may contain at succeeding levels a small, very fast, local random-access memory called a cache,
a slower but still fast random-access memory, and a large but slow disk. The time to move data
between levels in a memory hierarchy is typically a few CPU cycles at the cache level, tens of
cycles at the level of a random-access memory, and hundreds of thousands of cycles at the disk
level! A CPU that accesses a random-access memory on every CPU cycle may run at about
a tenth of its maximum speed, and the situation can be dramatically worse if the CPU must
access the disk frequently. Thus it is highly desirable to understand for a given problem how
the number of data movements between levels in a hierarchy depends on the storage capacity
of each memory unit in that hierarchy.
In this chapter we study tradeoffs between the number of storage locations (space) at each
memory-hierarchy level and the number of data movements (I/O time) between levels. Two
closely related models of memory hierarchies are used, the memory-hierarchy pebble game and
the hierarchical memory model, which are extensions of those introduced in Chapter 10 .
In most of this chapter it is assumed not only that the user has control over the I/O algo-
rithm used for a problem but that the operating system does not interfere with the I/O oper-
ations requested by the user. However, we also examine I/O performance when the operating
system, not the user, controls the sequence of memory accesses (Section 11.10 ). Competi-
tive analysis is used in this case to evaluate two-level LRU and FIFO memory-management
algorithms.
529