Worked examples — Multi-cycle datapath

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

Yeh parent topic ki ek child page hai. Parent ne kyun aur paanch steps build kiye the. Yahaan hum har tarah ke question drill karte hain jo exam mein aa sakte hain — har instruction type, har degenerate case (zero delays, balanced vs unbalanced stages), limiting behaviour, ek real-world word problem, aur ek nasty exam twist.

Shuru karne se pehle, parent note ka ek waada jo hum nibhaate rahenge: ek instruction exactly utne hi cycles leta hai jitna kaam usse karna hai, aur clock period sabse lamba single step hoti hai, poora path kabhi nahi. Agar koi symbol naya mile, hum usse wahi pe define kar denge.

---

Vocabulary jo hume kisi bhi example se pehle fix karni hai

Parent note mein IR, A, B, IR[15:11], PC, aur "sign-ext" jaisi terms freely use ki gayi thi. Inhe cold mein dekhne wala koi bhi confuse ho jaata. Toh hum har ek ko yahaan, ek baar, define karte hain — aur phir har example sirf inhe use karta hai.

---

Scenario matrix

Cell	Kya special hai	Kis example mein covered hai
C1 R-type, normal	4 cycles, MEM skip karta hai	Example 1
C2 lw, the long one	saare 5 cycles	Example 2
C3 sw, MEM pe khatam hota hai	4 cycles, no WB	Example 3
C4 beq, EX pe khatam hota hai	3 cycles, branch taken vs not	Example 4
C5 j, 3 kyun 2 nahi	PC EX mein likha jaata hai	Example 5
C6 Degenerate: balanced stages	jab multi-cycle jeet jaata hai	Example 6
C7 Limiting: memory dominates	memory delay ≫ others	Example 7
C8 Zero/degenerate delay	ek unit ka delay 0 ps hai	Example 8
C9 Real-world word problem	mixed program, wall-clock time	Example 9
C10 Exam twist	"ek step add karo" / hidden trap	Example 10

Neeche ke har numeric answer ko verify block mein machine-check kiya gaya hai.

Do symbols jinka hum baar baar use karenge, ek baar define kar lete hain:

Agar koi problem override na kare, hum parent ke component delays reuse karte hain:

Neeche ki picture dekho — yeh "ruler" hai jiske against har example measure hota hai.

---

Example 1 — R-type add (Cell C1)

1. List karo add ko kya kaam chahiye. IF (IR mein instruction laao), ID (A mein $t1,‘B‘mein$t2 padho), EX (ALU add kare), WB (sum store karo). Yeh data memory kabhi read ya write nahi karta. Yeh step kyun? Hum cycles count karte hain required work ke hisaab se, defined steps ki sankhya se nahi — yeh parent ka "no dummy cycles" rule hai.
2. Toh yeh MEM skip karta hai. Cycle count $=4$: IF, ID, EX, WB (not MEM). Yeh step kyun? MEM sirf un instructions ke liye exist karta hai jo data memory touch karte hain; add nahi karta, toh uska 4th cycle WB hai.
3. Kaun sa register? EX mein sum ALUOut mein land karta hai (woh sticky-note register jo clock edge survive karta hai). WB mein, Reg[IR[15:11]] $\leftarrow$ ALUOut — yaani sum us register mein jaata hai jo rd field $\text{IR}[15:11]$ ke naam se pehchana jaata hai (yahaan $t0). Yeh step kyun? Combinational ALU output edge pe vanish ho jaata hai, toh EX usse ALUOut mein latch karta hai taaki WB next cycle mein padh sake.
4. Time. $4\times 300=1200$ ps. Yeh step kyun? Execution time = cycles × period.

---

Example 2 — lw the long instruction (Cell C2)

