arXiv CS open access

Theoretical and Empirical Analysis of Sparse Convolution

Keshvi Tuteja et al. · arxiv_cs

arXiv CS · Papers

cloud distributed-computing parallel-computing

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 pro

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Theoretical and Empirical Analysis of Sparse Convolution Keshvi Tuteja

Scientific Computing Center, Karlsruhe Institute of Technology Germany keshvi.tuteja@kit.edu

arXiv:2611.17212v1 [cs.PF] 12 Nov 2026

Markus Götz

Helmholtz AI and Scientific Computing Center, Karlsruhe Institute of Technology Germany markus.goetz@kit.edu

Yu-Hsiang Tsai

Technical University of Munich Germany yu-hsiang.tsai@tum.de

Achim Streit

Scientific Computing Center, Karlsruhe Institute of Technology Germany achim.streit@kit.edu

Gregor Olenik

Technical University of Munich Germany gregor.olenik@tum.de

Hartwig Anzt

Chair of Computational Mathematics, Technical University of Munich, University of Tennessee Germany, USA hartwig.anzt@tum.de

Charlotte Debus

Scientific Computing Center, Karlsruhe Institute of Technology Germany charlotte.debus@kit.edu

Abstract 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 × 3 sparse convolution achieves an arithmetic intensity of approximately 10 FLOP/byte compared to ∼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.65× speedup as compared to dense convolution on NVIDIA A100 and upto 1.52× 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.

CCS Concepts • Computing methodologies → Parallel algorithms.

Keywords Sparse Convolution, GPU Acceleration, Performance Modeling, Roofline Analysis, Sparse Neural Networks, Edge Computing

Introduction

Convolutional neural networks (CNNs) [1] have become foundational to a wide range of applications, including medical imaging,

autonomous driving, robotics, surveillance, and mobile vision systems. The growing demand for real time, on device intelligence has shifted many CNN workloads from data centers to edge platforms, where processing data locally reduces latency, communication costs, and privacy concerns. However, edge devices such as embedded GPUs, FPGAs, and custom ASICs provide only limited memory capacity, power budgets and memory bandwidth [2]. This makes computational efficiency and low memory consumption essential. In many image processing tasks on edge deployment scenarios, model weights reside permanently in device memory while input feature maps, for example in the form of input images, are streamed at runtime. Due to the limited memory capacity of edge devices, memory footprint reduction by storing only non-zero model weights explicitly via sparse matrix formats becomes an attractive approach for reducing memory traffic and improving inference efficiency. One of the most promising strategies for reducing the memory footprint and computational cost of CNNs on resource-constrained hardware is weight sparsification [3, 4]. By pruning a large fraction of the learned weights to zero, sparse networks can substantially reduce both floating-point operations (FLOPs) and memory traffic during inference [5, 6]. Consequently, recent research has focused on pruning networks to extreme sparsity levels, typically between 90% and 99% [7]. However, translating these theoretical savings into practical performance gains remains challenging because sparse implementations incur additional execution overhead. In particular, irregular sparsity patterns require indirect accesses to locate non-zero weights and produce uneven workloads across processing elements, resulting in load imbalance and reduced memory efficiency [8, 9]. For a sparse convolution (sparse weights, dense images), We identify two principal obstacles to high performance: (1) inefficient sparse weight access, whereby non-contiguous weight layouts generate memory transactions that underutilize memory bandwidth, and

Conference’17, July 2017, Washington, DC, USA

(2) workload imbalance, arising because different output channels or spatial tiles encounter varying numbers of non-zero weights, causing some processing elements to idle while others remain saturated. We propose a packed weight representation that addresses the first challenge by enabling coalesced, single-transaction access and improved cache utilization, together with a thread mapping strategy that helps equalize load across threads for the second challenge. This paper makes three contributions: • A roofline analysis showing that direct sparse convolution at practical sparsity levels operates at or near the memorybandwidth bound regime of modern accelerators, motivating our kernel design. • A sparse convolution kernel utilizing compact 32-bit packed weight format combined with a shared-memory tiling for better memory bandwidth utilization. • An evaluation on both an NVIDIA A100 and an edge device: Jetson Nano (Tegra X1) showing consistent speedups over PyTorch’s dense convolution baseline, reaching up to 1.65× on the A100 and upto 1.52× on NVIDIA Tegra X1.

Related Work

Convolution kernels can broadly be categorized into three algorithmic families, each with distinct performance trade-offs. The first family relies on Im2col-based transformations [10], which reshape and rearrange the input tensor into a matrix so that convolution reduces to a general matrix–matrix multiply (GEMM) [11] or a sparse matrix–vector product (SpMV)/ sparse matrix–matrix product (SpMM) [12]. There have also been efforts in improving sparse convolution by improving sparse operations (SpMV/SpMM) [13]. While this approach maps well onto highly tuned BLAS libraries, it typically replicates input data, inflating memory consumption by a factor of ≈ 𝐾 2 , where 𝐾 is the kernel size. Therefore a 3 × 3 convolution would inflate memory consumption by 9× and a 5 × 5 by 25× and so on. These approaches also fail to fully exploit the data reuse hierarchy available in modern GPU caches and scratchpad memories. While there has been research in the direction of better memory usage in such convolutions [14], it remains limited to dense convolution [15]. [16] also discusses and implements a sparse convolution which is based on sparse matrix-dense matrix multiplication but this only supports execution on CPUs. The second family employs transformation based convolution such as the Fast Fourier Transform (FFT) and the Winograd algorithm. FFT-based convolution is suitable for large filters but suffers significant overhead for the small kernel sizes (e.g., 3 × 3, 5 × 5, the typical kernel sizes used in deep learning). Therefore, it is mainly used for signal processing tasks rather than deep learning. Another approach to compute convolution is through Winograd minimal filtering algorithm [17]. Dense 3 × 3 convolutions are typically accelerated using Winograd algorithms, which reduce the number of floating-point multiplications through small domain transforms [18]. The widely used 𝐹 (2 × 2, 3 × 3) Winograd algorithm decreases the multiplication count by approximately 2.25× compared to direct convolution [19], making it the preferred implementation for small dense convolutions in libraries such as cuDNN. However, Winograd relies on dense transform matrices and dense elementwise multiplications in the transformed domain. When applied to

Tuteja et al.

highly sparse convolution kernels, these transformations destroy the original sparsity pattern and introduce additional arithmetic and memory overhead, substantially reducing the potential benefits of weight pruning. Consequently, the next family: direct sparse convolution remains a more suitable approach for exploiting high levels of unstructured sparsity. The third family performs direct convolution, sliding the kernel across the input without any data transformation. Direct convolution preserves the full locality of the computation and avoids the overhead of format conversion, making it a natural fit for sparse convolution kernels.

Theoretical Background

Standard multi-channel image convolution is represented as: 𝐶ℎ,𝑤,𝑜𝑐 =

