Visual walkthrough — Multi-cycle datapath

5.2.2 · D2 · Hardware › Processor Datapath & Pipelining › Multi-cycle datapath

Do shorthand names jo hum throughout use karenge (yahan define kiye taaki koi symbol without explanation na aaye):

• $T_{single}$ = single-cycle machine ka clock period — ek beat ki length, jo poori instruction cover karni chahiye.
• $T_{multi}$ = multi-cycle machine ka clock period — ek chhoti beat ki length, jo sirf ek step cover karni chahiye.

Hum prove karenge ki $T_{multi}=\max (\text{one step})$ (aam taur par) $T_{single}=\max (\text{whole instruction})$ se bahut chhota hota hai.

Yeh parent note ka picture-first companion hai. Words ke liye woh padho; derivation ko zero se grow hote dekhne ke liye yeh padho.

Shuru karne se pehle, symbols ke baare mein chaar plain-word promises jo tumhe milenge:

• Ek clock ek heartbeat hai: ek signal jo fixed rate pe high–low flip karta hai. Ek poora beat = ek clock cycle. Ek beat ka time clock period $T$ hai (picoseconds mein measure hota hai, ps — trillionths of a second).
• ps ka matlab sirf picoseconds hai, time ki ek unit. Chhota $T$ = faster heartbeat = faster computer, agar beats ki ginti zyada na badhe.
• Ek register yahan ek chhoti si box hai jo ek number clock beats ke paar yaad rakhti hai. Hum important ones ko naam dete hain: $\text{PC},\text{IR},A,B,\text{ALUOut},\text{MDR}$ — har ek us moment define hota hai jab woh appear karta hai. ($\text{PC}$ = Program Counter, woh box jo us instruction ka address hold karta hai jo chal rahi hai; hum uska latch Step 3 mein dikhate hain.)
• Bit-slice notation $\text{IR}[25:21]$ ka matlab hai "instruction register ke bits number 25 se 21 tak le lo" — hardware kisi value ki wires ko number karta hai, bit 0 right pe, aur colon un wires ki ek range chunti hai (yahan 5 wires). Toh $\text{IR}[25:0]$ = "lowest 26 bits," aur $\text{IR}[15:0]$ = "lowest 16 bits." Yeh sirf instruction ki wires ka ek slice lena hai, bas itna hi.

Step 1 — Clock sabse slow kaam se baandhi hai

WHAT. Paanch kaam imagine karo jo ek load word (lw) sequence mein karta hai: memory se instruction padho, registers padho, ALU se address compute karo, data memory padho, register mein wapas likho. Yeh ek beat ke andar back-to-back hote hain.

WHY. Agar beat jaldi khatam ho jaata, to aakhri kaam finish nahi hota — answer garbage hota. Toh beat length poori chain cover karni chahiye: $T_{single}=\underset{\text{IMem}}{\underbrace{200}}+\underset{\text{RegFile read}}{\underbrace{100}}+\underset{\text{ALU}}{\underbrace{200}}+\underset{\text{DMem}}{\underbrace{200}}+\underset{\text{RegFile write}}{\underbrace{100}}=800\text{ps}$ Har under-brace ek functional unit ki delay hai; plus signs ka matlab hai "aur phir" — kaam strictly ek-ke-baad-ek hain, isliye unke times add hote hain. Total $800$ ps ek lambi beat ki length hai. (Is page mein throughout RegFile read aur RegFile write do register-file operations hain, har ek $100$ ps ka.)

PICTURE. Figure s01 ek single-cycle beat ko ek lamba grey bar ki tarah dikhata hai, left-to-right paanch labelled functional-unit delays mein split kiya hua (IMem 200, RegFile read 100, ALU 200, DMem 200, RegFile write 100). Upar ek yellow span poori cheez ko "one 800 ps beat" label karta hai, aur bar ke neeche ek pink note humein yaad dilata hai ki ek simple add, jo kabhi data memory nahi chhoota, poore bar ka bill bharta hai.

Step 2 — Lambe kaam ko balanced pieces mein kaato

WHAT. Hum lw bar ko functional units ke beech ke natural seams pe kaatenge, paanch slices denge: IF, ID, EX, MEM, WB (fetch, decode, execute, memory, write-back).

WHY. Har seam woh jagah hai jahan ek unit khatam hoti hai aur agli ko hand off karti hai. Agar hum har seam pe clock karein, naya period hoga $T_{multi}={\max }_{\text{step}}(\text{delay of that step})$ $\max$ symbol ka matlab hai "inme se sabse bada lo." Hum sabse bada step lete hain, sabse badi instruction nahi — yahi toh pura trick hai. Hamare numbers ke saath sabse bada single step $400$ ps nikalta hai (hum Step 4 mein iske baare mein build up karte hain), poori cheez ke $800$ ps ke muqable mein.

