Elements of Cache Design

Computer Organization & Embedded System — Computer Arithmetic and Memory System, NEC licence examination syllabus (Nepal Engineering Council).

Elements of Cache Design: the five big decisions

Cache size, mapping, replacement, write policy, number of caches — every cache design question is really about one of these five.

1. Mapping function — the highest-yield sub-topic here

Mapping decides where a block of main memory can go inside cache.

🗺️ Mapping Functions

DirectEach memory block maps to exactly ONE cache line (line = block number mod number of lines). Simple and fast, but causes more conflict misses if two frequently-used blocks map to the same line.

Fully associativeAny block can go into any cache line. No conflict misses, but needs to compare the address against every line simultaneously — expensive hardware.

Set-associative(k-way) Cache is divided into sets, each holding k lines; a block maps to one specific set but can occupy any of the k lines within it. Practically the most common — balances speed and flexibility.

💡 The classic numerical gives you an address and cache size, and asks you to find the tag/line/word breakdown for direct, associative, and 2-way/4-way set-associative — practice ALL THREE on the same numbers so you see the pattern.

🔄 Replacement Algorithms

LRUEvicts the block unused for the longest time. Best performance, but needs extra tracking hardware.

FIFOEvicts the oldest-loaded block, regardless of use.

LFUEvicts the least frequently used block.

RandomJust picks one at random — surprisingly not much worse than LRU in practice, and much cheaper to implement.

✍️ Write Policy

Write-throughEvery write updates both cache AND main memory immediately. Simple, always consistent, but slower writes.

Write-backWrites only update cache; main memory is updated later (when the block is evicted). Faster, but needs a "dirty bit" to track which lines have unwritten changes.

Number of caches — how many, and how they're split

Modern CPUs use multilevel caches: L1 (smallest, fastest, per-core), L2 (bigger, a bit slower), L3 (shared across cores, biggest). Many CPUs also use a split cache — separate I-cache (instructions) and D-cache (data) at L1, letting both be fetched simultaneously; a unified cache stores both together.

💡 Common short-answer: "Why split L1 cache into instruction and data caches?" → allows simultaneous instruction fetch + data access, avoiding a structural hazard in pipelining.

Syllabus points

Cache size
Mapping function: direct, associative, set-associative (solve all three)
Replacement algorithm: LRU, FIFO, LFU, Random
Write policy: write-through vs write-back; write-allocate vs no-allocate
Number of caches: multilevel (L1/L2/L3), unified vs split

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.