Search Knowledge

© 2026 LIBREUNI PROJECT

Computer Architecture/Memory, storage, and I/O
Page 9 of 20

Cache Hierarchies

Locality, mapping, replacement, and write policies.

Lesson briefMemory, storage, and I/O · 10 h · 3 outcomes

Required knowledge

  • Programming in a systems language
  • Binary arithmetic and basic digital logic

Learning outcomes

  • Derive cache address fields, local/global miss-rate AMAT, and conflict/capacity/compulsory miss classifications.
  • Trace replacement, write-back, nonblocking, coherence, and locality behavior for an explicit address stream.
  • Select a hierarchy policy from workload evidence while stating coherence, ordering, security, and bandwidth limits.

Assessment target

Given cache geometry, rates, and an address trace, calculate AMAT, classify each miss, and defend a policy change with a countertrace.

Scope boundary

  • RTL implementation and electrical device physics are reduced to the abstractions needed to reason about a modern processor.

The processor can execute many arithmetic operations in the time required for one main-memory access. A cache hierarchy reduces the effective cost by keeping recently or nearby used data in smaller, faster storage close to the core. The hierarchy is not a magical “fast memory”; it is a carefully specified prediction mechanism. A cache contains copies of lower-level data, decides whether a request hits, chooses where a block may reside, and defines how writes propagate. Its performance depends on an access trace, its correctness depends on coherence and permission rules, and its cost includes area, energy, refill bandwidth, and miss handling.

Locality and the two-level model

Temporal locality means that an address recently used is likely to be used again. Spatial locality means that addresses near a recently used address are likely to be used. A cache exploits both by transferring a block or line containing several adjacent bytes, not just the requested word. The block size is a design compromise: larger lines capture more spatial locality but consume bandwidth and may evict useful data; smaller lines reduce overfetch but increase tag and refill overhead.

In a two-level model, let hit time be tht_h miss rate be mm and miss penalty be the additional time to obtain the block from the next level. The average memory access time is

AMAT=th+m⋅tpenalty.AMAT=t_h+m\cdot t_{penalty}.

If the lower level’s access time includes the first level’s lookup, some texts instead write AMAT=th+(1−h)tlowerAMAT=t_h+(1-h)t_{lower} the variables must be defined before numbers are substituted. For a hierarchy with L1 and L2, one useful form is

AMAT=tL1+mL1(tL2+mL2tmem).AMAT=t_{L1}+m_{L1}\bigl(t_{L2}+m_{L2}t_{mem}\bigr).

The L2 miss rate is usually conditional on an L2 access, while a global miss rate is relative to all processor accesses. Confusing local and global rates is a frequent source of apparently impressive but incorrect performance calculations.

Worked AMAT example. Suppose L1 hit time is 1 cycle and its miss rate is 5%. L2 takes 8 cycles on a hit and has a local miss rate of 20%; DRAM costs 80 cycles after an L2 miss. Then AMAT=1+0.05(8+0.2⋅80)=2.2AMAT=1+0.05(8+0.2\cdot80)=2.2 cycles. The L2 lookup contributes 0.05⋅8=0.40.05\cdot8=0.4 cycles per processor access through the L1 miss path, while DRAM contributes 0.05⋅0.2⋅80=0.80.05\cdot0.2\cdot80=0.8 cycles. Improving L1 hit time from 1 to 0.8 cycles saves 0.2; halving the DRAM penalty saves 0.05⋅0.2⋅40=0.40.05\cdot0.2\cdot40=0.4 cycles under this workload. The bottleneck is identified by the product of frequency and cost, not by the largest raw latency alone.

Average Memory Access Time (AMAT) vs. L1 miss rate $m_1$, contrasting a direct main-memory penalty ($t_{\text{miss}}=40$) with an intermediate L2 cache ($t_{\text{miss}}=15$). Average Memory Access Time AMAT curves as a function of level-one cache miss rate, comparing single-level cache with two-level hierarchy. m1=6% 3.4 cyc 1.9 cyc
Figure 3.1.1: Average Memory Access Time (AMAT) vs. L1 miss rate m1m_1, contrasting a direct main-memory penalty (tmiss=40t_{\text{miss}}=40) with an intermediate L2 cache (tmiss=15t_{\text{miss}}=15).