PICTURE. Figure s02 wohi lw bar ko redraw karta hai, ab paanch chhote beats mein slice kiya hua (IF, ID, EX, MEM, WB) jo dashed vertical "clock edge" lines se alag hain. Har slice ek coloured block hai jiska width uski delay hai; sabse tall/wide (blue IF) slice ko flag kiya gaya hai jo clock set karega, yellow banner ke saath jo likha hai "clock fits the tallest slice."

Step 3 — "Sticky note" registers kyun add karne padte hain

WHAT. Ek combinational block (memory, ALU) apna output tabhi dikhata hai jab uske inputs steady held hain. Lekin har clock edge pe hum uske inputs change karte hain agla slice shuru karne ke liye. Toh pehle slice ka result gayab ho jaata. $\text{PC}$ ko bhi yahi problem hai: IF ke dauran compute ki gayi PC+4 value evaporate ho jaati agar hum use PC register mein latch na karein.

WHY. Hum har intermediate result ko ek edge-triggered register mein latch karte hain — ek box jo clock edge pe apna input capture karta hai aur poori agli beat steady hold karta hai. Is tarah ek baad wala slice woh padhh sakta hai jo ek pehle wale slice ne compute kiya. Sticky notes samjho jo time mein aage pass hoti hain. $\text{PC}$ latch address stream ke liye sticky note hai: IF usme PC+4 likhta hai; agar instruction ek branch (EX) ya jump (EX) hai, to wohi PC latch nayi target se overwrite ho jaata hai.

PICTURE. Figure s03 ek value dikhata hai jo ek beat mein janam leti hai (ek ALU output) aur clock edge pe (dashed yellow line) yellow $\text{ALUOut}$ sticky-note box mein "pin" ho jaati hai, taaki agli beat phir bhi use padhh sake. Uske neeche, ek blue box wohi mechanism dikhata hai jo PC+4 ko $\text{PC}$ box mein latch karta hai; arrows har fading combinational output se uske holding register ki taraf point karte hain, note ke saath "next beat can still read it."

Step 4 — Sabse tall step kaun sa hai? (clock period dhundhna)

WHAT. Hum parent ke numbers se har slice ki delay measure karte hain, lekin ab hum har unit ka budget har slice ke critical path pe karte hain — including woh pieces jo parent note quietly chhhod deta hai. Delays: IMem/DMem = 200 ps, RegFile read = RegFile write = 100 ps, ALU / dedicated adder = 200 ps, sign-extension unit ≈ 10 ps, shift-left-2 (woh chhoti wiring/shifter jo do zero bits append karta hai) ≈ 10 ps, aur control FSM (woh finite-state machine jo step decode karta hai aur har mux, register-enable aur ALU-op signal drive karta hai) ≈ 50 ps.

Kyunki control-signal generation aur shift/extend units bhi path pe hain, hum unhe wahan add karte hain jahan woh belong karte hain:

WHY IF ab sabse tall hai. Jab hum PC+4 adder (jo parent note ne omit kiya tha) aur control FSM (woh bhi omit tha) honestly budget karte hain, toh fetch slice — memory read aur increment — critical wala ban jaata hai. Sign-extension aur shift-left-2 units chhote hain (≈10 ps each) lekin hum unhe likhte hain rather than pretend karte ki woh gayab ho jaate hain. Toh: $T_{multi}=\max (450,160,260,250,150)=450\text{ps}$ $\max$ ke neeche har number ek step ki full critical-path delay hai including control logic; $\max$ sabse bada pick karta hai, kyunki clock itni lambi honi chahiye ki worst step bhi fit ho. (Yeh parent note ke simplified $300$ ps se is wajah se alag hai kyunki hum ab adder aur control-logic delays drop nahi karte.)

PICTURE. Figure s04 paanch step delays ko vertical bars ke roop mein plot karta hai; blue IF bar sabse upar $450$ pe pocha hai aur ek dashed yellow line $450$ ps pe woh clock period mark karti hai jo yeh force karta hai. IF bar pe ek pink arrow spell out karta hai "IF = IMem 200 + PC+4 adder 200 + control 50," aur doosre bars pe chhote stacked labels sign-ext/shift/control add-ons dikhate hain.

Step 5 — Alag instructions alag number of beats use karti hain

WHAT. Har instruction ko sirf unhi slices pe map karo jo use sachchi mein chahiye:

WHY R-type MEM skip karta hai. Ek add kabhi data memory nahi chhoota, isliye woh seedha EX (compute) se WB (answer wapas likhna) pe jump karta hai — uska 4th beat WB hai, MEM nahi. Ek common trap yeh sochna hai ki R-type MEM mein likhta hai; nahi likhta, kyunki koi memory kaam nahi hai.