1. Kaam kya chahiye: IF, ID, EX ($t1+8$ address compute), MEM (data memory padho), WB ($t0 mein likho). Saare paanch steps. Yeh step kyun? lw ek aisa instruction hai jo har canonical step use karta hai, isliye 5 cycles.
2. Register trail: IF→IR ko 32 instruction bits milte hain (aur PC ko PC+4); ID→A ko Reg[$\text{IR}[25:21]$] = Reg[$t1$] milta hai; EX→ALUOut ko effective address $A+\text{sign-ext}(\text{IR}[15:0])$ = $t1+8$ milta hai; MEM→MDR ko Memory[ALUOut] milta hai; WB→Reg[$\text{IR}[20:16]$] = Reg[$t0$] $\leftarrow$ MDR. Yeh step kyun? Har sticky-note register ek value ek cycle aage carry karta hai. MDR = Memory Data Register; note karo lw ka destination rt field $\text{IR}[20:16]$ hai, rd nahi.
3. Time. $5\times 300=1500$ ps. Yeh step kyun? cycles × period.

---

Example 3 — sw MEM pe finish hota hai (Cell C3)

1. Kaam chahiye: IF, ID, EX (address = $t1+8$ via $A+\text{sign-ext}(\text{IR}[15:0])$), MEM (B mein value memory mein likho). Yeh step kyun? ID ke dauran, sw register $t0ko‘B‘meinreadkartahai($\text{IR}[20{:}16]$ ke zariye); MEM mein B ki woh value Memory[ALUOut] mein push hoti hai.
2. No WB. Ek store register file ke liye koi result produce nahi karta — write back karne ke liye kuch nahi. Toh yeh MEM pe khatam: 4 cycles. Yeh step kyun? WB sirf register update karne ke liye exist karta hai; sw memory update karta hai, register nahi.
3. Time. $4\times 300=1200$ ps.

---

Example 4 — beq, taken vs not taken (Cell C4)

1. PC IF mein already advance ho chuka hai. IF mein hi, ALU ne $\text{PC}\leftarrow \text{PC}+4$ compute kiya aur PCSrc ne woh value choose ki — toh PC already fall-through instruction par point kar raha hai isse pehle ki hume pata chale yeh ek branch hai. Yeh step kyun? Isliye not-taken branch ko baad mein koi extra kaam nahi karna: default IF mein hi ho gaya tha.
2. Target ID mein pre-computed. Step ID mein, jab ALU idle hai, ALUOut $\leftarrow \text{PC}+(\text{sign-ext}(\text{IR}[15:0])\ll 2)$. Yeh optimistic pre-computation hai. Yeh step kyun? Target ko jaldi compute karne ka matlab hai ki branch taken ho toh koi extra cycle nahi chahiye. $\ll 2$ word offset ko byte offset mein badalta hai.
3. Decision EX mein. EX mein ALU $A-B$ compute karta hai (matlab Reg[$t0$] − Reg[$t1$]); agar $A=B$ toh PCSrc mux PC+4 se ALUOut par flip ho jaata hai, toh PC $\leftarrow$ ALUOut. Yeh step kyun? Equality ek subtraction check hai; ALU yeh karta hai, aur PC (conditionally) PCSrc ke zariye usi cycle mein rewrite ho jaata hai.
4. (a) Taken = 3 cycles (IF ID EX). (b) Not-taken = bhi 3 cycles — PC ko PC+4 IF mein hi mil gaya tha (step 1), toh aur kuch nahi chahiye. Dono 3 hain. Yeh step kyun? Chahe hum PC overwrite karein ya nahi, instruction EX pe hi khatam hoti hai; kaam length mein identical hai.
5. Time (dono): $3\times 300=900$ ps.

Neeche ki figure dono paths side by side dikhati hai — ise do timelines ki tarah padhein ek ke upar ek stacked:

---

Example 5 — j ko 3 cycles chahiye, 2 nahi (Cell C5)

1. PC EX mein likha jaata hai. Parent ka rule: jump ke liye, PCSrc mux jump address select karta hai, toh PC $\leftarrow \{\text{PC}[31:28],\text{IR}[25:0],00\}$ EX step mein hota hai (yeh PC ke top 4 bits, 26-bit target field $\text{IR}[25:0]$, aur do zero bits jodta hai). Yeh step kyun? Datapath ka control FSM jump-target ko PC mein (PCSrc ke zariye) sirf EX state ke dauran route karta hai; koi pehle wala path nahi hai.
2. Toh isko IF, ID, EX = 3 cycles chahiye. ID phir bhi traverse hoti hai (decode + register fetch har instruction ke liye blindly hota hai, kyunki hume type tab tak pata nahi jab tak decode khatam na ho). Yeh step kyun? ID unconditional hai — CPU kisi instruction ko decode karna skip nahi kar sakta jise usne abhi decode hi nahi kiya.
3. Time. $3\times 300=900$ ps.

