FPGA-based acceleration: Foundations — Hinglish deep dive

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

Parent note ko comfortably padhne se pehle, tumhe har woh symbol earn karna hoga jo woh tumhare saamne fekta hai. Yeh page har ek ko zero se leta hai: plain words mein kya matlab hai, kaunsi picture banti hai, aur topic ko uski zaroorat kyun hai.

0 · Sab ke peeche do words: gate aur clock

Do light-switches ka picture lo jo is tarah wired hain ki bulb sirf tab jale jab tum dono flip karo: yahi AND gate hai. Har digital chip — CPU, GPU, FPGA — millions of gates ko wire karke bana hai.

Upar wali square wave dekho. Do rising edges ke beech ka gap $T$ hai (seconds mein measure hota hai). Agar $T = 5$ nanoseconds hai, toh chip $200$ million times per second tick karta hai — iska matlab hai " $200$ MHz".

Topic ko $T$ ki zaroorat kyun hai: parent note mein har speed claim cycles ki count ko $T$ se multiply karta hai real time seconds mein paane ke liye. $T$ woh bridge hai "kitne ticks" aur "kitne microseconds" ke beech.

Recall Chhota

$T$ faster clock kyun hota hai? Ticks ke beech chhota gap ::: har second zyada ticks ::: higher frequency $f = 1/ T$ .

1 · Building blocks: LUT, flip-flop, BRAM, DSP

Parent note mein char hardware pieces ka naam hai. Yahan har ek picture ke saath hai.

Figure mein ek 2-input LUT dikha hai jo AND gate ki truth table store karta hai. Char input combinations 00, 01, 10, 11 char addresses hain; stored column 0,0,0,1 hi woh function hai. Stored column change karo aur wahi LUT OR, XOR ban jaata hai — 2 inputs ki koi bhi function.

Ek aisi camera ka picture karo jo exactly har tick par ek photo leta hai aur next tick tak wahi photo dikhata hai. Flip-flops hi woh tarika hai jisse assembly line (pipeline) har stage ka partial result hold karti hai jab tak next tick use aage move nahi kar deta.

Apni desk par ek notepad (BRAM) versus hall ke andar ek filing cabinet (DRAM) ka picture karo. Data notepad par rakhna hi woh reason hai jisse topic baad mein kehta hai "arithmetic intensity badhao" — §5 dekho.

Recall Ek 6-input LUT kitne bits store karta hai?

$2^{6}$ ::: $= 64$ bits.

2 · Sum notation $\sum$ — FIR formula padhna

Parent note ke worked example mein $y [n] = \sum_{k = 0}^{K - 1} c_{k} x [n - k]$ use hota hai. Chalte hain har piece earn karte hain.

$K = 3$ ke liye: $\sum_{k = 0}^{2} c_{k} x [n - k] = c_{0} x [n] + c_{1} x [n - 1] + c_{2} x [n - 2] .$

$x [n]$ = time-step $n$ par input sample (square brackets matlab " $n$ -waa item ek stream mein").
$x [n - 1]$ = ek step pehle wala sample; $x [n - k]$ = $k$ steps pehle.
$c_{k}$ = ek fixed weight (ek "tap coefficient"). $K$ = kitne taps hain.

Topic ko $\sum$ ki zaroorat kyun hai: yeh " $K$ multiply-adds" ko ek symbol mein compress karta hai taaki note baat kar sake saare $K$ ko same cycle mein karne ki, ek ek ke baad ki bajaye.

Recall

$\sum_{k = 0}^{K - 1}$ mein kitne terms add hote hain? $k = 0$ se $k = K - 1$ inclusive tak ::: exactly $K$ terms.

3 · Pipeline symbols: $S$ , $M$ , $t_{ma x}$

Yeh char letters topic ke har speed formula ko drive karte hain.

