Complementary Sparsity: Accelerating Sparse CNNs with High Accuracy on General-Purpose Computing Platforms
Authors: Kang Zhao
Yijun Tan
Kai Han
Ting Hu
Hanting Chen
Tao Yuan
Yunhe Wang
Jun Yao
Venue: Accepted by TMLR ()

Abstract: Model sparsity is a promising approach to reducing parameters or FLOPs of convolutional neural networks (CNNs). Compared to unstructured or coarse-grained structured sparsity, fine-grained structured sparsity, e.g., N:M sparse pattern, can achieve a better balance between accuracy and efficiency on general computing platforms like CPUs and GPUs. In particular, the 2:4 sparsity can accelerate CNN inference by 2$\times$ speed and with negligible accuracy drop. However, N:M sparsity needs to be supported by GPU within specific hardware circuits and hardly achieves significant speedups on common GPUs. To accelerate CNNs with general-purposed computing resources and simultaneously retain the model accuracy as much as possible, this paper proposes complementary sparsity (CS). CS denotes that only one weight can be retained for weights spaced at the same distance. On the one hand, CS features high mask flexibility, which is naturally favorable to high model accuracy. Moreover, we propose a CS-specific sparse training method to improve CS-based CNNs' accuracy under high parameter sparsities ($>$75\%). On the other hand, CS itself is memory-access balanced and robust to pattern hyperparameters, which can be utilized to speedup CS-based convolution computation on CPUs and common GPUs. We thus propose a CS convolution parallel computing algorithm that adapts to common GPUs without sparse tensor cores. Experimental results show that compared to other sparsity patterns, the proposed CS can achieve the optimal trade-off in terms of accuracy and latency for CPUs and common GPUs, respectively. Codes will be available at https://gitee.com/mindspore/models/tree/master/research/cv/CS.

Published in Transactions on Machine Learning Research (10/2023)
Complementary Sparsity: Accelerating Sparse CNNs with High Accuracy on General-Purpose Computing Platforms
Kang Zhao
shookng@9@@haauee.cco
Huowei Noah Ark's Lab
Yijun Tan'
tengji198&@gmaii. com
SKL of Processors, Institute of Computing Technology, CAS
Kai Han
kai.han moa.hin@hawweé.com
Huowei Noah Ark's
Ting Hu Huawei Noah Ark's Lab
hutingg8@@huawckkccom
Hanting Chen
chenbontingghhuawe..com
Huowei Noah Ark's Lab
Tao Yuan
yuantao38@haaweei.com
Huawei Noah Ark's Lab
Yunhe Wang!
yunhe. waabe..wnnShhhwwei..c
Huowes Nooh Ark's Lab
Jun Yao
yaojuu.77@huuuee..com
Huawei Noah Ark's Lab
Reviewed on OpenReview: https: // openreview. net/ forum? id- 9184g90w/79
Abstract
Model sparsity is a promising approach reducing parameters and FLOPs of convolutional neural networks (CNNs). Compared to unstructured coarse-grained structured sparsity, fine-grained structured sparsity, c.g., N:M sparse pattern, can achieve better balance be- tween accuracy and efficiency on general computing platforms like CPUs and GPUs. In particular, the 2:4 sparsity can accelerate CNN inference by 2x speed and with negligi- ble accuracy drop. However, N:M sparsity needs to be supported by GPU within spe- cific hardware circuits and hardly achieve significant speedups on common GPUs. To ac- celerate CNNs with general-purposed computing resources and simultaneously retain the model accuracy much as possible, this paper proposes complementary sparsity (CS). CS denotes that only one weight be retained for weights spaced at the distance. On the one hand, CS features high mask flexibility, which is naturally favorable to high model accuracy. Moreover, we propose CS-specific sparse training method to improve Ca-based CNNs' accuracy under high parameter sparsities (>75%). On the other hand, CS itself is memory-access balanced and robust to pattern hyperparameters, making it an ideal candidate for speeding up CS-based convolution computation on CPUs and common GPUs. We thus propose CS convolution parallel computing algorithm that adapts to common GPUs without sparse tensor cores. Experimental results show that compared to other sparsity patterns, the proposed CS achieves the optimal trade-off in terms of accu-
"Equal contribution.
i Coorespponiig author.

---

Published in Transactions on Machine Learning Research (10/2023)
racy and latency for CPUs and common GPUs, respectively. Codes will be available at able impact on CNN's accuracy, while it can significantly lower CNN's number of boating-point operations (FLOPs) during inference.
1 Introduction
Weight sparsification is a crucial method to compress CNNs. The rationality behind weight sparsification is that there are redundant weights in regular CNNs which lend to generate overlapped features (Hoefler) le al. [021] Ayinde et al.) 2019). Thus, removing a certain amount of weights in CNNs has little or manage-
According to the extent of pruning freedom and acceleration affinity, the existent weight sparsification technologies for CNNs can be divided into three categories: unstructured sparsity (US), coarse-grained structured sparsity (CSS), and fine-grained structured sparsity (FSS). US, depicted in Fig. [a], also called
random sparsity some studies (Huang et al.] 2022). permits pruning weights anywhere inside a weight
tensor (Zhu & Gupta 2017
Gale et al., 2019 Mostafa & Wang 2019 Evei al. 2020 Kusupati et al. 2020;
Liu et al. 2021 Ma et al. 2021 Peste et al.) 2021 Tai et al. 2022 Jaiswal et al., 2022 Park & No 2022 Chen
et al. 2021 Li et al. 2022a). Due to US's highest degree of pruning freedom, the most important weights
affecting network quality can always be retained under any sparsity. Hence, unstructurally sparsed networks can preserve a decent accuracy even if sparsity is very high (2 90%). However, the nonuniformity of weight distribution makes it nearly impossible to accelerate US-based convolution on general-purpose computing platforms. In contrast, for CSS, c.g., Fig. (d). the pruning granularity is block, channel, or filter -wise
(Wen et al., 2016 Li et al.] 2016 Gray et al. 2017: Ji
2018 Liu et al. 2017 Tang et al. 2020 Ding
et al. 2021 Hou et al.] 2022 Liu et al. 2022 Chen et al. 2022 Zhang et al., 2022
He & Xiao 2023) CSS's
patterns are generally with high regularity, which can significantly speedup the network inference. For some
of CSS patterns such as filter pruning and channel pruning, i.c., Fig. [c) and [d). the pruned CNNs can directly operate on the original forms without any new acceleration algorithm design. Nonetheless, the relatively bigger pruming granularity inevitably entails that many important weights are removed together with unimportant weights. Under the same accuracy, CNNs within CSS own a lower compression ratio compared to that within US patterns.
In this study, we focus on FSS since it generally results in better tradcoffs between accuracy and efficiency. We classify a sparsity pattern FSS if its pruming granularity is vector-wise (Yao et al.) 2019 Mishra et al. 2021 Huang et al. 2022 Tan et al. 2022 Meng et al. 2020), e.g., Fig. eh). Compared with US and CSS, FSS possesses both high prunability and decent acceleration affinity. However, the existing FSS patterns more or less have some shortcomings, as shown in Table D N:M sparsity, which has been the most popular FSS paltern lately, mainly facilitates inference efficiency on specific hardware, e.g.: Amphere archilecture within sparse tensor cores (Choquette& & Gandhil 2020). Some work tries accelerate N:M-base convolution common GPUs without sparse tensor cores Yao et al., 2019). but the practical specdup benefits compared to the dense convolution are probably limited, since the dense convolution has been adequately optimized and perfectly supported by current common GPUs. Shfll BW Huang et al. (2022) and OVW Tan et al. (2022) sparse patterns achieve practical speedups on common GPUs, but CNNs using these two patterns have not reached a satisficatory accuracy so far.
In this paper, we propose a complementarily sparsed pattern to better balance the accuracy and inference efficiency of sparse CNNs. The design principle behind complementary sparsity (CS) is to leverage the non-conflict strengths of the prior sparse patterns as much as possible while addressing their limitations. Firstly, like N:M sparsity, CS prunes weights inside vector. Secondly, the positions of the pruned weights and retained weights are complementary. For example, Fig. [e) shows 50% CS. In this subfigure, a vector's shape is 8 x 1, as marked by the red frame. The 'complementary" means that inside the vector, if the 1st weight is pruned, then the 5th weight has to be retained. This logic is the same for the 2nd and 6th weights, and so forth. Lastly, the size of a minimum vector to form CS is variable, which property is called hyperparameter robustness. The hyperparameter robustness of CS makes the pattern very adaptive to different computing platforms, such CPUs and GPUs.
2

