Exercises — Multi-cycle datapath

(a) IR IF mein write hota hai — yeh raw instruction bits Memory[PC] hold karta hai. (b) A and B ID mein write hote hain — yeh do source-register values Reg[rs], Reg[rt] hold karte hain. (c) ALUOut pehli baar ID mein write hota hai — yeh speculatively pre-computed branch target PC + (sign-ext(imm) << 2) hold karta hai. (Yeh R-type/address results ke liye EX mein dobara write hota hai — lekin pehla write ID mein hota hai.) (d) MDR MEM mein write hota hai — yeh lw ke dauran memory se padha gaya data hold karta hai. Yeh ordering kyun? Har register ek "sticky note" hai jo clock edge se pehle ek combinational value pakadta hai, taaki baad ka cycle use padh sake.

(a) add = 4 (IF ID EX WB — koi memory nahi). (b) lw = 5 (IF ID EX MEM WB — akela 5-cycle instruction). (c) sw = 4 (IF ID EX MEM — MEM mein khatam, koi write-back nahi). (d) beq = 3 (IF ID EX — PC, EX mein update hota hai). (e) j = 3 (IF ID EX — PC, EX mein update hota hai).

• IF = $200$ ps. Kyun? IF mein do cheezein parallel mein hoti hain: memory read IR ← Memory[PC] (200 ps) aur ALU par PC+4 add (200 ps). Kyunki yeh independent hardware par same time par run hote hain — memory IR ko feed karta hai jabki ALU PC ko feed karta hai — stage delay dono ka maximum hoti hai, $\max (200,200)=200$ ps, na ki unka sum. Yeh ID (neeche) se crucial difference hai, jahaan do operations chained hain.
• ID = RegFile read $(100)$ phir ALU branch-target calc $(200)$ sequence mein same cycle mein $=100+200=300$ ps. Yahan ALU ko register-read result input ke roop mein chahiye, toh use wait karna padta hai — delays add hoti hain.
• EX = ALU = $200$ ps.
• MEM = memory access = $200$ ps.
• WB = RegFile write = $100$ ps. Clock ko worst step fit karni chahiye, toh $T_{step}=\max (200,300,200,200,100)=300$ ps. ID kyun dominate karta hai: yeh ek register read aur ek ALU op ko chain karta hai (ek doosre ko feed karta hai), toh unki delays add hoti hain; IF isse bachta hai kyunki uska memory read aur PC+4 add independent aur parallel hain.

lw 5 cycles use karta hai: $5\times 300=1500$ ps. Single-cycle lw = $800$ ps. Toh lw akele ke liye, multi-cycle slower hai ($1500>800$). Yeh step kyun: execution time = cycles × period. Clock speeds compare mat karo; times compare karo.

beq 3 cycles use karta hai: $3\times 300=900$ ps. Yeh single-cycle ke 800 ps ke kareeb hai, lekin yahan thoda slower hai kyunki $T_{step}=300$ perfectly balanced nahi hai.

$\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=4.05$ Har term kyun: yeh $f_i\times c_i$ hai — program ka woh fraction jo type $i$ ka hai, multiply by us type ka cycle count. Saare types par sum karne se cycles ki weighted average milti hai jo ek "typical" instruction mein lagti hai.

$\frac{T_{single}}{T_{multi}}=\frac{N\cdot 800}{N\cdot 4.05\cdot 300}=\frac{800}{1215}\approx 0.66$ Kyunki $0.66<1$, multi-cycle inhi numbers ke liye raw time mein slower hai. Kyun: ID stage (300 ps) unbalanced hai — yeh clock period par kabza kar leti hai jabki doosri stages us period ka 100–200 ps waste karti hain. Multi-cycle ka guaranteed benefit yahan kam hardware (shared ALU aur unified memory) hai, speed nahi.

Break-even: $4.05\cdot T_{step}=800\Rightarrow T_{step}=800/4.05\approx 197.5$ ps. Toh multi-cycle single-cycle ko tabhi beat karta hai jab worst step ≈197.5 ps se neeche aaye. Kyunki ek memory access already 200 ps leta hai, yeh practically impossible hai jab tak hum CPI ya memory delay bhi kam na karein. Yeh quantify karta hai ki yeh particular machine speed mein kyun harti hai. Yeh step kyun: donon program-times ko equal set karo aur unknown ke liye solve karo — classic break-even technique.

beq IF, ID, EX use karta hai — ALU teeno mein kaam karta hai:

