Digital Design & Computer Architecture - Problem Solving II (Spring 2022)
•February 24, 2026
0
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.
Original Description
Digital Design and Computer Architecture, ETH Zürich, Spring 2022 (https://safari.ethz.ch/digitaltechnik/spring2021/doku.php?id=start)
Problem Solviing II -- Solutions to Some Homework Problems
Lecturer: Professor Onur Mutlu (https://people.inf.ethz.ch/omutlu/)
Date: July 15, 2022
Questions:
00:00:00 - Branch Prediction I (HW5, Q1)
00:15:08 - Systolic Arrays I (HW5, Q8)
00:24:40 - GPUs and SIMD I (HW6, Q4)
00:33:24 - Tracing the Cache (HW7, Q3)
00:55:26 - Cache Performance Analysis (HW7, Q5)
01:15:28 - Memory Hierarchy (HW7, Q6)
01:32:21 - Prefetching (HW7, Q11)
01:38:54 - Vector Processing III (HW6, Q3, Spring 2021)
02:05:07 - GPUs and SIMD III (HW6, Q8, Spring 2021)
02:24:34 - GPUs and SIMD IV (HW6, Q9, Spring 2021)
02:38:55 - Reverse Engineering Caches II (HW7, Q3, Spring 2021)
Recommended Reading:
====================
A Modern Primer on Processing in Memory
Intelligent Architectures for Intelligent Computing Systems
RowHammer: A Retrospective
Fundamentally Understanding and Solving RowHammer
RECOMMENDED LECTURE VIDEOS & PLAYLISTS:
========================================
Computer Architecture Fall 2021 Lectures Playlist:
Digital Design and Computer Architecture Spring 2021 Livestream Lectures Playlist:
Featured Lectures:
Interview with Professor Onur Mutlu:
The Story of RowHammer Lecture:
Accelerating Genome Analysis Lecture:
Memory-Centric Computing Systems Tutorial at IEDM 2021:
Intelligent Architectures for Intelligent Machines Lecture:
Computer Architecture Fall 2020 Lectures Playlist:
Digital Design and Computer Architecture Spring 2020 Lectures Playlist:
Public Lectures by Onur Mutlu, Playlist:
Computer Architecture at Carnegie Mellon Spring 2015 Lectures Playlist:
Rethinking Memory System Design Lecture @stanfordonline :
0
Comments
Want to join the conversation?
Loading comments...