Channel Permutations for N:M Sparsity

Jeff Pool, Chong YuNeurIPS 2021 · OpenReview

TL;DR

N:M structured sparsity offers massive hardware-accelerated speedups on modern GPUs, but pruning can significantly degrade the accuracy of small, efficient models. This paper introduces a zero-overhead "channel permutation" technique that rearranges weight matrices offline to preserve the most important weights during pruning. By finding the optimal channel order, the authors recover—and sometimes even improve—the accuracy of sparse networks without any change to inference run-time.

The Challenge of 2:4 Structured Sparsity

To make Deep Neural Networks (DNNs) faster, researchers often use "pruning" to remove unnecessary weights. A particularly effective form is 2:4 structured sparsity, where hardware (like NVIDIA’s Ampere architecture) expects exactly two out of every four consecutive weights to be zero.

The problem is that this "2:4 constraint" is rigid. In small, parameter-efficient networks (like MobileNet or SqueezeNet), the most important weights might be clustered together. If three high-value weights fall into the same group of four, the 2:4 rule forces you to kill at least one of them, leading to a permanent loss of information that fine-tuning cannot always fix.

By permuting the columns (channels), high-magnitude weights are redistributed, allowing more of them to survive the 2:4 pruning process.

The authors realized that while the values of the weights are fixed, their order along the channel dimension is often arbitrary.

Methods: Permuting for Preservation

The core idea is to permute the channels of a weight matrix so that the "heavy" weights are distributed across different groups of four, allowing them to survive the 2:4 pruning process.

  1. Permutations Across Layers: The authors exploit a fundamental property of matrix multiplication: if you swap the order of input channels in Layer $i$, you can maintain the exact same output by swapping the order of the output channels in Layer $i-1$. This allows them to "reorder" the network offline. When the model is deployed, the weights are simply stored in this new order, resulting in zero computational overhead at inference time.
  2. The Efficacy Metric: To avoid training a model for every possible permutation, they developed a quality metric called efficacy. It measures how much total weight magnitude is preserved by a specific permutation compared to a theoretical maximum.
  3. Search Algorithms: Finding the optimal permutation is a combinatorial nightmare (just 16 channels yield over 20 trillion possibilities). The authors propose a mix of strategies:
  4. Greedy Search: Iteratively swapping channels to see what improves the preserved magnitude.
  5. Bounded Regressions: To escape local minima, the algorithm intentionally takes "random steps" and then re-optimizes.
  6. Narrow, Deep Search: Exhaustively searching small sub-groups of channels to find the best local arrangement.

Key Insights and Results

The researchers evaluated their methods primarily on the ImageNet dataset, testing architectures ranging from efficient models (SqueezeNet, MobileNet) to standard models (ResNet-50).

  • Order is a Hidden Hyperparameter: We usually treat the order of channels in a convolutional layer as fixed, but for structured sparsity, it is a crucial degree of freedom that can be optimized.
  • Small Models Benefit Most: Large models like ResNet-50 have enough redundancy to "absorb" the damage of 2:4 pruning. Small models are "brittle"; for them, channel permutation is the difference between a usable sparse model and a broken one.
  • Magnitude as a Proxy: While weight magnitude isn't a perfect proxy for "importance," the authors show a very strong monotonic correlation between their "efficacy" metric and final fine-tuned accuracy.
There is a strong correlation between the weighted average efficacy of a permutation and the resulting accuracy improvement in models like SqueezeNet and EfficientNet.
  • Accuracy Recovery: In SqueezeNet v1.0, a standard 2:4 prune drops accuracy by 4.01%. Using channel permutations, the model actually gained 0.60% accuracy over the original dense baseline. Across every model tested, the permuted approach significantly outperformed default 2:4 pruning.
  • Negligible Cost: The search for the best permutation is extremely fast. For most models, the search took about one minute on a single GPU, representing less than 0.1% of the total training and fine-tuning time.

Limitations and Future Work

  • Heuristic Nature: The approach relies on the heuristic that preserving weight magnitude preserves accuracy. While it works well in practice, other importance metrics might perform even better.
  • Input Layers: The very first layer of a network cannot be permuted using this "layer-to-layer" trick because there is no previous layer to adjust. However, input layers are usually small (e.g., 3 RGB channels) and aren't typically pruned anyway.
  • Future Directions: The authors suggest integrating this permutation search directly into the training process ("training from scratch") rather than just using it as a post-processing step for pre-trained models. They also see potential in applying this to "transposable" sparsity, where the 2:4 constraint must be met for both forward and backward passes.

Summary updated

Abstract

We introduce channel permutations as a method to maximize the accuracy of N:M sparse networks. N:M sparsity requires N out of M consecutive elements to be zero and has been shown to maintain accuracy for many models and tasks with a simple prune and fine-tune workflow. By permuting weight matrices along their channel dimension and adjusting the surrounding layers appropriately, we demonstrate accuracy recovery for even small, parameter-efficient networks, without affecting inference run-time. We also present both a quality metric to simplify judging permutations as well as efficient methods to search for high-quality permutations, including two optimizations to escape local minima. Finally, we share an ablation study to show the importance of each part of our search algorithm, experimental results showing correlation between our quality metric and final network accuracy, improved sparse network accuracy using our techniques with insignificant overhead to training time, and the transformation of unstructured to structured sparse workloads. Code to use these techniques when generating a 2:4 sparse network is available at https://github.com/NVIDIA/apex/tree/master/apex/contrib/sparsity.
BibTeX
@inproceedings{pool2021channel,
  author = {Jeff Pool and Chong Yu},
  title = {{Channel Permutations for N:M Sparsity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=WAO1STUPWPP},
}
Figure