ECE 5755: Modern Computer Systems and Architecture

Lecture 10: Memory Hierarchy

Lynn Ann Conway, an American computer scientist, electrical engineer, and transgender activist, invested generalized dynamic instruction handling, a key advanced in out-of-order execution. Her work was also instrumental in VLSI chip design and electronic design automation.

Today’s agenda

• Lab 1 is out!
• Memory Hierarchy & Caching

Photos, illustrations, graphics here.

Memory Hierarchy Design

• Until now we have assumed an ideal memory
• All accesses are 1 cycle
• Unlimited size, very fast memory
• Fast memory is very expensive (power, cost)!
• Large amounts of fast memory would actually be very slow…
• There are always tradeoffs in memory design:
• Cost vs. speed & size vs. speed

​

​

​

Smaller, fast expensive memory close to the core (Cache, $)

Larger, slower, cheaper memory farther away

Photos, illustrations, graphics here.

Memory Wall in Modern GPUs

AI and Memory Wall. Gholami et. al. https://arxiv.org/pdf/2403.14123

Since the plot ended: HBM bandwidth per GPU

Peak FLOPS grew faster still: H100 ≈ 2 PF (FP8) → B200 ≈ 9 PF (FP4) → Rubin 50 PF (NVFP4).

Machine balance keeps rising: ≈ 590 → 1,100 → 2,300 FLOP per byte of HBM.

Photos, illustrations, graphics here.

What do we put in smaller, faster memories?

• Locality of memory references
• Property of real programs, few exceptions

​

​

• Temporal locality
• Recently referenced data is likely to be referenced again soon
• Reactive: cache recently used data in small, fast memory

​

• Spatial locality
• More likely to reference data near recently referenced data
• Proactive: fetch data in large chunks to include nearby data, how?

​

• Holds for data and instructions.
• Why? Where does it come from?

Photos, illustrations, graphics here.

Knowing that You Found It: Tags

• Each frame can hold one of 2¹⁷ blocks
• All blocks with same index bit pattern
• How to know which if any is currently there?
• To each frame attach tag and valid bit (why do we need valid bits?)
• Compare frame tag to address tag bits
• No need to match index bits (why?)
• Lookup algorithm
• Read frame indicated by index bits
• “Hit” if tag matches and valid bit is set
• Otherwise, a “miss”. Get data from next level

0

1

1021

1022

1023

2

3

[4:0]

tag [31:15]

data

index [14:5]

<<

address

=

hit?

wordlines

Photos, illustrations, graphics here.

How do caches work?

• Where does a block go when it is fetched?
• Block placement policy
• How do we find a block in the cache?
• Block identification policy
• When fetching a block into a full cache, how do we determine what other block gets kicked out?
• Block replacement policy
• Do any of these answers differ for read and writes?
• Write strategy

Photos, illustrations, graphics here.

Functional view of caches

• Cache if made of “frames”
• A frame includes {Data, tag, state bits}
• Tag: Portion of address to identify the memory address location
• State bits: Valid (tag/data present), Dirty (has data been written to since block placed in cache)

​

​

# find frame(s)

​

If (look up tag != stored tag) {

# miss

Evict block in frame

Replace block from memory (or next level in memory hierarchy)

}

​

Return memory corresponding to lookup address

Photos, illustrations, graphics here.

Direct mapped cache

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

Photos, illustrations, graphics here.

Direct mapped cache

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

1: Miss

3: Hit

2: Miss

4: Hit

3: Miss

15: Miss

01

Mem(4)

11

Mem(15)

References: 8

​

Misses: 6

Hits: 2

Photos, illustrations, graphics here.

The architecture of a direct mapped cache

What locality are we exploiting?

Photos, illustrations, graphics here.

Handling cache hits

Read hits (I$ and D$) – this is what we want!

​

