Approximate computing techniques: Exercises — Hardware deep dive

Before we start, a 30-second symbol refresher so nobody meets a new symbol cold:

Definition The symbols we reuse everywhere

$n$ = the bit-width: how many binary digits (0/1) we use to store a number. More bits = more precision, bigger circuit.
$V$ = the supply voltage driving the transistors. Think of it as the "push" behind the electrons.
$P = α C V^{2} f$ = dynamic power (energy burned per second). $α$ = fraction of transistors switching, $C$ = capacitance (how much charge each switch moves), $f$ = clock frequency. See Dynamic Power P = alpha C V^2 f.
$E$ = error = (approximate answer) − (exact answer). Relative error = $∣ E ∣ / ∣ exact ∣$ , i.e. error as a fraction of the true size.
$μ$ = the mean (average) of a set of numbers: add them all up, divide by how many there are. If you sum $N$ numbers each averaging $μ$ , the sum is about $N μ$ .
$σ$ = the standard deviation: the typical size of the wobble around the mean. Small $σ$ = errors cluster tightly near zero; large $σ$ = they spread out. Its square $σ^{2}$ is the variance, which is what adds up when you combine independent errors.

For each technique, name which layer of the stack it lives in (circuit / arithmetic / software-loop / memory / voltage): (a) loop perforation, (b) truncated multiplier, (c) lowering DRAM refresh rate, (d) running below the safe voltage.

Recall Solution L1.1

(a) Software-loop — we skip loop iterations; no hardware change needed.
(b) Arithmetic circuit — we redesign the multiplier to drop low-order partial products.
(c) Memory — fewer refreshes let some DRAM cells decay → bit flips in stored data. See DRAM Refresh and Memory Reliability.
(d) Voltage — voltage overscaling (VOS); rare timing errors on the slowest paths.

L1.2

Which of these is safe to approximate, and which must stay exact? (a) the mantissa's least-significant bits of a pixel colour, (b) a loop-bound counter, (c) the exponent of an FP32 number, (d) a summed sensor reading.

Recall Solution L1.2

(a) Safe — LSBs of a pixel are perceptually invisible.
(b) Exact — a corrupted loop bound can loop forever or crash. Control flow is critical.
(c) Exact — the exponent sets the magnitude. Flip one bit and a number can jump by a factor of $2^{128}$ . See Precision and Number Formats (FP32, FP16, INT8).
(d) Safe — aggregation absorbs per-reading error.

Level 2 — Application

L2.1

An $8 \times 8$ array multiplier is replaced by a $4 \times 4$ one (precision halved from $n = 8$ to $n = 4$ ). Using $E_{mult} \propto n^{2} V^{2}$ at fixed $V$ , by what factor does multiplier energy drop?

