Visual walkthrough — Domain-specific accelerators

6.5.6 · D2 · Hardware › Advanced & Emerging Architectures › Domain-specific accelerators

Ye raha poora safar, shuru karne se pehle:

---

Step 1 — Atom: ek multiply-accumulate

KYA HAI. Chip jo sabse chhota kaam karta hai woh hai: do numbers lo, unhe multiply karo, aur result ko ek running total pe add karo. Ise hum multiply-accumulate kehte hain, likha jaata hai MAC. Symbols mein:

$$\underset{\text{running sum}}{\underbrace{s}}\leftarrow \underset{\text{old sum}}{\underbrace{s}}+\underset{\text{one number}}{\underbrace{a}}\times \underset{\text{another number}}{\underbrace{b}}$$

Arrow "$\leftarrow$" padhiye "ban jaata hai" — left wala box right side ki value se update hota hai. Toh $s$ har baar ek naya product $a\times b$ "kha" leta hai. $a$, $b$, $s$ mein se har ek ek machine word hai.

MAC kyun, plain multiply kyun nahi? Kyunki matrix multiplication sirf "do numbers multiply karo aur total mein add karo" ka ek bada dhera hai. Agar kaam ka atom multiply-then-add hai, toh hardware ka atom bhi exactly wahi banao — koi waste nahi.

PICTURE. Ek cell: do inputs aate hain, product banta hai, aur woh andar baithe sum pe gir jaata hai.

---

Step 2 — MACs ko stack karke matrix multiply banana

KYA HAI. Matrix sirf numbers ki ek grid hoti hai. Do grids $A$ aur $B$ ko multiply karke result grid $C$ banane ke liye, $C$ ki har entry $A$ ki ek row ko $B$ ke ek column ke upar slide karke, pair by pair MAC-ing se banti hai. Hum $N$ use karte hain square grid ki side length ke liye — toh ek $N\times N$ grid mein $N$ rows aur $N$ columns hote hain. (Hum matrices ko square isliye rakhte hain taaki counting clean rahe; Step 8 mein dikhaya gaya hai ki general rectangular case bhi same behave karta hai.)

Ek output entry $C_{ij}$ (row $i$, column $j$) ke liye:

$$C_{ij}=\sum _{k=1}^N\underset{\text{row }i\text{ of }A}{\underbrace{A_{ik}}}\times \underset{\text{col }j\text{ of }B}{\underbrace{B_{kj}}}$$

• ${\sum }_{k=1}^N$ matlab hai "add karo jab $k$, $1,2,\dots ,N$ count kare" — woh hai $N$ MACs stacked.
• $A_{ik}$ row $i$ ke along chalta hai; $B_{kj}$ column $j$ ke neeche chalta hai. Dono matching position $k$ par milte hain.

Aisa count kyun karte hain? Kyunki "CPU vs accelerator" ka fair comparison karne ke liye pehle jaanna zaroori hai ki kaam mein kitna math actually hai aur kitna data actually touch hota hai. Woh comparison hi poori kahani hai, isliye hum dono count aage karte hain.

PICTURE. Ek row ek column ke upar sweep hoti hai, pairs ek single MAC ko feed karte hain jo $C_{ij}$ badhata hai.

Recall Ek output entry ko kitne MACs chahiye?

Exactly $N$ ::: har ek value of $k$ ke liye ek, $1$ se $N$ tak.

---

Step 3 — Math count karna: $N^3$ operations

KYA HAI. $C$ mein $N\times N=N^2$ entries hain, aur har ek ko $N$ MACs chahiye (Step 2). Multiply karo:

$$\text{total MACs}=\underset{\text{entries in }C}{\underbrace{N^2}}\times \underset{\text{MACs per entry}}{\underbrace{N}}=N^3$$

Yeh number kyun matter karta hai. $N^3$ woh unavoidable kaam hai — koi bhi smart memory trick ek bhi multiply nahi hata sakta. Yeh us ratio ka numerator hai jis ki hum care karte hain. Ise yaad rakho.

PICTURE. Output grid, ek highlighted cell explode hokar uske $N$ MACs dikhata hai; cells ki sankhya se multiply.

---

