Single-cycle datapath design: Exercises — Hinglish deep dive

5.2.1 · D4 · Hardware › Processor Datapath & Pipelining › Single-cycle datapath design

Is page mein single-cycle datapath design ki machinery test hoti hai. Timing ke ideas aage Pipelining aur Multi-cycle datapath mein kaam aate hain; delay-summing logic Performance equation ka seed hai.

Poore page mein use hone wale timing symbols (saare picoseconds mein, abbreviated $ps$ — ek trillionth of a second):

Level 1 — Recognition

Problem 1.1

Classic single-cycle MIPS datapath ke chaar muxes ke naam batao aur ek-ek phrase mein bolo ki har ek kaunse do inputs ke beech choose karta hai.

Recall Solution 1.1

Mux (multiplexer) ek hardware switch hai: kai data inputs, ek output, aur ek select line jo decide karti hai ki kaunsa input pass hoga. Yeh theek wahan hota hai jahan do instruction types ek block ko feed karne ke baare mein disagree karti hain.

ALUSrc mux — ALU ka 2nd operand choose karta hai: ==register rt value ya sign-extended immediate==.
MemToReg mux — choose karta hai ki register mein kya write-back hoga: ALU result ya data-memory output.
RegDst mux — destination register field choose karta hai: ==rd (R-type) ya rt (I-type)==.
PCSrc mux — next PC choose karta hai: ==PC+4 ya branch target==.

Problem 1.2

Ek sw (store word) instruction ke liye, har control signal ki value batao: RegWrite, ALUSrc, MemRead, MemWrite, Branch.

Recall Solution 1.2

Socho "store ko kya chahiye?" Store ek address compute karta hai (base + offset) aur ek register ki value memory mein likhta hai. Yeh koi register result produce nahi karta.

RegWrite = 0 (kuch bhi register mein wapas nahi jaata).
ALUSrc = 1 (ALU ka 2nd input sign-extended offset hai, koi register nahi).
MemRead = 0 (hum memory read nahi kar rahe).
MemWrite = 1 (hum memory WRITE kar rahe hain).
Branch = 0 (store kabhi PC redirect nahi karta).

Level 2 — Application

Problem 2.1

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$ (saare ps mein) diye hain, har instruction ka total path delay compute karo aur required clock period batao.

Recall Solution 2.1

Har instruction ko sirf unhi blocks se walk karwao jo woh actually use karta hai, delays sumate karte jao.

R-type (no memory): $200 + 100 + 200 + 0 + 100 = 600$ ps.
lw (sab kuch use karta hai): $200 + 100 + 200 + 200 + 100 = 800$ ps.
sw (no write-back): $200 + 100 + 200 + 200 = 700$ ps.
beq (sirf compare, no memory/no write-back): $200 + 100 + 200 = 500$ ps.

Clock period saari instructions ka max hota hai (single-cycle ek shared period force karta hai): $T_{c l k} = max (600, 800, 700, 500) = 800 ps .$

Upar ke bars mein har instruction ka path dikhaya gaya hai; sabse lamba (lw) dashed red clock line set karta hai jiske against baaki saari instructions measure hoti hain.

Problem 2.2

2.1 se $T_{c l k} = 800$ ps use karke, CPU ki clock frequency GHz mein compute karo, aur $2 \times 1 0^{6}$ instructions wale program ka execution time nikalo.

Recall Solution 2.2

Frequency period ka reciprocal hoti hai. $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 Performance equation use karta hai $CPI = 1$ ke saath (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

Ek student propose karta hai ki gates bachane ke liye PC+4 compute karne ke liye alag adder ki jagah main ALU reuse karo. Timing terms mein explain karo yeh single-cycle design ko kyun tod deta hai.

Recall Solution 3.1

Single-cycle mein, ek instruction ka saara kaam ek clock cycle mein hota hai. Us cycle ke dauran ALU already apna arithmetic (ya branch/address) compute karne mein busy hai. Usi ALU par PC+4 compute karne ke liye ALU ko ek cycle ke andar sequentially do additions karni padtein — lekin ise schedule karne ke liye koi doosra sub-cycle nahi hai. Concretely, path ban jaata $t_{A LU}$ (PC+4 ke liye) phir $t_{A LU}$ (instruction ke liye), ALU term double ho jaata aur critical path lambi ho jaati. Dedicated adder parallel mein chalta hai, isliye PC+4 ka $t_{a dd}$ fetch/decode delays ke saath overlap karta hai (unke peechhe chhup jaata hai) aur ALU ko kabhi nahi chhoota. Isliye: alag adder, ALU nahi.

Problem 3.2

Problem 2.1 ke delays lo lekin ALUSrc path par $t_{m ux} = 30$ ps aur MemToReg path par mux delay add karo, aur ek sign-extend delay $t_{se x t} = 20$ ps jo ALUSrc mux ko feed karti hai. lw ka critical path recompute karo.

Recall Solution 3.2

lw ke signal ko edge by edge trace karo. Registers read hone ke baad (ya immediate sign-extend hone ke baad, jo bhi ALU ke 2nd input par ho), value ALU tak pahunchne se pehle ALUSrc mux se guzarti hai; data memory ke baad value write-back se pehle MemToReg mux se guzarti hai.

Path ka 2nd-operand branch hai $t_{R e g R e a d} = 100$ vs. $t_{se x t} = 20$ ; slow wala mux ko gate karta hai, isliye hum $max (100, 20) = 100$ lete hain. Phir: $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 .$ Do 30 ps muxes period ko 800 se 860 ps par push kar dete hain — muxes free nahi hote.

Level 4 — Synthesis

Problem 4.1

Ek naye instruction lui rt, imm ("load upper immediate": 16-bit immediate ko register rt ke high half mein place karo, low half mein zeros) ke liye control-signal row design karo. Assume karo ki tum ek small shifter add karte ho jo immediate ko 16 bits left shift karta hai aur ise MemToReg mux mein third input ke roop mein route karo. RegWrite, ALUSrc, MemRead, MemWrite, Branch, RegDst do, aur MemToReg describe karo.

Recall Solution 4.1

Poochho lui ko kya chahiye: yeh ek register (rt) mein likhta hai, yeh data memory ko nahi touch karta, aur yeh branch nahi karta. Jo value likhi jaati hai woh shifted immediate hai — na ALU result na memory output — isliye MemToReg mux ko naya shifted-immediate input select karna hoga.

RegWrite = 1 (result rt mein jaata hai).
ALUSrc = X (don't care — ALU output use nahi hota; lekin agar reuse karein, immediate feed karna harmless hai, toh 1 ya X chhod do).
MemRead = 0.
MemWrite = 0.
Branch = 0.
RegDst = 0 (destination rt hai, I-type field).
MemToReg = shifted-immediate input select karo (naya 3rd mux position).

Key insight: lui ek register-writing instruction hai jo ALU-result aur memory dono paths ko bypass karta hai — exactly woh "instructions disagree" situation jo MemToReg mux ko wider karne ko justify karti hai.

Problem 4.2

Suppose hum ek mul instruction add karte hain jiska ALU stage $t_{A LU}^{m u l} = 500$ ps chahta hai (baaki ke 200 ps vs.). 2.1 ke base delays use karke, mul ka path compute karo (R-type shape: no memory) aur naya clock period, aur kitne percent baaki saari instructions slow hoti hain.

Recall Solution 4.2

mul ka R-type shape hai (fetch, read, execute, write-back — no memory): $T_{m u l} = 200 + 100 + 500 + 100 = 900 ps .$ Naya clock period $= max (800, 900) = 900$ ps. Ab har instruction 900 ps par chalta hai. Purane 800 ps ke against percentage slowdown: $\frac{900 - 800}{800} \times 100% = 12.5%.$ Ek slow instruction sabko $12.5%$ ka tax lagaata hai — yeh woh core weakness hai jo single-cycle inherit karta hai aur Pipelining fix karta hai.

Level 5 — Mastery

Problem 5.1

Ek colleague argue karta hai: "Single-cycle ka CPI = 1 hai, theoretical minimum. Isliye yeh sabse fast possible design hai." Is baat ko Performance equation use karke rigorously refute karo, aur woh condition batao jisme Multi-cycle datapath ya Pipelining design jeetata hai.

Recall Solution 5.1

Performance is se govern hoti hai: $T_{p r o g} = N \times CPI \times T_{c l k},$ jahan $N$ = instruction count, CPI = cycles per instruction, $T_{c l k}$ = clock period. Teen factors hain, sirf ek nahi. Single-cycle CPI ko minimize karke 1 karta hai lekin iske badle mein bahut bada $T_{c l k}$ (sabse slow instruction se set, jaise 800 ps) aata hai.

Multi-cycle design har instruction ko chhoti cycles mein todta hai, isliye $T_{c l k}$ shrink hoti hai (sabse slow single stage tak, ~200 ps) lekin CPI 1 se upar jaata hai (har instruction kai cycles leta hai). Yeh tab jeetata hai jab $T_{c l k}$ mein kami CPI mein bari se zyada ho, yaani jab $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 aur bhi achha karta hai: yeh CPI $\approx 1$ rakhta hai (steady state mein ek instruction per cycle finish hoti hai) jabki $T_{c l k}$ sabse slow stage ke paas chalaata hai. Toh pipelining generally single-cycle ko CPI $\times T_{c l k}$ ke product par beat karta hai, jo actually matter karta hai. CPI = 1 akele kuch prove nahi karta.

Problem 5.2

Concrete showdown. Single-cycle: $T_{c l k} = 800$ ps, CPI = 1. Unhi stages se bana ek 5-stage pipeline $T_{c l k} = 200$ ps (sabse slow stage) par run karta hai aur effective CPI 1.25 hai (hazards/stalls account karke). $N = 1 0^{6}$ instructions ke program ke liye, har execution time compute karo aur speedup nikalo.

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 .$ 1.25 ke CPI ke saath bhi (single-cycle ke 1 se worse), pipeline 3.2× faster hai kyunki iska clock period 4× chhota hai. Yahi wajah hai ki Performance equation sirf CPI se judge karne ke against warn karta hai.

Bar chart dono total times contrast karta hai; pipeline bar single-cycle bar ka ek fraction hai apne zyada CPI ke bawajood.

Recall Ek-line self-check

Woh single number jo program ki runtime decide karta hai ::: product $N \times CPI \times T_{c l k}$ , kabhi CPI akele nahi.