Memory Locality Matrix

0 / 4 answered

Evaluate each statement regarding spatial and temporal locality principles in hardware cache hierarchies:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Traversing randomly scattered linked-list node pointers through memory exploits spatial line neighborhoods.
2
Referencing an isolated single byte exactly once across an entire program execution yields strong temporal locality.
3
Sequential iteration across elements of a contiguous array amortizes block refill costs through spatial locality.
4
Repeatedly accessing loop counters or inner accumulator variables within a hot loop exploits temporal locality.

Address decomposition

For a cache with capacity CC bytes, line size BB bytes, and AA ways, the number of sets is S=C/(B⋅A)S=C/(B\cdot A) Assuming powers of two, a byte address divides into block offset bits, set-index bits, and tag bits. The offset has log⁡2B\log_2B bits; the index has log⁡2S\log_2S bits; the remaining address bits form the tag.

Worked decomposition. A 32-bit byte address accesses a 16 KiB, 4-way cache with 64-byte lines. There are 16384/(64⋅4)=6416384/(64\cdot4)=64 sets. The line offset is log⁡2(64)=6\log_2(64)=6 bits (bits [5:0]), the set index is log⁡2(64)=6\log_2(64)=6 bits (bits [11:6]), and the tag is 32−6−6=2032-6-6=20 bits (bits [31:12]). For byte address 0x12345678, the low 12 bits are 0x678 = 0b0110_0111_1000, so the block offset is 0b111000 = 0x38 5656 the set index is 0b011001 = 0x19 2525 and the 20-bit tag is 0x12345. Two addresses with set index 2525 but different 20-bit tags compete for the four ways of set 2525 they may conflict even if the other 63 sets are empty.

Alignment is part of this arithmetic. A word spanning two lines can require two tag lookups and two transfers, or the ISA may forbid the access. If a structure is aligned to a line boundary, its fields may still cross lines if its size and offsets are not chosen carefully. Performance analysis should use actual byte addresses and strides rather than assume every element maps independently.

Instruction count hides locality

Two loops execute the same number of loads. One scans adjacent array elements; the other follows randomly scattered pointers through the same amount of data.

Which architectural metrics and evidence explain the performance divergence between these two loops?

Mapping organizations

A direct-mapped cache has one possible line per set. It is inexpensive and fast to index, but two frequently alternating blocks mapping to one set cause conflict misses. A fully associative cache allows a block anywhere and minimizes conflict misses, but comparing its tag against every line is expensive. A set-associative cache is a compromise: each block maps to one set but can occupy one of AA ways.

Associativity does not eliminate capacity or compulsory misses. A compulsory miss occurs on the first access to a block. A capacity miss occurs because the working set exceeds the cache’s usable capacity. A conflict miss occurs because the mapping forces competing blocks into too few locations. The same trace can exhibit all three at different cache sizes and associativities.

Worked conflict trace. A direct-mapped cache with four lines receives accesses to blocks 0, 4, 0, 4. Both block numbers map to set block mod 4 = 0. Every access misses, even though only two blocks are needed and the cache holds four. A 2-way cache with four total lines has two sets; blocks 0 and 4 map to set 0 but can occupy its two ways, so after warm-up the alternating trace hits. If a third block 8 is added, the two-way set again thrashes. Associativity is a targeted response to mapping conflicts, not a universal capacity increase.

The explorer holds the number of sets at two and varies ways per set, so total capacity also varies. Its two-block trace still diagnoses a mapping conflict: a one-way two-set cache has capacity for both blocks, but both compete for set 0. Predict the first hit, then add a third competitor and inspect the most-recently-used to least-recently-used order after each access.

Interactive exploration

Make associativity explain the trace

Two sets receive a deliberately adversarial block stream. Change associativity and the number of competing blocks to separate conflict misses from capacity claims.

0/6 hits · 100% miss rate
Associativity = 1-way
BlockSetResultResident: MRU → LRU
B00
miss
B0
B40
missevict B0
B4
B00
missevict B4
B0
B40
missevict B0
B4
B00
missevict B4
B0
B40
missevict B0
B4

Model scope: two sets, block-sized accesses, LRU order within each set, and no prefetching or overlap. Real caches add more sets, byte offsets, refill queues, and coherence state; the mapping invariant is unchanged.