Step 4 — Traffic count karna: naive machine $\approx 2N^3$ words move karti hai

KYA HAI. Ab ek sneaky part: numbers kahan se aate hain? Upar ke memory model ko fix karo: ek output entry ke liye running sum $s$ ek register mein rehta hai jab tak uske $N$ MACs chalte hain, isliye woh free mein read aur write hota hai — yeh kabhi main memory touch nahi karta jab tak finish nahi ho jaata. Sirf inputs $A_{ik}$ aur $B_{kj}$ har MAC pe memory se re-fetch hote hain, kyunki ek naive machine ke paas koi scratchpad nahi hoti unhe hold karne ke liye.

Har MAC mein do input reads count karo, phir finished results write karna add karo:

$$Q_{\text{naive}}=\underset{\begin{array}{c}\text{read }{A}_{ik}\\ \text{read }{B}_{kj}\end{array}}{\underbrace{2}}\times \underset{\text{MACs}}{\underbrace{N^3}}+\underset{\begin{array}{c}\text{write each finished}\\ C_{ij}\text{ once}\end{array}}{\underbrace{N^2}}=2N^3+N^2\text{ words}$$

• $2N^3$ term: har ek $N^3$ MACs apne do inputs memory se fresh pull karta hai (no reuse).
• $N^2$ term: $N^2$ output entries mein se har ek memory mein ek baar likhi jaati hai, apna register-resident sum complete hone ke baad — har MAC pe nahi.

Bade $N$ ke liye input re-fetches dominate karte hain, toh $Q_{\text{naive}}=2N^3+N^2\approx 2N^3$ words. Ise bytes mein convert karne ke liye, word width $w$ se multiply karo: $Q_{\text{naive}}^{\text{bytes}}\approx 2N^{3}w$. $Q$ (quantity of data ke liye) main memory mein aane-jaane wala traffic hai.

$W$ se alag $Q$ kyun count karna zaroori hai? Kyunki chips ke paas do speed limits hoti hain: kitni tez compute kar sakte hain ($W$) aur kitni tez data move kar sakte hain ($Q$). Jo pehle khatam hota hai woh rokta hai. $Q$ count karna batata hai ki hum kaunsi wall se takraenge.

PICTURE. Ek narrow pipe (memory) ek bhukkha MAC feed kar raha hai jo har cycle mein dono inputs re-fetch karta hai, jabki sum $s$ chip ke register mein safely wait kar raha hai.

---

Step 5 — Arithmetic intensity: math ko traffic se divide karna

KYA HAI. Arithmetic intensity $I$ define karo as aap jo data move karte ho uski har unit ke liye kitna math karte ho:

$$I=\frac{W}{Q}=\frac{\text{operations}}{\text{bytes moved}}$$

Naive machine ke liye, Steps 3 aur 4 plug in karo. Bytes mein count karte hue, $Q_{\text{naive}}^{\text{bytes}}=(2N^3+N^2)w$:

$$I_{\text{naive}}=\frac{N^3}{(2N^3+N^2)w}=\frac{1}{(2+\frac{1}{N})w}\underset{N\to \infty }{\to }\frac{1}{2w}$$

Jab $N$ badhta hai toh $\frac{1}{N}$ gayab ho jaata hai, isliye intensity constant $\frac{1}{2w}$ pe flatten ho jaati hai — yeh problem size ke saath grow nahi karti. Ek billion-element matrix ki intensity utni hi bekar hogi jitni ek badi matrix ki.

Raw $W$ ya raw $Q$ ki jagah yeh ratio kyun? Kyunki chip ki real speed compute aur bandwidth ke balance se cap hoti hai, aur $I$ exactly wahi balance ek number mein hai. Low $I$ = "starvation": memory ke bahut saare trips, bahut kam math ke liye. High $I$ = "well fed": har expensive word bahut saare cheap operations kamaata hai.

PICTURE. Ek balance scale — left pe words ka bada dhera, right pe ops ka chhota dhera — "memory-bound" ki taraf jhukta hua.

---

Step 6 — Systolic fix: ek baar load karo, $N$ baar reuse karo