First, why does multiplier energy grow as $n^{2}$ ? Look at the figure below. An $n \times n$ array multiplier multiplies two $n$ -bit numbers by laying out a grid of AND gates and full-adder cells: each of the $n$ bits of one operand is combined with each of the $n$ bits of the other, forming an $n \times n$ array of partial-product cells. That is literally an $n$ -by- $n$ square of hardware — $n$ rows $\times$ $n$ columns $= n^{2}$ cells. Since each cell burns roughly the same switching energy $\propto V^{2}$ , the whole multiplier burns $\approx n^{2} V^{2}$ . This is the geometric reason behind the law (see 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} .$ So energy drops to one quarter — a $4 \times$ saving. Why $n^{2}$ and not just $n$ ? The cell count is the area of an $n \times n$ square, so halving $n$ quarters the area (like halving a square's side quarters its area). This is exactly why halving bit-width is such a lever.

L2.2

Dynamic power is $P = α C V^{2} f$ . We overscale voltage from $V = 1.0 V$ down to $V = 0.8 V$ , keeping $α, C, f$ fixed. What fraction of the original power do we save?

Recall Solution L2.2

Power scales with $V^{2}$ , so $\frac{P _{new}}{P _{old}} = \frac{0. 8 ^{2}}{1. 0 ^{2}} = 0.64.$ Saving $= 1 - 0.64 = 0.36 = 36%$ . The other $64%$ is what we still pay.

L2.3

Multiply $A = 1.375$ and $B = 1.500$ . The exact product needs some fractional bits; we truncate to 3 fractional bits ( $2^{- 3} = 0.125$ resolution). Find the truncated value, the absolute error, and the relative error.

Recall Solution L2.3

Exact: $1.375 \times 1.500 = 2.0625$ .
Truncate to multiples of $0.125$ (drop the tail, round down): $2.0625 \to 2.000$ (since $2.0625 = 2.000 + 0.0625$ , and $0.0625 < 0.125$ so the 3rd fractional bit is not set).
Absolute error $= 2.0625 - 2.000 = 0.0625$ .
Relative error $= 0.0625/2.0625 \approx 0.0303 = 3.03%$ .

Level 3 — Analysis

L3.1

You sum $N = 10, 000$ numbers, each with mean $μ = 5$ (recall from the refresher: $μ$ is the average value of each summand, $σ$ is the typical size of the injected wobble). Two approximation schemes:

Scheme U (unbiased): each addition adds independent zero-mean error with standard deviation $σ = 0.1$ .
Scheme B (biased): each addition always loses a fixed $b = 0.01$ (systematic).

Estimate the relative error of the final sum under each. Which wins and why?

Recall Solution L3.1

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

Scheme U — errors add in quadrature (variances $σ^{2}$ sum): $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 add linearly (they all point the same way): $total drift = N b = 10, 000 \times 0.01 = 100.$ Relative error $= 100/50, 000 = 2 \times 1 0^{- 3} = 0.2%$ .

Unbiased wins by $10 \times$ . The figure below shows why: random (zero-mean) errors partly cancel and grow only like $N$ (teal curve), while a bias never cancels and grows like $N$ (orange curve).

Reading the figure: the horizontal axis is $N$ , the number of accumulated operations; the vertical axis is the total error magnitude. The orange line is the biased drift $N b$ — a straight line climbing relentlessly. The teal curve is the unbiased spread $N σ$ — it bends over and flattens because each new random error is as likely to cancel as to add. At the dashed marker ( $N = 10, 000$ ) the gap is $100$ vs $10$ : a $10 \times$ penalty purely for being biased.

L3.2

Two $16 \times 16$ multiplier designs meet a target image quality PSNR $\geq 35$ dB (recall: PSNR is our image-quality metric — higher dB = less visible error):

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

An array multiplier's saved cells $\approx$ (rows dropped) $\times n$ . Which design do you ship, and why is "more truncation" not automatically better?

Recall Solution L3.2

Ship Design X. Design Y truncates more (drops $8 \times 16 = 128$ cells vs $6 \times 16 = 96$ cells — more energy saved) but PSNR $= 33 < 35$ fails the quality bound. A constraint violated is a product rejected; extra savings you can't use are worthless. The correct rule: pick the most aggressive design that still satisfies the bound — here that is X.

Level 4 — Synthesis

L4.1

You are designing an INT8 neural-network accelerator (see Neural Network Quantization). Combine two techniques to hit an energy budget: precision scaling (FP32 → INT8) and voltage overscaling (drop $V$ from $1.0$ V to $0.85$ V). Estimate the combined multiplier-energy factor relative to the FP32, $1.0$ V baseline. (Use $E \propto n^{2} V^{2}$ ; treat FP32 mantissa multiply as $n = 24$ , INT8 as $n = 8$ .)

Recall Solution L4.1

Multiply the two independent factors.

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.$ So multiplier energy falls to about 8% of the FP32 baseline — roughly a $12.5 \times$ reduction. This stacking (precision × voltage) is a standard recipe in energy-efficient design; see Dark Silicon and Energy-Efficient Architectures.

L4.2

Your accelerator's weights sit in DRAM. You lower the refresh rate (approximate memory) to save refresh power, but this occasionally flips bits. Design a partition scheme: which data goes in the low-refresh (lossy) region and which stays in the reliable region? Justify with the criticality principle.

Recall Solution L4.2

Reliable region (normal refresh): exponents / scale factors, loop counters, pointers, the top few mantissa bits of critical weights, and any ECC-protected control data. Flipping these causes magnitude blow-ups or crashes.
Lossy region (low refresh): the low-order mantissa bits of large weight/activation tensors, and cached intermediate feature maps. A flipped LSB nudges a weight by a tiny fraction — absorbed by the network's statistical aggregation.
Justification: approximation must follow criticality. Bits whose flip changes the answer's magnitude stay exact; bits whose flip changes only the last decimal go lossy. This mirrors the parent note's rule "never approximate exponents / control flow."

Level 5 — Mastery

L5.1

A video decoder must satisfy PSNR $\geq 40$ dB (higher dB = better picture; $\geq 40$ is "looks flawless"). A bit-width sweep gives:

$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$

Choose $n$ to minimise energy subject to the constraint, then state the energy saving vs the $n = 12$ design and explain the "quality cliff."

Recall Solution L5.1

Feasible choices (PSNR $\geq 40$ ): $n = 12$ (52), $n = 10$ (46), $n = 8$ (41). $n = 6$ gives $33 < 40$ → infeasible. Among feasible, minimise energy $\propto n^{2}$ : smallest is $n = 8$ (energy $64$ ). Saving vs $n = 12$ : $1 - \frac{64}{144} = 1 - 0.4 \overline{4} = 55.6%$ energy saved.

Quality cliff: from $n = 8$ ( $41$ ) to $n = 6$ ( $33$ ) PSNR drops $8$ dB for just $2$ fewer bits — a sudden collapse. The figure below plots PSNR against $n$ : the curve is gentle at high $n$ but plunges below the $40$ dB line right after $n = 8$ . That knee is the quality cliff; $n = 8$ sits right at its edge — the smallest bit-width still above the bound, i.e. the 80/20 sweet spot the parent note describes.

L5.2

Your final design runs a feedback / iterative filter (each output feeds the next input). Per-operation relative error is a tiny $0.1%$ . A colleague says " $0.1%$ is negligible, ship it." Under what condition is she wrong, and what must you check?

First, what is the loop gain $g$ ? Picture a feedback loop as a block diagram (figure below): an input enters, gets processed, and the output is fed back and re-processed on the next step. The loop gain $g$ is the factor by which one trip around that loop multiplies a signal (and any error riding on it). If $g = 0.9$ , each lap shrinks the error to $90%$ ; if $g = 1.1$ , each lap grows it to $110%$ .

Recall Solution L5.2

She is wrong when the loop has a gain $g > 1$ on the error path. In a recurrence, an error $e$ at step $t$ becomes $\approx g \cdot e$ at step $t + 1$ ; after $k$ steps it is $g^{k} e$ . If $g > 1$ this grows exponentially, so a $0.1%$ per-step error can dominate the output within a few dozen iterations. What to check: stability, not per-op error. Verify the loop gain $∣ g ∣ < 1$ (errors decay) or that the system is otherwise error-contracting. Per-operation smallness is necessary but not sufficient in feedback systems — exactly the fourth mistake in the parent note.

Recall One-line summary of the whole ladder

Recognition (name the technique & its layer) → Application (plug into $n^{2} V^{2}$ ) → Analysis (bias vs unbiased, constraint-first) → Synthesis (stack techniques and their errors) → Mastery (find the quality cliff & check feedback stability).

Exercises — Approximate computing techniques

Level 1 — Recognition

L1.1