Computer Architecture

ELE 475 / COS 475

Slide Deck 3: Cache Review
David Wentzlaff
Department of Electrical Engineering
Princeton University

1
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

2
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

3
Naive Register File

Write
Data

Read
Data

clk Read
Decoder Address

Write
Address
4
Memory Arrays: Register File

5
Memory Arrays: SRAM

6
Memory Arrays: DRAM

7
 Relative Memory Sizes of
SRAM vs. DRAM

On-Chip DRAM on
SRAM on memory chip
logic chip

[ From Foss, R.C. “Implementing Application-

Specific Memory”, ISSCC 1996 ] 8
 Memory Technology Trade-offs
Low Capacity
Latches/Registers Low Latency
High Bandwidth
(more and wider ports)

Register File

SRAM
High Capacity
DRAM High Latency
Low Bandwidth

9
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

10
 CPU-Memory Bottleneck
Main
Processor
Memory

• Performance of high-speed computers is usually limited by

memory bandwidth and latency
• Latency is time for a single access
– Main memory latency is usually >> than processor cycle time
• Bandwidth is the number of accesses per unit time
– If m instructions are loads/stores, 1 + m memory accesses per
instruction, CPI = 1 requires at least 1 + m memory accesses
per cycle
• Bandwidth-Delay Product is amount of data that can be in
flight at the same time (Little’s Law)
11
 Processor-DRAM Latency Gap

[Hennessy &
Patterson 2011]

• Four-issue 2 GHz superscalar accessing 100 ns DRAM could execute

800 instructions during the time for one memory access!
• Long latencies mean large bandwidth-delay products which can be
difficult to saturate, meaning bandwidth is wasted
12
From Hennessy and Patterson Ed. 5 Image Copyright © 2011, Elsevier Inc. All rights Reserved.
 Physical Size Affects Latency
Processor

Processor

Small
Memory
Big Memory

• Signals have further to travel

• Fan out to more locations

13
 Memory Hierarchy
Small Fast Big Slow
Processor Memory Memory
(RF, SRAM) (DRAM)

• Capacity: Register << SRAM << DRAM

• Latency: Register << SRAM << DRAM
• Bandwidth: on-chip >> off-chip
• On a data access:
– if data is in fast memory -> low-latency access to SRAM
– if data is not in fast memory -> long-latency access to DRAM
• Memory hierarchies only work if the small, fast memory
actually stores data that is reused by the processor 14
 Common And Predictable Memory
Reference Patterns
Address n loop iterations
Temporal Locality:
Instruction If a location is
fetches reference it is likely
to be reference again
subroutine subroutine in the near future
call return
Stack
Spatial Locality:
accesses
argument access If a location is
referenced it is likely
that locations near it
will be referenced in
Data the near future
accesses scalar accesses
Time
15
 Real Memory Reference Patterns
Spatial
Locality

Temporal
Locality
Memory Address

Temporal
& Spatial
Locality

Time (one dot per access to that address at that time)

[From Donald J. Hatfield, Jeanette Gerald: Program Restructuring 16
for Virtual Memory. IBM Systems Journal 10(3): 168-192 (1971)]
 Caches Exploit Both Types of Locality
Small Fast Big Slow
Processor Memory Memory
(RF, SRAM) (DRAM)

• Exploit temporal locality by remembering the

contents of recently accessed locations
• Exploit spatial locality by fetching blocks of
data around recently accessed locations

17
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

18
 Inside a Cache
Address Address
Main
Processor CACHE Memory
Data Data

copy of main copy of main

memory memory
location 100 location 101
Data Data
100 Byte Byte Line
Data
304 Byte

Address 6848
Tag 416

Data Block
19
Basic Cache Algorithm for a Load

20
 Classifying Caches
Address Address
Main
Processor CACHE Memory
Data Data

• Block Placement: Where can a block be

placed in the cache?
• Block Identification: How a block is found if it
is in the cache?
• Block Replacement: Which block should be
replaced on a miss?
• Write Strategy: What happens on a write? 21
 Block Placement:
Where Place Block in Cache?
1111111111 2222222222 33
Block Number 0123456789 0123456789 0123456789 01

Memory

Set Number 0 1 2 3 01234567

Cache

Fully (2-way) Set Direct

Associative Associative Mapped
anywhere anywhere in only into
block 12
can be placed set 0 block 4
(12 mod 4) (12 mod 8)
22
 Block Placement:
