Channel Permutations for N:M Sparsity
Authors: Jeff Pool
Chong Yu
Venue: NeurIPS 2021 Poster (2021)
Keywords: network pruning
sparsity
N:M
structured sparsity
inference

Abstract: We introduce channel permutations as a method to maximize the accuracy of N:M sparse networks. N:M sparsity requires N out of M consecutive elements to be zero and has been shown to maintain accuracy for many models and tasks with a simple prune and fine-tune workflow. By permuting weight matrices along their channel dimension and adjusting the surrounding layers appropriately, we demonstrate accuracy recovery for even small, parameter-efficient networks, without affecting inference run-time. We also present both a quality metric to simplify judging permutations as well as efficient methods to search for high-quality permutations, including two optimizations to escape local minima. Finally, we share an ablation study to show the importance of each part of our search algorithm, experimental results showing correlation between our quality metric and final network accuracy, improved sparse network accuracy using our techniques with insignificant overhead to training time, and the transformation of unstructured to structured sparse workloads. Code to use these techniques when generating a 2:4 sparse network is available at https://github.com/NVIDIA/apex/tree/master/apex/contrib/sparsity.

Channel Permutations for N:M Sparsity
Jeff Pool
Chong Yu Academy for Engineering and Technology, Fudan University NVIDIA
NVIDIA jpool@nvidia.com
chongy@nvidia.com
Abstract
We introduce channel permutations as a method to maximize the accuracy of N:M sparse networks. N:M sparsity requires out M consecutive elements to be zero and has been shown to maintain accuracy for many models and tasks with a simple prune and fine-tune workflow. By permuting weight matrices along their channel dimension and adjusting the surrounding layers appropriately, accuracy recovery for even small, parameter-efficien networks, without affecting inference run-time. We also present both quality metric to simplify judging permutations as well as efficient methods to search for high-quality permutations, including two optimizations to escape local minima. Finally, share ablation study to show the importance of each part of our search algorithm, experimental results showing correlation between our quality metric and final network accuracy, improved sparse network accuracy using our techniques with insignificant over- head to training time, and the transformation of unstructured to structured sparse workloads. Code to use these techniques when generating a 2:4 sparse network is available https://gthub.com//VDDAAAAA httpa//wwwwwoooooooooooooooooooa
demonstrate
Introduction
Deep Neural Networks (DNNs) excel at complex tasks such as image classification, object detection, and language modeling. Their success often comes at the cost of immense computational complexity, and growing model size generally results in even higher-quality results. To combat this ever- increasing computational workload inference, various approaches have been used to save effort; for example, network pruning removes weights from the network, and quantization can replace floating-pols operations with simpler integer operations. We focus one type of network pruning that is accelerated in hardware: 2:4 structured sparsity [22] (a particular form of the more general N:M sparsity), since it has been shown maintain accuracy across wide range of networks and tasks while being easy to save computation. While many networks do recover accuracy with a fine-tuning step, some small, parameter-efficien image-classffication networks that were designed with economy of memory and computation in mind cannot recover the accuracy lost due to pruning with this suggested workflow. Further, this workflow repeats the dense training all over again, which, while straightforward, can be costly if the lifetime of the deployment model is not long enough to amortize this extra training.
We seek to address these shortcomings with the observation that the 2:4 pruning step, which forces two out of every four consecutive elements be zero (the "2:4 constraint"), ) sometimes must prune relatively large, and intuitively important, value. If different options were available to each group of four values, then more advantageous choices can be made, as illustrated in Figure T When the example weight matrix (top-left) is pruned with 2:4 sparsity in its original order, it results in a sparse matrix (top-right) with total weight magnitude of 44.5. By first changing the order of the columns in the matrix, though (bottom-left), the resulting sparse matrix (bottom-right) has a total weight magnitude of 58.6. It simple to find this fruitful column permutation in such small example, but
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

