Lecture 12: Pipelined Processor Design II

What this lecture covers

This lecture finishes building the five-stage pipelined MIPS processor introduced in the previous session and answers the two questions a working pipeline must solve: how do you handle instructions that depend on each other, and how do you handle the fact that you don't know which instruction to fetch next until a branch is resolved? It walks through the pipeline datapath and control design first, then spends most of the lecture on data dependencies (flow, anti-, and output) and how hardware detects and resolves them through stalling and forwarding, before introducing control dependencies and basic branch prediction.

The lecture continues directly from the previous one, where the datapath was first divided into fetch, decode, execute, memory, and write-back stages. By the end, you can explain why a pipeline that only handles independent instructions is not yet correct, describe how stalling and forwarding fix data dependencies, and explain why branches create a similar problem for the program counter.

Key ideas

• Pipeline design process: build the datapath first by dividing a single-cycle design into stages and adding pipeline registers, then design control logic that reuses the single-cycle control signals but delays them to the stage where each is needed.
• Propagating signals: any data or control signal needed in a later stage must be carried forward through the pipeline registers between stages, not regenerated; using a signal from the wrong instruction produces wrong results.
• Ideal pipeline assumptions violated: real instruction pipelines lack identical operations, independent operations, and uniformly partitionable work, causing external fragmentation (idle stages) and internal fragmentation (uneven stage latency).
• Resource contention: when two pipeline stages need the same hardware (such as the register file), you either duplicate the resource or stall one of the instructions; a common trick writes to the register file in the first half of a cycle and reads in the second half.
• Three types of data dependence: flow (true, read-after-write) dependence must always be respected; anti- (write-after-read) and output (write-after-write) dependence are artifacts of limited register names and can be eliminated with more registers or renaming.
• Interlocking: hardware or software must detect dependences before they cause wrong results, either with a scoreboard (a valid bit per register) or combinational comparison logic that checks source registers against in-flight destination registers.
• Data forwarding (bypassing): instead of waiting for a value to reach the register file, the pipeline can route a produced value directly from a later pipeline stage back to an earlier stage that needs it, reducing stalls.
• Control dependence: because instructions after a branch are fetched before the branch is resolved, the pipeline must predict the next PC (commonly "always not taken") and flush incorrectly fetched instructions on a misprediction.

Walkthrough

Designing the pipeline datapath (7:33)

The lecture restates the design process: start from the single-cycle datapath, decide how many stages to divide it into (five here: fetch, decode, execute, memory, write-back), and add pipeline registers between stages so that work done in one stage in one cycle doesn't interfere with another stage in the same cycle. It notes this choice of stage count is itself a design decision, with real processors ranging up to around thirty stages, chosen to raise clock frequency.

Propagating data and control through pipeline registers (13:34)

Working through the datapath stage by stage, the lecture shows which values must be latched at each boundary: the fetched instruction and PC+4 out of fetch, register values and the sign-extended immediate out of decode, the ALU result and a directly-propagated second register (needed by stores) out of execute, and so on. Control points are identical to the single-cycle design, but each control signal must be routed into the specific pipeline register that carries it forward to the stage where it is actually used; a register-write signal, for example, must reach the write-back stage, not be read out earlier.

Two problems: dependencies and pipeline stalls (25:38)

The lecture identifies that a correctly wired datapath and control unit are not sufficient: an ideal pipeline requires identical, independent, and uniformly divisible operations, and real instruction pipelines violate all three. This causes external fragmentation (an add instruction doing nothing useful in the memory stage) and internal fragmentation (stages forced to share a clock cycle length even though their actual work differs). The lecture lists the general causes of pipeline stalls: resource contention, data and control dependencies, and long-latency multi-cycle operations, defining a stall as the pipeline being forced to stop moving to preserve correctness.

Resource contention and the half-cycle register trick (31:43)

When two stages need the same resource, such as a single-ported register file being read in decode and written in write-back, the lecture presents two fixes: duplicate the resource (as with separate instruction and data memories) or stall one of the contending stages. It then describes a common register-file design where writes happen in the first half of a clock cycle and reads happen in the second half, allowing an instruction to read a value written earlier in the same cycle without adding a stall.

Data dependencies: flow, anti-, and output (36:50)

The lecture distinguishes true flow dependence, where one instruction consumes a value produced by an earlier one, from anti-dependence (a later instruction writes a register an earlier instruction still needs to read) and output dependence (two instructions write the same register). It explains that anti- and output dependence exist only because of a limited number of architectural register names, not because of any real data relationship, and can be eliminated by writing to destinations only in the last pipeline stage and in program order.

Detecting dependences: stalling, scoreboarding, and combinational logic (46:50)

The lecture covers interlocking, the general term for detecting dependences to guarantee correct execution, contrasting software-based reordering (including inserting no-ops) with hardware-based detection. It describes scoreboarding, where each register has a valid bit cleared when an in-flight instruction will write it, and combinational dependence-check logic, where comparators check a decoding instruction's source registers against the destination registers of instructions later in the pipeline. It also explains how a stall is implemented mechanically: disabling the PC and earlier pipeline registers from latching, while inserting a bubble (a cleared, no-op pipeline register) into the stage that follows.

Data forwarding and branch resolution (1:21:48)

Instead of always stalling until a value reaches the register file, the lecture introduces forwarding (bypassing): routing a value directly from the pipeline register at the end of the execute or memory stage back to the ALU input of a dependent instruction. It notes one case forwarding cannot fully solve without a stall, a load immediately followed by a dependent instruction, since the loaded value is not available until after the memory stage. The lecture then turns to control dependence: because the next instruction is fetched before a branch is resolved, the pipeline predicts (by default, always not-taken) and must flush incorrectly fetched instructions on a misprediction, with early branch resolution in the decode stage offered as one way to shrink the penalty at the cost of extra hardware and a longer critical path.

Before you watch

• Watch or review the previous lecture in this course, which builds the single-cycle-to-pipeline datapath conversion that this lecture continues from.
• Be comfortable identifying source and destination registers in MIPS instruction encodings, since dependence detection is built entirely around register names.
• Recall the earlier discussion of multi-cycle memory access and finite state machines, since the same wait/stall mechanism reappears here.

Check your understanding

1. Why are anti-dependence and output dependence considered "fake" compared to flow dependence, and how can they be eliminated?
2. Explain how the combinational dependence-check logic decides whether a decoding instruction must stall.
3. Why can't forwarding alone resolve the dependence between a load and an immediately following dependent instruction?
4. What does it mean to insert a "bubble" into a pipeline stage, and which pipeline registers are disabled to create one?
5. Why does "always not taken" branch prediction cause instructions to be flushed, and how does early branch resolution reduce the number flushed?