Make associativity explain the trace
BlockSetResultResident: MRU → LRU
B00
miss
B0
B40
miss
B4 → B0
B00
hit
B0 → B4
B40
hit
B4 → B0
B00
hit
B0 → B4
B40
hit
B4 → B0

Static state: blocks 0 and 4 alternate in a 2-way, two-set cache. Both map to set 0, but both fit, so only compulsory misses remain.

Replacement policy

When a set is full, the cache needs a replacement policy. Least recently used (LRU) evicts the line whose most recent access is farthest in the past; it exploits temporal locality but becomes expensive to track as associativity grows. Pseudo-LRU approximates LRU with fewer bits. Random replacement is simple and can avoid adversarial patterns that defeat a deterministic policy. The policy affects performance, not the abstract contents that must eventually be returned, provided coherence and validity are correct.

Replacement metadata is itself state and must be reset or initialized consistently. A valid bit distinguishes an unused way from a line whose tag happens to match a reset value. A dirty bit records whether a write-back line differs from the lower-level copy. A coherence state may add shared, exclusive, modified, or invalid information in a multiprocessor.

Write policies

A write-through cache sends every write to the lower level, simplifying consistency but increasing traffic. A write-back cache updates only the cache line and writes it back on eviction if dirty, reducing bandwidth but requiring dirty tracking and careful eviction ordering. A write-allocate cache brings a missing line into the cache before applying a write; no-write-allocate sends a write miss directly downward. Common pairings are write-back/write-allocate and write-through/no-write-allocate, but the choice is workload- and coherence-dependent.

Write buffers decouple a processor from lower-level write latency. They introduce ordering obligations: a later load cannot observe stale data if an older buffered store targets the same address, and a memory barrier must drain or order the buffer as the ISA requires. Memory-mapped I/O often uses uncached or specially ordered regions because caching a device register can turn one device operation into repeated reads of an old copy.

Worked write example. A write-back cache has a dirty line for address A. A miss to another block mapping to the same set selects that way for replacement. The controller must first write the dirty line to the lower level, wait for acceptance or record a safe buffered transaction, install the new tag/data, and then satisfy the new request. If it overwrites the line first, the old value is lost. A write-through cache avoids this particular dirty eviction but can still require ordering if multiple writes are outstanding.

Miss handling and nonblocking caches

A blocking cache stalls the requesting pipeline until a miss is complete. A nonblocking cache can continue serving hits and track outstanding misses with miss-status holding registers (MSHRs). It must know which requests depend on which refill, merge multiple accesses to one missing line, and preserve ordering for stores and fences. Multiple outstanding misses improve memory-level parallelism but increase control-state complexity.

MSHR FieldData Width / FormatHardware PurposeTransition on Memory Refill
Valid1 bitIndicates active in-flight cache line miss requestCleared to 0 when line arrives and targets are served
Block AddressTag + Set index bitsMatches secondary misses to coalesce requests to same blockCompared against incoming pipeline loads/stores
Way Allocationlog⁡2(Ways)\log_2(\text{Ways}) bitsPre-selected replacement way identified by cache controllerReceives refilled cache line data from interconnect
Merged Load QueueEntry bitmask / register listIdentifies destination registers awaiting missing wordsDelivers words directly to execution units / register file
Dirty / Write MaskLine size bitmaskTracks byte offsets modified by coalesced stores before refillMerged with incoming memory line before writing back

The refill path may receive critical words first, allowing the processor to resume before the entire line arrives. This is useful when the requested word is available early but creates hazards if a later word is consumed before refill completion. The cache’s valid/ready protocol must make partial data visible only under a defined rule.

Arrays, loops, and locality

Row-major traversal of a matrix stored with rows contiguous accesses neighboring elements and uses each fetched line efficiently. Column-major traversal jumps by the row stride; if the stride exceeds line size and the working set exceeds the cache, each access may fetch a line whose other words are not used. Loop interchange can transform the trace without changing the mathematical result.