JUMP target kahan compute hota hai. Ek jump ka target address ALU calculation nahi hai — yeh bits ko wires se jod ke banta hai: current PC ke top 4 bits, instruction ke 26 address bits ($\text{IR}[25:0]$, yaani instruction ki lowest 26 wires), aur shift-left-2 unit se append kiye do zero bits, sab milake ek 32-bit address banta hai. Yeh assembled target EX mein $\text{PC}$ latch mein likha jaata hai — yahi exact wajah hai ki j ko EX beat tak pahunchna padta hai aur isliye 3 beats chahiye, isse kam nahi.

PICTURE. Figure s05 ek row dikhata hai har instruction ke liye (lw, sw, add, beq, j); har row mein paanch cells hain IF ID EX MEM WB label kiye. Filled blue cells use hone wale beats hain, hatched empty cells skip steps hain, aur beat count (5, 4, 4, 3, 3) har row ke right pe call out kiya gaya hai, note ke saath ki j EX mein PC update karta hai.

Apni understanding reveal karo:

Step 6 — Beats ko real time mein convert karo (CPI weighting)

WHAT. Ek real instruction mix lo aur average beats per instruction compute karo, phir real time ke liye $T_{multi}$ se multiply karo.

WHY multiply. Time = (beats ki ginti) × (ek beat ki length). CPI average beats hai; $T_{multi}$ beat length hai; unka product average time per instruction hai.

WORKED (parent's 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)=4.05$ Har term $f_i\times c_i$ hai; sum karne pe $4.05$ average beats per instruction milte hain.

PICTURE. Figure s06 har type ka contribution $f_i{c}_i$ ek coloured slab ke roop mein stack karta hai (lw 1.25, sw 0.40, R 1.80, beq 0.45, j 0.15); stack ki total height ek dashed yellow CPI = 4.05 line se mark hoti hai, har slab apne $f_i\times c_i$ arithmetic ke saath labelled hai.

Step 7 — Honest edge case: multi-cycle slower bhi ho sakta hai

WHAT. $N$ instructions ke ek program ke liye total time compare karo, jahan $N$ = execute ki gayi instructions ki total ginti (wohi program dono machines pe chalta hai, isliye $N$ dono ke liye same hai). Hamare fully-budgeted $T_{multi}=450$ ps use karke: $\frac{T_{single}\text{-total}}{T_{multi}\text{-total}}=\frac{N\cdot 800}{N\cdot \text{CPI}\cdot T_{multi}}=\frac{800}{4.05\times 450}=\frac{800}{1822.5}\approx 0.439$ $N$ cancel ho jaata hai kyunki dono ke liye same hai. $800$ ps single-cycle time per instruction hai; $4.05\times 450=1822.5$ ps multi-cycle time per instruction hai.

WHY < 1 means slower. 1 se neeche ratio bolta hai ki single-cycle kam time mein finish karta hai yahan. Culprit unbalanced $450$-ps IF step hai (memory read + PC+4 adder + control ek hi path pe) — jab tum sab kuch budget karte ho, to fetch stage dominate karta hai aur multi-cycle is mix ke liye raw time pe slower hota hai. Multi-cycle ki guaranteed jeet hai kam hardware (ek shared ALU, ek shared memory); iska speed jeetna chahta hai balanced steps ya memory delay jo baaki sab se baddi ho.

PICTURE. Figure s07 do per-instruction times ko side by side rakhta hai — grey single-cycle bar (800) clearly shorter pink multi-cycle bar (1822.5) se — ek yellow arrow ke saath jo unbalanced IF stage (aur newly-counted PC+4 adder aur control logic) ko reason ke roop mein flag karta hai.

Ek-picture summary

Figure s08 poori derivation ko ek board pe compress karta hai: upar lamba grey single-cycle bar (800 ps); uske neeche multi-cycle version paanch chhote beats mein slice kiya hua jiske beech yellow sticky-note registers pinned hain; ek arrow sabse tall slice (IF = 450, jab PC+4 adder aur control logic count hote hain) ko mark karta hai jo clock set karta hai; aur bottom line humein yaad dilati hai ki pakka jeet shared ALU aur memory hai, raw speed nahi.

Yeh bhi dekho

• Single-cycle datapath — woh slower-clock baseline jise humne improve kiya.
• Pipelining — agla idea: slices ko overlap karo taaki kai instructions ek saath chalein.
• Control unit — FSM vs microprogramming — har step ke control signals kaise generate hote hain (woh FSM jiska delay humne budget kiya).
• CPI and CPU performance equation — time = instructions × CPI × period framework.
• ALU design · Memory hierarchy — woh shared units jo yeh design reuse karta hai.