Chapter 10
Cache Memory
Outline
• Computer memory system overview
– Characteristics of memory systems
– Memory hierarchy
• Cache memory principles
• Elements of cache design
– Cache addresses
– Mapping function
– Replacement algorithms
– Write policy
Memory characteristics
• Location
• Capacity
• Unit of transfer
• Access method
• Performance
• Physical type
• Physical characteristics
• Organisation
Memory characteristics -Location
• Refers to whether memory is internal and external
to the computer
• Internal memory is often equated with main
memory
• Cache is another form of internal memory
• External memory consists of peripheral storage
devices that are accessible to the processor via I/O
controllers
• Processor requires its own local memory, in the
form of registers
Memory characteristics-Capacity
• Memory is typically expressed in terms of
bytes
– For internal memory, expressed in terms of bytes
(1 byte = 8 bits) or words.
– Common word lengths are 8, 16, and 32 bits.
– External memory capacity is expressed in terms of
bytes.
Memory characteristics -Unit of transfer
• For internal memory the unit of transfer is
equal to the number of electrical lines into
and out of the memory module.
• This may be equal to the word length, but is
often larger, such as 64, 128, or 256 bits. To
clarify this point, consider three related
concepts for internal memory:
– word, addressable units, unit of transfer
Memory characteristics -Access method
• Sequential
– Memory is organized into units of data, called records. Access must be
made in a specific linear sequence.
• Direct
– individual blocks or records have a unique address based on physical
location
• Random
– Each addressable location in memory has a unique, physically wired-in
addressing mechanism
• Associative
– random access type of memory that enables one to make a
comparison of desired bit locations within a word for a specified
match, and to do this for all words simultaneously
Memory characteristics -Performance
• Access time (latency)
• Memory cycle time
• Transfer rate
Memory characteristics -Physical Type
• The most common forms are: (a)
a. Semiconductor memory
b. Magnetic surface memory
c. Optical
d. Magneto-optical
(c)
(b)
(d)
Memory characteristics -Physical
Characteristics
• Several physical characteristics of data storage are
important:
• Volatile memory - information decays naturally or is lost when
electrical power is switched off
• Nonvolatile memory - once recorded, information remains
without deterioration until deliberately changed
• No electrical power is needed to retain information
• Magnetic-surface memory – nonvolatile
• Semiconductor memory - may be either volatile or nonvolatile
• Non-erasable memory - cannot be altered, except by
destroying the storage unit, semiconductor memory of this type
is known as read-only memory (ROM)
Memory characteristics -Organization
• Organization refers to the physical
arrangement of bits to form words
• For random-access memory the organization
is a key design issue
Memory Hierarchy (1)
• Design constraints on a computer’s memory can be
summed up by three questions:
– How much, how fast, how expensive
• There is a trade-off among capacity, access time, and
cost
– Faster access time, greater cost per bit
– Greater capacity, smaller cost per bit
– Greater capacity, slower access time
• The way out of the memory dilemma is not to rely on a
single memory component or technology, but to employ
a memory hierarchy
Memory Hierarchy (2)
r bit
pe
ost
c
is ng cit
y
s of
a p a e es
cre c a ti m a cc r
De si ng c e ss
y of esso
a ac nc roc
c re g e
In
a sin e qu he p
re r
f yt
c n g b
In a si ory
ecre em
D em
th
Cache memory principles
Cache and Main Memory
Cache/Main Memory Structure
Cache read operation
Typical Cache Organization
Elements of Cache Design
Cache Addresses
• Virtual memory
– Facility that allows programs to address memory
from a logical point of view, without regard to the
amount of main memory physically available
– When used, the address fields of machine
instructions contain virtual addresses
– For reads to and writes from main memory, a
hardware memory management unit (MMU)
translates each virtual address into a physical
address in main memory
Logical Caches
Physical Caches
Cache Sizes
of Some
Processors
a
Two values
separated by a slash
refer to instruction
and data caches.
b
Both caches are
instruction only; no
data caches.
Mapping Function
• Because there are fewer cache lines than main
memory blocks, an algorithm is needed for
mapping main memory blocks into cache lines
• Three techniques can be used:
– Direct mapping
– Associative mapping
– Set-associative mapping
Direct Mapping
• Simplest technique
• Map each block of main memory into only one
possible cache line
• The mapping is expressed as:
i = j modulo m, where
i = cache line number
j = main memory block number
m = number of lines in the cache
Mapping from Main Memory to Cache:
Direct Mapping
Mapping from Main Memory to Cache:
Associative Mapping
Direct Mapping Cache
Organization
Direct Mapping:
An Example
Direct Mapping Summary
• Address length = (s + w) bits
• Number of addressable units = 2s+w words or
bytes
• Block size = line size = 2w words or bytes
• Number of blocks in main memory = 2s+ w/2w =
2s
• Number of lines in cache = m = 2r
• Size of tag = (s – r) bits
Associative Mapping
• Each memory block is loaded into any line of
the cache
• Cache control logic interpret a memory
address as tag and word field
Associative Mapping Cache Organization
Associative Mapping: An Example
Associative Mapping Summary
• Address length = (s + w) bits
• Number of addressable units = 2s+w words or
bytes
• Block size = line size = 2w words or bytes
• Number of blocks in main memory = 2s+ w/2w =
2s
• Number of lines in cache = undetermined
• Size of tag = s bits
Set Associative Mapping
• Compromise that exhibits the strengths of both
the direct and associative approaches while
reducing their disadvantages
• Cache consists of a number of sets
• Each set contains a number of lines
• A given block maps to any line in a given set
• e.g. 2 lines per set
– 2 way associative mapping
– A given block can be in one of 2 lines in only one set
Mapping From Main Memory
to Cache: k-Way
Set Associative
k-Way Set Associative Cache Organization
Set Associative Mapping Summary
• Address length = (s + w) bits
• Number of addressable units = 2s+w words or bytes
• Block size = line size = 2w words or bytes
• Number of blocks in main memory = 2s+w/2w=2s
• Number of lines in set = k
• Number of sets = v = 2d
• Number of lines in cache = m=kv = k * 2d
• Size of cache = k * 2d+w words or bytes
• Size of tag = (s – d) bits
2-Way Set Associative Mapping Example
Replacement Algorithms (1)
• Once the cache has been filled, when a new
block is brought into the cache, one of the
existing blocks must be replaced
• For direct mapping there is only one possible line
for any particular block and no choice is possible
• For the associative and set-associative
techniques a replacement algorithm is needed
• To achieve high speed, an algorithm must be
implemented in hardware
Replacement algorithms (2)
• Least recently used (LRU)
– Most effective
– Replace that block in the set that has been in the cache longest with
no reference to it
– Because of its simplicity of implementation, LRU is the most popular
replacement algorithm
• First-in-first-out (FIFO)
– Replace that block in the set that has been in the cache longest
– Easily implemented as a round-robin or circular buffer technique
• Least frequently used (LFU)
– Replace that block in the set that has experienced the fewest
references
– Could be implemented by associating a counter with each line
Least recently used (LRU)
First-in-first-out (FIFO)
F
B C D E
Cache after A, B, C, D, E, F
Least frequently used (LFU)
F
A B C D E
Cache after A, B, C, B, D, D, E, A, E, F
Write Policy
• Must not overwrite a cache block unless main
memory is up to date
• Multiple CPUs may have individual caches
• I/O may address main memory directly
Write through
• All writes go to main memory as well as cache
• Multiple CPUs can monitor main memory
traffic to keep local (to CPU) cache up to date
• Lots of traffic
• Slows down writes
Write back
• Updates initially made in cache only
• Update bit for cache slot is set when update
occurs
• If block is to be replaced, write to main
memory only if update bit is set
• Other caches get out of sync
• I/O must access main memory through cache
• N.B. 15% of memory references are writes