Multi-cycle datapath

WHY does multi-cycle exist?

WHY is this bad? An add needs no memory access but is still charged for one. The clock is "one size fits all — the slowest size."

WHAT is the fix? Break execution into balanced sub-steps (each ≈ one functional-unit delay). Now the clock only has to be long enough for one step, not the whole instruction: $T_{multi} = \max(\text{delay of a single step}) \ll T_{single}$

HOW do we reuse hardware? Because steps happen in different cycles, one ALU / one memory can serve many roles. So we:

Use a single memory for both instructions and data (accessed in different cycles).
Use a single ALU for PC increment, branch target, and arithmetic.
Add internal registers (IR, A, B, ALUOut, MDR) to hold values between cycles, since combinational signals vanish at the clock edge.

The five canonical steps

Not every instruction uses all five. Cycle count per type:

Instruction	Steps used	# Cycles
R-type (`add`)	IF ID EX WB	4
`lw`	IF ID EX MEM WB	5
`sw`	IF ID EX MEM	4
`beq`	IF ID EX	3
`j`	IF ID EX	3

(A jump must reach EX because the PC is updated in step 3 — jump uses IF, ID, EX = 3 cycles.)

Deriving each step from first principles

We derive what must happen each cycle, and which internal register catches the result.

Step 1 — IF (Instruction Fetch)

We need the instruction bits, so read memory at address PC.
We also want PC+4 ready (default next instruction). $\text{IR} \leftarrow \text{Memory}[\text{PC}], \qquad \text{PC} \leftarrow \text{PC} + 4$ Why latch into IR? Because in the next cycle Memory may be used for data — the instruction bits would be lost otherwise. Why compute PC+4 now? The ALU is free this cycle, so we reuse it to increment PC.

Step 2 — ID (Decode / Register Fetch)

We don't yet know the instruction type, so do work that's useful for all possibilities: $A \leftarrow \text{Reg}[\text{IR}[25{:}21]], \quad B \leftarrow \text{Reg}[\text{IR}[20{:}16]]$ $\text{ALUOut} \leftarrow \text{PC} + (\text{sign-ext}(\text{IR}[15{:}0]) \ll 2)$ Why compute the branch target speculatively? The ALU is idle; if the instruction turns out to be beq we already have the target — no extra cycle wasted. This is optimistic pre-computation.

Step 3 — EX (depends on type)

R-type: $\text{ALUOut} \leftarrow A \ \text{op}\ B$
lw/sw: $\text{ALUOut} \leftarrow A + \text{sign-ext}(\text{IR}[15{:}0])$ (effective address)
beq: if $A = B$ then $\text{PC} \leftarrow \text{ALUOut}$ (target from step 2)
jump: $\text{PC} \leftarrow \{\text{PC}[31{:}28],\ \text{IR}[25{:}0],\ 00\}$ (PC updated here — this is why j needs the EX step)

Step 4 — MEM

lw: $\text{MDR} \leftarrow \text{Memory}[\text{ALUOut}]$
sw: $\text{Memory}[\text{ALUOut}] \leftarrow B$ — and sw is done here.
(R-type does not touch memory; it skips this step and writes back in Step 5.)

Step 5 — WB

lw: $\text{Reg}[\text{IR}[20{:}16]] \leftarrow \text{MDR}$
R-type: $\text{Reg}[\text{IR}[15{:}11]] \leftarrow \text{ALUOut}$ — R-type finishes here (writes back the ALU result computed in EX).

Worked examples

Worked example Example 3 — Average CPI

Mix: 25% loads (5), 10% stores (4), 45% R-type (4), 15% branch (3), 5% jump (3). $\text{CPI} = 0.25(5)+0.10(4)+0.45(4)+0.15(3)+0.05(3)$ $= 1.25+0.40+1.80+0.45+0.15 = \mathbf{4.05}$ Why this step? Each term is frequency × its cycle count; summing gives the weighted average. Speedup vs single-cycle (same instr count $N$ ): $\frac{T_{single}}{T_{multi}} = \frac{N\cdot 800}{N\cdot 4.05\cdot 300} = \frac{800}{1215} \approx 0.66$ Interpretation: With these numbers multi-cycle is actually slower on raw time — because the ID stage (300 ps) is unbalanced. Multi-cycle wins big only when stages are balanced or when memory delay dwarfs the others; its guaranteed benefit is less hardware (shared ALU/memory).

Common mistakes (Steel-manned)

Flashcards

Why must a single-cycle clock period equal the slowest instruction's delay?

Because every instruction completes in exactly one cycle, the cycle must be long enough for the worst-case path (lw).

What is the core trade-off of multi-cycle vs single-cycle?

More cycles per instruction, but a much shorter clock period, plus hardware reuse (one ALU, one memory).

