CS 61C: Great Ideas in Computer

Architecture (Machine Structures)

Caches Part 3

Instructors:
Bernhard Boser & Randy H. Katz
[Link]

10/24/16 Fall 2016 - Lecture #16 1

 You Are Here!
Software Hardware
• Parallel Requests
Warehouse Smart
Assigned to computer Scale Phone
e.g., Search “Katz” Computer
Harness
• Parallel Threads Parallelism &
Assigned to core Achieve High
e.g., Lookup, Ads Performance Computer
• Parallel Instructions Core … Core
Today’s
>1 instruction @ one time Memory (Cache)
Lecture
e.g., 5 pipelined instructions
Input/Output Core
• Parallel Data
Instruction Unit(s) Functional
>1 data item @ one time Unit(s)
e.g., Add of 4 pairs of words A0 +B0 A1 +B1 A2 +B2 A3 +B3
• Hardware descriptions
Main Memory
All gates @ one time
Logic Gates
• Programming Languages
10/24/16 Fall 2016 - Lecture #16 2
 Typical Memory Hierarchy
On-Chip Components
Control
Third-
Level Secondary
Main

Cache Cache
Instr
Second- Cache
Memory Memory
Level (SRAM)
Datapath (DRAM) (Disk
RegFile

Cache
Or Flash)
Data
(SRAM)

Speed (cycles): ½’s 1’s 10’s 100’s-1000 1,000,000’s

Size (bytes): 100’s 10K’s M’s G’s T’s
Cost/bit: highest lowest

• Principle of locality + memory hierarchy presents programmer with

≈ as much memory as is available in the cheapest technology at the
≈ speed offered by the fastest technology

10/24/16 Fall 2016 - Lecture #16 3

 Write Policy Choices
• Cache Hit:
– Write through: writes both cache & memory on every access
• Generally higher memory traffic but simpler pipeline & cache design
– Write back: writes cache only, memory written only when dirty
entry evicted
• A dirty bit per line reduces write-back traffic
• Must handle 0, 1, or 2 accesses to memory for each load/store
• Cache Miss:
– No write allocate: only write to main memory
– Write allocate (aka fetch on write): fetch into cache

• Common combinations:
– Write through and no write allocate
– Write back with write allocate

10/24/16 Fall 2016 - Lecture #16 4

 Average Memory Access Time (AMAT)
• Average Memory Access Time (AMAT) is the
average time to access memory considering
both hits and misses in the cache
AMAT = Time for a hit
+ Miss rate × Miss penalty

10/24/16 Fall 2016 - Lecture #16 5

 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 6

 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 7

Miss Rate vs. Cache Size on the Integer
Portion of SPECCPU2000

10/24/16 Fall 2016 -- Lecture #16 8

 Sources of Cache Misses (3 C’s)
• Compulsory (cold start, first reference):
– 1st access to a block, not a lot you can do about it
• If running billions of instructions, compulsory misses are
insignificant
• Capacity:
– Cache cannot contain all blocks accessed by the
program
• Misses that would not occur with infinite cache
• Conflict (collision):
– Multiple memory locations mapped to same cache set
• Misses that would not occur with ideal fully associative
cache

10/24/16 Fall 2016 - Lecture #16 9

 How to Calculate 3C’s
Using Cache Simulator
1. Compulsory: set cache size to infinity and fully
associative, and count number of misses
2. Capacity: Change cache size from infinity, usually
in powers of 2, and count misses for each
reduction in size
– 16 MB, 8 MB, 4 MB, … 128 KB, 64 KB, 16 KB
3. Conflict: Change from fully associative to n-way
set associative while counting misses
– Fully associative, 16-way, 8-way, 4-way, 2-way, 1-way

10/24/16 Fall 2016 - Lecture #16 10

 3Cs Analysis

• Three sources of misses (SPEC2000 integer and floating-point

benchmarks)
– Compulsory misses 0.006%; not visible
– Capacity misses, function of cache size
– Conflict portion depends on associativity and cache size
10/24/16 Fall 2016 - Lecture #16 11
 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 12

 CPU-Cache Interaction
(5-stage pipeline)

0x4 Add E
M
A
we
Decode, ALU Y addr
bubble Primary
IR Register B
Data rdata
PC addr inst Fetch Cache R
D wdata hit?
hit? wdata
PCen Primary
Instruction MD1 MD2
Cache
Stall entire
CPU on data
cache miss
To Memory Control

Cache Refill Data from Lower Levels of

Memory Hierarchy
10/24/16 Fall 2016 - Lecture #16 13
 Improving Cache Performance
