CS 61C: Great Ideas in Computer

Architecture (Machine Structures)

Caches Part 1

Instructors:
Bernhard Boser & Randy H. Katz
hDp://[Link]/~cs61c/

10/13/16 Fall 2016 - Lecture #14 1

 New-School Machine Structures
So$ware 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 InstrucZons Core … Core
>1 instrucZon @ one Zme Memory (Cache)
e.g., 5 pipelined instrucZons
Input/Output Core
• Parallel Data
InstrucZon Unit(s) FuncZonal
>1 data item @ one Zme Unit(s)
e.g., Add of 4 pairs of words A0+B0 A1+B1 A2+B2 A3+B3
• Hardware descripZons
Cache Memory
All gates @ one Zme
Logic Gates
• Programming Languages
10/13/16 Fall 2016 - Lecture #14 2
 Components of a Computer
Memory
Processor Input
Enable?
Read/Write
Control

Program
Datapath
Address
PC Bytes
Write
Registers Data

ArithmeZc & Logic Unit Read Data

Output
(ALU) Data

Processor-Memory Interface I/O-Memory Interfaces

10/13/16 Fall 2016 - Lecture #14 3
 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 4

 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 5

 Why are Large Memories Slow?
Library Analogy
• Time to find a book in a large library
– Search a large card catalog – (mapping
Ztle/author to index number)
– Round-trip Zme to walk to the stacks
and retrieve the desired book
• Larger libraries worsen both delays
• Electronic memories have same issue,
plus the technologies used to store a
bit slow down as density increases
(e.g., SRAM vs. DRAM vs. Disk)
However what we want is a large
yet fast memory!
10/13/16 Fall 2016 - Lecture #14 6
 Processor-DRAM Gap (Latency)

1980 microprocessor executes ~one instruc7on in same Zme as DRAM access

2016 microprocessor executes ~1000 instruc7ons in same Zme as DRAM access
Slow DRAM access has disastrous impact on CPU performance!
10/13/16 Fall 2016 - Lecture #14 7
 What To Do: Library Analogy
• Write a report using library books
– E.g., works of J.D. Salinger
• Go to library, look up relevant books,
fetch from stacks, and place on desk in
library
• If need more, check them out and keep
on desk
– But don’t return earlier books since might
need them
• You hope this collecZon of ~10 books on
desk enough to write report, despite 10
being only 0.00001% of books in UC
Berkeley libraries
10/13/16 Fall 2016 - Lecture #14 8
 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 9

 Big Idea: Memory Hierarchy
Processor
Inner Increasing
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. Why?
10/13/16 Fall 2016 - Lecture #14 10
 Big Idea: Locality
• Temporal Locality (locality in Zme)
– Go back to same book on desk mulZple Zmes
– If a memory locaZon is referenced, then it will tend to
be referenced again soon
• SpaCal Locality (locality in space)
– When go to book shelf, pick up mulZple books on J.D.
Salinger since library stores related books together
– If a memory locaZon is referenced, the locaZons with
nearby addresses will tend to be referenced soon

10/13/16 Fall 2016 - Lecture #14 11

 Memory Reference PaDerns
Memory Address (one dot per access)

Temporal
Locality

Spa7al
Locality
Donald J. Hatfield, Jeanette Gerald: Program Restructuring for Virtual Memory. Time
IBM Systems Journal 10(3): 168-192 (1971)
10/13/16 Fall 2016 - Lecture #14 12
 Principle of Locality
• Principle of Locality: Programs access small
porZon of address space at any instant of Zme
(spaZal locality) and repeatedly access that
porZon (temporal locality)
• What program structures lead to temporal
and spaZal locality in instrucZon accesses?
• In data accesses?

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

 Memory Reference PaDerns
Address n loop itera7ons

Instruc7on
fetches

subrou7ne subrou7ne
call return
Stack
accesses
argument access