𝐼𝐶 −1 ∑︁

min(𝐾ℎ −1,𝐻 ∑︁+𝑃ℎ −ℎ−1)

min(𝐾𝑤 −1,𝑊 ∑︁+𝑃𝑤 −𝑤−1)

𝑖𝑐=0

𝑘ℎ =max(0,𝑃ℎ −ℎ)

𝑘 𝑤 =max(0,𝑃 𝑤 −𝑤 )

(1)

𝑋ℎ+𝑘ℎ −𝑃ℎ , 𝑤+𝑘 𝑤 −𝑃𝑤 , 𝑖𝑐 · W𝑘ℎ ,𝑘 𝑤 ,𝑖𝑐,𝑜𝑐 𝐻𝑜𝑢𝑡 =

𝐻 + 2𝑃ℎ − 𝐾ℎ +1, 𝑆ℎ

𝑊𝑜𝑢𝑡 =

𝑊 + 2𝑃 𝑤 − 𝐾𝑤 +1 (2) 𝑆𝑤

where: • 𝐶 is the output image with multiple channels, defined on ℎ ∈ [0, 𝐻𝑜𝑢𝑡 ), 𝑤 ∈ [0,𝑊𝑜𝑢𝑡 ), • 𝑆ℎ , 𝑆 𝑤 denote the stride in each spatial dimension (set to 1 for the unstrided case used above), • 𝑖𝑐 and 𝑜𝑐 denote the number of input and output channels, • 𝐾ℎ , 𝐾𝑤 denote the kernel height and width, • 𝑃ℎ , 𝑃 𝑤 denote the (symmetric) zero-padding applied to 𝑋 in each spatial dimension, • 𝑋 is the input image with multiple channels, defined only on ℎ ∈ [0, 𝐻 ), 𝑤 ∈ [0,𝑊 ), • W are the convolution weights, • ℎ and 𝑤 are the output coordinates, ℎ ∈ [0, 𝐻𝑜𝑢𝑡 ), 𝑤 ∈ [0,𝑊𝑜𝑢𝑡 ). In eq. (1), one output element 𝐶ℎ,𝑤,𝑜𝑐 is computed by accumulating contributions from all input channels and all kernel positions, restricted to the valid summation range so that 𝑋 is never indexed outside its defined domain [0, 𝐻 ) × [0,𝑊 ). Unlike dense convolution, sparse convolution only iterates over nonzero weights, thereby reducing memory traffic and arithmetic operations. Sparse convolution can therefore be written as: ∑︁ 𝐶ℎ,𝑤,𝑜𝑐 = 𝑣 𝑗 · 𝑋 Δ ( 𝑗 ) , Δ ( 𝑗 ) , 𝑖𝑐 ( 𝑗 ) (3) 𝑗 ∈ N (𝑜𝑐,ℎ,𝑤 )

ℎ

𝑤

where Δℎ( 𝑗 ) = ℎ + 𝑝 𝑦( 𝑗 ) − 𝑃ℎ and Δ𝑤( 𝑗 ) = 𝑤 + 𝑝𝑥( 𝑗 ) − 𝑃 𝑤 denote the padding-shifted input coordinates addressed by nonzero weight 𝑗, and: • N (𝑜𝑐, ℎ, 𝑤) = { 𝑗 ∈ N (𝑜𝑐) : 0 ≤ Δℎ( 𝑗 ) < 𝐻, 0 ≤ Δ𝑤( 𝑗 ) < 𝑊 } restricts 𝑜𝑐’s nonzero weights to those whose input position lies within the valid image bounds at this output location, • N (𝑜𝑐) denotes the full set of nonzero weights associated with output channel 𝑜𝑐, • 𝑣 𝑗 is the value of the 𝑗-th nonzero weight,

Theoretical and Empirical Analysis of Sparse Convolution

Conference’17, July 2017, Washington, DC, USA

• 𝑋 is the input image with multiple channels, defined only on ℎ ∈ [0, 𝐻 ), 𝑤 ∈ [0,𝑊 ), • 𝑖𝑐 ( 𝑗 ) is the corresponding input channel, • (𝑝𝑥( 𝑗 ) , 𝑝 𝑦( 𝑗 ) ) are the kernel offsets of the 𝑗-th nonzero weight, • 𝑃ℎ , 𝑃 𝑤 denote the symmetric zero-padding applied to 𝑋 , matching Eq. 1.

Table 1: Arithmetic intensity (FLOP/byte) for varying weight sparsities. 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

The sparse convolution is visually represented in fig. 1.

The corresponding computational cost is

Roofline Modelling

To understand the performance characteristics of sparse and dense convolution, we apply roofline modeling [20] to characterize whether each formulation is compute-bound or memory-bound on the target hardware. The resulting analysis guides the design of our sparse convolution kernel by identifying the dominant performance bottleneck. A key metric in roofline modelling is Arithmetic intensity (AI). AI is defined as the ratio of floating-point operations done per byte of memory accessed: AI =

𝐶𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛[FLOPs] . 𝐶𝑜𝑚𝑚𝑢𝑛𝑖𝑐𝑎𝑡𝑜𝑛[Bytes]

FLOPsdense = 2 𝑁 𝐻 out𝑊out 𝑂𝐶 𝐾 2 𝐼𝐶,

where the factor of two accounts for one multiply and one addition per multiply accumulate operation. Sparse convolution. Assume an unstructured weight sparsity of 𝑆 ∈ [0, 1), such that only a fraction (1 − 𝑆) of the weights are retained. Since the input and output activations remain dense, only the weight tensor is compressed. The resulting memory traffic becomes

(4)

For example, for the NVIDIA A100 GPU with a peak floatingpoint throughput of 19.5 TFLOP/s and a memory bandwidth of 2 TB/s [21], the FP32 ridge point is approximately 9.75 FLOP/byte. Kernels with arithmetic intensity below this threshold are memorybound, and those above are compute-bound. Edge accelerators shift this ridge point towards higher values: the Jetson AGX Orin (64GB), with 5.32 TFLOP/s FP32 and 204.8 GB/s of bandwidth, has a ridge point of approximately 25.98 FLOP/byte which is more than 2.5× that of the A100, while the Jetson Orin Nano (8GB), at 5.0 TFLOP/s and only 68 GB/s, reaches approximately 73.53 FLOP/byte, nearly an order of magnitude higher than the A100. In contrast, the original Jetson Nano (Tegra X1), at 0.236 TFLOP/s and 25.6 GB/s, lands at approximately 9.22 FLOP/byte: almost identical to the A100’s ridge point despite roughly 80× lower absolute throughput. This demonstrates that the ridge point is governed by the ratio of peak compute performance to memory bandwidth rather than their absolute values. Consequently, a kernel with fixed arithmetic intensity may be compute-bound on one architecture but memory-bound on another, even if the latter offers higher peak performance. Since edge devices typically have higher ridge points, more kernels fall into the memory-bound regime, making bandwidth optimization increasingly important. From eq. (4), we calculate the arithmetic intensity by estimating both the communication and the computational cost of dense and sparse convolutions. Consider a convolution with batch size 𝑁 , input channels 𝐼𝐶, output channels 𝑂𝐶, kernel size 𝐾 × 𝐾, and output spatial dimensions 𝐻 out ×𝑊out . Let 𝑃 denote the size of each floating-point value in bytes. Dense convolution. The memory traffic/communication cost consists of reading the input image/s, reading the weight tensor, and writing the output image/s: Memdense = 𝑁 𝐻𝑊 · 𝐼𝐶 + 𝐾 2 𝐼𝐶 𝑂𝐶 (5) + 𝐻 out𝑊out 𝑁 𝑂𝐶 𝑃

