FPGA-based acceleration: Worked examples — Hinglish deep dive

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

Kuch bhi compute karne se pehle, chaliye symbols ko naam dete hain taaki koi confused na ho. Yeh sab diagrams mein bhi dikhenge.

Definition Symbols jo hum har jagah use karte hain

$S$ = pipeline stages ki sankhya. Socho ek factory conveyor jisme $S$ work-benches row mein hain; ek item ko finish hone ke liye sabhi $S$ benches visit karne padte hain.
$M$ = data items jinhe hum push karte hain (samples, matrix rows, pixels).
$T$ = clock period, conveyor ki ek tick ka time. Agar clock $f$ hertz hai to $T = 1/ f$ . (Ek "hertz" matlab ek tick per second.)
$t_{ma x}$ = sabse slow single bench ko jitna time chahiye. Poora conveyor utni hi tez tick kar sakta hai jitna uska slowest bench, isliye $T = t_{ma x}$ .
$B$ = memory bandwidth (bytes jo hum per second fetch kar sakte hain) aur $I$ = arithmetic intensity (compute operations jo hum per byte fetched karte hain). Unka product $B \cdot I$ wo fastest rate hai jis par memory feed kar sakti hai.
$P_{p e ak}$ = chip ki peak compute rate (operations per second) agar infinite data mile — silicon mein kitne multiply/add units hain usse set hone wali hard ceiling.

Woh ek formula jiske around poora page revolve karta hai, phir se stated taaki hum usse own kar sakein:

The scenario matrix

