Approximate computing techniques: Exercises — Hinglish deep dive

6.5.16 · D4 · Hardware › Advanced & Emerging Architectures › Approximate computing techniques

Shuru karne se pehle, ek 30-second symbol refresher taaki koi bhi naya symbol achanak saamne na aaye:

Definition Woh symbols jo hum baar baar use karte hain

$n$ = bit-width: kitne binary digits (0/1) hum ek number store karne ke liye use karte hain. Zyada bits = zyada precision, bada circuit.
$V$ = supply voltage jo transistors ko drive karta hai. Isko electrons ke peeche "push" samjho.
$P = α C V^{2} f$ = dynamic power (energy per second burn hoti hai). $α$ = fraction of transistors switching, $C$ = capacitance (har switch kitna charge move karta hai), $f$ = clock frequency. Dekho Dynamic Power P = alpha C V^2 f.
$E$ = error = (approximate answer) − (exact answer). Relative error = $∣ E ∣ / ∣ exact ∣$ , yaani error as a fraction of true size.
$μ$ = mean (average) of a set of numbers: sab ko add karo, kitne hain uspe divide karo. Agar tum $N$ numbers ka sum karo jinka average $μ$ hai, toh sum lagbhag $N μ$ hoga.
$σ$ = standard deviation: mean ke aas-paas wobble ka typical size. Chhota $σ$ = errors zero ke paas tight cluster karte hain; bada $σ$ = woh spread out hote hain. Iska square $σ^{2}$ variance hai, jo tab add hoti hai jab tum independent errors combine karte ho.

Definition PSNR — image-quality metric jo hum baar baar use karte hain

PSNR = Peak Signal-to-Noise Ratio, decibels (dB) mein measure hota hai. Yeh ek picture ko uske perfect original ke saath compare karta hai aur poochta hai "true signal, hamari introduce ki gayi error ke comparison mein kitna bada hai?" Roughly: $PSNR = 10 lo g_{10} (\frac{peak signal ^{2}}{mean squared error}) .$ Isko use karne ke liye tumhe formula yaad rakhne ki zaroorat nahi — bas intuition chahiye:

Higher dB = better (kam visible error). $\infty$ dB = pixel-perfect.
Kyunki yeh ek logarithm hai, dB ek badi range ko compress karta hai: har $+ 10$ dB ka matlab hai error power mein ~ $10 \times$ shrink ho gayi.
Rules of thumb: $≳ 40$ dB aankhon ko flawless lagta hai; $\sim 30$ dB noticeable artefacts dikhata hai. Isliye exercises mein "PSNR $\geq 40$ dB" jaisi bounds set ki jaati hain.

Level 1 — Recognition

L1.1

Har technique ke liye, batao yeh stack ke kis layer mein hai (circuit / arithmetic / software-loop / memory / voltage): (a) loop perforation, (b) truncated multiplier, (c) DRAM refresh rate kam karna, (d) safe voltage se neeche run karna.

Recall Solution L1.1

(a) Software-loop — hum loop iterations skip karte hain; koi hardware change nahi chahiye.
(b) Arithmetic circuit — hum multiplier ko redesign karte hain taaki low-order partial products drop ho jaayein.
(c) Memory — kam refreshes se kuch DRAM cells decay karte hain → stored data mein bit flips. Dekho DRAM Refresh and Memory Reliability.
(d) Voltage — voltage overscaling (VOS); sabse slow paths par rare timing errors.

L1.2

Inme se kaunsa approximate karna safe hai, aur kaunsa exact rehna chahiye? (a) ek pixel colour ke mantissa ke least-significant bits, (b) ek loop-bound counter, (c) ek FP32 number ka exponent, (d) ek summed sensor reading.

Recall Solution L1.2

(a) Safe — pixel ke LSBs perceptually invisible hote hain.
(b) Exact — ek corrupted loop bound loop ko forever chala sakta hai ya crash kar sakta hai. Control flow critical hai.
(c) Exact — exponent magnitude set karta hai. Ek bit flip karo aur number $2^{128}$ factor se jump kar sakta hai. Dekho Precision and Number Formats (FP32, FP16, INT8).
(d) Safe — aggregation per-reading error ko absorb kar leti hai.

