Page 146 -

4.1 / COMPUTER MEMORY SYSTEM OVERVIEW 117

The use of two levels of memory to reduce average access time works in prin-
ciple, but only if conditions (a) through (d) apply. By employing a variety of tech-
nologies, a spectrum of memory systems exists that satisfies conditions (a) through
(c). Fortunately, condition (d) is also generally valid.
The basis for the validity of condition (d) is a principle known as locality of
reference [DENN68]. During the course of execution of a program, memory refer-
ences by the processor, for both instructions and data, tend to cluster. Programs typ-
ically contain a number of iterative loops and subroutines. Once a loop or subroutine
is entered, there are repeated references to a small set of instructions. Similarly,
operations on tables and arrays involve access to a clustered set of data words. Over
a long period of time, the clusters in use change, but over a short period of time, the
processor is primarily working with fixed clusters of memory references.
Accordingly, it is possible to organize data across the hierarchy such that the
percentage of accesses to each successively lower level is substantially less than that of
the level above. Consider the two-level example already presented. Let level 2 mem-
ory contain all program instructions and data.The current clusters can be temporarily
placed in level 1. From time to time, one of the clusters in level 1 will have to be
swapped back to level 2 to make room for a new cluster coming in to level 1. On aver-
age, however, most references will be to instructions and data contained in level 1.
This principle can be applied across more than two levels of memory, as sug-
gested by the hierarchy shown in Figure 4.1. The fastest, smallest, and most expen-
sive type of memory consists of the registers internal to the processor. Typically, a
processor will contain a few dozen such registers, although some machines contain
hundreds of registers. Skipping down two levels, main memory is the principal inter-
nal memory system of the computer. Each location in main memory has a unique
address. Main memory is usually extended with a higher-speed, smaller cache. The
cache is not usually visible to the programmer or, indeed, to the processor. It is a de-
vice for staging the movement of data between main memory and processor regis-
ters to improve performance.
The three forms of memory just described are, typically, volatile and employ
semiconductor technology.The use of three levels exploits the fact that semiconduc-
tor memory comes in a variety of types, which differ in speed and cost. Data are
stored more permanently on external mass storage devices, of which the most com-
mon are hard disk and removable media, such as removable magnetic disk, tape, and
optical storage. External, nonvolatile memory is also referred to as secondary mem-
ory or auxiliary memory.These are used to store program and data files and are usu-
ally visible to the programmer only in terms of files and records, as opposed to
individual bytes or words. Disk is also used to provide an extension to main memory
known as virtual memory, which is discussed in Chapter 8.
Other forms of memory may be included in the hierarchy. For example, large
IBM mainframes include a form of internal memory known as expanded storage.
This uses a semiconductor technology that is slower and less expensive than that of
main memory. Strictly speaking, this memory does not fit into the hierarchy but is a
side branch: Data can be moved between main memory and expanded storage but
not between expanded storage and external memory. Other forms of secondary
memory include optical and magneto-optical disks. Finally, additional levels can be
effectively added to the hierarchy in software. A portion of main memory can be