AMAT = Time for a hit + Miss rate x Miss penalty
• Reduce the time to hit in the cache
– E.g., Smaller cache
• Reduce the miss rate
– E.g., Bigger cache
• Reduce the miss penalty
– E.g., Use multiple cache levels

10/24/16 Fall 2016 - Lecture #16 14

 Cache Design Space
Computer architects expend considerable effort optimizing organization of cache
hierarchy – big impact on performance and power!
• Several interacting dimensions Cache Size

– Cache size
Associativity
– Block size
– Associativity
– Replacement policy
– Write-through vs. write-back
Block Size
– Write allocation
• Optimal choice is a compromise
– Depends on access characteristics Bad
• Workload
• Use (I-cache, D-cache)
– Depends on technology / cost Good Factor A Factor B

• Simplicity often wins Less More

10/24/16 Fall 2016 - Lecture #16 15

 Primary Cache Parameters
• Block size
– How many bytes of data in each cache entry?
• Associativity
– How many ways in each set?
– Direct-mapped => Associativity = 1
– Set-associative => 1 < Associativity < #Entries
– Fully associative => Associativity = #Entries
• Capacity (bytes) = Total #Entries * Block size
• #Entries = #Sets * Associativity
10/24/16 Fall 2016 - Lecture #16 16
 Impact of Larger Cache on AMAT?
• 1) Reduces misses (what kind(s)?)
• 2) Longer Access time (Hit time): smaller is faster
– Increase in hit time will likely add another stage to the
pipeline
• At some point, increase in hit time for a larger
cache may overcome the improvement in hit rate,
yielding a decrease in performance
• Computer architects expend considerable effort
optimizing organization of cache hierarchy – big
impact on performance and power!

10/24/16 Fall 2016 - Lecture #16 17

 Increasing Associativity?
• Hit time as associativity increases?
– Increases, with large step from direct-mapped to >=2 ways,
as now need to mux correct way to processor
– Smaller increases in hit time for further increases in
associativity
• Miss rate as associativity increases?
– Goes down due to reduced conflict misses, but most gain is
from 1->2->4-way with limited benefit from higher
associativities
• Miss penalty as associativity increases?
– Unchanged, replacement policy runs in parallel with
fetching missing line from memory

10/24/16 Fall 2016 - Lecture #16 18

 Increasing #Entries?
• Hit time as #entries increases?
– Increases, since reading tags and data from larger
memory structures
• Miss rate as #entries increases?
– Goes down due to reduced capacity and conflict
misses
– Architects rule of thumb: miss rate drops ~2x for every
~4x increase in capacity (only a gross approximation)
• Miss penalty as #entries increases?
– Unchanged

At some point, increase in hit time for a larger cache may overcome
the improvement in hit rate, yielding a decrease in performance
10/24/16 Fall 2016 - Lecture #16 19
 Increasing Block Size?
• Hit time as block size increases?
– Hit time unchanged, but might be slight hit-time
reduction as number of tags is reduced, so faster to
access memory holding tags
• Miss rate as block size increases?
– Goes down at first due to spatial locality, then
increases due to increased conflict misses due to
fewer blocks in cache
• Miss penalty as block size increases?
– Rises with longer block size, but with fixed constant
initial latency that is amortized over whole block

10/24/16 Fall 2016 - Lecture #16 20

 Administrivia
• Midterm #2 1.5 weeks away!
November 1!
– In class! 3:40-5 PM
– Synchronous digital design and
Project 3 (processor design)
included
– Pipelines and Caches
– ONE Double sided Crib sheet
– Review Session, Sunday, 10/30,
1-3 PM, 10 Evans
155 Dwinelle

10/24/16 Fall 2016 - Lecture #16 21

 Clickers/Peer Instruction
For a cache of fixed capacity and blocksize, what
is the impact of increasing associativity on
AMAT:
A: Increases hit time, decreases miss rate
B: Decreases hit time, decreases miss rate
C: Increases hit time, increases miss rate
D: Decreases hit time, increases miss rate

10/24/16 Fall 2016 - Lecture #16 22

 Clickers/Peer Instruction
Impact of Larger Blocks on AMAT:
• For fixed total cache capacity and associativity,
what is effect of larger blocks on each component
of AMAT:
A: Decrease
B: Unchanged
C: Increase Shorter tags +, mux at edge -
Hit Time? C: Unchanged (but slight increase possible)
Miss Rate? A: Decrease (spatial locality; conflict???)
Miss Penalty? C: Increase (longer time to load block)
Write Allocation? It depends!
10/24/16 Fall 2016 - Lecture #16 23
 Clickers/Peer Instruction