Data
accesses scalar accesses
Time
10/13/16 Fall 2016 - Lecture #14 14
10/13/16 Fall 2016 - Lecture #14 15
 Cache Philosophy
• Programmer-invisible hardware mechanism
gives illusion of speed of fastest memory with
size of largest memory
– Works even if you have no idea what a cache is
– Performance-oriented programmers someZmes
“reverse engineer” cache organizaZon to design
data structures and access paDerns opZmized for
a specific cache design
– You are going to do that in Project #4!

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

 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 17

 Memory Access without Cache
• Load word instrucZon: lw $t0,0($t1)
• $t1 contains 1022ten, Memory[1022] = 99

1. Processor issues address 1022ten to Memory

2. Memory reads word at address 1022ten (99)
3. Memory sends 99 to Processor
4. Processor loads 99 into register $t0

10/13/16 Fall 2016 - Lecture #14 18

 Adding Cache to Computer
Processor Memory
Enable? Input
Read/Write
Control

Cache Program
Datapath Memory (including
Address cache) organized
PC Bytes around blocks,
Write which are typically
Registers Data mulZple words

ArithmeZc & Logic Unit Data

Read Output
(ALU)
Data
Processor organized
around words and bytes
Processor-Memory Interface I/O-Memory Interfaces
10/13/16 Fall 2016 - Lecture #14 19
 Memory Access with Cache
• Load word instrucZon: lw $t0,0($t1)
• $t1 contains 1022ten, Memory[1022] = 99
• With cache: Processor issues address 1022ten to
Cache
1. Cache checks to see if has copy of data at address
1022ten
2a. If finds a match (Hit): cache reads 99, sends to processor
2b. No match (Miss): cache sends address 1022 to Memory
I. Memory reads 99 at address 1022ten
II. Memory sends 99 to Cache
III. Cache replaces word with new 99
IV. Cache sends 99 to processor
2. Processor loads 99 into register $t0
10/13/16 Fall 2016 - Lecture #14 20
 Administrivia
• Project 3-1 Released
tonight!
• Midterm #2 2.5 weeks
away! November 1!
– In class! 3:40-5 PM
– Focus on Pipelines and
Caches
– ONE Double sided Crib
sheet
– Review Session, Sunday,
10/30, 1-3 PM, 10 Evans

10/13/16 Fall 2016 - Lecture #14 21

 Cache “Tags”
• Need way to tell if have copy of locaZon in
memory so that can decide on hit or miss
• On cache miss, put memory address of block
in “tag address” of cache block
– 1022 placed in tag next to data from memory (99)
Tag Data

252 12
From earlier
1022 99 loads or stores
131 7
2041 20
10/13/16 Fall 2016 - Lecture #14 22
 Anatomy of a
16 Byte Cache, Processor
with 4 Byte Blocks
• OperaZons: 32-bit 32-bit
Address Data
1. Cache Hit
2. Cache Miss
3. Refill cache from 252 12
memory 1022 99
131 7
• Cache needs Address 2041 20
Tags to decide if Cache
Processor Address is a
32-bit
Cache Hit or Cache Miss Address
32-bit
Data
– Compares all four tags

10/13/16 Fall 2016 - Lecture #14

Memory 23
 Cache Replacement
• Suppose processor now requests locaZon 511, which
contains 11?
• Doesn’t match any cache block, so must “evict” a
resident block to make room
– Which block to evict?
• Replace “vicZm” with new memory block at address 511
Tag Data

252 12
1022 99
131 7
2041 20
10/13/16 Fall 2016 - Lecture #14 24
 Cache Replacement
• Suppose processor now requests locaZon 511, which
contains 11?
• Doesn’t match any cache block, so must “evict” a
resident block to make room
– Which block to evict?
• Replace “vicZm” with new memory block at address 511
Tag Data

252 12
1022 99
511 11
2041 20
10/13/16 Fall 2016 - Lecture #14 25
 Block Must be Aligned in Memory
