Accelerating Sparse Convolution with Column Vector-Wise Sparsity
Authors: Yijun Tan
Kai Han
Kang Zhao
Xianzhi Yu
Zidong Du
Yunji Chen
Yunhe Wang
Jun Yao
Venue: NeurIPS 2022 Accept (2022)

Abstract: 
Weight sparsity is a promising approach to reducing the model size and computation cost of convolutional neural networks (CNNs). Nevertheless, non-zero weights often distribute randomly in sparse CNN models, introducing enormous difficulty in obtaining actual speedup on common hardware (e.g., GPU) over their dense counterparts. Existing acceleration solutions either require hardware modifications for irregular memory access support or rely on a partially structured sparsity pattern. Neither of these methods is capable of achieving fruitful speedup on convolution layers.

In this work, we propose an algorithm-software co-designed sparse convolution based on a novel out-vector-wise (OVW) sparse pattern. 
Building on the insight that vertical vector integrity can preserve continuous memory access in IM2COL,  the OVW pattern treats a $V\times1$ vector as an entirety. To reduce the error caused by sparsity, we propose an equivalent transformation process, i.e., clustering-based channel permutation, to gather similar rows together. Experimental evaluations demonstrate that our method achieves a $1.7\times$ and $3.2\times$ speedup over the SOTA solution and the dense convolution of ResNet50 on NVIDIA V100 at 75\% sparsity, respectively, with only negligible accuracy loss. Moreover, compared to the SOTA solution that achieves speedups only on data with 60\% sparsity or more, our method begins to obtain speedups on data with only 10\% sparsity.

Accelerating Sparse Convolution with Column Vector-Wise Sparsity
Yijun Tan Kai Han Kang Zhao² Xianzhi Yu Zidong Du' Yunji Chen 1,2 Yunhe Wang" "Jun Yao
SKL of Processors, Institute of Computing Technology, CAS University of Chinese Academy of Sciences Huawei Noah's Ark Lab 19ny)19998gmail.com (kai ha,h,an,,ni,,, yunhe. wang) @hwwwei.
Abstract
Weight sparsity is promising approach to reducing the model size and computation of convolutional neural networks (CNNs). Nevertheless, non-zero weights often distribute randomly in sparse CNN models, introducing enormous difficulty in obtaining actual speedup on common hardware (e.g., GPU) over their dense counterparts, Existing ucceleration solutions either require hardware modifications for irregular memory access support or rely on partially structured sparsity pattern. Neither of these methods is capable of achieving fruitful speedup on convolution layers.
this work, we propose an algorithm- softtare co-designed sparse convolution based on novel out settveetor-wise (OVW) sparse pattern. Building the insight that vertical vector integrity can preserve continuous memory access in IM2COL, the OVW pattern treats V vector unit. To reduce the eπгоr caused by sparsity, we propose an equivalent transformation process, i.e., clustering-based channel permutation, to gather similar demonstrate that our method achieves 1.7 x and 3.2x speedup over the SOTA solution and the dense convolution of ResNet50 on NVIDIA V100 75% sparsity, respectively, with only negligible accuracy loss. Moreover, compared to the SOTA solution that achieves speedups only data with 60% sparsity more, method begins to obtain speedups on data with only 10% sparsity.
together. Experimental evaluations
Introduction
Recently, convolutional neural networks (CNNs) have yielded astonishing results in many important domains such vision R and language [8] With CNN algorithm developing rapidly, CNN models' storage and computing overhead grow exponentially. To significantly reduce both the computations and memory access, weight sparsity has been adopted as a promising approach to improve hardware efficiency.
Despite the success in reducing computations and data access, unconstrained, fine- fine-grained sparsity fails to bring practical speedups on common GPUs. This is because unstructured sparsity generally induces tremendous access conflicts and load unbalances, which lowers GPU's performance. For example, on NVIDIA V100, the sparse matrix multiplication performs not faster than the dense matrix multiplication until the sparsity ratio over 95% [1
Unfortunately, existing solutions either require hardware modifications or only partially address the problem by being constrained with structured, coarse coarse-grained sparsity, resulting in high accuracy loss. The former to leverage the sparse matrix-matrix multiplication (e.g., SPMM) operation
"Corresponding author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

