Exercises — Classic 5-stage pipeline (IF - ID - EX - MEM - WB)

1. IF — Instruction Fetch: PC mein address par instruction memory se instruction padho; phir PC ← PC + 4.
2. ID — Instruction Decode / register read: opcode decode karo, register file se source registers padho, immediate ko sign-extend karo.
3. EX — Execute: ALU arithmetic/logic karta hai, ya memory address compute karta hai, ya branch condition check karta hai.
4. MEM — Memory access: loads data memory padhti hain, stores likhti hain; baaki sab yahan idle rehte hain.
5. WB — Write Back: result ko register file mein likho.

Registers ID mein read hote hain aur results WB mein write hote hain. Mnemonic: Decode reads, Write writes.

Charo hain IF/ID, ID/EX, EX/MEM, MEM/WB. Har ek data (operand values, immediate, ALU result, loaded value) aur control signals (RegWrite, MemRead, MemWrite, …) carry karta hai. ID mein decide kiye gaye control signals WB tak, chaar cycles baad, pahunchne chahiye — registers unhe wahan tak ferry karte hain.

Step (kya): $\text{Cycles}(N)=k+(N-1)$ apply karo. Kyun: $k=5$ cycles pipe fill karne mein (pehla result cycle 5 par), phir $N-1$ aur results, har ek subsequent cycle mein. $\text{Cycles}(8)=5+(8-1)=12.$ Pehli instruction cycle $k=5$ mein finish hoti hai (usse saare paanch stages pass karne hain). Figure s01 dekho: top row ka last coloured cell column 5 mein baitha hai.

Step (kya): maximum delay lo. Kyun: saare stages ek clock share karte hain; cycle itni lambi honi chahiye ki slowest stage finish kar sake, warna us stage ka result latch hone ke liye ready nahi hoga. $\max (250,120,180,250,100)=250\text{ ps (IF aur MEM tie karte hain).}$ Step: latch overhead add karo, kyunki har cycle pipeline register mein likhne mein bhi $d$ spend karta hai. $T_{clk}=250+15=265\text{ ps.}$

Step: cycles $=k+(N-1)=5+599=604$. Step: time $=604\times 265=160,060$ ps $=160.06$ ns. Cycles ko $T_{clk}$ se multiply kyun? Har clock cycle exactly $T_{clk}$ chalta hai, aur cycles ek ke baad ek hote hain; isliye total wall-clock time simply "kitne cycles" times "har cycle kitni lambi hai" hai.

Single-cycle time per instruction: ek bada cycle saara combinational kaam plus ek latch fit karna chahiye: $T_{single}=(250+120+180+250+100)+15=900+15=915\text{ ps.}$ Pipelined time per instruction (large $N$): har $T_{clk}=265$ ps mein ek instruction finish hoti hai. Speedup: $\frac{915}{265}\approx 3.45\times .$ Yeh ratio kyun aur $\frac{Nk}{k+N-1}$ kyun nahi? Kyunki dono machines ke yahan alag cycle times hain (915 vs. 265), isliye hum seedha per instruction wall-clock time compare karte hain, exactly jaise intro formula box ne warn kiya tha. 5× kyun nahi? Stages unbalanced hain: WB (100 ps) aur ID (120 ps) apne 265-ps slot ka zyaadatar hissa waste karte hain, jabki IF/MEM (250 ps) pace set karte hain. Ideal 5× ke liye har stage equal hona chahiye aur $d=0$ hona chahiye. Dekho Clocking & Latch Overhead ki $d$ kabhi zero kyun nahi ho sakta.

• lw $t0, 8($s1) : IF · ID($s1padho)\cdot EX(addr=$s1+8) · MEM(read) · WB($t0 likho). Saare paanch use karta hai.
• add $t2,$t3,$t4 : IF · ID($t3,$t4 padho) · EX(add) · MEM(idle) · WB($t2 likho).
• sw $t5, 0($s2) : IF · ID($s2,$t5 padho) · EX(addr = $s2+0) · MEM(write) · koi WB nahi. Idle slots kyun rakhte hain? Taaki har instruction ki ek jaisi 5-stage shape ho. Uniform shape ⇒ simple control ⇒ ek instruction phir bhi har cycle finish hoti hai. Stages skip karne se assembly line ka steady rhythm toot jaata.

• 5-stage: $T_{clk}=250+15=265$ ps.
• 10-stage: $T_{clk}=125+15=140$ ps. Step (kya): throughput ratio $265/140\approx 1.89\times$ banao. Yeh throughput ratio kyun hai? Lambi stream ke liye, har $T_{clk}$ mein ek instruction finish hoti hai, isliye throughput = 1 / $T_{clk}$ (instructions per second). Do throughputs compare karna isliye $\frac{1/T_{clk}^{\text{old}}}{1/T_{clk}^{\text{new}}}=\frac{T_{clk}^{\text{old}}}{T_{clk}^{\text{new}}}=\frac{265}{140}$ hai — throughput cycle time ke inverse ke saath scale karta hai, isliye chhota $T_{clk}$ proportionally faster hai. Result $1.89\times$ us naive 2× se kam hai jo tum stages double karne par umeed karte. Kyun? Latch overhead $d$ nahi shrink hua; yeh ab cycle ka $15/140\approx 10.7\%$ hai instead of $15/265\approx 5.7\%$. Jaise stages thinner hote hain, $d$ bada fraction khaata hai. Bahut aage push karo aur speedup saturate ho jaata hai ya reverse ho jaata hai.