• Word blocks are aligned, so binary address of
all words in cache always ends in 00two
• How to take advantage of this to save
hardware and energy?
• Don’t need to compare last 2 bits of 32-bit
byte address (comparator can be narrower)
– Don’t need to store last 2 bits of 32-bit byte
address in Cache Tag (Tag can be narrower)

10/13/16 Fall 2016 - Lecture #14 26

Anatomy of a 32B
Cache, 8B Blocks Processor
• Blocks must be aligned 32-bit 32-bit
in pairs, otherwise Address Data
could get same word
twice in cache
– Tags only have even- 252 12 -10
numbered words 1022 99 1000
– Last 3 bits of address 130 42 7
always 000two 2040 1947 20

– Tags, comparators can Cache

be narrower
32-bit 32-bit
• Can get hit for either Address Data
word in block
10/13/16 Fall 2016 - Lecture #14
Memory 27
 Hardware Cost of
Cache Processor
• Need to compare every 32-bit 32-bit
tag to the Processor Address Data
address
• Comparators are
expensive Set 0 Tag
Tag Data
Data
• OpZmizaZon: use two
“sets” of data with a total
of only 2 comparators Set 1 Tag
Tag Data
Data
• Use one Address bit to Cache
select which set
32-bit 32-bit
• Compare only tags from Address Data
selected set
• Generalize to more sets
10/13/16
Memory
Fall 2016 - Lecture #14 28
 Hardware Cost of
Cache Processor
32-bit 32-bit
Address Data

Tag
Compare
252 12 Even
Set 0 1022 99 Word
131 7
Odd
Set Set 1 2041 20
Word
31
Index
3 2 1 0 Cache
00 32-bit
Address
32-bit
Data
Byte in
10/13/16
word (block)
Fall 2016 - Lecture #14
Memory 29
 Processor Address Fields Used by
Cache Controller
• Block Offset: Byte address within block
• Set Index: Selects which set
• Tag: Remaining porZon of processor address
Processor Address (32-bits total)
Tag Set Index Block offset

• Size of Index = log2(number of sets)

• Size of Tag = Address size – Size of Index
– log2(number of bytes/block)
10/13/16 Fall 2016 - Lecture #14 30
 What Limits Number of Sets?
• For a given total number of blocks, we save
comparators if have more than two sets
• Limit: As Many Sets as Cache Blocks => only
one block per set – only needs one
comparator!
• Called “Direct-Mapped” Design

Tag Index Block offset

10/13/16 Fall 2016 - Lecture #14 31

 Direct Mapped Cache Example:
Mapping a 6-bit Memory Address
5 4 3 2 1 0

Tag Index Byte Offset

Mem Block Within Block Within $ Byte Within Block

$ Block
• In example, block size is 4 bytes/1 word
• Memory and cache blocks always the same size, unit of transfer between
memory and cache
• # Memory blocks >> # Cache blocks
– 16 Memory blocks = 16 words = 64 bytes => 6 bits to address all bytes
– 4 Cache blocks, 4 bytes (1 word) per block
– 4 Memory blocks map to each cache block
• Memory block to cache block, aka index: middle two bits
• Which memory block is in a given cache block, aka tag: top two bits
10/13/16 Fall 2016 - Lecture #14 32
 One More Detail: Valid Bit
• When start a new program, cache does not
have valid informaZon for this program
• Need an indicator whether this tag entry is
valid for this program
• Add a “valid bit” to the cache tag entry
0 => cache miss, even if by chance, address = tag
1 => cache hit, if processor address = tag

10/13/16 Fall 2016 - Lecture #14 33

 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 34

 Cache OrganizaZon:
