The idea: one memory, one ALU, several short cycles

The single-cycle processor runs every instruction in one long clock cycle. It needs two memories (one for instructions, one for data) and two extra adders, because each part can be used only once per cycle. The multicycle processor of Patterson and Hennessy breaks each instruction into steps and runs one step per clock cycle. Then one memory and one ALU are enough: the same ALU adds PC + 4 in one cycle and an address or a sum in a later one.

Left, single-cycle: instruction memory, data memory, the ALU and two adders for PC + 4 and the branch target. Right, multicycle: one memory, one ALU, and five hidden registers IR, MDR, A, B and ALUOut that hold values between cycles.
Multicycle trades two memories and two adders for five small registers that carry values from one cycle to the next.

Press Clock Once to run one clock cycle. The state that runs is orange in the state machine, the wires and muxes it uses turn red, the control signals it sets are orange, and the values move as blue boxes. At the clock edge the registers that were written turn green.

The registers between the steps

A value made in one cycle is needed in the next one, so it must be stored. That is the job of five registers the program cannot see:

RegisterWritten inHolds
IR (instruction register)state 0the instruction word; kept until the next fetch, because IRWrite is 1 only in state 0
MDR (memory data register)state 3the word a lw read
A, Bstate 1the registers rs and rt
ALUOutstates 1, 2, 6the ALU result: a branch target, an address or a sum

One memory now holds both the program and the data, so its address must be chosen: the IorD mux picks the PC (to fetch an instruction) or ALUOut (to read or write data). Look at the memory panel: rows 0x00 to 0x20 are code, rows 0x40 to 0x48 are data.

One step per cycle

The rule for a step: it may do at most one memory access, one register file access or one ALU operation. Then the clock period only has to fit the slowest step, not the whole instruction.

  1. Fetch (state 0): IR ← Mem[PC], and the ALU computes PC ← PC + 4 at the same time.
  2. Decode (state 1): A ← Reg[rs], B ← Reg[rt], and ALUOut ← PC + (sign-extend(imm) << 2). The branch target is computed before the processor knows the instruction is a branch: the ALU is free, and it saves a cycle for beq.
  3. Execute: an address (state 2), an R-type operation (state 6), a branch compare (state 8) or a jump (state 9).
  4. Memory: lw reads (state 3), sw writes (state 5); R-type writes its result (state 7).
  5. Write back: lw writes MDR into rt (state 4).

The control unit is a finite state machine

In the single-cycle processor the control is a truth table on the opcode. Here the signals must change from cycle to cycle, so the control is a finite state machine: each state sets the signals for one cycle and chooses the next state. States 0 and 1 are the same for all instructions; at the end of state 1 the opcode picks the path.

StateDoesSignalsNext
0 fetchIR ← Mem[PC]; PC ← PC + 4MemRead, IRWrite, PCWrite; IorD 0, ALUSrcA 0, ALUSrcB 01, ALUOp 00, PCSource 001
1 decodeA, B ← Reg; ALUOut ← branch targetALUSrcA 0, ALUSrcB 11, ALUOp 00lw, sw: 2; R-type: 6; beq: 8; j: 9
2 addressALUOut ← A + sign-extend(imm)ALUSrcA 1, ALUSrcB 10, ALUOp 00lw: 3; sw: 5
3 lw readMDR ← Mem[ALUOut]MemRead, IorD 14
4 lw writeReg[rt] ← MDRRegWrite, RegDst 0, MemtoReg 10
5 sw writeMem[ALUOut] ← BMemWrite, IorD 10
6 executeALUOut ← A op BALUSrcA 1, ALUSrcB 00, ALUOp 107
7 R writeReg[rd] ← ALUOutRegWrite, RegDst 1, MemtoReg 00
8 branchif A = B: PC ← ALUOutALUSrcA 1, ALUSrcB 00, ALUOp 01, PCWriteCond, PCSource 010
9 jumpPC ← {PC[31:28], IR[25:0], 00}PCWrite, PCSource 100

