University of Technology – VNUHCM October 3, 2021

Principle of Locality
Computer Architecture • Programs access a small proportion of their
Chapter 5: Memory Hierarchy
address space at any time
• Temporal locality
– Items accessed recently are likely to be accessed again
soon
– e.g., instructions in a loop, induction variables
• Spatial locality
– Items near those accessed recently are likely to be
accessed soon
Adapted from Computer Organization the Hardware/Software Interface – 5th
– E.g., sequential instruction access, array data
Computer Engineering – CSE – HCMUT 1 Memory Hierarchy 2

Taking Advantage of Locality Memory Hierarchy Levels

• Block (aka line): unit of
• Memory hierarchy copying
– May be multiple words
• Store everything on disk • If accessed data is present in
upper level
• Copy recently accessed (and nearby) items – Hit: access satisfied by upper
level
from disk to smaller DRAM memory • Hit ratio: hits/accesses
– Main memory • If accessed data is absent
– Miss: block copied from lower
• Copy more recently accessed (and nearby) level
• Time taken: miss penalty
items from DRAM to smaller SRAM memory • Miss ratio: misses/accesses
= 1 – hit ratio
– Then accessed data supplied
– Cache memory attached to CPU from upper level

Memory Hierarchy 3 Memory Hierarchy 4

Chapter 5 – Memory Hierarchy 1

University of Technology – VNUHCM October 3, 2021

Memory Technology Cache Memory

• Static RAM (SRAM) • Cache memory
– 0.5ns – 2.5ns, $2000 – $5000 per GB
• Dynamic RAM (DRAM) – The level of the Mem. hierarchy closest to the CPU
– 50ns – 70ns, $20 – $75 per GB • Given accesses X1, …, Xn–1, Xn
• Flash Memory
– 5s – 50s, $0.75 - $1 per GB
• Magnetic disk • How do we know if
– 5ms – 20ms, $0.20 – $2 per GB the data is present?
• Ideal memory • Where do we look?
– Access time of SRAM
– Capacity and cost/GB of disk

Memory Hierarchy 5 Memory Hierarchy 6

Direct Mapped Cache Tags and Valid Bits