Worked stride calculation. With 64-byte lines and 4-byte integers, a sequential loop uses 16 integers per line and approaches one miss per 16 accesses after warm-up. A stride-16 loop touches one integer per line; it gets little spatial benefit and can cause one miss per access if the active lines do not fit. A stride of 1024 bytes maps to the same set periodically in a power-of-two cache, potentially causing conflict thrashing. Cache behavior is a property of line size, capacity, associativity, and address mapping together.

Data layout also controls locality. An array of structures is convenient when every field of one record is used together. A structure of arrays is better when a loop scans one field across many records, because each line contains more useful values and vector loads can be contiguous. Padding can prevent false sharing between cores, but increases footprint and may alter index mapping.

Coherence and consistency

In a shared-memory multiprocessor, each core may cache a copy of a line. Cache coherence answers whether writes to one location eventually become visible consistently and whether a reader can obtain the latest value under the protocol’s rules. A protocol such as MESI tracks whether a line is modified, exclusive, shared, or invalid and sends invalidations or updates over an interconnect.

Current MESI StateLocal Core ReadLocal Core WriteBus Snoop Read (Peer Read)Bus Snoop Invalidate (Peer Write)
Invalid (I)Miss: issue BusRd; →S\to \mathbf{S} or E\mathbf{E}Miss: issue BusRdX; →M\to \mathbf{M}No-op; ignore transactionNo-op; ignore transaction
Shared (S)Hit; no bus action; remain S\mathbf{S}Hit: issue BusUpgrade; →M\to \mathbf{M}No-op; peer receives shared copyInvalidate local tag; →I\to \mathbf{I}
Exclusive (E)Hit; no bus action; remain E\mathbf{E}Hit (silent upgrade); →M\to \mathbf{M}Respond Shared; transition to S\mathbf{S}Invalidate local tag; →I\to \mathbf{I}
Modified (M)Hit; no bus action; remain M\mathbf{M}Hit; write to line; remain M\mathbf{M}Intercept; flush data to bus; →S\to \mathbf{S}Intercept; write back dirty data; →I\to \mathbf{I}

Coherence is per cache line, not per language object or field. Two independent variables in one line can cause false sharing: cores repeatedly invalidate each other’s copies even though they never access the same variable. Coherence also does not define all cross-address ordering; the ISA memory model and synchronization operations determine whether a flag becoming visible implies that preceding data is visible.

Atomic read-modify-write and fences interact with caches. An atomic operation may acquire exclusive ownership of a line, perform the update without an intervening conflicting write, and impose ordering. A fence may prevent a compiler or processor from reordering specified memory operations, but it does not magically flush every cache on every architecture. The precise semantics belong to the ISA.

Security and correctness boundaries

Caches can create timing side channels because hits and misses have different latency. Isolation mechanisms may partition cache ways, flush state on context switch, use constant-access patterns, or accept a residual risk. A correct cache from the functional viewpoint can still leak access patterns. Security analysis must distinguish architectural data returned by loads from microarchitectural observations such as timing and replacement state.

Attack / Microarchitectural HazardConcrete MechanismTarget ResourceHardware / OS Countermeasure
Flush+ReloadAttacker flushes shared line via clflush, times victim accessInclusive shared LLC linesWay partitioning (CAT), unshared address mappings
Prime+ProbeAttacker fills target set, detects victim eviction via reload latencyCache set conflict replacementRandom cache indexing, partitioned set allocation
VIPT Virtual SynonymsTwo virtual aliases map to different sets b+s>pb+s > pL1 virtually-indexed setsHardware alias detection snoops, OS page coloring
Transient Speculative FillSquashed speculative loads fetch secrets into data cacheL1/L2 data cache tagsSpeculative load hardening, barrier fences (lfence)

The cache must also respect virtual memory permissions. Every cached access must still pass TLB permission checks for the current address space, and in virtually indexed caches where index bits extend above the page offset, synonym handling must prevent two virtual mappings of one physical frame from holding inconsistent dirty lines in different sets. The order of translation and cache lookup—physically indexed, virtually indexed, synonym handling—belongs to the implementation and must be proven equivalent to the architectural memory model.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 3.1.1: Address Bitfield Decomposition

Constructionapplication

Derive tag, index, and offset bits for a 64-bit address, 32 KiB, 8-way cache with 64-byte lines.

HintExpand

Compute offset bits from line size, index bits from set count, and assign remaining bits to the tag.

Worked solutionExpand

