Level 5 — MasteryAdvanced & Emerging Architectures

Advanced & Emerging Architectures

⏱ 2 minutes100 marksprintable — key stays hidden on paper

Chapter: 6.5 Advanced & Emerging Architectures Level: 5 — Mastery (cross-domain: math + physics + coding, build/prove) Time limit: 2 hours 30 minutes Total marks: 100

Instructions: Answer all three questions. Show derivations fully; state assumptions explicitly. Numerical answers must carry units and be justified. Partial credit follows the mark scheme.

Question 1 — Systolic Arrays, HBM Bandwidth & the Roofline (36 marks)

A domain-specific accelerator uses an $N \times N$ output-stationary systolic array of MAC (multiply-accumulate) processing elements running at clock frequency $f$ . It computes dense matrix multiplication $C = A \times B$ where $A$ is $M \times K$ and $B$ is $K \times N$ , all in bf16 (2 bytes/element). Weights and activations stream from an HBM3 stack.

(a) Derive the peak throughput of the array in FLOP/s. Take $N = 128$ , $f = 1.0\text{ GHz}$ , and count one MAC as 2 FLOP. Give the numeric peak. (6)

(b) The systolic array has fill (latency) overhead: for a single $N\times N$ tile the pipeline takes $2N-1$ cycles to fill before the first full column of results emerges, then produces results every cycle. For a full $M\times K$ by $K\times N$ multiply tiled into $N\times N$ blocks, derive the hardware utilization $\eta$ (useful MAC-cycles / total MAC-cycles) as a function of $M,K,N$ assuming $K$ is streamed through each tile (accumulation dimension). Evaluate for $M=K=1024$ , $N=128$ . (8)

(c) One HBM3 stack delivers $B_{\text{mem}} = 819\text{ GB/s}$ . Using the arithmetic-intensity roofline model, derive the arithmetic intensity $I^\ast$ (FLOP/byte) at the ridge point where the machine transitions from memory-bound to compute-bound. Use your part (a) peak. (7)

(d) For the multiply of part (b) ( $M=N=K=1024$ ... use $M=K=1024$ , $N=128$ tiling), compute the operational intensity of the whole GEMM assuming each of $A$ , $B$ read once from HBM and $C$ written once. State whether this workload is compute- or memory-bound on this machine, and give the achievable throughput. (9)

(e) Argue quantitatively why increasing $N$ improves operational intensity for square GEMM, and name one physical constraint from 2.5D/3D packaging that bounds how large $N$ (and on-die SRAM) can grow. (6)

Question 2 — Quantum Hardware, Coherence & Error Budget (32 marks)

A superconducting transmon quantum processor has single-qubit gate time $t_g = 20\text{ ns}$ and qubit relaxation time $T_1 = 100\ \mu\text{s}$ , dephasing time $T_2 = 80\ \mu\text{s}$ .

(a) The probability that a qubit in $|1\rangle$ has not decayed after time $t$ is $P(t)=e^{-t/T_1}$ . Derive the per-gate error contribution from $T_1$ relaxation for one gate, $\varepsilon_{T_1}\approx t_g/(2T_1)$ (state the small- $t$ approximation used and its justification). Compute $\varepsilon_{T_1}$ . (8)

(b) A circuit must run for depth $D$ gates on one qubit within the coherence-limited window. Define the "gate budget" as the number of gates before accumulated single-qubit error reaches $0.5$ (assuming errors add linearly for small $\varepsilon$ , using the combined $\varepsilon \approx t_g/T_2$ ). Derive and compute this budget $D_{\max}$ . (8)

(c) Surface-code quantum error correction requires physical error rate below threshold $p_{\text{th}}\approx 1\%$ and needs roughly $d^2$ physical qubits per logical qubit (distance $d$ ), with logical error suppressed as $p_L \approx A\,(p/p_{\text{th}})^{(d+1)/2}$ . Given physical error $p = 10^{-3}$ , $A = 0.1$ , find the smallest odd distance $d$ giving $p_L \le 10^{-12}$ , and the physical-qubit cost per logical qubit. (10)

(d) Contrast, in physical terms, why photonic interconnects (6.5.15/6.5.18) are attractive for linking quantum/cryogenic modules but why the qubits themselves are not simply "run faster" — connect to the coherence argument above. (6)

Question 3 — Build & Prove: Approximate MAC + Dataflow Energy (32 marks)

You will design and analyze an approximate fixed-point accelerator datapath and reason about its dataflow.

(a) Consider an approximate multiplier that truncates the lower $b$ bits of each $n$ -bit unsigned operand before multiplying (operands in $[0, 2^n)$ ). Derive the maximum relative error of the product $\hat{p}$ vs. exact $p = x\cdot y$ as a function of $b$ and $n$ (worst case, non-trivial operands). Bound it and evaluate for $n=8$ , $b=3$ . (9)

