Pruning granularity: from irregular to regular

Take a weight matrix with eight rows and eight columns, 64 weights in all, and decide to remove 24 of them. One way is to cross out rows 3, 4 and 7 completely. Another is to cross out 24 individual entries wherever the magnitude criterion of part 05 says they matter least. Both leave 40 weights and both reach a Sparsity of 24 / 64 = 37.5%. Everything else about them is different.

The unit you delete is the Pruning granularity. Deleting single weights is fine-grained, or unstructured, pruning. Deleting whole rows, columns, kernels or channels is coarse-grained, or structured, pruning. Two consequences pull in opposite directions as the unit grows. The number of masks you may choose from falls, which costs accuracy at a given Pruning ratio. The regularity of what survives rises, which is what lets ordinary hardware run the pruned layer faster.

Counting the choices

The slide calls fine-grained pruning "more flexible" and coarse-grained pruning "a subset of the fine-grained case". Both statements can be made exact by counting masks. A mask is the set of positions you zero, and the pruning problem of part 01 searches over masks for the one with the lowest loss.

Why irregular means hard to accelerate

Multiply a vector by the 5 x 8 survivor and nothing special happens. It is just a smaller dense matrix, and every BLAS routine, every tensor core and every microcontroller loop handles it at full speed. That is the slide's "easy to accelerate (just a smaller matrix!)". Now multiply by the 8 x 8 matrix with 24 holes. A dense routine still performs all 64 multiplies, 24 of them by zero, and gains nothing. To gain, you must store the 40 surviving values together with their positions, in a compressed sparse format, and let the hardware skip the zeros one by one. Mao et al. draw the same line: fine-grained sparsity scatters the tensor into isolated weights and needs custom accelerators such as EIE or SCNN to exploit it, while filter and channel sparsity is simple to accelerate on general-purpose processors because it "is equivalent to obtaining a smaller dense model" (Mao et al., 2017, section 2).

The gap is measurable. Wen et al. trained AlexNet with structured sparsity and reported average layer-wise speedups of the convolutional layers of 5.1x on CPU and 3.1x on GPU with off-the-shelf libraries, against 3.0x and 0.9x for non-structured l1 sparsity (Wen et al., 2016, Table 4). The fine-grained model had more zeros. The structured model ran faster.

What the accuracy price looks like

Because coarse units search a smaller space, they lose a little accuracy at the same density (the fraction of weights kept). Mao et al. measured this on ImageNet with the same pipeline at every granularity. The differences are small between fine and vector grains and grow as the grain reaches whole kernels; pruning entire filters "loses nearly 1% validation accuracy at the very first pruning stage" on AlexNet (Mao et al., 2017).

A linear layer's weight is a matrix, so its only structured units are rows and columns. A convolution weight is richer. Slide 17 draws one: three rows of kernels stacked vertically, two columns of kernels side by side, and each kernel a 3 x 3 grid. Count the cells and you get 3 x 2 x 3 x 3 = 54 weights.

Those four factors are the four dimensions of a convolution weight. The tensor has shape [c_o, c_i, k_h, k_w]: c_o output channels, also called filters; c_i input channels; and a kernel of height k_h and width k_w. Goodfellow, Bengio and Courville write the same object as a 4-D kernel tensor K whose element K[i, j, k, l] is the connection strength between output channel i and input channel j at a row offset of k and a column offset of l (Goodfellow et al., 2016, section 9.5). PyTorch stores Conv2d.weight with exactly the slide's ordering, (out_channels, in_channels / groups, kernel_size[0], kernel_size[1]) (PyTorch documentation).

Slicing the tensor into units

The reason the lecture stops to name the dimensions is that each way of slicing the tensor is a candidate pruning unit. Mao et al. name the slices with array notation, and reading them that way makes the counts automatic. Fix the output channel and you have a filter, a 3-D slab. Fix the output and input channel and you have one kernel, a 2-D grid. Fix a row inside that kernel and you have a 1-D vector. Fix everything and you have a single scalar weight (Mao et al., 2017, section 3.2).

Two formulas do all the work. A filter holds c_i · k_h · k_w weights, because it has one kernel per input channel. An input channel holds c_o · k_h · k_w weights, because every filter has a kernel that reads it. In the slide these are 18 and 27, and it is easy to mix them up, so picture the grid: a filter is a row of kernels, an input channel is a column of kernels.

