Question 3 of 6: Cache Organization and the Register/Cache Tradeoff

Question 3: Cache Organization and the Register/Cache Tradeoff (20 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, 32-bit address) byte-addressable machine; a 64KB, 4-way set-associative cache with 32-byte blocks.

Find. (a) the tag/index/offset split of a 32-bit address for this cache. (b) the address range of the block found in set 0x3, tag 0x10. (c) why caches exist at all, and how trading them for more registers would compare.

Approach. (a) derive offset bits from block size, set count from capacity÷(block size×ways), and the tag from what's left of 32 bits. (b) reassemble a concrete address from the given tag and set fields. (c) reason from the cost/latency/locality tradeoff that motivates a memory hierarchy.

1. Part (a) — address indexing. The 32-byte block needs $$\text{offset bits}=\log_2(32)=5$$ bits to select a byte within a 32-byte block. The number of sets is capacity divided by (block size×ways): $$\text{sets}=\frac{64\text{KB}}{32\text{B}\times4}=\frac{65536}{128}=512\ \Rightarrow\ \text{index bits}=\log_2(512)=9.$$ The remaining high-order bits form the tag: $$\text{tag bits}=32-9-5=\boxed{18}.$$ So a 32-bit physical address decomposes as [31:14] tag (18b) | [13:5] set index (9b) | [4:0] block offset (5b).
2. Part (b) — reassembling the address range. The block's full address is built by concatenating tag, index, and offset (offset ranging over the whole block): $$\text{base}=(\texttt{tag}\ll14)\ |\ (\texttt{set}\ll5)=(\texttt{0x10}\ll14)\ |\ (\texttt{0x3}\ll5)=\texttt{0x40000}+\texttt{0x60}=\texttt{0x40060}.$$ The block spans its own 32 bytes from there: $$\boxed{\texttt{0x40060}\ \text{to}\ \texttt{0x4007F}}\quad(32\ \text{bytes}).$$
3. Part (c) — why cache at all, and registers instead? Main memory (DRAM) is orders of magnitude slower to access than the processor's clock cycle, so without a cache nearly every instruction fetch and data access would stall the pipeline for many cycles. A cache exploits locality of reference — programs repeatedly touch the same (temporal) and nearby (spatial) memory locations — by holding a small, fast copy of recently/likely-used data close to the core, so most accesses complete in a couple of cycles instead of a full memory round trip.
   Instead, use MORE registers? Registers are even faster than any cache level (zero-cycle or single-cycle access, no tag compare, no hierarchy lookup) and consume less energy per access. Pros of a bigger register file: faster access to the values it holds, no tag/index overhead, and the compiler decides exactly what lives there (no cache-replacement guesswork). Cons: registers are explicitly named in the instruction encoding (each extra register costs opcode/operand bits, as in Q1's opcode-space tradeoff) so the count is capped by instruction width and compiler/allocator complexity; a register file's size is also fixed at compile time per architecture generation, whereas a cache transparently holds whatever data a running program actually needs, adapting automatically to different programs' working sets without recompilation; and registers cannot hold more data than fits in the encodable register-name space, while cache capacity can be grown independently of the ISA. Caches and registers are complementary, not substitutes: registers give the fastest possible access to a compiler-chosen handful of values, while a cache transparently accelerates the much larger, dynamically-varying set of memory locations a program actually revisits.