on GPU. While directly applying SPMM on sparse CNNs can run even slower than dense CNNs often require their unique need for dedicated hardware support to overcome discontinuous memory access, which is impractical. The latter is to leverage the general matrix-matrix multiplication (e.g., GEMM) operation on GPU.
17 17 pproductive SPMM acceleration solutions 2
Recent works focus on structured sparsity with different sparse patterns to gain speedup benefits from weight sparsity. Block sparsity [4] manages to restore the spatial locality of matrices to large extent, at the cost of a strict restriction on the non-zero Balanced sparsity 22 19 [3]. newly introduced on NVIDIA A100 GPU [4, however, lacks flexibility in choosing model sparsity rate that only exact 50% sparsity ratio could be deployed on this dedicated hardware. These efforts achieve some palpable acceleration compared to dense GEMM operation. but they all struggle attain similar results on convolution layers which have proven to be a greater challenge.
To tackle these problems, here we present a novel sparse convolution acceleration algorithm featured with column-wise sparsity and implicit matrix multiplication. Specifically, the proposed column-wise sparsity is dubbed the out-vector-wise (OVW) sparse pattern since the pattern sparsifies matrix by treating a VxI vector as an entirety, as shown in Figure [ During convolution, the OVW pattern can hold both strong memory consistency and high data reuse rates of input matrices using implicit matrix multiplication. Moreover, we propose to employ channel permutation and row clustering to improve the accuracy of OVW sparse pattern-bast baaser CNNs. Besides, a GPU kernel is carefully designed to ensure that our OVW sparse pattern is supported by common GPUs. With these efforts, our algorithm predominantly outperforms other sparse convolution acceleration algorithms on various CNN models. More importantly, our algorithm can achieve the acceleration of convolutions even with very low weight sparsity ratio, e.g., 10%. Instead, prior arts can only work fine when the weight sparsity ratio is over 60%.
The main contributions of this paper are listed as follows:
We propose vector-based sparsity pattern, i.e., the OVW pattern to balance inference accuracy loss and computation efficiency in a hardware-friendly manner.
We implement a new GPU convolution kernel to support the OVW pattern. The kernel utilizes the technique of extracting filter location information which can further reduce inference runtime.
We propose heuristic clustering method to obtain an appropriate channel permutation for reducing accuracy drop during weight pruning. This channel permutation operation is conducted offline, which does not affect inference time.
Our GPU kernel can accelerate convolution at a wide range of model sparsity rates. With few accuracy loss, the kernel can speed up ResNet50 by 1.7x and 3.2x, respectively over the SOTA solution and the dense cuDNN convolution on NVIDIA V100 GPU at 75% sparsity level.
2 Related work
2.1 Software-only Acceleration For Sparse CNN Model
Weight pruning has been a popular technique for efficient CNN inference. Early studies 7 6 show that removing large proportion of unimportant connections in CNN models does not necessarily lead to inference accuracy impairment. Reducing parameters helps exploit redundancy in CNN models, which requires fewer computations and data accesses. However, for CNN inference, weight pruned sparse CNNs usually perform worse than dense counterparts, unless the CNN sparsity ratios are substantial, i... very sparse CNNs.
To address this issue, methods other than unstructured sparsity are exploited. Researchers exploit various constraints on sparsity patterns in exchange for computation efficiency. A primary domain of this region is filter pruning. where parameters of an entire filter are pruned or kept as a whole. However, this direct modification of channel size suffers a sharp accuracy drop [10) 11 [6]. Moderate sparsity patterns are also examined, such as block sparsity [7] which is proposed to elevate the spatial locality of sparse matrices. But this feature can achieve speedup only when sparsity ratios are larger than 70%. Tile-wise sparsity 5 endows weight patterns with more flexibility. Compared to previous methods, balanced sparsity 15 19 is more feasible with recent support from NVIDIA A100 GPU which

---

Element- -Wise
Inter- Peen-Veetor-VVe WWise
Cuuter-Vector-oe
Block-Wise
Pruned
Unpruned
Figure 1: Comparison of four patterns with 50% sparsity.
directly optimizes 2:4 balanced sparsity. Recent work Sh,l_ uses matrix transformation to utilize block sparsity's computation efficiency while removing some of its constraints. In this way, the threshold of weight sparsity ratio that enables acceleration is reduced from 70% to 60%. Different from prior works which only work for very sparse matrices, in this paper, our algorithm can achieve speedup when the sparsity ratio is only 10%.
2.2 GEMM Based Convolution
GEMM has been adopted widely to perform convolution and it performs significantly better than other convolution methods such as FFT, and Winograd on modern commercial hardware accelerators such as TPUs and GPUs. The GEMM-based algorithms could be further divided into two types: explicit matrix multiplication and implicit matrix multiplication. Explicit matrix multiplication uses IM2COL to adapt inputs for GEMM. IM2COL is an I0-intensive operation, which brings in significant workload other than computation cost[]]. Implicit matrix multiplication merges these operations more efficient memory accesses. updates pointers feature map shared memory and performs tile-based matrix multiplication simultaneously. On NVIDIA V100 GPUs, explicit GEMM convolutions consume on average 120%, 126%, and 142% in time compared to implicit GEMM-based convolution convolution layers of Alexnet, Resnet and Googlenet [20]
Yet, few studies have investigated the sparse convolution with implicit GEMM. Performing sparse convolution by GEMM is always through explicit matrix multiplication rather than implicit matrix multiplication. This is because of the IM2COL operation which is extremely difficult not impossible for sparse matrix multiplication, sparse matrices are compactly compressed and irregularly stored. As result, implicit GEMM who does have to suffer from the costly IM2COL operation has the potential to achieve higher efficiency for sprase convolution. In this paper, we investigate the implicit GEMM-based sparse convolution to leverage the peroomaeformance GEMMs on existing hardware.
3 Accelerating Sparse Convolution
In this section, we introduce our proposed sparse convolution algorithm, including the OVW pattern of sparsity for the proposed sparse convolution, its advantage in convolution computation and our detailed implementation on GPU.
3.1 The OVW Pattern
The OVW pattern belongs to the rector-wise(V) (VW) pattern which is one of the three different pattern categories of sparsity in matrix. As shown in Fig the first sparsity pattern is the clement-wise(EWV pattern, corresponding to unstructured pruning, which evaluates each parameter individually. Having imposed no constraint on pruning, this pattern succeeded at model flexibility but struggled at actual acceleration due to its irregular memory accesses. The second sparsity pattern the VW pattern, which can be further divided into the inter-vectorwwise(NV
and the OVW pattern. They both treat a Vxl vector as an entirety while IVW pattern prunes a certain proportion of weights inside each vector and the OVW pattern focuses on the entire vector of weights. The third pattern is the (iie(B)) pattern, and minimum pruning granularity is a VxV block. This pattern has the highest computation efficiency, but its inference accuracy loss is high well. In this work,

---

Feuture
Fetch feature ptr off
origina?
Go
Output
Sparse Filter
POW
shored memory
lond
ide
data
colarol
gemm
batch_size
X
Figure 2: Illustration of GPU conv kernel. The solid lines the actual computation flow and the dotted lines are processing pointers and descriptors.
the OVW pattern since it shares the advantages of the VW pattern, which balances computation efficiency of BW and network accuracy of EW. The Sh SWW pattern is actually a variant this pattern, who uses extra channel reordering procedure gather block-wise pattern utilities.
3.2 The OVW Pattern's Advantage in Convolution Computation
The biggest advantage of the OVW pattern is that fits the way an efficient dense warp-level GEMM instruction fetches input data. This instruction the key contributor to most of the sparse matrix acceleration methods. The reasons are as followed.
As shown Fig 2 the OVW pattern-based sparse convolution can be broken down into multiple dense matrix multiplications of smaller sizes. During the loading process of a dense convolution procedure, column of filter data loaded into shared memory shares specific position the filter map. In the meantime, continuous block in the feature map is loaded accordingly to prepare convolution. Several columns fetched from the filters together form the left input matrix of the block matrix multiplication and their corresponding feature data blocks form the right input matrix. Noticing that this forming process of input matrix does require the loaded filter columns be continuous, meaning that efficient dense operations can also be performed by grouping some unrelated columns. Based on this observation, we could take in multiple columns of irrelevant column indices from the OVW pattern sparse matrix and handle them in the same way as the dense GEMM operation. This similarity between our convolution algorithm and the implicit GEMM convolution guarantees us similar overall computation efficiency.
What's more, other sparsity such the Shfl_B BW pattern who is actually variant of this pattern, uses an extra channel reordering procedure to gather block-wise pattern utilities. The OVW pattern, however, could be directly used in our convolution algorithm which denotes higher acceleration potential. Compared to N:M sparsity.one of the IVW pattern, our approach does not need specialized hardware supports and much more elastic in selecting the sparsity ratio of each layer. Besides, the IVW pattern still faces the memory- bound issue, because the amount of redundant data that needs be loaded into shared memory each time is equal its sparsity ratio.
3.3 GPU Sparse Kernel Implementation
As shown in Algorithm I our convolution kernel implementation contains three steps. The first step get the corresponding feature pointer offsets through original filter structure information recovery. These parts of calculation are done by the function Cal Thread, Sa Offest The second step is to

---

load data from both input matrices into shared memory. Some threads use the function load_ column load a column vector length TM from filters to shared memory with DY threads. Threads then use the function gond_row to load row vector from the feature map in the same way. The third step calls warp matrix multiplication operators. When calculating matrix AM X x BRXN = -M N a three dimension parallelism( DX, DY, DZ) thread is employed. (DX, DY, DZ) threads loop along (M, N, K) individually. Several threads together use the function W arr__MMMMM M to multiply the loaded matrices and write back after results accumulation is finished. Each thread computes a tile matrix multiplication of the size (MTNNKK)
The procedure of calculating the exact pointer offset of the feature map for corresponding filter columns contains two steps. During a convolution computation, the corresponding location of aij X bys is not obvious. Hence after loading aij into shared memory, firstly, the GPU kernel has to fetch the column indices of dzj in the original filter. The column indices are then used to recover the exact position of this column in the filter map. Subsequently, the location offset of the corresponding data in the feature map is calculated, after which dEs can finally located in the feature map.
Algorithm 1: Sparse convolution computation
Data: row pow_ddxll,. filter[], input]]
Result: output
Shared memory A[TM]]TK], BITKITNI, CITMITNN;
2 for Thread idx=I to DX, idy=l to DY, idz=l to DZ do
of fet Cal Thread Offset(row _ixl]lzzl,] idz, idy, idz);
4
idx < TK then Load_column(( (A, filter[idz][idaa TM, idy):
end
if' idy < TK then
Load_rowe imputlof fset), TN, idz);
end
10
Syncthreads();
11
Warp Warp_MMA(A, B, idz, idy);
MMA(A, Accumulate Results(C);;
12
13
Store(output, C);
end
15 Return output:
If only the column indices of sparse matrices stored, their location information has be recovered each time before the corresponding activation is loaded. Like the location offset in the feature map, the corresponding data location in the filter map could be prepared in advance. Because is constant for each thread during the whole process. Extra storage occupation of this technique is two extra dimension indices data array of filter map, which takes merely 3% total storage of compressed model with vector length=64, and 6% with vector length=32, in exchange for 10% run time reduction of Resnet50's s convolution layers on average. Considering that a sparse model is already highly compressed, this additional model redundancy is totally acceptable.
4 Pruning Algorithm
In this section, we introduce our pruning algorithm for the OVW pattern, including the channel permutation technique and our method to acquire desired permutation order for it.
4.1 Channel Permutation
Our pruning method can be divided into two steps: shuffling the filter matrix rows in each layer and applying vector-wise pruning.
Here we will explain why filter permutation will do no harm to the network inference. Matrix multi- plication only swaps the order in the output dimension and does not change the actual computation. Permuted operation results can be recovered through reversed permutation of the operand output. As we only permute the output channel of each layer, the permuted order of the current layer will be
5

---

actipations
layer
activationge2
layorkes
activation
originul:
3.8
0.2
Wos
Wax
Wos
Waa
06
Wa
W
W1:
W4:
1
A/
1
J
Wax
Win
Wey
Wix
3.4
0.9
0.4
0.7
Wsy
W3x
W5x
-.1
order:
0
permutod:
0.
0.2
0.3
Wox
0.6
0.1
0.6
0.2
Wix
W12
Wi.
b
F66
4
0.1
C.6
0.4
Wsx
W53
Wsa
C.9
Wao
W32
Was
W33
Pruned
Unpruned
Figure 3: Illustration of the permutation transfer process. The permuted matrix kept a larger amount of absolute weight value after pruning at the same spansity. Following activation is recovered by permuting the output channel layer and the input channel of layer k+1 simultancously.
absorbed by the input channel dimension of the next GEMM-based layer(convolution or linear). Fig shows one iteration for channel permutation between layer,, and layer As we have reordered the output channel of layer,, the activation; is changed to the same order, but after we permute the input channel layers+11, activationg+11 restored. More weights value could be saved after permutation. The same operation is then repeated on layeræ-1 and so on until every GEMM layer in the network is permuted. This permutation transfer procedure allows to choose an appropriate permutation row order for every filter without altering the output of the network.
The rest of the layers such the pooling layers and the activation layers involve modification along channel dimension thus are not affected by this process. The BN layers and the bias added at the end of convolution layers and linear layers do produce any new permutation order, but they have to permute according to the permutation passing through.
4.2 Row Clustering
Algorithm 2: Row clustering
Data: The original weight W. number of clusters kt number of selected column m. The reordered weight RW.
Result:
RW empty:
while W is not empty do
Sort the columns of W by column variance;
Build SampleW by selecting columns with the top-m largest variances; Get the clustered groups G Balanced Saaeeeeeeeeaaaaaeaeeaeaeaaeee k); Select the group g with maximum sum;
Append g to RW:
Remove g from W:
end
10 Return RW:
use row clustering method to obtain an appropriate permutation order. heuristic indicator evaluating the quality of permutation is the sum of absolute weight value being pruned, assuming that the method that the preservation of more important weights corresponds less inference accuracy loss. An obvious route is that the weight rows with shorter distances assigned to the same group as

---

Table 1: Network accuracy on Cifar100. V is the vector length of the OVW pattern. V for Vgg19 and Resnet is set to 64 for all layers. For SqueezeNet and MobileNetv2, the V value in the table is our average vector length of the whole network as we select an optimal V for each layer.
Network
Vgg19
Resnet18
Resnet50
SqueezeNet
MobileNetv2
Baseline
dense
71.41
77.19
78.60
71.01
68.99
Unstructured
71.62(=0.11)
76.42(+40.0)
77.99(+0.08)
70.27(+0.15)
68.89(+10006)
OVW
80%
+0.04)
73.67(40.38)
75.80 +0.16)
69.05
+0.12)
68.31
OVW permuted
71.46(=0.06)
74.22(
75.99
69.29(=0.15)
68.52(#0.05)
A
+0.10
+0.56
+0.19
+0.24
+0.21
64
64
64
44.48
32.02
Unstructured
71.35(=0..5)
74.87(+0.00)
78.02(+0.04)
68.40(+0.19) 70.29(=0..6)
OVW OVW permuted
90%
71.29(=0.03)
71.14(#0.10)
72.72(#0.13)
66.07(#0.64) 65.69(=0.59)
71.37
72.25(
73.26(#0.22)
65.80(=0.73))
67.46(#1.03)
+0.08
+1.I1
40.54
+0.11
+1.39
64
64
64
44.48
32.02
much as possible. Shfl_BW chooses the kmeans method for clustering, but after careful experiment, found that the kmeans method does suit this issue well. For starters, the number of elements in each group is set to be a fixed value (vector length), and kmeans requires additional operations to meet this demand. Also, the data dimension(input channel multiplies filter height and width) is too large, while the amount of data and groups is relatively small. Kmeans falls in local minima easily and the output cluster is extremely unstable. We introduced the balanced kmeans 13 modified it to palliate both symptoms mentioned above.
solve it and
Algorithm 2 shows the key steps of our algorithm. First, construct characteristic matrix by assembling rows with the highest variance, then cluster rows of this matrix to alleviate excessive dimension. We utilize balanced kmeans to get equal size clusters. In each iteration of balanced kmeans, instead of assigning each data vector to its nearest cluster center as the origin kmeans algorithm, distance matrix between all the vectors and the current cluster centers is formed. We minimize the sum of distance while each cluster contains the same amount of data vector. This minimization problem can be converted to bipartite matching and we employ the Kuhn-Munkres algorithm to solve it. Secondly, for each clustering result, we only adopt the most important group under this feature increase operation stability. This group removed from the original matrix and then the feature matrix is reconstructed and clustered. Repeat the above steps until all data grouping completes, the permuted matrix and its permuting order is obtained.
Evaluation
5.1
Model Accuracy
We evaluate our method on several popular CNN models on NVIDIA V100 GPU. We only calculate the speedup of the convolution layers in the following results. Table [ the accuracy of our method compared to unstructured sparsity where V stands for vector length. "OVW permuted" shows better accuracy over "OVW non-permuted" on all CNN models.
The upper bound of in our kernel implementation is 64 and we tend to make it as large as possible to maximize shared memory usage. However, group convolution has no filter data reusage for vector length larger than its group size. Similarly, V is set to in depthwise convolution layers. Besides that, the first convolution layer of SqueezeNet has only 96 output channels. If the vector length is 64, the second tile in the output channel dimension only processes 32 rows which is only half loaded. In this case, vector length is set to 32 maximize computation resource utilization. The V selection strategy here is to maximize while utilizing shared memory resources as much as possible.
All the results in this table use the same fine-tuning process. We fine-tune each network for 40 epochs after pruning with the same learning rate 0.0008. Also, each layer can hold different sparsity ratio credit to our acceleration for convolution at low sparsity ratio.
7

---

Rossvet50 convi
Resnet50 conv11
Resnet50 convil
dEA 21,
190, 7.7.3 Lacil Apnnan
20
up
0.5
ratio 1g19 average
ratio Squeezenet average
Resnet.50 average
Truech exeegg
Vig
knplei graze
2xy55 g0
expliit grome
eaplint peares
caplift gITEE
speed up
speott
sparsity
apors
sparssty
Figure Speed comparison between our sparsity convolution kernel and two GEMM-based convolu- tion in cuDNN library on NVIDIA V100 GPU.
Table Comparing sparsity patterns on Resnet50 for ImageNet classification. Speedup of unstruc- tured spasity is the same dense because the fastest way run it is to invoke the dense convolution kernel.
Network
Sparsity ratio
Accuracy
Speedup
Baseline
Dense
76.12
1x
Balanced sparsity (2:4)
50%
76.29
1.3x
ShfLBW BW (
90%
73.09
2.5x
OVW
30%
76.17
1.38x
OVW
50%
75.76
1.86
OVW
70%
73.35
2.79x
30
78
80
spanee pattern
accuracy
75
our method
76
2-4
shB-BW
85
74
90
95
72
speedup ratio
Figure 5: Speed up against the dense baseline on Resnet50 Cifar 100 comparing to other vector-level sparse patterns NVIDIA V100 GPU.

---

5.2 Convolution Kernel Speedup
As shown in Fig we evaluate the speedup of our method on three popular CNN models. We use the cuDNN convolution operator as the dense baseline. The first three graphs in Fig represent three typical convolution shapes in CNN models: small channel size with large feature map. medium channel size with a medium feature map, and large channel size with a small feature map. Our kernel can accelerate all these types of convolution layers while exceeds at the twelfth convolution layer of Resnet50 which is the most used kind of convolution layer 4.8x and 3.87 over cuDNN on V100 at 80% sparsity, vector lengths 64 and 32.
5.3 Comparing Different Sparsity Patterns
We replicate two vector-level sparsity pattern, balanced Sparsity 2:4)
15 and Shfl_BW [9] for comparison. Other vector-level sparsity patterns such Tile-wise are slower than the former two patterns. Also, these patterns lack implementation for convolution.
Table 2 shows results of Resnet50 on ImageNet directly copied from Shfl_BW paper, where an expensive method Grow and Prune[[2] used to recover its accuracy. Grow and Prune is a sparsity pattern independent method. We fine-tune our pretrained Resnet50 model for 20 epochs with the learning rate of 0.001. We lower the sparsity of our network to 70% where our method demonstrates 73.35% topl accuracy and 2.79x speedup. Our method exhibits an obviously better apcer-accuracy tradeoff compared to the Shft_BW. The OVW pattern also achieves a better speedup compared to balanced sparsity while recovering the full accuracy of the original model.
To ensure fair comparison, we reproduce these results under the same setting on Resnet50 and Cifar100, as shown in Fig We fine-tune each network for 40 epochs after pruning from pretrained dense models with the same learning rate of 0.0008. The OVW pattern dominates the speed-accuracy trade-off in vector-level sparsity.
6 Conclusion
Accelerating sparse convolution poses a greater challenge than accelerating sparse matrix multipli- cation. In this work, we propose novel sparsity pattern, the OVW pattern to facilitate the sparse convolution acceleration under intact accuracy. Although, limitations exist that our method relies heavily on the hardware supports for the implicit GEMM convolution algorithm. The performance of our base dense kernel against the commodity unpublished ones unstable. Our method does not acquire the same amount of acceleration rate matrix multiplication and the acceleration rate of our method is subject to filter shape. Its performance also degrades in specialized convolution layers where data reusage opportunity is limited. In consideration of this, our GPU implementation still largely outperforms all sparse acceleration approaches exceedingly with a sparse pattern of similar flexibility. We hope this work can fill the vacancy of specialized sparse convolution kernel design and our methodology can inspire further research this domain.
Acknowledgement
We gratefully acknowledge the support of MindSpore, CANN (Compute Architecture for Neural Networks) and Ascend Al Processor used for this research.
This work is partially supported by the National Key R&D Program of China(under Grant 2017YFA0700902), the NSF of China(under Grants 61925208, 61732020, U19B2019), Strate- gic Priority Research Program of Chinese Academy of Science (XDB32050200), Beijing Academy of Artificial Intelligence (BAAI), CAS Project for Young Scientists Basic (Deearc(YSBBR-22) Youth Innovation Promotion Association CAS and Xplore Prize.
References
[1] MegEngine:A fast, scalable and easy-to-use deep learning framework. 2020.
[2] Cao Shijie, Thang Chen, Yao Zhuliang, Xiao Wencong, Nie Lanshun, Zhan Dechen, Liu Yunxin, Wu Ming, Zhang Lintao. Efficient and effective sparse LSTM on FPGA with bank-

---

balanced sparsity // Proceedings of the 2019 ACM/SIGDA International Symposium on Programagre Gate Arrays. 2019. 63-72.
[3] Gale Trevor, Zaharia Matei, Young Cliff, Elsen Erich. Sparse gpu kernels for deep learning SC20: International Conference for High Performance Computing. Networking, Storage and Analysis. 2020. 1-14.
[4] Gray Scott, Radford Alec, Kingma Diederik P. Gpu kernels for block-sparse weights // arxiv preprint arXiv:171 1.09224. 2.17.3.2.
[5] Guo Cong, Hsueh Bo Yang, Leng Jingwen, Qiu Yuxian, Guan Yue, Wang Zehuan, Jia Xiaoying, Li Xipeng, Guo Minyi, Zhu Yuhao. Accelerating sparse dnn models without hardware-suppee via tile-wise sparsity SC20: International Conference for High Performance Computing. Networking, Storage and Analysis. 2020. 1-15.
[6] Han Song, Mao Huizi, Dally William J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding arXiv preprint 111.v:1510000149. 2015.
[7] Han Song, Pool Jeff. Tran John, Dally William. Learning both weights and connections for efficient neural network // Advances in neural information processing systems. 2015. 28.
[8] He Kaiming, Zhang Xiangyu, Ren Shaoqing, Sun Jian. Deep residual learning for image recognition // Proceedings of the IEEE conference on computer vision and pattern recognition. 2016. 770-778.
[9] Huang Guyue, Li Haoran, Qin Minghai, Sun Fei, Din Yufei, Xie Yuun, Shfl-BW: Accelerating Deep Neural Network Inference with Tensor-Core Aware Weight Pruning // arXiv preprint arXiv:2203.n N.Xv:2203.05016. 2022.
[10] Li Hao, Kadav Asim, Durdanovic Igor, Samet Hanan, Graf Hans Peter. Pruning filters for efficient convnets // arXiv preprint arXiv:1608.08711 10. 2016.
[11] Liu Zhuang, Sun Mingjie, Zhou Tinglui, Huang Gao, Darrell Trevor. Rethinking the value of network pruning // arXiv preprint 1.XYv:18100002700 2018
[12] Ma Xiaolong, Qin Minghai, Sun Fei, Hou Zejiang, Yuan Kun, Yi, Wang Yanzhi, Chen Yen- Kuang, Jin Rong. Xie Yuan. Effective Model Sparsification by Scheduled Grow-and-Prum Methods // arXiv preprint arXiv:2106.098: 09857. 2021.
[13] Malinen Mikko Fränti Pasi. Balanced k-means for clustering // Joint iapr international workshops statistical techniques in pattern recognition (spr) and structural and syntactic pattern recognition (sspr). 2014. 32-41.
[14] Mishra Asit, Latorre Jorge Albericio, Pool Jeff. Stosic Darko, Stosic Dusan, Venkatesh Ganesh, Yu Chong, Micikevicius Paulius. Accelerating sparse deep neural networks // arXiv preprint arXiv:2104.08378 2021.
[15] Pool Jeff. Yu Chong. Channel Permutations for N: M Sparsity // Advances in Neural Information Processing Systems. 2021. 34.
[16] Sui Yang, Yin Miao, Xie Yi, Phan Huy, Aliari Zonouz Saman, Yuan Bo. CHIP: CHannel independence-based Pruning for Compact Neural Networks // Advances in Neural Information Processing Systems. 2021. 34.
[17] Wen Wei, Wu Chunpeng, Wang Yandan, Chen Yiran, Li Hai. Learning structured sparsity in deep neural networks // Advances in neural information processing systems. 2016. 29.
[18] Zhang Xiang, Zhao Junbo, LeCun Yann. Character-level convolutional networks for text classification // Advances in neural information processing systems. 2015. 28.
[19] Zhou Aojun, Ma Yukun, Zhu Junnan, Liu Jianbo, Zhang Zhijie, Yuan Kun, Sun Wenxiu, Li Hong- sheng. Learning n: fine- ane-grrined structured sparse neural networks from scratch // arx preprint arXiv:2 040100 20211
10

---

[20] Zhou Yangjie, Yang Mengtian. Guo Cong. Leng Jingwen, Liang Yun. Chen Quan, Guo Minyi, Zhu Yuhao. Characterizing and Demystifying the Implicit Convolution Algorithm on Commercial Matrix-Multiliiattion Accelerators // 2021 IEEE International Symposium on Workload Characterization (IISWC). 2021. 214-225.
[21] Zhu Maohua, Zhang Tao, Gu Zhenyu, Xie Yuan. Sparse tensor core: Algorithm and hardware co-design for vector-wise sparse neural networks modern gpus // Proceedings of the 52nd Annual JEEE/ACM International Symposium on Microarchitecture. 2019. 359-371.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you's 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "YguWBg_289j", "reviewer": "Reviewer_HQDT", "summary": "This paper aims to speed up sparse convolutional neural networks on GPU devices. Instead of unstructured sparsity pattern, this paper proposes a vector-based sparsity pattern (OVW) to balance accuracy loss and computation efficiency. Based on the OVW pattern, a heuristic clustering method is introduced to obtain an appropriate channel permutation with smaller accuracy loss. Moreover, an efficient CUDA kernel is implemented for OVW-based sparse convolution. Extensive experiments on several network architectures demonstrate the efficiency of the method.", "questions": "- If I understand correctly, the hyperparameter $V$ should be an integer. In table 1, why $V$ is 44.48 (32.02) in the second last (last) row?\n- The proposed OVW sparsity pattern is faster than unstructured sparsity. It would be better to include the comparison with unstructured sparsity in Figure 5.\n", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- This work is clearly motivated. The unstructured sparsity is hard to be accelerated on GPUs, while channel-wise sparsity tends to have a large accuracy drop. The sparsity pattern between these two would have a better trade-off.\n- The proposed vector-based sparsity pattern (OVW) is reasonable and technically sound. It can preserve continuous memory access for efficient GPU implementation.\n- Extensive evaluation and impressive results. This paper demonstrates the power of the proposed sparse convolution on different network architectures, outperforming representative unstructured sparse methods.\n\n**Weaknesses:**\n- The proposed method can achieve practical speedup on V100 GPU. It would be better to verify on more GPU types.\n- The writing should be improved. There are some typos: \nCommon issue: there should be a space before left bracket.\nLine34: Missing citation number.\nLine270: Fig5 -> Fig 5.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8jSLVo7jHb", "reviewer": "Reviewer_C8Jt", "summary": "This paper introduces a new sparse convolution kernel, with the following properties:\n\n* The filters are \"outer-vector-wise\" sparse. This means that the matrix of flattened filters has its columns split into vectors, and each vector is either zero or non-zero.\n* This allows the kernel to use implicit matrix multiplication. (In explicit matrix multiplication the `im2col` operation is used to extract patches of the features map, which are then used in a batched matrix multiply. In implicit matrix multiplication, pointers into the feature map are used instead of explicitly extracting the patches. This is faster.)\n\nWhen compressing a dense network, there are two ways that the sparsity pattern can be optimized:\n\n* The sparsity pattern can be chosen (i.e., which vectors are zero and non-zero, under the constraint that each column of the flattened filter matrix must have the same number)\n* The rows of the flattened filter matrix can be permuted (i.e., the output channels can be permuted), since this doesn't actually change the computation (as long as the next layer's input channels are permuted correspondingly).\n\nThe authors propose a row clustering algorithm which uses k-means to find a permutation of the rows that maximizes the weights of the unpruned entries.\n\nThe results show that this sparsity kernel can reach significant speedups at relatively low sparsity levels. The experiments also show that the test accuracy remains relatively high after pruning and fine-tuning. Lastly, it's shown that the permutations provide a small but consistent improvement in the test accuracy compared to not permuting.", "questions": "**Writing**\n\nOverall the text requires a significant amount of editing. For example, the abstract contains typos (\"re[p]ly on\") and grammar mistakes such as incorrect plurals/singulars (\"pattern[s]\", \"speedup[s]\"), missing articles (\"[the] OVW pattern\"), and incorrect conjugations (\"achieve[s]\"). I found the writing to be meandering and unstructured throughout. As a reader it was often unclear to me what the main point of each section was. I suggest the authors spend some time editing the text for both grammar and structure.\n\nThe text could also be more precise to help ensure reproducibility. Section 4.2 is a particular example of this, with vagues statements (\"kmeans requires additional operations to meet this demand\") and a lack of precision, e.g., \"We employ Kuhn-Munkres algorithm to solve the distance matrix and optimize the mean square error of it\". Which distance matrix? Mean square error of what? None of this seems to appear in algorithm 2.\n\n**Illustrations**\n\nI believe figure 1's illustration of \"inter-vector-wise\" sparsity contains a small mistake (the two top right vectors have 3 instead of 2 unpruned entries)\n\nFigure 2 is confusing to me: The diagram makes it look as if the sparse filter is first densified to then be passed to `load_columns`, the output of which seems the same as the original input `data`? There's a function `recover` which seems to just be `reshape`? And the figure suggests that the feature offsets are a function of the filters' values, whereas they are actually computed based on the row indices (`row_idx`).\n\n**Experimental results**\n\nI believe it would be valuable to perform multiple runs and provide confidence intervals on the presented results, given the small margins (e.g., 65.49 and 65.46 for SqueezeNet OVW permuted/non-permuted).\n\nThe \"V\" in the table of results should probably be explained in the caption. I assume it's the vector length as in the text, but what does it mean for the vector length to be 44.48 or 32.02? And perhaps it is better to move this column to the end of the table, to make it easier to compare the OVW columns to the baseline columns.\n\nThe results are also a bit hard to parse since they require the reader to compare numbers across 6 columns to see which ones are bigger or smaller. Perhaps the authors could report \"drop/increase in accuracy compared to baseline\" instead? And perhaps the columns are better grouped by their sparsity level rather than by the sparsity type.\n\n**Training**\n\nThis paper assumes a setting of dense training followed by compression for deployment. I would be interested to see the authors discuss using these sparse kernels during training as well.\n\n**Title**\n\nThe title of the paper is overly general. Many papers discuss accelerating sparse convolutions after all. Perhaps something along the lines of \"Column-wise sparsity and implicit matrix multiplication for efficient sparse convolutions\" would be more descriptive of the content of the paper.", "limitations": "The authors claim to have discussed the limitations of their method, but it's not clear to me where they did so.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this paper proposes a very neat sparse convolutional kernel. The outer-vector-wise sparsity seems like a good trade-off between fast structured sparsity (e.g., block-wise sparsity) and flexibility (e.g., unstructured sparsity). This works nicely with the implicit matrix multiplication approach, which gives impressive experimental results.\n\nThe main weakness of this paper is the presentation and reproducibility. The writing is not good, which makes it more difficult to follow along than it should be, and the pseudo-algorithms seem to be missing important details required to reproduce their results. Similarly, the figures are not as elucidating as they could be, and the experimental results are presented in a way that is difficult to parse.\n\nAll in all, the amount of editing that needs to be done to bring this paper to a publishable state is on the borderline of what is reasonable to expect from a conference rebuttal cycle. This makes it difficult to recommend this paper as is.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-sksaHLE2eu", "reviewer": "Reviewer_m2da", "summary": "This paper proposes an out-vector-wise (OVW) pattern-based sparse convolution for accelerating neural networks. The proposed OVW pattern can preserve continuous memory access. Moreover, the clustering-based channel permutation method is introduced to reduce error caused by sparsity. The sparse convolution is efficiently implemented using CUDA for GPU acceleration. The experimental results demonstrate the efficiency of the proposed method over unstructured sparsity.", "questions": "please refer to the weaknesses.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The proposed out-vector-wise (OVW) sparse pattern can preserve continuous memory access which is beneficial to GPU acceleration, while unstructured sparsity involves random memory access which is unfriendly for hardware.\n- Sparse model acceleration is an important problem for mobile devices. The proposed method achieves a better tradeoff between inference speed and accuracy over unstructured sparsity and channel sparsity.\n- The clustering-based channel permutation method can reduce error caused by sparsity.\n\nWeaknesses:\n\n- The paper claims that the OVW pattern can achieve a better tradeoff than channel pruning. please add the experimental comparison to evaluate this claim.\n- The hyperparameter V determines the length of a vector. How does it affect the inference speed? It would be better to present an ablation study of it.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept