FPGA-based acceleration: Exercises — Hinglish deep dive

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

Intuition Is page ko kaise use karein

Har problem ko pehle khud solve karo phir uska Solution fold kholo. Exercises ek ladder climb karte hain: pehle tum sirf terms pehchante ho, phir throughput formula apply karte ho, phir bottlenecks analyse karte ho, phir poora design synthesize karte ho, aur finally mastery tak pahunchte ho — wo cases jo parent note mein sirf hint kiye gaye the. Yahan har symbol parent FPGA-based acceleration page par define hai; jahan bhi koi formula dobara aata hai hum use restate kar dete hain taaki tumhe kabhi wapas flip karna na pade.

Is page par Notation convention: ek word jo double-equals mein wrapped hai wo ek key term hai jise tum sight par recall kar sako (Obsidian mein yeh highlighted render hota hai). Yeh sirf emphasis hai — iska word ka meaning kabhi nahi badalta.

Teen formulas jin par hum poore page bhar rely karte hain — restate kiye gaye taaki kuch bhi use hone se pehle dikhaya ja sake:

Formula Toolbox restated

Pipeline cycles $M$ items ke liye $S$ stages se (sabse slow stage clock period $T$ set karta hai): $cycles = S + (M - 1), Time_{p i p e} = (S + M - 1) T$ Extra "drain" term kyun nahi hai? Ek pipeline $S - 1$ cycles mein fill hoti hai pehla result cycle $S$ par aane se pehle; uske baad har cycle mein ek result exit karta hai. $M$ items mein se aakhri item cycle $S + (M - 1)$ par exit karta hai. Draining alag kaam nahi hai — yeh sirf tail items hain jo har cycle ek-ek karke nikal rahe hain, pehle se hi $(M - 1)$ mein count ho chuke hain. Toh $S + (M - 1)$ fill, steady state, aur drain sab cover karta hai.

Speedup — $\frac{M S}{S + M - 1}$ kahan se aata hai? Ek hi kaam karne ke do tarike compare karo.

Serial (no pipeline): har item ko saare $S$ stages se guzarna padta hai pehle agle item ko start karne se, kyunki sirf ek hi worker hai jo ek time mein ek stage karta hai. Ek item cost karta hai $S$ cycles, toh $M$ items cost karte hain $M \times S$ cycles. Yahi numerator hai: $serial cycles = M S$ .
Pipelined: $S$ stages $S$ alag workers hain jo ek line mein arrange hain, har ek apna output agle ko hand karta hai. Woh overlap hi hai jo $M S$ ko $S + M - 1$ cycles mein badal deta hai (upar derive kiya gaya). Yahi denominator hai.

Slower ko faster se divide karo (clock period $T$ cancel ho jaata hai kyunki dono same clock use karte hain): $Speedup = \frac{serial cycles}{pipelined cycles} = \frac{M S}{S + M - 1} M \to \infty S .$ Limit ka Intuition: jaise-jaise $M$ bahut bada hota jaata hai, fixed " $S - 1$ " head-start cost ocean mein ek drop ki tarah ho jaata hai, toh pipelined time $\approx M$ cycles versus serial $M S$ cycles — ek clean $S \times$ jeet, har cycle mein ek item ka kaam khatam.

Roofline — achievable performance ka ceiling. Yahan $P$ = performance, measure ki gayi operations per second mein (kitni useful compute operations design actually har second mein complete karta hai): $P \leq min (P_{p e ak}, B \cdot I)$ jahan $P_{p e ak}$ = hardware ka maximum ops/second agar kabhi data ke liye starved na ho, $B$ = memory bandwidth bytes/second mein, aur $I$ = arithmetic intensity = operations performed per byte moved. Product $B \cdot I$ isliye units hote hain $(bytes/s) \times (ops/byte) = ops/s$ , jo $P$ se match karta hai.

Yahan $T$ (clock period) clock ke ek tick ka time hai; agar clock frequency $f$ hai (ticks per second) toh $T = 1/ f$ . $5 ns$ ka period matlab $f = 200 MHz$ , kyunki $1/ (5 \times 1 0^{- 9} s) = 200 \times 1 0^{6}$ ticks/s.

Level 1 — Recognition

Exercise 1.1

Har block ko woh single kaam match karo jiske liye woh exist karta hai: LUT, Flip-Flop, BRAM, DSP slice, Interconnect.

Recall Solution

