Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks

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 and require thousands of petaflops for the training process. For this reason, compression of DNNs training and inference process is a research topic of paramount importance in both academia and industry. The main techniques of compression include quantization , knowledge distillation , and pruning .

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 or filter pruning, are more hardware friendly. Unfortunately, these methods usually fail to keep the original accuracy for high compression ratios . Finding an optimal structured sparsity pattern is still an ongoing research topic.

Recently, Nvidia announced the A100 GPU, containing sparse tensor cores which are able to accelerate fine-grained sparse matrix multiplication. The sparse tensor cores in A100 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-grained 2:4 sparsity structure, i.e. out of every four contiguous elements in $W$, two are pruned. Nvidia suggested a two-fold scheme for pruning a pretrained dense model: (a) Define a fine-grained 2:4 fixed mask, and (b) retrain with the masked weights using original training schedule. Indeed, the Nvidia approach is very appealing for the common case where a pretrained dense model is given.

While the Nvidia method works well on many models, a 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. suggested a method that trains from scratch a model with $N:M$ fine-grained mask, using a sparse-refined straight-through estimator (SR-STE). Similarly to the quantization-aware-training methods , they maintain a dense copy of the weights and prune it in every iteration, passing the gradients using the straight-through estimator . 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. that aims to reduce memory footprint for sparse training from scratch, Zhou et al. only eliminates the need to train a dense model before pruning it.

Motivated by these promising results, our goal here is to answer three remaining questions: (Fig. 1)

How to rank different types of sparsity masks? We suggest a new measure called “mask diversity", which is the first to connect mask constraints and network accuracy (Section 3).

Can fine-grained sparsity masks accelerate training? We start by observing both the forward and the backward matrix-multiplications involving the weight matrix $W$. Since the backward pass requires using the transposed matrix $W^{T}$:

Can we change the type of sparsity mask structure without re-training? Different hardware devices can support different types of fine-grained sparsity masks. Therefore, we 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).

Related work

Pruning of neural networks weights has been extensively investigated, starting with classical methods in the late 1980s and then amounting to dozens of papers published in recent years. Since DNNs are generally over-parameterized, pruning the weights reduces their memory footprint. In special cases, when the sparsity mask has a 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 has emerged. The goal is to train models that cannot fit into currently available hardware. Next, we briefly overview the structured, unstructured, and accelerating-sparse-training categories.

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 , approximate $L_{0}$ regularization , or connection sensitivity . Recent methods , 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 using the original training schedule. These methods are able to achieve over 80% sparsity on ResNet50- ImageNet dataset . Despite the high sparsity ratio that can be achieved with these methods, modern hardware cannot efficiently utilize such a form of sparsity for reducing computational resources .

It removes weights in specific location based patterns, which are more useful for hardware acceleration. Such methods can be applied at either the level of channels or layers. For example, Li et al. remove the channels with the lower norm, Luo et al. prune channels according to the effect on the activation of the following layer, and split the filters into multiple groups, applying a 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 a reasonable accuracy with sparsity levels higher than 50%. As observed by Liu et al. , filter pruning of a pretrained dense over-parameterized model is rarely the best method to obtain an efficient final model. Thus, here the structured pruning serves mostly as a DNN architecture search for the optimal compact model . Our work is most closely related to Zhou et al. , which is the first work that attempted training with a fine-grained $N:M$ structured sparsity mask, as explained above.

The most common approach for sparse model deployment requires a three steps process: (a) train a dense model; (b) define a sparsity mask (c) fine-tune while enforcing the mask on the model’s weights. The lottery ticket hypothesis of Frankle & Carbin demonstrates that we can avoid the dense training, i.e., step (a), had we known how to choose the appropriate mask. Since Frankle & Carbin 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 a predefined fixed mask results in some accuracy degradation (Gray et al. that requires expanding the model size), several researchers 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 et al. does not aim to reduce the model memory footprint during training, but rather accelerate inference while avoiding dense pre-training. To that end, they keep a dense weight matrix, and in each iteration they re-calculate 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 a pretrained dense model is not given, and one wishes to obtain a fine grained $N:M$ sparse model for inference. While our work focuses on the setting of Zhou et al. , we argue that it can easily combined with Evci et al. work, as it aims to solve a different issue within the same problem.

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 a new measure, called mask-diversity (MD). MD is the number of all possible masks that adhere to the restrictions of the structure under similar sparsity level. As an example, we derive the MD for a tensor size $T$ under four different structure constraints:

Unstructured sparsity: no constraints, except for an overall sparsity level. This is the most common setting in the literature.

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 .

Transposable N:M sparsity: for a block of size $M\times 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.

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 (Section A.6):

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 multiplications are 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. 1). 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-grained sparsity). In this section, we tackle this issue by presenting a novel to find $N:M$ transposable fine-grained sparsity masks, where the same mask can be used to accelerate both forward and backward passes (Fig. 2). The required mask contains only $M-N$ non-zero elements, for every contiguous $M$ elements, in both $W$ and $W^{T}$ simultaneously. We formulate the problem and suggest two methods to generate the transposable mask.

In the following, we 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. 3) reduces to a min-cost flow problem. There is a vast literature on efficient min-cost flow algorithms (see e.g., ), however, the most efficient algorithms for our setting take time $O(M^{3}\log M)$ time for computing an optimal transposable mask for a block size of $M\times M$ [pp. 396-397]More modern methods that are based on interior point algorithms seem to be less efficient for our setting.. 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 a solution which is guaranteed to be within a factor of 2 of an optimal solution (to the given input), yet it runs in almost linear time.

We design a greedy 2-approximation algorithm (see Algorithm 1) having a low time complexity that can be used in practice without compromising too much the quality of the solution produced. Unlike the optimal min cost flow solution that runs in time complexity of $O(M^{3})$ for a block size of $M\times M$, Algorithm 1 has a running time of $O(M^{2}\log M)$ i.e., a time complexity that is almost linear in the number of block elements $M^{2}$. The approximation algorithm uses the same construction described in Fig. 4, but instead of running a min-cost flow on the graph, it 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.e., the minimal sum of edges that can be pruned to create a $\frac{M}{2}:M$ transposable sparsity mask). The next lemma establishes that Algorithm 1 finds a 2-approximate solution (proof in Section A.2, with an example showing the upper bound is tight):

Algorithm 1 produces a tight 2-approximate solution, i.e., $W(P)<2\cdot W^{*}$.

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 a 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 Section A.3 we extend the complexity analysis.

1 Experiments

In this section, we demonstrate the effectiveness of our proposed transposable $N:M$ fine-grained structured sparsity in computer vision and natural language processing tasks. We evaluate the suggested method in two cases: (i) initialize from a trained dense model and re-train with a fixed mask, similar to APEX’s Automatic Sparsity (ASP ), (ii) train from scratch and update the mask frequently, as done by Zhou et al. . 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 1, have a similar MD as 2:4 mask used in previous works . Experimental details appear in Section A.4. In Section 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 3.

Initialization from a 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) on the dense trained network and then fix the mask. In Table 3 we compare our method with ASP 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.