(6)

Memsparse = (𝑁 𝐻𝑊 · 𝐼𝐶 + 𝑁 𝐻 out𝑊out 𝑂𝐶) 𝑃 + (1 − 𝑆)𝐾 2 𝐼𝐶 𝑂𝐶 (𝑃 + 𝑃idx ) ,

(7)

where 𝑃idx denotes the storage required for the index metadata associated with each nonzero weight. In our implementation, each nonzero weight is stored as a 16-bit FP16 value together with 16 bits of indexing information in a single 32-bit packed entry, requiring 4 bytes per nonzero (𝑃 = 2 bytes and 𝑃idx = 2 bytes). During convolution, the FP16 weights are converted to FP32 and accumulated in FP32 registers without additional per-nonzero accumulator storage. The computational cost decreases proportionally with the number of retained weights: FLOPssparse = 2 𝑁 𝐻 out𝑊out 𝑂𝐶 (1 − 𝑆) 𝐾 2 𝐼𝐶.

4.1

(8)

Impact of Sparsity

Using eq. (7) and eq. (8), the arithmetic intensities for direct convolution across varying sparsities were computed. The values of arithmetic intensities for sparsities 𝑆 ∈ [0.90, 0.98] with increments of 0.01 are reported in table 1. A fixed configuration of 𝐻 = 𝑊 = 256, 𝐼𝐶 = 32, 𝑂𝐶 = 64, 𝑁 = 32 and 𝐾 = 3 was used. The corresponding roofline plots for NVIDIA A100 and NVIDIA Jetson Nano (Tegra X1) are presented in figures 2a and 2b respectively. The corresponding arithmetic intensity for dense convolution is around 96 (computed using eq. (5) and eq. (6)), which is about an order of magnitude larger than the arithmetic intensity values for the sparse convolution. Dense convolution is strongly compute-bound with AI exceeding the ridge point at all the sparsities in table 1. Sparse convolution at 90% sparsity reduces AI by approximately 10×, which is consistent with the (1−𝑆) reduction in FLOPs. The 𝑆 = 0.90 sparse case with an AI of ∼9.6 FLOP/byte, falls right at the ridge point of our target GPU. This means that even the smallest inefficiencies in memory access patterns such as uncoalesced loads caused by irregular sparsity structure, will push the kernel below the ridge point and into the memory-bandwidth bound regime. The rest of the values fall below the ridge point, making memoryaccesses the main bottleneck for the sparse convolution.

Conference’17, July 2017, Washington, DC, USA

Tuteja et al.

𝐼𝐶 = 0

𝐼𝐶 = 1

𝐼𝐶 = 2

Input channels

Weights for 𝑂𝐶 = 0

𝐼𝐶 = 0

Weights for 𝑂𝐶 = 1

𝐼𝐶 = 1

𝐼𝐶 = 2

𝐼𝐶 = 0

𝐼𝐶 = 1

𝐼𝐶 = 2

nonzero weight

Sparse filters

Output channels

𝑂𝐶 = 0

zero weight

𝑂𝐶 = 1

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.

4.2

Roofline Comparison: Direct vs. Winograd

Since Winograd convolution is the standard high-performance baseline for small kernel sizes and is used by major deep learning frameworks, we also compare sparse direct convolution against Winograd based dense convolution. As already discussed earlier, Winograd based algorithms can reduce the number of operations up to and higher than roughly 2𝑥. Table 2 and 3 report the theoretical time based speedup of sparse direct convolution over Winograd dense convolution for varying input and output channel counts for NVIDIA A100 and NVIDIA Jetson nano (Tegra X1) respectively. The analysis was done for 𝐾=3, 𝐻 =𝑊 =256, 𝑁 =32, and 𝑆=0.9 and assuming a reduction in operations by 1.5𝑥. This analysis was done by calculating the execution time for each of those kernels using Roofline analysis for NVIDIA A100. Here, we assumed, execution time to be 𝑚𝑎𝑥 (𝑇𝑐𝑜𝑚𝑝 ,𝑇𝑐𝑜𝑚𝑚 ). Table 2: Theoretical speedup of sparse direct convolution over Winograd dense convolution on NVIDIA A100. 𝐾=3, 𝐻 =𝑊 =256, 𝑁 =32, 𝑆=0.9. Output Channels (OC) IC

128

256

512

1 16 32 64 128

1.0× 1.8× 2.8× 3.7× 4.4×

1.0× 2.2× 3.7× 5.0× 5.0×

1.0× 2.5× 4.4× 5.0× 5.0×

1.0× 2.6× 4.9× 5.0× 5.0×

1.0× 2.7× 5.0× 5.0× 5.0×

Table 3: Theoretical speedup of sparse direct convolution over Winograd dense convolution on Jetson Nano (Tegra X1). 𝐾=3, 𝐻 =𝑊 =128, 𝑁 =8, 𝑆=0.9. Output Channels (OC) IC

1 8 16 24 32

1.0× 1.3× 2.0× 2.3× 2.6×

1.0× 1.5× 2.3× 3.0× 3.3×

1.0× 1.6× 2.6× 3.3× 4.0×

1.0× 1.6× 2.8× 3.7× 4.3×

1.0× 1.7× 2.9× 4.0× 4.7×

At 𝐼𝐶=1, no speedup is achieved because both formulations are memory bound and the execution time is dominated by loading the input and output feature maps rather than the weights at large batch sizes. As 𝐼𝐶 increases, the weight tensor grows and the sparsity savings become significant, yielding a consistent theoretical speedup of approximately 4.5–4.8× over Winograd for channel counts representative of practical CNN layers. These results confirm that sparse direct convolution is a theoretically compelling alternative to Winograd for high-sparsity regimes, provided that the memory access irregularity introduced by sparse weight formats can be adequately managed. But for this analysis, we take the optimistic estimate for speedup. It is calculated assuming that the communication and computation completely overlap with each other. According to prior studies, profiling of cuSPARSE’s csrmv (compressed sparse row matrix-vector multiplication) kernel on an

Performance (GFLOP/s)

