PointAcc, the lecture summary and references

The roadmap on slide 110 puts PointAcc in the last row, next to TorchSparse, under the heading activation sparsity. Read the row as a pair: TorchSparse is the software answer to sparse inputs, and PointAcc is the hardware answer to the same inputs. Both start from the Sparse convolution of part 11, where a layer is driven by maps of (In, Out, Wgt) tuples and each tuple contributes f_out = f_out + f_in × W_wgt.

What changes between the two is where the time goes. On a GPU, the multiplies are batched into matmuls and run well once the map exists. Building the map is the problem. A point cloud has dynamic sparsity: which coordinates are occupied depends on the scene, so the map cannot be precomputed and must be rebuilt on every input. The PointAcc paper measures that cost on PointNet++-based networks and reports that more than half of the total runtime on general-purpose hardware goes to mapping operations, and that existing neural accelerators simply do not support them, so a TPU has to ship the coordinates back to its host CPU, where data movement then takes 60 to 90 percent of the runtime (Lin et al., 2021, section 3).

The pairing rule, and how to turn it into an equality test

A 3 × 3 kernel has nine weight offsets, W−1,−1 through W1,1. Input point p contributes to output point q through offset δ exactly when p sits at q + δ. On a GPU the natural code is a loop over outputs that asks a hash table "is there an input at q + δ?". PointAcc rewrites the same condition so that no lookup is needed.

Subtract δ from every input coordinate and the question becomes "which shifted inputs land on an output coordinate?", which is a set intersection. If both sets are sorted, an intersection is found by merging them and looking at adjacent elements: any input and output that coincide must end up side by side. This is why slide 112 adds (−1, −1) to the inputs for W1,1 and slide 111 adds (1, 1) for W−1,−1. The shift is always −δ, so the sign flips relative to the offset name.

Slide 111 runs the identical procedure for the opposite corner of the kernel. The table below puts the two passes side by side. Notice the symmetry: the pairs for W1,1 are the pairs for W−1,−1 with the roles of input and output exchanged, P1 with Q0 against P0 with Q1. That is exactly what p = q + δ predicts, because if p = q + δ then q = p − δ, and with the input and output clouds sharing coordinates the same two points swap places.

Why a hash table is the wrong tool for silicon

The GPU library that PointAcc compares against builds its maps with a hash table, and on a GPU that is a reasonable choice: memory is large and random access is cheap enough. Neither holds on chip. The paper puts two numbers on it. First, a hash table sized for a real point cloud at a sensible load factor can reach 160 MB, which no accelerator can hold in SRAM. Second, to serve N lookups in parallel the SRAM needs an N-by-N crossbar so that any lane can reach any bank, and that crossbar grows as O(N²) in area (Lin et al., 2021, section 4.1).

Merging has neither problem. The Mapping Unit feeds window-sized chunks of the two sorted lists to a fixed-size bitonic merger, a parallel comparator network, and a forwarding loop carries leftover elements into the next cycle, so the lists are read in order and never probed at random. Detecting the intersection is just as local: the paper describes feeding each pair of adjacent elements of the merged array to a comparator that checks whether their coordinates are equal. With |I| shifted inputs and |O| outputs the strip has |I| + |O| cells and |I| + |O| − 1 adjacent comparisons, all independent, so they can run in a single cycle. The Mapping unit builds this from a bitonic sorting network feeding a merger of fixed length, and the paper reports that at the same parallelism the merge-sort design is 1.4x faster than the hash-table design while saving up to 14x in area (Lin et al., 2021, section 4.1).

One sorting unit, four point-cloud operations

The reason PointAcc calls this block a mapping unit rather than a convolution helper is that sorting turns out to be the common core of every irregular operation a point-cloud network needs. Kernel mapping is an equality after a shift. Building the output cloud under a stride s is quantizing coordinates to the stride grid and then deduplicating, which sorting does by putting duplicates next to each other. Farthest point sampling picks the point with the largest distance, a top-1 of a ranking. k-nearest-neighbor search is a top-k of the same ranking, and ball query is a threshold on the sorted distances. The paper lists these as the operations the single ranking-based unit implements (Lin et al., 2021, sections 2.1 and 4.1). Flip the simulator above to stride 2 to see the output construction case: the five inputs collapse to fewer outputs before any offset is tried.

Slide 113 is a pair of bar charts with three baselines, and the baselines matter more than the bars. Red is an NVIDIA RTX 2080Ti, the server GPU that already runs TorchSparse-style code well. Dark grey is an Intel Xeon Skylake host paired with a TPU V3, a dense-matmul accelerator that has to send every mapping operation back to the host. Light grey is an Intel Xeon Gold 6130 CPU alone. The right-most group, GeoMean, is the geometric mean across the eight networks, so no single network dominates the average.

