Visual walkthrough — FPGA-based acceleration

6.5.10 · D2 · Hardware › Advanced & Emerging Architectures › FPGA-based acceleration

Yeh FPGA-based acceleration ka dhadakta hua dil hai: ek FPGA isliye fast nahi hota kyunki uski clock fast hai, balki isliye kyunki woh ek spatial pipeline bichha sakta hai aur use bhara rakh sakta hai. Aao hum yeh result zero se samjhein.

---

Step 1 — "Stage" kya hota hai? (assembly line ki picture)

KYA. Socho ek toy car bana rahe ho. Kaam teen jobs mein banta hai: (1) wheels lagao, (2) paint karo, (3) box karo. Har job apne station par hoti hai. Ek station par kaam karne wala worker sirf wahi ek kaam karta hai, hamesha.

KYUN. Ek CPU ek akela worker hai jo ek car par teenon kaam karta hai, puri tarah se, agle car ko haath laganey se pehle — ek aadmi, teen tools, bahut chalna-phirna. Ek pipeline teen workers hai, har ek apne station se chipka hua, car ko line mein aage pass karta hai. Yeh "ek station per job" ka idea exactly waahi hai jo ek FPGA silicon mein karta hai: ek physical circuit per operation. Hum kaam ko stages mein isliye todtey hain taaki har station ek alag car par usi waqt kaam kar sake.

PICTURE. Neeche, teen stations ek row mein baithe hain. Ek car left se enter karti hai, right se nikalti hai. Abhi sirf station 1 busy hai — pipe abhi bhi us ke peechey se khaali hai.

---

Step 2 — "Clock tick" kya hota hai? (drumbeat)

KYA. Har station apni car ko agley station ko usi ek pal mein pass karta hai — ek shared drumbeat par. Woh beat hi clock hai. Do beats ke beech ka waqt clock period hai, jise $T$ likhte hain.

KYUN. Sabhi stations ko saath mein hand off karna padta hai, warna ek adhi-bani car aglay wali se takraayegi. Toh drum utni hi tez beat kar sakta hai jitni tez sabse slow station apna kaam khatam kar sakta hai. Agar painting sabse zyada $t_{max}$ seconds leta hai, toh

$T=t_{max}$

• $T$ — beats ke beech seconds (clock period). Chhota $T$ = faster clock.
• $t_{max}$ — sabse slow stage ko kitna waqt chahiye. Yahi pace set karta hai; ek chain utni hi mazboot hoti hai jitna uska sabse kamzor link.

PICTURE. Teen stations, chhoti stopwatches ke saath. Painting (station 2) slow wali hai, toh uski stopwatch sab ke liye drumbeat $T$ define karti hai.

---

Step 3 — Naive tarika: pipeline nahi (ek baar mein ek car)

KYA. Pehle, waqt ko slow tarike se count karo — koi assembly line nahi. Ek car sabhi $S$ stations se guzarti hai, shuru se ant tak, aglay car ke enter karne se pehle.

KYUN. Humein compare karne ke liye ek baseline chahiye. CPU yahi karta hai: item 1 poora khatam karo, phir item 2, aur aisa hi aage. Items ki sankhya ko hum $M$ kehte hain.

Count, term by term. Ek item ko $S$ stages lagte hain, har ek ek beat $T$ ka kharcha karta hai, toh ek item = $ST$. Yahi $M$ items ke liye karo:

${\text{Time}}_{\text{naive}}=M\cdot S\cdot T$

• $M$ — kitne data items (cars) hum daalte hain.
• $S$ — ek item ke liye stages (har item ko abhi bhi sab chahiye).
• $T$ — seconds per stage.
• Product $M\cdot S$ = total stage-visits; times $T$ = total seconds.

PICTURE. Cars ka ek uncha stack wait kar raha hai. Car 2 tab tak start nahi ho sakti jab tak car 1 teeno stations nahi chod deti. Kisi bhi waqt teen mein se do stations idle bethe hain — waste workers.

---

Step 4 — Pipeline trick: cars ko overlap karo

KYA. Ab har station ko busy rakho. Jaise hi car 1 station 1 chhodti hai, car 2 station 1 mein enter karti hai — jabki car 1 station 2 par hai. Cars waqt mein overlap karti hain.

KYUN. Step 3 ke woh idle workers hi waste the. Overlapping ka matlab hai ki jab line bhar jaati hai toh saare $S$ stations $S$ alag cars par kaam kar rahe hote hain. Yahi poora idea hai: pipe bharo, phir kabhi station ko idle mat rehne do.