104

103

102 Higher sparsity

Conference’17, July 2017, Washington, DC, USA

Comm: 2.0 TB/s Comp: 19.5 TFLOP/s S: 90% S: 91% S: 92% S: 93% S: 94% S: 95% S: 96% S: 97% S: 98%

101 10 3 10 2 10 1 100 101 102 103

Arithmetic Intensity (FLOPs/Byte)

Performance (GFLOP/s)

Theoretical and Empirical Analysis of Sparse Convolution

Comm: 25.6 GB/s Comp: 236 GFLOP/s S: 90% S: 91% S: 92% S: 93% S: 94% S: 95% S: 96% S: 97% S: 98%

102

101

100

Higher sparsity

10 3 10 2 10 1 100

101

102

103

Arithmetic Intensity (FLOPs/Byte)

(a) NVIDIA A100

(b) Jetson Nano

Figure 2: Roofline model for sparse convolution on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) NVIDIA A100 shows memory bandwidth utilization of only 2.9–11.34% for irregular application matrices, versus 67.79–73.67% for dense GEMV (General Matrix-Vector multiplication) on the same hardware, illustrating the gap that pure FLOPs/bytes roofline accounting doesn’t fully explain [22]. Therefore, in practice, it is generally hard to achieve the speedups suggested by roofline model (mentioned in table 2 and table 3 ) for sparse applications.

Packed-Weight Sparse Convolution Kernel

The roofline analysis in Section 4 shows that sparse 3×3 convolution sits at or below the memory bandwidth ridge point for both NVIDIA A100 as well as NVIDIA Tegra X1. Therefore, the bottleneck is not arithmetic but data movement. Realizing the theoretical FLOP and memory savings of sparsity therefore requires mitigating the two obstacles identified in Section 1 directly, rather than simply skipping zero-valued multiplications in an otherwise dense kernel. Our strategy combines three techniques, each targeting a specific source of memory traffic or imbalance. • Shared-memory tiling: (Section 5.1) loads each region of the input feature map from DRAM exactly once per thread block and reuses it across all output channels and rows computed by that block, reducing redundant global memory traffic • Packed weight format: Section 5.3 fuses each nonzero’s value and metadata into a single 32-bit word, so that a single coalesced memory transaction retrieves all the information a thread needs about a non-zero element. independent of sparsity level. • Thread and warp mapping: Strategy in (Section 5.2) distributes output channels across threads within a warp, mitigating obstacle (2), workload imbalance, when sparsity is comparable across channels. Together, these techniques aim to keep the kernel’s realized memory traffic close to the lower bound implied by the roofline model, rather than the inflated traffic that naive sparse indexing

would otherwise incur. Algorithm 1 at the end of this section summarizes how these three techniques compose into the full kernel. Implementation details are explained in the following sections.

5.1

Shared Memory Tiling

The input images are stored in 𝑁 × 𝐼𝐶 × 𝐻 ×𝑊 layout to make this convolution compatible with major deep learning (DL) frameworks. Before computation, each block cooperatively loads the required input tile (a part of an image) into the shared memory. The tile includes the halo region required by the convolution window. For a kernel of size 𝐾, the shared memory tile is larger than the output tile by 𝐾 − 1 rows and columns if 𝑠𝑡𝑟𝑖𝑑𝑒 = 1. This ensures that input tile is not loaded from DRAM multiple times by different threads. The data from the same tile is used for the entire computation block. Input elements outside the feature map boundary are padded with zeros. In lines 1 and 2 in algorithm 1, we determine the corresponding image for each block and thread. The output tile indices (𝑜ℎ 0, 𝑜𝑤 0 ) for a given thread are determined in line 3 and then corresponding input tile is loaded by the entire block cooperatively in lines 4 - 9.

5.2

Thread and Block Organization

The output feature map is divided into spatial tiles as shown in fig. 3. The top grid shows how an output tile is mapped onto a warp. In this illustrative example, each warp computes four output rows and four output columns across all output channels. The actual mapping parameters were selected through an ablation study comparing multiple configurations. Although, we also parallelize over OCs along z-axis. Since a warp constitutes of 32 threads, eight threads collaborate to compute a single output column across multiple OCs and rows. Specifically, thread IDs 0–7 compute output channels 0–7 for the first column in the tile, and then proceed to compute output channels 8–15 (again for the first column in the tile), continuing in the same manner. Likewise, thread IDs 8–15 carry out the same computations for the second output column. This mapping strategy

Conference’17, July 2017, Washington, DC, USA

Tuteja et al.

𝑂𝐶

𝐻 =2

column = 0

column = 1

column = 2

column = 3

𝑜𝑤0

𝑜𝑤1

𝑜𝑤2

𝑜𝑤3

thread _id = 0–7 0

thread _id = 8–15

thread _id = 16–23

thread _id = 24–31

𝑂𝐶

0...7

8 . . . 15

16 . . . 23

24 . . . 31

0...7

8 . . . 15

16 . . . 23

24 . . . 31

time 0

16 lane

ℎ =0

ℎ =1

Figure 3: Mapping of an output tile to a warp. In this example, one warp computes four output columns across two output rows. The warp is partitioned into four groups of eight threads, with each group assigned to one output column. For the first column, threads 0–7 initially compute output channels (OCs) 0–7, before proceeding to OCs 8–15, 16–23, and 24–31 in subsequent steps. Similarly, threads 8–15, 16–23, and 24–31 process the second, third, and fourth output columns, respectively. The same mapping is repeated for every output row assigned to the warp. The number inside each thread box indicates the OC computed by that thread at the corresponding execution step. is applied consistently across all output tiles. Each thread block computes a tile containing several output columns and output rows for all output channels. This mapping ensures that the computation is load-balanced when sparsity per output channel is similar. In lines 10-12 in the algorithm, one determines the corresponding output indices (row, col and output channel). In line 13, each thread loops over multiple OC with step 32/𝐶𝑂𝐿_𝑃𝐸𝑅_𝑊 𝐴𝑅𝑃 as discussed above and as shown in fig. 3

5.3

Sparse Weight Format

Each non-zero weight v, along with its corresponding input channel ic, px and py (respective x and y coordinates in the kernel) is stored as a single 32-bit unsigned integer. The upper 16 bits store the FP16 weight value, bits 15-8 store the input channel index, bits 7-4 store the kernel column offset, and bits 3-0 store the kernel row offset as shown in fig. 4. This is also shown in line 16 of the pseudocode. Sparse convolution filters are transformed into a compact packed representation to improve memory efficiency, especially on resource-constrained devices. This representation allows one 32-bit load to retrieve both the weight value and its metadata. An offset array of length 𝑂𝐶+1 stores the start and end positions of the non-zero weights for each output channel, similar to the CSR format. All convolution arithmetic and accumulation are performed in FP32 using CUDA cores, and output values are stored in FP32. Upon loading a packed entry, the FP16 weight is converted to FP32 before computation.