• Write hits (D$ only)
• allow cache and memory to be inconsistent
• Write the data only into the cache block (write-back the cache contents to the next level in the memory hierarchy when that cache block is “evicted”)
• Need a dirty bit for each data cache block to tell if it needs to be written back to memory when it is evicted
• require the cache and memory to be consistent
• Always write the data into both the cache block and the next level in the memory hierarchy (write-through) so don’t need a dirty bit
• Writes run at the speed of the next level in the memory hierarchy–so slow! – or can use a write buffer, so only have to stall if the write buffer is full

​

Photos, illustrations, graphics here.

Write-through caching

• Write buffer in between the cache and main memory
• Processor: writes data into the cache and the write buffer
• Memory controller: writes contents of the write buffer to the memory
• The write buffer is a FIFO (first-in first-out)
• Typically has ~4 entries
• Works OK if the store frequency (time, not cycles) << 1 / DRAM write cycle
• This can be a nightmare when store frequency approaches 1 / DRAM write cycle as it leads to write buffer saturation
• One solution is to use a write-back cache (L2 cache, future lectures)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

01

Mem(4)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

0: Miss

00

Mem(0)

01

Mem(4)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

0: Miss

4: Miss

00

Mem(0)

01

Mem(4)

01

Mem(4)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

0: Miss

4: Miss

4: Miss

0: Miss

0: Miss

4: Miss

4: Miss

00

Mem(0)

00

Mem(0)

00

Mem(0)

01

Mem(4)

01

Mem(4)

01

Mem(4)

01

Mem(4)

References: 8

​

Misses: 8

Hits:0

Photos, illustrations, graphics here.

What types of misses do we have in caches?

• Compulsory
• Cold start or process migration, first reference
• First access to a block, “cold” fact of life, not much we can do…
• If you have large enough programs (e.g., millions of accesses) conflict misses usually aren’t a big deal
• Conflict
• Collisions
• Multiple memory locations mapped to the same cache location
• Solution 1: Increase cache size
• Solution 2: Increase associativity
• Capacity
• Cache cannot contain all blocks accessed by a program
• Solution: Increase the cache size

Photos, illustrations, graphics here.

Handling Cache Misses

• Read misses (I$ and D$)
• Stall the pipeline, fetch the block from the next level in the memory hierarchy, install it in the cache and send the requested word to the processor and resume the pipeline
• Write misses (D$ only)
• Stall the pipeline, fetch the block from the next level in the memory hierarchy, install it in the cache, write the word from the processor to the cache and let the pipeline resume…

or (in write back caches…)

• Write allocate: just write the word into the cache updating both the tag and data (which may involve evicting a dirty block if using a write-back cache), no need to check for cache hit, no need to stall

Or (in write-through caches with a write buffer)

• No-write allocate: Skip the cache write and just write the word to the write buffer (eventually to the next memory level), no need to stall if the write buffer isn’t full; must invalidate the cache block since it will be inconsistent (now holding stale data)

Photos, illustrations, graphics here.

How do we exploit spatial locality?

Photos, illustrations, graphics here.

How do we exploit spatial locality?

• Four word per block, with a cache size of 1000 words

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

References: 8

​

Misses:4

Hits:4

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

1: Hit

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

1: Hit

2: Miss

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

1: Hit

2: Miss

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

1: Hit

2: Miss

3: Hit

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

01

Mem(5)

1: Hit

2: Miss

3: Hit

4: Miss

Mem(4)

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

01

Mem(5)

1: Hit

2: Miss

3: Hit

4: Miss

3: Hit

Mem(4)

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

01

Mem(5)

1: Hit

2: Miss

3: Hit

4: Miss

3: Hit

4: Hit

Mem(4)

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

01

Mem(5)

1: Hit

2: Miss

3: Hit

4: Miss

3: Hit

4: Hit

15: Miss

Mem(4)

11

Mem(15)

Mem(14)

Photos, illustrations, graphics here.

Taking advantage of spatial locality…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

01

Mem(5)

References: 8

​

Misses:4

Hits:4

​

Before it was

6 misses + 2 hits

1: Hit

2: Miss

3: Hit

4: Miss

3: Hit

4: Hit

15: Miss