Name the five multi-cycle steps in order.

IF, ID, EX, MEM, WB.

Why are internal registers (IR, A, B, ALUOut, MDR) needed?

To hold combinational results across clock edges so a later cycle can use an earlier cycle's value.

How many cycles does an R-type instruction take and in which step does it write back?

4 cycles — IF, ID, EX, WB; it skips MEM and writes ALUOut to the register file in the WB step.

Why does a jump instruction need the EX step (3 cycles, not 2)?

Because the PC is updated in step 3 (EX); the new target address is written to PC there.

Why can multi-cycle use a single unified memory?

Instruction fetch and data access occur in different cycles, so no simultaneous access is needed.

Why is the branch target computed in the ID step?

The ALU is idle then; pre-computing it speculatively saves a cycle if the instruction is a branch.

What does the ALU compute during IF?

PC + 4 (the default next instruction address).

Which stage often sets the multi-cycle clock period, and why?

ID — it does a register-file read (100 ps) followed by an ALU branch-target calc (200 ps) in the same cycle = 300 ps.

Formula for average CPI?

CPI = Σ fᵢ·cᵢ (frequency × cycle count summed over instruction types).

In which step and register does lw place data before write-back?

In MEM, into MDR (Memory Data Register).

Recall Feynman: explain to a 12-year-old

Imagine building a LEGO model. Single-cycle = you must build the whole model in one giant timed block, and the timer is set for the hardest model, so easy models waste time. Multi-cycle = you build in small steps (find pieces, snap base, add top...). Each step is quick, and an easy model just does fewer steps and stops early. You also reuse the same table (memory) and same hands (ALU) at different steps, so you need less equipment. You do more little steps, but each is fast — and you don't waste effort on the parts you don't need.

Connections

Single-cycle datapath — the baseline this improves on
Pipelining — takes multi-cycle idea further: overlap steps of different instructions
Control unit — FSM vs microprogramming — multi-cycle needs a finite-state control (one state per step)
CPI and CPU performance equation — how cycles × period gives execution time
ALU design — the shared unit reused across IF/ID/EX
Memory hierarchy — why one unified memory port is a real constraint

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, single-cycle datapath ki problem ye hai ki har instruction ko ek hi clock cycle me poora hona padta hai. Isliye clock ko itna slow rakhna padta hai ki sabse slow instruction (lw) bhi fit ho jaye. Matlab add jaisa fast instruction bhi utna hi time leta hai jitna lw. Ye waste hai. Multi-cycle isko fix karta hai — ek instruction ko chhote chhote steps me tod deta hai (IF, ID, EX, MEM, WB), aur har step ek chhota clock cycle leta hai. Fast instructions kam steps use karte hain, slow zyada.

Ab magic point: kyunki steps alag alag cycles me hote hain, hum same hardware reuse kar sakte hain. Ek hi memory instruction aur data dono ke liye (kyunki fetch aur data-access alag cycle me hote hain), aur ek hi ALU jo IF me PC+4 karta hai, ID me branch target nikalta hai, aur EX me actual arithmetic karta hai. Beech me values ko sambhalne ke liye internal registers rakhte hain — IR, A, B, ALUOut, MDR — ye "sticky notes" ki tarah value ko agle cycle tak hold karte hain, warna clock edge par value gayab ho jati.

Ek important detail: clock period sabse lambe stage se decide hota hai. Is example me ID stage me register read (100 ps) ke baad ALU ka branch-target calc (200 ps) hota hai — same cycle me — to ID = 300 ps ban jata hai, aur wahi clock period set karta hai. Performance nikalne ka formula: execution time = (cycles) × (clock period), aur average CPI = har instruction ki frequency × uske cycles ka sum. Yaad rakho — multi-cycle hamesha fast nahi hota; agar stages unbalanced hain to raw time me slow bhi ho sakta hai. Asli guaranteed faayda hai kam hardware (shared ALU/memory).

Ek aur baat: sab instructions 5 cycle nahi lete. beq aur j sirf 3 lete hain, add (R-type) 4 — aur R-type MEM step ko skip karta hai, uska write-back WB (step 5) me hota hai. Jump ko EX step chahiye kyunki PC step 3 me update hota hai. Jaise hi instruction ka kaam khatam, wo ruk jata hai — koi dummy cycle nahi. Ye concept aage pipelining me kaam aayega.

WHY does multi-cycle exist?

The five canonical steps

Deriving each step from first principles

Step 1 — IF (Instruction Fetch)

Step 2 — ID (Decode / Register Fetch)

Step 3 — EX (depends on type)

Step 4 — MEM

Step 5 — WB

Worked examples

Common mistakes (Steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Processor Datapath & Pipelining

Connections