5.4

Sparse Accumulation

Each thread traverses the non-zero weights belonging to its assigned output channels. For every packed entry, the thread unpacks the weight value, input channel index, and kernel offsets. The corresponding input value is read from shared memory, and the result is accumulated using fused multiply-add (FMA) operations. FMA operations are especially helpful for larger GPUs such as NVIDIA A100 where AI is close to the ridge point as this reduces the number of operations per thread. Since the same weight is reused across multiple output rows, the method reduces repeated global memory accesses as shown in lines 15-20 of algorithm 1.

5.5

Output Write-Back

After accumulation, each thread writes the computed output values back to the output tensor as shown in line 24. Boundary checks are used for partial tiles near the image border. The output tensor is stored in 𝑁 × 𝑂𝐶 × 𝐻 × 𝑊 layout as this is a widely used format and supported by major DL frameworks like PyTorch.

Performance Results and Analysis

We benchmarked our sparse convolution implementation against PyTorch’s dense convolution baseline. To ensure a fair comparison, we developed Python bindings for our implementation using Pybind11 [23] and evaluated both approaches through the Python frontend. The convolution weights were generated using Python’s

Theoretical and Empirical Analysis of Sparse Convolution

Conference’17, July 2017, Washington, DC, USA

Algorithm 1 Sparse Direct Convolution with Packed Weights B

𝐼𝐶 =0 E

.. .

𝐼𝐶 =1

𝐼𝐶 =1 H

Value

𝑜𝑐 = 0 B

𝐼𝐶 =0

𝐼𝐶 =1

𝑜𝑐 =J 1

Offset

Packed

𝑂𝐶 =0

𝑂𝐶 =1

𝑂𝐶 =2

𝐼𝐶 =0

𝑂𝐶 = 0 0

𝐼𝐶 =1

𝑂𝐶 = 1

fp16 weight

[31:16]

[15:8]

[7:4]

[3:0]

Figure 4: Each nonzero entry is encoded into a 32-bit packed word containing the FP16 weight value together with the input-channel index (𝑖𝑐) and kernel offsets (𝑝𝑥, 𝑝𝑦). 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. In the following sections, we present benchmark results for both the NVIDIA A100 GPU and the NVIDIA Jetson Nano.

6.1

NVIDIA A100

Fig. 5a shows the speedup achieved by the proposed sparse convolution implementation relative to PyTorch’s dense convolution for varying sparsity levels and output-channel (OC) configurations on CUDA cores. The experiments were performed with fixed input dimensions of 𝐻 = 𝑊 = 256,

random module with varying sparsity levels. In this work, we report results for sparsity levels ranging from approximately 90% to 98% across different output channels (OC) and sparsities. All benchmarks were conducted using CUDA cores. We evaluated our implementation on two NVIDIA platforms: the NVIDIA A100 GPU on the HoreKa supercomputer and the NVIDIA Jetson Nano (NVIDIA Tegra X1), which represents a more resource constrained edge device. For the NVIDIA A100 experiments, we used Python 3.11 together with CUDA 12.2, loaded via the environment module devel/cuda/12.2 and PyTorch 2.9. The Jetson Nano experiments were conducted using JetPack 4.6, Python 3.6, and PyTorch 1.10. This is the latest software stack for this device. Rather than a limitation of our evaluation, we view this as representative of the deployment reality as it is fairly common for edge devices to be locked to whatever software stack is shipped with them. These software configurations were applied consistently during benchmarking.

𝑂𝐶 = 1

𝐼𝐶 =0 𝑂𝐶 = 0

Require: Packed sparse weights 𝑃, offset array 𝑂 Require: Output dimensions ℎ, 𝑤, number of output channels 𝑂𝐶 Ensure: Output tensor 𝑌 ∈ R𝑁 ×𝑂𝐶 ×ℎ×𝑤 1: for all thread blocks (𝑏𝑥 , 𝑏 𝑦 , 𝑏𝑛 ) do 2: Determine batch index 𝑛 ← 𝑏𝑛 3: Determine output tile origin (𝑜ℎ 0, 𝑜𝑤 0 ) 4: Allocate shared-memory tile 𝑆 5: for all threads in block do 6: Cooperatively load required input tile from 𝑋 into 𝑆 7: Use zero padding for out-of-bound input locations 8: end for 9: Synchronize all threads 10: for all threads in block do 11: Determine warp id, lane id, output column 𝑜𝑤 12: Determine output-channel lane 𝑜𝑐 lane for 𝑜𝑐 ← 𝑜𝑐 lane to 𝑂𝐶 − 1 step 32/𝐶𝑂𝐿_𝑃𝐸𝑅_𝑊 𝐴𝑅𝑃 13: do 14: Initialize accumulators 𝑎𝑐𝑐 [0 . . . 𝑅 − 1] ← 0 15: for 𝑗 ← 𝑂 [𝑜𝑐] to 𝑂 [𝑜𝑐 + 1] − 1 do 16: Unpack 𝑃 [ 𝑗] into weight 𝑣, input channel 𝑖𝑐, offsets (𝑝𝑥 , 𝑝 𝑦 ) Compute shared-memory address for 17: 𝑆 [𝑖𝑐, 𝑝 𝑦 , 𝑜𝑤 + 𝑝𝑥 ] 18: for 𝑟 ← 0 to 𝑅 − 1 do 19: 𝑎𝑐𝑐 [𝑟 ] ← 𝑎𝑐𝑐 [𝑟 ] + 𝑣 · 𝑆 [𝑖𝑐, 𝑝 𝑦 + 𝑟, 𝑜𝑤 + 𝑝𝑥 ] 20: end for 21: end for 22: for 𝑟 ← 0 to 𝑅 − 1 do 23: if 𝑜ℎ 0 + 𝑟 < ℎ and 𝑜𝑤 < 𝑤 then 24: 𝑌 [𝑛, 𝑜𝑐, 𝑜ℎ 0 + 𝑟, 𝑜𝑤] ← 𝑎𝑐𝑐 [𝑟 ] 25: end if 26: end for 27: end for 28: end for 29: end for

Require: Input tensor 𝑋 ∈ R𝑁 ×𝐼𝐶 ×𝐻 ×𝑊

𝑁 = 32,

𝐼𝐶 = 32.

