Page 183 -

APPENDIX 4A 153

Time
(in units of calls/returns)

t 33

Return

w 5
Call

Nesting
depth
Figure 4.21 Example Call-Return Behavior of a Program

A distinction is made in the literature between spatial locality and temporal
locality. Spatial locality refers to the tendency of execution to involve a number of
memory locations that are clustered.This reflects the tendency of a processor to ac-
cess instructions sequentially. Spatial location also reflects the tendency of a pro-
gram to access data locations sequentially, such as when processing a table of data.
Temporal locality refers to the tendency for a processor to access memory locations
that have been used recently. For example, when an iteration loop is executed, the
processor executes the same set of instructions repeatedly.
Traditionally, temporal locality is exploited by keeping recently used instruc-
tion and data values in cache memory and by exploiting a cache hierarchy. Spatial
locality is generally exploited by using larger cache blocks and by incorporating
prefetching mechanisms (fetching items of anticipated use) into the cache control
logic. Recently, there has been considerable research on refining these techniques to
achieve greater performance, but the basic strategies remain the same.

Operation of Two-Level Memory
The locality property can be exploited in the formation of a two-level memory. The
upper-level memory (M1) is smaller, faster, and more expensive (per bit) than the
lower-level memory (M2). M1 is used as a temporary store for part of the contents
of the larger M2. When a memory reference is made, an attempt is made to access
the item in M1. If this succeeds, then a quick access is made. If not, then a block of
memory locations is copied from M2 to M1 and the access then takes place via M1.
Because of locality, once a block is brought into M1, there should be a number of ac-
cesses to locations in that block, resulting in fast overall service.
To express the average time to access an item, we must consider not only the
speeds of the two levels of memory, but also the probability that a given reference
can be found in M1.We have
T = H * T + (1 - H) * (T + T )
1
2
1
s
= T + (1 - H) * T 2 (4.2)
1