Impact of Larger Blocks on Misses:
• For fixed total cache capacity and associativity,
what is effect of larger blocks on each component
of miss:
A: Decrease
B: Unchanged
C: Increase
Compulsory? A: Decrease (if good Spatial Locality)
Capacity? B: Increase (smaller blocks fit better)
Conflict? A: Increase (more ways better!)
Less effect for large caches
10/24/16 Fall 2016 - Lecture #16 24
 How to Reduce Miss Penalty?
• Could there be locality on misses from a
cache?
– Use multiple cache levels!
– With Moore’s Law, more room on die for bigger
L1$ and for second-level L2$
– And in some cases even an L3$!
• Mainframes have ~1GB L4 cache off-chip

10/24/16 Fall 2016 - Lecture #16 25

 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of Multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 26

 Memory Hierarchy
Processor
Increasing
Inner distance from
Level 1 processor,
Levels in decreasing
memory Level 2 speed
hierarchy Level 3
Outer ...
Level n

Size of memory at each level

As we move to outer levels the latency goes up
and price per bit goes down.
10/24/16 Fall 2016 - Lecture #16 27
 Local vs. Global Miss Rates
• Local miss rate: the fraction of references to one
level of a cache that miss
– Local Miss rate L2$ = L2$ Misses / L1$ Misses
= L2$ Misses / total_L2_accesses
• Global miss rate: the fraction of references that
miss in all levels of a multilevel cache
– L2$ local miss rate >> than the global miss rate

10/24/16 Fall 2016 - Lecture #16 28

 Local vs. Global Miss Rates
• Local miss rate – the fraction of references to one
level of a cache that miss
– Local Miss rate L2$ = $L2 Misses / L1$ Misses
• Global miss rate – the fraction of references that
miss in all levels of a multilevel cache
– L2$ local miss rate >> than the global miss rate
• Global Miss rate = L2$ Misses / Total Accesses
= (L2$ Misses / L1$ Misses) × (L1$ Misses / Total Accesses)
= Local Miss rate L2$ × Local Miss rate L1$

• AMAT = Time for a hit + Miss rate × Miss penalty

• AMAT = Time for a L1$ hit + (local) Miss rate L1$ ×
(Time for a L2$ hit + (local) Miss rate L2$ × L2$ Miss penalty)
10/24/16 Fall 2016 - Lecture #16 29
 Multilevel Cache Considerations
• Different design considerations for L1$ and L2$
– L1$ focuses on fast access: minimize hit time to achieve
shorter clock cycle, e.g., smaller $
– L2$, L3$ focus on low miss rate: reduce penalty of long main
memory access times: e.g., Larger $ with larger block
sizes/higher levels of associativity
• Miss penalty of L1$ is significantly reduced by presence
of L2$, so can be smaller/faster even with higher miss
rate
• For the L2$, fast hit time is less important than low miss
rate
– L2$ hit time determines L1$’s miss penalty
– L2$ local miss rate >> than the global miss rate

10/24/16 Fall 2016 -- Lecture #16 30

 L1 Cache: 32KB I$, 32KB D$
L2 Cache: 256 KB
L3 Cache: 4 MB

Cache Buster

10/24/16 Fall
Fall2016
2016--- Lecture #16
#13 31
 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of Multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 32

10/24/16 Fall 2016 - Lecture #16 33
 CPI/Miss Rates/DRAM Access
SpecInt2006
Data Only Data Only Instructions and Data

10/24/16 Fall
Fall2016
2016--- Lecture #16
#12 34
 Skylark: Intel’s Latest Generation
Laptop/Tablet Class CPUs

10/24/16 Fall 2016 -- Lecture #16 35

 Outline
• Understanding Cache Misses
• Increasing Cache Performance
• Performance of Multi-level Caches (L1,L2, …)
• Real world example caches
• And in Conclusion …

10/24/16 Fall 2016 – Lecture #16 36

 Bottom Line: Cache Design Space
• Several interacting dimensions Cache Size

– Cache size
Associativity
– Block size
– Associativity
– Replacement policy
– Write-through vs. write-back
Block Size
– Write allocation
• Optimal choice is a compromise
– Depends on access characteristics Bad
• Workload
• Use (I-cache, D-cache)
– Depends on technology / cost Good Factor A Factor B

• Simplicity often wins Less More

10/24/16 Fall 2016 - Lecture #16 37