where 𝐻 and 𝑊 are height and width of the input image, 𝑁 is the batch size and 𝐼𝐶 is number of input channels The results show that the performance benefit of the sparse implementation strongly depends on both the sparsity level and the number of output channels. For 𝑂𝐶 = 48 and 𝑂𝐶 = 80, the sparse implementation already outperforms the dense baseline at 90% sparsity, achieving speedups of approximately 1.07× and 1.03×, respectively. As sparsity increases, the speedup grows steadily, reaching 1.63× for 𝑂𝐶 = 48 and 1.65× for 𝑂𝐶 = 80 at 98% sparsity. For larger output-channel configurations, the sparse implementation becomes competitive at higher sparsity levels. At 90% sparsity, the 𝑂𝐶 = 96, 𝑂𝐶 = 112, 𝑂𝐶 = 128, and 𝑂𝐶 = 256 configurations achieve speedups slightly below 1×. However, as sparsity increases, the sparse implementation gradually overtakes the dense baseline. The crossover point occurs near 91% sparsity for 𝑂𝐶 = 64 , 92% for 𝑂𝐶 = 112 and 𝑂𝐶 = 128. Beyond these points, the performance advantage continues to increase with sparsity.

Conference’17, July 2017, Washington, DC, USA

Tuteja et al.

1.6

1.5

1.4

Speedup

1.3 1.2 1.1

1.3

Speedup

OC OC = 128 OC = 112 OC = 96 OC = 80 OC = 64 OC = 48

1.4

OC OC = 48 OC = 40 OC = 32

1.2 1.1 1.0

1.0

0.9

0.8

0.90 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98

0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98

Sparsity

(a) Speedup on NVIDIA A100

(b) Speedup on Jetson Nano

Figure 5: Speedup relative to PyTorch for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: 𝐻 = 𝑊 = 256, 𝑁 = 32, 𝐼𝐶 = 32 for NVIDIA A100 and 𝐻 = 𝑊 = 128, 𝑁 = 8, 𝐼𝐶 = 16 for Jetson Nano

Execution time (ms)

5 4 3

OC OC = 48 OC = 40 OC = 32

15 14

Execution time (ms)

OC OC = 128 OC = 112 OC = 96 OC = 80 OC = 64 OC = 48

13 12 11 10 9

Ours (sparse) PyTorch (dense) 0.90

0.92

0.94

Sparsity

0.96

0.98

(a) Execution times on NVIDIA A100

Ours (sparse) PyTorch (dense)

8 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98

Sparsity

(b) Execution times on Jetson Nano

Figure 6: Execution times for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: 𝐻 = 𝑊 = 256, 𝑁 = 32, 𝐼𝐶 = 32 for NVIDIA A100 and 𝐻 = 𝑊 = 128, 𝑁 = 8, 𝐼𝐶 = 16 for Jetson Nano A dependence on the number of output channels can be observed. This behavior is expected since the current implementation parallelizes the OCs along the z-axis in the CUDA grid. The highest performance gains are achieved when the number of output channels can be processed within a single thread block, while larger output-channel configurations incur additional parallelization overhead. Nevertheless, the implementation consistently benefits from increasing sparsity and achieves speedups of up to approximately 1.65× over PyTorch’s dense convolution at 98% sparsity while maintaining numerical correctness.

The error bars represent the standard error of the mean computed from ten independent benchmark runs, each consisting of forty convolution executions. The error bars are generally small, indicating stable and reproducible performance measurements across repeated executions. Fig. 6a compares the execution time of the proposed sparse convolution kernel with the dense PyTorch implementation on the NVIDIA A100. The runtime of the sparse convolution kernel decreases consistently as weight sparsity increases, while the dense baseline remains nearly constant since it performs the same computation regardless of sparsity. The improvement is most pronounced for larger output channel counts, demonstrating the

Performance (GFLOP/s)

104

103

102 Higher sparsity

Conference’17, July 2017, Washington, DC, USA

Comm: 2.0 TB/s Comp: 19.5 TFLOP/s S: 90% S: 91% S: 92% S: 93% S: 94% S: 95% S: 96% S: 97% S: 98%

101 10 3 10 2 10 1 100 101 102 103

Arithmetic Intensity (FLOPs/Byte)

(a) Performance on NVIDIA A100

Performance (GFLOP/s)

Theoretical and Empirical Analysis of Sparse Convolution

Comm: 25.6 GB/s Compute: 236 GFLOP/s S: 90% S: 91% S: 92% S: 93% S: 94% S: 95% S: 96% S: 97% S: 98%

102

101

100

Higher sparsity

10 3 10 2 10 1 100 101 102 103

Arithmetic Intensity (FLOPs/Byte)

(b) Performance on Jetson Nano

Figure 7: Performance for varying sparsities on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) ability of the proposed kernel to effectively exploit sparsity. This reduction in execution time directly translates into lower inference latency (time-to-solution). Fig. 7a presents the roofline analysis of the proposed sparse direct convolution kernel on the NVIDIA A100 GPU for OC=128. As weight sparsity increases from 90% to 98%, the arithmetic intensity decreases from approximately 9.6 to 1.9 FLOP/Byte, shifting the kernel further toward the memory-bound region of the roofline. Correspondingly, the measured throughput decreases from approximately 2.4 TFLOP/s to 0.8 TFLOP/s, following the reduction in arithmetic intensity. The corresponding dense performance decreases from approximately 2.5 TFLOP/s to 0.5 TFLOP/s as, sparsity increases from 90% to 98% considering only non-zero computations. Nevertheless, the kernel remains well below both the theoretical HBM bandwidth roof and the FP32 compute roof, indicating that performance is constrained not only by raw memory bandwidth but also by irregular sparse memory accesses, reduced memory coalescing. Overall, the results demonstrate that the proposed sparse direct convolution implementation effectively exploits high levels of weight sparsity on modern GPUs.

6.2

NVIDIA Jetson Nano

Figure 5b shows the speedup achieved by the proposed sparse convolution implementation relative to PyTorch’s dense convolution for varying sparsity levels and output-channel (OC) configurations on the NVIDIA Jetson Nano. The experiments were performed with fixed input dimensions of 𝐻 = 𝑊 = 128, batch size (𝑁 = 8), and 𝐼𝐶 = 16. For Jetson Nano, we consider smaller dimensions since the memory on the device is limited. The results demonstrate that the performance benefit of the sparse implementation increases with sparsity for all evaluated OCs. Across the considered sparsity range of 91% − 98%, the speedup grows steadily as the number of nonzero weights decreases. For the 𝑂𝐶 = 40 configuration, the speedup

