Memory hierarchy
Keep the common case close to the core.
Registers, SRAM caches, DRAM, and storage trade capacity for latency and cost. Caches work because access patterns exhibit temporal and spatial locality.
Recently used data is likely to be used again. Loops and accumulators are common examples.
Nearby addresses are likely to be used. A cache line fetches a neighborhood, often 64 bytes.
Identifies which memory block currently occupies the selected way.
Selects a set, reducing the number of tag comparisons.
Selects the byte or word within the cache line.
Cache address explorer
Split a physical address and size the tag array.
Address 0x1234ABCD selects set 687 of 2,048, byte offset 13, and compares tag 0x91A against 8 ways.
Accuracy note: PIPT tags use the physical address width. The source gives a 32-bit virtual address but not the physical width. Its requested 17-bit tag and 288 Kibit tag array imply a 34-bit physical address. If the physical address is 32 bits, the correct result is a 15-bit tag and 256 Kibit, or 32 KiB, including one valid bit per line.
Placement
Associativity chooses how many homes a block may use.
Direct mapped
One possible line per index. Fast and compact, but vulnerable to conflicts.
Set associative
N candidate ways in one set. Parallel tag checks trade power for fewer conflicts.
Fully associative
Best placement freedom, but every tag may need comparison. Practical for small structures.
Compulsory miss
Cause: The block has never been fetched.
Response: Prefetch useful streams or use a larger line when spatial locality justifies it.
Larger lines can waste bandwidth and pollute the cache.Conflict miss
Cause: Active blocks compete for the same set even while other sets have space.
Response: Increase associativity or improve placement and indexing.
More ways add tag comparisons, power, mux delay, and replacement state.Capacity miss
Cause: The working set exceeds the cache's usable capacity.
Response: Increase cache capacity or reduce the software working set.
A larger cache costs area and can lengthen hit latency.Coherence miss
Cause: Another agent's write invalidates the local copy.
Response: Reduce writable sharing and false sharing; use an appropriate coherence protocol.
This miss reflects inter-core communication, not only local placement.| Parameter | Choice | Performance benefit | Cost and complexity |
|---|---|---|---|
| Capacity | Small ↔ large | Larger capacity reduces capacity misses and holds a bigger working set. | More area and leakage; longer wires can increase hit time. |
| Associativity | Direct ↔ N-way ↔ fully associative | More ways reduce conflict misses. | More comparators, replacement metadata, mux delay, power, and verification. |
| Line size | 16 B ↔ 64 B ↔ 128 B | Larger lines exploit spatial locality, amortize refill overhead, and need fewer tag entries. | Longer refill latency, more bandwidth, pollution, and false sharing. |
| Write policy | Write-through ↔ write-back | Write-through simplifies lower-level visibility; write-back bundles repeated writes. | Write-through needs bandwidth and usually a write buffer. Write-back needs dirty state and reliable eviction. |
VIPT L1 cache
Index while translation runs.
A virtually indexed, physically tagged cache uses page-offset bits to select a set in parallel with the TLB lookup, then compares translated physical tags. This removes serial TLB-plus-cache latency.
The synonym problem
Two virtual addresses can map to one physical page. If their index bits differ, duplicate copies could occupy different sets. Keep index plus offset within the page offset, commonly expressed as cache capacity divided by associativity no larger than page size. Page coloring and explicit alias handling cover designs that exceed this constraint.
Non-blocking cache
Keep independent work moving.
MSHRs record each outstanding line, request type, destination, and waiting consumers. They enable hit-under-miss, merge requests to the same line, and allow multiple independent misses.
Where it matters
A long DRAM miss need not block an unrelated L1 hit. Several concurrent misses can overlap until MSHRs, fill buffers, memory-level parallelism, or bandwidth become the new limit. When all MSHRs are occupied, new misses must stall.
Parallel lookup
A VIPT cache spends the page offset twice.
One branch translates the VPN. The other uses untranslated page-offset bits to start the SRAM read. They meet at the physical-tag comparison, so no data becomes valid before translation and permission checks finish.
Design intuition
Fast structures work because a hidden invariant stays true.
Use virtual page-offset bits to index the set while the TLB produces the physical tag.
Every index bit used before translation must be unchanged by translation.
Synonyms create duplicate physical lines in different sets, producing stale copies.
Track an outstanding line and let independent hits or misses continue.
Every waiter links to one fill, and same-line requests merge without a duplicate refill.
A lost waiter never wakes; a premature free misroutes data; full MSHRs apply backpressure.
AMAT calculator
Price every miss at the level where it occurs.
AMAT = tL1 + mL1 × (tL2 + mL2 × tDRAM)2 + 0.1 × (10 + 0.2 × 60)
4.2 nsAMAT is 4.2 ns. L1 contributes 2 ns, L2 contributes 1 ns, and DRAM contributes 1.2 ns. L1 lookup is the largest contribution.
What happens on a cache read miss?
Allocate miss-tracking state, select a victim, write back a dirty victim if needed, request the line from the next level, install data and tag, update replacement state, then wake or replay the waiting load.
How does associativity reduce conflict misses?
Blocks with the same index can coexist in different ways. It does not remove compulsory or capacity misses, and the extra ways increase lookup cost.