Memory System Design I - Fundamentals of Computer Organization and Architecture - page 111

deliberation to the simple case of a hierarchy consisting only of two levels, that is,
the cache and the main memory. We assume that the main memory access time is t m
and the cache access time is t c . We will measure the impact of locality in terms of the
average access time, defined as the average time required to access an element (a
word) requested by the processor in such a two-level hierarchy.

6.2.1. Impact of Temporal Locality

In this case, we assume that instructions in program loops, which are executed many
times, for example, n times, once loaded into the cache, are used more than once
before they are replaced by new instructions. The average access time, t av ,isgivenby

nt c þ t m
n

t m
n

t av ¼

¼ t c þ

In deriving the above expression, it was assumed that the requested memory element
has created a cache miss, thus leading to the transfer of a main memory block in time
t m . Following that, n accesses were made to the same requested element, each taking
t c . The above expression reveals that as the number of repeated accesses, n,increases,
the average access time decreases, a desirable feature of the memory hierarchy.

6.2.2. Impact of Spatial Locality

In this case, it is assumed that the size of the block transferred from the main
memory to the cache, upon a cache miss, is m elements. We also assume that due
to spatial locality, all m elements were requested, one at a time, by the processor.
Based on these assumptions, the average access time, t av , is given by

mt c þ t m
m

t m
m

t av ¼ ¼ t c þ

In deriving the above expression, it was assumed that the requested memory element
has created a cache miss, thus leading to the transfer of a main memory block, con-
sisting of m elements, in time t m . Following that, m accesses, each for one of the
elements constituting the block, were made. The above expression reveals that as
the number of elements in a block, m, increases, the average access time decreases,
a desirable feature of the memory hierarchy.

6.2.3. Impact of Combined Temporal and Spatial Locality

In this case, we assume that the element requested by the processor created a cache
miss leading to the transfer of a block, consisting of m elements, to the cache (that
take t m ). Now, due to spatial locality, all m elements constituting a block were
requested, one at a time, by the processor (requiring mt c ). Following that, the orig-
inally requested element was accessed (n 2 1) times (temporal locality), that is, a