increases from approximately 1.19× at 91% sparsity to 1.52× at 98% sparsity. Similarly, the 𝑂𝐶 = 48 configuration improves from approximately 1.11× to 1.42×, while the 𝑂𝐶 = 32 configuration increases from 0.76× to 0.94×. A clear dependence on the number of output channels can also be observed. Configurations with larger output-channel counts achieve higher speedups than those with fewer output channels. This behavior is expected because larger output-channel counts increase the computational workload of the dense convolution, allowing the sparse implementation to benefit more substantially from the reduction in arithmetic operations and memory traffic. The error bars represent the standard error of the mean computed from ten independent benchmark runs, each consisting of forty convolution executions. With the exception of a few isolated measurements, the error bars are relatively small, demonstrating stable and reproducible performance across repeated benchmark runs. Fig. 6b compares the execution time of the proposed sparse convolution kernel with the dense PyTorch implementation on the Jetson Nano. The execution time of the proposed kernel decreases with increasing sparsity, whereas the dense PyTorch implementation remains largely unchanged. The sparse implementation consistently reduces the time-to-solution for inference across all evaluated output channel counts except 𝑂𝐶 = 32. Fig. 7b presents the roofline analysis of the proposed sparse direct convolution kernel on the Tegra X1 GPU for OC=48. As weight sparsity increases from 90% to 98%, the measured throughput decreases from approximately 12.5 GFLOP/s to 3.3 GFLOP/s, following the reduction in arithmetic intensity. The corresponding dense performance decreases from approximately 11.5 GFLOP/s to 2.3 GFLOP/s as, sparsity increases from 90% to 98% considering only non-zero computations. Similar to the A100 case, the kernel remains well below both the theoretical HBM bandwidth roof and the FP32 compute roof, indicating that performance is constrained

Conference’17, July 2017, Washington, DC, USA

not only by raw memory bandwidth but also by irregular sparse memory accesses, reduced memory coalescing.

Conclusion

This paper presented a theoretical and empirical analysis of sparse direct convolution for highly sparse convolutional neural networks on both: a high-performance GPU and an edge accelerator. Using roofline analysis, we demonstrated that increasing weight sparsity fundamentally changes the performance characteristics of convolution by reducing arithmetic intensity and shifting execution from the compute-bound to the memory-bound regime. Guided by this analysis, we proposed a direct sparse convolution kernel based on packed sparse weights, shared-memory tiling, and a warp-level thread mapping strategy. The resulting implementation achieved speedups of up to 1.65× on the NVIDIA A100 and 1.52× on the NVIDIA Jetson Nano compared to PyTorch’s dense convolution implementation. Beyond the observed kernel level speedups, our results highlight the practical potential of direct sparse convolution for edge AI applications. Modern convolutional neural networks such as ResNet-18, ResNet-34, and ResNet-50 are widely deployed in autonomous drones, mobile robots, medical devices, and intelligent sensors, where latency, power consumption, and limited computational resources are critical constraints. During inference, model weights remain resident in device memory while feature maps are streamed continuously. Consequently, reducing both the number of arithmetic operations and the amount of weight data transferred from memory can directly improve inference latency and throughput without modifying the network architecture. . It is also important to note that these results are obtained for a 3 × 3 convolution kernel with a stride of 1. Achieving similar performance improvements becomes increasingly challenging for larger input dimensions and kernel sizes. Although the roofline model predicts substantially larger speedups, the measured performance remains well below the theoretical memory-bandwidth roof. This gap reflects an inherent challenge of sparse computation rather than a limitation of the implementation itself. Roofline analysis assumes ideal memory behavior, perfect load balancing, and complete utilization of the available memory bandwidth. In practice, sparse workloads suffer from irregular memory accesses, reduced memory coalescing, lower cache locality, additional index decoding overhead, and workload imbalance caused by varying numbers of nonzeros across output channels. Moreover, NVIDIA GPUs and most modern edge accelerators are primarily optimized for regular dense computation. Efficiently exploiting high levels of sparsity may therefore require specialized hardware support, such as sparse processing units, sparsity-aware memory systems, and execution mechanisms capable of handling irregular workloads without sacrificing hardware utilization. We also plan to evaluate complete sparse neural networks, including pruned ResNet models, to quantify end-to-end inference speedups, energy efficiency, and real-world deployment benefits on modern edge accelerators.

Tuteja et al.

Acknowledgments This work was performed on the HoreKa supercomputer and the NHR@KIT Future Technologies Partition testbed, funded by the Ministry of Science, Research and the Arts Baden-Württemberg and by the Federal Ministry of Research, Technology and Space. This work is supported by the Helmholtz AI platform grant. The authors would like to thank the Federal Ministry of Education and Research and the state governments (www.nhr-verein.de/unserepartner) for supporting this work/project as part of the joint funding of National High Performance Computing (NHR). The authors acknowledge the use of AI-based tools for language editing and grammar improvement during the preparation of this manuscript.

A Appendix A.1 Maximum absolute error for convolution To validate the correctness of the convolution, fig. 8a and fig. 8b report the maximum absolute error between the sparse convolution kernel and the dense PyTorch baseline across the same sparsity sweep 𝐻 = 𝑊 = 256, 𝑁 = 32, 𝐼𝐶 = 32 for NVIDIA A100 and and 𝐻 = 𝑊 = 128, 𝑁 = 8, 𝐼𝐶 = 16 Jetson Nano respectively. Error decreases monotonically with sparsity for both of the devices. The residual error against the FP32 PyTorch baseline reflects two effects: the reduced number of accumulated terms at higher sparsity, and the one time quantization of weight values to FP16 during packing. Both of these factors diminish as sparsity increases, since fewer terms are summed.

AD Appendix Part 1: Overview of Contributions & Artifacts A. Paper’s Main Contributions. The computational artifacts support the following contributions of the paper: (1) A roofline analysis demonstrating that sparse direct convolution operates in the memory bandwidth bound region on modern GPUs. We showed the analysis for NVIDIA A100 and Jetso Nano (NVIDIA Tegra X1). (2) A CUDA implementation of a sparse direct convolution kernel using • packed 32-bit sparse weight representation, • shared-memory tiling, • an optimal thread mapping. (3) An experimental evaluation on NVIDIA A100 and NVIDIA Jetson Nano demonstrating execution time, speedup, numerical correctness, and roofline behavior compared to PyTorch’s dense convolution. B. Computational Artifacts.

Part 2: Artifact Identification Artifact 1: Sparse Convolution Evaluation. A. Relation to Contributions. The artifact reproduces the proposed sparse convolution kernel, benchmarks it against PyTorch’s dense convolution, performs roofline analysis, and regenerates the figures presented in the paper. B. Expected Results. Executing the artifact should reproduce:

Theoretical and Empirical Analysis of Sparse Convolution

Conference’17, July 2017, Washington, DC, USA

OC OC = 128 OC = 112 OC = 96 OC = 80 OC = 64 OC = 48

10 7

6 × 10 8

Maximum Absolute Error

2 × 10 7

10 7 OC OC = 48 OC = 40 OC = 32

6 × 10 8

4 × 10 8 3 × 10 8

0.90

0.92

0.94

Sparsity

0.96

0.98

(a) Maximum absolute error on NVIDIA A100

0.90

0.92

0.94

Sparsity

0.96

0.98

(b) Maximum absolute error on Jetson Nano

Figure 8: Maximum absolute error for varying sparsities and Output Channels (OC) on NVIDIA A100 and Jetson Nano (NVIDIA Tegra X1) with configurations: 𝐻 = 𝑊 = 256, 𝑁 = 32, 𝐼𝐶 = 32 for NVIDIA A100 and 𝐻 = 𝑊 = 128, 𝑁 = 8, 𝐼𝐶 = 16 for Jetson Nano Table 4: Overview of computational artifacts. Artifact Sparse convolution implementation Roofline analysis scripts Benchmark scripts Plot generation scripts