---

Published in Transactions on Machine Learning Research (10/2023)
Cin H x W
Cin
(a)
(b)
(c)
(d)
Cout
Cout
H
W
Unstructured Sparsity
Block Sparsity
Filter Pruning
Channel Pruning
Cour
Cin
H W
Cin X H X W
Cout x x W
(e)
(f)
(h)
Cin
CoME
Cout
SELE
W
Complementary
OVW Sparsity
Shfl_ BW Sparsity
N:M Sparsity
Sparsity (Ours)
(2:4)
Figure 1: Visualization of different sparse patterns at the 50% sparsity. (a) Unstruct structured spansity
that allows to discard weights arbitratry positions. (b)-(d) Coarse-grained structured sparsity. (e)-(h) Fine-grained structured spansity. In particular, (e) is the proposed complementary sparsity and '2 SELE. 1' represents retaining one from weights in all the complementary positions.
The major contributions of this paper as follows:
We propose sparse pattern-Co CS, which features both high mask flexibility and high acceler- ation affinity. CS allows pruming CNNs with less accuracy reduction and accelerating sparse CNNs on both CPUs and common GPUs.
Used in the training phase, CS-specific sparse training method is proposed to boost CS-based CNNs' accuracy under high sparsities. With the proposed method, CS-based CNNs perform par with or better than that with N:M sparsity in terms of accuracy. At the 50% sparsity on ImageNet, CS-based ResNet50 achieves 76.37% accuracy with negligible accuracy loss. At the 93.75% sparsity, CS- based ResNet50 achieves 71.07% accuracy with a 5.32% drop, which better than N:M sparsified ResNet50 which drops 5.8%.
Used in the inference phase, a parallel acceleration algorithm is proposed to speedup the CS- based convolutions on common GPUs. With the acceleration algorithm, CNNs within CS achieves 2.59x-3.07x speedups at the 93.75% sparsity over the dense counterparts supported by cuDNN.
Through the algorithm-softwal co-optimization, the proposed CS reaches better tradcoff's between sparse CNNs' model quality and inference elficiency compared with other fine-grained structured sparse patterns. To be clear, the advantages of our CS over similar works are shown in Table [
2 Related Work
Unstructured sparsity (US) Neural networks within US have been researched for long time. The winning ticket hypothesis denotes that there always exists sparse neural network inside a dense network and the subnetwork can be trained to reach the comparable accuracy as the dense one (Frankle & Carbin 2018). Since the hypothesis was proposed, a surge of studies have focused on developing good pruning methods to form US. Gale al. (2019): Zhu Guptal (2017) improve the magnitude-based pruning methods simply by gradually sparsifying and prolonging the training time, respectively. Rather than fully training
dense network before pruning, Mostafa & Wang 2009): Evei et al. (2020): Ma et al. (001) ) adopt the

---

Published in Transactions on Machine Learning Research (10/2023)
Pattern
Accelcration w/o ASICs
Accu.
US
Almost impossible
High
Block sparsity
Yes
Low
Filter pruming
Yes
Low
Channel pruning
Yes
Low
N:M et al. [2021]
Hard
High
Shfll BWTunag et a.. 2202
Yes
Medium
OVW Tan et al. 2022
Yes
Medium
CS (Ours)
Yes
High
Table 1: Comparison among different sparse patterns.
sparse training to directly generate the unstructured sparse neural networks. These sparse training methods basically contain a common mechanism that periodically prunes and regrows some weights according to some critcrion. Furthermore, Poste et al.] (2021) p alternatively conducts sparse and dense training. In this way, both dense and unstructured sparse neural networks are generated after training. Instead of pruning weights by carefully designed criterion, [usupati et al. [2020] Tai et al. (0022) learn the sparse masks by differentiation. In particular, the proposed method in Tai et al. (2022) reports the state-of-the-art accuracy of US-based CNNs on the ImageNet dataset. Generally, CNNs within US can not obtain significant speedup
gains on CPUs and common GPUs due to the severe memory-access conflict.
Coarso-grained structured Sparsity (CSS) Normally, CSS can be enforced along either the input or output axes of a weight tensor. Separately shrinking the output and input axis is called filter and channel pruning, respectively. Pruning square block in both input and output axes is called block sparsity (Gray et al. 2017). To our knowledge, Wen et al. (2016) is the first to propose filter pruming channel pruning for CNN compression. In their study, the group LASSO method is directly enforced into weights to induce sparsilies among filters or channels. Some studies like Liu et al. (2017); Ding et al. (2021) employ extra indicators to evaluate the filters, e.g., scaling factors in batch normalization layers, or properly placed 1 x 1 convolutions that can be absorbed during inference. Since pruning filters also result in pruming the related channels in the next layers, the proposed method in in et al. (2016) jointly considers the impact of filter and channel pruning on network accuracy. Rather than developing various hypotheses to measure the importance of filters, Tang ct al. (2200) assossos filters by observing the network responses to real data and adversarial samples. Besides, some principles originally used for US have lately been introduced to realize CSS, e.g., Hou et al. (002)) Tai et al. (2022). Despite these efforts, CSS-based CNNs' accuracy is still relatively lower and drops drastically espocially when the required sparsity> 70%.
Fine-grained structured sparsity (FSS) N:M sparsity is a well-known fine-grained structured sparse pattern where at most N non-zero weights are retained for every continuous M weights (Yao al.) 2019 Mishra et al.] 2021 Lu et al.) 2023; Zhang et al. 2023). However, N:M sparse pattern needs to be supported by GPUs embedded with sparse tensor cores. On common GPUs, the pattern hardly outperforms dense convolutions supported by cuDNN. To tackle the problem, Shfll BW and OVW sparsity regard M x 1 vector as an entirety which is pruned or retained together (Huang et al. 2022 Tann et al.] 2022). By this design, the retained weights and the related features during convolution computation can be casily indexed. Thus, Shfl. BW and OVW sparsity can accelerate convolutions on common GPUs to a great extent. However, the relatively large pruning unit of M x still decrcases the ficxibility (Hubara et al. 2021), which results in reduced model accuracy. In contrast, our CS can help maintain similar or better model accuracy relative to N:M sparsity, as well achieve the practical speedups of sparse convolutions on common GPUs and CPUs.
GPU acceleration for convolutions So far, there are basically four sorts of parallelable algorithms to implement convolutions: direct convolution, Winograd (Chikin & Kryzhanovskiy 2022). FFT (Wang el al. 2020), explicit general matrix multiplication (GEMM) (Jiang et al. 2022) and implicit GEMM (Zhou et al, 2021b). Among these, GEMM-base convolution algorithms are more performant on GPUs since the modern
2014 Jorda al., 2019 Li et al. 2022b). However, explicit GFMM-basee convolutions need to firstly invoke img2col to change
parallel computing platforms have highly optimized the GEMM operations (Chetlur et al.
4

---

Published in Transactions on Machine Learning Research (10/2023)
tensors to matrices, which is memory access-intensive and time-consuming. By contrast, implicit GEMM- based convolutions remove the memory access overheads, which is top-performed in most cases. Moreover, Tan et al. (2022) employs the implicit GEMM to accelerate sparse convolutions, which implies the potential of implicit GEMM to speedup other sparse patterns. In this work, the implicit GEMM also utilized to develop the parallel acceleration algorithm of CS- convolutions on common GPUs.
3
Method
3.1
Complementary Sparsity Formulation
For a sparse weight. tensor W with the shape of Cout Cin. Fn, Pw,, each filter W; has the shape Can X F P.. and is flattened. We use Wi[j] to denote the jth weight in the flattened W, S is the sparsity of the weight tensor. Two key parameters are introduced to conveniently describe CS: 1) K. K denotes the amount of the complementary positions from which only one single weight should be selected. For instance, at the 50% sparsity, there should be K = complementary positions for selecting a weight. for the 75% sparsity, there are K = 4 complementary positions from which a weight is selected. 2) M. M represents the address offset with which weights in the complementary positions can mutually be located. Specifically,
1
K
(1)
1-S
L M
K' E (Cmn/c, Cin Fb Fw}
(2)
In Equation 2 if I. Cin/c, the typical values M include 2,4,8, 16. Here e only means that Cin should divisible by M. Then, a sparse weight tensor regarded as complementarily sparsed as long as for any i.li E [1, Coul,, j E MJ,
|W W + 1 M., 1)) MJ]o < K
(3)
Furthermore, a sparse weight tensor is regarded strictly conforming to the pattern of CS if and only if
[[&b]) Wili + M.ljj + (K - M]
(4)
To intuitively understand the definition of CS, Fig. gives some examples strictly obeying the pattern of CS across multiple sparsities. Accordingly, the parameter values, i.e., K and M of each example, are listed in Table 2 Note that K is only related to the specified sparsity S and is independent of the specific weight tensor shapes. Unless otherwise specified, the rest of the paper only discusses the strict CS.
(a)
0.8
0.1
0.2
1.5
1.2
0.4002
0.5
(b)
0.8
0.1
0.2
1.3
0.40.2
0.5
1.0
(c)
0.8
0.2
1.5
1.3
0.4
0.2
0.5
1.0
(d)
0.8
0.8
0.2
1.5
1.2
1.3
0.4
0..2000
0.7
2.0
0.9
0.5
1.0
0.3
2.1
1.4
(e)
0.8
0.1
0.2
0.4
2.0
0.5
1.0
0.3
2.1
1.4
Figure 2: Examples of CS at different sparsities. The blue shading of (b)-(e) indicates the selected weights, (a) a dense weight tensor. For convience, the tensor is 2D and with the shape of 1 x 16, i.c., Cout and Cmn Fj Fu 16 (b) The 50% CS of the weight tensor. (c) The 75% CS of the weight tensor. (d) The 87.5% CS of the weight tensor. (e) The 93.75% CS of the weight tensor.