Start with the GeoMean row and read the two charts together. Against the GPU, PointAcc is 3.7x faster and 22x more energy efficient. Against the TPU system it is 53x faster and saves 210x energy. Against the CPU it is 90x faster and saves 176x (the slide prints 193x, see the errata below). The paper's abstract leads with the GPU pair, 3.7x and 22x over an RTX 2080Ti, evaluated on eight models across four applications (Lin et al., 2021).

The network names encode the benchmark. The PointNet++ suffixes are (c) classification, (ps) part segmentation and (s) semantic segmentation. F-PointNet++ is the frustum detector built on PointNet++. MinkNet(i) and MinkNet(o) are MinkowskiUNet on an indoor dataset (S3DIS) and an outdoor dataset (SemanticKITTI), the two sparse-convolution workloads closest to part 11 (Lin et al., 2021, Table 2).

Why the TPU column swings from 3.4x to 269x

The GPU column is flat, between 2.4x and 8.3x, because a GPU handles both the mapping and the matmuls in the same memory. The TPU column ranges from 3.4x on DGCNN to 269x on F-PointNet++, and the spread is the lesson of the whole part. The paper attributes the gain over the TPU mainly to supporting mapping operations on chip (Lin et al., 2021, section 5.2). The paper does not break that number down per network, so the following is a reading of the chart, not a quoted result. DGCNN's neighbor search is a pairwise-distance computation in feature space, recomputed inside every EdgeConv layer, and a dense matmul unit already runs that well, so it has the least mapping work to move on chip. F-PointNet++ and the segmentation variants of PointNet++ are dominated by sampling, neighbor search and gathering, exactly the operations the TPU must hand back to the host, so removing that round trip is worth two orders of magnitude.

Slide 114 compresses the lecture into two bullets: automated ways to find pruning ratios, and system and hardware support for different granularities. Those two bullets are two separate questions from the five that opened the deck. The first asks how much to remove from each layer. The second asks how the zeros you created turn into time and energy actually saved. Neither is worth much without the other.

Thread one: choosing the ratio

Sensitivity analysis prunes one layer at a time across a sweep of ratios, plots accuracy against ratio, and reads each layer's rate where its curve crosses an accuracy threshold. It is cheap and transparent, and its weakness is that it ignores Layer interaction: the compounding loss when many layers are pruned together, which is why its per-layer rates are only a starting point. AMC (AutoML for Model Compression) replaces the human with a DDPG agent that sees a layer embedding and emits a continuous sparsity ratio, rewarded by accuracy under a FLOPs or latency budget. NetAdapt keeps a rule instead of a policy: cut latency by a fixed step, choose the layer whose short-term fine-tuned accuracy is highest, consult a measured latency lookup table rather than FLOPs, repeat until the budget is met, then long-term fine-tune. Whichever chooses the ratios, Fine-tuning and Iterative pruning are what recover the accuracy afterwards.

Thread two: making the zeros pay

A pruned weight is only free if the hardware skips it. EIE (Efficient Inference Engine) skips two kinds at once: static Weight sparsity stored in CSC form across an array of processing elements, and dynamic activation sparsity caught by leading non-zero detection so that a zero activation is never broadcast. NVIDIA Ampere tensor cores accept 2:4 sparsity only, and in return the Sparse tensor core uses the two-bit metadata to select operands and doubles math throughput (Mishra et al., 2021). TorchSparse handles the sparsity of point-cloud inputs in software by trading a little padding for regular batched matmuls through Adaptive grouping, and TorchSparse++ overlaps the gather and scatter with compute. PointAcc moves the same problem into hardware, with the merge-sort mapping unit of the previous concept. The granularity is the thread joining all four: the finer the sparsity, the more bookkeeping the system must do to skip it, and the coarser the sparsity, the more the pruning method must give up to fit the pattern.

The bridge to the next lecture

Pruning removes weights. Quantization shrinks the ones that stay. Slide 114 sets the order for the next lecture: first the numeric data types modern computer systems actually offer, then the basic concept of neural network quantization, then the common quantization methods. The two techniques are complementary in the deep compression sense: after pruning left AlexNet with a ninth of its connections, quantizing and coding the survivors is what pushed the total to 35x in Han et al.'s pipeline, and both will show up together in the memory and energy arguments of the next lecture (Han, Mao and Dally, 2016).

Slide 115 lists nineteen references. Read as a map of the lecture they fall into six groups: foundations of model compression and energy (items 1, 2, 4, 5, 6), pruning criteria (3, 12, 13, 15), structured and channel pruning (7, 10, 11, 14, 16, 17), automated ratio search (9), hardware support (8), and one-shot pruning of large language models (18), with Prof. Han's TinyML course (19) as the source the whole deck follows. The Sources block at the end of this part gives a link for each one that has an archival home.

The list is also worth checking against the slides themselves, because several of the papers this lecture leaned on hardest are cited in slide footers but never make it to the reference page. Every hardware system in the second half of the deck is in that position. If you cite from this lecture in your own writing, take the references from the Sources below rather than from slide 115.