Har FPGA-timing question inn cells mein se ek hai. Neeche ke worked examples mein har ek [C#] tag carry karta hai jo batata hai ki woh kaunsi cell cover karta hai.

#	Case class	Isme kya extreme hai	Example
C1	Large $M$ (streaming limit)	$M \to \infty$ , speedup $\to S$	Ex 1
C2	Tiny $M$ ( $M = 1$ , single item)	Fill cost dominate karta hai, koi speedup nahi	Ex 2
C3	Degenerate pipeline ( $S = 1$ )	Pipeline karne ko kuch nahi — sanity floor	Ex 3
C4	Balanced vs unbalanced stages	Ek slow stage $T$ set karta hai	Ex 4
C5	Compute-bound roofline side	$P_{p e ak} < B \cdot I$	Ex 5
C6	Memory-bound roofline side	$B \cdot I < P_{p e ak}$ ; zyada logic useless	Ex 6
C7	Real-world word problem	Latency budget se device choose karo	Ex 7
C8	Exam twist	Clock unit trap + efficiency $\to S$	Ex 8

Related vault topics jo padhte waqt open rakhne chahiye: Pipelining and Throughput, Roofline Model & Arithmetic Intensity, Configurable Logic Blocks (LUTs & Flip-Flops), GPU vs FPGA vs ASIC trade-offs, High-Level Synthesis (HLS), Dataflow architectures.

Upar ke conveyor ko dekho: pehla item (amber) sabhi $S$ benches ke upar crawl karta hai — yahi fill hai. Jab woh exit karta hai, cyan items ek per tick follow karte hain. Yahi ek tasveer hai kyun neeche ke har case ka behavior waise hi hota hai.

C1 — The streaming limit (large $M$ )

Pipelined cycles compute karo. $cycles = S + (M - 1) = 8 + 99, 999 = 100, 007$ . Yeh step kyun? Conveyor picture: pehle item ko pure pipe mein crawl karne ke liye sabhi $S = 8$ ticks chahiye (the fill), aur baaki $M - 1 = 99, 999$ items mein se har ek ek aur tick add karta hai jaise woh uske peechhe pop out hote hain. $8 + 99, 999 = 100, 007$ .
Speedup compute karo. $\frac{M S}{S + M - 1} = \frac{100 , 000 \times 8}{100 , 007} = \frac{800 , 000}{100 , 007} \approx 7.9994$ . Yeh step kyun? Serial CPU se compare kar rahe hain jo $M \cdot S$ ticks spend karta hai.
Interpret karo. Hum ceiling $S = 8$ ke $0.008%$ ke andar hain. Yeh step kyun? Limit $\frac{M S}{S + M - 1} \to S$ as $M \to \infty$ confirm karta hai.

Recall Verify

Jab $M \to \infty$ , top aur bottom dono ko $M$ se divide karo: $\frac{S}{1 + ( S - 1 ) / M} \to S$ . $M = 100, 000$ aur $S = 8$ ke saath, hum $7.9994$ par hain — essentially $8$ . Units: dimensionless (times ka ratio). ✓

C2 — Ek akela item ( $M = 1$ )

Pipeline ke liye cycles. $S + (M - 1) = 8 + 0 = 8$ ticks. Yeh step kyun? $M = 1$ ke saath item ke peechhe overlap karne ke liye kuch nahi hai; woh bas full length crawl karta hai.
Serial CPU ke liye cycles. $M \cdot S = 1 \times 8 = 8$ ticks. Yeh step kyun? Ek item, aath serial operations.
Speedup. $\frac{1 \times 8}{8 + 1 - 1} = \frac{8}{8} = 1$ . Yeh step kyun? Dono machines same time lete hain — pipeline ne zero benefit diya.

Recall Verify

$\frac{M S}{S + M - 1}$ at $M = 1$ gives $\frac{S}{S} = 1$ for any $S$ . Speedup exactly $1$ hai. ✓

C3 — Degenerate pipeline ( $S = 1$ )

Plug in karo. $\frac{M S}{S + M - 1} = \frac{5000 \times 1}{1 + 5000 - 1} = \frac{5000}{5000} = 1$ . Yeh step kyun? Ek stage matlab har item poore datapath ko akele occupy karta hai — doosre item ko overlap karne ki jagah nahi.
Ceiling interpret karo. $M \to \infty$ par limit $S = 1$ hai. Yeh step kyun? Agar sirf ek stage ho to $1 \times$ se aage nahi ja sakte. Ceiling hi stage count hai.

Recall Verify

$S = 1 \Rightarrow \frac{M}{M} = 1$ for all $M$ . Degenerate case correctly "no speedup" report karta hai. ✓

C4 — Unbalanced stages clock set karte hain

Bottleneck dhundho (a). Clock slowest bench se tez tick nahi kar sakti: $T = t_{ma x} = 9 ns$ . Yeh step kyun? Har stage ek clock share karta hai; agar $9 ns$ se tez tick karta to slow stage tick aane par finish nahi hota → galat data (ek timing-closure violation, parent note dekho).
Split se pehle total time (b). $(S + M - 1) T = (4 + 999) \times 9 = 1003 \times 9 = 9027 ns$ . Yeh step kyun? Pipeline-time formula ka seedha use.
Split ke baad (c). Ab $S = 6$ , $T = 3 ns$ : $(6 + 999) \times 3 = 1005 \times 3 = 3015 ns$ . Yeh step kyun? Do aur stages se do extra fill ticks lagte hain, lekin har tick teen guna chhota hai — ek bada net win.
Re-balancing se speedup. $9027/3015 \approx 2.994 \times$ faster. Yeh step kyun? Intuition confirm karta hai: slowest stage sabko throttle kar rahi thi; usse slice karne par clock breathe kar sakta hai.

Recall Verify

Before: $9027 ns$ . After: $3015 ns$ . Ratio $\approx 2.994$ . Units sab ns mein → ratio dimensionless. ✓

C5 — Compute-bound (roofline, right side)

Memory ceiling compute karo. $B \cdot I = 20 GB/s \times 40 ops/byte = 800 GOP/s$ . Yeh step kyun? Yeh wo fastest rate hai jis par memory tumhe feed kar sakti hai.
Min lo. $min (500, 800) = 500 GOP/s$ . Yeh step kyun? Memory $800$ feed kar sakti thi, lekin silicon sirf $500$ chew kar sakta hai — compute wall hai.
Verdict: compute-bound. Zyada BRAM caching add karne se madad nahi milegi; tumhe aur DSP slices / deeper pipeline chahiye. Yeh step kyun? Tum binding constraint fix karte ho, slack wala kabhi nahi.

Recall Verify

$B \cdot I = 800$ , $P_{p e ak} = 500$ , $min = 500$ . Compute-bound kyunki $P_{p e ak} < B \cdot I$ . ✓

C6 — Memory-bound (roofline, left side)

Ceiling (a). $B \cdot I = 20 \times 5 = 100 GOP/s$ ; $min (500, 100) = 100$ . Memory-bound. Yeh step kyun? Memory sirf $100$ feed karti hai; $500$ ka compute zyaadatar idle baitha rehta hai.
Compute double karo (b). $min (1000, 100) = 100 GOP/s$ — unchanged. Yeh step kyun? Tumne slack side wide ki; bottleneck (memory) kabhi nahi hila. Yahi "more logic used ≠ faster" wali galti hai parent note se.
BRAM se intensity raise karo (c). Naya $B \cdot I = 20 \times 30 = 600$ ; $min (500, 600) = 500 GOP/s$ . Yeh step kyun? Cached data reuse karne ka matlab per op fewer DRAM trips → higher $I$ → tum diagonal ke upar slide ho ke compute roof par aa jaate ho. $5 \times$ faster.

Recall Verify

(a) $min (500, 100) = 100$ . (b) $min (1000, 100) = 100$ (no change). (c) $min (500, 600) = 500$ ; $500/100 = 5 \times$ . ✓

C7 — Real-world word problem: device choose karo

FPGA latency (a). Pehla result $S$ ticks ke baad: $20 \times 5 ns = 100 ns = 0.1 μ s$ . Yeh step kyun? Latency = pipeline fill = $S T$ . $10 μ s$ budget se compare karo → vast margin ke saath pass.
FPGA throughput (b). Pipe full hone ke baad har tick mein ek sample emit hota hai, isliye $N = 1000$ samples ka frame $N T = 1000 \times 5 ns = 5 μ s \leq 8 μ s$ leta hai. ✓ Yeh step kyun? Throughput sustained rate hai; frame size $N$ (problem mein given) ko tick $T$ se multiply karne par per-frame time milta hai, aur $5 μ s < 8 μ s$ deadline meet karta hai.
GPU check (c). Throughput $6 μ s \leq 8 μ s$ ✓ lekin latency $50 μ s > 10 μ s$ ✗. Yeh step kyun? GPU throughput pane ke liye batch karta hai, latency budget blow karta hai. Reject karo.
Decision. FPGA dono meet karta hai; GPU latency fail karta hai. FPGA choose karo — classic low-latency streaming win.

Recall Verify

FPGA latency $= 100 ns \leq 10, 000 ns$ ✓; frame time $5 μ s \leq 8 μ s$ ✓; GPU latency $50 μ s > 10 μ s$ ✗. FPGA hi ek device hai jo dono pass karta hai. ✓

C8 — Exam twist: clock-unit trap + efficiency

Clock convert karo (the trap). $T = \frac{1}{200 \times 1 0 ^{6} Hz} = 5 \times 1 0^{- 9} s = 5 ns$ . Yeh step kyun? MHz millions of ticks per second hai; invert karna bhool jaane par nonsense milta hai. Time formula mein plug karne se pehle hamesha frequency ko period mein turn karo.
Pipeline time (a). $(S + M - 1) T = (12 + 9999) \times 5 ns = 10, 011 \times 5 ns = 50, 055 ns \approx 50.06 μ s$ . Yeh step kyun? Seedha pipeline-time formula mein correct $T$ ke saath: 11 fill ticks plus $M - 1 = 9999$ pops, sab $\times 5 ns$ .
CPU time (b). $M \times S \times 1 ns = 10, 000 \times 12 \times 1 ns = 120, 000 ns = 120 μ s$ . Yeh step kyun? Serial machine mein koi overlap nahi: $M = 10, 000$ items mein se har ek ko apne poore $S = 12$ operations ka cost lagta hai, har ek $1 ns$ , toh total $= M \cdot S \cdot 1 ns$ .
Efficiency (c). $\frac{CPU time}{pipeline time} = \frac{120 , 000}{50 , 055} \approx 2.40$ ? Nahi — efficiency yahan speedup matlab hai $\frac{M S}{S + M - 1} = \frac{120 , 000}{10 , 011} \approx 11.99$ . Yeh step kyun? Efficiency honest speedup ratio $\frac{M S}{S + M - 1}$ hai (same total work $M S$ pipe ke actual $S + M - 1$ ticks ke upar). $11.99$ par hum ceiling $S = 12$ ke $99.9%$ par hain, kyunki $11$ -tick fill cost $10, 000$ streamed items ke against negligible hai — yeh exactly $M \to \infty$ limit hai jo $S$ approach karta hai.

Recall Verify

$T = 5 ns$ ; pipe $= 50, 055 ns$ ; CPU $= 120, 000 ns$ ; efficiency $= 120, 000/10, 011 \approx 11.99 \approx S = 12$ . Parent note ke numbers se match karta hai. ✓

Recall check

Kisi bhi

S

-stage pipeline mein ek single item (

M = 1

) ke liye FPGA speedup kya hoga?

Exactly

1

— koi overlap possible nahi, isliye pipelining kuch nahi kharidta.

Memory-bound kernel extra compute units kyun ignore karta hai?

Kyunki

P \leq min (P_{p e ak}, B \cdot I)

aur

B \cdot I

binding term hai;

P_{p e ak}

wide karne par min unchanged rehta hai. Iske bajaye

I

raise karo (BRAM reuse).

Pipeline ka clock period kya set karta hai?

Sabse slow single stage,

T = t_{ma x}

— kabhi average nahi; ise violate karne par timing closure break ho jaati hai.

200 MHz

ko period mein convert karo.

T = 1/ (200 \times 1 0^{6}) = 5 ns

M \to \infty

par

S

-stage pipeline ka speedup ceiling?

S

— ek complete computation har cycle finish hoti hai jab pipe full ho jaata hai.