Where Place Block in Cache?
1111111111 2222222222 33
Block Number 0123456789 0123456789 0123456789 01

Memory

Set Number 0 1 2 3 01234567

Cache

Fully (2-way) Set Direct

Associative Associative Mapped
anywhere anywhere in only into
block 12
can be placed set 0 block 4
(12 mod 4) (12 mod 8)
23
Block Identification: How to find block
in cache?

• Cache uses index and offset to find

potential match, then checks tag
• Tag check only includes higher order bits
• In this example (Direct-mapped, 8B block,
4 line cache )
24
Block Identification: How to find block
in cache?

• Cache checks all potential blocks with

parallel tag check
• In this example (2-way associative, 8B block,
4 line cache) 25
 Block Replacement: Which block to
replace?
• No choice in a direct mapped cache
• In an associative cache, which block from set should be
evicted when the set becomes full?
• Random
• Least Recently Used (LRU)
– LRU cache state must be updated on every access
– True implementation only feasible for small sets (2-way)
– Pseudo-LRU binary tree often used for 4-8 way
• First In, First Out (FIFO) aka Round-Robin
– Used in highly associative caches
• Not Most Recently Used (NMRU)
– FIFO with exception for most recently used block(s)
26
 Write Strategy: How are writes
handled?
• Cache Hit
– Write Through – write both cache and memory,
generally higher traffic but simpler to design
– Write Back – write cache only, memory is written
when evicted, dirty bit per block avoids unnecessary
write backs, more complicated
• Cache Miss
– No Write Allocate – only write to main memory
– Write Allocate – fetch block into cache, then write
• Common Combinations
• Write Through & No Write Allocate
• Write Back & Write Allocate
27
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

28
 Average Memory Access Time
Hit
Main
Processor CACHE Memory
Miss

• Average Memory Access Time = Hit Time + ( Miss Rate * Miss Penalty )

29
Categorizing Misses: The Three C’s

• Compulsory – first-reference to a block, occur even

with infinite cache
• Capacity – cache is too small to hold all data needed by
program, occur even under perfect replacement policy
(loop over 5 cache lines)
• Conflict – misses that occur because of collisions due
to less than full associativity (loop over 3 cache lines) 30
 Reduce Hit Time: Small & Simple
Caches

Plot from Hennessy and Patterson Ed. 4

Image Copyright © 2007-2012 Elsevier Inc. All rights Reserved.
 Reduce Miss Rate: Large Block Size

• Less tag overhead • Can waste bandwidth if data is

• Exploit fast burst transfers not used
from DRAM • Fewer blocks -> more conflicts
• Exploit fast burst transfers
over wide on-chip busses

Plot from Hennessy and Patterson Ed. 5 Image Copyright © 2011, Elsevier Inc. All rights Reserved.
 Reduce Miss Rate: Large Cache Size

Empirical Rule of Thumb:

If cache size is doubled, miss rate usually drops by about √2

Plot from Hennessy and Patterson Ed. 5 Image Copyright © 2011, Elsevier Inc. All rights Reserved.
 Reduce Miss Rate: High Associativity

Empirical Rule of Thumb:

Direct-mapped cache of size N has about the same miss rate
as a two-way set- associative cache of size N/2
Plot from Hennessy and Patterson Ed. 5 Image Copyright © 2011, Elsevier Inc. All rights Reserved.
 Reduce Miss Rate: High Associativity

Empirical Rule of Thumb:

Direct-mapped cache of size N has about the same miss rate
as a two-way set- associative cache of size N/2
Plot from Hennessy and Patterson Ed. 5 Image Copyright © 2011, Elsevier Inc. All rights Reserved.
 Agenda
• Memory Technology
• Motivation for Caches
• Classifying Caches
• Cache Performance

36
 Acknowledgements
• These slides contain material developed and copyright by:
– Arvind (MIT)
– Krste Asanovic (MIT/UCB)
– Joel Emer (Intel/MIT)
– James Hoe (CMU)
– John Kubiatowicz (UCB)
– David Patterson (UCB)
– Christopher Batten (Cornell)

• MIT material derived from course 6.823

• UCB material derived from course CS252 & CS152
• Cornell material derived from course ECE 4750

37
Copyright © 2013 David Wentzlaff

38