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^{32}$ byte) address space, 128KB, 4-way set-associative cache, 64-byte blocks. (b) set index 0x10, tag 0x01. (c) 10 sequential byte reads into an initially-empty 32-byte-block data cache; instruction fetches always hit.

Find. (a) how the address splits into tag/index/offset fields. (b) the hexadecimal address range that set/tag combination covers. (c) the minimum and maximum bytes the data cache reads from memory over the 10 accesses.

Approach. (a) derive block count from cache size and block size, then set count from block count and associativity, then take base-2 logs for the field widths. (b) reconstruct the address from tag/index/offset. (c) bound the miss count by best-case (all 10 in one block) and worst-case (each in a different block) locality.

1. Part (a) — address field widths. Number of blocks in the cache: $$\text{blocks}=\frac{128\text{KB}}{64\text{B}}=\frac{131072}{64}=2048\ \text{blocks}$$ 4-way set-associative means 4 blocks share each set, so: $$\text{sets}=\frac{2048}{4}=512\ \text{sets}$$ Field widths follow from these counts and the 32-bit ($2^{32}=4$GB) address: $$\text{offset bits}=\log_2(64)=6,\quad\text{index bits}=\log_2(512)=9,\quad\text{tag bits}=32-9-6=\boxed{17}$$ So each 32-bit address splits as [17-bit tag][9-bit set index][6-bit block offset], low to high: the low 6 bits select a byte within the 64-byte block, the next 9 bits select one of 512 sets, and the remaining 17 bits are compared against the tags of that set's 4 ways.
2. Part (b) — address range for set 0x10, tag 0x01. Reassembling the address from its fields (tag in the high 17 bits, set index in the next 9, offset spanning the low 6): $$\text{base}=(\text{tag}\ll15)\ |\ (\text{set}\ll6)=(0x01\ll15)+(0x10\ll6)=32768+1024=33792=0x8400$$ The 64-byte block spans offsets 0 through 63 from that base: $$\boxed{0x8400\ \text{to}\ 0x843F}$$
3. Part (c) — min/max data-cache memory traffic for 10 byte reads. Each cache miss pulls in one full 32-byte block; a hit costs no memory traffic. Minimum: if all 10 byte addresses happen to fall within the same 32-byte-aligned block, the first access misses (fetching that one block) and the remaining 9 addresses are hits within the block already resident, so only one block is ever fetched: $\boxed{32\text{ bytes}}$. Maximum: if each of the 10 addresses falls in a different, never-before-accessed 32-byte block (worst-case, zero spatial reuse), every access misses and fetches its own block: $10\times32=\boxed{320\text{ bytes}}$.