Sparse Training from scratch. In 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. 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. who changed the mask every iteration, we found that we can use 2-approximation scheme to extract the transposable mask every 40 iterations. Empirically we found that the 2-approximation scheme is on average within a factor of 1.2 from the optimal mask. The hyper-parameters used for training are equal to the ones suggested by Zhou et al. . In Table 4 we test the proposed method over ResNet18, ResNet50, ResNext50, Vgg11 (ImageNet dataset) and fine-tune of Bert (SQuAD-v1.1 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 4 we suggested 4:8 transposable-mask 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 on 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 as most DNN pruning methods focus on unstructured pruning, which reduces the memory footprint. However, current hardware implementations suggest that, unless very high sparsity levels are achieved, the model cannot be accelerated at all. Hence, commonly, the weights are simply decompressed before multiplication. To understand the problem we study the probability that an unstructured mask would not violate any $N:M$ constraint . Then we discuss two light methods to bridge the gap when a sparse model is given but the hardware does not support its structure.

Let $X=\{x_{1},x_{2},...,x_{M}\}$ be a block of independent and identically distributed random variables. Assume that with a probability $\rho$, $x_{i}$ 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$ to be $N:M$ 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

In Fig. 5(a) we plot Eq. 4 for the case of $\rho=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 , 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-violations. Removing active weights without re-training tends to severely degrade the model accuracy. To demonstrate the problem we used an unstructured sparse pretrained ResNet-50 model ($\rho=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 a given percentage. Here we used a block size of $M=8$. Notably, without any optimization even a $1\%$ pattern-violation results in severe degradation (Fig. 5(b)). Next, we describe two light methods to boost the accuracy.

Several works 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. 5(b) this simple fix, by itself, greatly boosts accuracy.

Recently, several works 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 a 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 parallel-AdaQuant technique to the pruning problem by defining its objective to be:

where $W$ is the original weight layer, $W^{\prime}$ is the weight layer we aim to find, $X$ is the output of the previous activation layer, $S$ is the weight sparsity mask, and $\odot$ 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 in Fig. 5(b), AdaPrune is capable of correcting the remaining error and obtain less than 1% degradation from the original unstructured-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% pattern-violation), since there we get 2.3% degradation using AdaPrune. We discuss and extend those experiments in Section A.1.

Conclusions

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 applications, or even use the extra time to improve the existing models. We need to take into account that accelerated training could introduce training instabilities. These models will need a 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

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] to [Yes] , [No] , or [N/A] . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:

Did you include the license to the code and datasets? [Yes] See Section LABEL:gen_inst.

Did you include the license to the code and datasets? [No] The code and the data are proprietary.

Did you include the license to the code and datasets? [N/A]

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. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.

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. 1

Did you describe the limitations of your work? [Yes] As explained in Section 6, there can be models that we didn’t check where the proposed method could introduce training instabilities. We didn’t notice any instability in all the models we checked. (Brian: ?)

Did you discuss any potential negative societal impacts of your work? [Yes] Yes, in section Section 6 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.

Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]

If you are including theoretical results…

Did you state the full set of assumptions of all theoretical results? [Yes] See Section A.2

Did you include complete proofs of all theoretical results? [Yes] See Section A.2

Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] As written in the abstract - A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.

Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section A.4

Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [No] The experiments were run with random seed one time, as in the previous works we compare to. Error bar not applicable.

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 Section A.4

If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…

If your work uses existing assets, did you cite the creators? [Yes] In the url https://github.com/papers-submission/structured_transposable_masks that includes our implementation, we cite the creator of existing assets with link to their license

Did you mention the license of the assets? [Yes] In the url https://github.com/papers-submission/structured_transposable_masks that includes our implementation, we cite the creator of existing assets with link to their license

Did you include any new assets either in the supplemental material or as a URL? [Yes] As written in the abstract - A reference implementation can be found at https://github.com/papers-submission/structured_transposable_masks.

Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A]

Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

If you used crowdsourcing or conducted research with human subjects…

Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]

Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]

Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]

Appendix A Supplementary Material

To further examine AdaPrune capabilities we checked two additional settings: (a) starting from pre-trained dense model, and (b) staring from less constrained N:M mask.

While this case is more common, we expect to see some degradation as we know that we have 50% mask violations. Yet as can be seen in table 2 we managed to restore accuracy to 2-3% of the full-precision baseline using just AdaPrune. To further improve results we applied batch-norm-tuning as suggested by Hubara et al. and kept the first and last layers dense which results in less than 2% degradation. We believe it to be the first tolerable post-training-pruning results reported.

A.1.2 AdaPrune from N:M sparse