---

Example 6 — Jab multi-cycle actually JEET JAATA HAI (balanced stages) (Cell C6)

1. Pehle CPI. $\text{CPI}=0.25(5)+0.10(4)+0.45(4)+0.15(3)+0.05(3)$. Yeh step kyun? Frequency × cycle-count, summed — CPI ki definition.
2. Compute karo. $=1.25+0.40+1.80+0.45+0.15=4.05$. Yeh step kyun? Same mix hai parent ki tarah, toh same CPI = 4.05; sirf period badla.
3. Speedup $=\frac{N\cdot 800}{N\cdot 4.05\cdot 200}=\frac{800}{810}\approx 0.988$. Yeh step kyun? $T_{\text{single}}/T_{\text{multi}}$ jahan $T_{\text{multi}}=\text{CPI}\times T_{\text{step}}$; same $N$ instructions upar aur neeche cancel ho jaate hain.

---

Example 7 — Limiting case: memory dominates (Cell C7)

1. Single-cycle lw $=500+100+100+500+100=1300$ ps. Yeh step kyun? Poora worst-case path: IMem + RegFile read + ALU + DMem + RegFile write.
2. Multi-cycle step delays: IF=500, ID=RegFile read(100)+ALU(100)=200, EX=100, MEM=500, WB=100. Sabse lamba = 500 ps. Yeh step kyun? Clock worst single step fit karta hai; yahaan memory-access steps (IF, MEM) 500 par tie karte hain.
3. CPI = 4.05 (same mix). Time per instruction $=4.05\times 500=2025$ ps. Yeh step kyun? CPI × period.
4. Speedup $=\frac{1300}{2025}\approx 0.642$. Yeh step kyun? $T_{\text{single}}/T_{\text{multi}}$.

---

Example 8 — Zero / degenerate delay (Cell C8)

1. Step delays recompute karo. IF=200, ID=0+200=200, EX=200, MEM=200, WB=0. Yeh step kyun? Har step ki delay us mein use hone wale functional-unit delays ka sum hai; RegFile ab dono apne read (ID mein) aur apne write (WB mein) mein 0 contribute karta hai.
2. Naya period $=\max (200,200,200,200,0)=200$ ps. Yeh step kyun? Clock = longest step. 100 ps register read hatane se ID 300 se 200 ho jaata hai, toh poora clock 200 pe aa jaata hai.
3. Cycle counts unchanged. Zero delay steps remove nahi karta — WB abhi bhi exist karta hai (bas 0 ps kharcha hai), toh add abhi bhi 4 cycles ka hai. Yeh step kyun? Cycle count required work ke baare mein hai, kitni tez ek unit hai nahi. Ek 0-ps step FSM mein abhi bhi ek step hai.

---

Example 9 — Real-world word problem (Cell C9)

1. Total cycles $=N\times \text{CPI}=1,000,000\times 4.05=4,050,000$ cycles. Yeh step kyun? $N$ instruction count hai; CPI cycles-per-instruction hai, toh unka product total cycles hai.
2. Multi-cycle wall time $=4,050,000\times 300\text{ ps}=1,215,000,000$ ps. Convert karo: $1\mu \text{s}=10^6$ ps, toh $1,215,000,000/10^6=1215\mu \text{s}$. Yeh step kyun? Total time = total cycles × clock period; phir hum ps → µs mein convert karte hain $10^6$ se divide karke, kyunki ek microsecond ek million picoseconds hota hai.
3. Single-cycle wall time $=N\times 800\text{ ps}=1,000,000\times 800=8\times 10^8$ ps $=800\mu \text{s}$. Yeh step kyun? Single-cycle har instruction ke liye 800 ps par 1 cycle karta hai.
4. (c) Compare karo. Single-cycle (800 µs) yahaan multi-cycle (1215 µs) se fast hai; ratio $=800/1215\approx 0.658$, yaani multi-cycle lagbhag $1/0.658\approx 1.52\times$ zyada time leta hai. Yeh step kyun? Same speedup ratio hai jaise parent Example 3 mein, kyunki same mix aur same periods hain — ab ek million instructions par scale ho gaya.

