Worked examples — Single-cycle datapath design

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

Yeh page single-cycle datapath design ka drill room hai. Parent note ne machine banai; yahan hum har tarah ke sawaal chalate hain jo exam ya real design mein aa sakte hain. Har solution se pehle aapko forecast karna hai — pehle apna andaaza likho, phir compare karo.

Jo bhi numeric hai woh page ke bottom par machine-check hai.

---

The scenario matrix

Har single-cycle problem in boxes mein se kisi ek mein aata hai. Hum sab ko cover karenge.

#	Case class	Tricky kyun hai	Covered by
A	R-type timing (no memory)	path data-memory block ko skip karta hai	Ex 1
B	lw timing (sab kuch touch karta hai)	usual critical path	Ex 2
C	sw / beq short paths	write-back ya memory absent	Ex 3
D	Ek slow instruction add karna	ek instruction sabka clock raise kar deti hai	Ex 4
E	Zero / degenerate delay	ek block delay 0 ps (ya remove ho jaaye)	Ex 5
F	Branch target arithmetic — positive offset	sign-extend phir shift, forward branch	Ex 6
G	Branch target arithmetic — negative offset	sign bit survive karna chahiye; backward loop	Ex 7
H	Control-signal fill-in incl. "don't care" X	jab mux value sach mein matter nahi karti	Ex 8
I	Real-world word problem (speedup)	English → performance equation mein translate karo	Ex 9
J	Exam twist: "reuse the ALU?"	single-cycle time-sharing kyun forbid karta hai	Ex 10

Delays jo hum har jagah reuse karte hain (parent note jaisi, picoseconds mein, ps = ek-trillionth of a second):

Upar wala bar chart hamaara map hai: har instruction un blocks ka stack hai jinhein woh touch karta hai. Sabse uncha stack jeet jaata hai aur clock period ban jaata hai. Baar baar isko dekhte rehna.

---

Case A — R-type timing

Recall Forecast: kya

add data memory touch karta hai? Apna total ps guess karo. Yeh data memory touch nahi karta. Aage padhne se pehle guess karo.

Steps.

1. add jin blocks se guzarta hai unhe list karo: Instruction Memory → Register read → ALU → Register write-back. Yeh step kyun? Ek R-type do registers padhta hai, ek ALU operation karta hai, aur result wapas store karta hai. Yeh kabhi load ya store memory nahi karta, isliye Data Memory block bilkul skip ho jaata hai.
2. Inhe sum karo: $200+100+200+100$. Yeh step kyun? Ek path par blocks series mein chalte hain (ek doosre ko feed karta hai), isliye delays add hote hain.
3. Total $=600$ ps.

Verify: Figure s01 dekho — R-type stack 600 tak jaata hai aur wahan ek visible gap hai jahan Data Memory hota. Units sab ps hain jo ps mein sum hue. ✓

---

Case B — lw, the usual critical path

Recall Forecast:

lw mein add ke comparison mein kaun sa extra block add hota hai? Data Memory read. Toh yeh hona chahiye add + $t_{DMem}$.

Steps.

1. lw blocks: IMem → RegRead → ALU (address compute karta hai) → Data Memory (padhta hai) → RegWrite. Yeh step kyun? Ek load ko address compute karna hota hai (ALU base register + offset add karta hai), phir memory read karta hai, phir loaded value wapas register mein likhta hai. Yeh literally paanch saare logical stages hain.
2. Sum: $200+100+200+200+100$.
3. Total $=800$ ps.

Verify: $800=600(\text{R-type})+200(\text{DMem})$. S01 mein lw stack sabse uncha hai — akela yeh clock set karta hai. ✓

---

Case C — short paths (sw, beq)

Recall Forecast:

sw store karta hai — kya yeh end mein register write karta hai? beq — kya yeh memory touch karta hai? sw final register write-back drop karta hai. beq memory aur write-back dono drop karta hai.

Steps.

1. sw blocks: IMem → RegRead → ALU (address) → Data Memory (likhta hai). No write-back — ek store koi register result produce nahi karta. $200+100+200+200=700$ ps. Yeh step kyun? Store karne ka matlab hai value bahar memory mein jaati hai; kuch register mein wapas nahi aata, isliye $t_{RegWrite}$ path par nahi hai.
2. beq blocks: IMem → RegRead → ALU (compare karne ke liye subtract karta hai). No memory, no write-back. $200+100+200=500$ ps. Yeh step kyun? Ek branch sirf do registers compare karta hai; ALU ka Zero output branch decide karta hai. Yeh kabhi data memory touch nahi karta aur koi register nahi likhta.

