Theoretical and Empirical Analysis of Sparse Convolution
Authors: Keshvi Tuteja, Yu-Hsiang Tsai, Gregor Olenik, Markus Götz, Achim Streit, Hartwig Anzt, Charlotte Debus
Organizations: Scientific Computing Center, Karlsruhe Institute of Technology, Germany · Technical University of Munich, Germany · Helmholtz AI and Scientific Computing Center, Karlsruhe Institute of Technology, Germany · Chair of Computational Mathematics, Technical University of Munich, University of Tennessee, Germany, USA
Deep neural networks for image processing are increasingly deployed on resource-constrained edge devices such as drones, medical systems, and smartphones, where limited computational resources and memory bandwidth pose significant challenges for efficient inference. Pruning during training often produces highly sparse convolutional kernels, offering the potential to significantly reduce computation and memory requirements. However, exploiting this sparsity efficiently at runtime remains challenging due to irregular memory access patterns and workload imbalance across processing elements. In this work, we investigate the standard convolution with sparse weights and analyze its performance characteristics through roofline analysis, showing that a 3 x 3 sparse convolution achieves an arithmetic intensity of approximately 10 FLOP/byte compared to roughly 96 FLOP/byte for its dense counterpart. We propose techniques for an efficient sparse convolution at high sparsities. Preliminary results demonstrate that our approach achieves upto 1.65x speedup as compared to dense convolution on NVIDIA A100 and upto 1.52x on NVIDIA Jetson Nano (Tegra X1) , motivating further exploration of direct convolution as a practical path to efficient sparse inference on modern accelerators/edge devices.
Figures & tables
Figure 1. Sparse convolution with sparse weights. Here, the input image has 3 input channels (IC), output image has 2 output channels (OC). OC denotes the number of output channels, with each output channel generated using a distinct set of convolutional kernels spanning all input channels. The convolution filter has a 3x3 weight matrix for each OC and IC.
Sparsity
90
91
92
93
94
95
96
97
98
AI
9.6
8.6
7.7
6.7
5.7
4.8
3.8
2.9
1.9
Table 1. Arithmetic intensity (FLOP/byte) for varying weight sparsities.
Output Channels (OC)
IC
32
64
128
256
512
1
1.0 ×
1.0 ×
1.0 ×
1.0 ×
1.0 ×
16
1.8 ×
2.2 ×
2.5 ×
2.6 ×
2.7 ×
32
2.8 ×
3.7 ×
4.4 ×
4.9 ×
5.0 ×
64
3.7 ×
5.0 ×
5.0 ×
5.0 ×
5.0 ×
128
4.4 ×
5.0 ×
5.0 ×
5.0 ×
5.0 ×
Table 2. Theoretical speedup of sparse direct convolution over Winograd dense convolution on NVIDIA A100. K=3 , H=W=256 , N=32 , S=0.9 .
Output Channels (OC)
IC
16
24
32
40
48
1
1.0 ×
1.0 ×
1.0 ×
1.0 ×
1.0 ×
8
1.3 ×
1.5 ×
1.6 ×
1.6 ×
1.7 ×
16
2.0 ×
2.3 ×
2.6 ×
2.8 ×
2.9 ×
24
2.3 ×
3.0 ×
3.3 ×
3.7 ×
4.0 ×
32
2.6 ×
3.3 ×
4.0 ×
4.3 ×
4.7 ×
Table 3. Theoretical speedup of sparse direct convolution over Winograd dense convolution on Jetson Nano (Tegra X1). K=3 , H=W=128 , N=8 , S=0.9 .
Figure 2. Roofline model for sparse convolution on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1)
Figure 4. Each nonzero entry is encoded into a 32-bit packed word containing the FP16 weight value together with the input-channel index ( ic ) and kernel offsets ( px,py ). This layout enables aligned and coalesced memory accesses, allowing packed weights along with its indices to be fetched with a single 32-bit global memory transaction. Since sparse convolution is primarily memory bound, reducing memory traffic and improving load efficiency are critical for achieving high performance.
Figure 5. Speedup relative to PyTorch for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: H=W=256 , N=32 , IC=32 for NVIDIA A100 and H=W=128 , N=8 , IC=16 for Jetson Nano
Figure 6. Execution times for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: H=W=256 , N=32 , IC=32 for NVIDIA A100 and H=W=128 , N=8 , IC=16 for Jetson Nano
Figure 7. Performance for varying sparsities on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1)
Figure 8. Maximum absolute error for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: H=W=256 , N=32 , IC=32 for NVIDIA A100 and H=W=128 , N=8 , IC=16 for Jetson Nano