Cache Memory

CSS Optional — Paper-II, Section-A · Chapter 7 · 🔥 Highest-yield numerical topic in this chapter

Cache exists to solve one problem: the CPU is roughly 100× faster than main memory. A 3 GHz processor completes a cycle in 0.33 ns, but a DRAM access takes 60–100 ns. Without cache, the CPU would spend most of its life stalled. Cache is a small, fast buffer holding the data the CPU is likely to need next.

---

🗺️ Architecture Diagram — Memory Hierarchy

graph TD
    R["Registers
~1 cycle, smallest"] --> L1["L1 Cache
~1-4 cycles"]
    L1 --> L2["L2 Cache
~10 cycles"]
    L2 --> L3["L3 Cache
~30-40 cycles"]
    L3 --> MM["Main Memory - RAM
~100+ cycles"]
    MM --> SEC["Secondary Storage - SSD/HDD
~10,000+ cycles, largest"]

SECTION 1 — Why Cache Works: The Principle of Locality

Cache would be useless if memory access were random. It works because real programs are predictable in two ways:

• Temporal locality — if you used it recently, you'll use it again soon. A loop counter is read and written every iteration. This justifies keeping recently used data.
• Spatial locality — if you used an address, you'll use its neighbours. Arrays are traversed sequentially; instructions execute in order. This justifies fetching an entire block (typically 64 bytes) rather than a single byte.

Sequential locality (a sub-case of spatial) refers specifically to instructions executing in address order.

---

SECTION 2 — Cache Terminology

The Three C's — classification of misses (frequently examined)

• Compulsory (cold) miss — the first-ever reference to a block. Unavoidable; reduced only by larger block size or prefetching.
• Capacity miss — the working set exceeds total cache size. Reduced only by a larger cache.
• Conflict miss — the block was evicted because too many blocks map to the same line/set, even though the cache had free space elsewhere. Reduced by higher associativity. Direct-mapped caches suffer these worst; fully associative caches have none.

---

SECTION 3 — Cache Mapping Techniques ⭐

The central question: when a memory block is brought in, which cache line may it occupy?

3.1 Address Partitioning — The Master Method

Every mapping problem is solved by splitting the physical address into fields. Learn this procedure and every variant follows.

Step 1: Address bits

$$A = \log_2(\text{Main memory size in bytes})$$

Step 2: Offset bits (which byte inside the block)

$$O = \log_2(\text{Block size in bytes})$$

Step 3: Number of lines

$$L = \frac{\text{Cache size}}{\text{Block size}}$$

Step 4: Middle field

• Direct mapped: $\text{Line bits} = \log_2 L$
• N-way set-associative: $S = L / N$, $\text{Set bits} = \log_2 S$
• Fully associative: no middle field (0 bits)

Step 5: Tag bits

$$T = A - \text{Middle bits} - O$$

Always verify: Tag + Middle + Offset = total address bits.

3.2 Direct Mapping

Each memory block maps to exactly one permitted cache line:

$$\text{Block number} = \left\lfloor \frac{\text{Address}}{\text{Block size}} \right\rfloor \qquad \text{Line} = \text{Block number} \bmod L \qquad \text{Tag} = \left\lfloor \frac{\text{Block number}}{L} \right\rfloor$$

• ✅ Simplest and fastest — only one tag comparison needed.
• ✅ Cheapest hardware; no replacement algorithm required (only one candidate line).
• ❌ Severe conflict misses. Two hot blocks mapping to the same line evict each other repeatedly — called thrashing — even with the rest of the cache empty.

3.3 Fully Associative Mapping

A block may be placed in any cache line.

• ✅ Maximum placement freedom; zero conflict misses.
• ✅ Best possible hit rate for a given cache size.
• ❌ Every tag must be compared in parallel, requiring one comparator per line — prohibitively expensive (CAM hardware). Used only for very small structures such as TLBs.
• ❌ Requires a replacement algorithm.

3.4 Set-Associative Mapping (the practical compromise)

The cache is divided into sets; a block maps to one set but may occupy any line within that set. An N-way set-associative cache has N lines per set.

$$S = \frac{L}{N} \qquad \text{Set} = \text{Block number} \bmod S \qquad \text{Tag} = \left\lfloor \frac{\text{Block number}}{S} \right\rfloor$$

• ✅ Most of the flexibility of fully associative at a fraction of the hardware cost — only N comparators needed.
• Real CPUs use this almost universally: L1 typically 4–8 way, L3 often 12–16 way.

Unifying insight worth stating in an exam:

Direct-mapped = 1-way set-associative. Fully associative = L-way set-associative (one single set). Both are special cases of the same scheme.

3.5 Comparison Table (high-yield)

---

SECTION 4 — Replacement Algorithms ⭐

Needed whenever a set is full and a new block arrives (i.e., for associative and set-associative caches; not for direct-mapped).

4.1 FIFO (First In, First Out)

Evicts the block that has been resident longest, regardless of use. Implemented with a simple queue or counter.

• ✅ Very cheap hardware.
• ❌ May evict a heavily used block simply because it arrived early.
• ❌ Suffers Bélády's anomaly — increasing cache size can increase misses.

4.2 LRU (Least Recently Used) ⭐

Evicts the block unused for the longest time. Directly exploits temporal locality.

• ✅ Consistently the best hit rates among practical policies.
• ❌ Requires age tracking. For an N-way set, exact LRU needs roughly log₂(N!) bits per set, so real hardware uses pseudo-LRU approximations beyond 4-way.

4.3 LFU (Least Frequently Used)

Evicts the block with the lowest access count.

• ❌ Cache pollution — a block accessed heavily once and never again keeps a high count and resists eviction forever.

4.4 Random

Evicts a randomly chosen line.

• ✅ Free to implement; no state at all.
• ✅ Surprisingly competitive at high associativity (within a few percent of LRU).

4.5 Optimal (OPT / Bélády's algorithm)

Evicts the block that will be needed furthest in the future.

• ❌ Requires knowledge of future references — impossible to implement.
• ✅ Used as a theoretical benchmark to measure how good a real policy is.

---

SECTION 5 — Write Policies

On a write miss:

• Write-allocate — load the block into cache first, then write. Usually paired with write-back.
• No-write-allocate (write-around) — write straight to memory, bypassing cache. Usually paired with write-through.

Write buffer — a small FIFO that holds pending writes so the CPU need not stall waiting for memory; mitigates write-through's main weakness.

---

SECTION 6 — All Formulas (Derived and Explained)

One idea builds every formula below:

$$\text{Average time} = \sum (\text{Chance of a case}) \times (\text{Time that case costs})$$

🗣️ In simple words: list the cases (hit, miss, …), write how often each happens and how long it takes, multiply, add. Forget a formula in the exam → rebuild it this way.

6.1 Hit and Miss

What it finds: how often the cache already has the data.

$$H = \frac{\text{Hits}}{\text{Total accesses}} \qquad M = \frac{\text{Misses}}{\text{Total accesses}} = 1 - H$$ $$\text{Hits} = H \times \text{Total accesses} \qquad \text{Total accesses} = \text{Hits} + \text{Misses}$$

6.2 Average Access Time — Which Formula When ⚠️

6.2.1 The Difference First

If the question names no model, write your assumption in one line before solving.

6.2.2 Derivation — Simultaneous

Step 1: Cases — hit: chance $H$, time $T_c$; miss: chance $1-H$, time $T_m$ (memory was already searching).

Step 2: Chance × time, add

$$T_{avg} = H\,T_c + (1-H)\,T_m$$

Step 3: Rewrite in AMAT shape

$$\begin{aligned} T_{avg} &= T_c - (1-H)T_c + (1-H)T_m \\ &= T_c + (1-H)(T_m - T_c) \end{aligned}$$

So here the miss penalty is $T_m - T_c$.

6.2.3 Derivation — Hierarchical

Step 1: Cases — hit: chance $H$, time $T_c$; miss: chance $1-H$, time $T_c + T_m$.

Step 2: Chance × time, add

$$T_{avg} = H\,T_c + (1-H)(T_c + T_m)$$

Step 3: Simplify

$$\begin{aligned} T_{avg} &= H T_c + T_c + T_m - H T_c - H T_m \\ &= T_c + (1-H)\,T_m \end{aligned}$$

So here the miss penalty is the full $T_m$.

🗣️ In simple words: everyone pays the cache time; only the misses pay the extra.

6.2.4 Why Form A and Form B Are One Formula

Both reduce to:

$$T_{avg} = \text{Hit time} + \text{Miss rate} \times (\text{Extra time on a miss})$$

• The only question to ask: "On a miss, how much EXTRA time beyond the hit?"
• Gap between the two models:

$$T_{hier} - T_{sim} = (1-H)\,T_c$$

(the cache time wasted on misses — Numerical 3: $0.1 \times 10 = 1$ ns)

6.2.5 Reverse Formulas (finding H or M)

$$\text{Simultaneous: } H = \frac{T_m - T_{avg}}{T_m - T_c} \qquad \text{Hierarchical: } H = 1 - \frac{T_{avg} - T_c}{T_m} \qquad \text{AMAT: } M = \frac{AMAT - T_{hit}}{P}$$

Check with Numerical 14: $H = (80 - 10)/(80 - 5) = 70/75 = 0.9333$.

6.3 Miss Penalty with Block Transfer (asked in 2025)

What it finds: how long it takes to bring a whole line from memory.

$$\text{Words per line} = \frac{\text{Line size}}{\text{Word size}}$$ $$P = T_{first\,word} + (\text{Words} - 1) \times T_{next\,word}$$

Alternative wording (latency + bandwidth):

$$P = \text{Latency} + \frac{\text{Block size}}{\text{Bandwidth}}$$

If the cache waits for the line, then re-executes as a hit:

$$T_{miss} = T_c + P + T_c$$

Check with the 2025 question: 64-byte line = 16 words → $P = 50 + 15 \times 5 = 125$ ns, $T_{miss} = 2.5 + 125 + 2.5 = 130$ ns.

🗣️ In simple words: a bigger block raises H but also raises P — always compute both averages and compare.

6.4 Multi-Level Cache

6.4.1 Two Levels — Derivation

$M_1, M_2$ = local miss rates; $T_1, T_2, T_m$ = L1, L2, memory times (hierarchical).

Collecting each time term ($T_1$ is in all cases, $T_2$ in the last two, $T_m$ in the last one):

$$AMAT = T_1 + M_1\,T_2 + M_1 M_2\,T_m$$

Nested form (work inside out):

$$AMAT = T_1 + M_1\big[\,T_2 + M_2\,T_m\,\big]$$

Check with Numerical 4: $1 + (0.1)(8) + (0.1)(0.2)(100) = 1 + 0.8 + 2 = 3.8$ ns.

6.4.2 Three and n Levels

$$AMAT = T_1 + M_1T_2 + M_1M_2T_3 + M_1M_2M_3\,T_m$$ $$AMAT = \sum_{i=1}^{n} \big(M_1 M_2 \cdots M_{i-1}\big)\,T_i \qquad (\text{the first term is just } T_1)$$

🗣️ In simple words: each level's time × the fraction of accesses that reach it. Keep multiplying the misses.

6.4.3 Local vs Global Miss Rate

$$\text{Local } M_i = \frac{\text{Misses at level } i}{\text{Accesses reaching level } i} \qquad \text{Global } M_i = M_1 \times M_2 \times \cdots \times M_i$$

• Fraction of all accesses that reach memory = product of all local miss rates.

6.5 Cache Organisation

Counting:

$$L = \frac{\text{Cache size}}{\text{Block size}} \qquad S = \frac{L}{N} \qquad \text{Memory blocks} = \frac{\text{Main memory size}}{\text{Block size}}$$

Where an address goes:

$$\text{Block no.} = \left\lfloor \frac{\text{Address}}{\text{Block size}} \right\rfloor \qquad \text{Offset} = \text{Address} \bmod \text{Block size}$$ $$\text{Line} = \text{Block no.} \bmod L \;\;(\text{direct}) \qquad \text{Set} = \text{Block no.} \bmod S \;\;(\text{N-way})$$

Bits:

$$O = \log_2(\text{Block size}) \qquad \text{Line bits} = \log_2 L \qquad \text{Set bits} = \log_2 S \qquad T = A - \text{Middle} - O$$

Shortcut for tag bits (no address split needed):

$$T_{direct} = \log_2\!\left(\frac{\text{Main memory}}{\text{Cache size}}\right) \qquad T_{N\text{-way}} = \log_2\!\left(\frac{N \times \text{Main memory}}{\text{Cache size}}\right) \qquad T_{fully} = A - O$$

• Why it works: the tag says which of the many memory blocks that share one line (or set) is sitting there. Memory ÷ cache = how many blocks compete for one line; a set holds N, so multiply by N.
• Check with Numerical 5: $64\text{ KB} / 2\text{ KB} = 32 = 2^5$ → 5 bits. Numerical 6: $4 \times 2^{32} / 2^{13} = 2^{21}$ → 21 bits.

Hardware:

• Comparators: direct = 1, N-way = N, fully associative = L (each one T bits wide).

$$\text{Tag directory} = L \times (T + \text{Valid} + \text{Dirty} + \text{Replacement bits})$$ $$\text{Total cache} = \text{Data} + \text{Tag directory} \qquad \text{Overhead \%} = \frac{\text{Tag directory}}{\text{Data}} \times 100$$

6.6 Write-Policy Formulas

6.6.1 Write-Back — Dirty Blocks

Step 1: Cases on a miss ($d$ = fraction of evicted blocks that are dirty)

• Clean victim → chance $1-d$ → fetch new block: $P$
• Dirty victim → chance $d$ → write old block back, then fetch: $2P$

Step 2: Effective penalty

$$P_{eff} = (1-d)P + d(2P) = (1+d)\,P$$ $$AMAT = T_{hit} + M\,(1+d)\,P$$

🗣️ In simple words: every dirty eviction costs one extra memory trip.

6.6.2 Write-Through (simple model, no write buffer)

Reads (fraction $f_r$) behave like normal cache accesses; every write (fraction $f_w$) goes to memory:

$$T_{avg} = f_r\big[T_c + (1-H)\,T_m\big] + f_w\,T_m$$

Textbooks vary on this model — state your assumption. A write buffer hides most of the $f_w T_m$ cost.

6.7 Performance Impact

$$\text{Penalty (cycles)} = \frac{\text{Penalty (ns)}}{\text{Clock cycle (ns)}}$$ $$\text{Stall cycles per instruction} = \text{Accesses per instruction} \times \text{Miss rate} \times \text{Penalty}$$ $$\text{Effective CPI} = \text{Base CPI} + \text{Stall cycles per instruction}$$

Split instruction / data caches (more detailed):

$$\text{CPI} = \text{Base} + (1 \times M_I \times P) + (f_{data} \times M_D \times P)$$ $$\text{CPU time} = IC \times CPI \times \text{Cycle time} \qquad \text{Slowdown} = \frac{\text{Effective CPI}}{\text{Base CPI}} \qquad \text{Speedup} = \frac{T_{without}}{T_{with}}$$

6.8 One-Look Formula Sheet

6.9 Easy Ways to Remember 🧠

6.9.1 What Cache Is — The Chai Dhaba

• The dhaba keeps a few cups of tea ready on the counter (cache) instead of brewing every cup from scratch in the back (main memory). Most customers want the usual tea (locality), so most get it instantly (hit).

6.9.2 Mapping — Exam Hall Seating

• Direct mapped = fixed seat by roll number (roll no. mod seats). Finding someone is instant (1 comparator), but two students with the same seat keep pushing each other out → conflict misses.
• Fully associative = free seating. Sit anywhere (no conflicts), but to find someone you must check every seat (L comparators → expensive).
• Set-associative = your row is fixed, any seat in that row. Check only N seats → the practical compromise.
• Hook: "Mod gives the seat, divide gives the tag." Line/Set = block mod L (or S); Tag = block ÷ L (or S).

6.9.3 Address Split — "T-S-O" (Tag, Set, Offset), left to right

• Offset = which page of the book, Set/Line = which shelf, Tag = whose book it is.
• Bits must always add up to the address width — your built-in answer check.
• Shortcut hook: "Memory ÷ Cache = how many fight for one line" → that number in bits is the tag (×N for N-way).

6.9.4 The Three C's — First Day at School

• Compulsory = first day at a new school; nobody knows you yet (first-ever reference).
• Capacity = your school bag is simply too small for all your books.
• Conflict = two students forced into the same seat while other seats are empty.

6.9.5 Replacement Policies

• FIFO = bank queue — whoever came first leaves first, even if still busy. Only FIFO shows Belády's anomaly ("more space, more misses").
• LRU = the dusty book — the book you haven't opened for the longest goes back to the library.
• LFU = least popular student — problem: an old celebrity with a huge count never leaves (cache pollution).
• OPT = fortune teller — perfect, but nobody can see the future (benchmark only).
• Random = lottery — free, and surprisingly decent.

6.9.6 Write Policies — Notebook and Register

• Write-through = write in your rough notebook AND the official register every time — always safe, always slow.
• Write-back = write only in the notebook; mark the page red (dirty bit); copy to the register only when the page is torn out (evicted) — fast, but if the notebook is lost (power failure) the register is out of date.
• Dirty penalty hook: "Dirty = double trip" → $(1+d)P$.

6.9.7 Formula Hooks

• AMAT: "Sab ka hit time, missers ka penalty." Always ask: on a miss, how much EXTRA?
• Multi-level: "Keep multiplying the misses."
• Block transfer: "First word slow, rest quick" — like a counter queue: the clerk takes time to arrive, then serves everyone quickly.
• CPI: "Base + stalls"; stalls = how often × how unlucky × how long (accesses × miss rate × penalty).
• Reverse H: "Gap covered ÷ total gap" = $(T_m - T_{avg})/(T_m - T_c)$.

6.9.8 Quick Answer Checks ✅

• Average time must lie between cache time and memory time (or $T_c + T_m$ for hierarchical).
• Hierarchical answer > simultaneous answer for the same data.
• Tag + Middle + Offset = address bits.
• Hits + misses = total references in a trace.
• Convert penalties to the same unit (ns or cycles) before adding.

---

SECTION 7 — Solved Numericals

🧮 Numerical 1 — Hit Ratio and Average Access Time (Form A)

Q: A CPU makes 1,000 memory references, of which 950 are found in cache. Cache access time is 10 ns; main memory access time is 100 ns. Find the hit ratio, miss ratio, and average access time.

Step 1: Hit ratio

$$H = \frac{\text{Hits}}{\text{Total}} = \frac{950}{1000} = 0.95 \;(95\%)$$

Step 2: Miss ratio

$$M = 1 - H = 1 - 0.95 = 0.05 \;(5\%)$$

Step 3: Average access time (weighted average form)

$$\begin{aligned} T_{avg} &= H\,T_c + M\,T_m \\ &= (0.95 \times 10) + (0.05 \times 100) \\ &= 9.5 + 5 \\ &= 14.5\,\text{ns} \end{aligned}$$

Answer: H = 95%, M = 5%, Average access time = 14.5 ns.

Interpretation: without cache every access costs 100 ns. With a 95% hit rate the average falls to 14.5 ns — a 6.9× speedup from a small buffer. This one line converts a mechanical answer into an analytical one.

---

🧮 Numerical 2 — AMAT with Miss Penalty (Form B)

Q: Hit time = 2 ns, miss rate = 4%, miss penalty = 50 ns. Find AMAT.

$$\begin{aligned} AMAT &= \text{Hit time} + \text{Miss rate} \times \text{Miss penalty} \\ &= 2 + (0.04 \times 50) \\ &= 2 + 2 \\ &= 4\,\text{ns} \end{aligned}$$

Answer: 4 ns.

⚠️ Contrast with Numerical 1. There, 100 ns was the total memory time. Here, 50 ns is the extra penalty on top of the 2 ns hit time. Applying the wrong form gives the wrong answer — always identify which quantity the question has given.

---

🧮 Numerical 3 — Hierarchical vs Simultaneous Access

Q: Cache access = 10 ns, main memory access = 100 ns, hit ratio = 0.9. Compute average access time under (a) simultaneous access, (b) hierarchical access.

(a) Simultaneous — cache and memory searched together; a miss costs memory time only

$$\begin{aligned} T_{avg} &= H\,T_c + (1-H)\,T_m \\ &= (0.9 \times 10) + (0.1 \times 100) \\ &= 9 + 10 = 19\,\text{ns} \end{aligned}$$

(b) Hierarchical — memory searched only after the cache lookup fails; a miss costs both

$$\begin{aligned} T_{avg} &= H\,T_c + (1-H)(T_c + T_m) \\ &= (0.9 \times 10) + 0.1 \times (10 + 100) \\ &= 9 + 11 = 20\,\text{ns} \end{aligned}$$

Answer: (a) 19 ns, (b) 20 ns.

The 1 ns difference is exactly the wasted cache lookup on the 10% of accesses that miss. Examiners use this pair to test whether you read the access model or merely pattern-matched a formula.

---

🧮 Numerical 4 — Two-Level Cache

Q: L1 hit time = 1 ns, L1 miss rate = 10%. L2 hit time = 8 ns, L2 local miss rate = 20%. Main memory = 100 ns. Find AMAT and the global L2 miss rate.

Step 1: Effective L2 access time (work inside out)

$$\begin{aligned} T_{L2,eff} &= T_{L2} + M_{L2} \times T_m \\ &= 8 + (0.20 \times 100) \\ &= 8 + 20 = 28\,\text{ns} \end{aligned}$$

Step 2: AMAT

$$\begin{aligned} AMAT &= T_{L1} + M_{L1} \times T_{L2,eff} \\ &= 1 + (0.10 \times 28) \\ &= 1 + 2.8 = 3.8\,\text{ns} \end{aligned}$$

Step 3: Global L2 miss rate

$$M_{L2,global} = M_{L1} \times M_{L2,local} = 0.10 \times 0.20 = 0.02 = 2\%$$

Answer: AMAT = 3.8 ns; global L2 miss rate = 2%.

Only 10% of accesses reach L2 and only 2% reach main memory — the quantitative case for multi-level caching.

---

🧮 Numerical 5 — Direct-Mapped Address Breakdown

Q: A direct-mapped cache has 128 lines with a block size of 16 bytes. Main memory is 64 KB. Determine the tag, line, and offset bits.

Step 1: Address bits

$$64\,\text{KB} = 2^{16}\,\text{bytes} \;\Rightarrow\; A = 16\,\text{bits}$$

Step 2: Offset bits

$$16\,\text{bytes} = 2^{4} \;\Rightarrow\; O = 4\,\text{bits}$$

Step 3: Line bits (direct mapped)

$$128\,\text{lines} = 2^{7} \;\Rightarrow\; \text{Line} = 7\,\text{bits}$$

Step 4: Tag bits

$$T = 16 - 7 - 4 = 5\,\text{bits}$$

Verify: $5 + 7 + 4 = 16$ ✓ · Shortcut: cache = 128 × 16 B = 2 KB, $\log_2(64\text{ KB}/2\text{ KB}) = \log_2 32 = 5$ ✓

Answer: Tag = 5 bits, Line = 7 bits, Offset = 4 bits.

---

🧮 Numerical 6 — Set-Associative Address Breakdown

Q: A 4-way set-associative cache has 256 lines, block size 32 bytes, and a 32-bit address. Find the tag, set, and offset bits.

Step 1: Number of sets

$$S = \frac{L}{N} = \frac{256}{4} = 64\,\text{sets}$$

Step 2: Offset bits

$$32\,\text{bytes} = 2^{5} \;\Rightarrow\; O = 5\,\text{bits}$$

Step 3: Set bits

$$64 = 2^{6} \;\Rightarrow\; \text{Set} = 6\,\text{bits}$$

Step 4: Tag bits

$$T = 32 - 6 - 5 = 21\,\text{bits}$$

Verify: $21 + 6 + 5 = 32$ ✓

Answer: Tag = 21 bits, Set = 6 bits, Offset = 5 bits.

---

🧮 Numerical 7 — Fully Associative Breakdown (comparison)

Q: For the same cache as Numerical 6 (32-bit address, 32-byte blocks) organised as fully associative, find the field sizes. Compare tag storage overhead with the 4-way design.

Step 1: Fields (fully associative has no set field)

$$O = 5\,\text{bits} \qquad T = 32 - 5 = 27\,\text{bits}$$

Step 2: Tag storage (256 lines each)

$$\text{4-way: } 256 \times 21 = 5{,}376\,\text{bits} \qquad \text{Fully associative: } 256 \times 27 = 6{,}912\,\text{bits}$$

Step 3: Extra overhead

$$6{,}912 - 5{,}376 = 1{,}536\,\text{bits} \qquad \frac{1{,}536}{5{,}376} \times 100 \approx 29\%\ \text{more}$$

Answer: Tag = 27 bits, Offset = 5 bits; fully associative needs 29% more tag storage — plus 256 comparators instead of 4. This quantifies exactly why full associativity is impractical at scale.

---

🧮 Numerical 8 — Block Placement (which line does an address map to?)

Q: A direct-mapped cache has 64 lines and 8-byte blocks. Which cache line will memory address 1200 map to, and what is its tag?

Step 1: Block number

$$\text{Block} = \left\lfloor \frac{1200}{8} \right\rfloor = 150$$

Step 2: Line number

$$\text{Line} = 150 \bmod 64 = 150 - (2 \times 64) = 22$$

Step 3: Tag

$$\text{Tag} = \left\lfloor \frac{150}{64} \right\rfloor = 2$$

Step 4: Offset within the block

$$\text{Offset} = 1200 \bmod 8 = 0$$

Answer: Line 22, Tag 2, Offset 0.

---

🧮 Numerical 9 — Set Placement (set-associative)

Q: A 2-way set-associative cache has 128 lines and 16-byte blocks. Which set does address 4096 map to?

Step 1: Number of sets

$$S = \frac{128}{2} = 64$$

Step 2: Block number

$$\text{Block} = \frac{4096}{16} = 256$$

Step 3: Set number

$$\text{Set} = 256 \bmod 64 = 0$$

Answer: Set 0 (and it may occupy either of the 2 lines within that set).

---

🧮 Numerical 10 — FIFO Replacement Trace ⭐

Q: A fully associative cache holds 3 blocks and is initially empty. Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Using FIFO, find the number of hits and misses.

$$\text{References} = 12 \qquad \text{Hits} = 3 \qquad \text{Misses} = 9$$ $$H = \frac{3}{12} = 0.25 = 25\% \qquad M = \frac{9}{12} = 0.75 = 75\%$$

Answer: 3 hits, 9 misses, hit ratio 25%.

---

🧮 Numerical 11 — LRU Replacement Trace ⭐

Q: Same 3-block cache and same reference string (1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5) using LRU. Compare with FIFO.

$$\text{Hits} = 2 \qquad \text{Misses} = 10 \qquad H = \frac{2}{12} = 16.67\%$$

Answer: LRU gives 2 hits; FIFO gave 3 hits.

Important exam point: LRU is generally better than FIFO, but not always — this specific reference string is a counterexample. If an exam trace produces this result, it is not an error. State explicitly that no replacement policy is optimal for every reference string; only Bélády's OPT is, and it is unimplementable.

---

🧮 Numerical 12 — Optimal (OPT) Replacement for Comparison

Q: Same cache and string using the Optimal algorithm — evict the block needed furthest in the future.

$$\text{Hits} = 5 \qquad \text{Misses} = 7 \qquad H = \frac{5}{12} = 41.67\%$$

Answer: OPT achieves 5 hits — the theoretical maximum.

Summary comparison for this reference string:

Presenting all three in one table is exactly what a "compare replacement algorithms" question wants.

---

🧮 Numerical 13 — Bélády's Anomaly (FIFO with a larger cache)

Q: Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with FIFO. Compare a 3-block cache with a 4-block cache.

4-block FIFO trace:

$$\text{3 blocks: } 9\ \text{misses} \qquad \text{4 blocks: } 10\ \text{misses}$$

Answer: increasing the cache from 3 to 4 blocks increased misses from 9 to 10.

This is Bélády's anomaly — a counterintuitive property unique to FIFO among the common policies. LRU and OPT are "stack algorithms" and can never exhibit it. Naming the anomaly is a strong mark-earner.

---

🧮 Numerical 14 — Required Hit Ratio (reverse problem)

Q: Cache access = 5 ns, memory access = 80 ns. What hit ratio is required to achieve an average access time of 10 ns?

Step 1: Set up the weighted-average equation

$$5H + (1-H) \times 80 = 10$$

Step 2: Expand and collect the H terms

$$\begin{aligned} 5H + 80 - 80H &= 10 \\ -75H &= -70 \end{aligned}$$

Step 3: Solve

$$H = \frac{70}{75} = 0.9333$$

Shortcut check: $H = (T_m - T_{avg})/(T_m - T_c) = (80 - 10)/(80 - 5) = 0.9333$ ✓

Answer: 93.33% hit ratio required.

Reverse problems appear regularly. The method is always the same: write the weighted-average equation and solve for the unknown.

---

🧮 Numerical 15 — Cache Size Including Tag Directory

Q: A 4-way set-associative cache has a total data capacity of 16 KB, block size 32 bytes, and a 32-bit address. Each line also stores a valid bit and a dirty bit. Find the total physical size of the cache including the tag directory.

Step 1: Number of lines

$$L = \frac{16\,\text{KB}}{32\,\text{B}} = \frac{16{,}384}{32} = 512$$

Step 2: Number of sets

$$S = \frac{512}{4} = 128$$

Step 3: Address fields

$$O = \log_2 32 = 5 \qquad \text{Set} = \log_2 128 = 7 \qquad T = 32 - 7 - 5 = 20\,\text{bits}$$

Step 4: Bits per line in the directory

$$T + V + D = 20 + 1 + 1 = 22\,\text{bits}$$

Step 5: Tag directory size

$$512 \times 22 = 11{,}264\,\text{bits} = 1{,}408\,\text{bytes} = 1.375\,\text{KB}$$

Step 6: Total cache size

$$16 + 1.375 = 17.375\,\text{KB}$$

Answer: 17.375 KB total.

Overhead: 1.375/16 ≈ 8.6% of the data size is spent on metadata. Noting this overhead shows you understand that "16 KB cache" describes data capacity only.

---

🧮 Numerical 16 — Effective CPI Including Cache Misses

Q: A processor has a base CPI of 1.0. 30% of instructions are memory references. The cache miss rate is 5% and the miss penalty is 100 cycles. Find the effective CPI and the performance loss.

Step 1: Memory accesses per instruction

$$\underbrace{1.0}_{\text{instruction fetch}} + \underbrace{0.3}_{\text{data}} = 1.3$$

Step 2: Stall cycles per instruction

$$1.3 \times 0.05 \times 100 = 6.5\,\text{cycles}$$

Step 3: Effective CPI

$$\text{CPI} = 1.0 + 6.5 = 7.5$$

Step 4: Performance loss

$$\text{Slowdown} = \frac{7.5}{1.0} = 7.5\times$$

Answer: Effective CPI = 7.5 — the processor runs 7.5× slower than its ideal.

Interpretation: a 5% miss rate sounds trivial, but with a 100-cycle penalty it dominates execution time. This is the strongest possible argument for why cache design receives so much engineering attention, and it links directly to Performance Metrics.

---

🧮 Numerical 17 — Speedup from Adding Cache

Q: A system without cache has a memory access time of 80 ns. Adding a cache with 5 ns access time and a 92% hit ratio. Find the speedup.

Step 1: Average access time with cache

$$\begin{aligned} T_{avg} &= (0.92 \times 5) + (0.08 \times 80) \\ &= 4.6 + 6.4 = 11\,\text{ns} \end{aligned}$$

Step 2: Speedup

$$\text{Speedup} = \frac{T_{without}}{T_{with}} = \frac{80}{11} = 7.27\times$$

Answer: 7.27× speedup.

---

🧮 Numerical 18 — Three-Level Cache ⭐

Q: L1 = 1 ns (local miss 10%), L2 = 5 ns (local miss 20%), L3 = 20 ns (local miss 25%), main memory = 100 ns. Find AMAT and the fraction of accesses reaching memory.

Step 1: L3 subsystem (innermost)

$$T_{L3,eff} = 20 + (0.25 \times 100) = 20 + 25 = 45\,\text{ns}$$

Step 2: L2 subsystem

$$T_{L2,eff} = 5 + (0.20 \times 45) = 5 + 9 = 14\,\text{ns}$$

Step 3: AMAT

$$AMAT = 1 + (0.10 \times 14) = 1 + 1.4 = 2.4\,\text{ns}$$

Step 4: Check with the expanded form

$$1 + (0.1)(5) + (0.1)(0.2)(20) + (0.1)(0.2)(0.25)(100) = 1 + 0.5 + 0.4 + 0.5 = 2.4\,\text{ns} \;\checkmark$$

Step 5: Fraction reaching memory

$$0.10 \times 0.20 \times 0.25 = 0.005 = 0.5\%$$

Answer: AMAT = 2.4 ns; only 0.5% of accesses reach main memory.

---

🧮 Numerical 19 — Write-Back with Dirty Blocks

Q: A write-back cache has hit time 2 ns, miss rate 5%, and a block transfer time of 40 ns. 30% of replaced blocks are dirty. Find AMAT. What would it be if dirty blocks were ignored?

Step 1: Effective miss penalty

$$P_{eff} = (1 + d)\,P = (1 + 0.3) \times 40 = 52\,\text{ns}$$

Step 2: AMAT

$$\begin{aligned} AMAT &= T_{hit} + M \times P_{eff} \\ &= 2 + (0.05 \times 52) \\ &= 2 + 2.6 = 4.6\,\text{ns} \end{aligned}$$

Step 3: Ignoring dirty blocks

$$2 + (0.05 \times 40) = 4\,\text{ns}$$

Answer: 4.6 ns — dirty write-backs add 0.6 ns (15%) to every average access.

---

SECTION 8 — Exam Guidance

🎯 CSS Exam Angle

Cache is the most numerically examined topic in Computer Organization. A complete answer usually needs three layers:

1. Conceptual — locality, why cache works, the Three C's of misses.
2. Structural — the three mapping techniques with the address-partition diagram, plus replacement policies.
3. Numerical — hit ratio, AMAT, and address breakdown, with the formula written before substitution.

For a replacement-algorithm question, always draw the trace table (reference / cache contents / hit-or-miss). Examiners award marks for the table itself even if one row is wrong.

For a mapping question, always draw the address partition as a labelled box diagram and verify the bits sum to the address width.

🔁 Repeated CSS Questions

1. Explain cache mapping techniques — direct, fully associative, and set-associative — with diagrams. (Very frequently repeated)
2. Calculate average memory access time given hit ratio, cache time, and memory time. (Numerical — very frequently repeated)
3. Given a reference string and cache size, compute hits and misses under FIFO and LRU. (Numerical — frequently repeated)
4. Differentiate between write-through and write-back cache policies.
5. Given a cache configuration and memory size, determine tag, line/set, and offset bits. (Numerical)
6. What is the principle of locality? Explain temporal and spatial locality with examples.
7. Compare LRU, FIFO, Optimal, and Random replacement algorithms.
8. What is Bélády's anomaly? Which algorithms exhibit it?
9. Explain the three types of cache miss (compulsory, capacity, conflict) and how each is reduced.
10. Calculate the effective CPI of a processor accounting for cache misses. (Numerical)

⚠️ MCQ Traps

• Direct mapping is the fastest to search but has the worst hit rate. Lookup speed and hit quality are opposite properties here — candidates conflate them constantly.
• Direct-mapped caches need no replacement algorithm. "Which replacement policy does a direct-mapped cache use?" is a trick question — there is only one candidate line.
• Two average-access-time formulas exist. Hit time + (miss rate × miss penalty) where the penalty is extra time, versus (H × cache) + (M × memory) where memory time is total. Mixing them is the most common source of wrong answers.
• Simultaneous vs hierarchical access changes the miss cost. Hierarchical adds the wasted cache lookup to every miss.
• Only FIFO suffers Bélády's anomaly among the common policies. LRU and OPT are stack algorithms and cannot.
• LRU is not always better than FIFO for a specific reference string, though it is better on average.
• Optimal replacement is unimplementable — it needs future knowledge. It exists only as a benchmark.
• Conflict misses do not occur in a fully associative cache — by definition, any block may go anywhere.
• Write-back is faster but riskier; write-through is safer but slower. Frequently reversed in MCQs.
• Cache is managed entirely by hardware, unlike virtual memory, which the OS manages.
• A fully associative cache is a set-associative cache with one set; a direct-mapped cache is 1-way set-associative.
• "16 KB cache" refers to data capacity only — the tag directory adds roughly 5–10% more physical storage.

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

How to write: For numerical questions, present Given → Required → Formula → Substitution → Result → Check. For conceptual questions, answer each part directly with relevant technical reasoning and a small example. Marks allocations below guide answer depth; they are not an official FPSC marking scheme.

2022 · Paper-II · Q4(b) · 6 marks — Set-associative cache address format

Question: A set-associative cache consists of 64 lines, divided into 4-line sets. Main memory contains 4K blocks of 128 words each. Show the format of main memory addresses.

Given

Required: Find the number of tag, set-index, and word-offset bits and draw the address format.

Step 1 — Total main-memory address bits. Assuming word-addressable memory:

$$\begin{aligned} \text{Words in memory} &= 2^{12}\times 2^7 = 2^{19}\\ A &= \log_2(2^{19}) = \boxed{19\text{ bits}} \end{aligned}$$

Step 2 — Word offset. There are 128 words in each block:

$$O = \log_2(128) = \boxed{7\text{ bits}}$$

Step 3 — Number of sets and set index. Four-way associative means four cache lines per set, not four sets:

$$\begin{aligned} S &= \frac{64}{4} = 16\text{ sets}\\ I &= \log_2(16)=\boxed{4\text{ bits}} \end{aligned}$$

Step 4 — Tag.

$$T = A-I-O = 19-4-7 = \boxed{8\text{ bits}}$$

Step 5 — Address diagram.

| TAG (8) | SET INDEX (4) | WORD OFFSET (7) |

Check: 8 + 4 + 7 = 19 bits. Thus the 19-bit main-memory address contains an 8-bit tag, 4-bit set index and 7-bit word offset.

Interpretation: The set bits select one of 16 sets; the tag identifies which memory block occupies one of the four candidate lines; the word bits select the required word within the block. Since bytes per word were not specified, no extra byte-offset field can be determined.

2024 · Paper-II · Q3(a) · 7 marks — Cache and data representation

Question: Why is cache memory considered a critical component in a computer system? How does internal and external data representation contribute to optimising memory usage and system efficiency?

Model answer (7 marks)

Introduction: Cache memory is a small, fast memory placed close to the processor. It stores recently used blocks of main-memory data and instructions so that the CPU does not have to access slower RAM for every request.

1. Why cache is critical. Cache exploits temporal locality (recently accessed information may be used again) and spatial locality (nearby addresses are likely to be accessed). On a cache hit, data is obtained quickly; on a miss, the block must be fetched from a lower memory level. This reduces the average memory-access time.

2. Quantifying the benefit. When the miss penalty is the additional time on a miss:

$$AMAT = T_{hit} + (1-H)\times P_{miss}$$

For an illustrative cache with hit time 2 ns, hit ratio 0.95 and an extra miss penalty of 80 ns:

$$AMAT = 2 + (1-0.95)\times80 = \boxed{6\text{ ns}}$$

3. Internal representation. Data is stored internally as binary values, such as two's-complement integers, IEEE 754 floating-point numbers and encoded character bytes. Choosing appropriate widths and memory layouts can reduce wasted space; contiguous and aligned data structures can let one cache line serve several successive values.

4. External representation. Data presented to users or exchanged between programs may use decimal text, human-readable dates or formats such as JSON. Converting these to suitable internal formats for processing can reduce repeated text parsing and unnecessary memory traffic. External formats do not themselves determine cache organization.

5. Concrete example. A 64-byte cache line can contain sixteen contiguous 4-byte integers. When a program scans an array sequentially, fetching the first integer may bring the following fifteen integers into the cache. Scattered object references may require more separate cache-line accesses.

Conclusion: Cache improves performance by exploiting locality, while efficient internal representation and sensible data layout help conserve memory and increase cache usefulness.

2025 · Paper-II · Q2(b) · 7 marks — Line size, miss time and AMAT

Question: A single-level cache has an access time of 2.5 ns, a line size of 64 bytes and a hit ratio H = 0.95. Main memory has a first-word (4 bytes) access time of 50 ns and 5 ns for each following word. (i) What is the access time on a cache miss, if the cache waits until the line is fetched and then re-executes for a hit? (ii) If a 128-byte line raises H to 0.97, does this reduce the average access time?

Given

Required: (i) Total time on a cache miss for the 64-byte line; (ii) compare average access times and determine whether doubling line size helps.

Step 1 — Calculate the number of words in the original line.

$$W_{64} = \frac{64\text{ bytes}}{4\text{ bytes/word}} = \boxed{16\text{ words}}$$

Step 2 — Calculate full-line fetch time. The first word takes 50 ns; the remaining 15 words take 5 ns each:

$$\begin{aligned} T_{fetch,64} &= 50 + (16-1)\times 5\\ &= 50 + 75 = \boxed{125\text{ ns}} \end{aligned}$$

Step 3 — Calculate the miss access time. The question explicitly requires an initial unsuccessful cache lookup and then a second cache hit after loading:

$$\begin{aligned} T_{miss,64} &= T_{cache}+T_{fetch,64}+T_{cache}\\ &= 2.5+125+2.5 = \boxed{130\text{ ns}} \end{aligned}$$

Answer to (i): 130 ns.

Step 4 — Calculate AMAT for the 64-byte cache. A hit takes 2.5 ns; a miss takes 130 ns, so use the weighted average of total hit and miss times:

$$\begin{aligned} AMAT_{64} &= H\,T_{hit} + (1-H)\,T_{miss}\\ &=0.95(2.5)+0.05(130)\\ &=2.375+6.5=\boxed{8.875\text{ ns}} \end{aligned}$$

Step 5 — Repeat for a 128-byte line.

$$\begin{aligned} W_{128} &=128/4=32\text{ words}\\ T_{fetch,128}&=50+(32-1)\times5=\boxed{205\text{ ns}}\\ T_{miss,128}&=2.5+205+2.5=\boxed{210\text{ ns}} \end{aligned}$$

Step 6 — Calculate the new average access time (H = 0.97).

$$\begin{aligned} AMAT_{128}&=0.97(2.5)+0.03(210)\\ &=2.425+6.3=\boxed{8.725\text{ ns}} \end{aligned}$$

Step 7 — Compare and conclude.

$$\Delta AMAT = 8.875-8.725=\boxed{0.150\text{ ns}}$$

Relative decrease = (0.150 / 8.875) × 100 ≈ 1.69%.

Answer to (ii): Yes. The 128-byte line reduces average access time slightly, from 8.875 ns to 8.725 ns, because the higher hit ratio compensates for the longer miss penalty.

Conceptual trade-off: Larger blocks may exploit more spatial locality, but increase miss transfer time and can reduce the number of distinct blocks that fit in a fixed-size cache. Thus a larger line is not always better.

Exam trap: Do not use the AMAT formula with miss penalty as extra time and then substitute a total miss access time without adjusting it. The weighted-average calculation above consistently uses total hit and miss times.

📝 Practice MCQs (exam-style)

1. A direct-mapped cache has 128 lines of 16 bytes; main memory is 64 KB. How many tag bits?

• (A) 4
• (B) 5
• (C) 7
• (D) 9

Answer: (B) 5. Address = 16 bits, offset = 4, line = 7 → tag = 16 − 7 − 4 = 5. Shortcut: $\log_2(64\text{ KB}/2\text{ KB}) = 5$.

2. Which replacement policy can suffer Bélády's anomaly?

• (A) LRU
• (B) Optimal
• (C) FIFO
• (D) None of these

Answer: (C) FIFO. LRU and OPT are stack algorithms, so a bigger cache can never give them more misses. FIFO evicts by arrival order alone, so it can.

3. Conflict misses never occur in a:

• (A) Direct-mapped cache
• (B) 2-way set-associative cache
• (C) 4-way set-associative cache
• (D) Fully associative cache

Answer: (D). A block may go into any line, so no block is ever evicted while free space exists elsewhere.

4. Hit time = 2 ns, miss rate = 5%, miss penalty = 40 ns. The AMAT is:

• (A) 2.0 ns
• (B) 4.0 ns
• (C) 3.9 ns
• (D) 42 ns

Answer: (B) 4.0 ns. $AMAT = 2 + (0.05 \times 40) = 4$. Option (C) is the trap of using the weighted-average form on a penalty value.

5. Cache = 10 ns, memory = 100 ns, H = 0.9, simultaneous access. Average access time is:

• (A) 10 ns
• (B) 19 ns
• (C) 20 ns
• (D) 28 ns

Answer: (B) 19 ns. $0.9 \times 10 + 0.1 \times 100 = 19$. Option (C) is the hierarchical answer.

6. Which cache organisation needs no replacement algorithm?

• (A) Direct mapped
• (B) Fully associative
• (C) 4-way set-associative
• (D) 8-way set-associative

Answer: (A). Each block has exactly one possible line, so there is no choice to make.

7. The dirty bit is needed in a:

• (A) Write-through cache
• (B) Write-back cache
• (C) No-write-allocate cache only
• (D) Read-only instruction cache

Answer: (B). Write-back updates memory only on eviction, so it must remember which lines were modified.

8. L1 miss rate = 10%, L2 local miss rate = 20%. The global L2 miss rate is:

• (A) 30%
• (B) 20%
• (C) 10%
• (D) 2%

Answer: (D) 2%. Global = $0.10 \times 0.20 = 0.02$. Keep multiplying the misses.

9. A 4-way set-associative cache has 256 lines. The number of sets is:

• (A) 4
• (B) 64
• (C) 256
• (D) 1024

Answer: (B) 64. $S = L/N = 256/4 = 64$.

10. Fetching a whole block on a miss, instead of a single word, mainly exploits:

• (A) Temporal locality
• (B) Spatial locality
• (C) Bélády's anomaly
• (D) Write-back policy

Answer: (B) Spatial locality. Neighbouring addresses are likely to be used next, so bringing the whole block turns future accesses into hits.