LUT (Look-Up Table): ek tiny truth-table memory jo apne inputs ka koi bhi boolean gate ban jaata hai — custom logic ka atom.
Flip-Flop: ek 1-bit register jo do clock edges ke beech pipeline state hold karta hai.
BRAM: on-chip SRAM jo data ko compute ke paas rakhta hai taaki slow DRAM trips se bacha jaa sake.
DSP slice: ek hardwired multiply-accumulate unit; multipliers LUTs se banaye jaayein toh expensive hote hain, isliye inhe harden kiya jaata hai.
Interconnect: programmable wires + switches jo tumhe blocks ko kisi bhi topology mein connect karne dete hain.

LUT/FF pair in depth ke liye Configurable Logic Blocks (LUTs & Flip-Flops) dekho.

Exercise 1.2

Ek $6$ -input LUT kitne output bits store karta hai, aur exactly kyun utne?

Recall Solution

Ek $k$ -input LUT $2^{k}$ bits store karta hai — apne inputs ke har combination ke liye ek output. $k = 6$ ke saath: $2^{6} = 64 bits.$ Chhe inputs ke $64$ possible input patterns hain; truth table ko har pattern ke liye ek output entry chahiye. Kisi bhi boolean function ka truth table un $64$ cells mein likho aur LUT woh function ban jaata hai.

Exercise 1.3

"Field-programmable" — field ka matlab kya hai, aur programming kaunsa physical object karta hai?

Recall Solution

Field = manufacturing ke baad, duniya mein ("field" mein), factory mein bake-in nahi. Programming bitstream se hoti hai: ek configuration file jo har LUT cell aur interconnect switch ko us pattern mein flip karti hai jo tumhara circuit realize karta hai. Compare karo ek ASIC se, jiska logic fabrication par hamesha ke liye fix ho jaata hai.

Level 2 — Application

Exercise 2.1

Ek pipeline mein $S = 8$ stages hain aur $M = 5000$ items clock $T = 4 ns$ par stream karta hai. Total time aur serial version par speedup nikalo.

Recall Solution

Cycles: $cycles = S + (M - 1) = 8 + 4999 = 5007.$ Time: $5007 \times 4 ns = 20028 ns \approx 20.03 μ s .$ Speedup: $\frac{M S}{S + M - 1} = \frac{5000 \times 8}{5007} = \frac{40000}{5007} \approx 7.99.$ Ideal $8 \times$ se thoda kam: $S - 1 = 7$ fill cycles $5000$ items ke against tiny hain. Yeh Pipelining and Throughput ek line mein hai.

Exercise 2.2

Same $S = 8$ pipeline lekin sirf $M = 8$ items. Ab speedup kya hai, aur yeh kya lesson deta hai?

Recall Solution

$\frac{M S}{S + M - 1} = \frac{8 \times 8}{8 + 8 - 1} = \frac{64}{15} \approx 4.27.$ Sirf $\approx 4.27 \times$ , $8 \times$ nahi. Lesson: fill cost $S - 1$ fixed hai; yeh sirf tab negligible hoti hai jab $M ≫ S$ . Short streams fill penalty bahut zyada pay karti hain. Latency (pehla result $S$ cycles baad) dominate karta hai jab $M$ chhota ho.

Exercise 2.3

Ek FPGA $250 MHz$ par run karta hai aur har cycle $1000$ operations complete karta hai. Ek CPU $4 GHz$ par run karta hai aur har cycle $10$ operations complete karta hai. Kiska throughput zyada hai, aur kitna zyada?

Recall Solution

Throughput $=$ (ops/cycle) $\times$ (cycles/second): $FPGA = 1000 \times 250 \times 1 0^{6} = 2.5 \times 1 0^{11} ops/s .$ $CPU = 10 \times 4 \times 1 0^{9} = 4 \times 1 0^{10} ops/s .$ Ratio: $\frac{2.5 \times 1 0 ^{11}}{4 \times 1 0 ^{10}} = 6.25.$ FPGA $6.25 \times$ faster hai baawajood apne bahut kam clock ke — parallelism $\times$ pipelining raw clock speed ko beat karta hai.

Level 3 — Analysis

Exercise 3.1

Ek kernel ka arithmetic intensity $I = 2 ops/byte$ hai aur woh hardware par run karta hai jiska bandwidth $B = 20 GB/s$ aur peak compute $P_{p e ak} = 100 GOP/s$ hai. Kya yeh compute-bound hai ya memory-bound, aur best achievable $P$ kya hai?