A 64-byte line needs 6 offset bits. There are 32768/(64⋅8)=6432768/(64\cdot8)=64 sets, requiring 6 index bits. The remaining 64−6−6=5264-6-6=52 bits are tag bits.

Exercise 3.1.2: Multilevel AMAT Calculation

Verificationapplication

A hierarchy has t1=1t_1=1 cycle, t2=5t_2=5 cycles, t3=30t_3=30 cycles, and main-memory penalty tm=100t_m=100 cycles. Its local miss rates are m1=0.08m_1=0.08 m2=0.25m_2=0.25 and m3=0.40m_3=0.40 Compute AMAT under the serial additive model, then report the global L2 and L3 miss rates and explain the difference between local and global L2 miss rate.

HintExpand

Apply the serial memory hierarchy equation where each level's miss penalty includes lower-level access times.

Worked solutionExpand

The serial model gives 1+0.08(5+0.25(30+0.40(100)))=1+0.08(5+17.5)=2.81+0.08(5+0.25(30+0.40(100)))=1+0.08(5+17.5)=2.8 cycles. The global L2 miss rate is 0.08⋅0.25=0.020.08\cdot0.25=0.02 (2% of processor references), and the global L3 miss rate is 0.08⋅0.25⋅0.40=0.0080.08\cdot0.25\cdot0.40=0.008 (0.8%). The local L2 rate, 25%, is conditional on an L1 miss; treating it as 25% of all accesses would overstate lower-level traffic and cost.

Exercise 3.1.3: Direct-Mapped Conflict Miss Trace

Constructiontransfer

Construct a trace that produces conflict misses in a direct-mapped cache but hits in a 2-way cache. Then add a third competing block.

HintExpand

Identify memory addresses that map to the identical cache set index and trigger ping-pong evictions.

Worked solutionExpand

Blocks 0 and 4 alternate in a four-line direct-mapped cache and both map to set 0, so every access misses after each replacement. A 2-way cache can retain both; adding block 8 makes three blocks contend for two ways and can thrash under LRU.

Exercise 3.1.4: Write Allocation Policies Comparison

Descriptiontransfer

Compare write-through/no-write-allocate and write-back/write-allocate for a streaming store and a repeatedly updated small object.

HintExpand

Analyze bus traffic differences when writing streaming sequential data versus repeatedly updating hot variables.

Worked solutionExpand

A streaming store may waste a read-for-ownership under write-allocate and benefit from write-through or no-write-allocate; a hot object benefits from write-back because repeated writes stay local. The answer changes with reuse, bandwidth, durability, and coherence assumptions.

Exercise 3.1.5: Dirty Line Eviction Invariants

Formalisationtransfer

Explain why a dirty line must be written back before replacement and what state a write buffer must preserve.

HintExpand

Consider data loss if memory is overwritten before a modified cache block is copied back.

Worked solutionExpand

The dirty data is the only current copy. Replacement must preserve its address tag and bytes until lower-level acceptance; a write buffer must also preserve order relative to later loads, stores, fences, and device accesses.

Exercise 3.1.6: Loop Interchange for Spatial Locality

Generalisationsynthesis

Design a loop transformation that improves locality for a matrix operation. State the cache assumptions under which it helps.

HintExpand

Reorder nested loops so that memory accesses step contiguously through row-major arrays.

Worked solutionExpand

Interchange loops so the innermost dimension follows contiguous storage. For row-major data, iterate columns inside rows. The benefit assumes lines are larger than one element and the working set or tile fits enough cache to exploit reuse.

Exercise 3.1.7: Coherence vs Consistency vs False Sharing

Descriptionsynthesis

Distinguish coherence, consistency, and false sharing using one two-core example for each.

HintExpand

Contrast cache line ownership conflicts with memory ordering rules and independent variable packing.

Worked solutionExpand

Coherence: two cores write the same memory address X and must observe a single protocol-defined serialization order for X. Consistency: a producer writes data = 42 and executes a release store flag = 1, while a consumer executes an acquire load of flag == 1 before reading data, guaranteeing cross-address visibility. False sharing: two cores write distinct variables (counter[0] and counter[1]) that reside in the same 64-byte cache line, causing MESI invalidation ping-pong without any logical data sharing.

References & Further Reading