A
C
D
F
6
A
8
D
E
H
0.4
1.1
1.5
6.9
0.8
6.7
5.4
8.8
Prune
0
0
1.5
6.9
0
6.7
8.8
1.5
0
0
8.9
Original
2:4 Sparse
Permute Columns
Total Magnitude: 44.5
E
A
D
C
H
8
0.8
6.9
1.5
11
6.7
Prunn
5.4
6.9
0
8.8
6.7
8.8
1.5
0.5
1.3
0.6
4.2
8.8
8.9
0
8.9
4.2
Permuted
2:4 Sparse (Permuted)
Magnitude:588
Figure 1: Permuting weights before pruning them helps preserve weight magnitude.
the complexity of the problem explodes with problem size. Further, once permutation is found, applying it to some layer of DNN can result in performance overhead at run-time [14]. In this work, we give solutions both these problems and show several benefits of using permutations for N:M sparsity. While we focus on a particular variant of N:M structured sparsity for practical reasons (acceleration with availlle hardware (26)). the techniques and observations herein apply equally to all N and M. Similarly, our permutation search strategies can be used to increase or decrease any metric of interest, not just magnitude.
We note that while weight magnitude not proven to be the optimal pruning metric, and that increasing magnitude is not guaranteed improve accuracy, show it to work well for the cases studied herein.
Our contributions include (1) method of permuting input channels of weight matrices without changing the output the network or incurring a performance overhead, (2) an efficient algorithm for generating unique permutations for N:M structured sparse matrices, (3) two methods to overcome a shortcoming of greedy permutation generation algorithms, (4) searching for and applying permuta- tions to improve accuracy of 2:4 sparse networks, and (5) transparently transforming unstructured sparse to structured sparse matrices.
The rest of this paper is as follows: Section 2 discusses previous work in the area and provides background information on matrix permutations, and (ictionn[prreeee our method of to permuting weights of neural network with no run-time overhead. In Section 4 we present quality metric, an
intractable exhaustive solution to find a high-quality permutation, a greedy solution, and improvements to the baseline greedy algorithm. We share ablation study, quality metric/accuracy correlation, accuracy improvements, and results transforming unstructured to structured sparsity in Section [ along with brief discussion of the runtime needed to search for permutations. Finally, we offer discussion and areas for future work in Section 3
2 Related Work and Background
Network pruning. Removing weights from network used to reduce both the storage and bandwidth required for the network as well the computational power required to deploy the network. The area of network pruning multi-dimmnsional:: one can prune to different amounts, with different sorts of structure or regularity, using weight magnitude or other metrics to choose which weights to make zero [23 [6), pruming gradually (6 33 or in one shot, kceping the network the same size growing it to accommodate for the sparsity [5) etc.
Let focus on structure and regularity; this dimension is the most important for this work and is generally composable with the others. Early work in pruning DNNs used unstructured sparsity, removing individual weight values (6) but research soon moved on to pruning at coarser granular- ity 34 19 18 [5]: at the cost of accuracy loss for the same amount of sparsity 21] removing smaller, dense workload which easy to accelerate. At
entire channels or filters results
extreme, sparsity can be in the form of blocks [5] entire layers 4 Simply put, network pruning has been balaneing act between maintaining accuracy and inducing enough sparsity to impart useful benefit, either in storage requirements or the runtime of the resulting model.

---

N:M structured sparsity. Recently-eleased hardware accelerates matrix- wwltimmy-accmmmaaenee instructions if one operand satisfies 2:4 sparsity constraint [22] a particular form of N:M sparsity in which at least N out of every M (contiguous, aligned) elements are zero. In particular, this hardware requires the sparsity to be applied to the input channel dimension, C. of convolutional layers: weights along this dimension are divided into groups of four weights, and two of them are forced to zero. A workflow to generate networks that satisfy this 2:4 constraint, using a form of Learning Rate Rewinding [28]. has been empirically verified to maintain accuracy across a wide range of networks and tasks (with the exception of the aforementioned small, parameter-efficient networks).
Hubara et al. report a technique for finding good transposable masks for use in both forwards and backwards passes [T]], as well as two techniques for improving accuracy when fine-tuning N:M sparse networks for inference, but they are orthogonal to this work. Though we focus on fine-tuming an existing dense network, there has been work in training N:M networks from scratch 37 but results for 2:4 sparsity fall short of the dense baseline.
matrix changes the order of the individual rows or columns that make up the matrix, and can be specified as a vector P of indices, with no repetitions, from 0 to the size of the dimension (-1). These indices are used to permute the matrix by moving the column (or row) at index j to position P[i]-
Matrix permutations. Applying a permutation
be permuted in two ways without materially affecting the results: permuting the inner dimension or the outer dimension of the operands. Simultancously permuting the inner dimension of both operands changes the order in which the partial sums of the dot-produe are computed, but not the eventual sum in each position of the output matrix. An example of this appears in the right side of Figure 2 Layer i's input channel, or C, dimension, common to both operands, is permuted (numbers and 2) by permutation P:, and the output is unaffected. On the other hand, permuting rows of the first operand (number on the left side of Figure 2 or the columns of the second operand, either outer dimension, affects the position of the corresponding rows or columns in the output matrix. For this reason, when rows are permuted in the weight matrix of neural network, it is necessary to apply the inverse permutation to the output to restore the original order. Since we are concerned with the order of only the C' dimension, which defines each 2:4 group, permutations will be applied to the inner dimension of GEMM operations in high biggh-eerforance math libraries (3 Herein, permutations will apply to columns of a matrix's 's weights or channels of a convolution tensor's weights interchangeably. Each layer (or, as discussed in Section 3 group of layers) can have a unique permutation, P; (for layer i).
A matrix multiplication's 's operands
These properties have been used to cluster large values together when pruning a network with group sparsity, such as blocks or vectors [4]. The approach in this prior work has two shortcomings: it (1) incurs a runtime performance penalty and (2) can not escape from poor local minima. Permutations have also been used to make unstructured sparsity easier to accelerate on systolic arrays 2
3 Applying Permutations
3.1 Permutations Across Layers
To apply a desirable permutation to some layer i's C' dimension, we can permute its weights just once, offline. To avoid an explicit operation apply the same permutation to its input activations, we exploit the property that permuting weights along the output channel, or K, dimension also permutes output activations along the K dimension, and the outpu/ channel dimension of one layer's activations is the input channel dimension of those same activations when used as the input to the next layer.
Consider permutation P. desired by layer i: that layer's weights will be permuted along C₁ as indicated by the 'I' on the right side of Figure 2 In order to keep the output constant, its activations need the same permutation applied along C; (*2"). We effect this input activation permutation with another offline step: permuting the previous layer's weights along K;-1 ('3'). By permuting the K dimension of layer - I's weights to reorder its output activation's 's K dimension, we have prepared layer i's input activations as required by P. without an explicit permutation operation. Since each layer needs to permute its own weights along only one dimension and can "absorb" an orthogonal permutation in the other dimension without conflict, we incur no performance overhead at run-time. We note that this simplification could also be applied to past work to climinate the
3

---

Layer 1-2's output Layer i's Input
2
1u
hr
by
by
bx
ba
ha
h4
kx
bu
kg
kg
Cu
Ga
bg
bg
kg
Wio
Wes
Win
Wis
Og
OO:
O1
0g
C
Wio
Was
Win
Win
Ol
O6
0g
Ku=ci
Wou
Wes
Wen
Opo
Og:
Og
On
K:= Ciu
Wio
Wis
Olo
Ol
On
00
Ws
Wa
Wa
Oao
Oj.
Op
On
Layer i-1
Layer
Figure 2: Permuting along the inner dimension of a GEMM (Layer i, right side) does not change the output, but permuting along an outer dimension (such Layer i - 1's rows, left side) causes corresponding permutation in the same dimension of the output. We exploit these two properties to apply some desired permutation P. Layer i's weights ('1"). The required matching permutation in the same dimension of the input activations ('2') is effected by permuting the previous layer's weights along rows using the same permutation (33), requiring run-time overhead. Colors show the order of rows (activations) and columns (weights) involved in each GEMM operation.
reported performance overhead due each layer's desired permutation being applied in multiple dimensions [4], potentially at the expense of final network accuracy.
So, each layer may two permutations: one that is for itself, applied along its C' dimension, and one that is desired by a downstream layer (or layers, below), applied along its K dimension. For example: if following layer + has its desired C' permutation, layer i would be responsible for permuting the activations by permuting its own weights' K dimension. This second permutation is orthogonal to and will not conflict with its own C dimension permutation. Similarly, layer i can apply a permutation to its C dimension without affecting the K permutation for layer i.
3.2 Handling Complexities of Deep Neural Networks
Forks and joins. Many network types, including Residual Networks 77]. have forks and joins in their network graphs, leading to layer being a "parent" to multiple layers in that its outputs are inputs to some number of downstream layers (children). Since a parent layer can only have one output channel order, all children of parent must share the same input channel order: the children's 's permutations are constrained to be identical. Foreing the same permutation to be used for multiple layers is straightforward: concatenating the weight matrices along the input channel dimension (which, if coming from fork, will be of the same size), searching for a good permutation (see Section 4 and splitting the earlier concatenation will force multiple weight matrices to have the same permutation that has been optimized for all layers. layer with multiple parents (after a join, for example), can apply its input channel permutation, once found, to its parents' output channel dimension.
parent, we can stop only when there is a GEMM operation (convolution, FC layer, recurrent layer, etc.), which can apply the permutation to its weights' outer dimension to prepare the output activations. Until we encounter that operation, we must apply the permutation to the output channel dimension of the current operation then pass the permutation through the next parent. For example, convolution's 's outputs are generally subject to bias term, BatchNorm 13. and an activation function before they are input to the next convolution operation. Bias and BatchNorm operations have per-output channel parameters, thus they require the permutation to be applied to keep the network graph consistent with the originally parameterized function. Activation functions are typically performed per-element and have no notion of a channel dimension, so these types of layers do not need to apply the permutation before passing it through to their parent. Quantizing a neural network typically involves applying scaling factors to weight tensors, often per-channel 355: these factors permuted before the permutation is passed on.
Phss-through operations. When applying permutation
Input layers. For most layers in a network, the activation permutation can be accomplished by permuting the preceding weights, as above. The first layer cannot use this technique, though, since there are no preceding weights. We choose to forego permutations on the input layers, which generally not a noticeable decision since (1) input layers are often not pruned for accuracy reasons, and (2) networks use for image-basee tasks, like classification and object detection, have only three input channels, which are too few to be accelerated with 2:4 sparsity [22].

---

4 Finding Good Permutations
4.1 Efficacy: What Makes a Good Permutation
To avoid fine-tuning the network for every potential permutation, we construct a quality metric based only on the imput and permuted matrices. We use weight magnitude to choose weights to prune, so it is natural to maximize the total magnitude after the 2:4 constraint's 's application: a perfect permutation would preserve all the magnitude of the input matrix. In order for a perfect permutation to be achievable, the input matrix must have at least 50% sparsity in each row. The magnitude after enforcing 50% sparsity in each row, W W50%_rows rowsl: is an upper bound for a permutation's 's quality. We define a metric, efficacy, to quantify the quality of permutation applied to a weight matrix W (WP when permuted), terms of how much it improves the magnitude with respect to this upper bound:
W rows
WW2.4
fffccy = 1.0
W W50%_ 50%_roos
W2:4
If the magnitude after the 2:4 constraint of the original and permuted matrices are the same, then the permutation changed nothing and has an efficacy of 0.0. On the other hand, if the magnitude after the permutation is the same as that of the 50% row sparse matrix, then the efficacy metric will be a perfect 1.0 and it will be clear that no better permutation can be found. Finally. if the magnitude of the permuted matrix worse than the original matrix, the permutation's 's efficacy will be negative.
4.2 Exhaustive Searches
Intractability. For a network layer with C' channels, there are Ct channel permutations possible; this is nearly 21 trillion permutations for only 16 channels. However, there are two characteristics of N:M structured sparse matrices that reduce the number of unique permutations to only MIGGI. where G= C/M, the number of pruning groups, or "stripes" of the matrix. A stripe is a vertical slice of a matrix covering exactly M (aligned) columns. and the first simplifying observation is that the order of the columns within a stripe is immaterial; the same pruning decisions will be made regardless of this order, long the stripe contains the same columns. The second observation is that the order of stripes in the larger matrix does not matter, since pruning decisions are local to stripe. For layer with 16 channels and targeting 2:4 structured sparsity, the number of unique permutations is reduced to only 2.6 million. However, this value still grows much too quickly to test them all for even moderate channel counts: at 32 channels, there are nearly quintillion unique permutations. (See Appendix for details.)
C!
Algorithm. There are too many unique permutations check beyond a small number of channels, but smaller matrices can still be exhaustively searched (we will exploit this in Section 4.4). Here, we design an algorithm to generate only the unique permutations from the set of C! total permutations.
First, we define a canonical form for a unique permutation, exploiting the two observations from the previous subsection: permutation is unique only if each of its stripes' channels are in sorted order and the stripes are sorted with respect to each other (e.g. by the first value of each stripe). If two permutations result in the same pruning decisions, they will have the same canonical form. From these two restrictions, it can be seen that (1) all unique permutations start with column 0, and (2) if a column begins a group, then every column
must be member of previous group.
Next, we use standard recursive solution to the general problem of generating all permutations. We provide the permutation [0] and remaining columns [1.CC- - 1] input, and in turn move each entry from the remaining columns to the end of the current permutation. Each time the current permutation grows, the function is called again with the larger permutation and smaller list of remaining columns as input. Eventually, there will be no entries left in the remaining columns, and a full permutation can be added to a global list of permutations.
To limit this algorithm to only unique permutations, the recursive step is performed only if the current permutation is in canonical form and, therefore, unique. By checking at every stage of the generation algorithm, we can eliminate unnecessary effort and complete in linear time with respect to the number of unique permutations. (Listing 2 in Appendix C shows this algorithm.)
5

---

Algorithm 1: "Deep" greedy permutation search with bounded regressions to escape local minima
def Find_ fermulation(matrix num sum_cols, stripes_per grouugp escape cccape_attempis///e
permutation = for e in range(0,, num_colm num_cols)];
#Identity permutation
for escape escape_attempt in rangefescape pnngeesccpe_attemptt--+ 0, -1):
#Greedy phase: optimize stripe groups that give large benefits
while True:
optimizations Optimize Stripe_ Groups(matrixx permutation,, stripes Bacissper___rrr group;;;
optimization = Find Largest Positive P www.oo/mmeemoopppiiiiiioooo
if optimization is None: break;
permutation = Permute(permutation, optimization);
#Escape phase: attempt to escape the local minimum if
1:
src, dst = Unique_Random
Random Lottonnnnnneetuummmemom _olls;;
permutation Swap_ Columnn(permuuaation,, sre, dst);
return permutation;
#Final permutation
4.3 Greedy Incremental Improvements
We begin building an efficient permutation generation algorithm by adapting a greedy algorithm used for sparseeparseeeeee patterns [14]. At each iteration of the base algorithm, a sparsity mask is first determined to maximize weight magnitude. Then, all pairs of channels are speculatively swapped; only the swap that leads to the greatest increase in magnitude for the mask found in step one is enacted, generating a new permutation and concluding a single iteration. The algorithm ends when there is no swap that increases magnitude. This approach has useful qualities: it provably converges using greedy decisions at each step, it can be parallelized, and it can be optimized to minimize the cost of the C²2 potential channel swaps considered at each step. However, (I) it does not directly fit the problem of 2:4 sparsity, and (2) can get trapped in a local minimum.
Since there is no notion of blocks/vectors of zeros and nonzeros and our goal is not simply to cluster together values with large magnitudes, splitting the maak--eeeectinn and permutation selection separate steps is fruitless. Instead, it is better to consider the quality of a potential permutation as though the new mask were determined after the permutation, rather than trying to make a permutation conform to given mask. For N:M sparsity, this can be simplified: since each stripe is independent from every other stripe, the benefit to the entire matrix of swapping two channels is the same as the benefit to the two stripes to which those channels belong.
permutatioon-slletion -eleetttoonnneeetiinnnnooo into
This modified greedy algorithm converges rapidly, but it highly likely that this convergence will be to local minimum. We can show this empirically with matrices that are small enough to be solved exhaustively: Table shows that the basic channel swapping greedy phase finds the optimal solution for weeety-five 32x16 matrices (which are small enough to be solved exhaustively) only three times. As the input matrix grows, is increasingly likely that the solution will be local minimum.
4.4 Escaping Local Minima
Here, introduce techniques we use escape local minima without the possibility of falling into a worse solution. (Appendix D discusses some ways to change, but not necessarily improve, the minimum found; such techniques can be applied on top of those presented in this section, which provably do not worsen an already-converged solution.)
Escape technique 1: bounded regressions. After convergence, swapping any two channels and b will cause a regression in the permutation's 's efficacy. However, after repeating the greedy process until convergence, one of two things may happen:
1. There is no pair of channels that result in an improvement greater than the reduction caused by the swap of a and b. In this case, a and b are swapped back to their original position by the greedy step and the "new" solution the original converged solution.
2. There is some pair of channels and d that result in an improvement greater than the reduction of the swap of and b. The solution after e and d are swapped by the greedy process will be better than the original solution.

---

Since perturbing a solution by swapping any two channels and iterating to convergence will never reduce the efficacy of an sions." To prove the current solution's 's minimum is at least two swaps away from better solution, we can swap every pair of channels exhaustively upon convergence, but in practice we swap two random channels, up to B times. Any two columns can be swapped, but the search horizon is limited to depth of only one channel swap, so these bounded regressions are broad, but shallow. We must add depth to the search horizon to find solutions that are two or more swaps away.
solution, we call these perturbations "bounded regres-
Escape technique 2: narrow, deep search. We add depth to our search process by exhaustively optimizing stripe groups: choosing D stripes to form group and then exhaustively searching for the best permutation for that group in isolation. Optimizing a group of two stripes (D 2) is trivial since there are only 35 unique permutations. but this allows an effective search depth of 2: the best permutation for a group of 8 channels may be two swaps away from the initial order. In some
cases, D = 3 (or D = 4) is still feasible, with 5,335 (2.6 million) unique permutations, for search depth of (8). We use our O(N) algorithm from Section 2 to generate only the unique permutations from the set of over 479 million (nearly 21 trillion) potential permutations. Similar to bounded regressions, optimizing stripe groups as a method to escape a local minimum can be as simple as randomly choosing D stripes, optimizing, and then repeating the greedy phase. Since these stripe groups are optimized atomically, there is no chance for the overall solution to worsen.
Putting it all together Our final column permutation generation algorithm, shown in Algorithm [ maintains the iterative greedy step as phase one. However, each greedy step consists not of swapping two columns for maximum benefit, but exhaustively optimizing some number of stripes (we use D = 2 unless otherwise specified). Every potential group of D stripes, (#stripes) in total, is speculatively optimized, then the group with the most beneficial permutation is chosen, then all stripe groups are speculatively optimized again, and so on. This modification incorporates the narrow, deep searches into the greedy phase, helping to bypass some local minima without first converging to them.
We use bounded regressions to try to escape the local minimum found by phase onc. Phase two is instantaneous: two random channels are swapped. The real escape is up to the greedy phase, which attempts to improve upon the permutation that resulted from the swap. If the greedy phase escapes the previous minimum, it will repeat to converge to some new solution, else it will return to the previous minimum, and the escape phase will repeat again; we default to 100 total escape attempts.
5 Experiments
Ablation study. We examine the benefit of each technique used to escape local minima. As a baseline, we generate 1000 random permutations and choose the best. We then show two types of greedy phases: the baseline of simply swapping channels, and the enhanced option of optimizing stripe groups. When optimizing stripe groups, they can be comprised of either two or three stripes (8 or 12 total channels); the higher number affords a higher search depth at the cost of higher search time. We also examine using bounded regressions as a local minimum escape phase, allowing up to 100 total attempts to escape the various minima found during the greedy phase. We report the average efficacy for set of 25 random 128-column, 64-row matrices in Table Both enhancements improve on the baseline greedy approach; while the bounded regressions increase efficacy whenever they are used, increasing the number of stripes per optimization group provides larger benefit when used in the greedy phase. We also show that for a set of 25 random 32x 16 matrices, which can be solved exhaustively to find the optimal permutation, Po. our techniques find p. much more often than the baseline, and both techniques together improve even further.
Elftcacc//ccuracy correlation. Having shown that our techniques improve the efficacy metric over a baseline approach adapted to this task, we now show the utility of this metric by demonstrating a strong correlation between permutation efficacy and final accuracy of the fine-tuned network. We use
the ILSVRC12 (29] dataset to evaluate SqueezeNet v1.0 [12] and EfficientNet BO (3), which are
trained densely before being pruned and fine- -uned according to the procedure (2 implemented in
the ASP (23 library using PyTorch [27] and NVIDIA V100 24 accelerators. By first finding the best
permutation using the technique in Section 4.4 we can then generate permutations that evenly divide the efficacy into eighths, from 0 up to the best permutation's 's efficacy for each layer. Fine-tuning each of these new seven intermediate networks produces the curve of accuracy improvement vs. efficacy shown in Figure 3 Both networks' final accuracy increases monotonically with permutation
7

---

Table 1: Ablation study: escaping local minima with bounded regressions and using a more thorough greedy phase. BR (B) bounded regressions total of B pairs of channels are swapped when the greedy phase converges), OSG (D) optimize stripe groups of size D during the greedy phase. Search times were collected on a V100 accelerator.
25x
64x128
25x
32x16
Greedy Phase
Escape Phase
Efficacy (%)
Optimal Found (#)
Random (1000)
8.0 +.3.0
Channel Swap
46.5 #2.2
Channel Swap
BR (100)
47.1 #1.9
Channel Swap
BR (1000)
49.1 11.9
11
OSG (2)
47.7 +2.2
OSG (2)
BR (100)
48.2 +2.
15
OSG (2)
BR (1000)
49.5 +1.9
OSG (3)
51.9 11.7
17
OSG (3)
BR (100)
52.3 116
OSG (3)
BR (1000)
53.4 +1.8
25
(a) SqueezeNet v1.0
(b) EfficientNet BO
Accuracy improvement
Accuracy improvement
Tpl
Topl Top5
2
0.5
0.00
0.05
0.10
0.15
0.20
0.25
0.00
0.05
0.10
0.15
0.20
0.25
Welghted Average Efficacy
Weighted Average Efficacy
Figure Network accuracy increases monotonically with permutation efficacy.
efficacics (the weighted average over all weight layers is used as the x-axis). SqucezeNet v1.0 sees a large improvement after (relatively) poor permutations are used, while EfficientNet BO reflected a steady improvement through the entire range of efficacies.
Network accuracy. The primary goal of our technique is to allow the suggested workflow [22 to maintain accuracy for parameter-efficient networks. We demonstrate the success of channel permutations on several such networks. First, we train each network densely from scratch, using hyperparameters from public repositories (see Appendix [A). Then, we prune the dense models with 2:4 sparsity and repeat the training process again, resetting hyperparameters and optimizer state [22]. Finally, we search for and apply permutations (using the technique from Section 4.4) to each layer of the dense models, then prune and repeat the training process to fine-tune the remaining weights.
Accuracy results are shown in Table 2 the absolute top-1 and top-5 accuracy values are shown for the dense baseline network, then the difference in the default-pruned and permuted-pric pruned models with respect the dense baselines are shown the third pair of result columns. In every case, the accuracy of the network that was permuted before pruning is higher than pruning the network in its default channel order. Moreover, for small models that cause trouble for the default process, our technique yields models with accuracy that is equivalent to the dense baseline model. Finally, to show the universality our technique, we include results for larger models that did not struggle with the default pruning order; even for these networks, accuracy is improved. This suggests that permutations may be safely applied to all networks, not just those that fail without permutations, and also that the number of fine-tuning samples necessary recover accuracy may be reduced by using permutations. Appendix B shows the same trends for other tasks: semantic segmentation, object detection, language translation, and language modeling.
We perform one extra accuracy study, fine-tuning MobileNet v2 and MNASNet 1.0 after applying permutations found by the baseline Channel Swap strategy. Their final top- 1/pp1/ accuracies remained worse than the dense baselines by -1.26/-0.69 (MobileNet v2) and -0.66/-0.51 (MNASNet 1.0). While this is improvement over pruning in the default order, predicted by weighted average

---

Table 2: Using the same fine-tuning process, channel permutations improve accuracy for all networks and incur only trivial increase in training time. Training and fine-tuning uses 8 V100 accelerators, the permutation search uses only one V100. (ILSVRC12)
Baseline (Dense)
Default 2:4
Permuted (ours)
Search Time
Network
Topl
Top5
Toopl
ATopS
ATopl
AoopS
Train+FT
MobileNet v2
71.55
90.28
-1.98
-1.13
0.01
0.02
00:50
0.02%
MobileNet v3 (Small)
67.67
87.40
-2733
-1.67
0.10
0.15
00:32
0.01%
MobileNet (Large)
74.04
91.34
-0.91
-0.40
0.10
0.04
00:58
0.01%
SqueezeNet v1.0
58.09
80.42
-4.01
-2.66
0.60
0.54
00:12
0.02%
SqueezeNet v1.1
58.21
80.62
-1.25
-0.93
0.03
0.05
00:12
0.02%
MNASNet
31
73.24
91.36
-0.58
0.02
01:10
0.04%
ShuffleNet v2
20
68.32
88.36
-1.35
-0.87
0.10
0.01
00:14
0.01%
EfficientNet B0
32
77.25
93.59
-1.27
-0.52
0.04
0.07
01:34
0.04%
ResNet-50 [8]
76.16
92.88
0.05
0.13
0.13
0.26
02:13
0.10%
ResNeXt-50 [36
77.62
93.70
0.01
0.05
0.13
0.07
02:57
0.08%
DenseNet-16 161 10
77.14
93.56
0.82
0.41
0.92
0.52
00:56
0.02%
Table 3: Runtimes for various strategies searching for good permutations for various input sizes show that our improved search algorithm completes quickly for even large matrices (default settings emphasized). Results captured single V100 accelerator.
Cols
32
64
128
256
2048
Strategy
Rows
32
64
64
128
128
256
256
512
2048
OSG(2)
0.00
0.00
0.01
0.01
0.02
0.03
0.17
0.23
29.99
OS((2)BB((10)
0.07
0.09
0.11
0.13
0.21
0.27
0.57
0.75
59.85
(100)))
0.71
0.83
0.99
1.26
1.87
2.49
4.65
6.07
332.93
OSG(3)
0.12
0.20
0.37
0.84
8.76
22.60
129.83
348.19
OSG(3),BR(10))
3,26
5.92
8.29
14.59
68.35
135.76
628.45
1191.39
OSG())
32.47
58.26
76.37
139.35
580.23
1095.28
4666689
9455.46
efficacies of 22.098% and 29.145% it shows that is important to escape these local minima in order recover as much accuracy as possible. Weighted average efficacies for our suggested setting of OSG (2) BR (100) are 22.472% and 29.394%. (Appendix F has more details.)
Search Time While the apparent complexity of the improvements over the baseline algorithm may seem to make the technique too expensive to use in practice, an efficient implementation can reduce the time required to perform the search for good permutation
insignificant fraction of the time required to train the model, as shown in Table 2 The total training and fine-tuning time is never increased by more than one tenth of percent in our networks. There are likely opportunities to improve the performance further, but the results on random matrices of various sizes in Table 3 show that the proposed settings (OSG(2) BB (100)) are fast enough for even large weight matrices.
Unstructured to structured sparsity. Unstructured pruning is commonly used to reduce model complexity. However, aggressive sparsity is required out-perform dense matrix and vector instruc- tions, so the achieved performance from unstructured sparsity is typically limited [1]]. Using channel permutations,
transform unstructured sparse layers into layers that conform 2:4 structured sparsity so that they can take advantage of sparse matrix instructions above, it is clear that we can reduce the impact of enforcing the 2:4 constraint network to improve the fine-tuned accuracy, similar to prior work [11], but we can also transparently transform layers structured sparsity if the permutation allows the weight values remain as they are; if we make no extra zeros, then there is no fine-tuning necessary. To show the benefit of channel permutations for this purpose, we begin with a pre-trained ResNet-50 from torchvision By imposing different amounts of unstructured sparsity on this model's 's layers, we can generate plausible patterns of zeros; even if the resulting network the weights are in reasonable places. Then, search for permutations for each layer at each sparsity. permutation found that results in the same number of nonzero values before and after enforcing
(22) From our accuracy results already-sparse
very accurate due to the lack of fine-tune muninnn the zeros in
"nttss:/pyttocchoor//vssoooo wtwiiii///////mmlll.aammm 8/models.html

---

ResNet-50: Unstructured to 2:4 Sparse
#Layers Transformed
None
Channel Swap
OSG(2)
OSG(2), BR(100)
0SG(2), BR(1000)
20
06G(3)
80
90
100
Unstructured Sparsity (%)
Figure 4: Permutations increase the number of unstructured sparse layers that can accommodate the 2:4 constraint without making extra zeros. Using deeper greedy searches (optimizing stripe groups instead of simply swapping channels) and escaping from local minima with bounded regressions further increase the number successfully-rranffornee layers.
the 2:4 constraint, then the layer can be transparently transformed. For each of six permutation search strategies, Figure shows how many layers can be transparently transformed when each layer is pruned to different sparsities. Permutations allow more layers at each sparsity to be transparently transformed, and better permutations can further increase this transparently transformable layer count.
Conclusion
We propose the use of weight matrix permutations to reduce the impact of pruning with N:M structured sparsity, adapting prior work [14] to this new type of sparsity. Modifying the resulting greedy algorithm to use deeper searches by exhaustively optimizing groups of stripes and allowing bounded regressions help the search escape local minima. Our permutation quality metric, efficacy, shows strong correlation with network accuracy improvements, and we show that small, parameter- efficient networks can use the existing fine-tuning workflow to recover accuracy after undergoing channel permutations. By limiting permutations the inner dimension of network's 's matrix operations, this technique requires only an offline step with no overhead when the model is deployed.
Limitations. While our results suggest that there may be general workflow to recover accuracy that does not require as much overhead as the original dense training, we do not have evidence for such a workflow. Similarly, our heuristic of increasing weight magnitude empirically results in improved network accuracy, this may not hold in general; other heuristics may perform better.
Potential societal impact. Our technique aims to improve the accuracy of neural networks that require reduced resources train and deploy. We do this by changing the order of weights along the channel dimension; similar effect comes from using different random seed to initialize the network, so societal impacts related our technique are not readily apparent.
Future work. We see three areas for further study. First, permutations may reduce the number of fine-tuning samples required to recover the accuracy lost by pruning for networks that already succeed in maintaining accuracy. Second, there has been recent work in exploring how to train with N:M sparsity from scratch [37]. It may be possible include permutations as part of this process by performing the greedy iterative process over time, amortizing the convergence of the permutation search over the convergence of the network. Also, accelerate the data gradient calculation phase of the backwards pass, N:M sparsity in weights must be transposable: the N:M constraint must be satisfied on both rows and columns of the weight matrix. In this case, permuting rows may help reduce the impact of these transposable constraints at the cost of runtime overhead to permute activations between layers. Finally, we observed significant efficacy improvements when the depth of the searches was increased by optimizing more groups of stripes but quickly became limited by processing time. This time could be reduced by parallelizing the search over more processing resources or finding more efficient implementation, perhaps by adapting Lehmer codes [17] to generate unique permutations on the processor where they will be tested. Formulating the problem for combinatorial solver may also allow better solutions to be found.
10

---

Funding Disclosure
This work was supported by Shanghai Municipal Science and Technology Major Project (No 101222201222 the Shanghai Engineering Research Center of AI & Robotics, Fudan University, China; and the Engineering Research Center of AT & Robotics, Ministry of Education, China.
References
[1] Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural
networks. J. Emerg. Technol. Comput. Syst. 13(3), Feh, 2017.
[2] Xizi Chen, Jingyang Zhu, Jingbo Jiang, and Chi-Ying Tsui. Tight compression: Compressing cnn model
tightly through unstructured pruning and simulated annealing based permutation. In 2020 57th ACM/IEEE
Design Automation Conference (DAC), pages 1-6, 2020.
[3] Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and
Evan Shelhamer. CuDNN: Efficient primitives for deep learning, 2014.
[4] Sara Elkerdawy. Mostafa Elhoushi, Abhineet Singh, Hong Zhang. and Nilanjan Ray. To filter prune, or to layer prune, that is the question. In Proceedings of the Asian Conference Computer Vision (ACCV), November 2020.
[5] Scott Gray. Alec Radford, and Diederik P. Kingma. GPU Kernels for Block-Sparse Weights, Accessed April 13, 2021. /tttps://openai cww hoom/bloo/bloce sparse- spu-kernels/
[6] Song Han, Jeff Pool, John Tra, Wilham Dally. Learning both weights and connections for efficient neural networks.
Proceedings of the 28th International Conference on Neural Information Processing
Systems, pages 135-1 143, 2015.
[7] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. [8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR), June 2016. [9] Andrew Howard, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, Yukun 7hu, Ruoming Pang, Hartwig Adam, and Quoc Le. Searching for mobilenetv3. In 2019 IEFF/CVF International Conference on Computer Vision (ICCV), pages 1314-1324, 2019.
[10] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR). pages 2261-2269, 2017.
[11] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Seffi Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find N:M transposable masks, 2021.
[12] Forrest N. landola, Matthew W. Moskewicz. Khalid Ashraf, Song Han, William J. Dally, and Kurt Keutzer. Squeezenet: Alexnet-level accuracy with 50x fewer parameters and <lmb model size. CoRR. /ss/1602.0760.. 2016.
[13] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei, editors, Proceedingy of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448 456, Lille, France, 07 09 Jul 2015, PMLR.
[14] Yu Ji, Ling Liang, Lei Deng, Youyang Zhang, Youhui Zhang, and Yuan Xie. Tetris: Tile-matching the tremendous irregular sparsity. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Ccsa-Bianchi, and R. Garnttt, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates.
Inc., 2018
[15] Eugene Lee and Chen-Yr Yi Lee. Neuralscale: Efficient scaling of neurons for essourc--oonstrannc deep neural networks. Proceedings of the IEEE International Conference on Computer Vision, pages
1478-1487, 2020.
[16] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: single-shot network pruning based on connection sensitivity. In ICLR, 2019.
[17] D. H. Lehmer. Teaching combinatorial tricks to computer. In R. Bellman and M. Hall Jr., editors, Proc. Symp. App. Math. Combinatorial Analysis, volume 10, pages 179-193. American Mathematical Suciety, 1960.
[18] Yawei Li, Shuhang Gu, Christoph Mayer, Luc Van Gool, and Radu Timofte. Group sparsity: The hinge between filter pruning and decomposition for network compression. In Proceedings of the IEEE International Conference on Computer Vision, 2020.
[19] Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang. Kwang-Tine Cheng, and Jian Sun. Metapruning: Meta learning for automatic neural network channel pruning. Proceedings of the IEEE International Conference on Computer Vision, pages 3296-3305, 2019.
[20] Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. Shufflenet v2: Practical guidelines for efficient can architecture design. In Proceedings of the European Conference on Computer Vision (ECCV), September 2018
[21] Huizi Mao, Song Han, Jeff Pool, Wenshuo Li, Xingyu Liu, Yu Wang, and William J. Dally. Exploring the granularity of sparsity in convolutional neural networks. In Proceedings of the IEEE Conference on
11

---

Computer Vision and Puttern Recognition (CVPR) Workshops. July 2017.
[22] Asit K. Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong
Yu, and Paulius Micikevicius, Accelerating sparse deep neural networks. CoRR, abs/2104.08378 2021. Pavlo Molchanov, Arun Mallya, Stephen Tyree, Juri Frosio, and Jan Kautz. Importance estimation for
[23]
neural network pruning. In CVPR, 2019.
[24]
NVIDIA. NVIDIA Tesla V100 GPU architecture.
httts://image: httpe://maage..vidia.coom
NVIDIA. Automatic SParsity wrw.taaaarrccittteeeeeeteeeeeeee
colta-arrhiteccuureppttco
pdf 2017
[25]
contrib/ contrib/sparsity 2020.
[26]
NVIDIAA NVIDIA 1100 tensor core GPU architecture.
http:://wwww.iiddaaaacmomottteee dam/
un-2z/Solutions aaaautiiiinnttaattttteeee Data- -tt---eeeeeeeecatetet---e-------
pdf, 2020.
[27]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan. Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, perforrefrmmnce deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlchBuc, E. Fox, and R. Garnett, editors,A Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[28] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations. 2020.
[29]
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Scan Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstcin, Alexander C. Berg, and Li Fei-Fei. ImageNct Large
Scale Visual Recognition Challenge. IJCV, 115(3):211 1-222,, 2015.
[30] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chich Chich Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
[31] Mingxing Tan, Bo Chen, Ruoming Pang. Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V.
Le. Mnasnet: Platform- aware neural architecture search for mobile. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). June 2019.
[32] Mingxing Tan and Quoe Lc. EfficientNet: Rethinking model scaling for convolutional neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 6105-61 14. PMLR, 09-15 Jun 2019.
[33] Huan Wang, Qiming Zhang, Yuehai Wang, and Haoji Hu. Structured pruning for efficient convnets via incremental regularization. CoRR, ahs/1811 1.083990 2018.
[34] Wei Wen. Chunpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Learning structured sparsity in deep
neural networks. Proceedings of the 30th International Conference on Neural Information Prucessing Red Hook, NY, USA, 2016. Curran Associates Inc.
Systems, NIPS'16, 16, page
[35] Hao Wu, Patrick Judd, Xiaojie Zhang, Mikhail Isaev, and Paulius Micikevicius. Integer quantization for deep learning inference: Principles and empirical evaluation. CoRR, ahs/20004 009602, 2020.
[36] Saining Xie, Ross Girshick. Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transforma- tions for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern
recognition, pages 1492-1500, 2017.
[37] Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li. Learning N:M graiind structured sparse neural networks from scratch. In International Conference on Learning Representations, 2021.
[38] Michael 7hu Suyog Gupta. To prune, compression. ICLR Workshops, 2018.
prune: Exploring the efficacy of pruning for model
12


Reviews:
[{"review_id": "WH_Bo2e7Rnh", "reviewer": "Reviewer_GQXR", "summary": "Recent nVidia chips support hardware acceleration of structured sparsity patterns in weight matrices — specifically 2:4 sparsity where consecutive groupings of 4 entries have half of their entries set to zero.  The naive way to exploit this acceleration in deep learning is to prune weight matrices so as to meet this sparsity requirement, but doing this naively can be suboptimal if some groups contain many “important” weights and other groups contain all zeros already — it would be better if the “important” weights had a better distribution across groups.  So this paper proposes a way to permute the weights such that the pruning yields less loss.\n\nThe main idea is that if we can permute the weight rows/cols appropriately, then we can force pruning to give something that has more weight magnitude. The authors introduce permutation efficacy (and show on Imagenet experiments that this makes sense and acts as a kind of proxy for quality) and present a (mostly) greedy algorithm for optimizing this measure.  Final experiments on a number of Imagenet trained architectures show accuracy improvements over the naive method.\n", "questions": "", "limitations": "", "rating": 7, "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": "There are several strong points in favor of this proposed method.  First, it does not change running time for inference — (so the benefits are free in some sense) and does not require retraining or fine tuning.  The proposed method is also fairly intuitive (seems natural).  And finally it yields positive results in terms of accuracy — and according to the experiments seems generally applicable across a range of networks.\n\nThe weaknesses of this paper is that there is limited upside (the improvements seem to be quite small on average). There is also no discussion of running time of the optimization (I agree this time can be amortized away, but I believe it should be discussed). Finally, exposition needs improvement — I found a number of statements to lack in mathematical rigor (more details below) and some of the figures to be confusing which increased the cognitive burden of reading this paper.\n\nOverall, though I find the paper to be somewhat incremental - I believe it’s worth sharing this with the community so I lean towards acceptance.\n\n\nMore detailed comments:\n* It’s presented starting from the beginning as if it is obvious that preserving weight magnitude corresponds to good final accuracy, but this is not actually obvious (and I believe the authors recognize this in the experiments). It would be good to have a more transparent discussion about this issue at the top of the paper.\n* The proposed method ignores the fact that the output channels can also be swapped and intuitively, optimizing jointing for swapping both the rows and columns of a matrix, one could achieve even greater efficacy — I wonder if it would be worth commenting on this possibility somewhere (or tell me that I’m wrong).\n* Several times, the authors mention “applying the 2:4 constraint” without explicitly spelling out what this means exactly — does this just mean, dropping the lowest magnitude 2 weights in each group of 4 consecutive entries?  Or is there something fancier happening here?\n* The Figure 2 example is very confusing to read — I would recommend that the caption identify the colors, label what every arrow represents and explain the permutation notation (e.g. does [1,0,2] mean that we permute row 0 to be first, row 1 to be 0th, etc?).\n* More on this point, permutations are never really defined and this causes problems throughout.  At some point for example, the authors say that “a permutation is unique if its stripes channels are in sorted order…” — but what are the stripes of a permutation (I think I can infer, but it would be best to not require the reader to have to)?  I recommend stating upfront, that each weight matrix is associated with a permutation, saying how the permutation is notated and what index spaces it maps between.\n* Table 1 ablation: given that efficacy is not clearly connected to final preserved accuracy, why not just report preserved accuracy here? Also I recommend reporting running times — it seems like the more exhaustive the search, the better optima the algorithm was able to find (which is not surprising). What if we were to compare against a random baseline where we just evaluate thousands of random unique permutations and take the best?\n* Figure 3: report original dense performance/accuracy?\n* Line 141: “to keep the network graph consistent” — don’t you mean to keep the parameterized function equivalent?\n* Final minor thing: this pdf file is 38 Mb which is huge given that there are no graphics in this pdf and I don’t know if a printed screenshot was submitted instead of an original pdf… but it’s also not possible to search the document which made reading hard if I had to do a search within the document for a particular term.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "S98y70YCTfk", "reviewer": "Reviewer_fH7G", "summary": "The paper focuses on fine-grained block sparsity setting (N:M sparse network) and in specific the case where a pre-trained model is given and one wishes to extract an N:M mask and retrain. The authors suggest using channel permutation to reduce the initial accuracy degradation and demonstrate a significant accuracy boost on parameter-efficient models using their method.  They suggest two greedy methods to find a good permutation. Additionally, the authors used their method to transform several layers from an unstructured sparse model to an N:M structure sparse layers. ", "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": "Pros:\n\n1) The main idea of the paper (channel permutation) is simple and seems to work. \n2) While the idea is not novel as it was suggested before [1] for a different type of pruning it was never used for N:M sparsity. \n3) The authors check their approach on several models.\n4) The authors demonstrate that given enough resources their algorithm can find the optimal permutation. \n\nCons:\n\n1) The paper is poorly written and hard to follow. There are many terms that were not defined or defined in the appendix without reference. For example, G in line 174 was defined only in the appendix and DGRAD in line 346 was not defined at all.\n2) While channel swapping is clearly a combinatorial problem it was never discussed or formulated (is this an NP-hard problem?). I believe that finding the right formulation would enable using open-source parallel packages for combinatorial problems.\n3) No code!  paper with no code has a much lower impact as other researchers would probably avoid using or extending it.\n\nQuestions:\n\n1) While table 2 demonstrates that OSG is much better than channel swapping, and figure 3 demonstrates that weight average efficacy correlates with accuracy improvement. The authors did not present results with simple channel swapping. Thus, it is not clear why the OSG overhead is required. \n2) OSG is clearly not a very light technique, can you comment on the amount of time it takes to find the best permutation (with OSG(3)-BR-1000, OSG(2) BR-1000, channel swap). \n3) Have you tried to fix the bias as suggested by [2] perhaps it should help with “unstructured to structure”  experiments as suggested by [2]. I also believe you should mention [2] in this paragraph. Finally, it might help for “fine-tuning” experiments with parameter efficient models (table 2) as well. \n\n[1] Ji et al., TETRIS: TilE-matching the TRemendous IrregularSparsity\n\n[2] Hubara et al., Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the potential social impact but did not address the limitation of their study. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}, {"review_id": "ATDR-T8rYLS", "reviewer": "Reviewer_rysJ", "summary": "This paper introduces a channel permutation method to maintain the important connections. the idea is very interesting and meaningful. ", "questions": "", "limitations": "", "rating": 7, "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": "Strong points:\n\nThis paper emphasizes the drawback of N:M sparsity when each group only has M elements.   \n\nTo handle the local minima solutions, this paper proposes the bounded regression method, which is simple yet effective, to escape local permutation.\n\nThe channel permutation method does not incur inference cost and can handle the complex structure of DNNs, These points are important for sparse neural networks. \n\nthe experimental on ImageNet1K support the claims with various CNN-based models. This paper is a good practical work to facilitate the deployment of N:M sparse model.\n\n\nWeak points\n\nThe experiments only consider the classification.\n\n\nOverall, I am inclined to clear accept this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Weak points\n\nthe experiments only consider the classification.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "5IDvtzoTvyo", "reviewer": "Reviewer_32Qz", "summary": "In this paper, the authors proposes channel permutation to improve the accuracy of N:M sparsified networks. Compared with previous works on N:M sparsity, channel permutation could maximize the magnitude of the weight matrix after N:M sparsification. Thus, the accuracy of the sparsified network could be preserved. To find the optimal permutation, a greedy searching algorithm is proposed, which is enhanced by two local minima escaping techniques including \"bounded regressions\" and \"narrow, deep search\". The effectiveness of the proposed channel permutation and local minima escaping methods are validated by experiments on a sufficient number of network architectures. ", "questions": "", "limitations": "", "rating": 8, "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": "Pros:\n1. The idea of channel permutation for N:M sparsity is quite novel. \n2. The problem of finding the optimal channel permutation is well addressed by the greedy search and the local minima escaping technique.\n3. The experimental results validates the benefits brought by the proposed method.\n\nCons:\n1. Some of the details in the paper is not well described. \n    Line 160: It is very clearly how the term $W_{50\\%\\_rows}$ is defined. Is the 50% sparisty constraint applied to each row of the matrix independently?\n2. Missing references to recent work on network pruning.\n[1] https://arxiv.org/abs/1903.10258\n[2] https://arxiv.org/abs/2003.08935\n[3] https://arxiv.org/abs/2006.12813\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addresses this problem properly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper suggests an interesting permutation based method which closes the (sometimes small, but significant) performance gap in 2:4 fine-grained sparsity. The reviewers were all positive, and it seems most of their clarity-related concerns were addressed in the authors' response and the following discussion. I ask the authors to address all these issues in the camera-ready version to improve the readability of the paper and publish the code, as promised.
Decision: Accept (Poster)