Approximate computing techniques

WHY does this even work?

Three structural reasons resilience exists:

Perceptual limits — humans have finite resolution (audio, video, images).
Noisy/redundant input — sensor data is already noisy; extra tiny error is lost in the noise floor.
Statistical aggregation / self-healing — sums, averages, and iterative algorithms (gradient descent, PageRank) absorb per-operation error.

Formula Why aggregation hides error (derived from scratch)

Suppose we sum $N$ numbers, and each addition injects an independent error $\varepsilon_i$ with mean $0$ and standard deviation $\sigma$ . The total error is $E = \sum_{i=1}^{N}\varepsilon_i.$ Because the errors are independent with mean zero:

\operatorname{Var}(E)=\sum \operatorname{Var}(\varepsilon_i)=N\sigma^2.$$ So the **typical error grows as** $\sqrt{N}\,\sigma$, while the **signal (the sum) grows as** $N$. The *relative* error therefore shrinks: $$\frac{\text{error}}{\text{signal}}\sim\frac{\sqrt N\,\sigma}{N\mu}=\frac{\sigma}{\mu\sqrt N}\xrightarrow{N\to\infty}0.$$ **Why this matters:** the larger the aggregation, the more approximation you can afford. This is the mathematical license for approximate hardware.

HOW: the toolbox of techniques

Approximation happens at every layer of the stack.

Figure — Approximate computing techniques

Deep dive 1 — Why precision scaling saves so much

Deep dive 2 — Why voltage overscaling is a $V^2$ jackpot (and a $V$ risk)

Dynamic power is $P = \alpha C V^2 f$ . Drop $V$ by 20% ⇒ power drops by $1-0.8^2=36\%$ . But circuit delay $\propto V/(V-V_{th})^\beta$ increases as $V$ falls, so at fixed clock some paths miss their deadline → timing errors. VOS says: tolerate those rare errors on the least-significant bits, keep the huge power win.

Worked examples

Worked example Example 1 — Truncated (fixed-point) multiplier

Multiply $A=1.0110_2$ and $B=1.1010_2$ (4 fractional bits each). Exact product needs 8 fractional bits. Suppose we truncate the lower 4 bits of the result.

Step: exact $A=1.375$ , $B=1.625$ , product $=2.234375$ . Why? Establish ground truth.
Step: keep 4 fractional bits → $2.0011_2 = 2.1875$ . Why this step? Truncation just drops the tail; hardware needs no logic for those bits → smaller array.
Error $= 2.234375 - 2.1875 = 0.046875$ , relative $\approx 2.1\%$ .
Trade-off: we removed $\approx$ a $4\times4$ chunk of partial-product logic for a 2% error.

Common mistakes (steel-manned)

Recall Feynman: explain it to a 12-year-old

Imagine you're drawing a picture with crayons. If you're a tiny bit outside the lines, the picture still looks great — but you finished way faster and used less crayon. Computers can do the same trick: for stuff like photos, music, or guessing "is this a dog?", they can do the math a little sloppily on purpose. Sloppy math is faster and uses less battery, and you can't even tell the answer is slightly off. The clever part is choosing where to be sloppy — never on the important stuff (like the page number), only on the parts nobody notices.

Active-recall flashcards

#flashcards/hardware

What is the core trade-off in approximate computing?

A small, bounded loss of output quality in exchange for large gains in energy, speed, or area.

Why can summing/averaging tolerate approximation?

For

N

independent zero-mean errors, total error grows as

\sqrt N\sigma

while the sum grows as

N

, so relative error

\to 0

Why does halving the bit-width cut multiplier energy ~4×?

n\times n

array multiplier uses

\approx n^2

full-adder cells, and energy

\propto n^2V^2

;

n\to n/2

gives

(1/2)^2 = 1/4

What is voltage overscaling and why is it powerful?

Running below safe voltage; power

\propto V^2

so big savings, at the cost of rare timing errors on non-critical bits.

What is loop perforation?

Skipping some loop iterations (e.g. every other pixel) and reusing/interpolating, exploiting redundancy for speedup.

Which parts of a program must you NEVER approximate?

Control flow, loop bounds, pointers/addresses, and FP exponents — errors there cause crashes or catastrophic magnitude errors.

When does the "error averages out" assumption FAIL?

When errors are biased (non-zero mean); systematic error then grows as

N

, not

\sqrt N

Name a quality metric used to bound approximation error.

PSNR (images), classification accuracy (ML), or relative/absolute error.

Why is approximation not the same as a bug?

It is engineered and bounded — you choose where error goes and guarantee a quality metric; a bug is uncontrolled.

What is load-value/memoization approximation?

Reusing a previous or similar computed value instead of recomputing, when inputs are close enough.

Connections

Precision and Number Formats (FP32, FP16, INT8)
Dynamic Power P = alpha C V^2 f
DRAM Refresh and Memory Reliability
Neural Network Quantization
Ripple-Carry vs Array Multipliers
Error-Correcting Codes (the opposite philosophy — spend energy to remove error)
Dark Silicon and Energy-Efficient Architectures

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, idea simple hai: har computation ko perfect karne ki zaroorat nahi hoti. Jaise aapki aankh 100% aur 98% quality wali photo me farak nahi bata sakti, waise hi bahut se applications (images, audio, machine learning) thodi si galti ko tolerate kar lete hain. Approximate computing isi baat ka fayda uthata hai — thodi si controlled accuracy chhod do, aur badle me bahut saara energy, speed aur chip area bacha lo. Key word hai controlled: galti sirf wahan daalte hain jahan koi farak nahi padta (jaise LSB bits ya pixel values), aur uski limit fix karte hain.

Yeh kaam kyun karta hai? Kyunki jab aap bahut saari values ko sum ya average karte ho, toh independent random errors aapas me cancel ho jaate hain — total error $\sqrt{N}$ ke rate se badhta hai jabki sum $N$ ke rate se, toh relative error chhota hota jaata hai. Isi wajah se neural network INT8 me bhi cat ko cat hi bolta hai.

Techniques yaad rakhne ke liye "PA-LOVE-M" socho: Precision scaling (kam bits, jaise FP32→INT8 — multiplier energy $n^2$ ke saath chalti hai, toh bits half karo toh energy 4 guna kam!), Approximate circuits, Loop perforation (kuch iterations skip), Overvoltage scaling (voltage kam, power $V^2$ se girta hai), Value memoization, aur approximate Memory.

Sabse important baat — steel-man ki galtiyaan: kabhi bhi control flow, loop bounds, pointers ya floating-point exponent ko approximate mat karna, warna program crash ya bilkul galat answer. Aur "error toh average ho jaayega" tabhi sach hai jab error unbiased ho; agar hamesha neeche round karoge (biased) toh error $N$ ke saath badhega. Bas isliye smart engineering matters — galti daalo, par soch-samajh ke.

WHY does this even work?

HOW: the toolbox of techniques

Deep dive 1 — Why precision scaling saves so much

Deep dive 2 — Why voltage overscaling is a $V^2$ jackpot (and a $V$ risk)

Worked examples

Common mistakes (steel-manned)

Active-recall flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced & Emerging Architectures

Connections