Cache Memory — Practice Problem Set

Direct-Mapped Caches · Tag / Index / Offset · SRAM Bit Counting

These problems cover every calculation type for direct-mapped cache design: deriving address fields
from cache parameters, reversing the calculation to find cache size or block size, computing total
SRAM requirements, and comparing word-addressed vs byte-addressed schemes. Work each problem
before checking the solution.

Quick Reference
Field Formula What it means
Offset (m) log₂(block size in Selects byte within block
bytes)
Index (n) log₂(number of Selects which cache line
blocks)
Tag addr bits − n − m Identifies which memory
block
Cache size 2^n × 2^m bytes Recover from n and m
SRAM bits/line (2^m × 8) + tag + 1 Data + tag + valid bit

Problem 1: Basic Tag Calculation [Warm-Up]

Given Find
A direct-mapped cache uses 32-bit byte Offset bits (m), index bits (n), and tag bits.
addresses, has 512 blocks, and each block
holds 16 bytes.

Hint: m = log₂(block size in bytes). n = log₂(number of blocks). tag = 32 − n − m.

Your Work:

Solution
Step 1: m = log₂(16) = 4
Step 2: n = log₂(512) = 9
Step 3: tag = 32 − 9 − 4 = 19 bits
Answer: 19 tag bits, 9 index bits, 4 offset bits.
 Key Insight: The three fields must always sum to 32 (the address width). Check your
answer by adding them up.

Problem 2: Words to Bytes Conversion [Warm-Up]

Given Find
A cache has 4 KiB capacity, 32-bit byte All address fields and tag size.
addresses, and 4-word blocks (4 bytes per
word).

Hint: Convert words to bytes first: 4 words × 4 bytes/word = 16 bytes per block.

Your Work:

Solution
Step 1: Block size = 4 × 4 = 16 bytes → m = log₂(16) = 4
Step 2: Number of blocks = 4 KiB / 16 B = 256 → n = log₂(256) = 8
Step 3: tag = 32 − 8 − 4 = 20 bits
Answer: 20 tag bits, 8 index bits, 4 offset bits.

Key Insight: Block size must always be converted to bytes before computing m, because
byte addresses index individual bytes within a block.

Problem 3: Solve for Cache Size [Standard]

Given Find
A direct-mapped cache has tag = 20 bits, Cache size in KiB.
uses 32-bit byte addresses, and has 8-word
blocks (4 bytes/word).

Hint: You know tag and m, so solve for n. Then cache size = 2^n × 2^m bytes.

Your Work:
 Solution
Step 1: Block size = 8 × 4 = 32 bytes → m = 5
Step 2: n = 32 − tag − m = 32 − 20 − 5 = 7
Step 3: Number of blocks = 2^7 = 128
Step 4: Cache size = 128 × 32 = 4,096 bytes = 4 KiB
Answer: 4 KiB

Key Insight: A larger tag means fewer index bits and therefore a smaller cache. Tags and
cache size trade off directly when address width and block size are fixed.

Problem 4: Bit-Range Decoding [Standard]

Given Find
A direct-mapped cache uses 32-bit byte Block size in bytes, number of blocks, cache
addresses. The index field is bits 13–6 and size, and tag bits.
the offset field is bits 5–0.

Hint: Count the bits in each field. Bit range [high:low] has (high − low + 1) bits.

Your Work:

Solution
Step 1: Offset: bits 5–0 → m = 6 → block size = 2^6 = 64 bytes
Step 2: Index: bits 13–6 → n = 8 → number of blocks = 2^8 = 256
Step 3: Cache size = 256 × 64 = 16,384 bytes = 16 KiB
Step 4: tag = 32 − 8 − 6 = 18 bits
Answer: 64-byte blocks, 256 blocks, 16 KiB cache, 18 tag bits.

Key Insight: Reading bit ranges is just subtraction: (high − low + 1). The +1 is easy to forget
— bits 5–0 is 6 bits, not 5.

Problem 5: Total SRAM Bits [Standard]

Given Find
A direct-mapped cache has 1,024 blocks, 32- Total SRAM bits required (include valid bit).
byte blocks, and 32-bit byte addresses. Express in Kibibits.

Hint: Bits per line = (block bytes × 8) + tag bits + 1 valid bit. Total = lines × bits per line.

Your Work:

Solution
Step 1: m = log₂(32) = 5, n = log₂(1024) = 10
Step 2: tag = 32 − 10 − 5 = 17 bits
Step 3: Bits per line = (32 × 8) + 17 + 1 = 256 + 18 = 274
Step 4: Total = 1,024 × 274 = 280,576 bits = 274 Kibibits
Answer: 274 Kibibits

Key Insight: The overhead (tag + valid) is small per line but adds up. Here, 18 overhead
bits per 256 data bits ≈ 7% overhead.

Problem 6: Fixed Cache Size, Changing Block Size [Tricky]

