Cache mapping

ACompressed recap

🧾

Address split: offset = log₂ B; lines L = C/B; sets S = L/k; index = log₂ S (0 for fully associative); tag = rest. Block j → set j mod S. Direct: 1 comparator, no policy; k-way: k comparators + k-to-1 MUX per output bit; fully associative: L comparators. Doubling ways: index −1, tag +1. Hit latency adds MUX delay. Tag directory = L × (tag + V [+ D] [+ replacement]). Trace with block numbers; three Cs: compulsory, capacity (fully associative of same size also misses), conflict. Policies: LRU (hits reorder), FIFO (they don't; Belady's anomaly), OPT (farthest future use, benchmark), random.

BMerged rule card

4.2.1 Cache lines and blocks; direct mapping: tag, line, offset

• Offset = log₂ B; lines L = C/B; line bits = log₂ L; tag = address bits − line − offset.
• Block j → line j mod L, tag ⌊j/L⌋.
• Line stores valid + tag + data. One comparator; no replacement policy.
• Blocks per line = 2^(tag bits).

4.2.2 Fully associative and set-associative mapping; comparators and multiplexers

• k-way: sets S = L/k; set bits log₂ S; tag = address − set − offset; block j → set j mod S.
• Fully associative: tag = address − offset; L comparators.
• Comparators = k; data MUXes = output width × (k-to-1).
• Doubling ways: index −1 bit, tag +1 bit. Hit latency adds MUX delay for k > 1.

4.2.3 Tag directory size and cache hardware: valid, dirty and replacement bits

• Directory = L × (tag + V [+ D] [+ replacement bits]).
• Total storage = L·B·8 + directory.
• Index never stored. Comparators: 1, k or L, each tag-bits wide.

4.2.4 Tracing references: hits and misses; compulsory, capacity and conflict misses

• Trace: byte address → block → set (j mod S) → hit/miss → update (LRU unless stated).
• Direct: S = L; fully associative: S = 1.
• Compulsory (first use), capacity (fully associative of same size also misses), conflict (the rest).
• Associativity cuts conflict misses; size cuts capacity misses; neither guarantees fewer misses on every sequence.

4.2.5 Replacement policies: LRU, FIFO, random, optimal; tracing sets

• LRU: evict least recently used (hits reorder). FIFO: evict earliest loaded (hits don't). Random. OPT: evict farthest next use (benchmark). LFU: least used.
• Belady's anomaly: FIFO only.
• LRU state: log₂ k bits per line (counter scheme); ≥ ⌈log₂ k!⌉ per set exact.

CInterleaved GATE-style questions

Q1NAT1 markSplit

24-bit byte addresses, 8 KB direct-mapped cache, 16-byte blocks. Tag bits?

Numerical answer: ________

Q2NAT2 marksSet-associative split

32-bit addresses, 512 KB 8-way cache, 128-byte blocks. Set-index bits?

Numerical answer: ________

Q3NAT2 marksDirectory

Direct-mapped 16 KB cache, 16-byte blocks, 32-bit addresses, V and D bits. Directory bits?

Numerical answer: ________

Q4NAT2 marksHit latency

Same 16 KB cache (16-byte blocks, 32-bit addresses) made 4-way. A t-bit comparator takes t/10 ns; a 4-to-1 MUX takes 1 ns. Hit latency (ns)?

Numerical answer: ________

Q5NAT2 marksTrace

A 4-line direct-mapped cache receives blocks 2, 6, 2, 3, 7, 3, 6, 2. Misses?

Numerical answer: ________

Q6NAT2 marksTrace associative

The same sequence on a 4-line fully associative LRU cache. Misses?

Numerical answer: ________

Q7MCQ1 markMiss type

A direct-mapped cache misses on a block that a fully associative cache of the same size would have kept. The miss is:

• (A) capacity
• (B) conflict
• (C) coherence
• (D) compulsory

Q8NAT2 marksPolicy

A 2-way set receives (all mapping to it) blocks A, B, A, C, B, A with FIFO. Misses?

Numerical answer: ________

DAnswer Vault