Digital Design & Computer Architecture - Problem Solving II (Spring 2022)
Why It Matters
Accurate branch prediction and efficient systolic‑array designs are critical for maximizing CPU throughput and accelerating matrix‑intensive workloads such as AI inference.
Key Takeaways
- •Local correlation exists only for the outer for-loop branch (B1).
- •Global correlation ties B4 (multiple of six) to B2 and B3.
- •Two-bit global history predictor uses four pattern entries for branch outcomes.
- •Probability of a branch being taken derived from random value distribution 1‑6.
- •Systolic PE computes P=M, Q=N, R=R+M·N each cycle.
Summary
The video walks through a textbook‑style problem on branch prediction and then shifts to designing a systolic array for matrix multiplication, illustrating two core concepts in computer architecture.
It defines locally correlated branches—where knowledge of a previous iteration predicts the current one—and shows that only the outer for‑loop (B1) meets this criterion because its iteration count is deterministic. Globally correlated branches are identified by mathematical relationships: if the condition “multiple of six” (B4) is true, then the “multiple of two” (B2) and “multiple of three” (B3) conditions must also be true, establishing a bidirectional correlation.
The instructor demonstrates a two‑bit global history register feeding a four‑entry pattern history table, updating counters by +1 for taken and –1 for not‑taken, and works through the expected counter value after 120 iterations using a uniform 1‑6 random distribution. He then derives the processing‑element equations for a systolic array—P equals input M, Q equals input N, and R accumulates the product M·N—showing how to populate 30 input slots to compute a 3×3 matrix product.
Understanding these correlations helps designers choose appropriate branch predictors, directly affecting pipeline efficiency, while the systolic‑array mapping provides a concrete example of how dataflow architectures can be programmed for high‑throughput linear algebra, a cornerstone of modern AI workloads.
Comments
Want to join the conversation?
Loading comments...