• Location determined by address • How do we know which particular block is
• Direct mapped: only one choice stored in a cache location?
– (Block address) modulo (#Blocks in cache) – Store block address as well as the data
– Actually, only need the high-order bits
• #Blocks is a – Called the tag
power of 2 • What if there is no data in a location?
• Use low-order – Valid bit: 1 = present, 0 = not present
address bits – Initially 0

7 Memory Hierarchy 8

Chapter 5 – Memory Hierarchy 2

University of Technology – VNUHCM October 3, 2021

Cache Example Cache Example

• 8-blocks, 1 word/block, direct mapped Word addr Binary addr Hit/miss Cache block
22 10 110 Miss 110
• Initial state
Index V Tag Data Index V Tag Data
000 N 000 N
001 N 001 N
010 N 010 N
011 N 011 N
100 N 100 N
101 N 101 N
110 N 110 Y 10 Mem[10110]
111 N 111 N
Memory Hierarchy 9 Memory Hierarchy 10

Cache Example Cache Example

Word addr Binary addr Hit/miss Cache block
Word addr Binary addr Hit/miss Cache block 22 10 110 Hit 110
26 11 010 Miss 010 26 11 010 Hit 010

Index V Tag Data Index V Tag Data

000 N 000 N
001 N 001 N
010 Y 11 Mem[11010] 010 Y 11 Mem[11010]
011 N 011 N
100 N 100 N
101 N 101 N
110 Y 10 Mem[10110] 110 Y 10 Mem[10110]
111 N 111 N
Memory Hierarchy 11 Memory Hierarchy 12

Chapter 5 – Memory Hierarchy 3

University of Technology – VNUHCM October 3, 2021

Cache Example Cache Example

Word addr Binary addr Hit/miss Cache block
16 10 000 Miss 000 Word addr Binary addr Hit/miss Cache block
3 00 011 Miss 011 18 10 010 Miss 010
16 10 000 Hit 000

Index V Tag Data Index V Tag Data

000 Y 10 Mem[10000] 000 Y 10 Mem[10000]
001 N 001 N
010 Y 11 Mem[11010] 010 Y 10 Mem[10010]
011 Y 00 Mem[00011] 011 Y 00 Mem[00011]
100 N 100 N
101 N 101 N
110 Y 10 Mem[10110] 110 Y 10 Mem[10110]
111 N 111 N
Memory Hierarchy 13 Memory Hierarchy 14

Address Subdivision Example: Larger Block Size

• 64 blocks, 16 bytes/block
– To what bytenumber does address 1200 map?
• Block address = 1200/16 = 75
• Block number = 75 modulo 64 = 11
31 10 9 4 3 0
Tag Index Offset
22 bits 6 bits 4 bits

Memory Hierarchy 15 Memory Hierarchy 16

Chapter 5 – Memory Hierarchy 4

University of Technology – VNUHCM October 3, 2021

Block Size Considerations Cache Misses

• Larger blocks should reduce miss rate • On cache hit, CPU proceeds normally
– Due to spatial locality • On cache miss
• But in a fixed-sized cache – Stall the CPU pipeline
– Larger blocks  fewer of them
– Fetch block from next level of hierarchy
• More competition  increased miss rate
– Instruction cache miss
– Larger blocks  pollution
• Restart instruction fetch
• Larger miss penalty
– Data cache miss
– Can override benefit of reduced miss rate
• Complete data access
– Early restart and critical-word-first can help
Memory Hierarchy 17 Memory Hierarchy 18

Write-Through Write-Back
• On data-write hit, could just update the block in • Alternative: On data-write hit, just update the
cache
– But then cache and memory would be inconsistent block in cache
• Write through: also update memory – Keep track of whether each block is dirty
• But makes writes take longer • When a dirty block is replaced
– e.g., if base CPI = 1, 10% of instructions are stores, write to
memory takes 100 cycles – Write it back to memory
• Effective CPI = 1 + 0.1×100 = 11
– Can use a write buffer to allow replacing block to
• Solution: write buffer
– Holds data waiting to be written to memory
be read first
– CPU continues immediately
• Only stalls on write if write buffer is already full

Memory Hierarchy 19 Memory Hierarchy 20

Chapter 5 – Memory Hierarchy 5

University of Technology – VNUHCM October 3, 2021

Write Allocation Example: Intrinsity FastMATH

• What should happen on a write miss? • Embedded MIPS processor
– 12-stage pipeline
• Alternatives for write-through – Instruction and data access on each cycle
– Allocate on miss: fetch the block • Split cache: separate I-cache and D-cache
– Write around: don’t fetch the block – Each 16KB: 256 blocks × 16 words/block
• Since programs often write a whole block before – D-cache: write-through or write-back
reading it (e.g., initialization) • SPEC2000 miss rates
• For write-back – I-cache: 0.4%
– Usually fetch the block – D-cache: 11.4%
– Weighted average: 3.2%
Memory Hierarchy 21 Memory Hierarchy 22

Example: Intrinsity FastMATH Main Memory Supporting Caches

• Use DRAMs for main memory
– Fixed width (e.g., 1 word)
– Connected by fixed-width clocked bus
• Bus clock is typically slower than CPU clock
• Example cache block read
– 1 bus cycle for address transfer
– 15 bus cycles per DRAM access
– 1 bus cycle per data transfer
• For 4-word block, 1-word-wide DRAM
– Miss penalty = 1 + 4×15 + 4×1 = 65 bus cycles
– Bandwidth = 16 bytes / 65 cycles = 0.25 B/cycle

Memory Hierarchy 23 Memory Hierarchy 24

Chapter 5 – Memory Hierarchy 6

University of Technology – VNUHCM October 3, 2021

Increasing Memory Bandwidth Measuring Cache Performance

• Components of CPU time
– Program execution cycles
• Includes cache hit time
– Memory stall cycles
• Mainly from cache misses
• With simplifying assumptions:
• 4-word wide memory Memory accesses
- Miss penalty = 1 + 15 + 1 = 17 bus cycles Memory stall cycles =  Miss rate  Miss penalty
Program
- Bandwidth = 16 bytes / 17 cycles = 0.94 B/cycle
• 4-bank interleaved memory Instructions Misses
=   Miss penalty
- Miss penalty = 1 + 15 + 4×1 = 20 bus cycles Program Instruction
- Bandwidth = 16 bytes / 20 cycles = 0.8 B/cycle
Memory Hierarchy 25 Memory Hierarchy 26

Cache Performance Example Average Access Time

• Given • Hit time is also important for performance
– I-cache miss rate = 2%
– D-cache miss rate = 4% • Average memory access time (AMAT)
– Miss penalty = 100 cycles – AMAT = Hit time + Miss rate × Miss penalty
– Base CPI (ideal cache) = 2
– Load & stores are 36% of instructions • Example
• Miss cycles per instruction – CPU with 1ns clock, hit time = 1 cycle, miss
– I-cache: 0.02 × 100 = 2 penalty = 20 cycles, I-cache miss rate = 5%
– D-cache: 0.36 × 0.04 × 100 = 1.44 – AMAT = 1 + 0.05 × 20 = 2ns
• Actual CPI = 2 + 2 + 1.44 = 5.44 • 2 cycles per instruction
– Ideal CPU is 5.44/2 =2.72 times faster
Memory Hierarchy 27 Memory Hierarchy 28

Chapter 5 – Memory Hierarchy 7

University of Technology – VNUHCM October 3, 2021

Performance Summary Exercise

• When CPU performance increased • Assume that, a memory has 20-bit byte
– Miss penalty becomes more significant address
• Decreasing base CPI a) How many bits does the 16 one-word
– Greater proportion of time spent on memory blocks direct-mapped cache need?
stalls
• Increasing clock rate b) How about the 8 2-word blocks direct-
– Memory stalls account for more CPU cycles
mapped cache?
• Can’t neglect cache behavior when evaluating
system performance
Memory Hierarchy 29 Memory Hierarchy 30

