Single-cycle datapath design: Exercises — Hardware deep dive

This page tests the machinery of single-cycle datapath design. Timing ideas feed forward into Pipelining and Multi-cycle datapath; the delay-summing logic is the seed of the Performance equation.

Timing symbols used throughout (all in picoseconds, abbreviated $ps$ — one trillionth of a second):

Level 1 — Recognition

Problem 1.1

Name the four muxes in the classic single-cycle MIPS datapath and, in one phrase each, say what two inputs each one chooses between.

Recall Solution 1.1

A mux (multiplexer) is a hardware switch: several data inputs, one output, and a select line that picks which input passes through. It exists exactly where two instruction types disagree about what feeds a block.

ALUSrc mux — chooses the ALU's 2nd operand: the ==register rt value vs. the sign-extended immediate==.
MemToReg mux — chooses what gets written back to a register: the ALU result vs. the data-memory output.
RegDst mux — chooses the destination register field: ==rd (R-type) vs. rt (I-type)==.
PCSrc mux — chooses the next PC: ==PC+4 vs. the branch target==.

Problem 1.2

For a sw (store word) instruction, state the value of each control signal: RegWrite, ALUSrc, MemRead, MemWrite, Branch.

Recall Solution 1.2

Ask "what does a store need?" A store computes an address (base + offset) and writes a register's value to memory. It produces no register result.

RegWrite = 0 (nothing goes back into a register).
ALUSrc = 1 (the ALU's 2nd input is the sign-extended offset, not a register).
MemRead = 0 (we are not reading memory).
MemWrite = 1 (we ARE writing memory).
Branch = 0 (a store never redirects the PC).

Level 2 — Application

Problem 2.1

Given block delays $t_{I M e m} = 200$ , $t_{R e g R e a d} = 100$ , $t_{A LU} = 200$ , $t_{D M e m} = 200$ , $t_{R e g W r i t e} = 100$ (all ps), compute the total path delay for each instruction and state the required clock period.

Recall Solution 2.1

Walk each instruction through only the blocks it actually uses, summing delays.

R-type (no memory): $200 + 100 + 200 + 0 + 100 = 600$ ps.
lw (touches everything): $200 + 100 + 200 + 200 + 100 = 800$ ps.
sw (no write-back): $200 + 100 + 200 + 200 = 700$ ps.
beq (compare only, no memory/no write-back): $200 + 100 + 200 = 500$ ps.

The clock period is the max over all instructions (single-cycle forces one shared period): $T_{c l k} = max (600, 800, 700, 500) = 800 ps .$

The bars above show each instruction's path; the tallest (lw) sets the dashed red clock line every other instruction is measured against.

Problem 2.2

Using $T_{c l k} = 800$ ps from 2.1, compute the CPU's clock frequency in GHz, and the execution time of a program with $2 \times 1 0^{6}$ instructions.

Recall Solution 2.2

Frequency is the reciprocal of the period. $800 ps = 800 \times 1 0^{- 12} s$ . $f = \frac{1}{800 \times 1 0 ^{- 12}} = 1.25 \times 1 0^{9} Hz = 1.25 GHz .$ Execution time uses the Performance equation with $CPI = 1$ (single-cycle): $T_{p r o g} = Instr count \times CPI \times T_{c l k} = 2 \times 1 0^{6} \times 1 \times 800 \times 1 0^{- 12} s = 1.6 \times 1 0^{- 3} s = 1.6 ms .$

Level 3 — Analysis

Problem 3.1

A student proposes reusing the main ALU to compute PC+4 instead of adding a separate adder, to save gates. Explain, in timing terms, why this breaks the single-cycle design.

Recall Solution 3.1

In single-cycle, all of an instruction's work happens in one clock cycle. During that cycle the ALU is already occupied computing the instruction's own arithmetic (or its branch/address). Computing PC+4 on the same ALU would require the ALU to do two additions sequentially within one cycle — but there is no second sub-cycle to schedule it into. Concretely, the path would become $t_{A LU}$ (for PC+4) then $t_{A LU}$ (for the instruction), doubling the ALU term and lengthening the critical path. A dedicated adder runs in parallel, so PC+4 costs $t_{a dd}$ that overlaps with (is hidden behind) the fetch/decode delays and never touches the ALU. Hence: separate adder, not the ALU.

Problem 3.2

Take the delays of Problem 2.1 but add a mux delay $t_{m ux} = 30$ ps on the ALUSrc path and the MemToReg path, and a sign-extend delay $t_{se x t} = 20$ ps that feeds the ALUSrc mux. Recompute the lw critical path.

Recall Solution 3.2

Trace lw's signal edge by edge. After the registers are read (or the immediate is sign-extended, whichever is on the ALU's 2nd input), the value passes through the ALUSrc mux before reaching the ALU; after data memory the value passes through the MemToReg mux before write-back.

