Question 4 of 6: Set-Associative Cache Indexing, Address Decoding, and Registers vs. Caches

Question 4: Set-Associative Cache Indexing, Address Decoding, and Registers vs. Caches (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) A 4GB byte-addressable address space (32 address bits, part 1(c)); a 32KB, 2-way set-associative cache with 32-byte blocks. (b) The same cache; a block resident in set 0x1 with tag 0x20. (c)–(d) General cache-design questions (motivation for caches vs. more registers; motivation for block size $>$ typical access size).

Find. (a) The address breakdown (tag/index/offset field widths) and how a location is indexed. (b) The full range of byte addresses the tagged block covers. (c) Why caches exist, and the tradeoffs of using extra registers instead. (d) Why cache blocks are made larger than a typical memory access.

Approach. (a) block count $=$ cache size / block size, set count $=$ block count / associativity, then index/offset/tag bits follow from $\log_2$ of each field's size, summing to the 32-bit address. (b) reconstruct the full address by placing the given tag and set index into their bit positions and letting the block offset range over all values.

1. Part (a) — how the cache is indexed. Number of blocks in the cache: $32\text{KB}/32\text{B}=1024$ blocks. At 2-way associativity, blocks are grouped into sets of 2, giving $1024/2=512$ sets. That requires $\log_2(512)=9$ index bits to select a set, and each 32-byte block needs $\log_2(32)=5$ offset bits to select a byte within it. With a 32-bit address (from part 1(c)), the remaining bits form the tag: $$\text{tag bits} = 32-9-5=18$$
   Fig. Q4 — 32-bit address breakdown for the 32KB, 2-way set-associative, 32-byte-block cache.
   Every address is indexed by extracting its middle 9 bits to pick one of the 512 sets, then comparing its top 18 bits (the tag) against the tags of both ways stored in that set to find a hit; the low 5 bits select the specific byte within the 32-byte block. $\boxed{\text{18-bit tag}\ |\ \text{9-bit set index}\ |\ \text{5-bit block offset}}$.
2. Part (b) — address range of the tagged block. Reassembling a full address from the given tag (0x20) and set index (0x1), with the offset field ranging over all $2^5=32$ values, using the field layout from part (a) (tag in the high 18 bits, index in the next 9, offset in the low 5): $$\text{base address} = (0\text{x20}\ll14)\ |\ (0\text{x1}\ll5) = 0\text{x80000}\ |\ 0\text{x20} = 0\text{x80020}$$ $$\text{end address} = 0\text{x80020} + (2^5-1) = 0\text{x80020}+31 = \boxed{0\text{x8003F}}$$ So the block spans addresses $\boxed{0\text{x80020}\text{ through }0\text{x8003F}}$ inclusive (32 consecutive bytes, as expected of a 32-byte block).
3. Part (c) — why caches instead of just more registers? Caches exist to bridge the large and growing gap between CPU speed and main-memory (DRAM) speed: a cache is fast, on-chip, and automatically retains recently/nearby-accessed data, cutting the AVERAGE memory access time far below a DRAM access without the programmer or compiler having to manage it explicitly. Registers are even faster than a cache, so it is natural to ask: why not just add more of them? Pros of more registers: a register access is faster than even an L1 cache hit (no tag comparison, no set lookup) and gives the compiler direct, guaranteed-fast storage for the values it chooses to keep there. Cons of more registers: registers must be explicitly named and allocated by the compiler/programmer at compile time out of a small, fixed set visible in the instruction encoding (widening the register file also costs encoding bits, as in Question 2) — the compiler cannot know at compile time which memory locations a program will access at run time (data-dependent array indices, pointers, dynamically sized structures), so no number of registers can hold "whatever the program will need" the way a cache automatically captures whatever was recently touched. A cache is transparent (works for any address, decided at run time) and can be made far larger (KB–MB) than any practical register file (tens of registers) without touching the instruction encoding. Caches complement, rather than replace, registers: registers give the compiler explicit control over a tiny, fastest tier; caches transparently capture temporal/spatial locality over the much larger set of addresses the compiler cannot pin down in advance.
4. Part (d) — why cache blocks are larger than a typical access. A larger block exploits spatial locality: programs overwhelmingly access memory in small clusters (consecutive instructions, array elements, structure fields), so fetching a whole 32-byte (or larger) neighbourhood around a requested word, instead of just the requested up-to-8 bytes, brings in data that is very likely to be referenced again soon — converting several future accesses into cache hits after paying for only one miss. This amortizes the fixed per-miss overhead (address decode, bus arbitration, DRAM row activation) over more useful bytes, and DRAM itself is naturally organized to deliver a whole "row" or burst efficiently, so fetching a larger block is not much slower per byte than fetching a small one. Blocks are sized well above the typical single-instruction access size because the cost of a miss is dominated by fixed overhead, not by the number of bytes transferred, so a larger block converts that fixed cost into many more future hits via spatial locality — up to the point where blocks become so large they evict useful data ("pollution") faster than they capture new locality.