In Section 3 we explained why as the block size decreases the mask diversity decreases. Thus, we expect to have many violations when a pre-trained sparse model with $N_{1}:M_{1}$ translates to $N_{2}:M_{2}$, for $N_{1}>N_{2}$ and $M_{1}>M_{2}$. We argue that this might be a common case in the future as different hardware vendors would support different formats. In table Table A.2 we can see results of converting ResNet-50 model trained with $4:8$ sparsity pattern to $2:4$ and $1:2$ patterns. As can be seen, converting from $4:8$ to $2:4$ produces results with negligible accuracy degradation (less than 0.5%). Therefore, we argue that AdaPrune is an efficient and useful approach to convert models which were optimized on a different hardware than the one in use, as it removes the need for full sparse training. This is even more important when the training data is not available.

A.2 Proof of Lemma

Algorithm 1 produces a tight 2-approximate solution, i.e., $W(P)<2\cdot W^{*}$.

Consider any node $i\in V\setminus\{s,t\}$. Let $E^{\prime}(i)=\{e^{\prime}_{1},e^{\prime}_{2},e^{\prime}_{3},...e^{\prime}_{M/2}\}$ denote the edges of an optimal solution that are adjacent to node $i$ and sorted in ascending order from light to heavy. Let $E(i)=\{e_{1},e_{2},e_{3},...e_{M/2}\}$ denote the first $M/2$ edges adjacent to $i$ in $P$ with respect to the order in which Algorithm 1 picked them. By construction, we have that for all edges in $E(i)$:

We note that we can truncate the list of $i$ at $M/2$, since if $i$ has more than $M/2$ edges adjacent to it in $P$, then any such edge $(i,j)$ would also appear in $E(j)$ (among the first $M/2$ edges adjacent to $j$) by the minimality of the solution $P$. Thus, the union of the lists $E(i)$ contains all edges in $P$. We now prove by induction that for any $n$, $n\geq 1$,

Base case ($n=1$): $w(e_{1})\leq w(e^{\prime}_{1})$, since by construction of Algorithm 1, edge $e_{1}$ is the lightest edge adjacent to node $i$.

Inductive step: assume $w(e_{n})\leq w(e^{\prime}_{n})$, then it must hold that $w(e_{n+1})\leq w(e^{\prime}_{n+1}))$; otherwise, if $w(e_{n+1})>w(e^{\prime}_{n+1}))$, then $e^{\prime}_{n+1}$ should have been considered before $e_{n+1}$ and also chosen by Algorithm 1.

To complete the proof, our goal is to charge the weight of the edges in $P$ to the weight of the edges in the optimal solution based on the above inequality. However, note that an edge $(i,j)\in P$ may appear in only one of the lists $E(i)$ or $E(j)$. Thus, for example, two edges in $P$, $(i,j)$ and $(i^{\prime},j)$, may charge their weight to the same edge $(i,i^{\prime})$ in the optimal solution. Clearly, this “double" charging can happen at most twice for each edge in the optimal solution, hence:

In the following, we show that our analysis of the upper bound of 2 on the approximation factor (proved in the lemma) is asymptotically tight. Consider the example in Fig. 1(c). Let us assume we want to zero out one element in each row and column in the block of size $4\times 4$ presented in Fig. 1(a) using the 2-approximate algorithm (Algorithm 1). First, we need to convert the block into a bipartite graph (as suggested in Figure 4). This construction appears in Fig. 1(b). Next, we sort the the edges from light to heavy and go over the sorted list. In Fig. 1(c) we show the seven iterations of the 2-approximate algorithm. All edges are added to the list of chosen edges $P$ up until the 7th iteration. The algorithm stops at the 7th iteration, since after adding edge $u_{4}\xrightarrow{1}{v_{4}}$, every node is already “covered" by at least one edge (in other words, each row and each column has at least one entry chosen for pruning). Note that the optimal solution would choose the edges that correspond to the entries on the diagonal (i.e., $u_{1}\xrightarrow{1}{v_{1}},u_{2}\xrightarrow{1}{v_{2}},u_{3}\xrightarrow{1}{v_{3}}$, and $u_{4}\xrightarrow{1}{v_{4}}$), summing up to a total weight of 4. Hence, we get an approximation ratio of $\frac{7}{4}$. It is easy to see that when using the same construction for a general block of size $M\times M$, we get an approximation ratio of $\frac{2M-1}{M}$, asymptotically converging to 2 as $M$ goes to infinity.

