Datapath and Control Overview

A synchronous digital system is built from two kinds of components: combinational logic, which computes an output as a pure function of its current inputs (adders, multiplexers, the ALU), and sequential logic, which stores state across clock edges (registers, the register file, memory). The datapath is the combinational-plus-sequential network that moves and transforms data: it is the union of every register, every multiplexer, every bus, and the ALU, wired so that data can flow from sources (register file outputs, immediates, memory) through computation (the ALU) to destinations (register file inputs, memory, the program counter). The control unit is a separate piece of logic — often literally implemented as a Finite State Machine — whose job is to decide, on every clock cycle, what the datapath should do. It does this by asserting control signals: single wires or small buses that select multiplexer inputs, enable or disable register writes, and choose the ALU's operation. Crucially, the control unit does not manipulate data itself. It only looks at control inputs (the instruction's opcode, function code, and possibly the current FSM state) and produces control outputs (signals). This separation is what makes processors comprehensible: you can verify the datapath's wiring once, then verify the controller's signal table once, and trust that any combination the controller can produce is handled correctly by the datapath. Two classic organizations differ in how much datapath is built and how many clock cycles an instruction takes. A single-cycle datapath completes every instruction — load, store, add, branch — within one clock cycle, which means the cycle time must be as long as the slowest possible instruction (typically a load, which touches the register file, the ALU, and memory). A multicycle datapath breaks each instruction into several shorter steps (fetch, decode, execute, memory access, write-back), reusing the same ALU and memory port across cycles, with the control unit now genuinely stateful — an FSM whose state is "which step of this instruction am I on." Multicycle designs shrink the clock period to match the slowest single step, not the slowest instruction, at the cost of needing extra registers to hold intermediate values between steps and a real FSM (rather than a simple combinational decoder) for control.

The datapath's building blocks

A minimal processor datapath needs:

