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

0 · Recall Warm-up

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

• Average rotational latency at 7,200 rpm? from Lesson 4.1.5
• Hierarchical AMAT formula? from Lesson 4.1.2
• 2ᵃ / 2ᵇ = ? from Lesson 0.2.1

1 · The Hook

🎣

A cache holds a few hundred blocks out of millions in memory. When the CPU asks for an address, the cache must answer "do I have it, and where?" in about a nanosecond, without searching. Direct mapping answers with arithmetic: the address itself says which line to look in, and a short tag confirms whether the right block is there.

2 · Predict First

🤔

32-bit byte addresses, a 32 KB cache, 64-byte blocks, and each memory block can go into exactly one cache line. How many bits of the address pick the byte inside the block, how many pick the line, and how many are left?

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

3 · Core Concept

💡

Predict First — the answer

Offset: log₂ 64 = 6. Lines: 32 KB / 64 B = 2⁹ = 512 → 9 line bits. Left over (the tag): 32 − 9 − 6 = 17.

Blocks and lines

• Memory is divided into blocks of B bytes: block number = ⌊address / B⌋, offset = address mod B.
• The cache has L = cache size / B lines, each holding one block.

Direct mapping

Memory block j can go only in line j mod L.

Address split (most significant bits on the left):

• Offset = log₂ B: which byte in the block.
• Line (index) = log₂ L: which cache line (j mod L).
• Tag = the rest = ⌊j / L⌋: which of the many blocks that share this line is actually there.

What a line stores

Valid bit (does the line hold anything?), tag, and the data block.

Lookup

• Use the line bits to select one line.
• Compare the stored tag with the address's tag (one comparator).
• Hit if valid and equal: use the offset to pick the byte. Miss otherwise: fetch block j from memory into that line (replacing whatever was there), set the tag and valid bit.

There is no choice of where to put a block, so no replacement policy is needed.

Worked split

32-bit address, 32 KB cache, 64 B blocks: tag 17 | line 9 | offset 6. Address 0x12345678: offset = low 6 bits = 0x38 = 56; line = next 9 bits = 345; tag = top 17 bits = 0x2468.

Small example for tracing

16-bit addresses, 256 B cache, 16 B blocks: 16 lines → tag 8 | line 4 | offset 4.

• 0x1A2F → tag 0x1A, line 2, offset 0xF.
• 0x3B24 → tag 0x3B, line 2, offset 4.

Both want line 2: whichever came last evicts the other. Repeated use of two blocks that share a line causes conflict misses even if the cache is mostly empty.

How many blocks share a line

Memory blocks / lines = 2^(tag bits). With a 17-bit tag, 2¹⁷ different blocks compete for each line.

4 · Visual

32-bit address, 32 KB direct-mapped cache, 64 B blocks

 31                15 14          6 5      0
+--------------------+-------------+--------+
|      tag (17)      |  line (9)   | off (6)|
+--------------------+-------------+--------+
                            |
                            v
   line 0   [V][  tag  ][ 64-byte block ]
   ...
   line 345 [1][0x2468 ][ ...            ]  <- compare stored tag with address tag
   ...                                         (one comparator)
   line 511 [V][  tag  ][ 64-byte block ]

5 · Worked Examples

Example 1 Easy

24-bit byte addresses, 16 KB direct-mapped cache, 32-byte blocks. Tag, line and offset widths?

Solution

Offset 5; lines 16K/32 = 512 → 9; tag 24 − 14 = 10 | 9 | 5.

Example 2 Medium

In that cache, which line does byte address 0x00ABCD go to, and with which tag?

Solution

Block = 0xABCD ÷ 32 = 1374. Line = 1374 mod 512 = 350; tag = ⌊1374 / 512⌋ = 2.

Example 3 GATE

A 1 MB main memory (byte-addressable) and a 4 KB direct-mapped cache with 16-byte blocks. How many memory blocks map to each cache line?

Solution

Memory blocks = 2²⁰ / 2⁴ = 2¹⁶; lines = 2¹² / 2⁴ = 2⁸; per line = 2¹⁶ / 2⁸ = 256 (= 2^(tag bits), tag = 20 − 8 − 4 = 8).

6 · GATE Traps

⚠️

• Offset from block size, line bits from the number of lines, tag = the rest.
• Lines = cache size ÷ block size, not cache size ÷ word size.
• Direct mapping needs one comparator and no replacement policy.
• Two blocks with the same line bits evict each other even when other lines are empty.

7 · Memory Hook

🧠

"Tag | Line | Offset — who | where | which byte." The line is j mod L; the tag is j div L.

8 · Connect the Dots

Direct mapping fixes one line per block, which is cheap but conflict-prone. Next: let a block go in any of several lines (set-associative) or in any line at all (fully associative), and see what that costs in comparators.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markTag bits

32-bit addresses, a 64 KB direct-mapped cache with 64-byte blocks. Tag bits?

Numerical answer: ________

Q2NAT2 marksLine number

16-bit addresses, 256 B direct-mapped cache, 16-byte blocks. Which line does address 0x7E5C go to?

Numerical answer: ________

Q3MCQ1 markConflict

In that 16-line cache, which address competes for the same line as 0x1A2F?

• (A) 0x9B21
• (B) 0x1A3F
• (C) 0x1A1F
• (D) 0x2A4F

Q4NAT2 marksBlocks per line

A 4 GB byte-addressable memory and a 256 KB direct-mapped cache with 128-byte blocks. How many memory blocks map to each line?

Numerical answer: ________

Q5MSQ2 marksDirect mapping facts

Which are true?

• (A) The line number is the block number mod the number of lines.
• (B) Each memory block can be placed in exactly one line.
• (C) Hit detection needs one tag comparator.
• (D) A direct-mapped cache needs a replacement policy such as LRU.

10 · Rule Card

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

11 · Concept Ledger

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

block number and offsetcache linedirect mappingtagline (index) fieldvalid bittag comparisonconflict between blocksblocks per line = 2^tag

12 · Answer Vault