PICTURE — space-time chart. Yeh key diagram hai. Rows = stations, columns = clock ticks. Har colored block ek car hai jo ek station par ek tick ke liye hai. Diagonal stripes padho: har car diagonally neeche-daayein jaati hai, har tick par ek station. Pipe bhar jaane ke baad, har column poori tarah colored hai — har station har tick par busy.

---

Step 5 — Pipelined time count karo (bharo, phir har tick ek)

KYA. Step 4 ke diagram mein ticks count karo. Do phases: pipe bharna, phir har tick ek result nikalte rehna.

KYUN. Pehla result free nahi aata — car 1 ko abhi bhi sabhi $S$ stations se crawl karna hoga iske pehle koi car finish ho. Yahi fill cost hai. Lekin pehle ke baad har car exactly ek tick baad nikalti hai, kyunki sab overlap hain.

Count, banate hue.

Pipe bharna (pehla result nikalta hai): car 1 ko sabhi $S$ stations pass karne mein $S$ ticks lagte hain.

$\underset{\text{pehla result nikla}}{\underbrace{S}}$

Baaki $M-1$ cars mein se har ek exactly ek tick baad apne aage wali car ke finish hoti hai (woh exactly ek beat se overlap hain):

$\underset{\text{fill}}{\underbrace{S}}+\underset{\text{baaki har item ke liye ek}}{\underbrace{(M-1)}}=S+M-1\text{ticks}$

Har tick $T$ seconds hai, toh:

$\boxed{{\text{Time}}_{\text{pipe}}=(S+M-1)T}$

• $S$ — ek-baar ki fill cost (pehla result aane se pehle ticks).
• $M-1$ — extra ticks, pehle ke baad har item ke liye ek.
• $T$ — seconds per tick, poori tick count ko seconds mein multiply karta hai.

PICTURE. Wahi chart, ab do phases shaded hain: left mein ek pale-yellow "fill" triangle length $S$ ka, phir ek chalk-blue "steady state" jahan results har column mein ek ek tapak rahe hain.

---

Step 6 — Speedup, aur yeh $S$ ki taraf kyun jaata hai

KYA. Naive time (Step 3) ko pipelined time (Step 5) se divide karo.

KYUN. Speedup "kitni baar faster" hai — purana time naye time se divide. Yeh akela ratio batata hai ki poori exercise worth it thi ya nahi.

Algebra, term by term.

$\text{Speedup}=\frac{{\text{Time}}_{\text{naive}}}{{\text{Time}}_{\text{pipe}}}=\frac{MST}{(S+M-1)T}$

$T$ cancel ho jaata hai (dono mein same clock) — pipelining faster clock ke baare mein nahi hai:

$\text{Speedup}=\frac{MS}{S+M-1}$

• Numerator $MS$ — total kaam (item-stage visits).
• Denominator $S+M-1$ — actual ticks jo hum ne pay kiye.
• Unka ratio = useful-work-per-tick vs one-tick-of-clock.

Ab $M$ (batch size) ko infinity ki taraf push karo. Top aur bottom dono ko $M$ se divide karo:

$\frac{MS}{S+M-1}=\frac{S}{\frac{S-1}{M}+1}\stackrel{M\to \infty }{\to }\frac{S}{0+1}=S$

• $\frac{S-1}{M}$ — fill cost $M$ items par spread out. Jaise $M$ badhta hai, yeh $0$ ho jaata hai.
• Jo bachta hai woh sirf $S$ hai: ek poora $S\times$ speedup.

PICTURE. Speedup vs $M$ ka ek curve: woh $1$ ke paas shuru hota hai (chhota batch, sab fill), badhta hai, aur $S$ par dashed ceiling line ko chhuute hue flat ho jaata hai.

---

Step 7 — Edge cases: woh corners jahaan intuition phisal jaati hai

KYA. Hum chhoti aur degenerate inputs check karte hain, warna reader formula par wahan trust karega jahan woh galat hoga.

KYUN. Jo formula aap tod nahi sakte, usse aap trust nahi kar sakte. Chaar corners:

(a) Ek item, $M=1$. Plug in karo: $\text{Speedup}=\frac{1\cdot S}{S+1-1}=\frac{S}{S}=1$. Bilkul koi speedup nahi! Ek akeli car ke saath, pipeline pure fill hai — aap poore $S$ ticks pay karte ho aur kuch gain nahi hota. Yeh latency vs throughput hai: ek item ki latency unchanged rehti hai.

