Single-Cycle Control

In a single-cycle datapath, every instruction — whether an arithmetic operation, a memory access, or a branch — passes through the same physical wires and components during one clock cycle. The datapath itself is instruction-agnostic: the ALU will add whatever two numbers are presented to it, and a multiplexer will pass through whatever input its select line names, but neither knows why. The control unit supplies the "why" by translating the instruction's opcode field (and, for many instruction sets, a secondary function code) into a vector of Boolean control signals that steer every multiplexer select, every unit's operation code, and every read/write enable in the datapath. Formally, if $I$ is the (finite) set of instructions in the ISA and $S$ is the set of control-signal vectors the datapath accepts, the control unit implements a function

which is total (every legal instruction maps to some signal vector) and, for a correctly designed datapath, unambiguous (each instruction maps to exactly the signal vector that produces its architecturally defined behavior). Because $C$ has no memory — its output depends only on the current instruction's bits, not on any previous cycle — it is realizable as pure combinational logic: two-level AND-OR arrays, a PLA, a ROM lookup table, or synthesized gates, all equivalent in behavior though different in circuit-level cost. The key structural insight is that not all signals need the full instruction. Signals like `RegDst`, `ALUSrc`, `MemtoReg`, `RegWrite`, `MemRead`, `MemWrite`, and `Branch` depend only on the coarse instruction format — R-type, load, store, branch — which the opcode alone identifies. But the precise ALU operation for R-type instructions (add vs. subtract vs. AND vs. OR vs. set-less-than) additionally depends on the function code buried in the instruction's low-order bits. This observation motivates splitting control into a main control unit (opcode → format-level signals, including a 2-bit `ALUOp` hint) and a smaller ALU control unit (`ALUOp` + funct → the actual 4-bit ALU operation). This two-level decomposition is not just an implementation convenience — it reflects the genuine structure of the instruction set, where the opcode determines "shape" and the funct field determines "which flavor of R-type."

The derivation proceeds in four steps: identify instruction formats, enumerate required control signals per format, build a truth table, and factor the ALU-operation decoding into its own sub-unit.

Step 1 — Instruction formats. For a small MIPS-like subset, consider six instructions:

R-type instructions share one opcode (`000000`) and are distinguished by a 6-bit `funct` field in the instruction's low bits.

Step 2 — Datapath signals. Recall from the Single-Cycle Datapath the signals every instruction must set:

• `RegDst` — selects destination register: `rd` (R-type) vs. `rt` (I-type)
• `ALUSrc` — selects ALU's second operand: register file vs. sign-extended immediate
• `MemtoReg` — selects what is written back to the register file: ALU result vs. memory data
• `RegWrite` — enables writing the register file
• `MemRead` — enables reading data memory
• `MemWrite` — enables writing data memory
• `Branch` — gates whether the branch target replaces `PC + 4`
• `ALUOp` — a coarse hint (2 bits suffice here) telling the ALU control unit what family of operation is needed

Step 3 — Main control truth table.

`X` marks don't-care entries — the datapath never uses that signal's value for this instruction (e.g. `sw` writes no register, so `RegDst` is irrelevant), and don't-cares are exploited during logic minimization to shrink the resulting gates.

Step 4 — ALU control sub-table. `ALUOp = 00` always means "add" (used by `lw`/`sw` to compute an address). `ALUOp = 01` always means "subtract" (used by `beq` to test equality via zero-detection). `ALUOp = 10` means "consult `funct`":

``` // Main control: combinational function of the 6-bit opcode only. function MainControl(opcode): switch opcode: case R_TYPE: // 000000 return { RegDst:1, ALUSrc:0, MemtoReg:0, RegWrite:1, MemRead:0, MemWrite:0, Branch:0, ALUOp:"10" } case LW: // 100011 return { RegDst:0, ALUSrc:1, MemtoReg:1, RegWrite:1, MemRead:1, MemWrite:0, Branch:0, ALUOp:"00" } case SW: // 101011 return { RegDst:X, ALUSrc:1, MemtoReg:X, RegWrite:0, MemRead:0, MemWrite:1, Branch:0, ALUOp:"00" } case BEQ: // 000100 return { RegDst:X, ALUSrc:0, MemtoReg:X, RegWrite:0, MemRead:0, MemWrite:0, Branch:1, ALUOp:"01" } default: error("unimplemented opcode") // undefined instruction trap // ALU control: combinational function of ALUOp and the funct field. function ALUControl(ALUOp, funct): if ALUOp == "00": return ADD if ALUOp == "01": return SUBTRACT if ALUOp == "10": switch funct: case 0x20: return ADD // add case 0x22: return SUBTRACT // sub case 0x24: return AND // and case 0x25: return OR // or case 0x2A: return SET_LESS_THAN // slt default: error("unimplemented funct") error("unimplemented ALUOp") // Top-level control, invoked once per instruction, purely combinational. function Control(instruction): opcode = instruction[31:26] funct = instruction[5:0] mc = MainControl(opcode) aluOp = ALUControl(mc.ALUOp, funct) return { RegDst: mc.RegDst, ALUSrc: mc.ALUSrc, MemtoReg: mc.MemtoReg, RegWrite: mc.RegWrite, MemRead: mc.MemRead, MemWrite: mc.MemWrite, Branch: mc.Branch, ALUOperation: aluOp } ``` The pseudocode is written as ordinary control flow for clarity, but the actual hardware realization is a combinational circuit: every `switch` becomes a decoder feeding AND-OR gate arrays (or a lookup table / PLA), evaluated in parallel, not sequentially. There is no loop, no recursion, and no state element — a strict requirement, since the entire instruction must complete in one clock period and the control outputs must be stable well before the clock edge that commits the results.