Recall Solution

Roofline: $P \leq min (P_{p e ak}, B \cdot I)$ . $B \cdot I = 20 \times 1 0^{9} \times 2 = 40 \times 1 0^{9} = 40 GOP/s .$ Compare karo $P_{p e ak} = 100 GOP/s$ se. Kyunki $40 < 100$ , memory roof lower hai: $P \leq min (100, 40) = 40 GOP/s \Rightarrow memory-bound .$ Tum $60 GOP/s$ compute idle chhod rahe ho.

Neeche di gayi figure yeh plot karta hai. Iska horizontal axis ==arithmetic intensity $I$ hai ops/byte mein (kitna compute har fetched byte feed karta hai); iska vertical axis performance $P$ == hai GOP/s mein (billions of operations per second). Sloped orange line memory roof $B \cdot I$ hai, flat violet line $P_{p e ak}$ hai, navy line actual attainable roof hai (dono mein se lower), aur magenta dot is kernel ko $I = 2$ par sloped (memory) part par mark karta hai — vertical axis se seedha $P = 40$ padho. Dekho Roofline Model & Arithmetic Intensity.

Figure s01 — Roofline. X-axis: arithmetic intensity $I$ (ops/byte). Y-axis: performance $P$ (GOP/s). Magenta dot ( $I = 2$ ) sloped memory roof par baitha hai: memory-bound at $P = 40$ . Intensity ko ridge ( $I = 5$ ) ke paar right push karo aur violet dot ( $I = 8$ ) flat compute ceiling par $P = 100$ hit karta hai.

Exercise 3.2

Exercise 3.1 ke liye, tum data ko BRAM mein buffer karte ho taaki har byte $4 \times$ reuse ho sake, intensity $I = 8 ops/byte$ tak raise ho jaaye. $P$ recompute karo. Ab limiting factor kya hai?

Recall Solution

Naya memory roof: $B \cdot I = 20 \times 1 0^{9} \times 8 = 160 GOP/s .$ Ab $min (P_{p e ak}, B \cdot I) = min (100, 160) = 100 GOP/s$ — compute roof jeetta hai. Design ab compute-bound hai. Roofline plot par (figure s01) operating point "ridge" ke paar right move ho gaya hai jahan sloped memory line flat compute ceiling se milti hai. $I$ aur badhane se koi faida nahi; sirf zyada compute units help karenge.

Exercise 3.3

Ek design FPGA ke $90%$ LUTs use karta hai lekin sirf $30%$ peak throughput sustain karta hai. Uski intensity roofline ridge ke left hai. Koi propose karta hai ki aur compute units add karo. Kya yeh accha idea hai?

Recall Solution

Nahi. Ridge ke left matlab workload memory-bound hai — bandwidth $B$ , compute nahi, ceiling hai. Zyada compute units area aur power add karte hain lekin data ka wait karte hue idle baithte hain. Sahi fix yeh hai ki arithmetic intensity $I$ raise karo: BRAM mein data cache/reuse karo, loops tile karo, stream karo taaki har fetched byte kaafi operations feed kare. Bottleneck fix karo, abundant resource nahi.

Level 4 — Synthesis

Exercise 4.1

Ek $K = 16$ -tap FIR filter $y [n] = \sum_{k = 0}^{15} c_{k} x [n - k]$ ke liye ek streaming accelerator design karo. Hardware blocks list karo, batao kyun har ek exist karta hai, aur steady-state throughput do.

Recall Solution

Blocks aur unke kaam:

16 DSP slices — ek multiply per tap $c_{k} x [n - k]$ , sab ek hi cycle mein → 16-way spatial parallelism. (Hardened multipliers, LUT-built nahi.)
Adder tree, $lo g_{2} 16 = 4$ levels, har level registered — 16 products ko sum karta hai. Tree ko pipeline karna slowest stage ko chhota rakhta hai taaki clock fast rahe. Yeh dataflow hai.
$x$ ke liye length 16 ka shift register — har cycle ek naya sample shift in hota hai; har stored sample time ke saath ek alag tap feed karta hai. Yeh data reuse deta hai: koi byte DRAM se re-fetch nahi hota, toh intensity high rehti hai.

Throughput: pipeline fill hone ke baad, har clock cycle mein ek $y [n]$ . Ek CPU $\approx 16$ multiply-adds serially per output karta hai, toh speedup $\approx K = 16$ , input bandwidth se bounded. Is expression ko C mein express karne ke liye High-Level Synthesis (HLS) dekho.

