Processing-in-memory (PIM): Exercises — Hardware deep dive

Before we start, here is the tiny toolbox every problem draws from. Keep it in view.

Formula The six numbers you will reuse all page

$C$ = number of arithmetic operations a job does (a count, unitless).
$N$ = number of bytes moved from memory (a count of bytes).
Arithmetic intensity $I = \frac{C}{N}$ — "ops per byte." Small $I$ ⇒ the job spends its life waiting on memory (bandwidth-bound); large $I$ ⇒ it spends its life computing (compute-bound).
$B$ = external bus bandwidth (bytes/second the CPU can pull over the wire).
$B_{in t} = k \cdot B_{bank}$ = internal bandwidth: $k$ memory banks, each delivering $B_{bank}$ , all working at once.
Near-memory speedup estimate: $Speedup \approx \frac{B _{in t}}{B}$ .

Symbol warning: the italic $I$ always means arithmetic intensity (ops per byte). Later, in the crossbar problem, a boldface $I$ (with components $I_{i}$ ) will mean an electric current vector — a completely different quantity. We flag it again where it appears so the two never blur.

The figure above is our map: the roofline. The flat part on the left is bandwidth-bound territory (PIM's home turf); the slanted part on the right is compute-bound (caches and fast ALUs win). Arithmetic intensity $I$ places every workload left-to-right.

L1 — Recognition

Exercise 1.1

A job has $C = 2 \times 1 0^{6}$ operations and moves $N = 8 \times 1 0^{6}$ bytes. Compute its arithmetic intensity $I$ and state, in one word, whether it is bandwidth-bound or compute-bound.

Recall Solution 1.1

WHAT we do: apply the definition $I = C / N$ . $I = \frac{2 \times 1 0 ^{6}}{8 \times 1 0 ^{6}} = 0.25 ops/byte$ WHY it answers the question: $I$ is "how much math per byte fetched." A quarter-op per byte means we fetch four bytes for every single operation — the wire does almost all the work. Verdict: very low $I$ ⇒ bandwidth-bound ⇒ a good PIM candidate.

Exercise 1.2

Two flavors of PIM were defined. Which flavor uses the analog physics of the array itself (e.g., a memristor crossbar), and which one puts ordinary digital logic physically near the memory?

Recall Solution 1.2

Processing-using-memory (PUM): computes using the memory's own physics — the crossbar where Ohm's + Kirchhoff's laws do a matrix–vector multiply. See Memristor / ReRAM Crossbars.
Processing-near-memory (PNM): ordinary ALUs/cores placed next to memory, e.g. on the logic die of a 3D-stacked HBM stack. Mnemonic from the parent: Near = Next to; Using = the memory's own physics.

Exercise 1.3

True or false: "PIM's main win is a faster ALU." Justify in one sentence.

Recall Solution 1.3

False. PIM's win is reduced data movement, not faster arithmetic — it attacks the Memory Wall, the cost of dragging bytes across the bus. (This is the trap steel-manned just below.)

L2 — Application

Exercise 2.1

A vector operation a[i] = 2*b[i] + c[i] runs over $M = 5 \times 1 0^{6}$ elements of 4-byte floats. Each element needs a multiply and an add. Compute $C$ , $N$ , and $I$ .

Recall Solution 2.1

WHAT — count the ops $C$ : one multiply + one add per element ⇒ $2$ ops each. $C = 2 M = 2 \times 5 \times 1 0^{6} = 1 0^{7} ops$ WHY: the operation 2*b[i] + c[i] literally spells out one multiplication and one addition, and we perform it once for each of the $M$ elements — so the op count is simply $2$ per element times $M$ elements. WHAT — count the bytes $N$ : read b, read c, write a ⇒ 3 accesses × 4 bytes each. $N = 3 \times 4 \times M = 12 \times 5 \times 1 0^{6} = 6 \times 1 0^{7} bytes$ WHY: every memory touch crosses the bus and must be counted — two reads (b, c) plus one write (a) per element, each a 4-byte float. Forgetting the write-back is the classic slip (see the trap below). WHAT — intensity: $I = \frac{C}{N} = \frac{1 0 ^{7}}{6 \times 1 0 ^{7}} \approx 0.167 ops/byte$ WHY it matters: $I \approx 0.167$ is tiny — we move six bytes for every op. On the roofline (figure s01) this lands far left in the flat, bandwidth-bound zone ⇒ good PIM candidate.

Exercise 2.2

An HBM stack has $k = 8$ banks, each with internal bandwidth $B_{bank} = 10$ GB/s. The external bus is $B = 40$ GB/s. Estimate the near-memory speedup.

Recall Solution 2.2

WHAT — internal bandwidth: $B_{in t} = k \cdot B_{bank} = 8 \times 10 = 80 GB/s$ WHY: each of the $k = 8$ banks reads and computes on its own data simultaneously; because they run in parallel, their bandwidths add. This internal parallelism is exactly the resource the external bus could never expose. WHAT — speedup (bandwidth-bound approximation): $Speedup \approx \frac{B _{in t}}{B} = \frac{80}{40} = 2.0 \times$ WHY this ratio: for a bandwidth-bound job the runtime is set by how fast bytes flow. PIM replaces the $B = 40$ GB/s wire with $B_{in t} = 80$ GB/s of internal flow, so time shrinks by the bandwidth ratio — here $2 \times$ . (When compute time is not negligible this over-estimates; the full timing that exposes the gap is Exercise 5.2.)

Exercise 2.3

Rough energy fact: moving operands costs $E_{m o v e} \approx 200 E_{o p}$ , where $E_{o p}$ is the energy of one op. For a job with $I = 0.1$ ops/byte, roughly what fraction of energy is spent moving data vs. computing? (Assume one "move event" per byte, one $E_{o p}$ per op.)

Recall Solution 2.3

WHAT we build: per byte we do $I = 0.1$ ops, so per byte:

compute energy $= I \cdot E_{o p} = 0.1 E_{o p}$
move energy $= 1 \cdot E_{m o v e} = 200 E_{o p}$

WHY split per byte: normalizing "per byte moved" lets us compare the two energies on the same footing — one move event (cost $200 E_{o p}$ ) against the fraction of an op that byte earns ( $0.1 E_{o p}$ ). Fraction moving: $\frac{E _{m o v e}}{E _{m o v e} + E _{co m p u t e}} = \frac{200}{200 + 0.1} = \frac{200}{200.1} \approx 0.9995 = 99.95%$ Interpretation: essentially all energy is spent moving data. This is why PIM exists — cut the movement and you cut almost the whole energy bill.

L3 — Analysis

Exercise 3.1

A dense matrix multiply of size $n = 500$ has $C = 2 n^{3}$ ops and moves $N = 3 n^{2} \times 4$ bytes. Compute $I$ and decide: is PIM a strong win here? Contrast with the vector add from Exercise 2.1.

Recall Solution 3.1

Ops: $C = 2 n^{3} = 2 \times 50 0^{3} = 2 \times 1.25 \times 1 0^{8} = 2.5 \times 1 0^{8}$ . Bytes: $N = 3 n^{2} \times 4 = 12 n^{2} = 12 \times 250000 = 3 \times 1 0^{6}$ . Intensity: $I = \frac{2.5 \times 1 0 ^{8}}{3 \times 1 0 ^{6}} \approx 83.3 ops/byte$ Analysis: $I \approx 83$ is huge compared to the vector add's $0.167$ . Matrix multiply reuses each loaded value $O (n)$ times, so it is compute-bound — caches and fast ALUs already keep it fed. PIM's bandwidth win barely applies. See Roofline Model.

Exercise 3.2

A workload is 70% bandwidth-bound (call this fraction $p = 0.70$ ) and PIM makes that part $s = 4 \times$ faster. The remaining 30% is untouched. Use Amdahl's Law to compute the overall speedup.

Recall Solution 3.2

Amdahl's Law: if a fraction $p$ of the runtime is sped up by $s$ , and the rest ( $1 - p$ ) is unchanged, overall speedup is $Speedup = \frac{1}{( 1 - p ) + \frac{p}{s}}$ WHY this tool: PIM only accelerates the movement part of the job; the rest is a serial anchor. Amdahl is exactly "what happens when you speed up only a slice." 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$ Even a 4× local win yields only ~2.1× overall — the untouched 30% caps you.

Exercise 3.3

You measure that PIM gives near the maximum possible speedup even as $s \to \infty$ for the job in 3.2. What is that ceiling, and what does it prove?

Recall Solution 3.3

Let $s \to \infty$ in Amdahl: the term $p / s \to 0$ , leaving $Speedup_{m a x} = \frac{1}{1 - p} = \frac{1}{0.30} \approx 3.33 \times$ Proof it delivers: no matter how good PIM gets, the serial 30% caps you at 3.33×. This is why measuring the bandwidth-bound fraction $p$ matters more than tuning $s$ — the ceiling lives in $p$ .

L4 — Synthesis

Exercise 4.1

A memristor crossbar has a matrix $G$ of size $n \times n$ with $n = 4$ . Input voltages are $V = (1, 0, 2, 1)^{⊤}$ volts. Row $i$ produces current $I_{i} = \sum_{j} G_{ij} V_{j}$ (Ohm's law per cell, Kirchhoff's sum per row). Given $G = 1020031020010104 (siemens)$ compute the output current vector $I$ . Then state how many analog steps this took vs. a sequential CPU.

Recall Solution 4.1

Symbol note: here $I$ (boldface, components $I_{i}$ ) is an electric current vector — not the arithmetic intensity $I$ of the earlier problems. Same letter, different world; the boldface and the "amps" units keep them apart. WHY the crossbar does this in one shot: each crosspoint obeys Ohm's law $I_{ij} = G_{ij} V_{j}$ ; currents on a shared row wire add (Kirchhoff), giving $I_{i} = \sum_{j} G_{ij} V_{j}$ — a dot product per row, all rows in parallel. Trace this on figure s02 below: the input voltages $V_{j}$ (lavender arrows) enter down the columns, each crosspoint conductance (coral dots) scales its column's voltage into a current, and the currents merge rightward along each mint row wire into the output $I_{i}$ (coral arrows). Row by row ( $I = G 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$

$I = (5, 1, 2, 6)^{⊤} amps (in device units)$ Step count: the crossbar does this in one analog step ( $O (1)$ ). A CPU needs $n^{2} = 16$ multiply-accumulates ( $O (n^{2})$ ). That $O (n^{2}) \to O (1)$ collapse is why PIM loves Neural Network Accelerators.

Read this figure alongside Solution 4.1: it is the physical picture behind the numbers $I = (5, 1, 2, 6)$ . The conductance printed inside each coral dot is the corresponding $G_{ij}$ from the matrix; multiply it by its column's voltage and sum along the row to reproduce each $I_{i}$ by hand.

Exercise 4.2

Combine two levels. A neural-net layer is 90% matrix–vector multiply by runtime ( $p = 0.90$ ). A crossbar does that part effectively $s = 50 \times$ faster. (a) Overall speedup by Amdahl? (b) But crossbar output is approximate (device drift, ADC noise). What class of workload makes this acceptable, and what would make it unacceptable?

Recall Solution 4.2

(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) Acceptable for error-tolerant workloads — neural network inference tolerates small numeric noise (training already added robustness). Unacceptable for exact workloads like IEEE-precise finance or cryptography, where a drifted conductance corrupts the result. PUM trades exactness for speed.

L5 — Mastery

Exercise 5.1 (Design & defend)

You are handed three workloads. For each, decide PUM crossbar, PNM (near-memory ALUs), or plain CPU/GPU, and justify with the numbers.

W1: streaming vector add, $I = 0.08$ ops/byte, must be bit-exact.
W2: neural-net inference, dominated by $1000 \times 1000$ matrix–vector multiplies, tolerates ~1% error.
W3: dense scientific matrix multiply, $I \approx 167$ ops/byte, must be IEEE-exact.

Recall Solution 5.1

W1 → PNM. Very low $I$ ⇒ bandwidth-bound ⇒ PIM helps. But it must be exact, so we cannot use analog PUM (approximate). Digital near-memory ALUs give the bandwidth win and exactness. W2 → PUM crossbar. Matrix–vector multiply is the crossbar's native $O (1)$ operation; 1% error tolerance suits the analog imprecision. Ideal PUM case. W3 → plain CPU/GPU. $I \approx 167$ ⇒ compute-bound, so the bytes are already reused heavily inside the caches and PIM's bandwidth win barely helps. On top of that the job must be IEEE-exact, which rules out analog PUM entirely. Keep it on the GPU, where fast ALUs fed by cache are exactly the right tool. See Roofline Model.

Exercise 5.2 (Full pipeline estimate)

A job moves $N = 9 \times 1 0^{9}$ bytes and does $C = 4.5 \times 1 0^{8}$ ops. External bus $B = 30$ GB/s $= 30 \times 1 0^{9}$ B/s. Compute rate $R = 1 0^{9}$ ops/s. A PNM design has $k = 12$ banks, $B_{bank} = 12$ GB/s, and executes compute at the same rate $R$ . (a) Baseline time $T_{v N} = N / B + C / R$ . (b) PIM time $T_{P I M} = N / B_{in t} + C / R$ . (c) Actual speedup $T_{v N} / T_{P I M}$ . Compare it to the naive $B_{in t} / B$ and explain the gap.

Recall Solution 5.2

Internal bandwidth: $B_{in t} = 12 \times 12 = 144$ GB/s $= 144 \times 1 0^{9}$ B/s. (a) Baseline: $T_{v N} = \frac{9 \times 1 0 ^{9}}{30 \times 1 0 ^{9}} + \frac{4.5 \times 1 0 ^{8}}{1 0 ^{9}} = 0.30 + 0.45 = 0.75 s$ (b) PIM: $T_{P I M} = \frac{9 \times 1 0 ^{9}}{144 \times 1 0 ^{9}} + \frac{4.5 \times 1 0 ^{8}}{1 0 ^{9}} = 0.0625 + 0.45 = 0.5125 s$ (c) Actual speedup: $\frac{T _{v N}}{T _{P I M}} = \frac{0.75}{0.5125} \approx 1.463 \times$ Naive estimate $B_{in t} / B = 144/30 = 4.8 \times$ . Gap explained: the naive ratio assumes the job is pure movement. Here the compute term $C / R = 0.45$ s is large and unchanged by PIM — it becomes the new bottleneck. This is exactly Amdahl's ceiling: PIM only shrank the $0.30$ s movement part, not the $0.45$ s compute part. Always compute the full $T$ , never trust $B_{in t} / B$ alone.

Wrap-up

Return to the parent PIM note · related: DRAM Organization (banks, rows), Roofline Model, Amdahl's Law.