---

Published in Transactions on Machine Learning Research (10/2023)
Table 2: Parameter values of the examples shown in Fig. 2
Sparsity
Encoding bit number
Encoding
K
M
(%)
results
50
2
8
1
0,1,1,0,0,0,1,1
75
4
4
2
1,2,3,0
87.5
8
2
3
7,4
93.75
16
3.2 CS-specific Gradual Sparse Training Method
The aim of designing CS-specific sparse training method is to attain universality. That is, the desired training method can improve the accuracy of various CS-based CNNs among different sparsities. With the training method, users do not need to customize training recipes for different CNN structures.
Conventionally, training a sparse neural network follows the process of dense training, single-shot pruming, and finetuning. We argue the conventional training process unfavorable to CS-based CNNs under high sparsities (> 75%) in which case the derived sparse masks from the dense weight tensors tend to be subop- timal. In contrast, we propose two-phase training scheme: gradual sparse training followed by retraining. As demonstrated in Algorithm [ assuming that the allowed training iteralion amount in each phase is I, the first phase starts training with dense network and the sparsity of the network discretely steps up every P iterations. The completion of the first phase offers the sparse masks conforming to the pattern of CS and the weights as the initialization of the second phase. The second phase simply uses the same training setups as the first phase to retrain the retained weights in networks selected by the sparse masks. Obviously, the novelty of our training method mainly lies in the first phase. The first phase comprises two features as detailed below.
Variable number of steps for gradual sparsification. By empirical observation, we find the higher the required sparsity is, the more steps for gradual sparsification are needed to obtain the better model quality. Hence, to obtain a CS-based CNN at the sparsity S, we set K steps for gradually sparsifying the network. For instances, in case that the target sparsity is 75%, the change of sparsities during training in the first phase 0% + 25% + 50% - 75%, while for the target sparsity of 87.5%, the change is 0% + 12.5% > 25% + 37.5% + 50% + 62.5% 75% + 87.5%. To be formulated, for the ith training iteration, the desired sparsity S is:
S. ceilingft & K} 1
K
Equation 5 intuitively means that S, performs the piecewise linear growth as training iterations. The position of Equation 5 in the workflow of our training method is shown in Algorithm D Note that gradual sparsification only means the amounts of weights participating in the forward passes are gradually and discretely reduced. During backward passes, the gradients of all the weights are computed and every weight is updated no matter which sparsity step network is at.
CS-specific weight reselection. Since all the weights are kept updating in the first training phase, it is beneficial to reselect the weights, i.e., update the sparse masks once in a while. Supposing every F iterations, the sparse masks should be updated. The update process for CS is: 1) Reshape. A weight tensor with the shape Cout x Cin X Fn x Fu is reshaped into G x K x L, where K and L is defined in Equation ! and 2 respcctively. G can be inferred given K and L. 2) Reselection. Along K axis to reselect k; weights with the highest absolute value. k is related to the sparsity step that a network is at, i.e.,
k; (1- K
(6)
The positions of the reslected weights in masks are set ones while the other positions are set zeros. 3) Restoration, which means inversely reshape the weight tensor from x x back to Cout x Cr x Fn x F... Fig. 3 shows an example of the CS-specific weight reselection procedure, which mainly visualizes the step 2). Notably, the gradual sparsification exactly achieved by our weight reselection procedure by properly setting F to make P divisible by F.
6

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 1 Workflow of Our Training Method
Initialization: Dense weights W
Input: Required sparsity S, training ilerations 7, data D
Output: Sparse weights W
Key params: K, sparse mask M, mask updating freq. F
1:
Gradual Sparse Training Phase
2: for i 0 " do
3:
if 1%F then
4: S,+-Equatio 5i,,,
5: M + Weights Reselect( S;, W
6: end
7:
(Wr M, 1))
Backward(W; D)
Weights (igghttsUpddtteW)) #Update all weights
10:
end for
11:
Retraining Phase
12: for - 0; < ite; + + do
13:
Forward(W: M)
14: Backward (.W. M,, D)
Weights Update(W, M) #Update selected weights
16: end for
17:
18: W t W
M
-12
0.2
1.2
2.0
-2.1
0.1
1.4
2.9
P
S
Sz 25%
k,
0.4
1.2
-03
1.9
iterations
0.3
0.2
-022
1.4
3
1.0
-23
0.8
-2.3
1.1
-13
0.9
-2.1
K
-0.9
2.0
0.2
-0.7
-0.7
1.0
0.1
-0.6
Selected weight
After iterationn
Pruned weight
-1.2
-011
1.2
2.0
After iterations
-1.3
-0.1
1.8
1.0
S, 75%
0.3
-.3
-0.1
1.3
0.3
-0.3
-0.1
1.3
S3 50%
Rg 1
2
1.0
-2.3
0.8
-2.3
1.1
-2.9
0.4
-2.7
-0.6
2.0
0.1
-0.6
-0.6
1.0
0.1
-0.6
Figure 3: An example of CS-specific weight reselection.
3.3 Acceleration of CS-based Convolution
The obtained sparse weight tensors after training are stored in the compressed format. That is, only the non- weights and their indices are stored and used for inference. This procedure is formulated by, converting w to W and Idr, where W is the non-zero weight tensor with the smaller shapes and Idr is the index tensor. The index of a non-zero weight denotes the weight's position number among K complementary positions, thus the value an index is constantly less than K. Fig. ! exemplifies the compression of CS at the 50% sparsity. In this casc, the T has half of the shape than WS Although Idr has the same shape as W', each index in Idr can be encoded with very low numbers of bits. As shown in Table 2 only at most bits needed to encode non-zero weight's index.

