Lecture 28: Problem Solving III (Branch Prediction to Caches)

What this lecture covers

This is a problem-solving session where teaching assistants work through past homework and exam questions rather than presenting new material. It assumes you already know the underlying concepts from the course's branch prediction, GPU/SIMD, vector processor, and cache lectures, and instead shows how to apply them under exam conditions: reading a question carefully, identifying what data the question actually gives you, and reasoning step by step to a numeric or descriptive answer.

The problems progress from branch prediction correlation, through systolic array programming and GPU SIMD utilization, to vector processor timing with and without chaining, and finally a long sequence of cache problems: reconstructing cache contents from hit/miss traces, comparing replacement policies, and reverse-engineering an unknown cache hierarchy from measured access latencies. After watching, you should be able to set up and solve similar quantitative problems yourself, and know which formulas and reasoning patterns each problem type requires.

Key ideas

• Locally vs. globally correlated branches: a branch is locally correlated if its own past outcomes predict its next outcome (like a loop-bound branch); it's globally correlated if another branch's outcome predicts it (like a "multiple of six" branch implying "multiple of two" and "multiple of three").
• Systolic array programming: each processing element in the example array just passes its M and N inputs through as P and Q, while accumulating R = R + M * N; correctness comes entirely from staggering when each input value enters the array so that matching row and column elements arrive at the same cycle.
• SIMD/warp utilization: computed as active threads divided by total threads across all instructions and warps; utilization drops whenever threads in the same warp diverge on an if and take different paths, since a warp must issue both paths' instructions.
• Vector chaining: without chaining, a dependent vector instruction must wait for the entire producing instruction to finish; with chaining, it can start as soon as the first output element is available, cutting the total latency substantially.
• Reconstructing cache sets from a miss trace: with only a sequence of accesses and which ones missed, you can infer which cache blocks share a set by tracking which access must have evicted a previously present block.
• Stride vs. next-line prefetching: a stride prefetcher is accurate and effective only for constant, learnable access strides; a next-line prefetcher can work well even before a stride is learned, but neither helps with irregular, data-dependent access patterns, where techniques like run-ahead execution are more suitable.
• Reverse-engineering a cache hierarchy: plotting average access latency against a scanned array size (with a fixed stride) produces step increases exactly at each cache level's capacity; the flat regions in between reveal associativity, and stepping the stride reveals block size and replacement policy.

Walkthrough

Branch correlation analysis (0:00)

The first problem gives a loop containing three nested if statements testing whether an array element is a multiple of two, three, or six. The TA works out that only the loop-control branch is locally correlated (because the loop trip count is fixed), while the "multiple of six" branch is globally correlated with the "multiple of two" and "multiple of three" branches, since any multiple of six is necessarily a multiple of both. The second part extends this to a two-bit global history predictor: using a simplified value range of 1 to 6 for the random array elements, the TA computes the probability-weighted contribution of each branch outcome to a saturating counter after many iterations, combining fractions like 3/6 and 1/6 to get a final counter value.

Systolic array matrix multiplication (15:00)

Given a 3x3 grid of processing elements, each with inputs M and N, outputs P and Q, and an accumulator R, the task is to derive the per-element equations and fill in which input matrix elements enter the array on which cycle. The TA reasons that P and Q are simple pass-throughs of M and N, while R accumulates the running dot product R = R + M*N. The harder part is scheduling: elements of matrix A must be fed in one row at a time so they reach each processing element in the same cycle as the matching column element of matrix B, which requires inserting zero cycles for elements that need to travel further into the array.

GPU SIMD utilization problems (24:30)

Several related problems ask for the number of warps needed to run a loop, and the resulting SIMD utilization given specific data patterns. The TA repeatedly applies the same method: divide total threads by warp size (rounding up) for the warp count, then reason instruction by instruction about how many threads in each warp actually execute each instruction, given divergent if branches. Later parts ask for the conditions on the input array that produce maximum or minimum utilization, and work backward from a given utilization fraction (such as 134/320) to figure out exactly how many threads per warp take each path.

Vector processor timing with and without chaining (33:13)

For a vector ISA with pipelined load, store, add, multiply, and divide instructions, the TA works out the minimum number of memory banks needed to avoid stalls at different strides, then computes the total cycle count for a chain of load, add, multiply, and store instructions on an in-order machine. The same code is then re-timed assuming the processor supports chaining, showing how a dependent instruction can start as soon as the first result element is ready rather than waiting for the whole producing instruction to complete, substantially shortening the total latency.

Tracing cache misses and replacement policies (1:24:24)

Given only a sequence of memory accesses and which ones caused a cache miss, the TA reconstructs which of eight contiguous memory blocks map to the same cache set, first for a direct-mapped cache, then for fully associative and two-way set-associative caches, using LRU and FIFO reasoning to explain each hit or miss. A later related problem determines a cache's block size, associativity, and replacement policy purely from given hit rates on a specified access sequence, by testing candidate block sizes and associativities against the data until only one is consistent. Later sections extend this into hardware prefetching, comparing stride, next-line, and run-ahead-execution prefetchers by computing their accuracy and coverage on regular and irregular access patterns.

Reverse-engineering a cache hierarchy from latency traces (2:09:39)

The final long problem uses two microbenchmarks that access an array with a chosen stride and size while timing each access. By reading step changes in a latency-versus-array-size plot, the TA identifies L1 and L2 cache sizes (where latency jumps from a hit latency to a miss latency), infers block size from how many consecutive accesses share a latency, and infers associativity from the largest stride and range that still avoids extra misses. A companion problem works backward from given hit rates on an addressed sequence to determine an unknown cache's block size, associativity, and total size by testing candidate configurations, and a final example determines whether a two-level cache uses LRU or FIFO replacement based on which address remains cached after a sequence of conflicting accesses.

Before you watch

• Review the course's branch prediction lecture, especially the distinction between local and global history predictors.
• Be comfortable with GPU/SIMD execution and warp divergence, covered in the GPU and SIMD lectures earlier in this course.
• Know the basics of vector processor pipelines, including instruction latency and chaining.
• Review cache fundamentals: associativity, set indexing, and the LRU and FIFO replacement policies, before the cache-heavy second half of the session.

Check your understanding

1. Why is a branch that checks "multiple of six" globally correlated with branches checking "multiple of two" and "multiple of three," but not locally correlated with itself?
2. In the systolic array example, why must matrix A's elements be fed in one row at a time while matrix B's elements are fed in one column at a time, with staggered zero cycles?
3. How does adding chaining to a vector processor change when a dependent instruction can start, and why does this reduce total execution time?
4. Given only a sequence of cache accesses and which ones missed, how can you determine which memory blocks map to the same cache set without knowing the actual addresses?
5. Why does a stride prefetcher fail on an access pattern with no constant address difference, and what alternative technique can still help in that case?