CACHE SUBSYSTEMS
7.1 INTRODUCTION
TO
CACHES
In a cache·memory system, all the data
is
stored in main memory and some data
is
dupli-
cated in the cache. When the processor accesses memory, it checks the cache first.
If
the
desired data is in the cache, the processor can access it quickly, because the cache
is
a fast
memory.
If
the data
is
not in the cache, it must be fetched from the main memory.
A cache reduces average memory access time
if
it
is
organized
so
that the code and data
that the processor needs most often
is
in the cache. Programs execute most quickly when
most operations are transfers to and from the faster cache memory.
If
the requested data
is
found in the cache, the memory access
is
called a cache hit; if not, it
is
called a cache miss.
The hit rate
is
the percentage of accesses
that
are hits; it
is
affected by the size and physical
organization of the cache, the cache algorithm, and the program being run. The success of
a cache system depends
on
its ability to maintain the data
in
the cache
in
a way that increases
the hit rate. The various cache organizations presented
in
Section 7.2 reflect different strat-
egies for achieving this goal.
7.1.1 Program
locality
Predicting the location of the next memory access would be impossible
if
programs accessed
memory completely
at
random. However, programs usually access memory in the neighbor-
hood of locations accessed recently. This principle
is
known as program locality or locality
of reference.
Program locality makes cache systems possible. The same concept,
on
a larger scale, allows
demand paging systems to work
well.
In typical programs, code execution usually proceeds
sequentially or in small loops
so
that
the next
few
accesses are nearby.
Data
variables are
often accessed several times
in
succession. Stacks grow and shrink from one end
so
that
the
next
few
accesses are all near the top of the stack. Character strings and vectors are often
scanned sequentially.
The principle of program locality pertains to how programs tend to behave,
but
it
is
not a
law
that
all programs always obey. Jumps in code sequences and context switching between
programs are examples of behavior
that
may not uphold program locality.
7.1.2 Block Fetch
The block fetch uses program locality to increase the hit rate of a cache. The cache control-
ler partitions the main memory into blocks. Typical block sizes (also known as line size) are
2,
4,
8,
or
16
bytes. A 32-bit processor usually uses two or four words per block. When a
needed word
is
not in the cache, the cache controller moves not only the needed word from
the main memory into the cache, but also the entire block that contains the needed word.
A block fetch can retrieve the data located before the requested byte (lookbehind), follows
the requested byte (lookahead), or both. Generally, blocks are aligned (2-byte blocks
on
doubleword boundaries, 4-word blocks
on
doubleword boundaries). An access to any byte
in
the block copies the whole block into the cache. When memory locations are accessed in
7-2
To Next Page
Loading...