A.3 Min cost flow vs. 2-approximation run-time analysis

A.4 Experiments Setting

In all our experiments we use 8 GPU GeForce RTX 2080 Ti.

We used a small calibration set of 1000 images (one per-class). We run AdaPrune for 1000 iterations with batch-size of 100. For the results in the supplementary material, we kept the first and last layers dense.

We used torchvison model-zoo as our pre-trained dense baseline. For all ResNet models we used the original regime as given by He et al. , i.e., SGD over 90 epochs starting with learning rate of 0.1 and decreasing it at epochs 30,60,80 by a factor of 10. For BERT-large and MaskRCNN we used the defaults scripts as in Nvidia .

We use the exact same setting as given by Zhou et al. .

A.5 N:M hardware requirements

For conventional hardware, Broadly, N:M sparsity requires adding an N+1 to 1 multiplexer (N+1:1)to the adder tree in the code of the matrix multiplication. engine. Thus switching from 2:4 fine grained sparsity to 4:8 requires 5:1 multiplexers instead of 3:1. The simplest implementation of a multiplexer is build of set of 2:1 multiplexers which means that the area required for the multiplexers scale logarithmicly with the number of zeros in the block (N).

A.6 Mask diversity Derivation

Let us consider $W$ to be a block of size $n\times n$ from a weight tensor and our desired sparsity level to be $N/M$. Thus, the MD of unstructured sparsity consists of all possibilities to pick $N$ values out of $B$ (Eq. 2 (a)). The MD increases with the block size ($B$), which might explain the recent success of global pruning. Next we investigate, fine-grained $N:M$ structured sparsity . This approach requires us to zero out $N$ values in each block of size $M$. Since we have $\frac{T}{M}$ blocks this results in Eq. 2 (b). If we wish to enforce the constraints on both row and columns of the matrix (i.e., $N:M$ transposable structured) the diversity decreases. Let us first assume $N=1$. The number of possibilities in each block of size $M^{2}$ is $M!$. Repeating this process for general $N$ in all the $\frac{B}{M^{2}}$ blocks results in Eq. 2 (c). A more constrained mask, is a fine-grained $N:M$ mask with a sequential structure. Here we require that each $M$ contiguous elements would contain $N$ sequential zeros. In each block of size $M^{2}$, there are $M-N+1$ options of sequential zeros. Applying it on all the $\frac{B}{M}$ blocks results in Eq. 2(d).

A.7 Mask diversity Experiments

In additional to the results in Section 3 we experimented in Fig. A.3 with ResNet50 over ImageNet dataset. In all our experiments we used one-shot pruning from dense model and applied the same regime as the original training as suggested by Nvidia .

A.8 2:4 transposable mask

In Table A.4 we show experiments with the 2:4 transposable mask in the "training from scratch" setting. Moreover, after we published the first version of our paper, researchers from NVIDIA continued our work and demonstrated on a large set of models that one can achieve less than 1% degradation even with 2:4 transposable masks in the "training from a trained dense model" setting. As can be seen, 2:4 transpose mask can achieve high accuracy in part of the models. This results correlates with the shown MD, since 2:4 transpose mask has similar MD to 1:2 mask which already achieved high accuracy (Fig. A.3). Despite this, in some scenarios 2:4 transposable does not work as well, as in the case of finetuning BERT-Large on SQuAD dataset. Here the 2:4 transposable mask incurred a $\sim 1\%$ degradation (90.18 F1 vs. 91.1 F1 for the dense model) while a 4:8 transposable mask incurred less than 0.5% degradation in F1 score (90.65 F1).