• A program counter (PC), a register holding the address of the current instruction.
• An instruction memory, read (never written, in this simplified model) using the PC.
• A register file, with two read ports (for source operands) and one write port (for the result), as covered in Registers and Register Files.
• An ALU, performing arithmetic/logic operations selected by a control signal, as covered in Arithmetic Logic Units.
• A data memory, read for loads, written for stores.
• Multiplexers, selecting among alternative data sources (e.g., ALU's second operand is either a register or a sign-extended immediate).
• Adders, for computing PC+4 and branch targets.

The control unit

The control unit takes the instruction's opcode (and function field, for R-type instructions) and produces every control signal the datapath needs that cycle. In a single-cycle design this is purely combinational: a truth table (opcode → signals) with no memory of past cycles. In a multicycle design, control becomes an actual Finite State Machine: the same opcode produces different signals on different cycles, because the state variable itself remembers "we are in the execute step" versus "we are in the write-back step." The signal set for a simple RISC-style machine typically includes:

Step-by-step mechanism (single-cycle view)

``` // Executed once per clock cycle, on every rising edge, for one instruction function CYCLE(): // 1. FETCH (combinational read, using PC from the previous cycle) instruction ← InstructionMemory[PC] // 2. DECODE + CONTROL (pure combinational function of opcode/funct) signals ← ControlUnit(instruction.opcode, instruction.funct) // 3. REGISTER READ (combinational, using instruction's register fields) rs_val ← RegisterFile.read(instruction.rs) rt_val ← RegisterFile.read(instruction.rt) imm ← SignExtend(instruction.immediate) // 4. ALU OPERAND SELECT + EXECUTE (combinational) operand2 ← signals.ALUSrc ? imm : rt_val alu_result, zero ← ALU(rs_val, operand2, signals.ALUOp) // 5. MEMORY ACCESS (combinational read; write is latched at clock edge) mem_data ← signals.MemRead ? DataMemory[alu_result] : undefined // 6. WRITE-BACK SELECT (combinational) write_data ← signals.MemToReg ? mem_data : alu_result write_reg ← signals.RegDst ? instruction.rd : instruction.rt // 7. NEXT PC (combinational) branch_target ← PC + 4 + (imm << 2) next_PC ← (signals.Branch AND zero) ? branch_target : PC + 4 // ---- CLOCK EDGE: the ONLY moment state actually changes ---- on rising_edge(clock): if signals.RegWrite: RegisterFile.write(write_reg, write_data) if signals.MemWrite: DataMemory[alu_result] ← rt_val PC ← next_PC ``` Every line above step marked "CLOCK EDGE" is combinational logic — it settles to a stable value within one cycle, given stable inputs, and can be computed in any order because it has no memory. Only the final block is sequential: registers, the register file, data memory, and the PC all update simultaneously at the clock edge, using values that were computed combinationally during that same cycle. This is the invariant that makes single-cycle datapaths correct: all reads see the state from the end of the previous cycle; all writes take effect at the end of the current cycle.

The control unit as an FSM (multicycle view)

In a multicycle machine, the same skeleton is spread across states: ``` state ← FETCH function CONTROLLER_STEP(state, opcode, funct): switch state: case FETCH: signals ← { IorD: 0, MemRead: 1, IRWrite: 1, ALUSrcA: 0, ALUSrcB: 01, ALUOp: ADD, PCWrite: 1, PCSource: 0 } next_state ← DECODE case DECODE: signals ← { ALUSrcA: 0, ALUSrcB: 11, ALUOp: ADD } // compute PC+branch offset early next_state ← dispatch on opcode: R-type→EXEC, lw/sw→MEMADR, beq→BRANCH case MEMADR: signals ← { ALUSrcA: 1, ALUSrcB: 10, ALUOp: ADD } // base + offset next_state ← (opcode == lw) ? MEMREAD : MEMWRITE case MEMREAD: signals ← { IorD: 1, MemRead: 1 } next_state ← WRITEBACK case WRITEBACK: signals ← { MemToReg: 1, RegDst: 0, RegWrite: 1 } next_state ← FETCH case MEMWRITE: signals ← { IorD: 1, MemWrite: 1 } next_state ← FETCH case EXEC: signals ← { ALUSrcA: 1, ALUSrcB: 00, ALUOp: FUNCT(funct) } next_state ← RTYPEWB case RTYPEWB: signals ← { RegDst: 1, MemToReg: 0, RegWrite: 1 } next_state ← FETCH case BRANCH: signals ← { ALUSrcA: 1, ALUSrcB: 00, ALUOp: SUB, PCWriteCond: 1, PCSource: 1 } next_state ← FETCH return signals, next_state ``` Notice the key difference from the single-cycle controller: the state itself is part of the memory of "where we are in this instruction." The same opcode (`lw`) drives the controller through four different states (FETCH → DECODE → MEMADR → MEMREAD → WRITEBACK), asserting different signals each cycle, reusing one ALU and one memory port for both the address computation and the data access.

Space/hardware complexity. The datapath's size is linear in the number of distinct functional units and the bit-width of the machine: one ALU of width $w$, one register file of $r$ registers, each $w$ bits wide ($O(r \cdot w)$ storage), one instruction and one data memory (external, addressed rather than duplicated), and $O(1)$ multiplexers and adders — the count of multiplexers is fixed by the instruction set's control needs, not by program size. The control unit's size depends on its implementation: as a truth table, it is $O(2^{|\text{opcode bits}|})$ in the worst case (though sparse in practice, since not every opcode pattern is used); as an FSM, it is $O(S)$ states times $O(1)$ transition logic per state, where $S$ is the number of pipeline steps the most complex instruction requires (typically 3–5).

Time complexity — single-cycle. Every instruction takes exactly one clock cycle, so an $n$-instruction program runs in $T = n \cdot T_{\text{clk}}$, where $T_{\text{clk}}$ must exceed the critical path delay of the slowest instruction. For a load word, that path is: instruction-memory read → register-file read → ALU add (base+offset) → data-memory read → write-back mux → register-file write setup time. Every other instruction (e.g., an R-type add) has a shorter path but must still wait out the same $T_{\text{clk}}$, since the clock period is fixed for the whole machine. This is the core inefficiency of single-cycle design: the clock is only as fast as the slowest instruction, wasted on every other instruction.

Time complexity — multicycle. The clock period shrinks to the slowest single step (e.g., one register read, or one ALU op, or one memory access — never all of them in series), call it $T_{\text{step}} \ll T_{\text{clk}}$. But each instruction now takes multiple cycles: lw/sw take 5 steps, R-type takes 4, branch takes 3 in a typical design. So total time is $T = \sum_i c_i \cdot T_{\text{step}}$ where $c_i \in \{3,4,5,\dots\}$ is the cycle count of instruction $i$. Whether multicycle beats single-cycle depends on the instruction mix: if most instructions are cheap (branches, register-register ops) the shorter step time wins; if memory instructions dominate, the extra cycles can offset the gain. This tradeoff is exactly what pipelining (a separate technique) is designed to eliminate by overlapping steps across instructions instead of serializing them per-instruction.

Correctness argument. The design is correct if two properties hold on every cycle: 1. No write-write conflicts. At most one write is committed to each stateful element (register file, PC, memory) per cycle; this is guaranteed by construction because the control unit asserts at most one write-enable combination consistent with the instruction (`RegWrite` and `MemWrite` are never both meaningfully driving the same destination — they target different memories entirely). 2. Reads-before-writes ordering. All combinational reads (register-file reads, memory reads for `lw`, decode of the current instruction) use the values as they stood at the end of the previous clock edge. Because writes are gated behind `on rising_edge(clock)` and reads are plain combinational logic evaluated from the current stable state, there is no possibility of a read observing a write from the same cycle — this is precisely the register-transfer-level (RTL) semantics that make sequential circuits deterministic. Formally, if $Q(t)$ denotes register state after edge $t$, then every combinational output at cycle $t{+}1$ is a pure function $f(Q(t), \text{inputs}(t{+}1))$, and $Q(t{+}1) = g(Q(t), \text{inputs}(t{+}1))$ is computed and then latched — never read back within the same cycle. This is an inductive invariant: if it holds after edge $t$, the combinational logic at $t{+}1$ is well-defined, and the next edge preserves it. The controller's correctness reduces to a simpler claim: for every reachable (opcode, state) pair, the signal vector it emits matches the datapath's requirement table (the one a designer writes by hand, e.g. "for `lw`, `ALUSrc=1, MemRead=1, MemToReg=1, RegWrite=1`, all else 0"). This is checkable exhaustively because the opcode space and state space are both finite and small — a key reason FSM-based control scales to real hardware verification.

Honest tradeoffs. Single-cycle datapaths are simple to reason about (no state in the controller) but waste time and cannot share hardware (you often need two adders — one for PC+4, one for branch target — because a single-cycle design cannot reuse the same adder twice in one cycle). Multicycle datapaths reuse hardware (one ALU, one memory port, shared across steps) and shorten the clock, but the controller becomes a genuine FSM, harder to verify, and instructions incur multiple cycles of latency even when idle. Pipelining, a further refinement, keeps the multicycle step structure but overlaps steps of different instructions — a topic that builds directly on the datapath/control separation introduced here.

Trace a single-cycle datapath executing `add $t0,$s1, $s2` (an R-type instruction: `$t0 = $s1 +$s2`), assuming `$s1 = 12`, `$s2 = 7`, and PC = 4000 before the fetch.

Every intermediate value above (fetch through next-PC) is computed combinationally within the same cycle; only the final row is latched. Note that `branch_target` is computed even though this is not a branch instruction — this is normal and harmless in a single-cycle design, since the `Branch` signal simply ensures it's never selected as `next_PC`; wasted computation here is the price of a uniform datapath that handles every instruction with the same wires. Now contrast with `lw $t1, 8($s3)` (assume `$s3 = 5000`, and `DMEM[5008] = 42`), showing why loads set the worst-case critical path:

This instruction's critical path threads through five functional units in series (IMEM → RF read → ALU → DMEM → write-back mux), which is exactly why single-cycle clock period is dictated by `lw`, not by `add`.

The datapath/control separation traces back to the earliest stored-program computer designs, where engineers first confronted the need to distinguish "where the numbers live and move" from "what decides what happens next."

The datapath/control split is not a pedagogical simplification confined to textbook MIPS or RISC-V cores — it is the literal architecture of real silicon. Microcontrollers used in embedded systems (automotive ECUs, IoT sensors) are frequently single-cycle or simple multicycle designs exactly like the one built here, chosen for predictability and low gate count. High-performance out-of-order processors still contain, at their heart, a datapath (execution units, register files, load/store units) driven by control logic — though the controller there is vastly more complex, involving scheduling and speculation rather than a simple FSM. Hardware description languages (Verilog, VHDL) used in Field-Programmable Gate Arrays and ASIC design directly encode this split: a "datapath module" instantiating registers and an ALU, and a "control module" instantiating an FSM that drives select and enable lines. Compilers targeting real ISAs must understand the datapath's constraints (e.g., which operations can share a cycle, or how loads stall a pipeline) to schedule instructions efficiently, and hardware verification tools check exactly the correctness properties described above — no simultaneous writes, no read-before-write races — as part of formal RTL verification before a chip is fabricated.

Ask the tutor: How would you extend this single-cycle datapath's control unit and wiring to support a jump-and-link instruction?