COE 592Lecture 4.2Reference

Reference sheet

Pruning ratios, fine-tuning and sparse hardware compressed onto one page: the definitions, formulas and numbers to have in your head before a quiz or exam.

The pruning problem

Among all weight tensors with at most N nonzeros, pick the one with the lowest loss. Part 01: Where we are

\arg\min_{W_P} L(x;\, W_P) \quad \text{subject to} \quad \|W_P\|_0 \le N

Loss minimization under a nonzero budget

Every symbol

L: The training loss, for example cross-entropy
x: The input data the loss is evaluated on
W: The original dense trained weights
W_P: The pruned weights, same shape as W, some entries forced to exactly zero
||W_P||_0: The number of nonzeros in W_P. Not a norm, no usable gradient
N: The nonzero budget. With M weights, sparsity is 1 - N / M

Magnitude pruning on a 2 x 2 matrix at 50 percent

W: [[3, -2], [1, -5]]
|W|: [[3, 2], [1, 5]]
Keep top 2: importances 5, 3, so -5 and 3 survive
W_P: [[3, 0], [0, -5]], ||W_P||_0 = 2, sparsity 50%

Question	Asks	Answered in
Formulation	What is pruning and how is it written?	04-1, and part 01 here
Granularity	In what pattern are weights removed?	04-1
Criterion	By what score are weights ranked?	04-1
Ratio	What sparsity does each layer get?	Parts 02 to 05
Fine-tune	How is the lost accuracy recovered?	Part 06

Five questions and where each is answered

Level	What is removed	Flexibility	Hardware friendliness
Fine-grained	Single weights anywhere	Highest	Indices plus sparse kernels (EIE)
Pattern-based (2:4)	Two of every four along a row	High	2-bit tags, Ampere tensor cores
Vector or kernel	A row segment or a whole k x k kernel	Medium	Fewer indices per block
Channel	A whole filter and its output channel	Lowest	Dense kernels, layer simply narrows

Granularity ladder

Removing a neuron deletes one row of W (out x in); removing a conv channel deletes one whole filter (C_in x k x k). Both are coarse-grained weight pruning; the criterion is a separate choice from the granularity.

Sensitivity analysis

Uniform shrinking gives every layer the same factor and loses 2.1 points on MobileNet at the same latency (68.4% at 72.3 ms against AMC 70.5% at 68.3 ms). Layers differ in sensitivity, so each needs its own ratio. Part 02: Why per-layer ratios

\Delta \mathrm{Acc}_r^{\,i} = \mathrm{Acc}_{\text{dense}} - \mathrm{Acc}_r^{\,i}

Accuracy lost when only layer i is pruned at ratio r

The sweep

1. Pick a layer L_i: Every other layer stays exactly as trained
2. Prune only L_i: Magnitude, fine-grained, at r in {0, 0.1, ..., 0.9}
3. Record Delta Acc: Delta Acc_r^i = Acc_dense - Acc_r^i, one evaluation per r, no training
4. Restore and repeat: Copy the saved dense tensor back, move to the next layer
Cost: Layers x ratios evaluations: 11 x 10 = 110 for VGG-11, about 1.1 million forward passes on the 10,000 CIFAR-10 test images

Layer	r = 0.5	0.6	0.7	0.8	0.9	Verdict
L0 (first conv)	92	88	83	71	32	Most sensitive
L1	93	93	93	92	85	Most redundant
L2	93	93	90	90	79	Redundant
L3	93	93	90	86	51	Moderate
L4	93	93	90	78	38	Sensitive past 70
L5	93	92	92	90	82	Redundant

VGG-11 on CIFAR-10, accuracy (%) with one layer pruned at a time (dense about 93%)

Threshold read-off and the overall rate

One horizontal line at accuracy threshold T turns six curves into six rates. Part 03: Reading sensitivity curves

r_i = \max\left\{\, r \in \{0, 0.1, \dots, 0.9\} : \mathrm{Acc}^{\,i}_{r} \ge T \,\right\}

Per-layer rate: largest swept ratio still at or above T; never-crossing layers get the maximum swept ratio

R = \frac{\sum_i r_i N_i}{\sum_i N_i}, \qquad \text{compression} = \frac{1}{1 - R}

