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

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• 4-way, 32 KB, 64 B blocks, 32-bit address: tag | set | offset? from Lesson 4.2.2
• Blocks per line in a direct-mapped cache with a t-bit tag? from Lesson 4.2.1
• DRAM refresh overhead formula? from Lesson 4.1.3

1 · The Hook

🎣

A "32 KB cache" stores more than 32 KB: every line also needs its tag, a valid bit and maybe a dirty bit and bits for replacement. GATE asks for the size of this tag directory almost every few years; it is pure bookkeeping once the address split is known.

2 · Predict First

🤔

A direct-mapped 32 KB cache with 32-byte blocks and 32-bit addresses keeps a valid bit and a modified bit per line. How many bits does its tag directory hold?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Lines = 1024; offset 5, index 10 → tag 17. Per line 17 + 1 + 1 = 19 bits. Total 1024 × 19 = 19,456 bits.

Per-line metadata

Tag directory size = number of lines × (tag + V + D + replacement bits).

The index is not stored: it is the line's position.

Total cache storage

Total bits = data bits + tag directory = L × B × 8 + L × (tag + extra).

Worked examples

• Direct-mapped, 32 KB, 32 B blocks, 32-bit address, V + D: 19,456 bits (Predict).
• 4-way, 64 KB, 64 B blocks, 32-bit address, V + D + 2 LRU bits per line: lines 1024, sets 256 → index 8, offset 6, tag 18; per line 18 + 4 = 22 → 22,528 bits.
• 2-way, 64 KB, 16 B blocks, 32-bit address, tags only: lines 4096, sets 2048 → index 11, offset 4, tag 17 → 69,632 bits (68 Kbits).

Comparator hardware

• Comparators: 1 (direct), k (k-way), L (fully associative); each tag-bits wide.
• Fully associative caches need many wide comparators: that is why large caches are rarely fully associative.

4 · Visual

One line of a 4-way, write-back, LRU cache (64 B blocks, 32-bit addresses)

+---+---+-----+--------------------+------------------------------+
| V | D | LRU |     tag (18)       |       data (64 bytes)        |
| 1 | 1 |  2  |                    |         512 bits             |
+---+---+-----+--------------------+------------------------------+
 '-------- tag directory: 22 bits --------'   '--- data store ---'

5 · Worked Examples

Example 1 Easy

A direct-mapped cache has 2,048 lines and a 15-bit tag; each line has only a valid bit besides. Tag directory size in bits?

Solution

2048 × 16 = 32,768 bits (4 KB).

Example 2 Medium

A fully associative cache: 32-bit addresses, 256 lines of 64 bytes, each line with V, D and 8 bits of LRU state. Tag directory bits?

Solution

Tag 32 − 6 = 26; per line 26 + 1 + 1 + 8 = 36 → 256 × 36 = 9,216 bits.

Example 3 GATE

A 64 KB 2-way set-associative cache, 16-byte blocks, 32-bit addresses. What is the total size of the tags (tags only)?

Solution

Lines 4096; sets 2048 → 11 bits; offset 4; tag 17 → 4096 × 17 = 69,632 bits = 68 Kbits.

6 · GATE Traps

⚠️

• The index is not stored; only tag and status bits.
• Count the dirty bit only for write-back caches (or when the question lists it).
• Multiply by lines, not sets.
• Replacement bits per line vs per set: use what the question says.

7 · Memory Hook

🧠

"Directory = lines × (tag + status)." The line's position is free; everything else costs bits.

8 · Connect the Dots

You can split addresses and size the tag store. Next: run a cache. Feed it a sequence of references, mark each hit or miss, and classify misses as compulsory, capacity or conflict.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksTag directory

A direct-mapped 128 KB cache, 64-byte blocks, 32-bit addresses; each line has V and D bits. Tag directory size in bits?

Numerical answer: ________

Q2NAT2 marksSet-associative directory

A 4-way 32 KB cache, 32-byte blocks, 32-bit addresses; V bit and 2 LRU bits per line. Tag directory bits?

Numerical answer: ________

Q3NAT1 markComparators

How many tag comparators does a fully associative cache with 512 lines need?

Numerical answer: ________

Q4MCQ1 markNot stored

Which part of the address is NOT stored in the tag directory of a set-associative cache?

• (A) Neither; both are stored
• (B) Set index
• (C) Both are stored only for dirty lines
• (D) Tag

Q5NAT2 marksTotal storage

A direct-mapped cache: 256 lines of 32 bytes; 32-bit addresses; valid bit only. Total storage (data + directory) in bits?

Numerical answer: ________

10 · Rule Card

• 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.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

tag directory (tag store)valid bitdirty (modified) bitreplacement (LRU) bitstotal cache storagecomparator width

12 · Answer Vault