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
Inference of standard convolutional neural networks (CNNs) on FPGAs often incurs high latency and a long initiation interval due to the deep nested loops required to densely convolve every input pixel regardless of its feature value. However, input features can be spatially sparse in some image data, where semantic information may occupy only a small fraction of the pixels and most computation would be wasted on empty regions. In this work, we introduce SparsePixels, a framework that implements sparse convolution on FPGAs by selectively retaining and computing on a small subset of active input pixels while ignoring the rest, reducing the per-layer compute from O(HWK2CinCout) to O(n2CinCout) and the storage from O(HWC) to O(nC) when n2≪HW. Because computation always runs over a single pre-specified pixel budget that is frozen at synthesis, the inference latency is data-independent and constant at runtime. We show that, for identifying neutrino interactions in naturally sparse LArTPC images with 4k pixels, a standard CNN with a compact size of 4k parameters incurs an inference latency of 48.665 μs on an FPGA, whereas a sparse CNN of the same base architecture, computing on less than 1% of the input pixels, achieves a ×73 speedup to 0.665 μs with resource utilization well within on-chip budgets, trading only a small percent-level performance loss. This work aims to benefit future algorithm development for efficient data readout in modern experiments with strict latency requirements of microseconds or below.
Ho Fung Tsoi, Dylan Rankin, Vladimir Loncar +1
University of Pennsylvania, USA · Institute of Physics Belgrade, Serbia · Massachusetts Institute of Technology, USA +1
Modern CNNs' high computational demands hinder edge deployment, as traditional hard'' sparsity (skipping mathematical zeros) loses effectiveness in deep layers or with smooth activations like Tanh. We propose a soft sparsity'' paradigm using a hardware efficient Most Significant Bit (MSB) proxy to skip negligible non-zero multiplications. Integrated as a custom RISC-V instruction and evaluated on LeNet-5 (MNIST), this method reduces ReLU MACs by 88.42% and Tanh MACs by 74.87% with zero accuracy loss--outperforming zero-skipping by 5x. By clock-gating inactive multipliers, we estimate power savings of 35.2% for ReLU and 29.96% for Tanh. While memory access makes power reduction sub-linear to operation savings, this approach significantly optimizes resource-constrained inference.
Vishal Shashidhar, Anupam Kumari, Roy P Paily
Department of Electronics and Electrical Engineering, Indian Institute of Technology Guwahati
Fine-grained weight pruning and activation sparsification have emerged as effective approaches for reducing the compute and memory cost of inference for Transformer models. In the moderate-sparsity regime, Gustavson's dataflow provides a natural execution model for exploiting both activation and weight sparsity on vector processors through metadata-driven indexed accumulation. However, existing RVV architectures lack native support for this pattern, forcing kernels to rely on software index decoding and L1-backed indexed memory operations that keep sparse tensor contractions far below their roofline performance bound. We present Ventaglio, a runtime-configurable sparse execution unit coupled with RVV ISA extensions that drives sparse tensor contractions toward their roofline through indexed gather-accumulate-scatter support. Integrated into an open-source vector processing cluster and implemented in 12nm FinFET, Ventaglio accelerates sparse tensor contraction kernels by 6.9–7.4× over optimized RVV baselines, with only 3.1% area overhead for a cluster of tightly-L1 coupled vector processing elements. We build a performance-accurate instruction-level model of the Ventaglio extension, calibrate it against RTL implementation, and leverage it for scale-out performance analysis on a large 4×4 multi-cluster system. Using a DuoGPT-pruned LLaMA-3-8B model with practical 40–60% dual sparsity, Ventaglio achieves 2.40–5.25× and 2.06–3.16× speedup over dense baselines during prefill and autoregressive decoding, respectively.
Bowen Wang, Chi Zhang, Diyou Shen +3
*IIS, ETH Zürich, Switzerland · ‡Computing Systems Lab, Huawei, Switzerland · †DEI, Universit`a di Bologna, Italy