Exercises — Processing-in-memory (PIM)

KYA karte hain: definition $I=C/N$ apply karo. $I=\frac{2\times 10^6}{8\times 10^6}=0.25\text{ops/byte}$ KYUN yeh question ka jawab deta hai: $I$ hai "har fetched byte par kitna math." Quarter-op per byte matlab hai ki har single operation ke liye hum chaar bytes fetch karte hain — wire almost saara kaam karta hai. Verdict: bahut low $I$ ⇒ bandwidth-bound ⇒ ek acha PIM candidate.

• Processing-using-memory (PUM): memory ki apni physics use karke compute karta hai — woh crossbar jahan Ohm's + Kirchhoff's laws ek matrix–vector multiply karte hain. Dekho Memristor / ReRAM Crossbars.
• Processing-near-memory (PNM): ordinary ALUs/cores jo memory ke side mein rakhe hote hain, jaise ek 3D-stacked HBM stack ke logic die par. Parent se mnemonic: Near = Next to; Using = memory ki apni physics.

False. PIM ki win reduced data movement hai, faster arithmetic nahi — yeh Memory Wall par attack karta hai, jo bus ke across bytes khींchne ki cost hai. (Yahi woh trap hai jo steel-manned just below hai.)

KYA — ops $C$ count karo: har element mein ek multiply + ek add ⇒ $2$ ops each. $C=2M=2\times 5\times 10^6=10^7\text{ops}$ KYUN: operation 2*b[i] + c[i] literally ek multiplication aur ek addition spell out karta hai, aur hum ise $M$ elements mein se har ek ke liye perform karte hain — toh op count simply $2$ per element times $M$ elements hai. KYA — bytes $N$ count karo: b read karo, c read karo, a write karo ⇒ 3 accesses × 4 bytes each. $N=3\times 4\times M=12\times 5\times 10^6=6\times 10^7\text{bytes}$ KYUN: har memory touch bus cross karta hai aur count hona chahiye — do reads (b, c) plus ek write (a) per element, har ek 4-byte float. Write-back bhool jaana classic slip hai (neeche trap dekho). KYA — intensity: $I=\frac{C}{N}=\frac{10^7}{6\times 10^7}\approx 0.167\text{ops/byte}$ KYUN matters hai: $I\approx 0.167$ bahut chhota hai — hum har op ke liye chhe bytes move karte hain. Roofline par (figure s01) yeh flat, bandwidth-bound zone mein bahut left land karta hai ⇒ acha PIM candidate.

KYA — internal bandwidth: $B_{int}=k\cdot B_{bank}=8\times 10=80\text{GB/s}$ KYUN: $k=8$ banks mein se har ek apne data ko simultaneously read aur compute karta hai; kyunki woh parallel mein run karte hain, unke bandwidths add hote hain. Yahi internal parallelism woh resource hai jo external bus kabhi expose nahi kar sakta. KYA — speedup (bandwidth-bound approximation): $\text{Speedup}\approx \frac{B_{int}}{B}=\frac{80}{40}=2.0\times$ KYUN yeh ratio: bandwidth-bound job ke liye runtime set hota hai ki bytes kitni tezi se flow karte hain. PIM $B=40$ GB/s wire ko $B_{int}=80$ GB/s internal flow se replace karta hai, toh time bandwidth ratio se shrink hota hai — yahan $2\times$. (Jab compute time negligible nahi hoti tab yeh over-estimate karta hai; full timing jo gap expose karta hai woh Exercise 5.2 mein hai.)

KYA hum build karte hain: per byte hum $I=0.1$ ops karte hain, toh per byte:

• compute energy $=I\cdot E_{op}=0.1E_{op}$
• move energy $=1\cdot E_{move}=200E_{op}$

KYUN per byte split karo: "per byte moved" normalize karna dono energies ko same footing par compare karne deta hai — ek move event (cost $200E_{op}$) against woh fraction of op jo woh byte earn karta hai ($0.1E_{op}$). Moving ka fraction: $\frac{E_{move}}{E_{move}+E_{compute}}=\frac{200}{200+0.1}=\frac{200}{200.1}\approx 0.9995=99.95\%$ Interpretation: essentially saari energy data move karne mein jaati hai. Yahi wajah hai PIM exist karta hai — movement cut karo aur aap almost poora energy bill cut kar dete ho.

Ops: $C=2n^3=2\times 500^3=2\times 1.25\times 10^8=2.5\times 10^8$. Bytes: $N=3n^2\times 4=12n^2=12\times 250000=3\times 10^6$. Intensity: $I=\frac{2.5\times 10^8}{3\times 10^6}\approx 83.3\text{ops/byte}$ Analysis: $I\approx 83$ vector add ke $0.167$ ke comparison mein bahut bada hai. Matrix multiply har loaded value ko $O(n)$ times reuse karta hai, toh yeh compute-bound hai — caches aur fast ALUs already ise feed karte rehte hain. PIM ka bandwidth win barely apply hota hai. Dekho Roofline Model.

