Lecture 11: Multi-Cycle and Pipelined Processor Design

What this lecture covers

This lecture finishes the multi-cycle MIPS processor that the course started in the previous session and then opens the topic of pipelining. It answers a concrete design question: how do you build a processor where each instruction takes only as many clock cycles as it actually needs, instead of forcing every instruction to fit the worst-case cycle time of a single-cycle design? The lecture works through the datapath and control logic for load, store, R-type, and branch instructions one at a time, reusing a single ALU and a single memory across multiple cycles.

The lecture sits between the earlier single-cycle processor lectures and the pipelining sequence that follows. By the end, you can explain why a multi-cycle design lowers hardware cost but limits concurrency, describe how a finite state machine controls a multi-cycle datapath, and explain why pipelining is presented as the next logical step to recover the concurrency multi-cycle designs give up.

Key ideas

• Multi-cycle datapath: instructions are processed in stages held in registers (instruction register, ALU output register, memory data register), letting the design reuse one ALU and one memory across cycles instead of duplicating hardware for every instruction.
• Finite state machine control: each state asserts a specific set of control signals; the machine sequences from fetch through decode, address calculation, memory access, and write-back, taking a different number of states depending on the instruction.
• ALU reuse for PC increment: the design avoids adding a dedicated incrementer by routing the program counter through the same ALU used for address calculation, at the cost of extra states and multiplexers.
• Branch condition and target calculation: both share the single ALU, calculated in separate cycles rather than concurrently, which is a deliberate design trade-off different textbooks make differently.
• Microprogramming: control signals for each state (a micro-instruction) can be stored in a control store and sequenced by a microsequencer, turning processor design into a form of low-level programming that can later be patched.
• Multi-cycle memory handling: a "wait" condition lets the finite state machine stay in a memory-access state until the memory signals it is ready, rather than assuming memory always completes in one cycle.
• Limits of multi-cycle designs: hardware sits idle in most states (fetch logic idle during execute, most of the datapath idle during memory access), which motivates pipelining as a way to use that idle hardware for other instructions.
• Pipelining as overlap: processing multiple instructions concurrently, each in a different stage, increases instruction throughput without needing a faster clock, illustrated with an assembly-line and a laundry analogy.

Walkthrough

Recap: from single-cycle to multi-cycle (2:51)

The lecture opens by restating why single-cycle design is rejected: it forces every instruction into the same worst-case cycle time and duplicates hardware (adders, memories) so every operation can complete in one cycle. Multi-cycle design instead treats instruction processing as a finite state machine, letting each instruction take only the states it needs and letting the clock cycle time be set independently of any single instruction's total processing time. The lecture credits Maurice Wilks with the underlying microprogramming concept.

Building the multicycle load-word datapath (12:57)

Starting from a load-word instruction, the lecture builds the datapath state by state: fetch (using the PC to address memory, latching the result into an instruction register), register read (reading the base register into a pipeline register), address calculation (adding the base register to a sign-extended immediate in the ALU), memory access (looping the calculated address back into the same memory used for fetch, via a multiplexer), and write-back (writing the loaded value into the destination register). A separate step increments the PC by reusing the same ALU with extra multiplexers, since the design avoids adding a second adder.

Store, R-type, and branch instructions (22:08)

Store reuses almost the entire load datapath, adding only a second register read for the data to be written and asserting a memory-write signal instead of reading. R-type instructions read two registers, route both into the ALU, and add a multiplexer to choose between the ALU result and the memory result when writing back, since the destination register field differs from I-type encoding. Branch instructions (BEQ) reuse the ALU twice in separate cycles: once to compute whether two registers are equal (via subtraction and a zero flag) and once to compute the target address by adding PC+4 to a shifted, sign-extended immediate.

Multicycle control logic as a finite state machine (30:15)

With the datapath and its control signals defined, the lecture builds the controller as an explicit state machine: a fetch state, a decode state that reads registers "for free," an address-calculation state shared by load and store, and instruction-specific states after that (memory read and write-back for loads, memory write for stores, execute and write-back for R-type, a single combined state for branches). States are merged where possible to shorten common paths, and the lecture notes that adding a new instruction only requires adding datapath elements, control signals, and updating the relevant states.

Microprogramming and updatable control (44:24)

The lecture describes an alternative structuring of the same idea, based on the Patt and Patel textbook's appendix: control signals for each state are called a micro-instruction, stored in a control store (a small memory), and a microsequencer determines which micro-instruction runs next. This treats hardware design as a form of programming below the ISA level. The lecture connects this to real-world microcode patches, which let vendors fix bugs, add mitigations, or extend instructions in the field by changing the contents of the control store rather than the hardware itself, citing IBM's historical use of updatable "millicode."

From multicycle to pipelining (1:06:25)

The lecture turns to the limitations of the multi-cycle design: hardware cost grows, and most of the added hardware sits idle in any given state (fetch logic during decode, most of the datapath during a memory access). This motivates the core idea of pipelining: while one instruction uses a resource, use the otherwise-idle resources to process other instructions concurrently, increasing throughput without necessarily changing per-instruction latency. The idea is illustrated with a car-assembly-line analogy and, later, the Hennessy-and-Patterson laundry analogy, distinguishing throughput improvement from latency improvement and showing how a slow pipeline stage (the "dryer") becomes the bottleneck unless duplicated or sped up.

Building the pipelined datapath and control (1:28:37)

The lecture begins constructing a five-stage pipeline (fetch, decode, execute, memory, write-back) directly from the earlier single-cycle datapath, adding pipeline registers between stages to hold both data and control signals for each in-flight instruction. It shows that pipeline stages are rarely perfectly balanced in latency, which limits real speedup below the ideal factor equal to the number of stages, and that adding pipeline registers has its own hardware cost. Control signals are generated once per instruction (as in the single-cycle design) but propagated through the pipeline registers and used only in the stage that needs them, closing with the observation that every instruction must pass through every stage even when it does not need that stage's work.

Before you watch

• Review the single-cycle MIPS datapath and control-signal design from the earlier lectures in this course, since this lecture builds directly on it.
• Be comfortable with the MIPS instruction encodings for R-type, I-type (load/store), and branch instructions.
• Recall the performance equation (execution time = instructions x CPI x clock cycle time), which the lecture uses to motivate both multi-cycle and pipelined designs.

Check your understanding

1. Why does the multi-cycle design need extra states just to increment the program counter, and what design choice caused this?
2. Walk through the sequence of states a load-word instruction passes through, and explain what control signals are active in each.
3. What is a micro-instruction, and how does storing micro-instructions in a control store enable microcode patches?
4. Why does an R-type instruction sitting idle in a multi-cycle state motivate the move to pipelining?
5. In the five-stage pipeline datapath, why must control signals be delayed and propagated through pipeline registers rather than generated all at once?