Given Find
Two caches both hold 16 KiB with 32-bit byte Tag bits for each cache. Which has more,
addresses. Cache A has 4-word blocks; and by how much?
Cache B has 32-word blocks. Assume 4
bytes per word.

Hint: tag = 32 − log₂(cache size in bytes). Block size does not affect tag when total cache
size is fixed.

Your Work:

Solution
Step 1: Cache A: block = 16 B → m = 4, n = log₂(16K/16) = 10, tag =
32−10−4 = 18
Step 2: Cache B: block = 128 B → m = 7, n = log₂(16K/128) = 7, tag =
32−7−7 = 18
Step 3: Both caches have 18 tag bits.
 Answer: Both have 18 tag bits — the same.

Key Insight: tag = address bits − log₂(cache bytes). Since both caches have the same total
capacity and same address width, the tag is identical regardless of block size. Bigger blocks
trade index bits for offset bits at exactly 1-for-1.

Problem 7: 64-Bit Address Space [Tricky]

Given Find
A direct-mapped cache has 2^12 blocks, Total SRAM bits. Express in Kibibits.
each block holds 8 words (4 bytes/word), and
uses 64-bit byte addresses.

Hint: Same process as 32-bit, just replace 32 with 64 in the tag formula.

Your Work:

Solution
Step 1: Block = 8 × 4 = 32 bytes → m = 5
Step 2: n = 12 (given)
Step 3: tag = 64 − 12 − 5 = 47 bits
Step 4: Bits per line = (32 × 8) + 47 + 1 = 256 + 48 = 304
Step 5: Total = 2^12 × 304 = 4,096 × 304 = 1,245,184 bits = 1,216
Kibibits
Answer: 1,216 Kibibits

Key Insight: With 64-bit addresses the tag balloons — 47 bits of tag for just 5 bits of offset
means the tag is nearly 10× larger than the offset. Tag overhead is far higher in large
address spaces.

Problem 8: Word-Addressed vs Byte-Addressed [Tricky]

Given Find
A word-addressed cache uses 32-bit Tag bits for the word-addressed cache. Then
addresses, has 128 blocks, and 8 words per find tag bits for the equivalent byte-
block (no byte offset). Assume 4-byte words. addressed cache with the same physical
size. How do they differ and why?
 Hint: Word-addressed: m = log₂(words per block). Byte-addressed: m = log₂(block size in
bytes). The difference equals log₂(bytes per word).

Your Work:

Solution
Step 1: Word-addressed: m = log₂(8) = 3, n = log₂(128) = 7, tag =
32−7−3 = 22 bits
Step 2: Byte-addressed equivalent: block = 8×4 = 32 B → m = 5, n =
7, tag = 32−7−5 = 20 bits
Step 3: Difference: 22 − 20 = 2 bits
Answer: Word-addressed tag is 2 bits larger (22 vs 20 bits).

Key Insight: The 2-bit gap = log₂(4 bytes/word). In byte-addressing those 2 bits become
part of the offset (to select a byte within a word); in word-addressing they are freed from the
offset and reappear in the tag.

Problem 9: Reverse Engineer the Block Size [Challenge]

Given Find
A direct-mapped cache has 32-bit byte Block size in words.
addresses, a tag of 18 bits, and 256 cache
lines. What is the block size in words (4
bytes/word)?

Hint: Solve for m from the identity tag + n + m = 32. Then block size = 2^m bytes.

Your Work:

Solution
Step 1: n = log₂(256) = 8
Step 2: m = 32 − tag − n = 32 − 18 − 8 = 6
Step 3: Block size = 2^6 = 64 bytes = 64 / 4 = 16 words
Answer: 16 words per block.
 Key Insight: You can always recover any single unknown from tag + n + m = address bits,
as long as you know the other two.

Problem 10: Overhead Percentage [Challenge]

Given Find
A 64 KiB direct-mapped cache with 64-byte What percentage of total SRAM bits are
blocks uses 32-bit byte addresses. overhead (tag + valid bits, not data)?

Hint: Compute total bits and data bits separately. Overhead % = (overhead bits / total bits) ×
100.

Your Work:

Solution
Step 1: m = log₂(64) = 6, n = log₂(64K/64) = log₂(1024) = 10
Step 2: tag = 32 − 10 − 6 = 16 bits
Step 3: Bits per line = (64 × 8) + 16 + 1 = 512 + 17 = 529
Step 4: Total bits = 1,024 × 529 = 541,696
Step 5: Data bits = 1,024 × 512 = 524,288
Step 6: Overhead = 541,696 − 524,288 = 17,408 bits
Step 7: Overhead % = 17,408 / 541,696 ≈ 3.21%
Answer: ≈ 3.2% overhead

Key Insight: Larger blocks reduce overhead percentage because the tag+valid cost is
amortized over more data bits. Tiny blocks (like 1-word blocks) can push overhead above
10%.