KYA HAI. Re-fetching ki jagah, ek $N\times N$ systolic array ek value ek baar load karta hai aur use MAC cells ki poori row mein hand-to-hand pass karta hai (ya poore column mein neeche). Jo number edge pe enter karta hai woh $N$ alag-alag MACs mein participate karta hai nikalne se pehle. Toh math unchanged hai ($W=N^3$) lekin traffic collapse ho jaata hai.

$Q_{\text{systolic}}$ derive karo — aur pehle constant define karo. Maano $c$ un full matrices ki sankhya hai jo memory boundary cross karti hain. Exactly teen hain: $A$ padho, $B$ padho, $C$ likho. Toh $c=3$. Har matrix $N\times N=N^2$ words ki hai. Isliye traffic $N^2$ ke $c$ copies hain:

Q_{\text{systolic}} \;=\; c\,N^2 \;=\; \underbrace{N^2}_{\text{read all of }A}\; +\; \underbrace{N^2}_{\text{read all of }B}\; +\; \underbrace{N^2}_{\text{write all of }C}\; =\; 3N^2 \;\text{ words}$$ Ise Step 4 se compare karo, jahan do input reads *har MAC pe* hoti thi ($2N^3$). Systolic array har input read *har matrix ke liye* pay karta hai ($N^2$ each), kyunki har input word, ek baar array edge pe load hone ke baad, poori row/column mein reuse hota hai drop hone se pehle. **Running sums $s$ ka kya?** Bilkul naive model ki tarah, partial sums **kabhi main memory nahi jaate** — lekin ab woh CPU register ki jagah *MAC cells ke andar* rehte hain. Ek sum ek cell mein janam leta hai, data stream hote waqt on-chip apne $N$ products accumulate karta hai, aur sirf finished value $C_{ij}$ write out hoti hai — woh write $C$ ke liye $N^2$ mein already included hai. Toh kisi bhi model mein sums ke liye koi extra $N^3$ term kabhi appear nahi hota.

I_{\text{systolic}} ;=; \frac{W}{Q} ;=; \frac{N^3}{3N^2} ;=; \frac{N}{3} ;=; O(N)

- Akela $N$ jo survive karta hai woh punchline hai: **intensity ab array size ke saath grow karti hai.** Bada array → har loaded number zyada reuse hota hai → higher $I$. - (Bytes mein word width $w$ phir $Q$ ko multiply karta hai, giving $I=N/(3w)$ — phir bhi $O(N)$, kyunki $w$ ek fixed constant hai.) **Yeh Step 5 se kyun behtar hai?** Kyunki naive $\tfrac12$ kabhi improve nahi hota, lekin $N/3$ improve hota hai jis pal aap bada grid banate ho. Tumne ek fixed, low intensity ko ek aisi cheez mein convert kar liya jo tum *scale up* kar sakte ho. **PICTURE.** Ek value left edge se enter karti hai aur MAC cells ki poori row mein rightward hand hoti hai — har stop par reuse hoti hai, partial sums on-chip rehte hain, re-fetch hone ki jagah. ![[deepdives/dd-hardware-6.5.06-d2-s06.png]] > [!intuition] "Systole" mental model > Jaise dil ki dhadkan blood ko cell-to-cell pump karti hai, data bhi har clock pe grid mein pulse karta hai. Koi bhi cell main memory se baat nahi karta — sirf apne neighbours se. Sums apni jagah tike rehte hain; sirf inputs flow in karte hain aur finished outputs flow out karte hain. Wahi neighbour-passing *hai* reuse. > [!recall]- Naive $I\to\tfrac12$ kyun deta hai lekin systolic $O(N)$ kyun deta hai? > Naive $\approx 2N^3$ words move karta hai ($A$ aur $B$ inputs ko har MAC pe re-fetch karta hai; sum register mein rehta hai), toh $N^3$ cancel ho jaata hai aur $I$ ek constant pe flatten ho jaata hai ::: systolic sirf $3N^2$ words move karta hai ($A$ padho, $B$ padho, $C$ likho — har ek ek baar), har loaded input ko poori row mein reuse karta hai, toh $N$ ka ek factor survive karta hai. --- ## Step 7 — Verdict padhna: Roofline model **KYA HAI.** Ek chip ke paas do ceilings hoti hain. $P_{\text{peak}}$ = uski top compute rate (operations per second). $B$ = uski memory bandwidth (bytes per second). **Attainable** performance woh ceiling hai jo pehle hit ho:

P_{\text{attain}} ;=; \min!\Big(;\underbrace{P_{\text{peak}}}{\text{compute wall}},;; \underbrace{B\times I}{\text{memory wall}};\Big)

Memory wall product $B\times I$ kyun hai? Kyunki ek second mein tum $B$ bytes move karte ho, aur har byte $I$ operations kamaata hai, toh tumhe $B\times I$ operations milte hain — yeh tumhari speed hai *agar memory limit hai*. - Agar $B\times I < P_{\text{peak}}$: **memory-bound.** Tum roof ke sloped part pe ho. Zyada MACs se kuch nahi hoga. - Agar $B\times I > P_{\text{peak}}$: **compute-bound.** Tum flat part pe ho. Ab zyada MACs kaam aayenge. **Systolic array jawab kyun change karta hai?** Naive $I\to\tfrac12$ tumhe slope pe kaafi neeche pin karta hai (memory-bound). $I$ ko $O(N)$ tak raise karna tumhe rightward slide karta hai jab tak flat compute ceiling nahi aati — exactly wahan jahan MACs worth having hain. **PICTURE.** Roofline: sloped memory line, flat compute line, ek dot low-$I$ pe (naive, memory-bound) right slide karta hua corner tak (systolic, compute-bound). ![[deepdives/dd-hardware-6.5.06-d2-s07.png]] > [!example] Roof pe numbers daalna > Chip: $P_{\text{peak}} = 90$ TOPS, $B = 300$ GB/s. (Yahan $I$ ops **per byte** mein quoted hai.) > - Naive kernel, $I = \tfrac13$: memory ceiling $= 300\times10^{9}\times\tfrac13 = 100\times10^{9} = 0.1$ TOPS. Verdict $\min(90,\,0.1) = \mathbf{0.1}$ **TOPS** — chip ka lagbhag $0.11\%$ use ho raha hai. > - Systolic, $I = 50$: memory ceiling $= 300\times10^{9}\times 50 = 15\times10^{12} = 15$ TOPS. Verdict $\min(90,\,15) = \mathbf{15}$ **TOPS** — *same* silicon se 150× zyada real kaam, sirf reuse badhane se. --- ## Step 8 — Edge, degenerate aur non-square cases (koi gap mat chhodna) **KYA HAI aur KYU — woh cases jo ek smart reader zaroor poochhega:** 1. **$N=1$ (ek single number "matrix").** Tab $W=1$, aur $I_{\text{systolic}}=N/3=1/3=O(1)$. Koi reuse possible nahi — neighbour ko dene ke liye kuch hai hi nahi. **Systolic array scalar work ke liye zero advantage deta hai.** Yahi wajah hai ki ek DSA narrow hota hai aur odd bits ke liye ek [[Heterogeneous computing|CPU]] ke saath pair karta hai. 2. **$N$ array width se chhota.** Agar tumhari matrix $8\times8$ hai lekin grid $128\times128$ ka hai, toh zyada cells idle hain — reuse $128$ nahi, $8$ tak capped hai. **Array ko under-filling waste hai;** real compilers tile aur pad karte hain use full rakhne ke liye. 3. **Non-square matrices ($M\times K$ times $K\times N$).** Bilkul same accounting apply hoti hai: kaam hai $W = M\,K\,N$ MACs, aur traffic teen matrices ek baar read/write, $Q = MK + KN + MN$ words. Tab intensity hai $I = \dfrac{MKN}{MK+KN+MN}$. Jab teenon dimensions comparable aur itni badi hain ki *grid fill* ho sake, yeh phir bhi $O(\text{dimension})$ hai — same win. Agar ek dimension tiny ho (jaise $K=1$, ek outer product), toh denominator numerator ke relative nahi shrinkta aur reuse collapse ho jaata hai. **$O(N)$ scaling ek promise hai sirf tab jab tum har direction mein array fill kar sako.** 4. **Bandwidth $B\to\infty$ (imagined infinite memory).** Tab $B\times I$ hamesha huge hai, toh $P_{\text{attain}}=P_{\text{peak}}$ *kisi bhi* $I$ ke liye. Reuse matter hi nahi karta — yeh prove karta hai ki reuse sirf isliye matter karta hai kyunki real memory slow hai. Yeh ek real bimari ka ilaaj hai. 5. **$P_{\text{peak}}\to\infty$ (imagined infinite MACs).** Tab $P_{\text{attain}}=B\times I$, poora intensity se fix hota hai. MACs khareedna pure waste hai jab tak $I$ nahi badhta — bilkul wahi trap jiske baare mein [[Roofline model]] warn karta hai. **PICTURE.** Roofline degenerate corners ke liye redraw: $N=1$ dot slope pe stuck, aur "infinite bandwidth" flat-everywhere roof. ![[deepdives/dd-hardware-6.5.06-d2-s08.png]] > [!mistake] "Bada array banao aur koi bhi workload ud jaayega." > **Kyun sahi lagta hai:** bada grid = higher peak $I$ ceiling. **Fix yeh hai:** cases 2–3 — agar *matrix* chhoti ya kisi dimension mein thin hai, toh reuse matrix se set hoti hai, grid se nahi. Array tab hi help karta hai jab problem itni badi ho ki use har direction mein fill kar sake. --- ## Ek picture summary Upar ki sab baatein, compressed: do counts ($W=N^3$, aur $Q\approx 2N^3$ naive vs $3N^2$ systolic) ek intensity $I$ banti hain, aur $I$ decide karta hai ki tum roofline pe kahan land karte ho — naive ek constant pe memory-bound stuck, systolic $O(N)$ ke roop mein compute-bound push kiya gaya. ![[deepdives/dd-hardware-6.5.06-d2-s09.png]] > [!recall]- Feynman retelling — aise bolo jaise kisi dost ko explain kar rahe ho > Matrix multiply "do numbers multiply karo, total mein add karo" ka ek pahaad hai — math ka woh pahaad, $N^3$ ooncha, kabhi nahi shrinkta. Asli sawaal yeh hai: har multiply ke liye, kya tum slow memory mein do *inputs* ke liye fresh trip karte ho? (Running total problem nahi hai — woh register mein ya cell ke andar baithta hai aur sirf ek baar write out hota hai.) Dumb machine dono inputs har multiply pe re-fetch karti hai — lagbhag $2N^3$ trips — toh woh saara din fetch karne mein bitaati hai aur barely compute karti hai; uska "math-per-word" score lagbhag one-half pe flatten ho jaata hai chahe kaam kitna bhi bada ho. Clever trick hai tiny adders ki ek grid jahan ek input, ek baar load hone ke baad, *row ke saath haath mein haath daake nikalta hai* aur har cell pe reuse hota hai jahan se bhi guzarta hai. Toh tum memory sirf teen baar *per matrix* touch karte ho — $A$ padho, $B$ padho, $C$ likho, woh hai $3N^2$ words — har multiply ke liye nahi. Ab math-per-word grid size ke saath badhta hai, $N/3$. Ise roofline pe plot karo — ek chart jiska slanted line tumhari memory speed hai aur flat line tumhari raw compute speed hai — aur dumb machine slope par kaafi neeche baithe hai (starved), jabki systolic machine right slide karti hai jab tak flat top nahi chhooti, finally woh MACs use karte hue jiske liye pay kiya. Catch yeh hai: agar matrix tiny hai ($N=1$) ya kisi direction mein thin hai, toh neighbour ko dene ke liye kuch hai hi nahi aur poori trick evaporate ho jaati hai — exactly isliye yeh chips specialists hain, CPU ke replacements nahi. --- **Prerequisites aur neighbours:** [[Domain-specific accelerators (index 6.5.6)]] · [[Systolic arrays]] · [[Roofline model]] · [[TPU (Tensor Processing Unit)]] · [[Dennard scaling]] · [[Dark silicon]] · [[Amdahl's Law]] · [[Pollack's Rule]] · [[Heterogeneous computing]] · [[Quantization]] · [[GPU vs TPU]] · [[Mixed precision training]]