Figure mein ek 3-stage pipeline ( $S = 3$ ) ek grid ki tarah dikha hai: columns cycles (time) hain, rows stages hain. Item 1 (yellow) ko dekho stage 1 mein enter karta, next tick stage 2 mein move karta, uske agले tick stage 3 mein — yeh $S = 3$ ticks baad exit karta hai. Lekin item 2 (green) bilkul peeche hai, toh pipe fill hone ke baad, har tick ek finished result bahar aata hai.

Topic ko inki zaroorat kyun hai: parent note ka speedup $\frac{M S}{S + M - 1}$ poori tarah $S$ , $M$ , aur cancelled $T$ se bana hai. Woh formula tab tak nahi padh sakte jab tak tumhe pata na ho ki har letter kya picture banata hai.

Recall Throughput ≠ latency kyun?

Latency = pehle result ka time ( $S$ cycles) ::: throughput = fill ke baad results ki rate (har cycle 1); large $M$ ke liye rate dominate karti hai.

4 · Powers, logs, aur $\to$ (limit arrow)

Do mathematical tools topic mein ghus aate hain. Yahan kyun har ek, aur koi doosra nahi.

$K = 8$ ke liye: 4 mein pair karo, phir 2 mein, phir 1 → 3 levels, aur sach mein $lo g_{2} 8 = 3$ hai. Yeh tool kyun: yeh FIR adder tree mein pipeline levels count karta hai — tumhe log chahiye, multiply nahi, kyunki har level count ko halve karta hai.

Speedup par apply karo: $\frac{M S}{S + M - 1}$ . Upar aur neeche $M$ se divide karo: $\frac{S}{1 + ( S - 1 ) / M}$ . Jab $M \to \infty$ toh term $(S - 1) / M \to 0$ , sirf $S$ bachta hai. Yeh tool kyun: yeh claim ko precise banata hai "ek $S$ -stage pipeline $S \times$ speedup ke kareeb pahunchta hai" bina hand-waving ke.

Recall

$lo g_{2} 16 = ?$ 16→8→4→2→1 halve karo, char steps ::: $4$ .

T = 5 ns

ko MHz mein frequency mein convert kar sakta hoon

f = 1/ T = 1/ (5 \times 1 0^{- 9}) = 200 MHz

Main bata sakta hoon ki ek

k

-input LUT kitne bits store karta hai aur kyun

2^{k}

bits, har possible input combination ke liye ek — poori truth table.

Main

\sum_{k = 0}^{2} c_{k} x [n - k]

ko haath se expand kar sakta hoon

c_{0} x [n] + c_{1} x [n - 1] + c_{2} x [n - 2]

Main jaanta hoon ki

S

M

, aur

T

har ek pipeline formula mein kya mean karte hain

S

= stages,

M

= data items,

T

= clock period; time

= (S + M - 1) T

Main explain kar sakta hoon ki

\frac{M S}{S + M - 1} \to S

kyun hota hai jab

M \to \infty

M

se divide karo; fill term

(S - 1) / M \to 0

, sirf

S

bachta hai.

Main

lo g_{2} 8

compute kar sakta hoon aur bata sakta hoon yeh kya count karta hai

3

; 8 numbers ko pairwise sum karne ke liye adder-tree levels ki sankhya.

Main roofline bound aur uski units state kar sakta hoon

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

;

B \cdot I

ki units ops/s hain.

Main latency aur throughput ke beech ka difference explain kar sakta hoon

latency = pehle result ka time (

S

cycles); throughput = results per cycle (fill ke baad 1).

Foundations — FPGA-based acceleration

0 · Sab ke peeche do words: gate aur clock

1 · Building blocks: LUT, flip-flop, BRAM, DSP

2 · Sum notation $\sum$ — FIR formula padhna

3 · Pipeline symbols: $S$ , $M$ , $t_{ma x}$

4 · Powers, logs, aur $\to$ (limit arrow)

5 · Roofline symbols: $P$ , $B$ , $I$

Prerequisite map

Equipment checklist