Exercise 4.2

Exercise 4.1 design ke liye $T = 4 ns$ par, $M = 10000$ samples stream karte hue, pipeline depth (fill) $S = 1 + 4 = 5$ stages hai (1 multiply + 4 adder levels). Total time aur ek serial CPU par speedup compute karo jo $16$ ops per sample $1 ns/op$ par karta hai.

Recall Solution

FPGA time: $cycles = S + (M - 1) = 5 + 9999 = 10004.$ $Time_{F P G A} = 10004 \times 4 ns = 40016 ns \approx 40.02 μ s .$ CPU time: $10000 \times 16 \times 1 ns = 160000 ns = 160 μ s .$ Speedup: $\frac{160}{40.016} \approx 4.0.$ Sirf $\approx 4 \times$ baawajood 16 multipliers place karne ke — kyunki FPGA clock period ( $4 ns$ ) CPU op time ( $1 ns$ ) se $4 \times$ hai. Parallelism-16 win partly slower clock se cancel ho jaata hai: $16/4 = 4$ . Yeh exactly trade-off hai low clock aur high parallelism ke beech.

Level 5 — Mastery

Exercise 5.1 (degenerate case)

Pipeline speedup kya hai jab $S = 1$ ho? Physically interpret karo.

Recall Solution

$\frac{M S}{S + M - 1} = \frac{M \cdot 1}{1 + M - 1} = \frac{M}{M} = 1.$ Speedup $= 1$ har $M$ ke liye. Ek "one-stage pipeline" mein overlap karne ke liye kuch nahi hai — sirf ek combinational block hai, koi registers kaam ko split nahi karte, toh pipelining kuch buy nahi karta. Pipelining sirf tab pay karta hai jab $S \geq 2$ ho, aur uska ceiling $S$ ke saath badhta hai.

Exercise 5.2 (limiting behaviour, both directions)

$S = 10$ fix karo. $M = 1$ , $M = 10$ , $M = 1000$ , aur $M \to \infty$ par speedup evaluate karo. Curve ki shape describe karo.

Recall Solution

$M = 1 : \frac{10 \cdot 1}{10 + 1 - 1} = \frac{10}{10} = 1.$ $M = 10 : \frac{10 \cdot 10}{10 + 10 - 1} = \frac{100}{19} \approx 5.26.$ $M = 1000 : \frac{10 \cdot 1000}{10 + 1000 - 1} = \frac{10000}{1009} \approx 9.91.$ $M \to \infty : \to S = 10.$ Curve $1$ se rise karta hai (ek item = pure latency, koi overlap nahi) aur horizontal asymptote $S = 10$ ki taraf saturate ho jaata hai. Yeh concave hai: pehle fast gains, phir jaise $M$ badhta hai diminishing returns.

Neeche di gayi figure exactly yeh curve draw karti hai. Iska horizontal axis ==streamed items $M$ ki count== hai (log scale par draw kiya gaya taaki chhota aur bada dono $M$ visible ho); iska vertical axis speedup hai (dimensionless, "serial se kitna zyada fast"). Teen sample points aur $S = 10$ par dashed asymptote marked hain.

Figure s02 — Speedup $M S / (S + M - 1)$ for $S = 10$ . X-axis: streamed items $M$ ki count (log scale). Y-axis: speedup (×, dimensionless). $M = 1$ par $1$ se rise karta hai, $M = 10$ par $5.26$ aur $M = 1000$ par $9.91$ pass karta hai, aur dashed line $S = 10$ ki taraf flatten ho jaata hai.

Exercise 5.3 (two-roof crossover — the ridge point)

Ek roofline par jahan $P_{p e ak} = 100 GOP/s$ aur $B = 25 GB/s$ hai, arithmetic intensity $I_{⋆}$ nikalo jahan memory roof compute roof se milti hai ("ridge"). Exactly $I_{⋆}$ par ek operating point ka kya matlab hai, aur jo point uske left land kare use kis direction mein move karna chahiye?

Recall Solution

