Memory & Cache — Practice

Exam-pattern questions across locality, direct-mapped caches, bits, and associativity.

Locality & hierarchy

M-1smallState the two types of locality with an example of each.

M-2smallDown the memory hierarchy, what happens to size, speed and cost per bit?

Direct-mapped caches

M-3smallAn 8-line direct-mapped cache. Which line do memory blocks 12 and 20 map to, and what's the problem?

12 \bmod 8 = 4

and

20 \bmod 8 = 4

— both map to line 4. Problem: they conflict; only one can be cached at a time, so alternating accesses keep evicting each other (a conflict miss).

M-4big32-bit address, direct-mapped cache with 1024 one-word lines. Split the address and give the hit condition.

byte offset = 2, block offset = 0 (1-word block), index =

\log_2 1024 = 10

, tag =

32 - 10 - 2 = 20

Hit ⇔ valid = 1 AND stored tag = address tag.

Total bits

M-5bigHow many total bits for a direct-mapped cache with 16 KB of data, 4-word blocks, 32-bit address? (COD/slide example)

Block = 4 words = 16 B =

2^4

. Lines =

16\text{KB}/16\text{B} = 1024

. block offset =

\log_2 4 = 2

, byte offset = 2, index = 10, tag =

32 - 10 - 2 - 2 = 18

\text{bits/line} = 1 + 18 + (4\times32) = 147 \quad\Rightarrow\quad 1024\times147 = 150{,}528\ \text{bits}\ (147\text{ Kibits})

150,528 bits.

M-6bigTotal memory units for a direct-mapped cache with 2 MB of data, 8-word blocks, 32-bit address. (Spring 2024 Q3c)

Block = 8 words = 32 B =

2^5

. Lines =

2\text{MB}/32\text{B} = 2^{21}/2^{5} = 2^{16} = 65536

. block offset = 3, byte offset = 2, index = 16, tag =

32 - 16 - 3 - 2 = 11

\text{bits/line} = 1 + 11 + 256 = 268 \quad\Rightarrow\quad 65536 \times 268 = 17{,}563{,}648\ \text{bits}

≈ 17,152 Kibits (16.75 Mibits).

M-7smallA direct-mapped cache has 2^12 blocks and memory has 2^30 blocks. Index and tag size?

index =

\log_2 2^{12} = 12

bits; tag =

\log_2(2^{30}/2^{12}) = 30 - 12 = 18

bits. index 12, tag 18.

Associativity

M-8smallHow many degrees of associativity are possible for a 16-block cache? List them.

16 = 2^4 \Rightarrow n+1 = 5

configurations: 1-, 2-, 4-, 8-, and 16-way (1-way = direct-mapped, 16-way = fully associative).

M-9smallFor a cache with 2^n entries, which configuration is direct-mapped and which is fully associative?

Direct-mapped = 1-way (each set = 1 line, full index). Fully associative = 2ⁿ-way (one set holds all lines, no index). Total configurations =

n+1

Virtual memory

M-10small16-bit virtual address, 4 KB pages. How many bits for the offset and VPN, and how many virtual pages?

offset =

\log_2 4096 = 12

bits; VPN =

16 - 12 = 4

bits; virtual pages =

2^4 =

16 pages.