Mem(4)

11

Mem(15)

Mem(14)

Photos, illustrations, graphics here.

Block size tradeoffs

• Larger block size takes advantage of spatial locality but…
• If block size is too large relative to the cache size, the miss rate will go up (sacrificing temporal locality)
• Larger block size means larger miss penalty
• Need to fetch multiple data elements each time!

Photos, illustrations, graphics here.

Multi-word block considerations

• Read misses (I$ and D$)
• Processed the same as for single word blocks – a miss returns the entire block from memory
• Miss penalty grows as block size grows

Photos, illustrations, graphics here.

Multi-word block considerations

• Read misses (I$ and D$)
• Processed the same as for single word blocks – a miss returns the entire block from memory
• Miss penalty grows as block size grows
• Early restart – datapath resumes execution as soon as the requested word of the block is returned
• Requested word first – requested word is transferred from the memory to the cache (and datapath) first

​

Photos, illustrations, graphics here.

Multi-word block considerations

• Read misses (I$ and D$)
• Processed the same as for single word blocks – a miss returns the entire block from memory
• Miss penalty grows as block size grows
• Early restart – datapath resumes execution as soon as the requested word of the block is returned
• Requested word first – requested word is transferred from the memory to the cache (and datapath) first
• Non-blocking cache–allows the datapath to continue to access the cache while the cache is handling an earlier miss

​

Photos, illustrations, graphics here.

Multi-word block considerations

• Read misses (I$ and D$)
• Processed the same as for single word blocks – a miss returns the entire block from memory
• Miss penalty grows as block size grows
• Early restart – datapath resumes execution as soon as the requested word of the block is returned
• Requested word first – requested word is transferred from the memory to the cache (and datapath) first
• Non-blocking cache–allows the datapath to continue to access the cache while the cache is handling an earlier miss
• Write misses (D$)
• Can’t use write allocate or will endup with a“garbled” block in the cache (e.g., for 4 word blocks, a new tag, one word of data from the new block, and three words of data from the old block), so must fetch the block from memory first and pay the stall time

​

Photos, illustrations, graphics here.

Cache Summary

• The Principle of Locality:
• Program likely to access a relatively small portion of the address space at any instant of time
• Temporal Locality: Locality in Time
• Spatial Locality: Locality in Space

Photos, illustrations, graphics here.

Cache Summary

• The Principle of Locality:
• Program likely to access a relatively small portion of the address space at any instant of time
• Temporal Locality: Locality in Time
• Spatial Locality: Locality in Space
• Three major categories of cache misses:
• Compulsory misses: sad facts of life. Example: cold start misses
• Conflict misses: increase cache size and/or associativity Nightmare Scenario: ping pong effect!
• Capacity misses: increase cache size

Photos, illustrations, graphics here.

Cache Summary

• The Principle of Locality:
• Program likely to access a relatively small portion of the address space at any instant of time
• Temporal Locality: Locality in Time
• Spatial Locality: Locality in Space
• Three major categories of cache misses:
• Compulsory misses: sad facts of life. Example: cold start misses
• Conflict misses: increase cache size and/or associativity Nightmare Scenario: ping pong effect!
• Capacity misses: increase cache size
• Cache design space�– totalsize, blocksize, associativity (replacement policy) – write-hitpolicy (write-through, write-back)�– write-miss policy (writeallocate, writebuffers)

Photos, illustrations, graphics here.

Reducing cache miss rates (part 1)

1. Allow more flexible block placement

​

• In a direct mapped cache a memory block maps to exactly one cache block
• At the other extreme, could allow a memory block to be mapped to any cache block – fully associative cache

​

• A compromise is to divide the cache into sets each of which consists of n “ways” (n-way set associative). A memory block maps to a unique set (specified by the index field) and can be placed in any way of that set (so there are n choices)