The same counts at a realistic scale

Slide 17 is a toy so the picture fits. A VGG-style layer with 64 input and 64 output channels and 3 x 3 kernels has 64 x 64 x 9 = 36,864 weights, and the same slicing rules apply.

Removing a whole filter has a second effect that Li et al. spell out. The filter's output feature map disappears, so the next layer no longer receives that channel, and the corresponding kernels in the next layer's weight tensor disappear too. Pruning m of the n filters of a layer removes m / n of the compute in that layer and in the one after it (Li et al., 2017).

Put the two previous ideas together and the lecture's central figure appears. Slide 18 takes the same 54-weight tensor and prunes it five times, once per unit, arranging the results on an axis from irregular to regular. Read from left to right, the holes grow from single cells, to fixed shapes inside kernels, to whole rows, to whole kernels, to an entire column of kernels.

Every panel can be counted, and counting them shows something the picture hides: every panel removes between a third and two thirds of the weights, so the real difference between them is not how much Sparsity they reach but how the zeros are arranged. The fine-grained panel keeps 23 scattered weights. The pattern-based panel keeps exactly four cells in every kernel, and each kept shape is a Tetris piece (a T or an L of four cells). The vector-level panel keeps seven of the eighteen kernel rows. The kernel-level panel drops the first filter's right kernel and the second filter's left kernel. The channel-level panel drops the whole second input channel across all three filters, and what survives is a dense [3, 1, 3, 3] tensor.

The ladder, rung by rung

Mao et al. organise four grains (fine, vector, kernel, filter) by how many dimensions each unit spans. The slide keeps their order, inserts pattern-based pruning between fine-grained and vector-level, and shows the 3-D rung as an input channel instead of Mao's filter (Mao et al., 2017, section 3.2). At the bottom, fine-grained pruning removes 0-D scalars anywhere. Pattern-based pruning keeps a small catalogue of fixed shapes inside each kernel, which the slide calls "like Tetris": the hardware knows the finite set of masks in advance instead of facing arbitrary holes. Niu et al. describe it as "fine-grained pruning patterns inside the coarse-grained structures" and, by compiling specialised code per pattern, ran networks on mobile CPUs and GPUs up to 44.5x faster than TensorFlow Lite and up to 11.4x faster than TVM with no accuracy loss (Niu et al., 2020). Vector-level pruning removes 1-D rows, W[o, i, r, :], of a kernel. Kernel-level pruning removes 2-D kernels, W[o, i, :, :]. At the top, channel pruning removes a 3-D slab: on the slide, an input channel W[:, i, :, :] across every filter.

The right-hand column is the practical half of the story. Only the channel and filter rungs run faster on unmodified dense libraries, because the tensor simply shrinks. Kernel and vector sparsity line up with 2-D and 1-D convolution primitives (Winograd, Eyeriss-style 1-D units), which makes custom hardware simpler, but Mao et al. note they are still hard to accelerate on general-purpose processors. Pattern-based pruning needs compiler support (PatDNN) or dedicated support such as NVIDIA's 2:4 sparse tensor cores, and fine-grained sparsity needs accelerators such as EIE (Mao et al., 2017, section 6).

Try every rung on one tensor

The simulator below holds a random [3, 2, 3, 3] tensor and lets you prune it with any of the six units, including the filter unit that Mao et al. list alongside channels. It groups the weights by the chosen unit, scores each group with the L1 or L2 magnitude that part 05 develops, zeros the weakest groups until the target is met, and reports what survives. Watch three things as you switch units: the achieved sparsity snaps to coarser steps, the index count collapses as units grow, and only the channel and filter units ever produce a smaller dense tensor.

The energy argument from part 01 also runs along this axis. Mao et al. simulated the SCNN sparse accelerator on VGG-16 and found that, at the same density, vector-level sparsity needs 30 to 35% fewer output memory references than fine-grained sparsity. Neighbouring surviving weights in a row write to the same output address, so SCNN can skip the repeated read and write of that address (Mao et al., 2017, section 6 and Table 4). Since a DRAM access costs about two hundred times a multiply, fewer memory references is where the energy goes, not fewer multiplies.