• IF: operands = PC aur 4 → result PC+4, PC mein latch hota hai (default next instruction). Yeh ALU add memory read IR ← Memory[PC] ke parallel mein run karta hai, toh IF stage ko 200 ps se aage nahi badhaata (dekho L2-Q1).
• ID: operands = PC aur sign-ext(imm) << 2 → result = branch target, ALUOut mein speculatively latch hota hai.
• EX: operands = A aur B → ALU $A=B$ test karne ke liye subtract karta hai; agar zero-flag set ho, toh PC ← ALUOut (ID se target). Teeno uses kyun: multiplexers har cycle mein single shared ALU ke inputs re-route karte hain — wahi reuse multi-cycle ka point hai. (Figure dekho.)

(a) $\text{CPI}=0.50(4)+0.40(5)+0.10(3)=2.0+2.0+0.3=4.3$. (b) Time per instruction $=4.3\times 300=1290$ ps. (c) $1290>800$, toh multi-cycle abhi bhi slower hai — memory-heavy lw fraction CPI ko upar push karta hai, neeche nahi. Kyun: zyada lw matlab zyada 5-cycle instructions, CPI badhta hai. Multi-cycle tabhi help karta hai jab step delay ka advantage cycle-count penalty se zyada ho — jo yahan nahi hota.

sw memory likhta hai: MEM mein yeh Memory[ALUOut] ← B karta hai. Uska kaam — ek register value ko memory mein move karna — ek baar memory likh jaane par complete ho jaata hai. Koi register update nahi karna, toh WB nahi. lw memory padhta hai: MEM mein yeh MDR ← Memory[ALUOut] karta hai, data ko MDR mein capture karta hai. Lekin destination ek register hai, aur register file sirf ek alag cycle mein write ho sakti hai (WB): Reg[rt] ← MDR. Isliye lw ko extra 5th step chahiye. Asymmetry kyun: store ka destination memory hai (MEM mein likha jaata hai); load ka destination register hai (WB mein likha jaata hai). Data flow ki direction last step decide karti hai.

New cycle counts (har ek +1): lw=6, sw=5, R-type=5, beq=4, j=4. (a) ${\text{CPI}}_{new}=0.25(6)+0.10(5)+0.45(5)+0.15(4)+0.05(4)$ $=1.50+0.50+2.25+0.60+0.20=5.05$. (b) Time/instr $=5.05\times 200=1010$ ps. (c) single-cycle ke muqable: $800/1010\approx 0.79$ → abhi bhi single-cycle se slower, lekin kareeb. (d) original multi-cycle ke muqable: $1215/1010\approx 1.20$ → rebalanced machine original multi-cycle se 20% faster hai. Trade-off kyun matter karta hai: clock ko shorten karna (300→200) extra cycle ki cost se multi-cycle family ke andar zyada compensate kar gaya, even though na hi single-cycle ko beat kar saka is mix par. Yahi exact tension hai jo pipelining resolve karta hai — dekho Pipelining.

Multi-cycle yahan jeetata hai — lekin hardware ke liye, speed ke liye nahi. Reasoning:

• Workload memory-heavy hai, toh CPI high hai (bahut saare 4–5 cycle instructions) → multi-cycle ka time advantage weak hai (humne 0.66–0.79 speedups dekhe, matlab slower).
• Lekin constraint transistor budget hai. Multi-cycle ek unified memory aur ek shared ALU cycles mein use karta hai, jabki single-cycle ko separate I/D memories aur aksar multiple adders chahiye. Yeh ek chhoti chip ke liye decisive saving hai.
• Full Pipelining best throughput deta lekin sabse zyada hardware cost karta (pipeline registers, forwarding, hazard logic) — chhote budget ke liye galat. Conclusion: multi-cycle choose karo: uska defining benefit — hardware reuse — binding constraint se match karta hai. Throughput trade-off ke liye CPI and CPU performance equation dekho aur multi-step control kaise build hota hai uske liye Control unit — FSM vs microprogramming dekho.

Equal instruction counts $N$ cancel ho jaate hain: $T_{multi}<T_{single}⟺\text{CPI}\cdot T_{step}<T_{single}⟺T_{step}<\frac{T_{single}}{\text{CPI}}.$ $T_{single}=800$, CPI $=4.05$ ke saath: $T_{step}<800/4.05\approx 197.5$ ps chahiye (L3-Q3 se match karta hai). General rule: multi-cycle tabhi jeetata hai jab longest step single-cycle period divided by average cycle count se chhota ho. Kyun: yeh sirf "program time smaller" hai $N$ divided out ke saath — poore trade-off ka sabse clean statement.

Multi-cycle clock period longest single step ki delay ke barabar hoti hai. Program time = N × CPI × T_step. R-type ke chaar steps hain IF, ID, EX, WB (yeh MEM skip karta hai). Multi-cycle single-cycle ko tabhi beat karta hai jab $T_{step}<$ T_single / CPI. Multi-cycle ko sirf one (unified) memory chahiye kyunki IF aur MEM alag cycles mein hote hain.