(block address) modulo (# sets in the cache)

​

Photos, illustrations, graphics here.

Set associative cache

0

Cache

Q2: How do we find it?

​

Use next 1 low order memory address bit to determine which cache set (i.e., modulo the number of sets in the cache)

Tag

Data

Q1: Is it there?

​

Compare all the cache tags in the set to the high order 3 memory address bits to tell if the memory block is in the cache

V

0000xx

0001xx

0010xx

0011xx

0100xx

0101xx

0110xx

0111xx

1000xx

1001xx

1010xx

1011xx

1100xx

1101xx

1110xx

1111xx

Two low order bits define the byte in the word (32-b words)

One word blocks

Set

1

0

1

Way

0

1

Photos, illustrations, graphics here.

Set associative cache

0

Cache

Q2: How do we find it?

​

Use next 1 low order memory address bit to determine which cache set (i.e., modulo the number of sets in the cache)

Tag

Data

Q1: Is it there?

​

Compare all the cache tags in the set to the high order 3 memory address bits to tell if the memory block is in the cache

V

0000xx

0001xx

0010xx

0011xx

0100xx

0101xx

0110xx

0111xx

1000xx

1001xx

1010xx

1011xx

1100xx

1101xx

1110xx

1111xx

Two low order bits define the byte in the word (32-b words)

One word blocks

Set

1

0

1

Way

0

1

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

0: Hit

Photos, illustrations, graphics here.

Lets look at another case…

• Consider the following main memory accesses:
• Starting with an empty cache (all blocks are initially marked as not valid)

0: Miss

4: Miss

0: Hit

4: Hit

References: 8

Misses: 2

Hits:6

​

(Before 8 misses)

• Solves the ping pong effect in a direct mapped cache due to conflict misses since now two memory locations that map into the same cache set can co-exist!

Photos, illustrations, graphics here.

Four-way set associative cache

• 2⁸ = 256 sets each with four ways (each with one block)

Photos, illustrations, graphics here.

Four-way set associative cache

Block offset

Byte offset

Index

Tag

• For a fixed size cache, each increase by a factor of two in associativity doubles the number of blocks per set (i.e., the number or 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

Photos, illustrations, graphics here.

Costs of associative caches

• When a miss occurs, which way’s block do we pick for replacement?
• Least Recently Used (LRU): the block replaced is the one that has been unused for the longest time
• Must have hardware to keep track of when each way’s block was used relative to the other blocks in the set
• For 2-way set associative, takes one bit per set → set the bit when a block is referenced (and reset the other way’s bit)
• N-way set associative cache costs
• N comparators (delay and area)
• MUX delay (set selection) before data is available
• Data available after set selection (and Hit/Miss decision). In a direct mapped cache, the cache block is available before the Hit/Miss decision
• So its not possible to just assume a hit and continue and recover later if it was a miss

Photos, illustrations, graphics here.

Summary of Associativity

• Direct Mapped
• One place in cache, One Comparator, No Muxes
• Set Associative Caches
• Restricted set of places
• N-way set associativity
• Number of comparators = number of blocks per set
• N:1 mux
• Fully Associative
• Anywhere in cache
• Number of comparators = number of blocks in cache
• Large mux or CAM needed

Photos, illustrations, graphics here.

Reducing Cache Miss Rates (part 2)

Use multiple levels of caches

​

• With advancing technology have more than enough room on the die for bigger L1 caches or for a second level of caches – normally a unified L2 cache (i.e., it holds both instructions and data) and in some cases even a unified L3 cache

​

Quiz # 1: CPI_ideal of 2, 100 cycle miss penalty (to main memory), 36% load/stores, a 2% (4%) L1I$ (D$) miss rate, add a UL2$ that has a 25 cycle miss penalty and a 0.5% miss rate

• 2 + .02×25 + .36×.04×25 + .005×100 + .36×.005×100
• 2 + .36×.04×25 + .36×.005×100
• 2 + .04×25 + .36×.02×25 + .005×100 + .36×.005×100
• 2 + .02×100 + .36×.04×100 + .005×25 + .36×.005×25

​

Photos, illustrations, graphics here.

Reducing Cache Miss Rates (part 2)

Use multiple levels of caches

​

• With advancing technology have more than enough room on the die for bigger L1 caches or for a second level of caches – normally a unified L2 cache (i.e., it holds both instructions and data) and in some cases even a unified L3 cache

​

• For our example, CPI_ideal of 2, 100 cycle miss penalty (to main memory), 36% load/stores, a 2% (4%) L1I$ (D$) miss rate, add a UL2$ that has a 25 cycle miss penalty and a 0.5% miss rate

​

CPI_stalls = 2 + .02×25 + .36×.04×25 + .005×100 + .36×.005×100 = 3.54 (as compared to 5.44 with no L2$)

​

Photos, illustrations, graphics here.

Multi-level Cache Design Optimization

• Design considerations for L1 and L2 caches are very different
• Primary cache should focus on minimizing hit time in support of a shorter clock cycle
• Smaller with smaller block sizes
• Secondary cache(s) should focus on reducing miss rate to reduce the penalty of long main memory access times
• Larger with larger block sizes

​

• The miss penalty of the L1 cache is significantly reduced by the presence of an L2 cache – so it can be smaller (i.e., faster) but have a higher miss rate
• For the L2 cache, hit time is less important than miss rate
• The L2$ hit time determines L1$’s miss penalty

Photos, illustrations, graphics here.

Cache design parameters

Ranges span 2023–25 CPUs: AMD Zen 4/5, Intel Lion Cove, Arm Neoverse V2 (NVIDIA Grace), Apple M-series. Cycle counts assume ~4–5 GHz cores; DRAM latency is roughly constant in ns, so it grows in cycles as clocks rise.

Photos, illustrations, graphics here.

Example Machine Cache Designs

Sources: AMD Zen 4/Zen 5 Software Optimization Guides & Hot Chips 2024; Intel Lion Cove disclosures (Computex 2024) and Chips and Cheese measurements; Arm Neoverse V2 TRM; NVIDIA Grace/Vera documentation. Latencies are load-to-use, in core cycles.

Photos, illustrations, graphics here.

Questions of memory hiearchies

• Q1: Where can a block be placed in the upper level? (Block placement)

​

• Q2: How is a block found if it is in the upper level?� (Block identification)

​

• Q3: Which block should be replaced on a miss? �(Block replacement)

​

• Q4: What happens on a write? �(Write strategy)

Photos, illustrations, graphics here.

Q3: Which block should be replaced on a miss?

• Easy for direct mapped – only one choice
• Set associative or fully associative
• Random
• LRU (Least Recently Used)

​

• For a 2-way set associative cache, random replacement has a miss rate about 1.1 times higher than LRU.
• LRU is costly to implement for high levels of associativity (> 4-way) since tracking the usage information is expensive

​

Photos, illustrations, graphics here.

Q1/Q2: Where can block be placed/found?

Photos, illustrations, graphics here.

Q4: What happens on a write?

• Write-through – The information is written to both the block in the cache and to the block in the next lower level of the memory hierarchy
• Write-through is always combined with a write buffer so write waits to lower level memory can be eliminated (as long as the write buffer doesn’t fill)

​

• Write-back – The information is written only to the block in the cache. The modified cache block is written to main memory only when it is replaced.
• Need a dirty bit to keep track of whether the block is clean or dirty

​

• Pros and cons of each?
• Write-through: read misses don’t result in writes (so are simpler and cheaper)
• Write-back: repeated writes require only one write to lower level

Photos, illustrations, graphics here.

More detailed questions…

• Block placement policy?
• Where does a block go when it is fetched?
• Block identification policy?
• How do we find a block in the cache?
• Block replacement policy?
• When fetching a block into a full cache, how do we decide what other block gets kicked out?
• Write strategy?
• Does any of this differ for reads vs. writes?

Photos, illustrations, graphics here.

Block Placement + ID

• Placement
• Invariant: block always goes in exactly one set
• Fully-Associative: Cache is one set, block goes anywhere
• Direct-Mapped: Block goes in exactly one frame
• Set-Associative: Block goes in one of a few frames
• Identification
• Find Set
• Search ways in parallel (compare tags, check valid bits)

​

​

Photos, illustrations, graphics here.

Block replacement

• Cache miss requires a replacement
• No decision needed in direct mapped cache
• More than one place for memory blocks in set-associative
• Replacement Strategies
• Optimal
• Replace Block used furthest ahead in time (oracle)
• Least Recently Used (LRU)
• Optimized for temporal locality
• (Pseudo) Random
• Nearly as good as LRU, simpler

Photos, illustrations, graphics here.

Write Policies

• Writes are only about 21% of data cache traffic
• Optimize cache for reads, do writes “on the side”
• Reads can do tag check/data read in parallel
• Writes must be sure we are updating the correct data and the correct amount of data (1-8 byte writes)
• Serial process => slow
• What to do on a write hit?
• What to do on a write miss?

​

Photos, illustrations, graphics here.

Write hit policies

• Q1: When to propagate new values to memory?
• Write back – Information is only written to the cache.
• Next lower level only updated when it is evicted (dirty bits say when data has been modified)
• Can write at speed of cache
• Caches become temporarily inconsistent with lower-levels of hierarchy.
• Uses less memory bandwidth/power (multiple consecutive writes may require only 1 final write)
• Multiple writes within a block can be merged into one write
• Evictions are longer latency now (must write back)

​

Photos, illustrations, graphics here.

Write Hit Policies

• Q1: When to propagate new values to memory?
• Write through – Information is written to cache and to the lower-level memory
• Main memory is always “consistent/coherent”
• Easier to implement – no dirty bits
• Reads never result in writes to lower levels (cheaper)
• Higher bandwidth needed
• Write buffers used to avoid write stalls

​

​

Photos, illustrations, graphics here.

Write buffers

• Small chunks of memory to buffer outgoing writes
• Processor can continue when data written to buffer
• Allows overlap of processor execution with memory update

​

• Write buffers are essential for write-through caches

​

Photos, illustrations, graphics here.

Write buffers

• Writes can now be pipelined (rather than serial)
• Check tag + Write store data into Write Buffer
• Write data from Write buffer to L2 cache (tags ok)

​

Address| Data

Address| Data

Tag

Store Op

Data

Data Cache

Write Buffer

Entry

• Loads must check write buffer for pending stores to same address
• Loads Check:
• Write Buffer
• Cache
• Subsequent Levels of Memory

Photos, illustrations, graphics here.

Write buffer policies: performance/complexity tradeoffs

• Allow merging of multiple stores? (“coalescing”)
• “Flush Policy” – How to do flushing of entries?
• “Load Servicing Policy” – What happens when a load occurs to data currently in write buffer?

​

Stores

L2 Cache

Loads

Photos, illustrations, graphics here.

Write misses?

• Write Allocate
• Block is allocated on a write miss
• Standard write hit actions follow the block allocation
• Write misses = Read Misses
• Goes well with write-back

​

• No-write Allocate
• Write misses do not allocate a block
• Only update lower-level memory
• Blocks only allocate on Read misses!
• Goes well with write-through

Photos, illustrations, graphics here.

Summary of Write Policies

Photos, illustrations, graphics here.

Cache Performance

CPU time = (CPU execution cycles + Memory Stall Cycles)*Clock Cycle Time

​

AMAT = Hit Time + Miss Rate * Miss Penalty

​

• Reducing these three parameters can have a big impact on performance
• Out-of-order processors can hide some of the miss penalty

​

Photos, illustrations, graphics here.

Reducing Miss Penalty

• Have already seen two examples of techniques to reduce miss penalty
• Write buffers give priority to read misses over writes
• Merging write buffers
• Multiword writes are faster than many single word writes

​

• Now we consider several more
• Victim Caches
• Critical Word First/Early Restart
• Multilevel caches

​

Photos, illustrations, graphics here.

Logistics

• Lab 1 is due on Monday!

Photos, illustrations, graphics here.