Amdahl's Law: agar runtime ka ek fraction $p$ ko $s$ se speed up kiya jaye, aur baaki ($1-p$) unchanged rahe, toh overall speedup hai $\text{Speedup}=\frac{1}{(1-p)+\frac{p}{s}}$ KYUN yeh tool: PIM sirf job ke movement part ko accelerate karta hai; baaki ek serial anchor hai. Amdahl exactly "kya hota hai jab aap sirf ek slice speed up karo" wala sawaal hai. Plug in $p=0.70,s=4$: $\frac{1}{0.30+\frac{0.70}{4}}=\frac{1}{0.30+0.175}=\frac{1}{0.475}\approx 2.105\times$ 4× local win bhi sirf ~2.1× overall deta hai — untouched 30% aapko cap karta hai.

Amdahl mein $s\to \infty$ let karo: term $p/s\to 0$ ho jaata hai, yeh bachta hai: ${\text{Speedup}}_{\max }=\frac{1}{1-p}=\frac{1}{0.30}\approx 3.33\times$ Proof it delivers: chahe PIM kitna bhi acha ho jaye, serial 30% aapko 3.33× par cap karta hai. Isliye bandwidth-bound fraction $p$ measure karna $s$ tune karne se zyada matter karta hai — ceiling $p$ mein rehti hai.

Symbol note: yahan $\mathbf{I}$ (boldface, components $I_i$) ek electric current vector hai — nahi pehle wale problems ki arithmetic intensity $I$. Same letter, alag duniya; boldface aur "amps" units dono ko alag rakhte hain. KYUN crossbar yeh ek shot mein karta hai: har crosspoint Ohm's law $I_{ij}=G_{ij}{V}_j$ follow karta hai; shared row wire par currents add hote hain (Kirchhoff), jisse milta hai $I_i={\sum }_j{G}_{ij}{V}_j$ — ek dot product per row, saari rows parallel mein. Neeche figure s02 mein trace karo: input voltages $V_j$ (lavender arrows) columns ke neeche enter karte hain, har crosspoint conductance (coral dots) apni column ki voltage ko current mein scale karta hai, aur currents har mint row wire ke saath rightward merge hote hain output $I_i$ (coral arrows) mein. Row by row ($\mathbf{I}=G\mathbf{V}$):

• $I_1=1(1)+0(0)+2(2)+0(1)=1+0+4+0=5$
• $I_2=0(1)+3(0)+0(2)+1(1)=0+0+0+1=1$
• $I_3=2(1)+1(0)+0(2)+0(1)=2+0+0+0=2$
• $I_4=0(1)+0(0)+1(2)+4(1)=0+0+2+4=6$

$\mathbf{I}=(5,1,2,6{)}^{\top }\text{amps (device units mein)}$ Step count: crossbar yeh ek analog step mein karta hai ($O(1)$). Ek CPU ko $n^2=16$ multiply-accumulates chahiye ($O(n^2)$). Woh $O(n^2)\to O(1)$ collapse isliye hai kyun PIM Neural Network Accelerators ko love karta hai.

(a) Amdahl with $p=0.90,s=50$: $\frac{1}{(1-0.90)+\frac{0.90}{50}}=\frac{1}{0.10+0.018}=\frac{1}{0.118}\approx 8.47\times$ (b) Error-tolerant workloads ke liye acceptable hai — neural network inference chhote numeric noise tolerate karta hai (training ne already robustness add ki hai). Unacceptable exact workloads ke liye jaise IEEE-precise finance ya cryptography, jahan ek drifted conductance result corrupt kar deta hai. PUM exactness ko speed ke liye trade karta hai.

W1 → PNM. Bahut low $I$ ⇒ bandwidth-bound ⇒ PIM helps. Lekin yeh exact hona chahiye, toh hum analog PUM (approximate) use nahi kar sakte. Digital near-memory ALUs bandwidth win aur exactness dono dete hain. W2 → PUM crossbar. Matrix–vector multiply crossbar ka native $O(1)$ operation hai; 1% error tolerance analog imprecision suit karta hai. Ideal PUM case. W3 → plain CPU/GPU. $I\approx 167$ ⇒ compute-bound, toh bytes already caches ke andar heavily reuse ho rahe hain aur PIM ka bandwidth win barely helps karta hai. Upar se job IEEE-exact honi chahiye, jo analog PUM ko poori tarah rule out karta hai. Ise GPU par rakhein, jahan cache se fed fast ALUs exactly sahi tool hain. Dekho Roofline Model.

Internal bandwidth: $B_{int}=12\times 12=144$ GB/s $=144\times 10^9$ B/s. (a) Baseline: $T_{vN}=\frac{9\times 10^9}{30\times 10^9}+\frac{4.5\times 10^8}{10^9}=0.30+0.45=0.75\text{s}$ (b) PIM: $T_{PIM}=\frac{9\times 10^9}{144\times 10^9}+\frac{4.5\times 10^8}{10^9}=0.0625+0.45=0.5125\text{s}$ (c) Actual speedup: $\frac{T_{vN}}{T_{PIM}}=\frac{0.75}{0.5125}\approx 1.463\times$ Naive estimate $B_{int}/B=144/30=4.8\times$. Gap explained: naive ratio assume karta hai ki job pure movement hai. Yahan compute term $C/R=0.45$ s bada hai aur PIM se unchanged — woh naya bottleneck ban jaata hai. Yahi exactly Amdahl's ceiling hai: PIM ne sirf $0.30$ s movement part shrink kiya, $0.45$ s compute part nahi. Hamesha poora $T$ compute karo, kabhi $B_{int}/B$ par alone trust mat karo.