Simple First Example
Main Memory
0000xx
0001xx One word blocks
Cache Two low order bits (xx)
0010xx
Index Valid Tag Data define the byte in the
0011xx
block (32b words)
00 0100xx
01 0101xx
10 0110xx
11 0111xx Q: Where in the cache is
1000xx the mem block?
Q: Is the memory block in 1001xx
cache? 1010xx Use next 2 low-order
Compare the cache tag to the 1011xx memory address bits –
high-order 2 memory address 1100xx the index – to determine
bits to tell if the memory 1101xx which cache block (i.e.,
block is in the cache 1110xx modulo the number of
(provided valid bit is set) 1111xx blocks in the cache)
10/13/16 Fall 2016 - Lecture #14 35
 Direct-Mapped Cache Example
• One word blocks, cache size = 1K words (or 4KB)
Byte offset
31 30 ... 13 12 11 ... 2 1 0

Tag 20 10 Data
Hit
Valid bit Index
ensures Read
Index Valid Tag Data
something 0 data
useful in 1
2
from
cache for . cache
this index .
.
instead
1021
1022
of
Compare 1023 memory
Tag with 20 32 if a Hit
upper part of
Address to Comparator
see if a Hit
What kind of locality are we taking advantage of?
10/13/16 Fall 2016 - Lecture #14 36
 MulZword-Block Direct-Mapped Cache
• Four words/block, cache size = 1K words
31 30 . . . 13 12 11 . . . 4 3 2 1 0
Byte offset
Hit Data

Tag 20 8 2 Word offset

Index
Data
Index Valid Tag
0
1
2
.
.
.
253
254
255
20

32
What kind of locality are we taking advantage of?
10/13/16 Fall 2016 - Lecture #14 37
 AlternaZve Cache OrganizaZons
• “Fully AssociaZve”: Block can go anywhere
– First design in lecture
– Note: No Index field, but one comparator/block
• “Direct Mapped”: Block goes one place
– Note: Only 1 comparator
– Number of sets = number blocks
• “N-way Set AssociaZve”: N places for a block
– Number of sets = number of blocks / N
– N comparators
– Fully AssociaDve: N = number of blocks
– Direct Mapped: N = 1
10/13/16 Fall 2016 - Lecture #14 38
 Range of Set-AssociaZve Caches
• For a fixed-size cache, and a given block size, each
increase by a factor of two in associaZvity doubles the
number of blocks per set (i.e., the number of “ways”)
and halves the number of sets –
• Decreases the size of the index by 1 bit and
increases the size of the tag by 1 bit

More AssociaZvity (more ways)

Tag Index Block offset

What if we can also change the block size?

10/13/16 Fall 2016 - Lecture #14 39
 Clickers/Peer InstrucZon
• For a cache with constant total capacity, if we
increase the number of ways by a factor of
two, which statement is false:
A: The number of sets could be doubled
B: The tag width could decrease
C: The block size could stay the same
D: The block size could be halved
E: Tag width must increase

10/13/16 Fall 2016 - Lecture #14 40

 Total Cache Capacity =
AssociaZvity * # of sets * block_size
Bytes = blocks/set * sets * Bytes/block
C=N* S * B
Tag Index Byte Offset
address_size = tag_size + index_size + offset_size
= tag_size + log2(S) + log2(B)
Double the AssociaZvity: Number of sets?
tag_size? index_size? # comparators?
Double the Sets: AssociaZvity?
tag_size? index_size? # comparators?
10/13/16 Fall 2016 - Lecture #14 41
 Outline
• Memory Hierarchy and Latency
• Caches Principles
• Basic Cache OrganizaZon
• Different Kinds of Caches
• Write Back vs. Write Through
• And in Conclusion …

10/13/16 Fall 2016 – Lecture #14 42

 And In Conclusion, …
• Principle of Locality for Libraries /Computer
Memory
• Hierarchy of Memories (speed/size/cost per
bit) to Exploit Locality
• Cache – copy of data lower level in memory
hierarchy
• Direct Mapped to find block in cache using Tag
field and Valid bit for Hit
• Cache design choice:
− Write-Through vs. Write-Back
10/13/16 Fall 2016 - Lecture #14 43