Level 2 — Application

L2.1

Ek $8 \times 8$ array multiplier ko $4 \times 4$ se replace kiya gaya hai (precision $n = 8$ se $n = 4$ tak half ho gayi). $E_{mult} \propto n^{2} V^{2}$ use karte hue fixed $V$ par, multiplier energy kis factor se girti hai?

Pehle, multiplier energy $n^{2}$ ki tarah kyun badhti hai? Neeche diye figure ko dekho. Ek $n \times n$ array multiplier do $n$ -bit numbers ko multiply karta hai AND gates aur full-adder cells ka ek grid bichhaake: ek operand ke $n$ bits mein se har ek doosre ke $n$ bits mein se har ek ke saath combine hota hai, partial-product cells ka ek $n \times n$ array banata hai. Yeh literally hardware ka ek $n$ -by- $n$ square hai — $n$ rows $\times$ $n$ columns $= n^{2}$ cells. Kyunki har cell roughly same switching energy $\propto V^{2}$ burn karta hai, poora multiplier $\approx n^{2} V^{2}$ burn karta hai. Yeh law ke peeche geometric reason hai (dekho Ripple-Carry vs Array Multipliers).

Figure — Approximate computing techniques

Recall Solution L2.1

Energy ratio $= \frac{n _{new}^{2}}{n _{old}^{2}} = \frac{4 ^{2}}{8 ^{2}} = \frac{16}{64} = \frac{1}{4} .$ Toh energy one quarter ho jaati hai — ek $4 \times$ saving. $n^{2}$ kyun, sirf $n$ kyun nahi? Cell count ek $n \times n$ square ka area hai, isliye $n$ half karne se area quarter ho jaata hai (jaise ek square ki side half karne se area quarter ho jaati hai). Isliye bit-width half karna itna powerful lever hai.

L2.2

Dynamic power hai $P = α C V^{2} f$ . Hum voltage $V = 1.0 V$ se $V = 0.8 V$ tak overscale karte hain, $α, C, f$ fixed rakhte hue. Original power ka kitna fraction hum bachate hain?

Recall Solution L2.2

Power $V^{2}$ ke saath scale karta hai, isliye $\frac{P _{new}}{P _{old}} = \frac{0. 8 ^{2}}{1. 0 ^{2}} = 0.64.$ Saving $= 1 - 0.64 = 0.36 = 36%$ . Baaki $64%$ hum abhi bhi pay karte hain.

L2.3

$A = 1.375$ aur $B = 1.500$ multiply karo. Exact product ke liye kuch fractional bits chahiye; hum 3 fractional bits tak truncate karte hain ( $2^{- 3} = 0.125$ resolution). Truncated value, absolute error, aur relative error nikalo.

Recall Solution L2.3

Exact: $1.375 \times 1.500 = 2.0625$ .
$0.125$ ke multiples tak truncate karo (tail drop karo, neeche round karo): $2.0625 \to 2.000$ (kyunki $2.0625 = 2.000 + 0.0625$ , aur $0.0625 < 0.125$ isliye 3rd fractional bit set nahi hai).
Absolute error $= 2.0625 - 2.000 = 0.0625$ .
Relative error $= 0.0625/2.0625 \approx 0.0303 = 3.03%$ .

Level 3 — Analysis

L3.1

Tum $N = 10, 000$ numbers sum karte ho, jinka mean $μ = 5$ hai (refresher se yaad karo: $μ$ har summand ka average value hai, $σ$ injected wobble ka typical size hai). Do approximation schemes:

Scheme U (unbiased): har addition independent zero-mean error add karta hai standard deviation $σ = 0.1$ ke saath.
Scheme B (biased): har addition hamesha ek fixed $b = 0.01$ lose karta hai (systematic).

Har ek ke under final sum ki relative error estimate karo. Kaunsa jeetatA hai aur kyun?

Recall Solution L3.1

Signal (true sum) $\approx N μ = 10, 000 \times 5 = 50, 000$ .

Scheme U — errors quadrature mein add hote hain (variances $σ^{2}$ sum hoti hain): $typical error = N σ = 10, 000 \times 0.1 = 100 \times 0.1 = 10.$ Relative error $= 10/50, 000 = 2 \times 1 0^{- 4} = 0.02%$ .

