Cache Design

Two fundamental memory technologies used in modern systems:

Property	SRAM	DRAM
Cell structure	6 transistors (6T cell)	1 transistor + 1 capacitor (1T1C)
Speed	Fast (~1-2 ns)	Slower (~50-100 ns)
Density	Lower (6T per bit)	Higher (1T1C per bit)
Refresh needed?	No (static latch)	Yes (capacitor leaks charge)
Read type	Non-destructive	Destructive (must write-back)
Cost	Expensive	Cheap per bit
Use	Caches (L1, L2, L3)	Main memory

DRAM destructive reads: Reading a DRAM cell discharges the capacitor. After every read, the sense amplifier must write back the data to restore the charge. This adds latency.

The memory hierarchy exploits the trade-off between speed, size, and cost:

• Registers: sub-nanosecond, bytes, in the CPU core
• L1 Cache: ~1 ns, ~32 KB, per-core
• L2 Cache: ~3-10 ns, 256 KB - 1 MB, per-core or shared
• L3 Cache: ~10-30 ns, several MB, shared across cores
• Main Memory (DRAM): ~50-100 ns, GBs
• Disk/SSD: ~10 ms (HDD) / ~100 us (SSD), TBs

Why it works — Locality:

• Temporal locality: Recently accessed data is likely to be accessed again soon (e.g., loop variables, hot data structures)
• Spatial locality: Data near recently accessed data is likely to be accessed soon (e.g., array traversals, sequential instruction fetch)

Caches exploit temporal locality by keeping recently-used data close to the processor. They exploit spatial locality by fetching entire cache blocks (typically 64 bytes) at a time.

A cache consists of:

• Data store: holds the actual cache blocks (lines)
• Tag store: holds metadata for each block (tag bits, valid bit, dirty bit, replacement info)

Address decomposition (for a direct-mapped cache):

| Tag (upper bits) | Index (middle bits) | Block Offset (lower bits) |

• Block Offset: log₂(block size) bits — selects byte within the block
• Index: log₂(number of sets) bits — selects which set to look in
• Tag: remaining upper bits — identifies which block from memory is stored

Terminology:

• Hit: requested data found in cache → fast access
• Miss: data not in cache → must fetch from next level
• Hit rate: fraction of accesses that hit in cache
• Miss rate: 1 - hit rate

In a direct-mapped cache, each memory block maps to exactly one cache set (1-way associative).

• Number of sets = Cache size / Block size
• Set index = (Block address) mod (Number of sets)
• On access: check the tag at the indexed set. If tag matches and valid bit is set → hit
• On miss: the existing block at that index is evicted (no choice — only one place)

Advantages: Simple, fast lookup (single comparator), low power.

Disadvantages: High conflict miss rate — two blocks that map to the same index will keep evicting each other (ping-pong / thrashing).

Example: If blocks A and B both map to set 5, accessing A, B, A, B causes 100% miss rate even if the cache has room elsewhere.

An N-way set-associative cache has N blocks (ways) per set. A memory block can go in any of the N ways within its mapped set.

• Number of sets = Cache size / (Block size x Associativity)
• On access: index selects the set, then N parallel comparators check all tags
• On miss: one of the N blocks in the set must be evicted (replacement policy decides which)

Spectrum:

• 1-way = direct-mapped
• N-way = set-associative (typical: 2, 4, 8, 16 ways)
• If #sets = 1, it's fully associative (any block can go anywhere)

Trade-off: More associativity → fewer conflict misses, but more comparators, higher latency, more power.

Average Memory Access Time (AMAT) is the key metric for cache performance:

AMAT = Hit_Rate × Hit_Latency + Miss_Rate × Miss_Latency

Or equivalently:

AMAT = Hit_Latency + Miss_Rate × Miss_Penalty

where Miss_Penalty = Miss_Latency - Hit_Latency (time to service the miss).

For multi-level caches:

AMAT = L1_hit_time + L1_miss_rate × (L2_hit_time + L2_miss_rate × L2_miss_penalty)

Local vs. Global miss rate:

• Local miss rate: misses at this level / accesses to this level
• Global miss rate: misses at this level / total CPU memory accesses
• Global L2 miss rate = L1 miss rate × L2 local miss rate

All cache misses can be classified into three categories:

1. Compulsory (Cold) Misses: First access to a block that has never been in the cache. Unavoidable unless you prefetch. These occur even in an infinite cache.
2. Capacity Misses: The working set is larger than the cache. Even a fully-associative cache of the same size would miss. Occurs because the cache simply cannot hold all needed data.
3. Conflict Misses: Multiple blocks map to the same set, causing evictions even though the cache has unused space in other sets. Only occur in direct-mapped and set-associative caches (NOT in fully-associative).

How to identify miss type:

• Simulate with infinite cache → remaining misses are compulsory
• Simulate with same-size fully-associative cache → additional misses beyond compulsory are capacity
• Simulate with actual associativity → additional misses beyond capacity are conflict

When a miss occurs in a set-associative cache and the set is full, a replacement policy decides which existing block to evict.

• LRU (Least Recently Used): Evict the block that hasn't been accessed for the longest time. Optimal for many workloads but expensive to implement (need to track access order of all ways).
• Approximate LRU — Not-MRU: Don't track full order; just track which block was Most Recently Used and never evict it. Randomly pick from the rest. Much cheaper hardware.
• Hierarchical LRU: Divide ways into groups, do LRU within groups, approximate LRU across groups.
• Random: Pick a random victim. Surprisingly competitive with LRU for high associativity. Very simple hardware.

Set thrashing: When the working set in a particular set exceeds the associativity, even LRU performs poorly — it keeps evicting blocks that will be needed soon. This is the Belady's anomaly-like problem for caches. Working set > associativity → every access can miss.

Two orthogonal decisions for handling writes:

Write Hit Policy:

• Write-back: Write only to cache. Mark block as dirty. Write to memory only on eviction. Reduces memory traffic but requires dirty bits and write-back on eviction.
• Write-through: Write to both cache and memory simultaneously. Simpler, memory always up-to-date, but more memory traffic. Often uses a write buffer to avoid stalling.

Write Miss Policy:

• Write-allocate: On write miss, fetch the block into cache, then write to it. Makes sense with write-back (exploit temporal locality on future writes).
• No-write-allocate (write-around): On write miss, write directly to next level, don't bring block into cache. Makes sense with write-through.

Common pairings:

• Write-back + Write-allocate (most common in modern caches)
• Write-through + No-write-allocate

Using the AMAT formula, we can improve performance by reducing miss rate, reducing miss latency, or reducing hit time.

Reducing Miss Rate:

• Increase associativity → reduces conflict misses
• Increase cache size → reduces capacity misses
• Victim cache: Small fully-associative cache between L1 and L2 that stores recently evicted blocks. Catches conflict misses cheaply.
• Software optimization: loop interchange, loop fusion, tiling/blocking

Reducing Miss Latency:

• Multi-level caches: L1 fast but small, L2 larger with moderate latency → catches many L1 misses without going to DRAM
• Critical word first: Request the needed word first from memory, send it to processor immediately while filling rest of block
• MSHRs (Miss Status Holding Registers): Track outstanding cache misses. Enable non-blocking caches — the cache can continue servicing hits (and even other misses) while a miss is being resolved. Without MSHRs, a miss stalls all subsequent accesses.

Software optimizations:

• Loop interchange: Change loop nesting order to access arrays in row-major order (better spatial locality)
• Loop fusion: Merge loops over the same array to improve temporal locality