Lecture 15: Dataflow, Superscalar Execution and Branch Prediction

What this lecture covers

This lecture closes out the out-of-order execution topic from the prior two lectures, then moves through two more mechanisms for extracting instruction-level parallelism: dataflow-style execution at the ISA level (and why it failed there while succeeding inside the microarchitecture) and superscalar execution, which fetches, decodes, and retires multiple instructions per cycle. It ends by starting a new topic, branch prediction, motivating it with a worked example showing how sharply performance degrades as prediction accuracy drops, and introducing branch target buffers and simple static prediction schemes.

After watching, you should be able to summarize why out-of-order execution is described as "restricted dataflow," explain why superscalar and out-of-order execution are orthogonal design choices, compute how misprediction penalty scales with pipeline depth and issue width, and describe the difference between static and profile-based branch direction prediction. The lecture ends mid-topic and continues into the next lecture.

Key ideas

• Restricted dataflow: out-of-order execution behaves like a dataflow machine, but only within the bounds of the instruction window (reservation stations plus reorder buffer), not across the entire program.
• Physical register file design: modern out-of-order processors use one physical register file for all values (avoiding replication in reservation stations and the reorder buffer) plus two register maps, a front-end map for renaming and an architectural map for precise state.
• Latency tolerance vs. complexity trade-off: out-of-order execution lowers CPI by keeping functional units busy, but the added dependence-checking logic can lengthen the critical path and increase clock cycle time, so the net benefit is not automatic.
• Superscalar execution: fetching, decoding, executing, and retiring multiple (N) instructions per cycle; dependence checking must now happen "vertically," across concurrently fetched instructions, in addition to the "horizontal" checking out-of-order execution already does across time.
• Orthogonality of superscalar and out-of-order: a processor can be in-order scalar, in-order superscalar, out-of-order scalar (rare in practice), or out-of-order superscalar; most modern high-performance processors combine superscalar with out-of-order.
• Register renaming logic in superscalar machines: because multiple instructions are renamed in the same cycle, renaming logic must be sequentially chained across them, which can become a critical-path bottleneck and drives heavy pipelining in modern designs.
• Misprediction cost scales with pipeline depth and issue width: a wrong branch prediction wastes roughly (pipeline depth) x (issue width) instruction slots, so even a small drop in prediction accuracy causes a large drop in effective IPC.
• Branch target buffer (BTB): a cache, indexed by PC, that stores previously computed branch target addresses (and implicitly, whether a PC is a branch) so the target does not need to be recomputed each time.

Walkthrough

Wrapping up out-of-order execution (7:46)

The lecture reviews the four requirements for out-of-order execution covered previously (linking producer to consumer via renaming, buffering in reservation stations, tracking readiness via tag broadcast, and dispatch via wakeup-and-select), and restates that out-of-order execution is a restricted form of dataflow, limited by instruction window size. It reiterates the modern design with a single physical register file plus front-end and architectural register maps, used to avoid replicating values, and connects this to the Intel Pentium Pro.

Why out-of-order execution helps, and its costs (14:55)

Class discussion establishes that out-of-order execution's main benefit is latency tolerance: independent instructions keep functional units busy while a long-latency operation (for example, a cache miss) is still in flight, which matters more as instruction window size grows. The lecture balances this against disadvantages: higher hardware complexity, longer critical paths from dependence-checking logic, and the risk that a lower CPI is offset by a longer clock cycle time, so the net effect on execution time is a genuine design trade-off.

Dataflow at the ISA level vs. the microarchitecture level (20:01)

The lecture reviews the earlier ISA-design discussion of control-flow versus dataflow instruction sets. Dataflow at the ISA level exposes parallelism well but has largely failed in practice because it lacks precise-state semantics, making debugging and exception handling extremely difficult, and because tag-matching hardware can be costly. In contrast, implementing restricted dataflow inside the microarchitecture (as out-of-order execution does) while keeping a sequential, control-flow ISA has been very successful; dataflow-to-FPGA mapping is mentioned as a more recent, successful use of dataflow ideas for accelerating applications like machine learning.

Superscalar execution: fetching multiple instructions per cycle (31:08)

Superscalar execution means fetching, decoding, executing, and retiring N instructions per cycle. The lecture stresses that superscalar and out-of-order execution are orthogonal: a machine can combine in-order or out-of-order dispatch with scalar or superscalar width, though out-of-order scalar machines are rare in practice because the dependence-checking hardware needed for out-of-order execution pairs naturally with superscalar width. An in-order superscalar MIPS datapath example shows the doubled hardware required (two fetch ports, doubled register file ports, two ALUs, two data memory ports) and works through code examples showing how dependent instructions between the two fetched slots can cut the achieved IPC well below the ideal of two, and how compiler reordering can sometimes recover it.

Costs of superscalar and real designs (42:16)

The lecture lists superscalar's costs: dependence checking must now happen across concurrently fetched instructions ("vertically"), register renaming logic must be chained sequentially across instructions issued in the same cycle, and both add to critical path length and hardware cost. It closes this section with examples of real superscalar designs, including an early Intel Pentium, an AMD core translating instructions into micro-operations for a six-wide pipeline, and a reverse-engineered estimate of Apple M1 as an eight-wide superscalar out-of-order design.

Motivating branch prediction (1:04:43)

The lecture turns to control dependence: after fetching a branch, the processor does not know the next fetch address until the branch resolves, and different branch types (conditional, unconditional jump, call/return, indirect) vary in how hard they are to predict. A detailed worked example shows the cost of misprediction: with a 20-stage pipeline and 5-wide superscalar fetch, 100% accurate prediction gives an ideal IPC of 5, but dropping to 99% accuracy reduces IPC to about 4, and dropping further to 90% accuracy reduces IPC to only about 1.6, illustrating why even small accuracy losses matter enormously at modern pipeline depths and issue widths.

Basic approaches and static prediction schemes (1:12:53)

The lecture surveys ways to handle control dependence: stalling (rejected as a non-solution), branch prediction (the main topic), delayed branching, fine-grained multithreading (revisited as a way to hide branch latency by scheduling instructions from other threads, as used in GPUs), predicated execution, and speculative multi-path fetching. It then introduces the simplest predictor, always guessing PC+4, and how compilers can improve its accuracy by reordering control flow graphs so the likely path is the fall-through path. The lecture ends by introducing the branch target buffer (a PC-indexed cache of branch targets) and static direction-prediction schemes (always not-taken, always-taken, backward-taken/forward-not-taken, and profile-guided prediction), with the topic to continue in the next lecture.

Before you watch

• Watch the previous two lectures on precise exceptions and out-of-order execution in this course, since the first third of this lecture directly reviews and depends on the reorder buffer, register renaming, and reservation-station concepts built there.
• Recall the course's earlier discussion of control-flow versus dataflow instruction set design, since this lecture revisits that trade-off explicitly.
• Be familiar with basic pipeline hazard terminology (stalls, bubbles, forwarding) from the pipelining lectures, since the superscalar and branch-prediction analyses reuse it.

Check your understanding

1. Why is out-of-order execution described as a "restricted" form of dataflow rather than full dataflow?
2. Why has dataflow been successful as a microarchitecture implementation technique but largely unsuccessful as an ISA-level programming model?
3. Why are superscalar execution and out-of-order execution considered orthogonal design choices, and why are out-of-order scalar processors rare?
4. In the worked example, why does dropping branch prediction accuracy from 99% to 90% cause such a large drop in IPC, given a 20-stage, 5-wide pipeline?
5. What does a branch target buffer store, and why is a separate direction predictor still needed alongside it?