---

Published in Transactions on Machine Learning Research (10/2023)
Non-zero weights (uniform)
-1.2
0
1.2
-1.2
-2.3
1.2
1.9
0
0
1.9
-0.9
2.0
0.4
-2.3
-2.3
0
-2.3
0
1
0
-0.9
2.0
0.4
1
Index
Figure 4: A diagram of CS compression at the 50% sparsity.
After acquiring Wa and Idz, given an input activation X, the output featuremap Y can be computed in parallel. Contrary to the conventional method of feature reuse to speedup sparse convolutions TTan et al. (0022) on common GPUs, we propose a weight reuse-based algorithm. In implicit GEMM-bbaee dense convolutions, each thread is generally in charge of a subblock Y, c.g,, of size 4. Then,
Yi444::44 Σ W Wi++4,n Xnjej4
In Equation 7 L is only equal to On * Fi Fw for GPUs, and @ represents the outer product operation of two vectors. When CS-based convolution is conducted, Equation 7 can be modified into:
Y64449-44
Σ
W X ((.i)di4
(8)
n=
where
f(n ((n,t)=n =
M Idali: i nl
(9)
and in Equation g denotes the operation:
W; * X 111
W * Xn+ 1.
(10)
W.42 X Me
W,43 Xx+ M
Equation S makes it possible to compute CS-based convolutions by chunk. For non-zero weight, there are K related sub-blocks in an imput activation that may be indexed during convolution. On common GPUs, by loading all the related K sub-blocks to GPUs' shared memory in advance, Equation can be conducted efficiently. Algorithm shows this parallel acceleration process, where 50% CS-based convolution is taken for example.
On CPUs, the direct method is employed accelerate CS. Due to the instruction limit, CPUs can hardly fetch multiple values far apart from each other. Accordingly, CS allows different values of M without reducing network accuracy, which is very friendly to CPU operation. During convolutions, CPUs conduct sparse vector products along the Cin axis. In this case, L = C.n/c.
4 Experiments
4.1 Datasets, Models and Settings
CIFAR100 Krizhevsky el al. (2009) and ImageNet-lk Deng et al. (2009) are two datasets used to test the accuracy of CS-based CNNs. Specifically, on CIFAR100, we evaluate three classical CNNs including VGG-19 Simonyan & Zisserman (2014), ResNet-18 and ResNet-50 He al. (2016). and two parameter- efficient CNNs including MobileNetv2 and SqueezeNet Sandler al. (2018); Iandola et al. (2016). Since CIFAR100, low sparsities (S 75%) may result. in insignificant accuracy differences between CNNs with

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 2 Parallelization for 50% CS-based convolution
Input:
Idx, W, X
Output: Y
Key params: M,L
Shared float4 local_ w. Lololool_iae
Shared float4 local x[2],locut
Parallelism
2: for all N *0C* OH OW/16 threads do
3: Subblock(Y) < SUBCONV( thread[i], ddx, W, X
4: end for
5:
Delails
6: function SUBCoNv(tid, Idr,W, ,X)
7: for i= L;i+ BM do
8: local _filtr + Subblock(filter
local idr Subblock
10: local xz[0] + Subblock
11:
local _x[1] t Subblock2(X)
12:
Syncthreads();
13:
local_1 = Eq. local w, local x, local idr)
14:
end for
15: return local_
16: end function
our CS and with other sparse patterns, we test the three classical CNNs under high sparsities: 87.5% and 93.75%, while for MobileNetv2 and SqueezeNet, accuracy results under the 50% and 75% sparsities are adequately distinguishable for comparison. At each sparsity, each CNN is sparsified by US, filter pruning, N:M, OVW, and CS, respectively. All the sparse CNNs are firstly trained with the same training paradigm: dense training, pruning, and finetuning. This paradigm has been widely used to form various sparse CNNs. For simplicity, the finetuning phase uses the same setting as the dense training phase, which has been verified as reasonable in Mishra et al. (2021). After that, CS-based CNNs are trained with the proposed CS-spocific gradual training method for comparison. All the trainings use the common and the same settings. The total training epoch is 400. For the conventional training paradigm, the dense training phase uses 200 epochs and the finetuning phase uses the rest. Similarly, for our CS-specific gradual training method, cach training phase equally uses 200 epochs as well. Each experiment is repeated three times and all the experimental results CIFAR100 are listed in the format of "mean standard deviation to reduce the influence of random factors.
On ImageNet-lk, CS-based ResNet-50 at different sparsities are trained for comparing with other related works. We use the officially recommended hypermeter settings for our sparse training method zlm (2022) Besides, the speedups of CS-based CNNs over the dense counterparts are measured on an Intel(R) Xeon(R) Gold 6154 CPU and Tesla V100 GPU without sparse tensor cores, respectively.
4.2 Results on CIFAR100
Table shows the accuracy of different networks within different sparse patterns on CIFAR100. Firstly, for the three classical CNNs, our CS achieves the best accuracy under high sparsities among all the sparse patterns. Secondly, for MobileNetv2 and SqueezeNet, our CS also outperforms other fine- ane-ggrieed structured sparse pattern at the 75% sparsity. In particular, the accuracy of MobileNetv2 within CS at the 75% sparsily is even higher than that within the unstructured sparsity, i.e., 62.63%>>61.77 7..7%. Thirdly, the proposed training method significantly improves the accuracy of a series of CS- baseb CNNs, with the average accuracy increasing from 0.48% to 2.83%. Notably, at the 50% sparsity, all types of sparse patterns lead lossless accuracy. In this case, we argue the accuracy differences among the patterns and training methods are immaterial.

---

Published in Transactions on Machine Learning Research (10/2023)
Spa. (%)
VGG19
Resnet18
Resnet50
Spa. (%)
Mobilenetv2
SquoozeNett
Origin
70.8
74.7
72.2
Origin
65.3
65.1
Unstructared
71.3++0.1
73.3+0.1
0.3
Unstructured
66.9+-0.1
67.7+-0.2
Filter pruning
47.8+0.6
59.0
48.4=1.0
Filter pruning
65.5
36.410.2
N:M(1:8)
70.6#0.1
72.9:0.11
72.1=0.1
N:M(2:4)
66.4+0.3
67.210.1
50
87.5
OVW
63.610.3
64.110.7
59.2=1.6
OVW
61.8+0.3
64.020.4
CS-C
70.7+00.2
73.0+-..1
72.5=0.3
CS-C
66.4+0.1
67.2+0.1
CS (Ours)
71.7.1.33
73.5+0.11
73.1+0.0
CS (Ours)
66.710.2
67.0
A
+1.4
+0.5
+0.6
A
+0.2
-0.2
Unstructured
69.810.1
71.510.0
71.320.0
Unstructured
61.7400.1
64.510.22
Filter pruning
33.2+0.4
47.9+0.4
40.0=0.6
Filter pruning
53.4+1.1
15.9+0.2
N:M(1116)
68.1+0..3
70.4+0.2
70.6
N:M(1:8)
58.9+0.4
63.4
93.75
OVW
59.610.2
60.6+0.3
41.0
75
OVW
Failed
54.61009
CS-C
68.5+0.2
70.5+0011
70.5=0.2
CS-C
59.8+0.1
63.9+0.3
CS (Ours) A
69.9
72.2+0.3
73.0+0.33
CS (Ours) A
62.6+0.2
64.4
+1.4
+1.7
+2.5
+2.8
+0.5
Accuracy of sparse CNNs CTFAR100. 'Spa.' means sparsity. 'CS-C' represents CS-based CNNs formed by the Conventional training paradigm, while CC (Ours)' means that formed by the proposed training method. 'A' means the difference between 'CS-C' and 'CS (Ours): For spatial brevity, all the data are rounded to one significant digit.
Table 3:
Apart from Table the experimental results on CIFAR100 using the same network for all sparsity ratios are shown in Figure It is observed that the curves of our CS generally above the curves of other structured patterns and are overlapped with curves of unstructured sparsity. That observation further demonstrates the superiority of our CS in terms of accuracy across all the sparsity ratios.
(a)75
(b)
(c),
ResNer18 hiccurac(99)
70
ResNet50 Accuracy| ())
70
VGG19 Accuracy(S)
65
65
60
55
Unstructured
Unstructured
55
Unstructured
Structured
Structured
Structured
45
N:M
N.M
50
N.M
OVW
OVW
CVW
40
45
CS-C
CS-C
CS-C
35
CS(Ours)
CS(Ours)
40
(S(Ours)
AM
MM
AM
50
75
87.5 93, 75 100
0
50
75
87.5
100
50
75
87.593.75 100
Sparsity(%)
Sparsity(%)
Sparsity(%)
Figure 5: Accuracy sparsity curves of different CNNs whitin different sparse patterns. (a) VGG19. (b)
R8sNet18, (c) ResNet50.
Notably, on CIFAR100, our CS performs even better than unstructured sparsity due the relatively small dataset size. Generally, compared to modern DNNs' capacity, CIFAR100 is easy to be overfitted. Thus, within certain sparsity range, weight sparsification can largely regularize the model capacity and lead to higher accuracy over dense counterparts (Hoefler et al. 2021). Compared to unstructured sparsity, fine- grained structured sparsity such as CS and N:M constrains a model more strictly. This constraint generally endows the model favorable regularization on small datasets like CIFAR100 and at low sparsity like 50% and 75%. For example, as shown Figure 7, at 50% sparsity for VGG19 on CIFAR100, N:M sparsity leads 73.00% accuracy, which is better than 72.82% of unstructured sparsity. At 75% sparsity, our Ca-based VGG19 reaches 72.51 % accuracy, while unstuurd sparsity-based VGG19 is 72.13%.
10

---

Published in Transactions on Machine Learning Research (10/2023)
Under higher sparsity such 93.75%, despite the rare possibility of overfitting, the accuracy gap between fine-grained structured patterns like 'CS-C' and 'unstructured" was still narrow due to the small dataset size. Hence, with our proposed training scheme, 'CS(Ours) can easily fill the gap to further become on par with or to even surpass 'unstructurod.. By contrast, on ImageNet, our CS and other fine-grained sparsity patterns bring constantly lower accuracy than unstructured sparsity regardless of sparsity rat and network architectures.
4.3 Results on ImageNet
Table 1 shows the experimental results on ImageNet. Compared with the OVW and Shfl BW patterns, our CS with the proposed training scheme leads to better accuracy under high sparsities, c.g., 93.75%. For other sparsities, our CS achieves comparable accuracy with the state-of-the-arl N:M sparsity. However, the different settings of M in N:M sparsity significantly affect the network accuracy, e.g., Sun et al. (2021). On the contrary, our CS is robust to the pattern hyperparameter setting which will be shown in the ablation
study.
(xror(%)
Params
Flops (G)
Pattern
Spansity
Ori.
Pruned
Gap
(M)
N:M
2:4
77.3
77.0
0.3
13.8
2.15
OVW
50%
76.12
75.76
0.36
13.8
2.15
CS(Ours)
50%
76.39
76.37
0.02
13.8
2.15
N:M
1:4
77.3
75.3
2
7.93
1.17
OVW
70%
76.12
73.35
2.77
9.14
1.37
CS(Ours) 75%
76.39
75.18
1.21
7.93
1.17
Shfl. BW
80%
N/A
75.94
N/A
6.78
0.98
CS(Ours) 87.5%
76.39
72.44
3.95
5.02
0.69
N:M
1:16
77.3
71.5
5.8
3.52
0.44
Shftt BW
90%
N/A
73.09
N/A
4.43
0.59
CS(Ours) 93.75%
76.39
71.07
5.32
3.52
0.44
Table 4: ResNet50 accuracy comparison among different fine-grained structured sparse patterns on Ima- BW
geNet. The results of N:M, OVW, and Shft BW are from Zhou et al. (2021a), Tan et al. (002 and Huang
et al. 2022), respectively. 'N/A' means the related work does not report the result.
Besides, although this work mainly focuses on CNNs, we also give the preliminary results CS and N:M sparsity on Transformer structures as shown Table 5 The DeiT-small is used and the training settings of CS-based DeiT-small and N:M-based DeiT-small are identical. That is, our proposed training scheme is not used this time for an absolutely fair comparison. Experimental results show once more that our CS also incurs comparable accuracy as N:M sparsity on Transformer architectures. Note that at 50% sparsity, surpass the dense one, so the difference between the two sparse
both N:M sparsity and CS -based patterns at 50% sparsity is trivial.
With the experimental results of CNN and Transformer architectures, we would like to reaffirm that our CS mainly achieves comparable accuracy to N:M sparsity under identical training settings. The role of our proposed training scheme is only improve a CS-based network's accuracy under high sparsity ratios. For instance, 93.75%, 5e within CS surpasses that within N:M sparsity by a decent margin, ie., -0.5% ImageNet as shown before in Table In other words, better acceleration affinity CPUs and common GPUs under comparable accuracy, is truly our CS's advantage over N:M sparsity.
Finally, due to the slow progress in the explainability of DNNs, the model accuracy of CS lacks clear theoretical support. However, we found metric called mask diversity that may provide some insights (Hubara et al., 2021). The metric defined the number of possible masks for sparse pattern given a sparsity ratio. For example, for a 8 weight tensor and 50% sparsity, our CS has 2 4, 294, 967, 296 possible masks, while other vector-wise sparsity such OVW can only have (16) 12870 masks, not to
11

---

Published in Transactions on Machine Learning Research (10/2023)
mention only (+) 70 masks that channel pruning can provide. Altogether, CS's high mask flexibility probably promotes the high accuracy of CS-based CNNs.
Sparsity(%)
50
75
87.5
93.75
N:M
77.61
73.69
67.56
60.08
CS(Ours)
77.4
73.66
67.63
60.01
Table 5: Comparison between CS and N:M sparsity using Top1 accuracy of DeiT-small ImageNet. The dense DeiT--mall is 75.56%.
4.4 Ablation Study
Firstly, we investigate the effect of different mask updating frequencies in our training method, i.c., F mentioned in Algorithm [ on network accuracy. The results are shown in Table In the table, F means updating the mask once for every iteration, J' 0.5 means that updating frequency is 0.5 epoch, and on. We find that the higher the required sparsity is, the higher the mask updating frequency should be. For example, at the 50% sparsity, = is the best, while at 93.75%, F outperforms others. The F settings in Table 0 is exactly used in training CS-based ResNet50 on ImageNet. Secondly, we investigate pattern hypermeter of CS: M. Specifically, under the same sparsity decided by K, CS-based CNNs with different settings of M are trained and we conduct pairwise t-test on these CNNs' accuracy. As shown in Table 7 all the p values are larger than 0.05, which indicates that our is robust to pattern hyperparameters. The robustness is quite beneficial for accelcration as CPUs and GPUs can employ different values of M the respective constraints in memory access and instruction set.
F
50%
75%
87.5%
93.75%
0
74.7
74.14+2.63
73.44=0.19
72.06:10.38
0.5
74.78=00009
74.55++0.06
73.57+0.277
71.9+0.52
1
74.6
7..37
73.47:10.6
71.62:1.22
2
74.71=0.24
74.12+0.23
73.16=0.37
71.19::0.59
4
74.85=0.08
74.21=0.08
72.85=0.23
70.85+0.48
8
74.93++0.37
74.28+0.21
72.54+0.61
70.47++0.17
10
74.66=0.19
74.5=+0.19
73.06+0.17
70.14+0.09
Table 6: ResNet18 on CIFAR100: Impact F across sparsities.
Sparsity
(M, K)
VGG19
ResNet18
ResNet50
Sparsity
(M, K)
MobileNetv2
SqueezeNet
(2,8)
71.28:10.15
73.68:0.32
73.46:L0.85
(2,2)
66.8110.14
67.1910.229
(4,8)
71.4640.49
73.2+0.39
73.2340.65
(4,2)
66.65=0011
67.07=00.04
87.5%
50%
(8,8)
71.55+00.9
73.47=00116
73.38+00.39
(8,2)
N/A
67.27+00.09
t-test
0.77
0.29
0.82
t-test
0.18
0.57
(2,16)
69. 29.622-0.09
71.89-0.119
72.23=1.4
(2,4)
62.72:0..1
64.26+00.07
93.75%
(4,16)
69.76++0.19
72.22+0..9
72.56+00.11
75%
(4,4)
N/A
64.3++0.22
t-test
0.31
0.39
0.71
t-test
N/A
0.7
Table 7: Accuracy of CS- bssbased CNNs with different settings M on CIFARI00
4.5 Results on Speedups
On CPU, M set 2,4,8,16 on demand. On GPUs, we set M as large as possible, i.e., M Cin * FA Fw/K We find that the larger M makes indexing more casier on GPU. Fig. Gishows the normalized speedups on CS. Firstly, three typical convolutions in ResNet50 are used for test speedup. As shown in Fig. G(a), with batch size equal to 1, CPU achieves 4.27x, 5.46x and 7.7x speedups for the 3rd, 11th, 41th convolutions at the
12

---

Published in Transactions on Machine Learning Research (10/2023)
(a)*
(b)4.0
(C) 3.0
Dense
cuDNN
cuDNN
Conv3
Conv3
V5G19
3.5
Conv11
Conv11
ResNet50
CPU 5peedup
Conv41
GPU Speedup
3.0
Conv41
GPU Speedup
2.5
SqueezeNet
2.5
2.0
1.5
1.0
1
1.0
AM
AM
M/
0 50
75 Sparsity(%)
87.5 93.75 100
50
75 (parsity(%)
87.5 93.75 100
50
75
87.5 100
Sparsity(%)
Speedups for CS. (a) CPU speedups for three CS-based convolutions in ResNet50. (b) GPU speedups for three CS- basbased convolutions in ResNet50. (c) GPU speedups for three CS-based CNNs.
Figure 6:
75
50
87.5
Shfi_BV
60
OVW
1
75
70
93.75
C5
Filter pruning
Accuracy drop
2
80
3
4
90
5
95
7
75
2
5
Speedup
Figure 7: ResNet50 CIFAR100: Normalized accuracy-speodup curves of three fino-grained structured sparse palterns. Note N:M sparsity does not have acceleration gains common GPUs.
93.75% complementary sparsity, respectively. Similarly, shown in Fig. 6 b). with batch size equal to 64, GPU respectively achieves 4.02x, 3.33x and 2.52x speedups at 33.75% over dense counterparts supported by cuDNN. Secondly, we also estimate the speedups on net workk--leeel by averaging all the convolutions' runtime. GPU achieves 2.75x, 3.07x, and 2.59x speedups for VGG19, ResNet50 and SqueezeNet, respectively. These speedup performances prove the efficiency of the proposed parallel acceleration algorithm. In addition, our CS generally reaches better accuracy-spaa speedup tradeoffs compared with the OVW and Shft BW pattern, shown in Fig. 7
4.6 Results Practical Inference Performance
Table shows the speedup comparison of CS and N:M sparsity on A100 and V100 GPUs, respectively. Note that the speedup data of N:M sparsity are directly cited from A100 materials that are publically available. Although A100 GPUs have far stronger computing power than previous ones, it is noteworthy that A100 GPUs quite inflexible as it can only support the acceleration of 2:4 sparsity. Other sparsity ratios, such as 75% (1:4), 87.5% (1:8), and 93.75% (1:16) can not incur any speedups on A100. In contrast, our CS supports a wide range of sparsity ratios on common GPUs.
13

---

Published in Transactions on Machine Learning Research (10/2023)
50%
75%
87.5%
93.75%
N:M
(A100)
CS
1.39
1.86
2.48
3.07
(V100)
Table 8: ResNet50 speedups comparison different sparsities on V100 and A100
In addition, CS-based ResNet50 inference energy consumptions at different sparsities are shown in Table
As the sparsity ratio arises, the reduced FLOPPs efficiently convert to the shorter inference time. At the 93. 75% sparsity and 64 batch size, CS-based ResNet50 only consumes 3.28J energy for one inference, which is energy-cffciennt for cloud server scenarios.
Sparsity(%)
Gilops
Times(ns)
Energy cost (J)
50
2.15
28.98
7.25
75
1.17
21.59
5.4
87.5
0.69
16.24
4.06
93.75
0.44
13.12
3.28
Table 9: Energy consumption of ResNet50 within CS pattern. _ice 64
5 Conclusion and Future Work
We propose novel CS to accelerate sparse CNNs CPUs and common GPUs and retain the network accuracy as much as possible. To our knowledge, we are the first to report the practical speedups on both CPUs and common GPUs for a sparse pattern. Not only does the proposed CS feature high mask flexibility that contributes a lot to sparse CNNs' accuracy, but also the network accuracy is robust to pattern hyperparameters. The robustness enhances CS's adaptability to different computing platforms.
we would like to denote that the limitation of our proposed training scheme for CS is that the scheme is hardly viable for massive pretraining data. It is because our training scheme needs to be embedded into the pretraining stage and huge amounts of pretraining data make it actually impossible to replicate the pretraining. Thus, it is difficult for our scheme to be applied in scenarios such as LLMs. However, argue that the limitation does not disqualify our major contributions for CS and we will handle the limitation in future work.
6 Acknowledgement
We gratefully acknowledge the support of MindSpore (Hua 2020 CANN (Compute Architecture for Neural Networks) and Ascend AI Processor used for this research.
References
Huawei, mindspore, 2020. MindSpore MindSpore.https:// https::/ww..iidspprr cwt.hddspprreec.c....
Image classification reference training scripts, 2022.
referreccesCCaassiffcccccoo
Babajide O Ayinde, Tamer Inanc, and Jacek M Zurada. Regularizing deep neural networks by enhancing diversity feature extraction. JEEE transactions on neural networks and learning systems, 30(9):2650- 2661, 2019.
Tianlong Chen, Xuxi Chen, Xiaolong Ma, Yanzhi Wang, and Zhangyang Wang. Coarsening the granularity: Towards structurally sparse lottery tickets. In International Conference on Machine Learning, pp. 3025- 3039. PMLR, 2022.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Tianyi Chen, Bo Ji, Tianyu Ding, Biyi Fang, Guanyi Wang, Zhihui Zhu, Luming Liang, Yixin Shi, Sheng Yi, and Xiao Tu. Only train once: A one-shot neural network training and pruning framework. Advances in Neural Information Processing Systems, 14:19637-196511, 2021.
Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and Evan Shelhamer. cudnn: Efficient primitives for deep learning. arXiv preprint Xiv:::1400. 2014.
Vladimir Chikin and Vladimir Kryzhanovskiy. Channel balancing for accurate quantization of winograd convolutions. In Proceedings of the IEEE/CVF Conference on Compuler Vision and Pallern Recognition, pp. 12507-12516, 2022.
Jack Choquette and Wish Gandhi. Nvidia a100 gpu: Performance & innovation for gpu computing. In 2020 IEEE Hot Chips 32 Symposium (ICS), pp. 1 43. IEEE Computer Society, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. 2009 IEEE conference on computer vision and paltern recognition, pp. 248 255. leee, 2009.
Xiaohan Ding, Tianxiang Hao, Jianchao Tan, Ji Liu, Jungong Han, Yuchen Guo, and Guiguang Ding, Resrep: Lossless cmn pruning via decoupling remembering and forgetting, In Proceedings of the IEEE/CVP International Conference on Computer Vision, pp. 4510 4520, 2021.
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943 2952. PMLR, 2020.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv: 180300033,, 2018.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXi::190..0957, 2019.
Scott Gray, Alec Radford, and Diederik P Kingma. Gpu kernels for block-sparse weights, arXie preprint arXiv:1711.09224, 3:2, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yang He and Lingao Xiao. Structured pruning for deep convolutional neural networks: A survey. arXiv preprint Xrv: 005666 2023.
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. The Journal of Machine Learning Research, 22(1):00822-1100)) 2021.
Zejiang Hou, Minghai Qin, Fei Sun, Xiaolong Ma, Kun Yuan, Yi Xu, Yen-Kuang Chen, Rong Jin, Yuan Xie, and Yun-Yuan Kung. Chex: channel exploration for enn model compression. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognation, pp. 12287-12298, 2022.
Guyue Huang, Haoran Li, Minghai Qin, Fei Sun, Yufei Ding, and Yuan Xie. Shil-bw: bw: accelerating deep ncural network inforence with tensor-core aware weight pruning. In Proceedings of the 59th ACM/IEEE Design Aulomation Conference, pp. 1153 1158, 2022.
Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find n: transposable masks. Advances in Neural Information Processing Systems, 34:21099-21111, 2021.
Forrest N Tandola, Song Han, Matthew W Moskewiez, Khalid Ashraf, William J Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5 mb model size. arXiv preprint 10X 2016.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Ajay Kumar Jaiswal, Haoyu Ma, Tianlong Chen, Ying Ding, and Zhangyang Wang. Training your sparse neural network better with any mask. In International Conference on Machine Leurning, pp. PMLR, 2022.
Yu Ji, Ling Liang, Lei Deng, Youyang Zhang, Youhui Zhang, and Yuan Xic. Tetris: Tilc-matching the tremendous irregular sparsity. Advances in Newral Information Processing Systems, 31, 2018
Jiazhi Jiang, Dan Huang, Jiangsu Du, Yutong Lu, and Xiangke Liao. Optimizing small channel 3d convolu- tion on gpu with tensor core. Parallel Computing, 113:102954, 2022.
Mare Jorda, Pedro Valero-Lara, and Antonio Pena. Performance evaluation of cudan convolution algo- rithms on nvidia volta gpus. IEEE Access, 7:70461-70473, 2019.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Aditya Kusupati, Vivek Ramamujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft. threshold weight reparameterivation for learnable sparsity. In International Conference on Machine Learning, pp. 5544 5555. PMLR, 2020.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. arXiv preprint arXic:1608.0877 2016.
Qingynan Li, Bo Zhang, and Xiangxiang Chu. Eapruning: Evolutionary pruning for vision transformers and cnns. arXiv preprint arXiv:2210. 00181, 2022a.
Shigang Li, Kazuki Osawa, and Torsten Hoefler. Efficient quantized sparse matrix operations on tensor cores. arxiv preprint arXiv:2209.060 06979, 2022b.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Shen, Mykola Pech- enizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34:9908 9922, 2021.
Yufan Liu, Jiajiong Cao, Bing Li, Weiming Hu, and Stephen Maybank. Learning to explore distillability and sparsability: a joint framework for model compression. IEEE Transactions on Pallern Analysis and Machine Intelligence, 2022.
Zhuang Lūu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE international conference on compuler vision, pp. 2736 2744, 2017.
Yucheng Lu, Shivani Agrawal, Suvinay Subramanian, Oleg Rybakov, Christopher De Sa, and Amir Yazdan- bakhsh. Step: Learning n: M structured sparsity masks from scratch with precondition. arXie preprint arXiv:2302.011 01172, 2023.
Xiaolong Ma, Minghai Qin, Fei Sun, Zejiang Hou, Kun Yuan, Yi Xu, Yanzhi Wang, Yen-Kuang Chen, Rong Jin, and Yuan Xie. Elfective model sparsification by scheduled grow-and-prune methods. arxiv preprinl arXiv:2106. 09857, 2021.
Fanxu Meng, Hao Cheng, Ke Li, Huixiang Luo, Xiaowei Guo, Guangming Lu, and Xing Sun. Pruning filter in filter. Advances in Neural Information Processing Systems, 33:17629 17640, 2020.
Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelerating sparse deep neural networks. arXio preprint 0rXiv:2104.08371 2021.
Hesham Mostafa and Xin Wang. Paramcter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, pp. 4646-4655. PMLRR 2019.
16

---

Published in Transactions on Machine Learning Research (10/2023)
Jinhyuk Park and Albert No. Prune your model before distill it. In Computer Vision-ECCT 2022: 17th European Conference, Tel Avin, Israel, October 23-27, 2022, Proceedings, Part XI, pp. 120-136. Springer, 2022.
Alexandra Peste, Eugenia Tofinova, Adrian Vladu, and Dan Alistarh. Ac/dc: Alternating prossod /ccompressod training of deep neural networks. Advances in Newral Information Processing Sys- lems, 34:8557 8570, 2021.
M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L. C. Chen. Mobilenetv2: Inverted residuals and linear bottlemecks. IEEE, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXie:1409. 1556, 2014.
Wei Sun, Aojun Zhou, Sander Stuijk, Rob Wijnhoven, Andrew O Nelson, Henk Corporaal, et al. Domi- nosearch: Find layer-wise fine-grained n: M sparse schemes from dense neural networks. Advances in neural information processing systems, 34:20721 20732, 2021.
Kai Sheng Tai, Taipeng Tian, and Scr-Nam Lim. Spartan: Differentiable sparsity via regularizod transporta- tion. Xive preprinl or Xiv:2205. 14107, 2022.
Yijun Tan, Kai Han, Kang Zhao, Xianzhi Yu, Zidong Du, Yunji Chen, Yunhe Wang, and Jun Yao. Acceler- ating sparse convolution with column vector- wise sparsity. In Advonces in Neural Information Processing Systems, 2022.
Yehui Tang, Yunhe Wang, Yixing Xu, Dacheng Tao, Chunjing Xu, Chao Xu, and Chang Xu. Scop: Scientific control for reliable neural network pruning. Advances in Neural Information Processing Systems, 33:10936 10947, 2020.
Qinglin Wang, Dongsheng Li, Xiandong Huang, Siqi Shen, Songzhu Mei, and Jie Liu. Optimizing fft- based convolution on armv8 multi-core cpus. In Euro-Por 2020: Parallel Processing: 26th International Conference on Parallel and Distributed Computing, Warsaw, Poland, August 24-28, 28, 2020, Proceedings, pp. 248-262. Springer, 2020.
Wei Wen, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in newral information processing systems, 29, 2016.
Zhuliang Yao, Shijie Cao, Wencong Xiao, Chen Zhang, and Lanshun Nic. Balanced sparsity for efficient dnn inference on gpu. In Proceedings of the AAAI Conference on Arlificial Intelligence, volume 33, pp. 5676-560 5683, 2019.
Yuxin Zhang, Mingbao Lin, Chia-Wen Lin, Jie Chen, Yongjaan Wu, Yonghong Tian, and Rongrong Ji. Carrying out emn channel pruning in white box. IEEE Transactions on Neural Networks and Learning Systems, 2022.
Yuxin Zhang, Yiting Luo, Mingbao Lin, Yunshan Zhong, Jingjing Xic, Fei Chao, and Rongrong Ji. Bi- directional masks for elficient n: M sparse training. ariio preprint arXi::2302.0000 2023.
Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hong- sheng Li. Learning n: M fine-grained structured sparse neural networks from scratch. orXiv preprint arXiv:2102. arXiw:2102.04010, 2021a.
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 mutrix-mulipplication accelerators. In 2021 IEEE International Symposium on Workload Chamatteizaatio (IIWW),, pp. 214-225. TEFF, 2021b.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXie preprint orXix:1710.0180 2017.
17


Reviews:
[{"review_id": "EfWJTs9Xq1", "reviewer": "Reviewer_w9YE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strengths]\n\n- The manuscript provides a comprehensive set of metrics, including sparsity levels, model accuracy, computational speed-up, and FLOPs, to evaluate the proposed pruning method.\n- The inclusion of the well-established N:M sparsity scheme in the experiments lends credibility to the study.\n- The proposed 'complementary sparsity' technique demonstrates competitive performance across a range of CNN architectures.\n\n[Weaknesses]\n\n- The manuscript lacks an in-depth analysis to explain why the proposed pruning method yields superior model accuracy. Insights into the relationship between the distribution of significant weights and pruning outcomes are notably missing.\n- The choice of models for experimentation appears dated. Given that even contemporary CPUs and GPUs—including ARM chips—can efficiently handle models like ResNets, the study should extend its scope to include Transformer-based models or provide theoretical backing to explain its applicability to state-of-the-art architectures.\n- The claim that the proposed method surpasses unstructured pruning methods in terms of accuracy warrants further justification. Specific details addressing this point are needed to make such a claim credible.\n- Too many typos.\n\n[Overall Remarks]\n\nWhile the proposed method shows promise in maintaining high levels of parallelism, the empirical results are less convincing due to the selection of older models. For the manuscript to make a more compelling case, it should offer detailed analyses that demonstrate the method's viability for cutting-edge architectures. Additionally, the authors should elaborate on why their approach is particularly well-suited for contemporary parallel computing architectures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The manuscript introduces a novel fine-grained pruning technique termed 'complementary sparsity,' aimed at boosting model accuracy while preserving parallelism for enhanced performance on standard CPUs and GPUs. Through comparisons with existing coarse-grained and fine-grained pruning approaches, the authors demonstrate that their proposed method outperforms others in terms of model accuracy, specifically when tested on CIFAR-100 and ImageNet using VGG19 and ResNet architectures. Additionally, the manuscript includes an exploration of relevant hyperparameters.\"", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to 'weakness' above", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S3csaTbJNy", "reviewer": "Reviewer_r32s", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength:\n1. The complementary sparsity is an interesting new idea of achieving sparsity. \n2. Comparisons on CIFAR and Imagenet shows better speedup and accuracy.\n\nWeakness\n1. It seems that the propose CS requires specific optimization of the GPU kernel. It is thus unclear that when other sparsity patterns are optimized on cuda kernel level on a common GPU, whether the proposed CS sparsity can have better speed.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "1. The paper introduces a novel sparse pattern called CS, optimized for high mask flexibility and computational acceleration, allowing for effective pruning of CNNs with minimal loss in accuracy.\n2. It proposes a CS-specific training algorithm that enhances the accuracy of highly sparse CNNs, outperforming traditional N:M sparsity methods, such as 0.48% improvements on ResNet50.\n3. It proposes a parallel acceleration algorithm for the inference phase, tailored for CS-based convolutions, achieving up to 3.07x speedup over dense configurations supported by cuDNN at 93.75% sparsity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. page 7 we propose a weight resue-based => reuse-based\n2. Please also discuss the training overhead of the CS compared with other baseline pruning methods.\n3. Add performance of channel pruning and block sparsity to the Figure 6. \n4. Although not all GPU supports 2:4 sparsity, it would still be valuable to compare the speed of proposed method with N:M sparsity on GPU with N:M tensor core\n5. Please address the concern in weakness above. \n6. fixed the overlapped \"Sparsity\" with column line in table 3\n7. table 3, use the same network for all sparsities, so that the insight about trend of accuracy improvements can be obtained. \n8. it is surprising that the CS can outperform unstructured sparsity by such a large amount. More explanations and insights are needed.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kpu7LUyTH5", "reviewer": "Reviewer_SjDi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Fine-grained unstructured sparsity us plentiful in DNNs yet challenging to accelerate, and the proposed method moves towards finer-grained semi-structured sparsity that can be practically accelerated on commodity GPUs.\n- Both a sparsity algorithm is presented and real hardware speedups are realized through a custom GPU kernel.\n\nWeaknesses:\n- Evaluation is very limited to five somewhat dated CNNs. Evaluations on other DNN topologies (e.g. Transformers) and other tasks (e.g. speech, language, generative) would better demonstrate the efficacy of a new supposedly-general pruning approach.\n- I have some concerns about whether the accuracy comparisons are fair. A special training method was applied for the proposed complementary sparsity method. What about all the baselines? How were they trained? Hyperparameters, epochs, etc? Do you use the same gradual pruning approach for the baselines?\n- Improvements vs. baselines are somewhat limited.\n- No comparisons to N:M sparsity for which the support exists on current GPUs. I realize that authors wanted to present a method without dedicated/additional GPU support, but a comparison would've been informative.\n- [Minor] No energy/power measurements. Would be interesting to see if there are energy implications.\n- Are you releasing your code?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new fine-grained pruning method termed \"complementary sparsity\". Similar to the more widely-known N:M sparsity, this paper presents a 1:K strided sparsity pattern in CNNs. This means that for a strided group of weights along the channel dimension, every group of weights that are K elements apart, only one can have a value while the rest are set to zero. This feels like a specific case of N:M sparsity, but the authors of the paper point out that an efficient GPU kernel can be written to accelerate the proposed complementary sparsity, while N:M sparsity requires special sparsity support in Ampere GPUs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Addressing the weaknesses above would make the paper much better in my opinion. Specifically:\n- More experiments and demonstrating generality to different models, tasks, datasets.\n- A clarification of the training regime and ensuring a fair comparison.\n- Comparison to N:M sparsity from a perf/watt perspective.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores fine-grained structural pruning of deep learning models. The technique, referred to as “complementary sparsity”, build upon the N:M sparsity, but with constrained mask patterns, which is shown to have comparable accuracy performance as N:M sparsity, also enables a parallel accelerating algorithm that can be adapted to common GPUS without sparse tensor cores. The proposed methods are evaluated on a few popular CNN models and CIFAR/ImageNet datasets, demonstrating competitive accuracy and speedup. 

Overall, the paper is reasonably well-written. The concept of complementary sparsity is quite straightforward and offers clear advantage on terms of acceleration, without requiring special hardware, enabling its implementation on standard GPUs. The custom GPU kernel implementation and the results demonstrate the hardware speedup. The training algorithm for pruning may not be novel but demonstrates accuracy level comparable to N:M sparsity method. 

The reviewers have raised two primary concerns:

1). The evaluation is limited to a small number of relatively older CNN models. While the accuracy performance is evaluated on both CIFAR and ImageNet dataset, the speedup evaluation is primarily on CIFAR100 dataset. 

2). Lack of speedup comparison with N:M sparsity.

During rebuttal, the authors presented additional data and clarifications, to some extend addressing these concerns. In particular, the authors provide accuracy performance on small transformer models and speedup comparison with block sparsity and N:M sparsity.

To summarize, this paper is reasonably solid albeit with some reservations. Two reviewers recommend accept, while one reviewer leaning rejection. Considering the proposed sparsity patten is interesting and potential benefits offered by customer kernels for users lacking access to specialized hardware, I am inclined towards acceptance. However, certain modifications are warranted. In particular, the new data and explanations that presented in the rebuttal should be incorporated in the final version with comprehensive explanation. The authors are expected to fulfill their promise of releasing the code and the kernel implementation.  Additionally, the authors should fix typos and figure label issues thoroughly.
Decision: Accept (poster)