Verify: $700<800$ aur $500<800$, toh koi bhi critical path nahi hai — clock 800 ps rehta hai. Charon s01 mein lw bar ke neeche hain. ✓

---

Case D — ek nayi slow instruction sabka clock raise kar deti hai

Recall Forecast: kya

lw path slow hota hai? Ab kaun sa instruction critical hai? lw unchanged hai (abhi bhi 800). Lekin mul use exceed kar sakta hai.

Steps.

1. mul path (R-type shape, slow ALU): $t_{IMem}+t_{RegRead}+t_{ALU,mul}+t_{RegWrite}=200+100+500+100$. Yeh step kyun? mul ek register likhta hai aur koi memory nahi karta, isliye uski R-type block list hai — sirf uska ALU cost badla.
2. Total $=900$ ps.
3. Naya clock $=\max (800,900)=900$ ps. Yeh step kyun? Clock period sab instructions par maximum hai (parent formula $T_{clk}\ge {\max }_{\text{instr}}(\dots )$). Ek slow instruction jeet jaata hai.

Verify: $200+100+500+100=900>800$, toh $\max =900$. ✓

---

Case E — zero / degenerate delay

Recall Forecast: kaun si instructions shrink hoti hain? Kya

lw abhi bhi critical hai? Har instruction jo register write karti hai 100 ps khoti hai; sw/beq nahi (woh kabhi write-back nahi karte).

Steps.

1. $t_{RegWrite}=0$ ke saath nayi paths:
   • R-type: $200+100+200+0=500$
   • lw: $200+100+200+200+0=700$
   • sw: $700$ (unchanged — koi write-back nahi hata)
   • beq: $500$ (unchanged) Yeh step kyun? Ek block delay ko 0 set karna matlab signals use "free" mein pass karte hain; block logically wahan hai, bas kuch add nahi karta.
2. Naya clock $=\max (500,700,700,500)=700$ ps. Yeh step kyun? Ab lw aur sw tie karte hain 700 par — critical path shared ho gayi. Ek block zeroing change kar sakta hai ki kaun critical hai.

Verify: $\max (500,700,700,500)=700$. Note the surprise: write-back shave karne se sw ko help nahi mili, toh ceiling 800 se 700 hi gayi, 600 nahi. ✓

---

Case F — branch target with a positive (forward) offset

Recall Forecast:

$(\text{PC}+4)+(\text{SignExt(imm)}\ll 2)$ apply karo. Yeh kis taraf jump karta hai? Positive offset ⇒ forward jump karta hai.

Steps.

1. $\text{PC}+4=\text{0x00400010}+4=\text{0x00400014}$ compute karo. Yeh step kyun? MIPS branches already-incremented PC (next instruction) ke relative hain, branch ke khud ke nahi. Woh "+4" definition mein baked in hai.
2. imm sign-extend karo: 0x0003 = decimal $3$. Top bit 0 hai, toh 32-bit value abhi bhi $+3$ hai. Yeh step kyun? Sign-extension top (sign) bit ko left mein copy karta hai. Yahan yeh 0 hai, toh koi change nahi — lekin yeh shifting se pehle karte hain (order matters, parent ka mistake note dekho).
3. Shift left 2: $3\ll 2=3\times 4=12=\text{0x0000000C}$ bytes. Yeh step kyun? Offset instructions (words) count karta hai; har word 4 bytes hai, toh $\times 4$ (= shift left 2) word-count ko byte-address distance mein convert karta hai.
4. Add karo: $\text{0x00400014}+\text{0x0000000C}=\text{0x00400020}$.

Verify: $0x00400010=4194320$; target $=4194320+4+12=4194336=\text{0x00400020}$. S02 mein arrow next instruction ke baad 3 instructions forward point karta hai — ek forward jump. ✓

---

Case G — branch target with a negative (backward) offset

Recall Forecast:

0xFFFC ka top bit 1 hai. Sign ke liye iska kya matlab hai? Top bit 1 ⇒ negative ⇒ backward jump karta hai.

Steps.