(b) Write pseudocode (or Python) for the approximate MAC accumulating $L$ products, and give the worst-case bound on accumulated absolute error over $L$ terms. State how error-averaging (statistical, uniform inputs) changes the expected error growth (scaling with $L$ ). (9)

(c) In a weight-stationary dataflow, energy per MAC is dominated by data movement: $E = E_{\text{mac}} + \sum_i n_i E_i$ where accesses at level $i$ (RF, SRAM, DRAM/HBM) have relative energy costs $E_{\text{RF}}:E_{\text{SRAM}}:E_{\text{DRAM}} = 1:6:200$ (per byte). For a convolution reusing each weight $R$ times, derive the amortized DRAM energy per MAC and show the reuse factor at which SRAM access dominates DRAM. Take $R$ ranging; find $R$ where $E_{\text{DRAM}}/R = E_{\text{SRAM}}$ . (8)

(d) Prove that approximate computing gives no benefit for a workload whose correctness constraint requires bit-exact reproducibility, and give one realistic domain-specific accelerator workload (from 6.5.6) where approximation is safe and why. (6)

End of paper.

Answer keyMark scheme & solutions

Question 1

(a) Peak = (number of MACs) × (MACs/cycle each) × $f$ × (FLOP/MAC).

$N^2 = 128^2 = 16384$ PEs, each 1 MAC/cycle. (2)
MAC-rate $= 16384 \times 1.0\times10^9 = 1.6384\times10^{13}$ MAC/s. (2)
Peak FLOP/s $= 2 \times 1.6384\times10^{13} = 3.2768\times10^{13}$ FLOP/s $\approx 32.8$ TFLOP/s. (2)

(b) Number of tiles: $M/N$ row-blocks × $N/N$ ... For GEMM $M\times K$ by $K\times N$ with $N=$ tile:

Number of output tiles $= (M/N)\times(N/N) = M/N$ tiles when output width = $N$ . Each tile streams $K$ elements of the accumulation dimension.
Per tile: fill $2N-1$ cycles, then $K$ useful cycles (streaming $K$ accumulations). Total cycles per tile $= (2N-1) + K$ . Useful cycles $= K$ .
Utilization $\eta = \dfrac{K}{K + 2N - 1}$ . (5)
Evaluate: $\eta = 1024/(1024 + 255) = 1024/1279 = 0.8006 \approx 80.1\%$ . (3)

(Fill overhead is amortized over the $K$ streamed cycles; larger $K$ → higher $\eta$ .)

(c) Ridge point: $I^\ast = \dfrac{\text{Peak FLOP/s}}{B_{\text{mem}}}$ . (3)

$I^\ast = \dfrac{3.2768\times10^{13}}{819\times10^{9}} = 40.0$ FLOP/byte. (4)

Below $I^\ast$ memory-bound; above, compute-bound.

(d) GEMM $M\times K \times N$ with $M=K=1024$ , $N=1024$ (square whole-GEMM operational intensity — tiling internal):

FLOP $= 2MKN = 2\cdot1024^3 = 2.147\times10^9$ FLOP. (2)
Bytes (bf16, 2 B): read $A$ ( $MK$ ) + read $B$ ( $KN$ ) + write $C$ ( $MN$ ) $= 2(MK+KN+MN) = 2\cdot3\cdot1024^2 = 6.29\times10^6$ B. (2)
$I = 2.147\times10^9 / 6.29\times10^6 = 341$ FLOP/byte. (2)
$341 \gg I^\ast=40$ → compute-bound. (1)
Achievable throughput ≈ peak × utilization $\approx 32.8 \times 0.80 = 26.2$ TFLOP/s (compute-bound, so memory not limiting). (2)

(e) For square GEMM, FLOP $\propto N^3$ (per $N^3$ block) while HBM traffic $\propto N^2$ , so $I \propto N$ — bigger tiles reuse each loaded element more, raising intensity linearly. (3) Physical constraints from packaging: on-die SRAM to hold an $N\times N$ tile grows as $N^2$ , and the interposer/TSV area, thermal density (power/area, cooling through stacked dies), and reticle/interposer size limit die area, capping $N$ and SRAM. (3)

Question 2

(a) $P(\text{decay}) = 1 - e^{-t_g/T_1}$ . Small- $t$ : $t_g/T_1 = 20\text{ns}/100\mu\text{s}=2\times10^{-4}\ll1$ , so $1-e^{-x}\approx x$ . (3) Error averaged over states (qubit equally in $|0\rangle,|1\rangle$ ; only $|1\rangle$ decays) gives factor $1/2$ : $\varepsilon_{T_1}\approx t_g/(2T_1)$ . (3)

$\varepsilon_{T_1} = 20\times10^{-9}/(2\times100\times10^{-6}) = 1.0\times10^{-4}$ . (2)

(b) Combined decoherence per gate $\varepsilon \approx t_g/T_2 = 20\times10^{-9}/80\times10^{-6} = 2.5\times10^{-4}$ . (3)

