Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks

Abstract

Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. In this work, we first suggest a new measure called mask-diversity which correlates with the expected accuracy of the different types of structural pruning. We focus on the recently suggested N:M fine-grained block sparsity mask, in which for each block of M weights, we have at least N zeros. While N:M fine-grained block sparsity allows acceleration in actual modern hardware, it can be used only to accelerate the inference phase. In order to allow for similar accelerations in the training phase, we suggest a novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the error backward can also be accelerated. We formulate the problem of finding the optimal transposable-mask as a minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest a 2x speed-up in the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching between different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N:M fine-grained block sparsity model with little to no training. A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.

References in corpus (20)

• Distilling the Knowledge in a Neural Network
• Language Models are Few-Shot Learners
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
• Rethinking the Value of Network Pruning
• SNIP: Single-shot Network Pruning based on Connection Sensitivity
• Scalable Training of Artificial Neural Networks with Adaptive Sparse Connectivity inspired by Network Science
• Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity
• Scalable Methods for 8-bit Training of Neural Networks
• Sparse Networks from Scratch: Faster Training without Losing Performance
• Comparing Rewinding and Fine-tuning in Neural Network Pruning
• Deep Rewiring: Training very sparse deep networks
• Post-training 4-bit quantization of convolution networks for rapid-deployment
• Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization
• CondenseNet: An Efficient DenseNet using Learned Group Convolutions
• Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch
• Improving Post Training Neural Quantization: Layer-wise Calibration and Integer Programming
• Fighting Quantization Bias With Bias
• Sparse Systolic Tensor Array for Efficient CNN Hardware Acceleration
• Search Spaces for Neural Model Training

Cited by in corpus (4)

• SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification
• Accelerating Sparse Deep Neural Networks
• Sparse Training via Boosting Pruning Plasticity with Neuroregeneration
• Search Spaces for Neural Model Training