1. $\text{PC}+4=\text{0x00400014}$ (Ex 6 jaisi wajah).
2. imm = 0xFFFC sign-extend karo. Uska 16-bit sign bit 1 hai, toh yeh negative hai. Signed 16-bit number ke roop mein, 0xFFFC $=-4$. Yeh step kyun? Yeh sign-extension ka poora point hai: top bit mein 1 ko poori taraf left mein copy karna chahiye taaki 32-bit number $-4$ rahe, na ki giant positive 0x0000FFFC. Yeh shifting se pehle karo warna aap galat (unsigned) value shift kar loge.
3. Shift left 2: $-4\ll 2=-4\times 4=-16=\text{0xFFFFFFF0}$ bytes (two's complement mein). Yeh step kyun? $\times 4$ abhi bhi word-count → bytes convert karta hai; sign carry through hota hai.
4. Add karo: $\text{0x00400014}+(-16)=\text{0x00400004}$.

Verify: $4194320+4-16=4194308=\text{0x00400004}$ — yeh branch se 3 instructions pehle hai, exactly ek loop back. Agar hum sign-extension bhool jaate, toh $0x0000FFFC\times 4$ add karte, ek bada forward jump — classic bug. ✓

---

Case H — control signals with "don't care"

Recall Forecast:

sw memory likhta hai lekin register nahi. Kaun se signals "don't care" ban jaate hain? Koi bhi signal jo sirf tab matter karta hai jab hum register likhte hain woh don't-care hai.

Steps.

1. RegWrite = 0. Kyun? Store koi register result produce nahi karta; likhna ek register corrupt kar dega.
2. ALUSrc = 1. Kyun? ALU ka doosra input address banane ke liye sign-extended offset hona chahiye, na ki ek register.
3. MemRead = 0, MemWrite = 1. Kyun? Hum memory likh rahe hain, padh nahi rahe.
4. Branch = 0. Kyun? sw branch nahi hai; next PC bas PC+4 hai.
5. MemToReg = X. Kyun? Yeh mux sirf choose karta hai kya value register mein likhi jaaye — lekin RegWrite=0, toh kuch likha nahi jaata; uski value irrelevant hai.
6. RegDst = X. Kyun? Yeh mux sirf choose karta hai kaun sa register likha jaaye. Wapas RegWrite=0, toh destination kabhi use nahi hota.

Verify: RegWrite=0 dono X's justify karta hai; har non-X value parent ke sw ke control table row se match karti hai. ✓

---

Case I — real-world word problem (speedup)

Recall Forecast:

Performance equation hai $\text{Time}=N\times \text{CPI}\times T_{clk}$. Speedup ratio guess karo. Same $N$, same CPI ⇒ speedup bas clock periods ka ratio hai.

Steps.

1. Single-cycle time: $T_1=N\times \text{CPI}\times T_{clk}=10^6\times 1\times 800\text{ps}=8.0\times 10^8$ ps $=800\mu s$. Yeh step kyun? Yeh Performance equation hai: total time = instructions × cycles-per-instruction × seconds-per-cycle.
2. Pipelined time: $T_2=10^6\times 1\times 200\text{ps}=2.0\times 10^8$ ps $=200\mu s$.
3. Speedup $=T_1/T_2=800/200=4\times$. Yeh step kyun? $N$ aur CPI identical hone ke saath, ratio clock-period ratio par collapse ho jaata hai.

Verify: $10^6\times 800=8\times 10^8$ ps aur $10^6\times 200=2\times 10^8$ ps; ratio $=4$. Units: ps × count = ps of total wall-clock. ✓

---

Case J — exam twist: "just reuse the ALU"

Recall Forecast:

ek cycle ke andar, kitne additions ek hi waqt hone chahiye ek R-type ke liye? Kam se kam do: instruction ka khud ka arithmetic aur PC+4.

Steps.

1. Single-cycle mein, PC+4 usi tick mein ready hona chahiye jab ALU instruction ka arithmetic kar raha hota hai. Yeh step kyun? Sab kuch ek cycle mein khatam hota hai, toh PC+4 aur ALU result simultaneously chahiye, ek ke baad ek nahi.
2. Ek single ALU per cycle sirf ek operation kar sakta hai. Agar usne PC+4 compute kiya, toh woh usi cycle mein, maano, $t1+$t2 compute nahi kar sakta. Yeh step kyun? Hardware ko ek single cycle ke andar time-share nahi kar sakte — ALU ko wapas dene ke liye koi doosra sub-step nahi hai.
3. Isliye single-cycle mein PC+4 (aur branch target) ke liye ek dedicated adder zaroori hai.
4. Contrast: ek Multi-cycle datapath ALU reuse kar sakta hai kyunki woh ek instruction ko kayi cycles mein spread karta hai, ALU ko alag cycles mein alag kaam deta hai.

Verify: Parent ke mistake note se consistent hai ("cannot time-share within a cycle"); resolution across designs alag hai, jo examiner ka trap hai. ✓ (Check karne ke liye koi number nahi.)

---

Recall Poori matrix ki ek-line summary

Har sawaal do ideas par reduce hota hai: (1) woh blocks sum karo jo ek specific instruction actually touch karta hai, aur (2) clock sabhi instructions par max hai — plus branch-address recipe sign-extend, phir shift-left-2, phir PC+4 mein add karo.

---

Active-recall