Linear accumulation: $D_{\max}\varepsilon = 0.5 \Rightarrow D_{\max} = 0.5/2.5\times10^{-4} = 2000$ gates. (5)

(c) Need $p_L = A(p/p_{\text{th}})^{(d+1)/2} \le 10^{-12}$ , with $p/p_{\text{th}} = 10^{-3}/10^{-2}=0.1$ , $A=0.1$ .

$0.1\cdot(0.1)^{(d+1)/2}\le10^{-12}$ → $(0.1)^{(d+1)/2}\le10^{-11}$ → $(d+1)/2 \ge 11$ → $d \ge 21$ . (6)
Smallest odd $d = 21$ . (2)
Physical qubits $\approx d^2 = 441$ per logical qubit. (2)

(d) Photonic links (6.5.15/6.5.18) move information between cryostats/modules at low loss and no resistive heat dissipation in the fiber, ideal for scaling out modules and cutting cryogenic heat load. (3) But qubit operation speed is bounded by coherence, not link bandwidth: gates faster than $t_g$ risk leakage/control-bandwidth errors, and coherence ( $T_1,T_2$ ) sets the fixed error-per-gate — "running faster" doesn't extend the coherence window, so optics help interconnect, not qubit fidelity. (3)

Question 3

(a) Truncating $b$ bits: $\hat{x} = x - (x \bmod 2^b)$ , similarly $\hat y$ . Max truncation loss per operand $\le 2^b - 1 < 2^b$ .

$\hat p = \hat x\hat y$ , $p=xy$ . Error $p-\hat p = x\hat y_{err} + \hat x_{err} y - ...$ ; worst-case relative error dominated by $\Delta \approx (2^b/x)+(2^b/y)$ terms. (3)
Worst relative error when operands are small but $\ge$ threshold; bound: for operands with MSB set ( $x,y \ge 2^{n-1}$ ), $\frac{|p-\hat p|}{p} \lesssim \frac{2^b}{x}+\frac{2^b}{y} \le 2\cdot\frac{2^b}{2^{n-1}} = 2^{b-n+2}$ . (3)
$n=8,b=3$ : $2^{3-8+2}=2^{-3}=0.125 = 12.5\%$ worst case (bounded operands). (3)

(b) Pseudocode:

def approx_mac(xs, ys, b):
    acc = 0
    for x, y in zip(xs, ys):
        xt = x & ~((1<<b)-1)   # truncate low b bits
        yt = y & ~((1<<b)-1)
        acc += xt * yt
    return acc

(3) Worst-case absolute error per product $\le p_{\max}\cdot\varepsilon_{rel}$ ; over $L$ terms adds linearly: $E_{abs}^{worst} \le L\cdot 2^{2n}\cdot 2^{b-n+2}=L\cdot 2^{n+b+2}$ (loose). Grows $\propto L$ . (3) For uniform random inputs, truncation errors are zero-mean-ish and partly independent → expected error grows as $\sqrt{L}$ (central-limit), not $L$ ; so statistical averaging keeps relative accumulation error $\propto 1/\sqrt{L}$ . (3)

(c) DRAM read once per weight, reused $R$ times → amortized DRAM energy per MAC $= E_{\text{DRAM}}/R = 200/R$ . (3) SRAM accessed each MAC: $E_{\text{SRAM}} = 6$ . (2) Crossover: $200/R = 6 \Rightarrow R = 33.3$ . So for $R \gtrsim 33$ reuses, DRAM is no longer dominant and SRAM access dominates. (3)

(d) If correctness demands bit-exact output, any approximation changes bits → violates constraint by definition, so accuracy-for-energy trade is unusable (must run exact path). (3) Safe example (6.5.6): a neural-network inference accelerator (e.g., image classifier) — outputs are argmax class labels robust to low-order-bit noise; quantization/approximate MACs shift logits negligibly and rarely flip the top-1 result, saving energy. (3)

[
 {"claim":"Q1a peak = 32.768 TFLOP/s","code":"N=128;f=1.0e9;peak=2*N*N*f;result=abs(peak-3.2768e13)<1e9"},
 {"claim":"Q1b utilization = 1024/1279","code":"K=1024;N=128;eta=K/(K+2*N-1);result=abs(eta-0.8006)<1e-3"},
 {"claim":"Q1c ridge intensity = 40 FLOP/byte","code":"peak=3.2768e13;B=819e9;I=peak/B;result=abs(I-40.0)<0.2"},
 {"claim":"Q1d GEMM intensity = 341","code":"M=K=Nn=1024;flop=2*M*K*Nn;byts=2*(M*K+K*Nn+M*Nn);I=flop/byts;result=abs(I-341.3)<1"},
 {"claim":"Q2b gate budget = 2000","code":"tg=20e-9;T2=80e-6;eps=tg/T2;D=0.5/eps;result=abs(D-2000)<1"},
 {"claim":"Q2c smallest odd distance = 21","code":"import math;p=1e-3;pth=1e-2;A=