Scheme B — biases linearly add hoti hain (sab ek hi direction mein hain): $total drift = N b = 10, 000 \times 0.01 = 100.$ Relative error $= 100/50, 000 = 2 \times 1 0^{- 3} = 0.2%$ .

Unbiased $10 \times$ se jeetta hai. Neeche diya figure dikhata hai kyun: random (zero-mean) errors partly cancel hote hain aur sirf $N$ ki tarah badhte hain (teal curve), jabki ek bias kabhi cancel nahi hota aur $N$ ki tarah badhta hai (orange curve).

Figure padhna: horizontal axis $N$ hai, accumulated operations ki sankhya; vertical axis total error magnitude hai. Orange line biased drift $N b$ hai — ek seedhi line jo relentlessly badhti hai. Teal curve unbiased spread $N σ$ hai — yeh bend karke flatten hoti hai kyunki har naya random error utna hi cancel karne ki probability rakhta hai jitna add karne ki. Dashed marker par ( $N = 10, 000$ ) gap hai $100$ vs $10$ : purely biased hone ki $10 \times$ penalty.

L3.2

Do $16 \times 16$ multiplier designs target image quality PSNR $\geq 35$ dB meet karte hain (yaad karo: PSNR hamara image-quality metric hai — higher dB = kam visible error):

Design X: lower 6 partial-product rows truncate karta hai, measured PSNR $= 38$ dB.
Design Y: lower 8 rows truncate karta hai, measured PSNR $= 33$ dB.

Array multiplier ke saved cells $\approx$ (rows dropped) $\times n$ . Kaunsa design ship karoge, aur kyun "zyada truncation" automatically better nahi hai?

Recall Solution L3.2

Design X ship karo. Design Y zyada truncate karta hai ( $8 \times 16 = 128$ cells drop vs $6 \times 16 = 96$ cells — zyada energy saved) lekin PSNR $= 33 < 35$ quality bound fail karta hai. Ek violated constraint ek rejected product hai; extra savings jo tum use hi nahi kar sakte worthless hain. Sahi rule: sabse aggressive design choose karo jo still bound satisfy kare — yahan woh X hai.

Level 4 — Synthesis

L4.1

Tum ek INT8 neural-network accelerator design kar rahe ho (dekho Neural Network Quantization). Energy budget hit karne ke liye do techniques combine karo: precision scaling (FP32 → INT8) aur voltage overscaling ( $V$ ko $1.0$ V se $0.85$ V tak drop karo). FP32, $1.0$ V baseline ke relative combined multiplier-energy factor estimate karo. ( $E \propto n^{2} V^{2}$ use karo; FP32 mantissa multiply ko $n = 24$ , INT8 ko $n = 8$ maano.)

Recall Solution L4.1

Do independent factors multiply karo.

Precision factor: $\frac{n _{new}^{2}}{n _{old}^{2}} = \frac{8 ^{2}}{2 4 ^{2}} = \frac{64}{576} = \frac{1}{9} \approx 0.1111.$

Voltage factor: $\frac{V _{new}^{2}}{V _{old}^{2}} = \frac{0.8 5 ^{2}}{1. 0 ^{2}} = 0.7225.$

Combined: $0.1111 \times 0.7225 \approx 0.0803.$ Toh multiplier energy FP32 baseline ka lagbhag 8% ho jaati hai — roughly ek $12.5 \times$ reduction. Yeh stacking (precision × voltage) energy-efficient design mein ek standard recipe hai; dekho Dark Silicon and Energy-Efficient Architectures.

L4.2

Tumhare accelerator ke weights DRAM mein hain. Tum refresh power bachane ke liye refresh rate low karte ho (approximate memory), lekin yeh occasionally bits flip karta hai. Ek partition scheme design karo: kaunsa data low-refresh (lossy) region mein jaata hai aur kaunsa reliable region mein rehta hai? Criticality principle se justify karo.

Recall Solution L4.2