IF aur MEM dono 250 ps hain. Koi bhi split karne se uske halves 125 ps ho jaate hain, lekin doosra 250-ps stage abhi bhi bacha rehta hai aur max re-set kar deta hai. Isliye akela split $\max t_i$ ko 250 se neeche nahi laata — naya bottleneck abhi bhi un-split 250-ps stage hai. $\max t_i=250\text{ ps still}\Rightarrow T_{clk}=250+15=265\text{ ps (unchanged!).}$ Insight: koi gain dekhne ke liye tumhe dono 250-ps stages split karne honge. Sirf ek split karna ek extra latch waste karta hai bina kisi kaam ke. Yahi core lesson hai: doosra-slowest stage yeh limit karta hai ki slowest ki help kitni achieve kar sakti hai. Balance global hai, local nahi.

Pipelined time < single-cycle time set karo: $(k+N-1)T_{clk}<N\cdot T_{single}$ $(5+N-1)(265)<N(915)$ $(N+4)(265)<915N$ $265N+1060<915N$ $1060<650N\Rightarrow N>\mathrm{1.63.}$ Isliye $N=2$ se pipeline already jeet jaata hai. Itni jaldi kyun? Single-cycle machine ki per-instruction cost (915) 265 ke comparison mein enormous hai; sirf 4 extra cycles ka fill penalty almost turant pay off ho jaata hai.

(a) $\max (300,200,350,300,150)=350$; $T_{clk}=350+25=375$ ps. (b) Cycles $=k+(N-1)=5+999=1004$. (c) Time $=1004\times 375=376,500$ ps $=376.5$ ns. (d) Total kaam $=300+200+350+300+150=1300$ ps; single-cycle $=1300+25=1325$ ps/instr. Large-$N$ pipelined $\approx 375$ ps/instr. Speedup $=1325/375\approx 3.53\times$. (e) Balanced ideal: har stage $=1300/5=260$ ps, isliye $T_{clk}=260+25=285$ ps, jo $1325/285\approx 4.65\times$ deta hai — phir bhi 5× nahi. Theoretical 5× ke liye $d=0$ bhi chahiye, lekin latch overhead kabhi zero nahi ho sakta (real flip-flops mein setup + propagation time hota hai — dekho Clocking & Latch Overhead). Hazards ise aur erode karenge.

Yaad karo ek stall cycle = ek inserted empty cycle jo instruction ko tab tak delay karta hai jab tak uski needed value reachable na ho jaaye. Dono instructions ko timeline par rakho; rows instructions hain, columns clock cycles hain (c1…c7), har cell woh stage hai jo us instruction us cycle mein occupy karti hai.

**Step 1 — find karo ki $t0kabproduce(reachable)hotahai.\ast \ast ‘add‘$t0 apne WB mein likhta hai, jo cycle 5 hai:

**Step 2 — find karo ki sub ko $t0kabchahiye.\ast \ast ‘sub‘apnesources\ast \ast ID\ast \ast meinpadhtahai.Back-to-back,‘sub‘kaIFc2hai,isliyeuska\ast natural\ast IDc3hai.\ast \ast Step3—hardwareruleapplykaro.\ast \ast Same-cyclewrite-then-readnahi,matlab‘sub‘kaIDsirf\ast \ast add\ast \ast keWBke\ast \ast baad\ast \ast walicyclemeinchalsaktahai—yaani‘sub‘kaIDc3se\ast \ast c6\ast \ast parmovehojaatahai.\ast \ast Step4—stallscountkaro.\ast \ast NaturalID=c3,requiredID=c6,isliye‘sub‘$6 - 3 = 3$ cycles se delay hua → 3 stall cycles. Corrected timeline:

(teen "–" cells inserted bubbles hain). Step 5 — total cycles. Bina stalls ke do instructions $k+(N-1)=5+1=6$ cycles leti hain; 3 bubbles sub ko 3 se push karte hain, jo $6+3=9$ total cycles deta hai (last cell WB c9 mein). Forwarding kyun fix karta hai: ALU result add ke EX (c3) ke baad exist karta hai — ise seedha sub ke EX mein feed karo aur saare 3 stalls gayab ho jaate hain, wapas 6 cycles. Yahi Data Forwarding / Bypassing ka poora motivation hai.

Goal: dikhao ki $\frac{Nk}{k+N-1}<k$. Step 1 — fraction clear karo. Kyunki $k+N-1>0$ hai, dono sides ko inequality flip kiye bina multiply karo: $\frac{Nk}{k+N-1}<k⟺Nk<k(k+N-1).$ Step 2 — right side expand karo. $k$ distribute karo: $k(k+N-1)=k^2+kN-k.$ Step 3 — common $kN$ term cancel karo. Dono sides mein $kN$ hai (left mein $Nk$ hai), isliye ise subtract karo: $Nk<k^2+kN-k⟺0<k^2-k.$ Step 4 — factor aur interpret karo. $k^2-k=k(k-1)$. Kisi bhi real pipeline ke liye $k\ge 2$, $k$ aur $k-1$ dono positive hain, isliye $k(k-1)>0$ hamesha true hai — lekin notice karo ki is step ne sirf $k\ge 2$ use kiya, $N$ se independent. Wait: hum ne $kN$ cancel kiya strict form maanke; strictness actually $N\ge 2$ require karti hai taaki pipeline genuinely overlapping ho ($N=1$ par dono sides $k$ ke barabar hain). Isliye har finite $N\ge 2$ ke liye strict inequality hold karta hai. Step 5 — limit. Equality ke liye $k(k-1)=0$ chahiye, $k\ge 2$ ke liye impossible; lekin jaise $N\to \infty$, "$-1$" in $k+N-1$ negligible ho jaata hai aur ratio approach karta hai $k$ ko. Matlab: $(k-1)$ cycles ka fill/drain overhead almost nothing amortize ho sakta hai lekin finite stream ke liye kabhi actually remove nahi ho sakta.