Contr.

Paper elements reproduced

Algorithm 1; Figures 3,4

Figures 2,6; Tables 1,2,3

3 3

Figures 5,6,7,8 Performance figures and tables

• Increasing speedup of the sparse convolution kernel as sparsity increases. • Execution times comparable to those reported in the paper. • Numerical correctness compared with PyTorch. • Roofline plots with similar performance trends. Minor numerical differences may occur due to GPU architecture, CUDA version, compiler optimizations, and runtime variability. These results validate both the theoretical analysis and the proposed sparse convolution implementation. Table 5: Estimated reproduction time. Step

Time (minutes)

Artifact setup Compilation Benchmark execution Result analysis

15–20 3–5 2–15 2–3

Total

40–70

C. Expected Reproduction Time.

D. Artifact Setup. Hardware • NVIDIA GPU with CUDA support – NVIDIA A100 (recommended) – NVIDIA Jetson Nano (optional) Software Table 6: Required software for NVIDIA A100 Software

Version

CUDA Toolkit Python PyTorch pybind11 CMake GCC

12.2 3.11 2.9 latest ≥ 3.20 ≥ 11

Repository: The repository is hosted on GitHub at https://github.com/keshvituteja/ sparseconv. The source code and plotting scripts used in the paper can be esily reproduced by following the using the scripts at https:// github.com/keshvituteja/sparseconv/tree/main/benchmarks/legacy and by following the instructions in legacy_build.md. The code can also be installed as a Python package, the detailed installation instructions are presented in README.md. Datasets / Inputs No external datasets are required. Input tensors and sparse convolution kernels are generated automatically. Random sparse kernels are generated using a fixed random seed. Installation & Deployment Requirements: • CUDA compiler (nvcc) • CMake • Python

Conference’17, July 2017, Washington, DC, USA

• PyTorch Compilation: The Python bindings are compiled together with the CUDA implementation.

References [1] Keiron O’Shea and Ryan Nash. An introduction to convolutional neural networks, 2015. [2] Abdelrahman Hosny, Marina Neseem, and Sherief Reda. Sparse bitmap compression for memory-efficient training on the edge. In 2021 IEEE/ACM Symposium on Edge Computing (SEC), pages 14–25, 2021. [3] Md Aamir Raihan and Tor M. Aamodt. Sparse weight activation training, 2020. [4] Marko Stamenovic, Nils L. Westhausen, Li-Chia Yang, Carl Jensen, and Alex Pawlicki. Weight, block or unit? exploring sparsity tradeoffs for speech enhancement on tiny neural accelerators, 2021. [5] Enshu Liu, Junyi Zhu, Zinan Lin, Xuefei Ning, Matthew B. Blaschko, Shengen Yan, Guohao Dai, Huazhong Yang, and Yu Wang. Efficient expert pruning for sparse mixture-of-experts language models: Enhancing performance and reducing inference costs, 2024. [6] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks, 2021. [7] Denis Kuznedelev, Eldar Kurtic, Eugenia Iofinova, Elias Frantar, Alexandra Peste, and Dan Alistarh. Accurate neural network pruning requires rethinking sparse optimization, 2023. [8] Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning, 2020. [9] Nathan Bell and Michael Garland. Implementing sparse matrix-vector multiplication on throughput-oriented processors. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC ’09, New York, NY, USA, 2009. Association for Computing Machinery. [10] Kumar Chellapilla, Sidd Puri, and Patrice Simard. High performance convolutional neural networks for document processing. In Proceedings of the Tenth International Workshop on Frontiers in Handwriting Recognition (IWFHR), La Baule, France, October 2006. HAL Id: inria-00112631.

Tuteja et al.

[11] Cristian Ramírez, Adrián Castelló, Héctor Martínez, and Enrique S. QuintanaOrtí. Parallel gemm-based convolution for deep learning on multicore risc-v processors. The Journal of Supercomputing, 80(9):12623–12643, 2024. [12] Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets, 2019. [13] Keshvi Tuteja, Gregor Olenik, Roman Mishchuk, Yu-Hsiang Tsai, Markus Götz, Achim Streit, Hartwig Anzt, and Charlotte Debus. pyginkgo: A sparse linear algebra operator framework for python. In Proceedings of the 54th International Conference on Parallel Processing, ICPP ’25, page 753–763. ACM, 2025. [14] Shuai Lu, Jun Chu, and Xu T. Liu. Im2win: Memory efficient convolution on simd architectures. In 2022 IEEE High Performance Extreme Computing Conference (HPEC), page 1–7. IEEE, 2022. [15] Yangjie Zhou, Mengtian Yang, Cong Guo, Jingwen Leng, Yun Liang, Quan Chen, Minyi Guo, and Yuhao Zhu. Characterizing and demystifying the implicit convolution algorithm on commercial matrix-multiplication accelerators, 2021. [16] Jongsoo Park, Sheng Li, Wei Wen, Ping Tak Peter Tang, Hai Li, Yiran Chen, and Pradeep Dubey. Faster cnns with direct sparse convolutions and guided pruning, 2017. [17] Syed Asad Alam, Andrew Anderson, Barbara Barabasz, and David Gregg. Winograd convolution for deep neural networks: Efficient point selection, 2022. [18] Aleksandar Zlateski, Zhen Jia, Kai Li, and Fredo Durand. A deeper look at fft and winograd convolutions. In Proceedings of the 2nd Conference on Systems and Machine Learning (SysML), Stanford, CA, USA, 2018. [19] Syed Asad Alam, Andrew Anderson, Barbara Barabasz, and David Gregg. Winograd convolution for deep neural networks: Efficient point selection. ACM Trans. Embed. Comput. Syst., 21(6), December 2022. [20] Samuel Williams, Andrew Waterman, and David Patterson. Roofline: an insightful visual performance model for multicore architectures. Commun. ACM, 52(4):65–76, April 2009. [21] NVIDIA Corporation. NVIDIA A100 Tensor Core GPU Datasheet. https: //www.nvidia.com/content/dam/en-zz/Solutions/Data-Center/a100/pdf/nvidiaa100-datasheet.pdf, 2020. Accessed: 2025-08-14. [22] Felix Liu, Albin Fredriksson, and Stefano Markidis. A gpu-accelerated interior point method for radiation therapy optimization. arXiv preprint arXiv:2405.03584, 2024. [23] Wenzel Jakob, Jason Rhinelander, and Dean Moldovan. pybind11 – seamless operability between c++11 and python, 2017. https://github.com/pybind/pybind11.

Theoretical and Empirical Analysis of Sparse Convolution

Analyze & explore related research in Conceptio

Related documents