Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks
Authors: Itay Hubara
Brian Chmiel
Moshe Island
Ron Banner
Joseph Naor
Daniel Soudry
Venue: NeurIPS 2021 Poster (2021)
Keywords: Efficient Deep Learning
Compression
Prunning

Abstract: Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. In this work, we first suggest a new measure called mask-diversity which correlates with the expected accuracy of the different types of structural pruning. We focus on the recently suggested N:M fine-grained block sparsity mask, in which for each block of M weights, we have at least N zeros. While N:M fine-grained block sparsity allows acceleration in actual modern hardware, it can be used only to accelerate the inference phase. In order to allow for similar accelerations in the training phase, we suggest a novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the error backward can also be accelerated. We formulate the problem of finding the optimal transposable-mask as a minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a  fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest a 2x speed-up in the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching between different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N:M fine-grained block sparsity model with little to no training.  A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.

Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks
Itay Hubara for Brian Chmiel fo- Moshe Island
Ron Banner Joseph (Seffi) Naor Daniel Soudry
Habana Labs An Intel company, Caesarea, Israel Electrical and Computer Engineering Department Technion, Haifa, Israel Computer Science Department Technion, Haifa, Israel
ihubara,
bchmiel misland
rbanner Obanner)@habana.c
@habanaa.a ai
naor &cs. techni aechnion.2e. ac.11
daniell Saaniel.sudryyi Semudrr/@mmai.comm
Abstract
Unstructured pruning reduces the memory footprint in deep neural networks (DNNs). Recently, researchers proposed different types of structural pruning intending to reduce also the computation complexity. this work, we first suggest new measure called mask-diversity which correlates with the expected accuracy the different types of structural pruning. We focus on the recently suggested N M fine-graines block sparsity mask, in which for each block of M weights, we have at least zeros. While N : M fine-grained block sparsity allows acceler- ation in actual modern hardware, phase. In order to allow for similar accelerations in the training phase, we suggest novel transposable fine-grained sparsity mask, where the same mask can be used for both forward and backward passes. Our transposable mask guarantees that both the weight matrix and its transpose follow the same sparsity pattern; thus, the matrix multiplication required for passing the eтror backward can also be accelerated. We formulate the problem of finding the optimal transposable-mant minimum-cost flow problem. Additionally, to speed up the minimum-cost flow computation, we also introduce a fast linear-time approximation that can be used when the masks dynamically change during training. Our experiments suggest speed-up the matrix multiplications with no accuracy degradation over vision and language models. Finally, to solve the problem of switching be- tween different structure constraints, we suggest a method to convert a pre-trained model with unstructured sparsity to an N M fine-grained block sparsity model with little to no training. A reference implementation can be found at https //github. www. wwoom/ppprrs-.. http:/ppprsssuusssseeesees http:/siii..sstttuuuuuottaaaaaaa
be used only accelerate the inference
Introduction
Deep neural networks (DNNs) have established themselves as the first-choice tool for a wide range of applications, including computer vision and natural language processing. However, their impressive performance comes at a price of extensive infrastructure costs - as state-of-the-art DNNs may
contain trillions of parameters [TO] and require thousands of petaflops (6 for the training process. For this reason, compression of DNNs training and inference process is a research topic of paramount
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

importance in both academia and industry. The main techniques of compression include quantization
2
knowledge distillation [T7, and pruning [T5] 23
Pruning DNNS is one of the most popular and widely studied methods to improve DNN resource efficiency. The different pruning methods can be categorized into two different groups: unstructured and structured pruning. While the former can achieve a very high compression ratio, it usually fails in reducing the computational footprint in modern hardware. In contrast, structured pruning methods, such as block 41] or filter [23] pruning, are more hardware friendly. Unfortunately, these methods usually fail to keep the original accuracy for high compression ratios [37]. Finding an optimal structured sparsity pattern is still an ongoing research topic.
Recently, Nvidia [66] announced the A100 GPU, containing sparse tensor cores which are able to accelerate fine-grained sparse matrix multiplication. The sparse tensor cores in A 100 enable a 2x acceleration of regular matrix multiplication in DNNs, Y WX, where W and X are weight and input matrices, respectively. The only requirement is that W would have a fine-graine structure, i.c. out of every four contiguous elements in W, two are pruned. Nvidia [36] suggested a two-fold scheme for pruning a pretrained dense model: (a) Define fine-grained 2:4 fixed mask, and (b) retrain with the masked weights using original training schedule. Indeed, the Nvidia [36] approach is very appealing for the common case where a pretrained dense model is given.
2:4 sparsity
While the Nvidia (36] method works well on many models, pretrained model is not always given. In those cases, one has to first train a dense model and only then try to prune it. To alleviate this demand, Zhou et al. 43 suggested method that trains from scratch model with N M fine-grained mask, using a sparse-refined arraigh-thhough estimator (SR-STE). Similarly to the quantization-aware training methods [18], they maintain dense copy of the weights and prune it in every iteration, passing the gradients using the straight-through estimator [5]. Since the mask dynamically changes while training, they suggest adding an extra weight decay on the masked (i.e. pruned) elements to reduce the mask changes during the training process. As opposed to Evci et al. [9] that aims to reduce memory footprint for sparse training from scratch, Zhou al. 43 only eliminates the need train dense model before pruning it.
Motivation
Understanding fine- grained sparsity
Training
Inference
Questions
Can fine grained sparsity masks accelerate training?
How to rank types of sparsity masks?
Can we change sparsity mask type without tr-taliinn??
Proposed
Transposable sparsity
Mask divensity
Solutions
Section
Section 3
Section
Figure 1:
High-level overview of the different questions and their corresponding solutions proposed in this work. Motivated by understanding fine- praigra sparsity we first suggest a mcasure to rank different sparsity mask, then suggest method to accelerate training with fine-graines sparsity and finally propose method to change the fine-graino mask without re- re-training.
Motivated by these promising results, our goal here to answer three remaining questions: (Fig.
1. How to rank different types of sparsity masks? We suggest new measure called "mask diversity", which is the first to connect mask constraints and network accuracy (Section 3..
2. Can fine-grained sparsity masks accelerate training? We start by observing both the forward and the backward matrix- motrri-multillications involving the weight matrix W. Since the backward pass requires using the transposed matrix WT:
Losss ax
WT ÕLoss ØY
and in general WT does not have an N M fine-grained sparsity structure (even if W has this structure), the methods suggested in 43 36 accelerate only the forward pass matrix maatrix-uulipllcationn.

---

= WX. Consequently, the current methods only utilize in part the sparse tensor cores to accelerate training. We propose novel N : M cranposable-finegraane grained sparsity mask, where the same mask can be used for both forward and backward passes (Fig. 2 We focus accelerating sparse training in the two settings detailed above: (a) starting from pretrained model, and (b) starting from scratch. For (a) we derive novel algorithm to determine the optimal transposable- mask using a reduction to min-cost flow problem. For (b) we devise an approximation algorithm with (almost) linear (in input-size) time complexity that produces mask whose & norm is within a factor of from the optimal mask. We show the effectiveness both methods (Section
Forward
Forward
W
W
W
Backward
Backward
4:8
oLoss
oLoss
W
dooss
Loss
WT
0x
0Y
ax
ay
(a)
Figure 2: (a): 4:8 structured pruning mask, in Zhou al.
43 Nvidia 33) capable of accelerating with
sparse tensors core only the forward pass. (b): The suggested 4:8 transposable structured pruning mask capable of accelerating with sparse tensors core the forward and backward passes.
Can we change the type of sparsity mask structure without re-training? Different hardware devices support different types of fine-grained sparsity masks. Therefore, suggest the "Adaprune" " method, which converts between types of sparsity masks (even from unstructured masks) without the need of re-training, and almost no degradation in accuracy (Section 5).
2 Related work
Pruning of neural networks weights has been extensively investigated, starting with classical methods in the late 1980s (20 31 32 21 and then amounting to dozens of papers published in recent years. Since DNNs are generally over- wer-pparaeteriied, pruning the weights reduces their memory footprint. In special cases, when the sparsity mask has specific pattern, it has the potential to reduce computational footprint as well. The most common practice is to prune a pretrained dense model, so that it will be sparse at deployment. Since the accuracy of the pretrained dense model is known, one can tune the sparsity level to ensure comparable accuracy for the sparse model. Recently, a new line of research that aims to train sparse models from scratch [4 7 D has emerged. The goal is train models that cannot fit into currently available hardware. Next, we briefly overview the structured, unstructured, and Unstructured pruning. It removes individual elements of the matrix, aiming for high total sparsity, while being agnostic to the location of the pruned elements. Standard pruning methods are based on different criteria, such as magnitude [TS],, approximate Lo regularization (26). or connection sensitivity (22]. Recent methods [12. suggested to train a dense network until convergence, extract the required mask ("winning ticket"), and use the original training regime to re-train the active weights from their original initialization or final values (38) using the original training schedule. These methods able to achieve over 80% sparsity on ResNet50- ImageNet dataset (38). Despite the high sparsity ratio that can be achieved with these methods, modern hardware cannot efficiently utilize such form of sparsity for reducing computational resources (36).
categories.
Structured pruning. It removes weights in specific location based patterns, which are more useful for hardware acceleration. Such methods can be applied either the level of channels or layers. For example, Li et al. (23 remove the channels with the lower norm, Luo et al. (27) prune channels according to the effect the activation of the following layer, and [4] split the filters into multiple groups, applying group Lasso regularization. All these methods are natively supported in both hardware and software, as they effectively change the model structure by reducing channels or groups. Yet, no such method was able to achieve reasonable accuracy with sparsity levels higher than 50%. As observed by Liu et 25). filter pruning of pretrained dense over over-parameterized model rarely the best method to obtain an efficient final model. Thus, here the structured pruning serves mostly
3

---

as a DNN architecture search for the optimal compact model 40 42 Our work is most closely related to Zhou et [4], which the first work that attempted training with fine-grained N M structured sparsity mask, as explained above.
Accelerating sparse training for model deployment. The most common approach for sparse model deployment requires a three steps process: (a) train a dense model; (b) define sparsity mask (c) fine-tune while enforcing the mask the model's weights. The lottery ticket hypothesis of Frankle & Carbin [2] demonstrates that we can avoid the dense training, i.e., step (a), had we known how to choose the appropriate mask. Since Frankle & Carbin [2] discovered the optimal mask (winning ticket) by applying dense training. the question of how to find the optimal mask without training remained open. Since setting predefined fixed mask results in some accuracy degradation (Gray et al. [14] that requires expanding the model size), several researchers [4, [2] 30, 9 tried to enable dynamic mask changes during the training process. All methods focused on unstructured sparsity and aimed to enable training large models on hardware with memory limitations. In contrast to these approaches, Zhou al. 48 does not aim reduce the model memory footprint during training, but rather accelerate inference while avoiding dense pre- pre-training. To that end, they keep a dense weight matrix, and in each iteration they re-caleulate the mask. With the obtained pruned copy of the weights they perform the forward and backward pass and update the dense copy. Therefore, this method is most relevant when pretrained dense model is not given, and one wishes to obtain fine grained N M sparse model for inference. While our work focuses on the setting of Zhou et al. 433. we argue that it can easily combined with Evci al. 9 work, as it aims to solve a different issue within the same problem.
3 Mask Diversity
Structured sparsity requires masks with a hardware-friendly structure type. Yet, which structure should be employed is still an open question. The additional hardware cost (mainly chip-area and power) required to support each of the structures is hard to quantify, as it varies based on the hardware design. However, the effect of the structure on the model accuracy is oblivious to the hardware at hand. Therefore. in this section, we aim to find a method for ranking different types of sparsity masks, which can predict help the model accuracy. We start from an hypothesis that the structure constraints cause accuracy degradation. Thus, we expect that the best sparsity levels. without accuracy degradation, would be achieved by unstructured sparsity, which has no requirements on the sparsity structure type. To quantify how much a specific structure constrains the model, we introduce new measure, called mask-diversity (MD). MD the number of all possible masks that adhere to the restrictions of the structure under similar sparsity level. As example, we derive the MD for tensor size T under four different structure constraints:
1. Unstructured sparsity: no constraints, except for an overall sparsity level. This is the most common setting in the literature.
2. Structured N:M sparsity: N values in each block of size M are set to zero. This structure is currently supported in the most widely deployed hardware [36].
3. Transposable N:M sparsity: for block of size M x M both columns and rows must follow the N : M fine-grained constraints. As we later discuss (Section 4. the transposable structure is essential for training acceleration.
4. Sequential N:M sparsity: any block of size M must contain N sequential zeros. This is an example for a small potential modification to the N: : M fine-grained structure, which might be more hardware friendly (data can be compressed and decompressed more easily).
MD depends on the required sparsity level (and the tensor size), thus without loss of generality we set the sparsity level to be N/M. In Eq. (2) we write the MD for each of the constraints (1-4) above, derived using basic combinatorial arguments (Appendix A.6):
T
1. MD Unstructured
3. MD Transposaable (MI(M- (M 1)!... (M N N 1) N
NT
M
N7 :
M!
2. MD Structured =
4. Megeueenial = (M N 1)
N! - NY!

---

Table 1: MD for different constraints for matrix of size 8 8.
Table shows the MD for matrix of size 8 x 8 with 50% sparsity under dif-
N M
1:2
2:4
4:8
ferent constraints. As expected, unstruc- tured sparsity achieves best in class MD, however its hardware cost makes it un- feasible to use on modern architectures 14 8 [3 Additionally, sequential N:M
Unstructured
1.8 10
1.8 10th
1.8: 10
Structured
4 10
2.8 10
5.7 10
Transposable
6 10*
4 1.10
1.7 1013
Sequential
4- 10"
4- 10
4 10
sparsity has worst in class MD and con- sequently expect that using it would harm the model accuracy (Fig. Thus, from here we focus on the structured and transposable structured fine- grained sparsity. Notice the MD of structured 2:4, which was used in 36 43
is severely reduced when transposable constraints are enforced. Since a transposable structure enables training acceleration (Section 4. supporting this structure is essential. Thus, we suggest minimal expansion of the block size (from 4 to 8) which enables the transposable fine-grained structure to reach a similar MD as the 2:4. Increasing the block size requires more multiplexers to support the N M structure (24]. However, the hardware cost increases only logarithmically with respect to N (details given in Appendix [A.5). We therefore argue that such an expansion reasonable. To better degradation with respect to the mask diversity on ResNet18 with Cifar- dataset. As can be seen Fig. 3a the accuracy correlates with the MD metric and the 4:8 transposable fine-grained mask reached a comparable accuracy to the 2:4 fine- fine-grained mask. Moreover, recall the common method of magnitude pruning has an underlying objective
hypothesis, we measured the accuracy
preserve the tensor l norm. We therefore measured the effect of the different constraints on the & norm in Fig. 3b) This figure shows the f norm of the last layer in trained ResNet-50 after applying different structured pruning. Here as well, 2:4 structured and 4:8 transposable structured have (almost) similar & norms.
71
4:8
Normalized magnitued
1:2
0.95
69
2/4
Accuracy
68
3:4
0.90
Structured
67
Transposable
0.85
66
1:24.8
Sequential
Unstructured
0.80
65
15
20
25
30
35
40
US
4:8 Structure constraints
2:4
4:8-T
4:8-5
log(MD)
(a)
(b)
Figure 3: (a): ResNet18 Cifar100 top-1 accuracy for weight sparsity 50 % using different structured and unstructured masks. As expected the mask diversity correlates with the pruned model accuracy. (b): Magnitude of the last layer's 's weight tensor of ResNet-50 (pretrained dense model) masked with structured mask 4:8, 2:4, 4:8 transposable ("4:8-T") and 4:8 sequential ("4:8-S") normalized by the unstructured 50% sparsity ("US"). Notice that mask diversity is correlated with magnitude preservation. As expected the 4:8 transposable mask has similar score the 2:4 mask. Additional results and details Appendix A.7
Computing transposable sparsity masks
In general, training DNNs requires three matrix multiplications per layer. The first multiplication is required for the forward propagation between the weights and activation. The other two multiplica- tions used for the backward and update phases. The backward phase calculates the gradients of the loss function with respect to the input of the neural layer. This is done by recursively passing the error from the last layer to the first (Eq. (T) Note that the backward phase uses the transposed weight matrix. Hence, accelerating the backward phase requires the transposed weight matrix to adhere to the hardware required pattern (e.g., N M fine-graing grainerd sparsity). In this section, we tackle this issue by presenting novel to find N M transposable fine the-grained sparsity masks, where the same mask can be used accelerate both forward and backward passes (Fig. The required mask contains only M N non-zero elements, for every contiguous M elements, in both W and WT simultaneously. We formulate the problem and suggest two methods to generate the transposable mask.
5

---

Problem formulation. First, we provide an entege-programnnn optimal transposable fine- une-grained mask. Let us consider block of size M x M in a weight matrix W. Our goal is to maximize the & norm of W after masking N elements in each row and column. We formulate the problem as an integer program. Define binary sparsity mask S {0, 1) 3jMxx MMM where Si,j = 1 if and only if the element Wa, is not pruned, and otherwise S1,5 = 0. The resulting integer program is
(IP) formulation for finding an
max (6(0,))MX0
Σ Sa, |Wisl s.t. Vj: - Σ S NN 1.
(3)
In the following, examine several methods for solving this problem. We first describe an optimal, yet computationally expensive method. We then describe a more efficient method, which provides an approximate near-optimal solution.
Reduction to Min-Cost Flow. General integer programs (IP) require exponential time complexity with respect to the input size (worst-case). Fortunately, Fig. 4 shows that our IP formulation (Eq. reduces to a min-cost flow problem. There is a vast litcrature on efficient min-cost flow algorithms (see e.g., M., however, the most efficient algorithms for our setting take time OMM log M) time for computing an optimal transposable mask for a block size of M x M plpp. 396-397 The min-cost flow solution should be used when training from a pretrained dense model, where the transposable mask is generated once, remaining fixed from then on during training. On the other hand, sparse training from scratch requires changing the mask during training, and it is therefore essential to find a very efficient algorithm for computing the mask. To this end, we design a light 2-approximation algorithm, i.e., for every input it produces solution which is guaranteed to be within factor of 2 of an optimal solution (to the given input), yet it runs in almost linear time.
W E M
Rows
Columns
M
M 2
F
2
Figure 4: // .M transptsable-sparsity optimization as min-cost flow problem. In addition to source and sink, the network has node for each row and for each column. The construction uses three types of edges: (i) source edges emanating from the source node s into each row node i; (ii) sink edges connecting each column node j with the sink node t; and (iii) coefficient edge ji for cach matrix element W.,, Each source edge M
(s has capacity 2 which is equal to the number of elements that need to be selected for pruning in row i. Similarly, each sink edge (j. () has capacity M which is equal to the number of elements pruned in column j. Each coefficient edge (i.j) )) has unit capacity and cost [W.,le Finally, selecting a matrix element with weight Wi, for pruning corresponds to a unit flow on the coefficient edge (i.j). Assuming the source and sink edges have zero-cost, there is a one-to-one correspondence between a min-cost flow solution that sends a flow of value M²
2- from the source s to the destination i in this construction, and an optimal transposable mask minimizing the sum of absolute values selected for pruning.
2- A-Approximation algorithm. We design a greedy 2-approximation algorithm (see Algorithm I having low time complexity that can be used practice without compromising too much the quality of the solution produced. Unlike the optimal min cost flow solution that runs in time complexity of 3(3) for a block size of M x M, Algorithm| complexity that is almost linear in the number of block elements M The approximation algorithm uses the same construction described in Fig. 4 but instead of running min-cost flow on the graph, employs a simple greedy approach. Let P be the list of edges pruned by Algorithm 1 let W(P) be the total weight of the edges in P. and let W* be the weight of an optimal solution (i.c., the minimal M sum of edges that can be pruned to create 2 M transposable sparsity mask). The next lemma establishes that Algorithm I finds 2-approximate solution (proof in Appendix A.2 with an example showing the upper bound is tight);
[ has a running time of O(M² log M) i.e., a time
Mooe modern methods that based on interior point algorithms seem to be less efficient for setting.

---

Lemma. Algorithm 1 produces a tight 2- 2-approximate solution, i.e., ((P) < <2 W.
Algorithm 1 2-approximation algorithm. Input: Bipartite graph G=(V,B) Initialize: P= Ø
1: Sort list of coefficient edges from light to heavy; Let A = [e1, en] be the sorted list of edges.
2: for each edge e; = (u, v) E A, i = 1....,77 . do
3: if d M or d 2 in P then P <- E..
2
In Table 2 we show the running time overhead of ResNet50 training with IP, min cost flow and 2- approximation algorithms over regular training, the algorithms were implemented in non-optimized way. All experiments were run in a single GPU and the mask was updated every 40 iterations. Notice the acceleration achieved with the 2-approximation algorithm in comparison to the naive IP. In Appendix A..3 we extend the complexity analysis.
4.1 Experiments
In this section, we demonstrate the ef- fectiveness of our proposed transposable N : .M fine-grained structured sparsity in computer vision and natural language processing tasks. We evaluate the sug- gested method in two cases: (i) initialize from trained dense model and re- trair with a fixed mask, similar to APEX's Automatic Sparsity (ASP [36]), (ii) train from scratch and update the mask fre-
Table Overhead of different algorithms for finding the 4 8 transposable mask: ratio of their running time over regular training (ResNet50). Notice the overhead reduction in the 2-
approximation algorithm in comparison to the naive IP.
Method
Overhead (%)
integer-programmiing
180
Min-cost flow
70
2- 2-approximation
14
quently, done by Zhou al. 43). We show comparable accuracy to previous methods, while achieving a significant reduction of the training process resources - by exploiting the sparse tensor core abilities, allowing their use both in forward and backward passes. In all the experiments we use a 4:8 transposable-mask, which as shown in Table [ have a similar MD as 2:4 mask used in previous works (36 43 Experimental details appear in Appendix A.4 In Appendix A.8 we show additional experiments with the 2:4 transpose mask showing that: (1) in most cases, 2:4 transpose is enough to achieve high accuracy, (2) in some cases where the 4:8 transpose is necessary. and (3) this
is consistent with the MD results shown in Section
Initialization from trained dense model We evaluate the suggested N M transposable mask using a trained dense model as initialization. In order to find the transposable mask, we solve the min-cost flow reduction (Fig. 4 the dense trained network and then fix the mask. In Table we compare our method with ASP (36) on classification (ResNet50- ImageNet dataset), detection (MaskRCNN- COCO dataset) and question answering (BERT-large SQuAD dataset) tasks, While both methods initialized from the pre-trained models, the 4:8 transposable enables propagation acceleration in the retraining phase where ASP does not.
Table 3: Comparison of our suggested method with ASP (6) initialized from dense model on ResNet50 (Imagenet dataset), BERT-large (SQuAD dataset) and MaskRCNN (COCO dataset). We use transposable 4:8 mask while ASP used 2:4. SU refers to the sparse tensor cores utilization, used both in forward and backward passes the proposed method, allowing 2x sparse tensor cores utilization comparison to ASP which use the sparse tensor cores only in the forward pass. Missing results in Nvidia [36] were marked by '-'
Baseline
ASP 36 2:4
Ours 4:8-T
Model
Metric
SU
Accuracy
SU
Accuracy
SU
Accuracy
ResNet18
Top1
69.7%
70.06%
ResNet50
Top1
76.15%
76.6%
76.6%
0%
33%
66%
Bert-Large
F1
91.1
91.5
91.67
MaskRCNN
AP
37.7
37.9
37.84
Sparse Training from scratch. order to avoid the training of a dense model, we also evaluate the proposed transposable N M mask in the training from scratch setting. Similar to Zhou et al. x we keep a dense copy of the weights and before each forward pass we mask the weights with a N M transposable mask. In contrast to Zhou et al. [4] who changed the mask every iteration,
7

---

Table 4: Training from scratch of ResNet18, ResNet50, ResNex150 and Vggll on imageNet dataset and fine-tuning of Bert-base on SQuAD dataset, using the proposed 2-approximation scheme. SU refers to the sparse tensor cores utillization, used both in forward and backward passes in the proposed method, allowing 2x sparse tensor cores utilization in comparison to N:M-SS (43) with comparable results. Missing results in Zhou et al. were marked by"
Baseline
4:8-SS
43
Ours 4:8-T
Model
Metric
SU
Accuracy
SU
Accuracy
SU
Accuracy
ResNet18
Top1
70.54%
71.2%
70. 70.75%
ResNet50
Topl
77.3%
77.4%
71.1%
ResNext50
Topl
0%
77.6%
33%
66%
77.4%
Vggl 11
Topl
69%
68.8%
BERT-base
F1
88.52
88.38
found that we can use 2-approximation scheme extract the transposable mask every 40 iterations. Empirically we found that the 2- 2-approximation scheme is on average within a factor of 1.2 from the optimal mask. The syper-parametess used for training are equal to the ones suggested by Zhou et al. [4). In Table 4 we test the proposed method over ResNet18, 8, ResNet50, ResNext50, Vgg1 (emageNet dataset) and fine-tune of Bert (SQuAD-v1.) dataset) and compare to Zhou et al. results. As can be seen, we achieved comparable accuracy with 2x sparse tensor cores utilization in the training process.
Structured sparsity without full training
In section Section we suggested 4:8 transposable-mast to accelerate training, but what should we do if we wish to deploy the output of such training on hardware that supports only 2:4 fine- grained sparsity. Forcing structured sparsity a model that was trained with a different structured sparsity, leads to a severe accuracy degradation as several bits of the mask may change to satisfy the structured sparsity requirements. In this section we would focus on the more common case of deploying unstructured sparse model on hardware that support N:M structure. This is a fundamental problem most DNN pruning methods focus unstructured pruming, which reduces the memory footprint. However, current hardware implementations suggest that, unless very high sparsity levels achieved, the model cannot be accelerated at all. Hence, commonly, the weights decompressed before multiplication. To understand the problem we study the probability that an unstructured mask would not violate any N M constraint (36). Then discuss two light methods to bridge the gap when sparse model is given but the hardware does not support its structure.
simply
Probability for violating the N : M constraint in unstructured sparsity. Let X (21, Ty.,,,,..... xM } be block of independent and identically distributed random variables, Assume that with probability p. 24 can be pruned without accuracy degradation (i.e.. unstructured pruning). In this section, we consider a general form of block sparsity in which, for a block of size M, at least N values could be pruned. Define X be N . sparse if this M sized block has at least N values that can be pruned without harming accuracy. The probability of having a N M sparse block is given by the binomial distribution and so
M ( 2N
( is N M sparse)
= Σ
p² (1-
(4)
4 for the case of p = 0.5. To force a given sparse model to have a fine grained N M sparsity, we need to make sure that N out of every M contiguous elements are zero. Therefore, as in Nvidia [36], in each block we prune N weights with the lowest magnitude (including any zero weights, e.g., non-active). Forcing this pattern on an existing unstructured mask might remove active (non-zero) weights, i.e., flipping some of the mask values from one to zero. We named those required flips, pattern-violatioos, Removing active weights without re- re-training tends to severely degrade the model accuracy. To demonstrate the problem we used an unstructured sparse pretrained ResNet-50 model (p- = 0.86) and set the N M structure per-layer, based on Eq. (4). such that the probability for a pattern-violation would be equal or less than given percentage. Here we used block size of M = 8. Notably, without any optimization even a 1% pattern-violation results severe degradation (Fig. 5bp. Next, we describe two light methods to boost the accuracy.
In Fig. 5a we plot Eq.
8

---

10
M-16
0.8
M+p4
M=32
Top-1 Accuracy (%)
70
3o%
81s
85%
M-128
60
80%
Probability
0.6
50
40
85% Bos for
Baseiie
(unstrctured)
20
Abcorts Mean
AdsPrane
91% f.v. 72% Par
tt-sptimizztion
0.0
2
10
12
0.2
0.4 0.5
N:M sparse
Violations (%)
(a)
(b)
Figure 5: (a): Eq. (4) for p = 0.5 and various block sizes M. We have a sharp (" ("phase") transition at N/M = Specifically, (i) when N/M < we have a prohability larger than 0.5 that the sampled block is N M sparse; (ii) when N/M p this probability quickly decreases to zero. As block size M increases this phase-transition gets sharper. As expected, when M + oc, unstructured sparsity satisfies the structured constraints, and we expect it to display the phase transition precisely at the critical point p. (b): Top-1 accuracy vs. percent of constraints violated. The numbers next to the baseline samples represents the sparsity level of the refined model.
reported that it is important to fix the bias introduced when quantizing the model. We build on those results and suggest absorbing the mean of the N pruned weights into the M - N non zeroed weights. As can be seen in Fig. 5b this simple fix, by itself, greatly boosts accuracy.
Fixing pruning bias using mean absorption. Several works 3 [
AdaPrune. Recently, several works 119 33) suggested light and fast fine-tuning techniques for post-train quantization. These techniques replace the heavy full model training with a fast per- layer optimization which requires only few iterations to converge. While each method applies a different optimization technique, they all aim to reduce the discrepancy between the quantized and full- precision layer outputs. We adjusted the Aarallel-Aaauantt (19] technique to the pruning problem by defining its objective to be:
min |IWX (S W W
(5)
where Wi is the original weight layer. W" is the weight layer we aim to find, X is the output of the previous activation layer, S the weight sparsity mask, and @ is a component-wise product. We named this method AdaPrune. In our experiments we used 1000 images from the ImageNet training set as a calibration set. As can be seen Fig. (5b] AdaPrune is capable of correcting the remaining error and obtain less than 1 % degradation from the original unstructured-spaane sparse model counterpart. We argue that with AdaPrune, we can potentially adapt any generic mask to the hardware at hand, thus elevate the need to retrain the model. However, full re-training is still necessary when starting from a dense model (thus having 50% nattern-violation), since there we get 2.3% degradation using AdaPrune. We discuss and extend those experiments in Appendix A.
6 Conclusions
In this work, we analyze the constraints introduced by fine tee-grained sparsity. We discuss the limitations of current research in the field and suggest new measure called mask diversity to connect between the mask constraint and the accuracy of the network. In addition, we discuss the inherent problem of accelerating sparse training and suggest a novel N:M transposable-mast which enables accelerating the backward phase as well. We formulate the question of finding the optimal mask as a minimum- cost-flow problem and show no accuracy degradation
a variety of tasks with 2x acceleration in comparison to previous methods [36]. We experimented with transposable-man -makss also in the setting of Zhou et al. 43] where pretrained model is not given but the mask is dynamically changing based on the gradients and copy of the weights which are kept dense. In this setting we define an approximation scheme with an (almost) linear (in input-size) time complexity that produces a mask whose & noro is within a factor of 2 from the optimal mask and allow 2x acceleration in comparison to Zhou et al. 4 While a different line of research suggested more extreme setting which restrict the memory footprint to the compressed model size 4 29 30 9 we argue that our method is orthogonal to and both methods could be easily be combined. We believe this work paves the path toward true efficient sparse training. Finally, we suggest simple method (AdaPrune) to transform an

---

[6] T. Brown, B. Mann, Nick Ryder, Melanie Subbiah, Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Child, Aditya Ramesh, D. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, E. Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, unstructured sparse model to an N M fine-grand fine-grained sparse structured model with little to no training (e.g., less than 1% degradation in ResNet50). Furthermore, with light training procedure over calibration set (i.e., AdaPrune) we can switch from unstructured model to 4:8 structure sparsity and thus gain inference speedup.
Broader impact. Training DNNs is an expensive process which requires a high amount of resources and time. This long time can prevent the use of DNNs in many applications, despite their impressive performance. Reducing training time gives the opportunity to to use of DNNs in additional appli- cations, or even use the extra time to improve the existing models. We need take into account that accelerated training could introduce training instabilities. These models will need careful examination, specially when used in real applications, such as medical devices.
Acknowledgements
The research of JN is supported in part by US-Israel BSF grant 2018352 and by ISF grant 2233/19 (2027511). The research of DS was supported by the Israel Science Foundation (grant No. 1308/18), and by the Israel Innovation Authority (the Avatar Consortium).
References
[1] Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows. 1988.
[2] Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. Scalable methods for 8-bit training of neural networks. In NeurIPS, 2018.
[3] Ron Banner, Yury Nahshan, Elad Hoffer, and Daniel Soudry. Post-training 4-bit quantization of convolution networks for rapid-deployment. arXiv preprint arXiv: 2018.
[4] Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. arXiv preprint arXiv: 2017.
[5] Yoshua Bengio, Nicholas Léonard. and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint a3Xiv:1308..380 3432, 2013.
Voss. G. Krüger, T. Henighan,
J. Clark, Christopher Berner, Sam McCandlish, A. Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. ArXiv, abs/2005. 11120005.1165,, 2020.
[7] Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04844 2019.
[8] Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 14617-14626, 2020.
[9] Utku Evei, 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.
[10] W. Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. ArXiv, abs/2101 0039611, 2021.
[11] Alexander Finkelstein, Uri Almog, and Mark Grobman. Fighting quantization bias with bias. arXiv preprint arXiv: 1906.03399 2019.
[12] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In ICLR, 2018.
[13] Trevor Gale, Matei A. Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning. In SC, 2020.
10

---

[14] Scott Gray, Alec Radford, and Diederik P Kingma. Gpu kernels for block-sparse weights. arXiv preprint arXiv: 10t1..92..0924 3, 2017.
[15] Song Han, J. Pool, John Tran, and W. Dally. Learning both weights and connections for efficient neural network. ArXiv, abs/1506.02622 2015.
[16] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
[17] Geoffrey E. Hinton, Oriol Vinyals, and J. Dean. Distilling the knowledge in a neural network. ArXiv, 0obs/1503.02531 2015.
[18] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv,, and Yoshua Bengio, Quan- tized neural networks: Training neural networks with low precision weights and activations. The Journal of Machine Learning Research, (8(1):6869-689)) 2017.
[19] Itay Hubara, Yury Nahshan, Yair Hanani, R. Banner, and Daniel Soudry. Improving post training neural quantization: Layer-wise calibration and integer programming. ArXiv, abs/2006. 1051200061111,, 2020.
[20] A. Janowsky.
Pruning versus clipping in neural networks. Physical Review A, 1103/PhysRee......m
39(12):6600-660) 6603, 1989. URL https://link: aps http://l///...111///ayaeeeee
6600
[21] E. D. Karnin. A simple procedure for pruning backpropagation trained neural networks. IEEE transactions on neural networks, 1(2):239 22-2222222, 1990.
[22] N. Lee, Thalaiyasingam Ajanthan, and P. Torr. Snip: Single-shot network pruning based on connection sensitivity. ICLR, 2019.
[23] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for efficient convnets. In ICLR, 2017.
[24] Zhi-Gang Liu, Paul Whatmough, and Matthew Mattina. Sparse systolic tensor array for efficient cnn hardware acceleration. arXiv preprint arXiv:2009.0238/, 2020.. 2020.
[25] Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning, arXiv preprint arXiv:1810.052701 2018.
[26] Christos Louizos, M. Welling, and Diederik P. Kingma. Learning sparse neural networks through regularization. In JCLR, 2018.
[27] Jian-Hao Luo, Jianxin Wu, and W. Lin. Thinet: A filter level pruning method for deep neural network compression. 2017 IEEE International Conference on Computer Vision (ICCV), pp.
2017.
[28] Sébastien Marcel and Yann Rodriguez. Torchvision the machine- vision package of torch. In Proceedings of the 18th ACM International Conference on Multimedia, MM '10 pp. 1485-1488, New York, NY. USA. 2010. Association for Computing Machinery. ISBN 978 1605589333 doi:
10.1 10.1145/18739511 01555/873351111877 1..139991..111.54
httpss/ts:://oo htt://doo.oo///////// or0//0. 1145 1873951 1874254
[29] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibeseu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1112, 2018.
[30] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Machine Learning, pp. 4646-4655 PMLR, 2019.
[31] M. C. Mozer and P. Smolensky. Skeletonization: A technique for trimming the fat from network via relevance assessment. Advances neural information processing systems, pp. 107-115, 1989a.

---

[32] M. C. Mozer and P. Smolensky. Using relevance to reduce network size automatically. Connec- tion Science, 3 1989b.
[33] Markus Nagel, Rana Ali Amjad, Mart van Baalen, Christos Louizos, and Tijmen Blankevoort. Up down? adaptive rounding for post-training quantization. In ICML, 2020.
[34] Yury Nahshan, Brian Chmiel, Chaim Baskin, Evgenii Zheltonozhskii, Ron Banner, Alex M. Bronstein, and Avi Mendelson. Loss aware post-training quantization. ArXiv, abs/1911.07190, 2019.
[35] Nvidia. Nvidia deep learning examples for tensor cores. 2018. URL httpt:tttssstiiiii com/
[36] Nvidia.
a a100 tensor
core gpu architecture.
2020.
URL
http://
nttps://wwr nvidia
Catautiiiiinn/ataaaetttee Center/
[37] A. Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. ArXiv, abs/2003.02389, 2020.
[38] A. Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In ICLR, 2020.
[39] Darko Stosic and Dusan Stosic. Search spaces for neural model training. ArXiv, abs/2105.12920. 2021.
[40] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2820-2828, 2019.
[41] Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in neural information processing systems, pp. 2074-2082, 2016.
[42] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangging Jia, and Kurt Keutzer, Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10734-10744 2019.
[43] Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li. Learning n.m fine-grained structures sparse neural networks from scratch. In ICLR, 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes], [No] or [N/A]. You are strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license the code and datasets? [N/]]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
12

---

(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The main contribution of this paper include answering the three questions presented in the introduction and summarize in Fig. [
(b) Did you describe the limitations of your work? [Yes] As explained in Section 6 there can be models that we didn't 't check where the proposed method could introduce training instabilities.
We didn't 't notice any instability in all the models checked. (Brian: ?)
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Yes, in section Section O in broader impact we discuss the positive social impact of this work reduce training time and allow the use of DNNs in additional applications. We don't see any negative impact of this work.
(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? [Yes]
See Ap-
pendix A.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.2
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as URL)? [Yes] As written in the abstract reference implementation can be found at papers- wtt.susussssssssoooooo/ooooo wttpsssiiiiittttuuuuuuuuue strructured_rrrasposblll battssaalemmmsssss__e_a
com/
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.4
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No] The experiments were run with random seed one time, as
in the previous works 43 36
we compare to. Error bar not applicable.
(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] See Appendix [A.4
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? [Yes] In the url https: // github. com/papers Spapers-submisee cimissson http///uuuureddde wttpuuurddrrrappssseeeeee transposable sapassssaleeeeeeeeeeeeeeee that in- cludes our implementation, we cite the creator of existing assets with link to their license
(b) Did you mention the license of the assets? [Ye]] In the url https: //gptth/// com/ papers-subbi wwt.ssssumisiiooooeemeeeeemoeoie /tssssuuuuurdd. wewpuucuurddtraasssseeeeeee transposable masks that includes our imple- wttoomiissoo/sttutsurreeeeeeeeee
mentation, we cite the creator of existing assets with link to their license
(c) Did you include any new assets either in the supplemental material [Yes] As written in the abstract - A reference implementation can be found at https //github. cwt.uud..oomppppppeeeee submi ssi on/ sttrucuredudrr weapcccuued_ttrraspppeee transposableeeeee...oo.o __aless___ss___
URL?
(d) Did you discuss whether and how consent was obtained from people whose data you'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 or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "JN_MNi9eju", "reviewer": "Reviewer_E3cM", "summary": "The authors study N:M structured sparsity, specifically the challenge of finding N:M transposable masks so that N:M sparsity hardware acceleration can be exploited for part of the backward pass computation in addition to the forward pass. The authors additionally tackle the challenge of adapting models trained with other kinds of unstructured or structured sparsity to specific topology constraints supported by hardware. The authors provide a detailed analysis of the problem of finding transposable N:M masks and asymptotics associated with solving the problems and present a practical solution that achieves good results in practice.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Overall the paper is very well done. There are a few issues in the experiments I’d like to see resolved and then I believe this work will be an excellent contribution to the community.\n\nIntroduction and Background\n1. Structure causing accuracy degradation in sparsification is not a hypothesis. It’s well documented empirically [1, 2].\n2. “However [unstructured sparsity’s] hardware cost makes it infeasible to use on modern architectures“. Recent work has shown that unstructured sparsity can be accelerated, although it still requires high sparsity to exceed the performance of dense computation [1, 3].\n\nExperiments (Changes Required)\n1. Table 3, claiming a ‘2x” speedup over ASP is not correct. 2x more of the FLOPs in the model can now be accelerated by sparse tensor cores, which provide up to 2x performance over dense tensor cores. Let's say dense models speed is (fwd + bwd + update) / dense_throughput. For simplicity, we’ll say fwd = bwd = update so baseline takes 3 * fwd / dense_throughput seconds. The ASP model would then take fwd / (2 * dense_throughput + 2 * fwd / dense_throughput = 2.5 * fwd / dense_throughput. Your model would then take 2 * fwd / (2 * dense_throughput) + fwd / dense_throughput = 2 * fwd / dense_throughput. Thus, ASP provides a 3 / 2.5 = 1.2x speedup over the baseline and you would provide a 2.5 / 2 = 1.25x speedup over ASP. In reality your speedup will be lower because not all operations (e.g., batch normalization, activation functions) are accelerated by sparse tensor cores and the sparse tensor core operations will not fully realize the theoretical 2x gain over the dense tensor cores. This should be corrected in the authors’ response.\n2. I understand that 4:8 transposable masks have a similar MD to 2:4 masks but comparing 4:8 sparsity to 2:4 sparsity is not apples-to-apples as I expect 4:8 sparsity will make it much easier to maintain model quality. I like the inclusion of 4:8 sparsity results, but I’d also like to see 2:4 transposable results to see what the accuracy loss looks like in comparison to non-transposable masks.\n3. In Table 2, what N:M are used? As I understand it, the algorithm complexity depends on these factors.\n4. X-axis in Figure 5 (b) should be scaled by 100 to be percent.\n\nExperiments (Changes Suggested)\n1. The hypothesis that MD is correlated with accuracy would be made much stronger with results on other kinds of structured sparsity. For example, block sparsity and channel-sparsity. As someone who works on this topic, I’d be very interested to see these results.\n2. In Table 1, it might be nice to include the MD normalized to unstructured as well. This would make it easier to compare across the different structures for the reader.\n3. Most sparse training algorithms only perform mask updates periodically to reduce overhead (and also because it usually leads to higher accuracy). The update period is usually ~100 (e.g., with RigL). 40 is a tighter bound, but you could also run 100 (in Table 2) to align with prior work.\n\nOrganizational, Spelling and Grammar\n1. On page 2, your 3 questions are in a different order than they’re shown in your diagram (Figure 4)\n2. “sparse core tensor” should be “sparse tensor core”\n3. “|” before “In” should be deleted.\n\nAdditional Improvements\n1. Nvidia has recently proposed using permutations to reduce accuracy loss (talk, poster from SNN). How do permutations affect your MD metric? Do the results still correlate with accuracy? Do they make finding transposable N:M masks more difficult? These might be interesting questions to discuss in your conclusion.\n\nReferences\n1. https://arxiv.org/abs/1911.09723\n2. https://arxiv.org/abs/1811.00206\n3. https://arxiv.org/abs/2006.10901\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not identify potential negative societal impact in this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I did not identify ethical issues with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4hrs"}, "extra_text": {}}, {"review_id": "1Uf8-TgXPeB", "reviewer": "Reviewer_o2wE", "summary": "The sparse tensor core introduces the N:M sparsity in the latest Nvidia Ampere GPUs,  which bring sparse neural network deployment into the mainstream.  Most methods only focus on improving sparse model performance and compression ratio rather than speed up the training phase.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a method to utilize ampere GPUs sufficiently by exploring N:M sparse training. To find the optimal transposable mask, this paper formulates the problem as an integer program solved by an approximated algorithm (2-Approximationalgorithm).\n\nStrength:\n      1. Direct sparse training using modern hardware is an important direction to train gigantic models [2]. \n      2. The 2-Approximation algorithm is novel and efficient.\n      3. The performance of ResNets and Bert models is persuasive.\n      4. The code is available and can reproduce the results.\n\nTypo: line 273  \"N   :  M \"       \n\nThe main flaw of this paper may be the gap between theory and practical.  I look forward to authors give more discussion.\n\nOverall, this paper goes out an important step about fully sparse training, which should draw more attention in the future.\n\nI am inclined to accept this paper. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main flaw of this paper may be the gap between theory and practical.  I look forward to authors give more discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "1JauHbAHJHr", "reviewer": "Reviewer_PZCA", "summary": "The paper proposes a method to quickly find masks that allow DNN models to train with N:M sparsity. Prior works mainly leverage N:M sparsity for inference (i.e., forward pass), but training cannot directly benefit from N:M sparsity because model weights are transposed during backpropagation to calculate gradients. Therefore, the N:M sparsity constraints may no longer be satisfied during backward pass. The paper suggests that it is possible to find so-called N:M transposable masks, which allow both the forward pass and the backward pass of a DNN training to perform N:M sparse computation. One key challenge in this task is to find such transposable masks in a lightweight way since sparsity masks may need to dynamically change in order to get on-par accuracy as dense training. To quickly find masks that satisfy the N:M transposable mask constraints, the paper proposes to use a greedy-based approximation method. The authors show that such a method adds a modest amount of runtime overhead and scales almost linearly with respect to the input sizes. The paper conducts evaluations against some computer vision (e.g., ResNet) and NLP tasks (e.g., BERT fine-tuning tasks) to show that such a training regime can bring comparable accuracy as dense training.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n\n-- The transposable mask is an interesting idea to enable the system capability of N:M sparse training. \n-- The proposed 2-approximation solution adds a low overhead in finding transposable masks.\n\nWeaknesses:\n\n-- The proposed transposable N:M masks add strong constraints to weight diversity, which may limit the expressiveness of the model. \n-- No real training speedups from the proposed method, because real hardware constraints are not satisfied. \n-- Lack of details of implementation and hyperparameter settings. \n-- Baseline results are inconsistent. \n-- No discussions on how model convergence or training dynamics are affected by N:M sparse training.\n\nComments:\n\n1. The transposable N:M sparsity masks seem to add very strong constraints to the weight matrices, which might limit the model's expressiveness in a significant way. Indeed, after applying transposable N:M sparsity masks, there won't be enough mask diversity for 2:4 sparsity. As a result, the paper has to find the transposable N:M sparsity in 4:8. This is a deviation from real hardware constraints because no existing hardware supports 4:8 sparsity (Nvidia sparse tensor core supports 2:4).  The proposed method, therefore, cannot speed up training on real hardware either. It is disappointing as the paper motivates itself as a way to accelerate sparse training on real hardware in the introduction and only to find out later that the solution does not really work on real hardware. \n\n2. Some of the results of the evaluations are inconsistent, especially the baseline results. While the baseline results for ResNet18 and ResNet50 are 69.7% and 76.1% in Table 3, they become 70.5% and 77.3% in Table 4. Why are there two results for the same dataset and task? Which baseline should we look at? If we take 77.3% as the baseline result for ResNet50, then the proposed N:M sparse training actually leads to a non-trivial drop (77.3 vs. 76.6) in Table 3, and the \"no accuracy degradation\" claim is also not true. Please double-check the results and also provide detailed hyperparameter information. \n\n3. Despite claiming 2x speedup, no real training time is reported for all evaluations. The training cost depends on both the training time per iteration as well as the total number of iterations needed to converge. Although N:M sparse training might reduce the training time per iteration by 2x,  if the N:M sparse training takes more iterations to converge to get the same accuracy or introduces training instability, then N:M sparse training cannot really reduce the training cost and reducing the cost of finding transposable N:M sparsity becomes even less motivated.  Furthermore, the 2x speedup claim also seems to be problematic because (1) finding the transposable N:M masks still add non-negligible cost, which would make the speedup to be less than 2X, and (2) even with sparse tensor core, one cannot expect a 2x speedup because a DNN contains more components than just the matrix multiplication, such as non-linear functions or BatchNorm, which cannot be accelerated by sparse tensor core. \n\n\n4. The paper lacks details for implementation and hyperparameter settings. Can the authors add details for how the model has been trained, such as the number of update steps, the batch size, etc. for both the baseline and the N:M sparse training, as well as parameters for AdaPrune? The current paper doesn't seem like it could be reproduced. \n\n5. The proposed AdaPrune only seems to convert models trained with 8:4 to 4:2 for inference. Can it also be used to accelerate the training speed as well? \n\n6. The writing of Section 5 seems to be not good, with many typos and grammar errors. Just to give a few examples: \n\nIn line 223, \"…over regular training, The algorithms…\" -> Change \",\" to \".\". \nIn line 249, \"…where ASP do not.\" -> \"does not\"\nIn line 261, \"…to accelerate training. but what should we do…\" -> Change \".\" to \",\". \nIn line 262, \"…wish to deployed the output…\" -> \"wish to deploy\".\n\n-------------------------\n\nAfter a series of discussions, the authors have addressed my concerns. I have increased my score from 4 to 6.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the limitations in the detailed comments. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: I want to thank the authors for their active engagement with the reviewers in the rebuttal period, and I'm happy this lead to some modification of the paper (as outlined by the authors) that I think greatly improved the work. 

The proposed method seems novel and valuable to the community, coupled with thorough experimentation and a clear exposition, I think this paper matches the requirements for the conference. 
Decision: Accept (Poster)