Ridge wahan hai jahan dono roofs equal hain: $B \cdot I_{⋆} = P_{p e ak} \Rightarrow I_{⋆} = \frac{P _{p e ak}}{B} = \frac{100 \times 1 0 ^{9}}{25 \times 1 0 ^{9}} = 4 ops/byte .$ $I_{⋆} = 4$ par design perfectly balanced hai: yeh memory bandwidth aur peak compute dono simultaneously saturate karta hai. $I_{⋆}$ ke left ⇒ memory-bound; $I_{⋆}$ ke right ⇒ compute-bound. Jo point left of $I_{⋆}$ land kare use rightward push karna chahiye — uski intensity $I$ raise karo (BRAM mein data buffer aur reuse karo taaki har fetched byte zyada operations feed kare) jab tak ridge tak na pahunche; $I_{⋆}$ ke past intensity se aur kuch gain nahi, aur sirf extra compute units help karenge.

Exercise 5.4 (synthesis of both models — when is the FPGA worth it?)

Ek workload $M = 2000$ items stream karta hai, $S = 20$ pipeline stages chahiye, clock $T = 5 ns$ . Yeh memory-bound hai: intensity $I = 1 op/byte$ , bandwidth $B = 8 GB/s$ , har item $8$ bytes hai aur $40$ ops chahiye. Compute karo (a) ideal pipelined compute time, (b) roofline memory-bound time, (c) kaunsa actually govern karta hai — aur explain karo kyun hum total-ops $/ (B \cdot I)$ use karte hain, raw bytes $/ B$ nahi.

Recall Solution

(a) Pipelined compute time (assuming data hamesha available hai — sirf compute roof): $cycles = S + M - 1 = 20 + 1999 = 2019, Time_{co m p u t e} = 2019 \times 5 ns = 10095 ns \approx 10.1 μ s .$

(b) Roofline memory-bound time. Kyun sirf bytes $/ B$ nahi? Raw transfer time $= bytes / B = (2000 \times 8) / (8 \times 1 0^{9}) = 2 μ s$ sirf batata hai wires kitni der busy hain — yeh ignore karta hai ki har byte ko kitna useful compute feed karna hai. Roofline performance ops/s mein measure karta hai, toh honest memory-bound time hai total operations divided by memory-limited op-rate $B \cdot I$ : $Time_{m e m} = \frac{total ops}{B \cdot I} = \frac{M \times 40}{B \times I} = \frac{2000 \times 40}{8 \times 1 0 ^{9} \times 1} = \frac{80000}{8 \times 1 0 ^{9}} = 10 μ s .$ Dono numbers differ karte hain ( $2 μ s$ vs $10 μ s$ ) exactly isliye kyunki yahan har byte $I = 1$ op carry karta hai, lekin har item $8$ bytes hai phir bhi $40$ ops demand karta hai — toh compute-per-byte jo memory roof allow karta hai ( $B \cdot I$ ) real throttle hai, raw byte count nahi. bytes $/ B$ use karna galat claim karta ki kaam $2 μ s$ mein khatam ho jaayega.

(c) Kaunsa govern karta hai? Ek design apne dono ceilings mein se slower se faster khatam nahi kar sakta. Yahan compute time $\approx 10.1 μ s$ aur memory-bound time $= 10 μ s$ almost equal hain, toh yeh design ridge par bilkul baitha hai — koi bhi roof badly slack nahi hai. Memory roof marginally govern karta hai ( $10.0 < 10.1$ matlab memory dono mein se tighter hai sirf marginally; practice mein wo co-limit karte hain). Faster jaane ke liye tumhe dono uthane honge: $B$ raise karo (zyada DRAM channels) aur $I$ raise karo (BRAM reuse). Sirf ek improve karna doosre roof ko naya wall bana deta hai.

Recall One-line takeaways

Pipeline speedup kahan saturate hota hai, aur kya ho jaata hai? ::: Yeh $M \to \infty$ par stage count $S$ tak saturate hota hai; finite $M$ hamesha strictly less deta hai kyunki $S - 1$ fill cost hoti hai. Roofline ridge ke left, sahi optimisation kya hai? ::: Arithmetic intensity $I$ raise karo (BRAM mein data reuse karo); compute add karna useless hai kyunki tum memory-bound ho. "16 multipliers" ko honest CPU speedup mein kaise convert karo? ::: Parallelism $K$ ko clock-period ratio $t_{C P U -op} / T_{F P G A}$ se multiply karo. Memory-bound time total-ops $/ (B \cdot I)$ kyun hai aur bytes $/ B$ kyun nahi? ::: Kyunki roofline performance ops/s mein measure karta hai; $B \cdot I$ woh ops/s hai jo memory allow karta hai, toh total ops ko usse divide karna true time deta hai — raw bytes/B ops-per-byte ignore karta hai.