TL;DR
TETRIS is a novel pruning method that bridges the gap between high-accuracy fine-grained pruning and hardware-friendly structural pruning. By reordering the dimensions of weight tensors to cluster unimportant weights into dense blocks, the authors enable significant GPU speedups with minimal accuracy loss.
The Usability Gap in Weight Pruning
Weight pruning is a popular technique to compress Deep Neural Networks (DNNs) by removing weights with small magnitudes. However, there is a persistent "usability gap" in pruning methodologies:
- Fine-grained (element-wise) pruning achieves high sparsity with almost no accuracy loss, but it creates irregular memory access patterns. Standard hardware like CPUs and GPUs are optimized for continuous data; they struggle to accelerate these "holey" matrices, often running slower than the original dense models.
- Structural pruning (removing entire rows, columns, or filters) is very fast on hardware but significantly hurts model accuracy because it lacks the flexibility to keep important individual weights that happen to reside in a "pruned" row.
The authors identify a fundamental trade-off between sparsity granularity (how big the pruned chunks are) and accuracy. TETRIS aims to break this trade-off entirely.
Methods: The Reordering Algorithm
The core idea is inspired by the game Tetris: if you can move the pieces around, you can create solid structures that are easy to "clear" (prune).
The authors propose a Reordering Algorithm that applies permutations to the input and output dimensions of a weight matrix. Mathematically, for a layer $Y = \sigma(WX + B)$, they introduce permutations $\alpha$ and $\beta$ such that the computation becomes:
$$Y[\beta] = \sigma(W[\alpha; \beta]X[\alpha] + B[\beta])$$
By reordering the indices, they cluster weights with small magnitudes into contiguous blocks. Once clustered, these blocks can be pruned using standard block sparsity techniques, which GPUs can accelerate efficiently using libraries like blocksparse.
To find the optimal permutations, the authors use an iterative approach similar to the Expectation-Maximization (EM) algorithm:
- E-Step: Fix the permutations and find the best pruning mask.
- M-Step: Fix the mask and find the best permutations to minimize the "energy" (norm) of the weights remaining in the pruned blocks.
To make this computationally feasible for massive layers (like the 25,088-input FC layer in VGG16), they optimized the reordering logic to reuse intermediate results, reducing the complexity of the inner loop from $O(n^2)$ to $O(n)$.
Key Insights
- Permutation is "Cheap": Reordering dimensions is essentially a data-movement operation. In a deep network, the output permutation of one layer can often be merged with the input permutation of the next, meaning the runtime overhead is negligible (measured at only ~4% of total computation time).
- The 32x32 Sweet Spot: The paper demonstrates that on modern GPUs, block sizes smaller than 32x32 fail to provide practical speedups. TETRIS allows the use of these larger, hardware-efficient blocks without the massive accuracy penalty usually associated with such coarse granularity.
- Orthogonality: The reordering method is "orthogonal" to the pruning criteria. While the authors used L1-norm block pruning as a case study, the reordering logic could theoretically be applied to other structured patterns like row or channel pruning.
Key Results
The authors evaluated their method on three standard benchmarks: MNIST (LeNet), CIFAR-10 (VGG14), and ImageNet (VGG16).
- Speedup: On VGG16 (ImageNet), TETRIS achieved a 2.35x speedup over the dense baseline. Crucially, as seen in the scaling charts, the speedup was nearly proportional to the sparsity for larger block sizes—a feat rarely achieved with irregular pruning.
- Accuracy: Without reordering, increasing block size to 32x32 causes accuracy to plummet. With TETRIS reordering, the accuracy drop is significantly mitigated. For example, on ImageNet, the accuracy drop was reduced from a range of 2.3%–6.0% (standard block pruning) down to just 0.1%–2.4% using TETRIS.
- Efficiency: On the VGG14/CIFAR-10 model, they achieved a 3x speedup, and on LeNet/MNIST, they reached a 10x speedup.
Limitations and Future Work
- Scope of Architectures: The paper focuses heavily on VGG-style architectures. While these are standard benchmarks, it remains to be seen how reordering performs on more complex structures like Residual Networks (ResNets) where skip connections might constrain how much you can permute dimensions across layers.
- Automation: The authors used a uniform pruning rate for all layers for simplicity. They note that searching for per-layer optimal pruning rates (hyperparameter tuning) could further improve the sparsity-accuracy curve.
- Hardware Specifics: The results are highly dependent on the
blocksparseGPU kernel. Future work could involve developing specialized hardware or more flexible kernels to exploit the specific types of "permuted structures" TETRIS creates.
Summary updated