L1 Associativity Versus a 32 KB Stride in a Column-Wise Kernel
A signal-processing kernel walks a 64 MB array declared as int a[4096][4096] column by column, and it touches only even-numbered rows, giving an effective stride of 32 KB. The core has a 32 KB, 64-byte-block L1 data cache, a unified 512 KB L2 with 12-cycle access, and 180-cycle main memory. Two L1 options are being compared: a direct-mapped 32 KB cache with a 1-cycle hit time and a measured 12% miss rate on this kernel, and an 8-way set-associative 32 KB cache with a 2-cycle hit time and a measured 2% miss rate. Of all L1 misses, 90% are served by L2. An architect suggests instead doubling L1 to 64 KB while keeping it direct-mapped, arguing that the extra capacity will absorb the stride conflict; another suggests leaving the cache alone and blocking the loop.
1. For both options give sets, index bits, tag bits, and explain what the 32 KB stride does to this stream.
Read the worked answer
A 64 B block gives 6 offset bits; assume 32-bit addresses and 512 lines in both cases.
- Direct-mapped: 512 sets → 9 index bits → tag = 32 − 9 − 6 = 17 bits.
- 8-way: 512 / 8 = 64 sets → 6 index bits → tag = 32 − 6 − 6 = 20 bits.
The stride is 32,768 B = 512 blocks. The set index advances by 512 mod (number of sets) per access:
- 512 sets: 512 mod 512 = 0 → every access lands in one set, which holds exactly one line. The first touch of a row misses and evicts the previous row, so essentially every access misses.
- 64 sets: 512 mod 64 = 0 → still one set, but eight ways hold eight distinct rows simultaneously, so seven of every eight accesses to a resident row hit.
This is the key insight the question is testing: associativity does not remove a stride conflict, it multiplies how many conflicting streams survive it. That is why the measured miss rate falls by roughly 6× (12% → 2%) rather than to zero - the 2% remainder is cross-row reuse lost once a ninth row arrives.
2. Compute AMAT for both configurations and decide. State the assumption you make about the L2 hit rate, and derive the break-even miss rate.
Read the worked answer
Miss penalty = L2 access + (L2 miss rate × memory access) = 12 + 0.1 × 180 = 30 cycles. AMAT = hit time + miss rate × penalty.
- Direct-mapped: 1 + 0.12 × 30 = 4.6 cycles
- 8-way: 2 + 0.02 × 30 = 2.6 cycles
The 8-way cache wins by ~43% despite the extra cycle of hit time: one cycle of latency buys 10 points of miss rate at 30 cycles each, i.e. 3 cycles saved for 1 spent. Break-even: 2 + m × 30 = 4.6 → m = 8.7%. As long as associativity keeps the miss rate under 8.7% - it measures 2% - the set-associative design is correct.
Assumptions worth stating in the answer: the 90% L2 hit rate is uniform across the two designs (it will not be in reality - an 8-way L1 passes fewer, more widely scattered lines to L2), and the extra tag-compare energy and area of eight ways are not being costed. If the measured miss rates had been 8% versus 6%, the direct-mapped cache would win, so the decision is driven by the measured gap, not by the slogan that associativity is better.
3. Evaluate the 64 KB direct-mapped proposal and the loop-blocking proposal.
Read the worked answer
64 KB direct-mapped: reject. 1024 sets → 10 index bits, tag 16 bits. The stride is still 512 blocks, and 512 mod 1024 = 512, so every access still maps to a single set - set 512 instead of set 0. The conflict is structural: doubling the number of sets does not help while the stride remains a multiple of the set count. All that is bought is double the area and a longer tag path for the same 12% miss rate; the 4096 rows do not become any more compatible with a 512-block stride.
Loop blocking: accept - it fixes the cause. The kernel needs reuse while a row is resident, so process a tile that fits the cache: 8 rows × 512 columns × 4 B = 16 KB, half of a 32 KB L1, leaving room for the streaming operand and stack. Within a tile the stride is contiguous in the fast dimension, so lines are reused in registers and L1 instead of being revisited 32 KB apart, and conflict misses largely vanish.
Ordering of remedies: fix the access pattern first (free, no silicon), add hardware only if the kernel cannot be restructured - associativity as above, or a small fully-associative victim cache that catches the lines the stride evicts. The architect's capacity argument and the blocking argument differ in kind: one adds storage to a conflict problem, the other removes the conflict.