Overall rate is parameter-weighted, never the plain mean

Layer	Rate	Why
L0	about 73%	Crosses T between the 70 and 80 percent points
L1, L2, L5	90% (maximum swept)	Never cross T inside the sweep
L3	about 82%	Crosses just past 80 percent
L4	about 80%	Its 80 percent point sits just under the line

Read-off at T of about 79 to 80 percent (the slide's dashed line)

Layer	r = 50%	60%	70%	80%	90%	Rate
A (100,000 weights)	90%	84%	70%	52%	30%	50%
B (400,000 weights)	95%	93%	91%	86%	75%	70%
C (500,000 weights)	95%	95%	94%	93%	90%	90%

Exam-style table, T = 90 percent, accuracy after pruning one layer alone

Worked numbers

Weighted sum: 100,000 x 0.5 + 400,000 x 0.7 + 500,000 x 0.9 = 780,000
Overall rate R: 780,000 / 1,000,000 = 78%
Remaining, compression: 220,000 weights, about 4.5x
Unweighted mean (wrong): (50 + 70 + 90) / 3 = 70%
VGG-11 at the slide's T: rates 0.73, 0.90, 0.90, 0.82, 0.80, 0.90 give R = 86.3% (7.3x) against an unweighted 84.2%

Three ways to allocate one budget

Method	Who chooses the ratios	Cost	Interaction modelled	Transfers
Sensitivity analysis	One curve per layer plus one threshold T	Layers x ratios single-layer evaluations	No, layers swept alone	No, curves belong to one network
AMC	A DDPG agent, layer by layer	Hundreds of pruned networks, no retraining	Yes, the reward sees the whole network	New search per model and budget
NetAdapt	A greedy rule: the proposal with the highest accuracy	K proposals per iteration, each short-term fine-tuned	Yes, one layer at a time on the current network	New run per device and budget

Sensitivity analysis, AMC and NetAdapt

AMC: pruning as reinforcement learning

Fifty layers with ten candidate ratios each is 10^50 configurations. A DDPG agent learns only the per-layer ratio; magnitude selection inside each layer and one final fine-tune are unchanged. Part 04: AMC

The RL ingredients

State: Layer embedding: eleven scaled features (t, n, c, h, w, stride, k, FLOPs[t], reduced, rest, a[t-1])
Action: One continuous sparsity ratio a_t in (0, 1] for the current layer
Agent: DDPG, actor-critic: actor proposes a_t, critic scores Q(s_t, a_t)
Environment: Channel pruning of the pretrained network, magnitude selection inside each layer
Reward: -Error after all layers are pruned, if the FLOPs or latency budget holds
Episode: One pass over all layers, one pruned network, one reward, no fine-tuning during search

R = \begin{cases} -\text{Error} & \text{if the FLOPs or latency constraint is met} \\ -\infty & \text{otherwise} \end{cases}

Resource-constrained reward (slide 29)

R_{\text{FLOPs}} = -\text{Error} \cdot \log(\text{FLOPs})

Accuracy-guaranteed reward (slide 28)

W_{\text{duty}} = \alpha\, W_{\text{all}} - a_{\max} W_{\text{rest}} - W_{\text{reduced}}, \qquad a_t \leftarrow \max\!\left(a_t,\; \frac{W_{\text{duty}}}{W_t}\right)

Duty bound (Algorithm 1): the budget is met by construction, a_max is 0.8 for conv and 0.98 for FC

Region	Human expert	AMC
Conv1	50%	43%
ResBlock1 to ResBlock4	31, 31, 30, 30%	28, 28, 23, 19%
FC	20%	10%
Total (compression)	29% (3.4x)	20% (5x)
Top-1	76.13%	76.11%

ResNet-50 density kept, fine-grained pruning in four rounds (50, 35, 25, 20 percent)

The agent keeps 1x1 layers denser (peaks) and prunes 3x3 layers harder (crests): a stage-3 bottleneck holds about 590K of its 1.1M weights in the 3x3 layer.

Model	MACs	Top-1	Latency	Speedup
1.0 MobileNet	569M	70.6%	119.0 ms	1x
AMC (50% FLOPs)	285M	70.5%	64.4 ms	1.8x
AMC (50% Time)	272M	70.2%	59.7 ms	2.0x
0.75 MobileNet (uniform)	325M	68.4%	69.5 ms	1.7x

MobileNet on a Galaxy S7 Edge, TF-Lite, single core, batch 1 (slide 32)

NetAdapt: platform-aware pruning to a latency budget

A rule-based, iterative, progressive method: tighten the constraint by Delta R each round, thin one layer, keep the proposal that hurts least. Part 05: NetAdapt

\max_{\text{Net}} \; \text{Acc}(\text{Net}) \quad \text{s.t.} \quad \text{Res}_j(\text{Net}) \le \text{Bud}_j

Eq. 1: the global problem

\max_{\text{Net}_i} \; \text{Acc}(\text{Net}_i) \quad \text{s.t.} \quad \text{Res}_j(\text{Net}_i) \le \text{Res}_j(\text{Net}_{i-1}) - \Delta R_{i,j}

Eq. 2: the per-iteration problem

One iteration

1. Constraint: Con = Res_i - Delta R_i
2. Propose, per layer k: From the lookup table, the largest filter count that meets Con; keep the largest-l2 filters
3. Short-term fine-tune: About 10k iterations, then measure holdout accuracy
4. Pick: The proposal with the highest accuracy becomes Net_(i+1)
5. Repeat: While the latency is still above the budget
6. Long-term fine-tune: Once, to convergence; adds 1.8 to 4.5 points and is the number reported

Network	Top-1	MACs	Latency
25% MobileNetV1 (128)	45.1%	13.6M (100%)	4.65 ms (100%)
MorphNet	46.0%	15.0M (110%)	6.52 ms (140%)
NetAdapt guided by MACs	46.3%	11.0M (81%)	6.01 ms (129%)

Why a measured lookup table and not MACs (NetAdapt Table 1, Pixel 1 CPU)

Per-layer tables are indexed by layer shape, measured once on the device and summed; removing filters in layer k also removes input channels of layer k + 1. Worked hand run: 10.0 ms to a 7.0 ms budget with Delta R = 1.0 ms takes three iterations (9.0, 7.6, 6.5 ms), and the constraint is always set from the current latency, not the budget.

\#\text{models} = \#\text{iterations}

Every iteration's winner is a deployable network, so one run traces the accuracy versus latency frontier

Initial Delta R	Decay	Iterations	Top-1	Latency
0.5 ms	0.96	28	47.7%	4.63 ms
0.5 ms	1.0	20	47.4%	4.71 ms
0.8 ms	0.95	20	46.7%	4.65 ms

Resource reduction schedules, small MobileNetV1 (Table 2)

Slide 40: 1.7x faster than the width-multiplier baseline and 1.6x faster than MorphNet at equal or 0.3% higher accuracy on a Pixel 1 CPU; about 1.2x on a mobile GPU because of fixed overhead.

Aspect	AMC	NetAdapt
Who decides	DDPG agent learns a policy from rewards	Greedy rule: highest short-term accuracy wins
Search unit	Every layer once per episode	One layer changed per iteration, all layers tried
Cost model	FLOPs or latency in the reward, optional lookup table	Per-layer latency lookup table, measured and summed
Fine-tuning	One fine-tune of the final network	Short-term per proposal, long-term once
Output	One model per target	A model at every iteration, the whole frontier

AMC versus NetAdapt

Fine-tuning, iterative pruning and regularization

Pruning removes terms from a function the survivors were tuned to complete; fine-tuning at 1/10 to 1/100 of the original learning rate lets them absorb the work without leaving the minimum the ranking was measured in. Pipeline: Train Connectivity, Prune Connections, Train Weights, with a loop arrow back. Part 06: Fine-tuning and iterative pruning

AlexNet, Han et al. 2015

Parameters: 61M to 6.7M (9x)
Top-1 / top-5 error: 42.78 to 42.77% / 19.73 to 19.67%
Learning rate: 1/100 of the original for AlexNet, 1/10 for LeNet
Training versus retraining: 75 h versus 173 h on a Titan X
VGG-16: 138M to 10.3M (13x) in five iterations

s = 1 - \frac{1}{\text{ratio}}, \qquad \text{ratio} = \frac{1}{1 - s}

Sparsity and compression ratio are the same number

Ratio	Pruned away	What happens there
2x	50%	Free lunch, no retraining needed
3x	66.7%	Where pruning-only starts losing
5x	80%	Single prune plus fine-tune, no loss
9x	88.9%	Iterative, no loss on AlexNet
10x	90%	Iterative curve begins to drop
13x	92.3%	VGG-16 iterative result

Ratio to fraction pruned away

Curve	Within 0.5% loss up to	Reaches about -4% at
Pruning only	about 65%	about 80% (5x)
Pruning + fine-tuning	about 85%	about 93% (14x)
Iterative pruning + fine-tuning	about 92%	about 95.5% (22x)

Slide 51: how far each curve holds

s_t = s_f + (s_i - s_f)\left(1 - \frac{t - t_0}{n\,\Delta t}\right)^3

Zhu and Gupta's gradual schedule: fast early, slow late

L' = L(\mathbf{x};\mathbf{W}) + \lambda\,|\mathbf{W}| \qquad L' = L(\mathbf{x};\mathbf{W}) + \lambda\,\|\mathbf{W}\|^2

L1 and L2 regularized losses

	L1	L2
Penalty	lambda \|W\|	lambda \|\|W\|\|^2
Gradient	lambda sign(w), constant	2 lambda w, shrinks with w
Effect per step	Subtract a fixed amount	Multiply by a factor below one
Where weights end	Exactly zero, then stay	Small but never zero
Before retraining (Han et al.)	Better	Worse
After retraining (Han et al.)	Worse	Better, best overall

L1 versus L2 as preparation for magnitude pruning

Worked: w = 0.05, lambda = 0.01, eta = 0.1. L1 subtracts 0.001 per step and reaches zero in 50 steps. L2 multiplies by 0.998 per step: 0.0452 after 50, 0.0068 after 1000, never zero. Han et al. found L2 best overall for magnitude pruning.

L = \sum_{(x,y)} l\big(f(x, W), y\big) + \lambda \sum_{\gamma \in \Gamma} |\gamma|

Network Slimming: L1 penalty on batch norm scaling factors, then a global percentile threshold on gamma; 20x smaller, 5x fewer ops on VGGNet

EIE: why sparsity needs hardware

A 91% sparse AlexNet FC6 on vendor sparse kernels gains little and can lose. Part 07: EIE

Platform	Batch	Dense	Sparse	Sparse vs dense
Core i7-5930k CPU	1	7516.2 us	3066.5 us	2.5x faster
Titan X GPU	1	541.5 us	134.8 us	4.0x faster
Titan X GPU	64	19.8 us	94.6 us	4.8x slower
EIE, 64 PEs	1	sparse only	30.3 us	248x vs dense CPU

AlexNet FC6, EIE Table IV

Source	Sparsity or bits	Compute	Memory	Rule of thumb
Sparse weight	90% static	10x	5x (index overhead)	0 x A = 0
Sparse activation	70% dynamic	3x	none claimed	W x 0 = 0
Weight sharing	4-bit codes	none claimed	8x	2.09, 1.92 => 2

Three savings (slide 57)

b_i = \mathrm{ReLU}\Big(\sum_{j \in X_i \cap Y} S[I_{ij}]\, a_j\Big)

X_i: static nonzero columns of row i; Y: dynamic nonzero activations; S: 16-entry codebook; I_ij: 4-bit code

\mathrm{PE}(i) = i \bmod N, \qquad b_i = \mathrm{ReLU}\Big(\sum_{j \in Y} W_{ij}\, a_j\Big)

Rows interleaved round-robin; nonzero activations broadcast with their index; every output stays local to one PE

Worked 8 x 4 example with a = (0, 2, 0, 1) and eleven nonzeros: two broadcasts, seven multiplications instead of 32, columns 0 and 2 never visited, MACs per PE 3, 0, 3, 1. EIE accelerates only matrix-vector products in FC and LSTM layers at batch size 1.

Inside the PE and the storage format

Part 08: EIE dataflow and PE

Five stages in order

1. Act Queue: FIFO of broadcast (a_j, j) pairs, depth 8; depth 1 idles about half of all cycles
2. Pointer Read: p_j and p_(j+1) from even and odd banks in one cycle; entry count is p(j+1) - p(j)
3. Sparse Matrix Access: 8-bit entries, 4-bit code plus 4-bit relative index; one 64-bit read returns 8 entries
4. Arithmetic Unit: Decoder expands the code to 16-bit fixed point; address accumulator sums relative indices; multiply-add with bypass
5. Act R/W: Source and destination register files, 64 x 16 bits each, swap roles per layer
Tail: ReLU, then leading nonzero detection feeds the next layer's broadcast

Storage formats and bit widths

Weight code v: 4 bits, index into a 16-entry per-layer codebook
Relative index x: 4 bits, zeros since the previous entry, at most 15
Padding: gap above 15: insert v = 0, x = 15, keep counting
Pointer p(j): 16 bits, start of column j
Arithmetic: 16-bit fixed point (79.8% vs 80.3% FP32; 8-bit collapses to 53%)
Per PE: 162 KB SRAM, 93% of area, 0.638 mm2, 9.157 mW at 800 MHz, 45 nm
Chip: 64 PEs, about 600 mW, 21 LNZD nodes (16 + 4 + 1)

Relative-index CSC on the running example

PE0 slice (rows 0, 4): [w00, w01, 0, w03] over [0, 0, w42, w43]
Values v: [w00, w01, w42, w03, w43]
Relative index x: [0, 0, 1, 0, 0]
Pointers p: [0, 1, 2, 3, 5]
Column [0,0,5,0,0,0,0,7]: v = [5, 7], z = [2, 4]

EIE results and what came after

After the accumulators, ReLU then leading nonzero detection make the output the next layer's sparse input without leaving the chip. Part 09: EIE results and lessons

120 \times 10 \times 8 \times 3 = 28{,}800\times

Theoretical energy saving; dropping the SRAM factor alone leaves only 240x

Factor	Size	Where it comes from	Mechanism
SRAM instead of DRAM	120x	5 pJ vs 640 pJ per 32-bit read (128x, rounded)	Compression makes the model fit on chip
Weight sparsity	10x	10% density	Zeros never stored or fetched
Weight sharing	8x	4-bit codes vs 32-bit	Decoder expands on the way to the multiplier
Activation skipping	3x	about 70% zeros after ReLU	Never broadcast a zero

The four factors

Headline numbers to quote and qualify

Speed: 189x vs Core i7 CPU, 13x vs Titan X GPU, batch size 1
Energy: 24,000x vs CPU, 3,400x vs GPU, 2,700x vs Tegra K1
Theory versus measured: 28,800x on paper; about 10x lower measured because of index overhead and 45 nm vs 28 nm
Throughput: 102 GOPS on the compressed network equals about 3 TOPS dense
FLOP reduction per layer: 1 / (d_weight x d_activation): AlexNet-6 33x, VGG-6 100x, LSTM layers 10x (activation density 100%)
Versus DaDianNao, matched node: 2.9x throughput, 19x energy, 3x area

\text{FLOP reduction} = \frac{1}{d_{\text{weight}} \times d_{\text{activation}}}

AlexNet-6: 1 / (0.09 x 0.35), about 33x; LSTM gates produce no zeros so activation density is 100%

The cross-platform chart mixes 22, 28 and 45 nm, a projected 256-PE bar and a bandwidth estimate for DaDianNao: read it as decades, not ratios. EIE at 0.59 W gives 138,927 frames per joule against 9,263 for DaDianNao at 15.97 W.

Verdict	Point	Evidence or successor
Held up	Special-purpose hardware pays off early	Sparse stays cost-effective to 50% density on EIE; software only below 1%
Held up	Both sparsities, cycles and energy	NVDLA, Samsung NPU, Ambarella CV22
Held up	W4A16	GPTQ, AWQ, llama.cpp, MLC LLM for batch-1 LLM decoding
Did not	Irregular sparsity on vector processors	2:4 Sparse Tensor Cores, ESE load-balance-aware pruning
Did not	50% index overhead around one MAC	Coarse-grained block sparsity
Did not	FC layers only, batch 1	SCNN, Cambricon-X, Eyeriss v2 for sparse convolution
Did not	Everything in SRAM	10 to 100 billion parameter LLMs do not fit

The 2023 retrospective

M:N sparsity on tensor cores

Fine-grained in what it removes, structured in how many: exactly two of every four consecutive weights along a row. Part 10: M:N sparsity

\text{sparsity} = 1 - \frac{a}{b}, \qquad 2{:}4 \;\Rightarrow\; 50\%

a:b pattern, a survivors per block of b

\text{bits}_{2:4} = R \cdot \tfrac{C}{2} \cdot b + R \cdot \tfrac{C}{2} \cdot 2, \qquad \text{bits}_{\text{dense}} = R \cdot C \cdot b

Values plus 2-bit indices; the saving is below 50 percent because of the metadata

One group of four, and A100 peaks

FP16 dense: 4 x 16 = 64 bits
FP16 compressed: 2 x 16 + 2 x 2 = 36 bits, about 44% saved
INT8 dense: 4 x 8 = 32 bits
INT8 compressed: 2 x 8 + 2 x 2 = 20 bits, about 38% saved
A100 peak TOPS: FP16 312 dense, 624 sparse; INT8 624 dense, 1248 sparse

Case	Dense	Values	Metadata	Total	Saving
FP16, 1024 x 1024	16,777,216 (2 MiB)	8,388,608 (1 MiB)	1,048,576 (128 KiB)	9,437,184 (1.125 MiB)	43.75%
INT8, 4096 x 4096	134,217,728 (16 MiB)	67,108,864 (8 MiB)	16,777,216 (2 MiB)	83,886,080 (10 MiB)	37.5%

Whole-matrix storage in bits

Train the model dense, exactly as usual.
Prune to 2:4 by magnitude: zero the two smallest of every four along each row.
Retrain with the same optimizer, schedule and epochs, zeros held fixed. No hyper-parameter search.

GEMM-K	Speedup
1280	about 1.2x
3840	about 1.7x
12800	about 1.9x
20480	about 1.95x

INT8 sparse versus dense GEMM speedup on A100, M = N = 10240

Speedup grows with K because only the math halves; small GEMMs are memory and overhead bound (low arithmetic intensity). Amdahl with GEMMs at 70% of time: 1.8x on GEMMs gives about 1.45x end to end, 1.2x gives 1.13x. Accuracy: ResNet-50 76.1 dense, 76.2 sparse FP16 and INT8, within run-to-run noise on twenty CNNs. MobileNet v2 drops from 71.55 to 69.56 under the plain recipe and recovers to 71.56 with channel permutation.

Aspect	EIE (2016)	2:4 tensor core (2020)
Sparsity exploited	Weights about 90% plus activations about 70%	Weights only, exactly 50%
Weight format	CSC, 4-bit index plus 4-bit code, pointers, padding	Contiguous values plus one 2-bit index each
Finding work	Leading nonzero detection, FIFO for load balance	Multiplexer driven by 2-bit indices
Hardware	Custom 45 nm ASIC	Every Ampere or later GPU
Ceiling on math	Proportional to combined sparsity	2x, fixed by the pattern

EIE versus 2:4

Sparse convolution

Outdoor LiDAR grids are below 0.01% dense. A dense 3 x 3 convolution dilates one active site to 3^d, then 5^d. Submanifold sparse convolution computes an output only where an input exists, so P_out = P_in. Part 11: Sparse convolution

\lvert \mathcal{P}_L \rvert = (2L + 1)^d

Active sites from one point after L dense 3^d layers

Stage	Active cells	Density
Input	4 of 20	20%
After one dense 3 x 3 layer	17 of 20	85%
After one submanifold layer	4 of 20	20%
After a second dense layer	20 of 20	100%

Slide grid, 4 x 5 with four active cells

f_{\text{out}}(Q) \leftarrow f_{\text{out}}(Q) + f_{\text{in}}(P)\, W_{(dx,dy)} \quad \text{for every } (P, Q, W_{(dx,dy)}),\; P = Q + (dx, dy)

The update rule; the map of (In, Out, Wgt) tuples is the whole computation

For P0 on slide 95: nine conventional entries, two sparse entries (W(0,0) to itself and W(-1,-1) to the point at (2, 2)). State the sign convention before computing anything: TorchSparse writes the opposite sign.

Method	Entries	MACs
Fully dense 3 x 3 over 20 outputs	180	737,280
Conventional, skipping zero inputs	30	122,880
Submanifold sparse	10	40,960

One 3 x 3 layer on the slide grid, C_in = C_out = 64 (4,096 MACs per entry)

Weight	Entries (In, Out)	Rows
W(-1,-1)	(P0, Q1), (P3, Q4)	2
W(-1,0)	(P1, Q3)	1
W(0,0)	(Pi, Qi) for all five points	5
W(1,0)	(P3, Q1)	1
W(1,1)	(P1, Q0), (P4, Q3)	2
Other four offsets	none	0

Slide 96: eleven entries grouped by weight offset, five points on a 5 x 5 grid

TorchSparse: regularity from irregularity

A 3 x 3 x 3 kernel launches 27 (or 26 plus a separate centre) small uneven matmuls per layer. Part 12: TorchSparse

r = 1 - \frac{\sum_{\delta \in G} |M_\delta|}{|G| \cdot \max_{\delta \in G} |M_\delta|}

Redundant computation ratio of a group; adaptive grouping keeps r at or below epsilon, and a group runs as bmm only if its largest map is below S

Strategy	Launches	Rows computed	Pad rows	Overhead
Separate (one mm per offset)	9	302	0	0%
Dense (one bmm, batch 9, padded to 100)	1	900	598	66.4%
Adaptive (epsilon 0.05, S = 50)	3	308	6	1.9%

Nine offsets on a 100-point cloud (map sizes 100, 40, 40, 38, 38, 12, 12, 11, 11)

Dataset	Strategy	TFLOP/s	Speedup
SemanticKITTI	Separate	8.1	1.00x
SemanticKITTI	Fixed grouping	8.7	0.87x
SemanticKITTI	Adaptive grouping	11.9	1.39x
nuScenes	Separate	10.4	1.00x
nuScenes	Fixed grouping	21.1	1.50x
nuScenes	Adaptive grouping	16.9	1.54x

Matmul-phase ablation, RTX 2080 Ti, FP16 (Table 2)

Numbers to keep

Baseline bottlenecks: Gather and scatter 40 to 50% of runtime; matmul about 30% utilization (8.1 TFLOP/s on an RTX 2080 Ti)
Groups sweep (slide 105): 26 groups 1.0x, 13 about 1.2x, 6 about 1.5x, 3 below 1.0x, 1 about 0.35x
End to end: 1.6x over MinkowskiEngine, 1.5x over SpConv, memory movement cost 2.7x lower
TorchSparse++ on A100: 2.9x, 3.3x, 2.2x, 1.7x over MinkowskiEngine, SpConv 1.2.1, TorchSparse, SpConv 2.3.5
TorchSparse++ on Jetson Orin: 1.25x over SpConv 2.3.5 on average
Implicit GEMM redundancy: Slide 109: 12 to 10 (row reordering) to 8 (column splitting)

Dataflow	Stationary	Kernels	Memory and compute	Redundancy
Gather-GEMM-scatter	Weight	Three kernels per offset	No overlap	Zero (plus padding if grouped)
Fetch-on-demand	Weight, fused	One fused kernel	Loads overlap on-chip multiply	Zero, but 4x to 10x more output writes
Implicit GEMM	Output	One fused kernel, pipelined tiles	Next tile loads overlap the current one	Lockstep redundancy inside each warp

Three GPU dataflows (TorchSparse++)

TorchSparse++ fuses the phases so loads for the next tile overlap the current multiply, and contributes the Sparse Kernel Generator (fused, pipelined kernels at under a tenth of SpConv v2's 40,000 lines) and the Sparse Autotuner (dataflow and tile parameters per layer group). Adaptive grouping stays in its design space.

PointAcc: mapping in hardware

On point clouds more than half of runtime on general-purpose hardware is map construction, and a TPU must ship coordinates back to its host (60 to 90% of runtime in data movement). Part 13: PointAcc and summary

p = q + \delta \iff p - \delta = q, \qquad \text{comparisons per offset} = |I| + |O| - 1

Shift every input by minus delta, merge-sort with the outputs, read equal adjacent pairs as map entries

	W1,1 (slide 112)	W-1,-1 (slide 111)
Offset delta	(1, 1)	(-1, -1)
Shift applied to inputs	+ (-1, -1)	+ (1, 1)
Shifted inputs P0 to P4	(0,0) (1,1) (1,3) (2,1) (3,2)	(2,2) (3,3) (3,5) (4,3) (5,4)
Equal neighbors after the merge	Q0 = P1, Q3 = P4	Q1 = P0, Q4 = P3
Tuples emitted	(P1, Q0, W1,1), (P4, Q3, W1,1)	(P0, Q1, W-1,-1), (P3, Q4, W-1,-1)

Slides 112 and 111, five points P0 (1,1), P1 (2,2), P2 (2,4), P3 (3,2), P4 (4,3), stride 1

	Hash table	Merge sort
Memory access	Random probes, one per output per offset	Two sequential streams, read once
Parallel hardware	N x N crossbar, O(N^2) area	One comparator per merge step
Storage	Table up to 160 MB	Sorted coordinate lists, no table
At equal parallelism	Baseline	1.4x faster, up to 14x less area

Hash table versus merge sort as the mapping engine

One ranking unit also serves stride downsampling (quantize then deduplicate), farthest point sampling (top-1), kNN (top-k) and ball query (threshold). The mapping unit emits indices only; the systolic matrix unit does the multiplies.

Metric	vs RTX 2080Ti	vs Xeon Skylake + TPU V3	vs Xeon Gold 6130
Speedup	3.7x	53x	90x
Energy saving	22x	210x	176x (slide prints 193x)

Geometric means over eight networks (slide 113)

The TPU column swings from 3.4x (DGCNN, feature-space neighbour search is already dense matmul) to 269x (F-PointNet++, dominated by sampling and neighbour search the TPU sends back to the host). The energy number is the embedded number.

Sparsity types and the systems that exploit them

Sparsity	Origin	System	Mechanism
Fine-grained weight	Pruning, static	EIE	CSC storage, PE array, weight sharing, skip zero weights
M:N weight (2:4)	Patterned pruning, static	NVIDIA Ampere sparse tensor cores	2-bit metadata selects activations, 2x math
Activation (ReLU zeros)	ReLU at run time, dynamic	EIE	Leading nonzero detection, never broadcast a zero
Activation (point clouds)	Data occupancy, dynamic	TorchSparse, PointAcc	Maps plus gather, matmul, scatter; merge-sort mapping unit

The lecture in one table

Slide errata

Answer with the corrected fact, and name the slide if a question depends on it.

What the slides get wrong

Slide 3: Text writes ||W_p||_0 < N, figure writes ||W_P||_0 <= N. Read <= N and one matrix.
Slide 29: "constrains" means constraints. Action range is (0, 1] in the paper, not [0, 1).
Slide 40: "a serial of models" means a series of models.
Slide 43: "the model may decrease" means the model accuracy may decrease. "Finetuing" means Finetuning.
Slide 51: "Finetuing" again. 5X to 9X are compression ratios 5x and 9x.
Slide 52: "fine-tuning quantized networks" means pruned networks here. Network Slimming uses plain L1, not smooth-L1.
Slide 56: "Han et al (MIT)": all five papers list Stanford and NVIDIA; Han joined MIT afterwards.
Slides 61 to 64: With a = (0, a1, 0, a3), outputs b1, b3, b5 must be zero; the figure draws them nonzero.
Slide 74: Axes say Layers/s and Layers/J; the paper says frames. Same quantity for one FC layer.
Slide 77: PointAcc is MICRO 2021, not Micro'22.
Slide 86: Credit says Graham, BMVC 2015; submanifold sparse convolution is Graham and van der Maaten 2017 and CVPR 2018.
Slide 101: "TorshSparse" means TorchSparse.
Slide 113: CPU energy GeoMean printed as 193; the paper and the eight bars give 176x.
Slide 115: Missing NetAdapt, EIE, Mishra et al. 2021, TorchSparse, TorchSparse++, PointAcc. Hu et al. is 2016 (arXiv 1607.03250), not 2017.