(b) Ek stage, $S=1$. $\text{Speedup}=\frac{M\cdot 1}{1+M-1}=\frac{M}{M}=1$. Overlap karne ko kuch nahi — ek station pehle se hi poora kaam hai. Pipelining ko help karne ke liye $S\ge 2$ chahiye.

(c) Zero items, $M=0$. Time $=(S+0-1)T=(S-1)T$ — pipe andar se already rakhe leftovers drain karta hai, lekin naive time $0$ hai. Speedup undefined hai ($0/0$); physically, "koi kaam nahi, koi fayda nahi." Khali batch se divide karne se bachao.

(d) Unbalanced stages. Agar ek stage kaafi slow hai, toh $T=t_{max}$ usi stage se upar khicha jaata hai aur har doosra station har tick ka kuch hissa idle rehta hai. Formula abhi bhi sahi hai, lekin clock buri hai. Real-world fix hai balancing — slow stage ko todna taaki koi station $T$ par dominant na ho.

PICTURE. Chaar mini-panels, har corner ke liye ek: single car (sab fill), single station (koi overlap nahi), khaali batch, aur ek aisi lopsided line jahan mota slow station drum ko rok deta hai.

---

Step 8 — Real numbers daalte hain (parent ka example, check kiya gaya)

KYA. $S=12$ stages, $M=10,000$ items, clock $200$ MHz use karo toh $T=5$ ns.

KYUN. Ek formula ko numbers ke saath survive karna chahiye.

$\text{cycles}=S+M-1=12+9999=10011$ ${\text{Time}}_{\text{pipe}}=10011\times 5\text{ns}\approx 50.06\mu s$

Naive baseline $1$ ns per op, $12$ ops per item par:

${\text{Time}}_{\text{naive}}=10000\times 12\times 1\text{ns}=120\mu s$

$\text{Speedup}=\frac{120000}{10011}\approx 11.99\approx 12=S✓$

Hum ceiling $S=12$ se thoda neeche utare — exactly wahi fill toll $\frac{S-1}{M}=\frac{11}{10000}$ jo humne Step 6 mein predict ki thi. Picture aur algebra dono agree karte hain.

Recall Poori limit ek line mein bolo

${\lim }_{M\to \infty }\frac{MS}{S+M-1}$ kya hai aur kyun? ::: Yeh $S$ hai; ek-baar ki fill cost $S-1$ $M$ items par spread ho jaati hai aur gaayab ho jaati hai, puri stage count achievable speedup ke roop mein bachi rehti hai. $M=1$ ke saath, speedup kya hai? ::: Exactly $1$ — ek akela item pure fill hai, exploit karne ke liye koi overlap nahi.

---

Ek-picture summary

Yeh final chalkboard poori kahani compress karta hai: naive stack (workers idle) vs overlapped pipeline (sab workers busy), fill triangle of cost $S-1$, steady state jo har tick ek result tapkaata hai, aur speedup curve jo apni ceiling $S$ tak chadhta hai.

Recall Feynman retelling — bina math ke ek dost ko explain karo

Socho toy cars bana rahe ho. Slow tarika: ek worker ek poori car banata hai — wheels, paint, box — phir aglay pe jaata hai. Teen cars = nau slow kaam ek ke baad ek.

Pipeline tarika: teen workers, har ek apne station se chipka hua. Jaise hi car 1 wheel station chhodti hai, car 2 andar aa jaati hai. Jald hi teeno workers ek saath teen alag cars par busy hote hain. Uske baad, har drumbeat par ek finished car nikalti hai.

Shuru mein ek pareshani hai: pehli car ko abhi bhi teeno stations se crawl karna hoga kuch bhi nikalne se pehle — yahi "fill" hai. Woh toll aap ek baar pay karte ho. Lekin hazaar cars par, ek baar pay karna kuch nahi. Toh ek teen-station line, lambe run mein, lone worker se lagbhag teen guna faster cars nikalti hai — aur barah-station line, lagbhag barah guna. Jaadu ki sankhya sirf aapke paas kitne stations hain hai, $S$ — drum kitni tez beat karta hai nahi. Isliye ek slow-clocked FPGA with a deep pipeline ek fast CPU ko flatten kar deta hai: woh har single tick par ek poori computation ke barabar kaam khatam karta hai.

---

Related build-up: Pipelining and Throughput · Configurable Logic Blocks (LUTs & Flip-Flops) · Dataflow architectures · Roofline Model & Arithmetic Intensity · GPU vs FPGA vs ASIC trade-offs