The 2nd-operand branch of the path is $t_{R e g R e a d} = 100$ vs. $t_{se x t} = 20$ ; the slower one gates the mux, so we take $max (100, 20) = 100$ . Then: $T_{l w} = t_{I M e m} + 100 max (t_{R e g R e a d}, t_{se x t}) + t_{m ux} + t_{A LU} + t_{D M e m} + t_{m ux} + t_{R e g W r i t e}$ $= 200 + 100 + 30 + 200 + 200 + 30 + 100 = 860 ps .$ The two 30 ps muxes push the period from 800 to 860 ps — muxes are not free.

Level 4 — Synthesis

Problem 4.1

Design the control-signal row for a new instruction lui rt, imm ("load upper immediate": place the 16-bit immediate into the high half of register rt, zeros in the low half). Assume you add a small shifter that shifts the immediate left 16 bits and route it into the MemToReg mux as a third input. Give RegWrite, ALUSrc, MemRead, MemWrite, Branch, RegDst, and describe MemToReg.

Recall Solution 4.1

Ask what lui needs: it writes a register (rt), it does not touch data memory, and it does not branch. The value written is the shifted immediate — neither the ALU result nor memory output — so the MemToReg mux must select the new shifted-immediate input.

RegWrite = 1 (result goes to rt).
ALUSrc = X (don't care — the ALU output is not used; but if reused, feeding the immediate is harmless, so leave it 1 or X).
MemRead = 0.
MemWrite = 0.
Branch = 0.
RegDst = 0 (destination is rt, the I-type field).
MemToReg = select the shifted-immediate input (the new 3rd mux position).

Key insight: lui is a register-writing instruction that bypasses both the ALU-result and memory paths — exactly the kind of "instructions disagree" situation that justifies widening the MemToReg mux.

Problem 4.2

Suppose we add a mul instruction whose ALU stage needs $t_{A LU}^{m u l} = 500$ ps (vs. 200 ps for others). Using the base delays of 2.1, compute mul's path (R-type shape: no memory) and the new clock period, and by what percent every other instruction is slowed.

Recall Solution 4.2

mul has the R-type shape (fetch, read, execute, write-back — no memory): $T_{m u l} = 200 + 100 + 500 + 100 = 900 ps .$ New clock period $= max (800, 900) = 900$ ps. Every instruction now runs at 900 ps. Percentage slowdown vs. the old 800 ps: $\frac{900 - 800}{800} \times 100% = 12.5%.$ One slow instruction taxes all of them by $12.5%$ — the core weakness single-cycle inherits and Pipelining fixes.

Level 5 — Mastery

Problem 5.1

A colleague argues: "Single-cycle has CPI = 1, the theoretical minimum. Therefore it is the fastest possible design." Refute this rigorously using the Performance equation, and state the condition under which a Multi-cycle datapath or Pipelining design wins.

Recall Solution 5.1

Performance is governed by $T_{p r o g} = N \times CPI \times T_{c l k},$ where $N$ = instruction count, CPI = cycles per instruction, $T_{c l k}$ = clock period. Three factors, not one. Single-cycle minimizes CPI to 1 but at the cost of a huge $T_{c l k}$ (set by the slowest instruction, e.g. 800 ps).

A multi-cycle design breaks each instruction into short cycles, so $T_{c l k}$ shrinks (to the slowest single stage, ~200 ps) but CPI rises above 1 (each instruction takes several cycles). It wins when the reduction in $T_{c l k}$ outweighs the increase in CPI, i.e. when $CPI_{m u l t i} \times T_{c l k}^{m u l t i} < 1 \times T_{c l k}^{s in g l e} .$ Pipelining does even better: it keeps CPI $\approx 1$ (one instruction finishes per cycle in steady state) while running $T_{c l k}$ near the slowest stage. So pipelining generally beats single-cycle on the product CPI $\times T_{c l k}$ , which is what actually matters. CPI = 1 alone proves nothing.

Problem 5.2

Concrete showdown. Single-cycle: $T_{c l k} = 800$ ps, CPI = 1. A 5-stage pipeline built from the same stages runs at $T_{c l k} = 200$ ps (slowest stage) with an effective CPI of 1.25 (accounting for hazards/stalls). For a program of $N = 1 0^{6}$ instructions, compute each execution time and the speedup.

Recall Solution 5.2

Single-cycle: $T_{s in g l e} = 1 0^{6} \times 1 \times 800 \times 1 0^{- 12} = 8.0 \times 1 0^{- 4} s = 0.8 ms .$ Pipeline: $T_{p i p e} = 1 0^{6} \times 1.25 \times 200 \times 1 0^{- 12} = 2.5 \times 1 0^{- 4} s = 0.25 ms .$ Speedup: $\frac{T _{s in g l e}}{T _{p i p e}} = \frac{0.8}{0.25} = 3.2 \times .$ Even with a CPI of 1.25 (worse than single-cycle's 1), the pipeline is 3.2× faster because its clock period is 4× shorter. This is exactly why the Performance equation warns against judging by CPI alone.

The bar chart contrasts the two total times; the pipeline bar is a fraction of the single-cycle bar despite its higher CPI.

Recall One-line self-check

The single number that decides a program's runtime ::: the product $N \times CPI \times T_{c l k}$ , never CPI alone.