Question 3 of 6: Cache Organization and Performance

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

Find. (a) how the address splits into tag/index/offset fields; (b) how miss rate is expected to vary with block size at fixed total capacity, with a diagram; (c) whether a cache always improves performance.

Approach. (a) derive offset bits from the block size, the number of sets from capacity ÷ (block size × associativity), and the tag from what is left of the 32-bit address; (b)/(c) reason from the locality-of-reference tradeoff a cache exploits.

1. Part (a) — address indexing. The 64-byte block needs $$\text{offset bits}=\log_2(64)=6$$ to select a byte within a block. The number of sets is the capacity divided by (block size × ways): $$\text{sets}=\frac{32\text{KB}}{64\text{B}\times2}=\frac{32768}{128}=256\ \Rightarrow\ \text{index bits}=\log_2(256)=8.$$ The remaining high-order bits of the 32-bit address are the tag: $$\text{tag bits}=32-8-6=\boxed{18}.$$ So a physical address decomposes as [31:14] tag (18b) | [13:6] set index (8b) | [5:0] block offset (6b).
2. Part (b) — miss rate vs. block size at fixed capacity. With capacity held constant, increasing block size at first LOWERS the miss rate: a bigger block pulls in more of a program's spatially-local neighbours per miss, so fewer compulsory misses are paid for streaming/sequential access patterns. But because capacity is fixed, a bigger block also means FEWER blocks (fewer sets/ways) fit in the cache — past some point the loss of distinct cached blocks causes more conflict and capacity misses, and large blocks increasingly fetch bytes the program never touches before the block is evicted ("cache pollution"). The net expected shape is a "bathtub" (U-shaped) curve: miss rate falls, bottoms out at a moderate block size (commonly tens to a couple hundred bytes in real caches), then rises again as blocks get very large.
3. Part (c) — does a cache always help? No. A cache's hit-check itself costs a small, non-zero amount of logic/latency on every access, so its benefit is entirely conditional on hits recovering that cost by avoiding the much larger main-memory access — for a workload with poor locality (e.g. a single streaming pass over data far larger than the cache, with no reuse) almost every access misses, and the design pays the lookup overhead on every access while gaining almost none of the intended latency reduction. If the working set exceeds the cache's capacity and is accessed with a pattern that defeats the replacement policy, the cache can thrash (evict-then-immediately-need) and add overhead without amortized benefit. In multiprocessor systems, keeping caches coherent (invalidations from false sharing) can add traffic a cache-less shared-memory design would not incur. So: a cache's benefit is workload-dependent, not guaranteed — it helps whenever the workload has meaningful temporal/spatial locality, and can add pure overhead when it does not.