Time complexity. Control logic is combinational, so its "running time" is not measured in cycles but in gate delay: the depth of the longest path from an instruction bit to a control output. With a two-level (main + ALU) decomposition, the critical path is the main-control decode in parallel with the ALU-control decode, so total delay is $O(1)$ in the number of instructions — it does not grow as more instructions are added to the truth table, only as the encoding width (number of opcode/funct bits) grows, and that is fixed by the ISA. Concretely, if there are $k$ opcode bits and $j$ funct bits, a two-level AND-OR realization has depth $O(k + j)$ gate levels — a constant for a fixed ISA, independent of how many distinct instructions exist, because a decoder's depth scales with the number of input bits, not the number of output lines it distinguishes.

Space complexity. A naive one-level truth table over all opcode bits (ignoring the funct-based factoring) would need a row for every combination the opcode space allows, and — worse — if R-type variants were not factored out, a separate full-width entry per R-type operation, duplicating the shared control bits (`RegDst=1, ALUSrc=0, ...`) across every one. Factoring into main control (indexed by $k$ opcode bits, one row per instruction format, of which there are few) plus ALU control (indexed by $j$ funct bits, one row per R-type variant) reduces the table from $O(\text{formats} \times \text{variants})$ rows to $O(\text{formats} + \text{variants})$ rows — an additive rather than multiplicative structure. This is the central efficiency argument for two-level control: it exploits the fact that the format-determining signals and the operation-determining signal are independent axes of variation.

Correctness argument. Correctness means: for every instruction $i$ in the ISA, $C(i)$ equals the unique signal vector that the datapath's wiring requires to realize $i$'s architecturally defined semantics. The proof strategy is exhaustive and finite, which is exactly why it is tractable: 1. The instruction set is finite (bounded by the fixed opcode/funct field widths), so the specification is a finite table, not an inductive claim over unbounded input. 2. For each instruction, trace the datapath component-by-component (register-file read ports, ALU, memory, muxes, PC update logic) and derive, from the datapath's own wiring diagram, the unique setting of every mux-select and enable line that produces the instruction's defined effect. This step reuses correctness already established for the Single-Cycle Datapath — control assumes the datapath wiring is fixed and correct, and asks only "what values must flow on these particular wires." 3. Verify that the truth table entries match that derivation exactly, including don't-cares — a don't-care is only sound if the datapath output genuinely does not depend on that signal for this instruction (e.g., `RegDst` for `sw` is safe as `X` only because `sw` also sets `RegWrite = 0`, so no register write ever observes `RegDst`'s value). 4. Verify totality: every legal opcode/funct combination in the ISA maps to some table row (an `error` on an illegal combination is acceptable and expected — it signals an illegal-instruction trap, not a control bug). Because the table is finite and each row is checked independently against the datapath's requirements, correctness is a finite case analysis, not an inductive or asymptotic argument — this is a genuine strength of single-cycle control: it is exhaustively verifiable by hand or automated truth-table checking, unlike control schemes with internal state where correctness must reason about sequences of cycles.

Tradeoffs. The efficiency this buys is purely combinational (low gate count, one decode per instruction, easy to verify) — it does not make instructions execute quickly in wall-clock time. Every instruction, including the fastest (`add`), must wait for the slowest instruction's critical path (a `lw`, which chains PC→instruction-fetch→register-read→ALU-address-compute→data-memory-read→writeback) because the clock period is fixed to accommodate the worst case. This is the single-cycle datapath's defining inefficiency, and it is precisely the problem Multicycle Control addresses by allowing different instructions to take different numbers of (shorter) cycles, and that Introduction to Pipelining addresses by overlapping instructions across dedicated stages.

Trace the instruction `lw $t0, 8($s1)` through the control logic. In MIPS encoding this assembles to: ``` opcode = 100011 rs = $s1 (10001) rt =$t0 (01000) immediate = 8 (0000000000001000) ```

Now contrast with `sub $t1,$t2, $t3` (R-type, `funct = 100010`):

These two traces show the payoff of the two-level design directly: both instructions share the same main-control machinery for classifying "is this R-type or I-type," but only `sub` needs the ALU-control sub-decoder to distinguish it from `add`, `and`, `or`, or `slt` — all of which share the identical main-control row `RegDst=1, ALUSrc=0, ...` and differ only in the ALU-control output.

The idea that a fixed instruction format could be mechanically decoded into control signals traces back to the earliest stored-program computers, where the distinction between "control" and "datapath" first became an explicit engineering discipline rather than an ad hoc wiring exercise.

Single-cycle control is rarely the final design in production silicon, but the technique of deriving control signals from opcode and function fields underlies control logic at every complexity level. Modern superscalar and out-of-order cores still perform an analogous opcode decode as the first pipeline stage, just with far more elaborate downstream scheduling. Embedded microcontrollers with simple in-order pipelines (many classroom RISC-V cores, early ARM cores, and small soft-core processors on FPGAs) implement control almost exactly as described here — a combinational decode block feeding datapath muxes and enables. Hardware description languages like Verilog and VHDL express this control logic as `case` statements over opcode fields, which synthesis tools then compile into gate-level decoders or lookup tables, mirroring the pseudocode's structure directly. Understanding this derivation is also the necessary foundation for Multicycle Control, where the same signal set is instead produced cycle-by-cycle by a finite-state machine, and for Introduction to Pipelining, where control signals must additionally be latched and carried forward through pipeline registers alongside the instruction they govern.

Ask the tutor: How would this control table change if we added a jump (`j`) instruction to the ISA?