Associative Caches Associative Cache Example

• Fully associative
– Allow a given block to go in any cache entry
– Requires all entries to be searched at once
– Comparator per entry (expensive)
• n-way set associative
– Each set contains n entries
– Block number determines which set
• (Block number) modulo (#Sets in cache)
– Search all entries in a given set at once
– n comparators (less expensive)
Memory Hierarchy 31 Memory Hierarchy 32

Chapter 5 – Memory Hierarchy 8

University of Technology – VNUHCM October 3, 2021

Spectrum of Associativity Associativity Example

• For a cache with 8 entries • Compare 4-block caches
– Direct mapped, 2-way set associative,
fully associative
– Block access sequence: 0, 8, 0, 6, 8

• Direct mapped
Block Cache Hit/miss Cache content after access
address index 0 1 2 3
0 0 miss Mem[0]
8 0 miss Mem[8]
0 0 miss Mem[0]
6 2 miss Mem[0] Mem[6]
8 0 miss Mem[8] Mem[6]

Memory Hierarchy 33 Memory Hierarchy 34

Associativity Example How Much Associativity

• 2-way set associative • Increased associativity decreases miss rate
Block Cache Hit/miss Cache content after access
address index Set 0 Set 1 – But with diminishing returns
0 0 miss Mem[0]
8
0
0
0
miss
hit
Mem[0]
Mem[0]
Mem[8]
Mem[8]
• Simulation of a system with 64KB
6
8
0
0
miss
miss
Mem[0]
Mem[8]
Mem[6]
Mem[6]
D-cache, 16-word blocks, SPEC2000
– 1-way: 10.3%
• Fully associative
Block Hit/miss Cache content after access – 2-way: 8.6%
address
0 miss Mem[0] – 4-way: 8.3%
8 miss Mem[0] Mem[8]
0
6
hit
miss
Mem[0]
Mem[0]
Mem[8]
Mem[8] Mem[6]
– 8-way: 8.1%
8 hit Mem[0] Mem[8] Mem[6]

Memory Hierarchy 35 Memory Hierarchy 36

Chapter 5 – Memory Hierarchy 9

University of Technology – VNUHCM October 3, 2021

Set Associative Cache Organization Replacement Policy

• Direct mapped: no choice
• Set associative
– Prefer non-valid entry, if there is one
– Otherwise, choose among entries in the set
• Least-recently used (LRU)
– Choose the one unused for the longest time
• Simple for 2-way, manageable for 4-way, too hard
beyond that
• Random
– Gives approximately the same performance as
LRU for high associativity

Memory Hierarchy 37 Memory Hierarchy 39

Least Recently Used Algorithm Multilevel Caches

• Need to keep track of what was used when • Primary cache attached to CPU
• Keep “age bits” for each cache line – Small, but fast
• Update all the “age bits” of all cache lines • Level-2 cache services misses from primary
when a cache line is used cache
→ Pseudo-LRU: use one bit per cache line – Larger, slower, but still faster than main memory
• Main memory services L-2 cache misses
• Some high-end systems include L-3 cache

Memory Hierarchy 40 Memory Hierarchy 41

Chapter 5 – Memory Hierarchy 10

University of Technology – VNUHCM October 3, 2021

Multilevel Cache Example Example (cont.)

• Given • Now add L-2 cache
– CPU base CPI = 1, clock rate = 4GHz – Access time = 5ns
– Global miss rate to main memory = 0.5%
– Miss rate/instruction = 2%
• Primary miss with L-2 hit
– Main memory access time = 100ns
– Penalty = 5ns/0.25ns = 20 cycles
• With just primary cache • Primary miss with L-2 miss
– Miss penalty = 100ns/0.25ns = 400 cycles – Extra penalty = 400 cycles
– Effective CPI = 1 + 0.02 × 400 = 9 • CPI = 1 + 0.02 × 20 + 0.005 × 400 = 3.4
• Performance ratio = 9/3.4 = 2.6

Memory Hierarchy 42 Memory Hierarchy 43

Multilevel Cache Considerations Virtual Memory

• Primary cache • Use main memory as a “cache” for secondary
(disk) storage
– Focus on minimal hit time – Managed jointly by CPU hardware and the operating
• L-2 cache system (OS)
• Programs share main memory
– Focus on low miss rate to avoid main memory – Each gets a private virtual address space holding its
access frequently used code and data
– Hit time has less overall impact – Protected from other programs
• CPU and OS translate virtual addresses to physical
• Results addresses
– L-1 cache usually smaller than a single cache – VM “block” is called a page
– L-1 block size smaller than L-2 block size – VM translation “miss” is called a page fault

Memory Hierarchy 44 Memory Hierarchy 62

Chapter 5 – Memory Hierarchy 11

University of Technology – VNUHCM October 3, 2021

Address Translation Page Fault Penalty

• Fixed-size pages (e.g., 4K) • On page fault, the page must be fetched from
disk
– Takes millions of clock cycles
– Handled by OS code
• Try to minimize page fault rate
– Fully associative placement
– Smart replacement algorithms

Memory Hierarchy 63 Memory Hierarchy 64

Page Tables Translation Using a Page Table

• Stores placement information
– Array of page table entries, indexed by virtual
page number
– Page table register in CPU points to page table in
physical memory
• If page is present in memory
– PTE stores the physical page number
– Plus other status bits (referenced, dirty, …)
• If page is not present
– PTE can refer to location in swap space on disk

Memory Hierarchy 65 Memory Hierarchy 66

Chapter 5 – Memory Hierarchy 12

University of Technology – VNUHCM October 3, 2021

Mapping Pages to Storage Replacement and Writes

• To reduce page fault rate, prefer least-recently
used (LRU) replacement
– Reference bit (aka use bit) in PTE set to 1 on
access to page
– Periodically cleared to 0 by OS
– A page with reference bit = 0 has not been used
recently
• Disk writes take millions of cycles
– Block at once, not individual locations
– Write through is impractical
– Use write-back
– Dirty bit in PTE set when page is written
Memory Hierarchy 67 Memory Hierarchy 68

Fast Translation Using a TLB Fast Translation Using a TLB

• Address translation would appear to require extra
memory references
– One to access the PTE
– Then the actual memory access
• But access to page tables has good locality
– So use a fast cache of PTEs within the CPU
– Called a Translation Look-aside Buffer (TLB)
– Typical: 16–512 PTEs, 0.5–1 cycle for hit, 10–100 cycles for
miss, 0.01%–1% miss rate
– Misses could be handled by hardware or software
Memory Hierarchy 69 Memory Hierarchy 70

Chapter 5 – Memory Hierarchy 13

University of Technology – VNUHCM October 3, 2021

TLB and Cache Interaction TLB Misses

• If cache tag uses • If page is in memory
physical address – Load the PTE from memory and retry
– Need to translate before
cache lookup
– Could be handled in hardware
• Can get complex for more complicated page table
• Alternative: use virtual structures
address tag – Or in software
– Complications due to • Raise a special exception, with optimized handler
aliasing
• Different virtual • If page is not in memory (page fault)
addresses for shared
physical address
– OS handles fetching the page and updating the
page table
– Then restart the faulting instruction
Memory Hierarchy 71 Memory Hierarchy 72

TLB Miss Handler Page Fault Handler

• TLB miss indicates • Use faulting virtual address to find PTE
– Page present, but PTE not in TLB • Locate page on disk
– Page not preset
• Choose page to replace
• Must recognize TLB miss before destination
register overwritten – If dirty, write to disk first
– Raise exception • Read page into memory and update page
• Handler copies PTE from memory to TLB table
– Then restarts instruction • Make process runnable again
– If page not present, page fault will occur – Restart from faulting instruction
Memory Hierarchy 73 Memory Hierarchy 74

Chapter 5 – Memory Hierarchy 14

University of Technology – VNUHCM October 3, 2021

Memory Protection The Memory Hierarchy

The BIG Picture
• Different tasks can share parts of their virtual • Common principles apply at all levels of the
address spaces memory hierarchy
– But need to protect against errant access
– Based on notions of caching
– Requires OS assistance
• Hardware support for OS protection • At each level in the hierarchy
– Privileged supervisor mode (aka kernel mode) – Block placement
– Privileged instructions – Finding a block
– Page tables and other state information only – Replacement on a miss
accessible in supervisor mode
– Write policy
– System call exception (e.g., syscall in MIPS)
Memory Hierarchy 75 Memory Hierarchy 76

Exercise Solution
• Given the TLB (fully associative)
and the Page table (4KB pages)
V
1
Physical or Disk
5
V Tag Physical
• Virtual address (decimal): 4669, 2227, 13916,
1 11 12
with LRU replacement
0 Disk 1 7 4
34587, 48870, 12608, 49225
• If pages must be brought from
disk, increment the next largest 0 Disk 1 3 6 • Binary address: 4KB pages => 12-bit page offset
page number 1 6 0 4 9
a. Show the final state of the TLB 1 9
– 4669 = 1_0010_0011_1101, VPN = 1
and Page table if virtual address
requests are as follow:
1 11 – 2227 = 0_1000_1011_0011, VPN = 0
– 4669, 2227, 13916, 34587, 48870, 0 Disk
– 13916 = 11_0110_0101_1100, VPN = 3
12608, 49225 1 4
– 12948, 49419, 46814, 13975, 0 Disk – 34587 = 1000_0111_0001_1011, VPN = 8
40004, 12707, 52236
b. The same question but 16KB 0 Disk – 48870 = 1011_1110_1110_0110, VPN = 11
pages instead of 4KB 1 3
– 12608 = 11_0001_0100_0000, VPN = 3
1 12
– 49225 = 1100_0000_0100_1001, VPN = 12
Hint: Analyse the virtual address to extract virtual page number
Memory Hierarchy 77 Memory Hierarchy 78

Chapter 5 – Memory Hierarchy 15

University of Technology – VNUHCM October 3, 2021

Memory Hierarchy 79 Memory Hierarchy 80

Block Placement Finding a Block

• Determined by associativity • Hardware caches
– Direct mapped (1-way associative) – Reduce comparisons to reduce cost
• One choice for placement • Virtual memory
– n-way set associative – Full table lookup makes full associativity feasible
• n choices within a set – Benefit in reduced miss rate
– Fully associative Associativity Location method Tag comparisons
• Any location Direct mapped Index 1
• Higher associativity reduces miss rate n-way set Set index, then search n
associative entries within the set
– Increases complexity, cost, and access time Fully associative Search all entries #entries
Full lookup table 0
Memory Hierarchy 81 Memory Hierarchy 82

Chapter 5 – Memory Hierarchy 16

University of Technology – VNUHCM October 3, 2021

Replacement Write Policy

• Choice of entry to replace on a miss • Write-through
– Least recently used (LRU) – Update both upper and lower levels
– Simplifies replacement, but may require write
• Complex and costly hardware for high associativity buffer
– Pseudo-LRU • Write-back
• Close to LRU, less costly hardware – Update upper level only
– Random – Update lower level when block is replaced
• Close to LRU, easier to implement – Need to keep more state
• Virtual memory • Virtual memory
– Only write-back is feasible, given disk write
– LRU approximation with hardware support latency

Memory Hierarchy 83 Memory Hierarchy 84

Sources of Misses Concluding Remarks

• Compulsory misses (aka cold start misses) • Fast memories are small, large memories are slow
– First access to a block – We really want fast, large memories 
• Capacity misses – Caching gives this illusion ☺
– Due to finite cache size • Principle of locality
– A replaced block is later accessed again – Programs use a small part of their memory space
frequently
• Conflict misses (aka collision misses)
• Memory hierarchy
– In a non-fully associative cache
– L1 cache  L2 cache  …  DRAM memory
– Due to competition for entries in a set  disk
– Would not occur in a fully associative cache of the • Memory system design is critical for multiprocessors
same total size
Memory Hierarchy 85 Memory Hierarchy 86

Chapter 5 – Memory Hierarchy 17