Reliable region (normal refresh): exponents / scale factors, loop counters, pointers, critical weights ke top few mantissa bits, aur koi bhi ECC-protected control data. Inhe flip karne se magnitude blow-ups ya crashes hote hain.
Lossy region (low refresh): large weight/activation tensors ke low-order mantissa bits, aur cached intermediate feature maps. Ek flipped LSB ek weight ko thodi si fraction se nudge karta hai — network ki statistical aggregation absorb kar leti hai.
Justification: approximation criticality follow karni chahiye. Jis bits ka flip answer ki magnitude change karta hai woh exact rehti hain; jis bits ka flip sirf last decimal change karta hai woh lossy jaati hain. Yeh parent note ke rule ko mirror karta hai "kabhi exponents / control flow approximate mat karo."

Level 5 — Mastery

L5.1

Ek video decoder PSNR $\geq 40$ dB satisfy karna chahiye (higher dB = better picture; $\geq 40$ matlab "looks flawless"). Ek bit-width sweep deta hai:

$n$	PSNR (dB)	relative multiplier energy $\propto n^{2}$
12	52	$1 2^{2} = 144$
10	46	$1 0^{2} = 100$
8	41	$8^{2} = 64$
6	33	$6^{2} = 36$

Constraint ke subject energy minimise karne ke liye $n$ choose karo, phir $n = 12$ design ke saath energy saving batao aur "quality cliff" explain karo.

Recall Solution L5.1

Feasible choices (PSNR $\geq 40$ ): $n = 12$ (52), $n = 10$ (46), $n = 8$ (41). $n = 6$ deta hai $33 < 40$ → infeasible. Feasible mein se, energy $\propto n^{2}$ minimize karo: sabse chhota hai $n = 8$ (energy $64$ ). $n = 12$ se saving: $1 - \frac{64}{144} = 1 - 0.4 \overline{4} = 55.6%$ energy saved.

Quality cliff: $n = 8$ ( $41$ ) se $n = 6$ ( $33$ ) tak PSNR sirf $2$ fewer bits ke liye $8$ dB drop karta hai — ek sudden collapse. Neeche diya figure PSNR ko $n$ ke against plot karta hai: curve high $n$ par gentle hai lekin $n = 8$ ke baad $40$ dB line ke neeche plunge karta hai. Woh knee quality cliff hai; $n = 8$ bilkul iske edge par baitha hai — sabse chhota bit-width jo abhi bhi bound ke upar hai, yaani woh 80/20 sweet spot jo parent note describe karta hai.

L5.2

Tumhara final design ek feedback / iterative filter run karta hai (har output agla input ban jaata hai). Per-operation relative error ek tiny $0.1%$ hai. Ek colleague kehta hai " $0.1%$ negligible hai, ship karo." Woh kis condition mein galat hai, aur tumhe kya check karna chahiye?

Pehle, loop gain $g$ kya hai? Ek feedback loop ko ek block diagram ki tarah picture karo (neeche diya figure): ek input enter hota hai, process hota hai, aur output back feed hota hai aur agle step par re-process hota hai. Loop gain $g$ woh factor hai jis se us loop ke ek trip mein ek signal (aur uske saath koi bhi error) multiply hoti hai. Agar $g = 0.9$ , toh har lap error ko $90%$ tak shrink karta hai; agar $g = 1.1$ , toh har lap use $110%$ tak grow karta hai.

Recall Solution L5.2

Woh galat hai jab loop mein error path par gain $g > 1$ ho. Ek recurrence mein, step $t$ par error $e$ , step $t + 1$ par $\approx g \cdot e$ ban jaati hai; $k$ steps ke baad yeh $g^{k} e$ ho jaati hai. Agar $g > 1$ toh yeh exponentially grow karti hai, isliye ek $0.1%$ per-step error kuch dozen iterations mein output ko dominate kar sakti hai. Kya check karna hai: per-op error nahi, stability check karo. Verify karo ki loop gain $∣ g ∣ < 1$ hai (errors decay karte hain) ya system otherwise error-contracting hai. Per-operation smallness zaruri hai lekin feedback systems mein sufficient nahi — exactly parent note ki fourth mistake.

Recall Poori ladder ki one-line summary

Recognition (technique aur uski layer ka naam lo) → Application ( $n^{2} V^{2}$ mein plug in karo) → Analysis (bias vs unbiased, constraint-first) → Synthesis (techniques aur unki errors stack karo) → Mastery (quality cliff dhundho aur feedback stability check karo).