A signal that a state does not list is 0 if it is a write enable, and don't care (X) if it is a mux select. ALUSrcB picks one of four inputs: 00 = B, 01 = the constant 4, 10 = the sign-extended immediate, 11 = the immediate shifted left by 2. PCSource picks the ALU result (PC + 4), ALUOut (the branch target) or the jump address. The PC is written when PCWrite is 1, or when PCWriteCond is 1 and the ALU's Zero output is 1.

Cycles per instruction

The number of cycles is the length of the instruction's path through the state machine:

Five rows of state boxes: lw 0 1 2 3 4, 5 cycles; sw 0 1 2 5, 4 cycles; R-type 0 1 6 7, 4 cycles; beq 0 1 8, 3 cycles; j 0 1 9, 3 cycles. States 0 and 1 are the same in every row.
Every instruction starts with fetch and decode; after that its own states decide whether it takes 3, 4 or 5 cycles.

The program on the canvas runs each kind once (Demos 1 to 5): two lw that load 7 and 7, a beq that is taken because they are equal and skips 0x0C, an add that makes 14, a sw that stores it at 0x48, and a j that skips 0x1C and ends the program at 0x20. That is 5 + 5 + 3 + 4 + 4 + 3 = 24 cycles for 6 instructions: CPI = 4.00 (Demo: the whole program). A beq takes 3 cycles whether it is taken or not.

CPI from an instruction mix, and the clock

A real program runs different instructions in different amounts, so its CPI is the average weighted by the instruction mix. Patterson and Hennessy use the SPECint2000 mix: 25% loads, 10% stores, 52% R-type, 11% branches, 2% jumps (Demo: CPI of the textbook mix):

CPI = 0.25 × 5 + 0.10 × 4 + 0.52 × 4 + 0.11 × 3 + 0.02 × 3
    = 1.25 + 0.40 + 2.08 + 0.33 + 0.06 = 4.12

Time per program is instructions × CPI × clock period. Take the book's delays: memory 200 ps, ALU 100 ps, register file 50 ps. The single-cycle clock must fit a whole lw: 200 + 50 + 100 + 200 + 50 = 600 ps. The multicycle clock must fit one step, the longest being a memory access: 200 ps. So one instruction takes 4.12 × 200 = 824 ps on average, against 600 ps. The short clock does not pay off here: a lw needs 5 × 200 = 1,000 ps, and only beq and j (3 × 200 = 600 ps) break even.

Time axis in picoseconds. Single-cycle: lw 600 ps, beq 600 ps. Multicycle: lw 5 cycles of 200 ps = 1,000 ps, beq 3 cycles = 600 ps. The mix average is 824 ps for multicycle against 600 ps for single-cycle.
Each instruction pays for its own number of short cycles; on the textbook mix that averages 824 ps against a fixed 600 ps.

So why build it? It needs less hardware (one memory, one ALU), its steps are a good start for pipelining, which overlaps them, and its control can grow: more states give longer instructions such as multiply (Multiply and Divide Hardware) or the exception states of Exceptions in the MIPS Processor. Register setup and clock-to-Q overheads make the real multicycle clock even longer; Single-Cycle vs Multicycle vs Pipelined MIPS: a Performance Race runs the three designs side by side with Harris and Harris's delays.

See also How a Program Runs on the MIPS Datapath, the five-stage unpipelined datapath of Hennessy and Patterson's Quantitative Approach, with separate instruction and data memories and the NPC, LMD and Cond registers.

What the page leaves out

  • In the book, A, B, MDR and ALUOut have no write enable and load a new value at every clock edge. The page shows only the loads that the next state uses.
  • Other instructions (addi, bne, shifts) need more states or more control lines; exceptions add states 10 and 11 and the EPC and Cause registers.
  • The control can also be built as microprogram ROM words instead of a hard-wired state machine; the states and signals are the same.
  • Memory is ideal: every access takes one cycle. A cache miss would stall the state machine for many cycles.
  • Only 4 of the 32 registers are shown, and the control lines are drawn as a panel, not as wires from the control unit.

On the mind map

This page on the Computer Architecture mind map · 46 pages in 7 branches · open it to see the whole map and test yourself in recall mode.