Question 3 of 6

Question 3 (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) 4GB (2³²-byte) address space; 48KB cache, 3-way set-associative, 32-byte blocks. (b) the same cache; a block resident in set 0x10 tagged 0x01. (c) 100 sequential byte reads against an initially-empty 16-byte-block data cache (instruction fetches always hit and are irrelevant to the data-cache traffic).

Find. (a) how a physical address splits into tag/index/offset fields for this cache. (b) the full hexadecimal address range spanned by the described block. (c) the minimum and maximum bytes the data cache must fetch from memory over the 100 reads.

Approach. (a) derive the number of sets from capacity/(ways×block size), then take base-2 logs to size each field. (b) reconstruct the address by placing tag, then set index, then a zero offset, and add the block size−1 for the top of the range. (c) reason about the best- and worst-case spatial locality of 100 reads against 16-byte blocks.

1. Part (a) — cache indexing. A 3-way set-associative cache holding 48KB total in 32-byte blocks has $$\text{number of sets}=\frac{\text{cache size}}{\text{ways}\times\text{block size}}=\frac{48\times1024}{3\times32}=\frac{49{,}152}{96}=512\ \text{sets}$$ Since $512=2^9$, the set index needs $\log_2 512=9$ bits, and locating a byte within a 32-byte block needs $\log_2 32=5$ offset bits. With a 4GB ($2^{32}$-byte) address space, every physical address is 32 bits wide, so the remaining bits form the tag: $$\text{tag bits}=32-9-5=18$$ $$\boxed{\text{address}=[\text{tag }18\text{ bits}]\,[\text{set index }9\text{ bits}]\,[\text{block offset }5\text{ bits}]}$$ Each of the 512 sets holds 3 blocks (3-way associative), and any address maps to exactly one set via its middle 9 bits, then is compared against that set's (up to) 3 resident tags in parallel.
2. Part (b) — address range for set 0x10, tag 0x01. Using the field layout from part (a), the block's starting (offset = 0) address is formed by placing the tag in the top 18 bits and the set index in the next 9 bits: $$\text{low address} = (\text{tag}\ll14)\ |\ (\text{set}\ll5) = (0\text{x01}\ll14)\ |\ (0\text{x10}\ll5) = 0\text{x4000}+0\text{x200}=0\text{x4200}$$ (the shift by 14 places the tag above the combined 9 index + 5 offset bits). The block spans 32 contiguous bytes from that starting address: $$\boxed{\text{range}=0\text{x4200}\ \text{to}\ 0\text{x421F}}$$
3. Part (c) — minimum and maximum data-cache memory traffic for 100 byte reads. The data cache starts empty, and every miss fetches a full 16-byte block. Minimum: since a 16-byte block contains exactly 16 distinct byte positions, the best case is that all 100 reads target addresses within that same single block (repeatedly re-reading the same handful of bytes) — the first access misses and fetches the one 16-byte block, and every one of the remaining 99 reads then hits in that already-resident block, so only one block is ever fetched: $$\boxed{\text{minimum}=1\times16=16\ \text{bytes}}$$ Maximum: the worst case is that every one of the 100 reads targets a different, never-revisited 16-byte block (e.g. a stride of 16+ bytes with no address ever repeated), so every single read misses and triggers its own 16-byte fetch: $$\boxed{\text{maximum}=100\times16=1{,}600\ \text{bytes}}$$