---

Example 10 — Exam twist: ek hidden extra stage (Cell C10)

1. Kya clock badlega? Naya stage = 150 ps, jo current maximum se kam hai (ID = 300 ps). Toh $T_{\text{step}}$ 300 ps rehta hai. Yeh step kyun? Clock = sabse lamba single step; ek stage jo current champion se chhoti ho woh maximum nahi badha sakti.
2. Kya add ka cycle count badlega? Haan — ab har instruction ka ek aur mandatory step hai. add: IF, ID, new-stage, EX, WB = 5 cycles. Yeh step kyun? Twist kehta hai yeh stage har instruction ke liye mandatory hai, toh yeh har ek mein exactly ek cycle add karta hai, type chahe kuch bhi ho.
3. add ka naya time $=5\times 300=1500$ ps (pehle 1200 tha). Yeh step kyun? cycles × period; count 4→5 gaya jabki period 300 par raha.

---

Recall gauntlet

Recall

add 4 cycles kyun leta hai, 5 nahi? Yeh MEM skip karta hai (data-memory access nahi); iske 4 cycles hain IF, ID, EX, WB. ::: correct add ek step kyun skip karta hai? ::: R-type data memory kabhi touch nahi karta, toh yeh MEM omit karta hai aur WB mein write back karta hai. sw = 4 cycles aur lw = 5 kyun? ::: sw mein koi WB nahi (register mein likhne ke liye kuch nahi); lw loaded data write back karta hai, WB ki zaroorat hai. j ko 3 cycles chahiye, 2 nahi, kyun? ::: PC EX step ke dauran likha jaata hai (PCSrc jump address select karta hai), toh jump ko EX tak pahunchna padta hai. Multi-cycle clock period kya set karta hai? ::: Sabse lambe single step ki delay, poora instruction path nahi. Default machine mein kaun sa step bottleneck hai aur kyun? ::: ID = 300 ps, kyunki woh ek cycle mein RegFile read (100) aur ALU branch-target calc (200) karta hai. Kya 0-ps functional unit cycle counts kam karta hai? ::: Nahi — yeh sirf clock period chhota karta hai; step FSM mein abhi bhi exist karta hai. Sign-ext kya karta hai aur kaun sa unit yeh perform karta hai? ::: 16-bit number ka top sign bit upper 16 bits mein copy karta hai 32-bit value banane ke liye; ek fixed sign-extend wiring block, ALU nahi. IR[15:11] kya name karta hai? ::: rd field — R-type instruction ke liye destination register. PC register kya hai? ::: Program Counter — ek dedicated 32-bit register jo current instruction ka memory address hold karta hai. PC+4 kahan aur kyun compute hota hai? ::: IF mein, idle ALU use karke; +4 kyunki instructions 4 bytes ke hain, toh PC phir default next instruction par point karta hai. PCSrc mux kiske beech choose karta hai? ::: PC+4 (default, IF), branch target ALUOut (taken beq, EX), aur jump address (j, EX). Single-cycle ke upar multi-cycle ka guaranteed advantage kya hai? ::: Kam hardware — ek shared ALU aur ek unified memory alag cycles mein use hoti hai.

---

Aage kahan jaayein

• Parent topic par wapas jaao full step derivations ke liye.
• Single-cycle datapath se compare karo (ek lamba clock, no shared hardware).
• Natural upgrade: Pipelining (alag instructions ke steps overlap karo).
• In steps ko drive karne wali state machine: Control unit — FSM vs microprogramming.
• Hamare speedups ke peeche ka math: CPI and CPU performance equation.
• Supporting hardware: ALU design aur Memory hierarchy.
• 🇮🇳 5.2.02 Multi-cycle datapath (Hinglish)