Encoding Weights of Irregular Sparsity for Fixed-to-Fixed Model Compression
Authors: Bae Seong Park
Se Jung Kwon
Daehwan Oh
Byeongwook Kim
Dongsoo Lee
Venue: ICLR 2022 Poster (2022)
Keywords: Sparse Neural Network
Fixed-to-fixed data compression
Unstructured Pruning

Abstract: Even though fine-grained pruning techniques achieve a high compression ratio, conventional sparsity representations (such as CSR) associated with irregular sparsity degrade parallelism significantly. Practical pruning methods, thus, usually lower pruning rates (by structured pruning) to improve parallelism. In this paper, we study fixed-to-fixed (lossless) encoding architecture/algorithm to support fine-grained pruning methods such that sparse neural networks can be stored in a highly regular structure. We first estimate the maximum compression ratio of encoding-based compression using entropy. Then, as an effort to push the compression ratio to the theoretical maximum (by entropy), we propose a sequential fixed-to-fixed encoding scheme. We demonstrate that our proposed compression scheme achieves almost the maximum compression ratio for the Transformer and ResNet-50 pruned by various fine-grained pruning methods.

Published as a conference paper at ICLR 2022
ENCODING WEIGHTS OF IRREGULAR SPARSITY FOR FIXED-TO-FIXED MODEL COMPRESSION
Baeseong Park's Se Jung Kwon', Daehwan Oh?, Byeongwook Kim', Dongsoo Lee' NAVER CLOVA,
!baesung. paassngggaar,, se jung. kwon, byeonguk kim, dongsoo.. lee @navezcorp. *Samunn Research, dhdh. ohê samsung.. com
ABSTRACT
Even though fine-grained pruning techniques achieve high compression ratio, conventional sparsity representations (such as CSR) associated with irregular sparsity degrade parallelism significantly. Practical pruning methods, thus, usually lower pruning rates (by structured pruning) to improve parallelism. In this paper, we study fixed-to-fixee fixeixed (lossless) encoding architecture/algoritmm to support fine- grained pruning methods such that sparse neural networks can be stored in highly regular structure. We first estimate the maximum compression ratio of encoding- based compression using entropy. Then, an effort to push the compression ratio to the theoretical maximum (by entropy), we propose sequential fixed-to-fixed encoding scheme. We demonstrate that our proposed compression scheme achieves almost the maximum compression ratio for the Transformer and ResNet-50 pruned by various fine-gratd ane-gnained pruning methods.
INTRODUCTION
As one of the efficient compression methods, pruning reduces the number of parameters by replacing
model parameters of low importance with zeros (LeCun et al. 1990). Since magnitude-based pruning has shown that pruning can be conducted with low computational complexity (Han et al. (013)). various practical pruning methods have been studied achieve higher compression ratio (Zhu and Gupta 2017 Molchanov et al., 2017 Louizos et al. 2018 Gale et al. 2019). Recently, pruning has been extended a deeper understanding of weight initialization. Based on the Lottery Winning Ticker hypothesis (Frankle and Carbin 2018). (Renda et al. (2020) suggests weight reight-rewinding method to explore sub-networks from full trained models. Furthermore, pruning methods at initialization steps without pre-trained models have also been proposed (Lee et al. 2019b Wang et al. 2020).
Despite a high compression ratio, fine-grained pruning that eliminates each parameter individually has practical issues to be employed in parallel computing platforms. One of the popular formats to represent sparse matrices after pruning is the Compressed Sparse Row (CSR) whose structures are irregular. For parallel computing, such irregular formats degrade inference performance that dominated by matrix multiplications (Gale et al., 2020). Algorithm presents a conventional sparse vector multiplication (SpMV) algorithm using CSR format which involves irregular and data-dependent memory accesses. Correspondingly, performance gain using a sparse matrix multiplication (based CSR) is lot smaller than the compression ratio of pruning YYu al. 2017). Structured pruning methods (e.g, block-based pruning (Narang et al.) 2017]] Zhou et al. 2021 filter-based pruning (Li et al. 2017), and channel-based pruning (He al. 2017 Liu et al. 2017) have been suggested to enhance parallelism by restricting the locations of pruned weights Those methods, however, induce degraded accuracy and/or lower pruning rate than fine- -nn-iiai pruning.
In this paper, as an efficient method to compress sparse NNs pruned by line-grained pruning, we consider weight encoding techniques. As shown Algorithm encoded weights are multiplied by a fixed binary matrix R to reconstruct the original weights. We propose an encoding method and M design methodology compress sparse weights regular format. It should be noted that sparse matrix multiplication can be even slower than dense matrix multiplication unless pruning rate high enough (Yu et 2017
Gale et al. 2020 that does not happen with Algorithm
"quual contribution.

---

Published as a conference paper at ICLR 2022
Avorago of umpprnod weights
Variance
Mexigum A of ungroned weights
Fired-to-fized sparsity
Read#1
Read12
Bandwichh
Fiaod variill--allll sparsity formal (ex, CSR)
Bandwidtt
Read#4
ReadK3
ReadR5
ReadeG
Dense (Fuedd)
80% Pruned (Low Var.)
90% Fruned (High Virr)
90%
(Fired, Ours)
Denze
50% Pruned
0.
0.9
Sparsity (inn grn-ngraeedd pruning)
90% Pruned
Pruned
(a) Memory Bandwidth
(Fiedd, Ours)
(b) Memory Access Patterns
Figure Comparison between exee-to-vvrrable (e.g., CSR) sparsity format and fixed-to-fixx (proposed) sparsity format. (a): Memory bandwidth comparison. (b): Memory access patterns with irregular sparsity.
for memory-inten inttesivv workloads. We study the maximum compression ratio of such encoding- based compression using entropy and propose sequential fixed-to- -iee-to-fixed scheme that keeps high parallelism after fine-grained pruning. We show that by our proposed fixed-to-fixed scheme, a compression ratio can approach the maximum (estimated by entropy) even under the variation of the unpruned weights in block.
Algorithm 1: SpMV (CSR format)
Algorithm 2:
Proposed SpMV (using encoded weights)
In: Dense vector æ, CSR vectors dat. row, col Out: Dense vector y for to do for f row, row do y: - y: + dat x x [[]o
In: Dense vector æc R" Encoded vectors ER.
Fixed matrix M E {0, 1
Mask (k*m)
Out: Dense vector y do
for
W; <- wi x M over GF(2)
y/ W. - a with Mask (for zero skipping)
M Irregular, data-dependent access*/
1 Decoding m elements using wf (Regular access)*/
2 FIXED-TO-FIXED SPARSITY ENCODING
Data compression is a process of encoding original data into smaller size. If fixed number of original bits are encoded into fixed number of (smaller) bits, such a case categorized into a "fixed-to-fixed" compression scheme. Similarly, "fixed-to-variable" "variable-to-fixe"" and "variable- torvariable" categories are available while variable lengths of original and/or encoded bits allow higher compression ratio than fixed ones (e.g., Huffman codes (Huffman 1952) as
scheme, Lempel-Ziv (LZ))-baee coding (Ziv and Lempel| (006) as variable-to-fie scheme, and Golomb codes (Golomb) 1966) variable-to-variable scheme).
Among those 4 categories, "fixed-to-fieed" compression is the best for NNs that rely on parallel computing systems. Fixed-to-fixed compression schemes are, however, challenging when fine-grained pruning is employed in NNs because the number of unpruned weights in a fixed-size block varies. Accordingly, most previous sparsity representations (such as CSR format) translate a fixed-size weight block into a variable-size block while such translation would demand non unn-unfoomm memory accesses that lead to significantly degraded memory bandwidth utilization as shown in Figure []]
Specifically, in the case of ixveito-variable sparsity format (c.g., CSR) in Figure J we observe that memory bandwidth is low because fine-grat -nniiidd pruning induces a variable number of pruned weights for certain block or row while memory is designed to access fixed amount of consecutive data. Since higher sparsity leads to higher relative standard deviation (i.e., coefficient of variation) on pruned weights in a block, low memory bandwidth is significant issue even though the amount of data to be stored is reduced (see Appendix A). As a result, for fixed-to-varee variabee sparsity format, is difficult to implement fine- inn-inndeed pruning with parallel computing systems that require high memory bandwidth (Yu et al.) 2017). On the other hand, fixed to- fixed compression schemes in Figure I can maintain the same memory bandwidth regardless of sparsity.
2

---

Published as a conference paper at ICLR 2022
Unpraned
Pruned
Decoding fixed rate
X
X
X X
My
X
X
X
X
X
R,=5
X
X
X
RG=5
X
X
X
X
X
m4=33
of encoded weights 4a5
Encoding fixed-length codes
18[n.]
Figure 2: Fixed-to-fixed compression of a sparse weight matrix. Even when a block involves a varying number of unpruned weights, the size of each encoded block is fixed and determined by an average number of unpruned weights in blocks.
Random Number
Weight to be encoded
Generator
X0X1
0X0X
XOR-gates
0000
Unmatched
Matched
XOR-gates
1110
Unmatched
Unmatched
XOR-gates
0101
Unmatched
Matched
11 XOR-gates
1001
Matched
Unmatched
Figure Encoding of weights using XOR-gate decoder as a random number generator.
In this work, we propose "fixed-to-fixed" compression scheme as shown in Figure 2 when the number of pruned weights in block can vary. A successful fixed-to-fixed compression of sparse NNs should consider the followings:
(High compression ratio) The maximum compression ratio is limited by the minimum entropy (that can be obtained by fixed-to-variable scheme as we discuss in Appendix D). Suppose that block be encoded contains (fixed) n& bits among which (fixed) n, bits are unpruned. A sedd-to-fixed encoding scheme is required to support high compression close to (na/n.) (estimated by entropy). Fixed-to-fixed decoding, then, accepts (fixed) N., bits as an input and produces Nout bits as output while N Nout/No /N... ng/n..
(Variation tolerance) For fine-grained pruning, Th is given as random variable whose distribution is affected by pruning rate, ni size, a particular pruning method, and on. Our goal is to maintain fixed-to-fixed scheme with a high compression ratio even under [ar[n.] # O. In Figure 2 for example, blocks of original data have various nu values while the size of an encoded block is fixed to be 4 (=E(m..)). We will discuss how to design a variation tolerant encoding.
RANDOM NUMBER GENERATOR
Before discuss compression schemes, let us assume that binary masking matrix given to represent which weights are pruned or not (note such binary masking matrix can be compressed significantly (Lee al. 2019a)). Then, a pruned weight can be described as don't care value (X) that is to be masked. We also assume that 1) pruning each weight is performed independently with pruning rate S and 2) unpruned weight assigned to 0 or 1 with equal probability (such assumptions are not necessary when we demonstrate our experimental results in Section 5).
To obtain both "high compression ratio" and "variation tolerance" while a fixed-to- oo-fixed compression scheme is considered, we adopt random number generator schemes that enable encoding/decoding of weights. A random number generator accepts fixed number of inputs and produces nı, bits so to implement fixed-to-fieed compression scheme. As shown in Figure 3 weight block is compared with every output of a random number generator. there is an output vector matching original (partially masked) weights, then corresponding input vector of a random number generator can an encoded input vector. As an effort to increase the Hamming distance between any two outputs (i.e., the number of bit positions in which two bits are different), 2nd outputs out of 2n
3

---

Published as a conference paper at ICLR 2022
13.58
06.24
58.40
96.52
57.67
86.81
08:07
57-10
50:07
11-3.00)
(1R:31)
94.99 09
90.00
00.34
96.67
15,100
94.12
50.72
53.00
98.48
10.32
03.75
98.19
50.00
92.01
52.39
[-2 060
18: 115
114 56)
184 80)
(-0..1)
(4:103)
[30
181.211
(41 10g
[=0100)
(4:
[= (33)
(81 101
(:0 (0)
75
06.74
97.08
98.72
M8-72
05.88
06.78
85.01
25.43
10.36
05.50
05.23
94.50
96.71
15
[20 330
97.03
(21121
87.55
1231.1)
97.63
(501200
97-55
(200.2)
87.57
16
(231.22)
96.82
12: 22)
00.71
(20.23)
90.66
151.10
96.52
1=9.30
96.41
16
(20.30)
M6.03
(23120)
36.18
[2
60.09
(20.12
55,73
(201 16)
65.36
68.00 05
184.00
98.19
18.05
00.03
97:41
07.38
07:33
07.12
07.00
07.08
96.78
W1.32
06.40
96.35
075
07.5
0.9
18.5
0.6
0.7
0.5
005
0166
0.7
(a) Ru (=a number of unpruned (b) Mu follows binomial distribu-
(c) nu is empirically obtained by pruning the first decoder layer of the Transformer using a magnitude- based pruning method.
weights in block) is fixed to be tion B(Nout, 1 1-11 S).. Non (i.c,, Var =0)=
Figure 4: Encoding efficiency (%) of random XOR-gate decoders. S is pruning rate and Nout is given as [Ni. (1/(1-)))J
possible candidates need to be randomly selected. Note that random encoding has already been suggested by Claude Shannon to introduce channel capacity that is the fundamental theory in digital communication MMreeos-Zaraggzz 2006). Since then, practical error correction coding techniques have been proposed to implement random- -iike coding by taking into account efficient decoding (instead of using a large look-up table).
Similar to error correction coding that usually depends on linear operations over Galois Field with two elements, or GF(() (Morelos- Zaragozz 2006), for simple encoding of original data, recently, two compression techniques for sparse NNs have been proposed. An XOR-gate decoder produces (a large number of) binary outputs using (a relatively much smaller number of) binary inputs while outputs are quantized weights (won et al. 2020). Another example is adopt a Viterbi encoding/decoding scheme (Forney) 1973) to generate multiple bits using a single bit as an input (Ahn et al.) 2019). For a block that cannot be encoded into compressed one by a random number generator, we can attach patch data to fix unmatched bits (Kwon et al.) 2020) or re- re-train the model to improve the accuracy (Ahn et al. 2019).
To compare the random number generation capability of various block-leve compression schemes, we introduce 'encoding efficiency' given as a percentage.
E' (Encoding Efficiency) of correctly matched bits # of unpruned bits
100(%)
Let S be pruning rate (0 < S < 1). To mcasure encoding efficiency (E), we assume that the compression ratio of a random number generator (=the number of output bits the number of input bits) is 1/(1 5). We generate numerous randomly pruned (binary) weight blocks, and for each block, we investigate all of the possible outputs that a random number generator can produce. If there is block missing a matching output of generator, then the maximum number of correctly matched bits is recorded for each block. We repeat such an experiment for all of the blocks. Note that E cannot be higher than 100% for any generators.
3.1 FIXED PRUNING RATE IN A BLOCK
For simplicity, we assume that n. in a block fixed number. Let us study E when ny is fixed using XOR-gate decoder introduced in (K et al. 2020). For an XOR-gate decoder, when N Nout the number of output bits and N., the number of input bits, a matrix M E [0, 1) Nous N presents connectivity information between an input vector w {0, 1) and output vector (E {0, 1] Nowt)) such that we have w = M @ == over G2 For example, if the second row of R (with No. and Nout = 8) is given a binary XOR operation or an addition over GF (2) equivalently). An element of M 9 is randomly filled with 0 or I as simple random number generator design technique (Kwon al. 2020).
11011 1]. then w w ① w @ w ('@' indicates
To measure E, let N z 1 1-5 S such that Nout = [N... (1)(1-))) Correspondingly, for certain S, block size (=Nout) increases as Nrn increases. When nig Naut and n., N...
4

---

Published as a conference paper at ICLR 2022
Figure 4a describes statistics of E when random M matrices associated with random blocks. From Figure 4u it is clear that increasing No. is the key to improving encoding efficiency. Note that, however, increasing Nan and Nout complicates the decoding complexity (due to large M) and the encoding complexity as well (due to an exponentially large search space).
3.2
VARIABLE PRUNING RATE IN A BLOCK
Now we allow nu in a block to fluctuate. For Figure 4b we assume that pruning each weight Bernoulli event (with S probability) such that nl block follows binomial distribution (NNott S-S) (thus, E[n.,] = No-e(1-5 and Var[nw] 51 Ni, is given as [n in Figure 4b) Compared Figure 44| É becomes lower mainly because some blocks would have nu larger than Nin (i.e., too many unpruned weight bits that a random number generator cannot target).
Note that the coefficient of variation of Nu. Ct/Varmnl//BBa.a.
de- creases as Nout increases. Indeed, the gap be- tween E. in Figure 4a E. in Figure/4b)r tends
N The
R2 2
Nauc 1/'
The
X
X
X
X
21%
X
X
Encoding
be slightly reduced when Nan (as well cor- responding Nout) increases. To illustrate, as shown in Figure [ when there are two blocks of different uu concatenating two blocks into a block (thus, increasing Nout) can increase the probability of successful encoding due to effi- cient usage of Ni.. Increasing Nin and Nout by times, however, requires XOR-gate decoder
N..=3
Figure 5: Encoding of two blocks when a number of unpruned weights can vary in block.
to be larger by 2 times with only marginal gain in E.
Another way to improve E' under the variation on nhe is to decrease Nout and increase Nin- In this case, however, the compression ratio is reduced consequently. We need a solution to design fixed-to-fixed sparsity compression technique that can improve E of random number generator under the variation on ny without sacrificing compression ratio (i.e., Nan/Nout =-SS).
To validate our observations obtained by synthetic random data, we compute E of an XOR-gat decoder using the Transformer model (Vaswani et al. (017). The first fully-connected layer of the Transformer is pruned by magnitude- based pruning method (Han et al. 2015) with pruning rate Interestingly, E described in Figure 4clis similar to that of Figure 44b As such, our assumption that
pruning a weight is a Bernoulli event is valid for the context of magnitude-based pruning.
4 PROPOSED SEQUENTIAL ENCODING SCHEME
If Var[n..] is non-zero and Ni, is fixed, then blocks of small noy (< Nin) would have many possible input vectors with matching output vectors while other blocks with large ny (> Ni.)) may have no any single possible input vector. Such unbalance among encoding success rates over blocks can be mitigated if a part of input vectors associated with block of small n. can be reused for the neighboring blocks of large na. In other words, by sharing some parts of an input vector for multiple consecutive blocks (of diverse n. values), input search space size of each block can be balanced. Reusing inputs is fulfilled by shift registers that have been also introduced to convolutional codes such as Viterbi codes (Morelos-Zaragoza 2006). In this section, we propose sequential encoding techniques to address the limitations of previous fixed-to- seeddtt--ixed compression schemes (for example, MOR-gate-only decoder (Kwon et al. 2020) lacking tolerance for n, variation, and Viterbi encoders (Ahn et al. 2019) that receive only bit as input (i.e., Nr, is restricted to be 1).
Weight manipulation Since our encoding/decoding techniques process data in block-level (in the form of I-D vector), original sparse weight matrices (or tensors) need to reshaped through grouping. flattening, and slicing. Assuming that a number format has the precision of new bits (e.g.. =32 for FP32), as the first step of weight manipulation, a weight matrix W e R is grouped into n., binary matrices W Wi..... E 1) m (otherwise, nhe successive bits pruned or unpruned). Then, each binary matrix (or tensor) b is flattened be 1-D vector and each vector is sliced into w w..... blocks when I (=f mn. indicates the number of blocks in 1-D (flattened) vector.
5

---

Published as a conference paper at ICLR 2022
Example
Original
Weight
(p32)
W
Mask
Mask
W
Decoded Weight
W
Randomiy filldd through Encoding
1Aا0 1 10 Deоي
Decoding
sign
W
exponent
Wh, Wh,
fraction
32
Wi-2Wi-106 W
110 100
fof (XNNor) bits
Encoding
XOR-gate
w (Masked)
WiLl (1xN None) bits. 2
Network (M*)
Flattened and Sliced Vectors Encoding
w.;
w
Shift Register
Reuse
w
Wi Tu
Register
Decoder
w "
Computed Offline
During Inference
A Concalenation
Figure 6: Proposed fixed-to-fixed sequential encoding/decoding scheme. Weight encoding is per- formed offline, and thus, complex computation for encoding is allowed. Encoded weights are decoded during inference through -gte decoders that are best implemented by ASICs or FPGAs. Pruned weights are filled by random values during weight decoding.
Decoding with an input sequence For an XOR-gate decoder (as a non-sequential decoder) at time index f, an output vector w (E 1). 1 is a function of an input vector w6 (E {0, 1) such that wi is utilized only for one time index. In our proposed sequential encoding scheme, w is exploited for multiple time indices using shift registers. Specifically, we copy ws to shift register whose outputs are connected to the inputs of the next shift register. Let N₂ be the number of shift registers. In the proposed scheme, XOR-gate decoder receives inputs from N, shift registers as well as wf. Then, as shown in Figure 6 sequential decoder (consisting of an XOR-gate decoder and shift registers) produces w as a function of an input sequence of (wef, wi-1.-..) while such function can be described w. M (w. w. "...- ww- over GF(() where A B implies a concatenation of A and B and the sequence length is (N, + 1). Note that in Figure [6 an input vector w reused N₂ times and XOR-gate decoder accepts (N, + 1) -N bits yield Nout bits (hence, M {0, (NN.xx((N,++))N,,, (without increasing N,.) that improves E' as demonstrated in Figure
larger XOR-gate decoder 4 and 2) multiple paths from an input vector to multiple output vectors (of various n.,) resulting in balanced encoding. Note that our XOR-gate decoder (or effectively memory decompressor) is best implemented by ASICs or FPGAs where each XOR requires only 6 transistors (Rabaey et 2004
Increasing N, enables
Balanced encoding Figure/ 7 illustrates decoding process when N,=1, Na.=3, and Nou=88. Each weight vector to be encoded con- tains different number of unpruned weights. For wo at time index t (in Figure 7). less number of unpruned weights tends enlarge search space for wf. On the other hand for wht1 at time index (t + 1), large number of unprumed weights would highly restrict search space for wf. Correspondingly, compared to the case when wf is associated with only one v block (i.e., non-sequential encoding with N.=0), search space for wi can be balanced as more " blocks various nh, are correlated with wy. Note that Var[n..] of one block increases, ac- cording to the central limit theorem, N, required to be larger to maintain the balance encoding
w
x
x
O
Matched? we va. w
Matched?
Matched? we 2. 2
M Mf wof
1 w
0
w
Figure 7: Sequential decoding example when N,=1, =3.=3, and Nout=8. An input utilized for (Ng+1) time indices through shift registers.
capability of each wf. As demonstrate in the next section, under the variation on nus small non-zero N₂ can enhance E substantially while increasing Nr,, (and Nout while N,=0) improves E only marginally (as described in Figure

---

Published as a conference paper at ICLR 2022
Enccyptod Litts
50k
Fimont [
Eroon No=2j
100
N
N-=2
Memory Rostattioon (%)
300
upper bouid by S-0.9
Erart,,
Euerypte
30k
E (50)
20k
90
10k
0k
70
20
40
100
130
140
160
20
40
100
120
140
100
20
40
60
80
100
120
160
Nout
Noxt
Nout
Figure 8: Impact of N. with various Nout using 1M random bits, Nin 8, and S=0.9.
Encoding algorithm In the case of non-sequential encoding scheme, because of one-to-one correspondence between fi and w/ through M encoding can be performed independently for each block (c.g.. for given masked wf, we select one matching w out of all available w sets by decoder). Such block-wise encoding, however, is not applicable that needs to consider the whole sequence of wD blocks to find an input sequence fed into a decoder. Suppose that we find a particular output sequence matching blocks after exploring all feasible output sequences provided by a generator and the input sequence (wf, w2,,.. ...,, wf), the time-complexity of encoding would be O22-Nn..). Fortunately, sequential decoding operations shown in Figure 7 can be models as a hidden Markov model, where each state is represented by concatenating we. w wi-N, and there are 2. paths for the next state transitions (Viterbi 1998). Consequently, the time- and space- craplecomyyy can be reduced to be O (NN++1)) 1) by dynamic programming that computes the of our encoding algorithm, the reader is referred to Appendix E.
sequential encoding scheme
sequence in a hidden Markov model (Forney) 1973). For details
Lossless compression Any random number generators cannot produce outputs perfectly matching all unpruned weights (i.c., always less than 100%). To correct unmatched outputs of a random number generator (by flipping 0 ++ 1) in order to enable lossless compression, the locations of all unmatched weight bits need be recorded. Note that if E 1, the number of unmatched weight bits is a lot smaller than the number of encoded weight bits. If that is the case, such correction information can be stored in a separate on-chip memory that can be independently accessed without disturbing decoding operations. We propose format representing such correction information in Appendix where each ummatched weight bit requires Ne bits the correction format (N is around 10 in Appendix E). Taking into account compression ratio of generator given as Nout/N,, and additional correction information (using N₂ bits per one unmatched weight bit), a binary weight matrix W E {0, p can be compressed into ( (Nou mmmtNNeee bits when Nerr N, x (# of unmatched bits) = Namm(1 - (1 - E). Subsequently, memory reduction can be expressed as
Memory Save - (NNn/Nou mm + Nerr)/ (err)/(mm) (1 S) (1 No).),
when N is given as (1 S). Thus, memory reduction approaches S when E approaches 1. For the overall design complexity analysis of the proposed compression, refer Appendix G.
EXPERIMENTAL RESULTS
In this section, we demonstrate the encoding capability of our proposed sequential encoding tech- niques using synthetic random data and NNs pruned by various pruning methods. Even though various heuristic algorithms can be suggested, we adopt a simple dynamic programming technique for weight encoding that minimizes the number of unmatched weight bits. For our experiments, N is selected to be such that we feed a decoder on a byte-level.
5.1 SYNTHETIC RANDOM DATA -Ni.=8)
Setup We generate a random weight 1-D vector of IM bits. We also create a random masking data of 1M bits in which the percentage of zeros equals S. M matrix (formulating the structure of
7

---

Published as a conference paper at ICLR 2022
an XOR-gate decoder) basically needs be designed to maximize the randomness among outputs. Measuring randomness, however, is challenging and such measurement may not be highly correlated to E. Alternatively, we try numerous random M matrices and choose particular M of the highest E. Specifically, for a given set of Nin and Nout, element of M E Io ((N,+1)-NN.. randomly assigned to or I with equal probability. Then, of those random M @ matrices is estimated by using given random binary weight vectors and masking data. The best M providing the highest E (for a given set of Nin and Nout) is then utilized for our experiments.
Compression capability Figure g demonstrates the impact of N₂ on E and corresponding memory reduction($) (6) with various Nou and 1M random bits when = and $=0.9. Regardless of N.. as Nout increases (i.e., the compression ratio D.Nout/NN,, oott 88 of a decoder increases), the number of encoded bits is reduced while the number of unmatched (error) bits increases. Because of such trade-off between the number of encoded bits and the number of error bits, there exists certain Nout that maximizes the memory reduction. Note that compared to a non-sequential encoding (of =0). sequential encoding (even with small N₂) significantly reduces the number of error bits and maintains high F. (of almost 100%) until Nout reaches N₂. x (1/(1 )= Indeed, memory reduction becomes highest (=89332%) when N₂ is highest and Nout is 80 in Figure g As we discussed for lossless compression in Section 5, 89.32% of memory reduction is close to S(=90%) that is the maximum memory reduction obtained when E' 1. In the remainder of this paper, Nout is given as Nan x (1)()))) to maximize the memory reduction.
Impact of S on memory reduction Table D presents memory reduction using various S. For a certain S in Ta- [ as N₂ increases, the difference between S and memory reduction de- creases. In other words, regardless of S, sequential encoding/decoding principles are crucial for memory re- duction to approach S which is the maximum. Increasing also facili-
Table 1: Memory reduction (%) using 1M random bits and various N, and when N = 8 and Now.- Nin 1/(1- S).
S
60.0%
70.0%
80.0%
90.0%
N₂
38.6%
53.8%
67.9%
83.5%
55.9%
67.4%
77.5%
88.5%
58.4%
69.1% %
78.9%
89.3%
tates memory reduction to approach
in Table as described in Eq. 2 where increasing S with a constant E enhances memory reduction.
Inverting technique So far, we assumed that a bi- nary weight matrix holds equal amounts of zeros and ones. A few representations such bindry-coding- based quantization (Rastegari et al.
100
2016 Xu et al.
2018) and signed INT8 (Jacob et al.
2018) would in-
herently justify such an assumption. However, there exist exceptional representations as well (e.g.. FP32). We conduct experiments to find relationship be- tween the ratio of zeros and E using random weight vector as shown in Figure 9 E increases if a sub- stantial amount of zeros are employed as unpruned weight bits, because of a higher chance to find trivial inputs (of all zeros fed into XOR operations) to pro- duce zero outputs. Hence, to improve E (especially when N₂ is low), we propose an inverting technique where entire binary weight vector is inverted if the ratio of zeros is less than 50%.
N, =1
N,
96
0.0
0.2
0.4
0.6
0.8
1.0
Ratio of Zeros(S 0.7)
Figure 9: E with various ratio of zero in random vector.
5.2 SPARSE TRANSFORMER AND RESNET-50 (N,,.=)
We measure compression capability of our proposed sequential encoding scheme using sparse
Transformer (Vaswani al. 2017) on WMT' 14 en-de dataset and ResNet-50 (He et al. (2016) on ImageNet. Those two model in FP32 format are pruned by various methods including magnitude- based one (Han et al. 2015). LO regularization (Louizos et al. 2018 and random pruning (Gale et al.
8

---

Published as a conference paper at ICLR 2022
Table 2: E' and memory reduction of sparse Transformer and ResNet-50 pruned by two different
pruning methods. When N₂ is O or I, inverting can be applied to a layer if unpruned weights accommodate more zeros than ones. Inverting has no effect for weights of signed INT8.
E (%)
Memory Reduction (%)
(Max: 100%)
(Max: S)
Non-Seq.
Sequential
Non-Seq.
Sequential
Model
S(Method)
N,=O(Inv.)
NI=v(Inv.)
N,=2
N,=0(Inv.)
N,=1(Inv.)
N₂=2
70%g(Mag.)
93.8(94.5)
98.0(98.3)
98.7
50.3(52.4)
63.1(63.8)
65.3
Transformer
70%dd.
94.6(95.2)
99.2(99.3)
99.8
52.8(54.6)
66.6(66.8)
68.3
WMT14 en-de
(ag.
92.6(93.9)
97.6(97.9)
82.4(83.7)
87.4(87.7)
88.2
(FP32)
(Rndd.
93.7(94.5)
98.7(98.9) 9)
99.5
83.5(84.3)
88.5(88.7)
89.3
(Mag)
94.4(95.0)
98.6(98.7)
99.1
52.2(54.2)
64.7(65.3)
66.5
ResNet-50
(0%d..
94.6(95.1)
99.1(99.2)
99.7
52.7(54.2)
66.5(66.7)
68.3
ImageNet
MMg.
92.7(93.7)
97.3(97.6)
98.1
82.5(83.3)
87.1(87.4)
87.9
(FP32)
(Rand..
92.7(93.55
97.6(97.9)
98.7
82.5(83.3)
87.5(87.7)
88.6
ResNet-50
(Mag)
93.9(N/A)
98.5(N/A)
99.1
50.9(N/A)
64.5(N/A)
66.4
ImageNer
(0%d.)
96.2(N/A)
99.7(N/A)
99.9
57.6(N/A)
68.3(N/A)
69.0
(Signed
(M%.
92.4(NIA)
97.I(N/A)
98.0
82.2(N/A)
86.9(N/A)
87.8
INT8)
(Rand...)
93.5(N/A)
98.2(N/A)
99.2
83.3(N/A)
88.0(N/A)
89.0
Table 3: Coefficient of variation of nu and E of selected layers of the Transformer pruned by random, signitude-basedd or LO regularization pruning method.
Layer: dcc3/self att/qq (512 x 512), FP32
Layer: dcc3/fin2
Pruning Method
Target S
(2048 x 512), FP32
Caell. of
(%)
Caelf. of
E (%)
Var: (n,,)
N,=0
N,=1
N.=2
Var. (n.,)
N,=0
N,=1
N.=2
Random
0.299
94.6
99.2
0.303
94.6
99.2
Mag.
0.7
0.324
94.5
98.9
99.6
0,366
94.1
98.3
98.9
LO Reg.
0.347
94.5
99.0
99.6
0.331
94.3
98.7
99.2
2019) (also variational dropout (Molchanov et al.) 2017) in Appendix H). For the ResNer-50 model (on ImageNet), also consider signed INT8 format (Jacob al. 2018). Table preseenss E and memory reduction when every layer of the Transformer and ResNet-50 is pruned by the same pruning rate S. Both F and memory reduction to the case when inverting technique is applied to non-sequential encoding (N,=0), we observe that sequential encoding (N,>0) without inverting yields lot higher compression capability. Note that the compression capabilities of random pruning and magnitude-basee pruning methods are similar in Table such that our experiments with synthetic random data are justified. Such justification is also verified in Table 3 that is achieved by using two selected layers of the Transformer. Compared to random pruning, magnitude- based and LO regularization pruning methods exhibit somewhat lower E that is related to higher coefficients of variation of n.,. See Appendix H for additional results.
significantly improved by increasing N,. Even compared
All all, our proposed encoding method designed in the context of random pruning also effec- tive for other fine-grained pruning methods. Through various cases including synthetic data and benchmark models, we demonstrated the superiority of the proposed encoding scheme to previous fixed-to-fixed compression methods including non-sequential XOR-gate decoder of N,=0 (Koon) et al. 2020) and a Viterbi-based encoder structure where No, is limited to be 1 (Ahn et al. 2019).
CONCLUSION
In this paper, we proposed a sequential encoding scheme that is a useful fixed-to-fixed compression for sparse NNs. We studied the maximum compression ratio using entropy based on the strategy of mapping a weight block into a small number of symbols. We also investigated random number generators practical fixed-to-fixed fixed decoder using an XOR-gate decoder. Random number generators can improve compression capability if input vectors are reused for multiple time indices through shift registers.

---

Published as a conference paper at ICLR 2022
REFERENCES
D. Ahn, D. Lee, T. Kim, and J.-J. Kim. Double Viterbi: Weight encoding for high compression ratio and fast on-chip reconstruction for deep neural network. In International Conference Learming Representations (ICLR), 2019.
G. D. Fomey. The Viterbi algorithm. Proc. of the IEEE, 61:268 - 278, March 1973.
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks.
1803. 2018.
T. Gale, E. Elsen, and S. Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574. 2019.
Gale, M. Zaharia, C. Young, and Elsen. Sparse gpu kernels for deep learning. arXiv preprint arXiv:2006. 10901, 2020.
S. Golomb. Run-length encodings. IEEE Transactions on Information Theory, 12(3):399-401, 1966.
S. Han, J. Pool, J. Tran, and W. J. Dally. Learning both weights and connections for efficient neural networks. In Advances in Neural Information Processing Systems, pages 1135-1143, 2015.
S. Han, X. Liu, H. Mao, J. Pu, A. Pedram, M. A. Horowitz, and W. J. Dally. EIE: efficient inference engine on compressed deep neural network. In Proceedings of the 43rd International Symposium on Computer Architecture, pages 243-254, 2016a.
S. Han, H. Mao, and W. J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and Huffman coding. In International Conference on Learning Representations (ICLR), 2016b.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 770-778, 2016.
Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision, pages 1389-1397) 2017.
D. A. Huffman. A method for the construction of minimum-redundaacyy codes. Proceedings of the IRE, 1099)11098-11 1952.
B. Jacob, Kligys, Chen, M. Zhu, M. Tang, A. Howard, H. Adam, and D. Kalenichenko. Quantization and training of neural networks for efficient integerariihmmeticonnl inference. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2704- 2713, 2018
S. J. Kwon, D. Lee, B. Kim, P. Kapoor, B. Park, and G.-Y. Wei. Structured compression by weight encryption for unstructured pruning and quantization. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 1909-1918. 2020.
Y. LeCun, S. Denker, and S. A. Solla. Optimal brain damage. In Advances in Neural Information Processing Systems, pages 598-605, 1990.
D. Lee, S. Kwon, P. Kapoor, B. Kim, and G.-Y. Wei. Network pruning for low-rank binary indexing. NeXiv:/905.055
2019a.
N. Lee. T. Ajanthan, and P. H. Torr. Snip: Single-shot network pruning based on connection sensitivity. In ICLR, 2019b.
H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf. Pruning filters for efficient convnets. In International Conference on Learning Representations, 2017.
Z. Liu, J. Li, Z. Shen, G. Huang. S. Yan, and C. Zhang. Learning efficient convolutional networks through network slimming. In ICCV, 2017.
C. Louizos, M. Welling, and D. P. Kingma. Learning sparse neural networks through 1rrpougghhiOOrgrrriiiii Oeguularization.
In International Conference on Learning Representations, 2018. URL TRRl/attts://openeeeeee fett/forumiid=iiiy
10

---

Published as a conference paper at ICLR 2022
D. Molchanov, A. Ashukha, and D. P. Vetrov. Variational dropout sparsifies deep neural networks. In International Conference on Machine Learning (ICML), pages 2498-2507, 2017.
R. H. Morelos-Zaragoza. The art of error correcting coding. John Wiley & Sons, 2nd edition, 2006.
S. Narang, G. Diamos, S. Sengupta, and E. Elsen. Exploring sparsity in recurrent neural networks. In International Conference on Learning Representations (ICLR), 2017. 2017.
M. Rabaey, A. Chandrakasan, and B. Nikolic. Digital integrated circuits- A design perspective. Prentice Hall, 2ed edition, 2004.
M. Rastegari, V. Ordonez, J. Redmon, and A. Farhadi. XNOR-Net: Imagenet classification using binary convolutional neural networks. In ECCV, 2016.
A. Renda, J. Frankle, and M. Carbin. Comparing rewinding and fine-tuning in neural network pruning. arXiv preprint (xXxx20003.02389 2020.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. 2xXv::7706003622. 2017.
A. J. Viterbi. An intuitive justification and simplified implementation of the map decoder for convolutional codes. IEEE Journal on Selected Areas in Communications, 16(2):260-264, 1998.
C. Wang, G. Zhang, and R. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020. URL ltttpss//pppeeeeiiee
net / wowummiddusguaaaaaaeairr SkgssAKKK
W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29:2074-2082, 2016.
C. Xu, J. Yao, Z. Lin, W. Ou, Y. Cao, Z. Wang, and H. Zha. Alternating multi-bit quantization for recurrent neural networks. In International Conference Learning Representations (ICLR), 2018.
J. Yu, A. Lukefahr, D. Palframan, G. Dasika, R. Das, and S. Mahlke. Scalpel: Customizing DNN pruning to the underlying hardware parallelism. In Proceedings of the 44th Annual International Symposium on Computer Architecture, pages 548-560, 2017.
A. Zhou, Ma, Zhu, Liu, 7. Zhang, K. Yuan, W. Sun, and Li. Learning n.m fine- fine-grained structured sparse neural networks from scratch. In International Conference on Learning Repre- sentations, 2021. URL
X. Zhou, 7. Du, Q Guo, S. Liu, C. Liu, C. Wang. X. Zhou, I., Li, T. Chen, and Y. Chen. Cambricon-s: Addressing irregularity in sparse neural networks through cooperative software/hardware ap- proach. In 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 15-28. IEEE, 2018
M. Zhu and S. Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. CoRR, abs/1710.01878, 2017.
J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transac- tions on Information Theory, 24(5):530-55 2006.

---

Published as a conference paper at ICLR 2022
A MEMORY BANDWIDTH WITH FIXED-TO- VARIABLE SPARSITY FORMAT
Memory bandwidth is expressed as the access rate (usually in units of bytes/second) at which the data can be read from or written into memory. While the number of memory transactions can be reduced a lot by pruning weights, the utilization memory bandwidth is affected by the variability of the length of data to be accessed during one transaction (Yu et al., 2017). In the case of fixed-to fixed-to-fieed sparsity representation, since all encoded blocks have the same size, full memory bandwidth is utilized. On the other hand, in the case of fxee-to-variable weight representation, encoded blocks have variable sizes such that memory bandwidth can be wasted. To be more specific, let Thur Vl,, and be the number of weights to be encoded, the number of unpruned weights in block, and sparsity, respectively, Assuming that pruning weight is a Bernoulli trial, for CSR format, we obtain
R| = Nhw x (1 S) S)
Var[us] nww x S S1- S).
(4)
Thus, the coefficient of variation (or relative standard deviation) given as
/Varnna]
S
(5)
E[ro]
Tiw I-S
which increases as S increases (0 < S < 1). In other words, for fixed-to-variable sparsity format, more memory bandwidth wasted as more weights are pruned (as shown Figure Note that for fixed-to-fin fixed sparsity format, we have Var[ns] = O, and thus, the memory bandwidth is not wasted at all.
B PERFORMANCE OF SPARSE MATRIX MULTIPLICATION USING CSR FORMAT
6.0
MKL(K=1)
Execation Time (normalized)
5.0
MKL(K-16)
MKL((K-2)
CUDAIR-1)
CUDA(E=16)
CUDA(E-32)
2.0
1.0
Dense
0.0
0.5
0.6
0.7
0.8
0.9
1.0
Proning
Figure S.10: Normalized execution time of multiplying a (2048 2048) sparse matrix with (2048 x k) dense matrix.
For inference of NNs, is known that performance (including latency and throughput) is dominated by matrix multiplications. Figure 10 presents performance when a (2048 x 2048) sparse matrix (of CSR format) is multiplied by (2048 k) dense matrix when is usually small for inference with small batch size. MKL library (operated by i7-7700 @ 3.6GHz) and CUDA 10.2 library (performed by nVIDIA V V100) perform sparse matrix multiplications whose execution times are normalized with respect to corresponding dense matrix multiplications (i.e., using dense (2048 x 2048) matrix). From Figure S.10 it should be noted that even with a high compression ratio (due to high pruning rate), if CSR format is adopted, sparse matrix multiplications can be even slower than dense matrix multiplication. Thus, proposing a regular format after fine-grained pruning critical for parallel computing achieve performance gain by pruning.
C RELATED WORKS
This section describes the previous works regarding how to represent sparsity after fine-grained weight pruning. As mentioned in Section 1, high sparsity and compression ratio be expected
12

---

Published as a conference paper at ICLR 2022
by fine-gu grained (unstructured) pruning, which prunes individual weights at randomly distributed locations.
To represent sparse weights with reduced memory footprint, recording unprumed weights associated with (binary) masking information may be the simplest way. However, for such a case, a reconnttruttonn process is required right before matrix multiplications during inference and it is challenging to be parallelizable due to its random locations (i.e., the number of pruned weights to be processed by a computation unit should highly vary as mentioned in Appendix A). As efforts save memory footprints with fine-grained sparsity, by large, there have been two lines of researches, namely, fixed- to-variable and fixed-to- fo-fixed formats. The Compressed Sparse Row (CSR) format is well-known example of exed-to-variable formats. Since DeepCompression (Han et al.) (016b) utilized the CSR format for representing sparse neural networks (NNs), most of the acceleration library kernels and computing systems have supported CSR data formats along with related APIs for CSR format (e.g. cusparse library in CUDA). Based on recording unpruned values and relational indices row-wise, the CSR format can lead to increased parallelism for computing sparse neural networks. However, because the number of unpruned weights in each row still varies, CSR inherently leads to irregular memory access patterns. SpMM or SpMV operations based on CSR format (even when including block CSR or advanced hardware design for CSR (Han et al., (0) cannot still achieve full (or high) memory bandwidth utilization of computing systems, as numerous studies have raised related issues (Wen et al.] 2016] Yu et al. 2017]] [hhn et al. [2019] Zhou et al. 2018 K Kwon et al. [020 Gale ct al. 2020) (we also reported similar concerns in Appendix B). Despite a highly reduced amount of
parameters to be stored, pruned networks in an unstructural manner have not been fully employed by
the currently available commercialized computing systems.
Fixed-to-fixed data compression, on the other hand, can achieve cully-parallelizable computations along with memory-saving formats and higher memory bandwidth because the length of compressed data is supposed to be ideally equal among any subsets of compressed data. By adopting compression approaches that have been widely used in well-established engineering areas (e.g.. digital communi-
cation, VISII testing, and so on), Viterbi-based compression (Ahn et al. 2019) and XOR- -atee--based compression (Kwon et al. 2020) have been proposed. Note that despite regular memory access patterns, compression methods of Ahn et al. (2019) require a heavy re-training process to acquire proper weight bits and masks while presenting the limitation that the compression ratio should be fixed to be integer values. As for the work of (Kwon al. (2020), the encoding efficiency of previous XOR- EeR-gates-bbsedd based compression is significantly degraded due to combinational encoding algorithm and inefficiency of patch systems.
Our proposed work can be regarded as an extended study of XOR-gates-based compression: 1) this paper verifies that typical data representations (e.g., FP32 and INT8) for DNNs can also be compressed by the XOR-gate decoder (additionally, the inverting technique can boost the encoding efficiency). 2) By using the proposed sequential encoding/decoding schemes, encoding efficiency E can closely approach the theoretical upper bound of fixed-to- to-fixed sparsity formats, and 3) Our encoding algorithm can explore encoded bits according to sequential decoding within the limited size of XOR- gate decoder while Kwon et al. (2020) proposed simple heuristic algorithm assuming combinational decoding only (i.e., N₂- = =0).
D FUNDAMENTAL LIMITS OF COMPRESSION
We are interested in the upper bound of compression ratio that can be analyzed by entropy (while allowing sred-to-variable compression). Then, when we suggest a fixed-to-fixed compression scheme, we can estimate how close the compression capability of a fixed-to-fixed scheme is to the maximum.
Entropy presents the minimum average number of bits to represent an event when a probability distribution of those events is provided (Margoos-Zaragoza 2006). To investigate the entropy of pruned weight blocks (and the maxinum compression ratio correspondingly). block of bits is assigned to a symbol such that a probability distribution of symbols minimizes the entropy. In other words, symbol assignment is designed to minimize the average number of bits (i.e., entropy to represent symbols) that is given as
H =
Σ ps loga Pi:
(6)
13

---

Published as a conference paper at ICLR 2022
where n is the total number of symbols and P; is the occurrence probability of each symbol.
Symbol assignment We concatenate all of k-th bits weights into a group and produce fww groups when The is the number of bits represent weight (e.g., The 32 for single-precision and 8 for INT8) and 1 S & S Thy Symbol assignment is performed in each group independently without referring to other groups. Suppose that certain block from one of the groups given as {0XX1} and corresponding mask bits (that are shared by all nuw groups) are {1001} (0 means masking). By filling up X with 0 or 1, [0XX1) is selected to assigned one of 4 symbols (i.e., (0001), {0011}; {0101) or (0111)) while such symbol selection decides entropy. In the following two examples (where m==4), we illustrate the symbol assignment method that minimizes the entropy.
Entropy (n, e.g., {XXX0), {X1XX}) In this case, every block (of ny=4 and n. =1) can be assigned to either one of two symbols (f0000), {1111}. Since P(0000) = P(1111) = 0.5, from Eq. 6 H (0.5 (-1) 0.5 (-1)) 1. Thus, block of n,=4 and na, be compressed into bit that indicates one two symbols. There are many other sets two symbols to meet 1,
such ((0010), {1101}) and ([1010), (0101)).
Entropy (n,, 2, e.g. [X01X), {10XX}) A set of symbols should meet the following require- ment: if we choose random nl and random n:2 (1 S ml, n22 S ni, of n2) and collect Inil-th bit, n2-th bit) of each symbol, then, each of (00, 01, 10, 11] should appear in the collection. Under such a constraint, after a careful investigation using a full search, the minimum number of symbols 5 to represent all blocks of n4,44 and n. =2. An example set of 5 symbols with corresponding occurrence probability to minimize entropy is as follows: P(0000) = 6 /2, P(1110) = 6/24, P(0101) = 5/24, P(1001) = 4/24, and P(0011) 3/24. Then, from Eq. 6 H is approximately 2.28 (bits) attainable through fixed-to-variable compression. On the other hand, for a fixed-to-fixed scheme, a block (of n,-4 and nt,, 2) is compressed into 3 bits to represent one of symbols.
For n,=3,, the minimum number of symbols is 8 and a block can be compressed into 3 bits. All in all, when ny is fixed across blocks, can be equal to or slightly higher than T2.
14

---

Published as a conference paper at ICLR 2022
E ENCODING ALGORITHM
In this section, we describe our encoding algorithm based on dynamic programming algorithm that can minimize the number of unmatched bits. Our encoding algorithm presents time-complexity as O(l 2 N (N,+)) and space-complexity as O(2 No.) Thus, even though increasing Ni, and N, enhances E, (Nin x N.) is empirically limited to be less than 26 under the constraint of 32GB memory of single GPU. For each binary weight (7 generates the encoded vectors (1.(L...+N.)- XOR- decoder (M ) is pre-determined and fixed for inference. Note that the number of encoded vectors (w... 1I.(1+,,)) ++ No. not l. wi and w are pre-determined as (0) and used for encoding the first binary weight vector.
I Rur), the function ENCODING
15

---

Published as a conference paper at ICLR 2022
Algorithm 3: Encoding algorithm when N, = 2. For binary matrix W the ENCODING function generates encoded bit vectors. For varied N.. the number of for-loop statements for i² (e.g. line 34-36) and the dimensions of arrays (dp and path) are changed N₂ +
Parameters W is binary weight vector to be encoded. MASK is pruning mask information for W is (N.++ + -dddemensiin array. dp[[[[a][[ stores the minimum number of error bits when (aN(a) and BIN(b) are fixed as wi and wf-1- path (N,=1)-dimension array for history.
Additional Functions SIZE W) returns the number parameters in W. RESHAPE(ar, shape) returns same data (ar) with specified shape, shape. (NIT(ar, inif) sets a value init to all elements in ar. BIN(dec) returns binary value of dec. DEC(bin) returns decimal value of bin.
Function ERR nErr f- for - to Nout 1 do
ERR_NUN_ NUM (z, y, mask):
if mask(i] i] + and æ1i] + vli then nErr Err
return nErr
Function ENCOD NG (W,, . AAK)):
I T SIZE(W
data f- RESHAPE(W [t, NNaaa) P Slicing
mask < RESHAPE(M ASK, Noma)) Slicing
INIT (dp, FN) p Initialize for starting point and wf. w BIN(O), BIN(O)
dpl dp[N:][0[01
> Find the minimum number of errors for < N. 1-+1 to I+NN do for < to 2on
for 1' -- 0 to 2 Nen 1 do
for 2-2 +- 2i.
out +- M (BIN(1 B) BIN BIN
Bar ERR NUM tout, data mask(t]
if dpp[t[="]]a">> 2 >
+ dpl 1] 1 then
[ + new dplt 1][0
[oth(]][=]["* BIN(
b Find the last two(=N,) encoded vectors minerr + FNF.
for if = to No. - do
for f'1 to 2N
do
if minerr > dpll N. i
then
mimmer dpll N. FF'
wf+2, wi41 BIN(1 ).BI)()))
Get encoded bits by following history array for t to 2N. + by L w/ + pathhtt + N. [///DEC(uu(==)]]][C((rr... return (wf, wi...., wi.,,
16

---

Published as a conference paper at ICLR 2022
F MEMORY REDUCTION WITH LOSSLESS COMPRESSION
Reshape
Correction
Encoded bit vectors (Nax bits)
Decoding
W W
512
(length 512)
Mask
for each block (k bits)
1
1
W
Body for Correction
Location information Aipppdd (1)): of unmatched bits)
Idx
(m x m)
W
Correction process for lossless compression. After the encoded (compressed) bit vectors decoded, unmatched bits (that encoding could not target successfully) are flipped by correction information that records the locations of unmatched weight bits.
Figure S.11:
For lossless compression, the unmatched bits (error bits) should be corrected right after decoding procedures. Since the random number generator produces 0 1, the unmatched bits can be simply corrected by flipping.
To compute the memory reduction, we suggest block-wise correction logic to be conducted by flipping error bits in a p-length vector while each error location is given as bit position inside vector. As depicted has p-length, the decoded vectors wV',, are reshaped to w (I: [ 1) and each reshaped vector
Figure[S.11] when the block-wise correction is performed while block size
"h corrected by corresponding error bit locations indicating which bit is be flipped inside block (of p-length).
The amount of compressed bits can be computed
mm + (log, p + 1) of unmatched bits).
Nin
Nout
p
The first term is the number of bits of w . as the compression results by sequential encoding. The second term is the number flag bits while each flag bit indicates whether non-zero number of unmatched bits exists in each p-length vector (as E' approaches 1, there are many p-length vectors that skip the correction step)). The third term includes locations of unmatched bits (inside p-length block) to be flipped and an additional one bit to specify the end of the streaming error bit locations (i.e., means the following (loga p) bits contains the next correction information of the same block). Thus, each block of p-length involves (log, 512 + 1) x (# of unmatched bits)) for error bit locations.
17

---

Published as a conference paper at ICLR 2022
G DESIGN COMPLEXITY OF THE PROPOSED COMPRESSION METHOD
The time and space complexity the encoding process (presented in Appendix with corresponding algorithm description) independent of inference performance since encoding is performed offline (thus, GPUs or CPUs would be fine to run the encoding algorithm). Encoding algorithm based on a dynamic programming technique as shown in Appendix E has the following space and time complexity.
Encoding Process
Time complexity: O(l (1122)((NN+t))
Space complexity: O(2N
Algorithm 3 shown in Appendix explores all possible 2((4+N,)) outputs of an XOR-gar decoder to produce imput vector that can minimize the number of unmatched bits. Note that partial string of imput (of an XOR-gate network) having 2N, bits share N N. bits continuously through shift registers. As such, for the time index t + 1, search space (having the size of 2((++14N,))N.. is overlapped with the search space of the time index (having the size of 2((t++N,, as much as 2 g.,, Accordingly, the time complexity at the time index t (that optimize the input) is Then, since iterate such operation times, the overall time complexity becomes O(l 2(((+,N.)NNN.))) To exploit sharing computations between different time indices, we need to store intermediate results having the size of 2N.XN. which becomes the space complexity of Algorithm 3.
reduced from ((2(((+1+N
to (( ( )
/2((-N(n))
Decoding Process As for decoding operations, we suggest that the decoding algorithm is best supported by a hardware design consisting of XOR gates (and a few shift registers). Hence, this section, let specifically argue hardware design issues of XOR-gate decoders.
The strongest benefit of employing digital circuits (in the form of ASICs FPGAs) to implement XOR gates is that all XOR gates can performed simultancously (unlike GPUs or CPUs where each needs to simulate only a few XOR gates). Thus, all XOR operations of our proposed decoder are completed within just one clock cycle.
Ne (with shift registers) would increase the latency. Throughput, however, maintains to be the same regardless of N, through pipelining technique which is basic hardware design principle.
Overall, the design complexity (in terms of area overhead and latency) of XOR- gate decoders is extremely low (note that one XOR gate consumes only 6 transistors).
XOR-gate decoders would work as memory decompressors (located in-between memory and computation logic). In the view of computational units that receive outputs of an XOR-gate decoder, then, the amount of memory is simply reduced while regular memory access patterns are not disturbed.
Given N., an XOR-gate decoder requires N, additional clock cycles for the latency.
Since M matrix has the size of Nout x Nin and an element of M is randomly filled with 0 or 1, the number of XOR gates is (Nout - N2../2). Thus, the total number transistors to design XOR-gate -ate decoder is (3 Nout ...))
Overall, we can provide full memory bandwidth (based regular memory access patterns through fixed-to-fieed sparsity formats) while the overall hardware design cost only marginal.
While designing DNN inference accelerators is gaining increasing attention, our work can provide new research direction.
18

---

Published as a conference paper at ICLR 2022
H ADDITIONAL ANALYSIS ON EXPERIMENTS
In this section, we provide additional analysis and results for experiments in Section 6.2.
Transformer (FP32. Magnicude- based Pruning)
0.75
0.2
14 15 16
10
211
22
21
.2
bit Index
(lisign Bit, 2-01
exponnnt bits, 10:32)
Traction bitt))
(b) ResNet-50 (PP32, Maguitude--eeee Pruning)
0.70
0.00
0.35
0.00
Indic
(lisign bit, 2-0) expouoot bits, 10-32) Draction botte)
RewNet-50 (INTS, Magnitudee-baoct Pruning)
1.00
0.50
0.00
inder (1ziggn
Figure S.12: Ratio zeros when weights are divided into groups when is the bit-index (i.c., for FP32 number format, k=1 means sign bit and k=32 means the least significant bit in mantissa). For models, Transformer(F332) 50sPet-) and ResNet-50(INTB) are investigated. Most weights consist of similar amounts of Os and 1s. For the exponent bits of FP32 models, there noticeable skewed ratios of zeros (e.g. while most of the 2nd bits in Transformer are zero, most of 3rd 4th and 5th bits are ones.) because the range of exponent bits is limited according characteristies of DNN models (e.g. regularization such as weight decay). We can gain additional efficiency by adopting the inverting technique for the FP32 models.
19

---

Published as a conference paper at ICLR 2022
Table S.4: Coelficient of variation of The and E of selected layers of the Transformer pruned by random, magnitude- buseee,abeddd.... L0 regularization, or variational dropout pruning method.
N.
99.5%
99.3%
99.0%
99.2%
98.7% 7%
98.8 08.8%
99.7%
99.7%
99.3 33
99.5
98.0%
99.1%
99.2%
99.6%
94.3%
97.4%
E (%6
N
98.7%
98.7%
98.2%
98.5%
97.6%
97.7%
99.1%
99.1%
98 6%
98.9%
97.0%
98.5%
98.7% 7%
99.0%
93.6%
96.4% .%
NN=0
93.7%
93.7%
93.4%
93.6%
92.7%
92.76
94.3%
94.3%
94.4 4
94. 6%
92.5%
93.7%
94.3%
94.3%
89.4%
91.8%
COFFF
0.341
0.343
0. 0.390
0.363
0.476
0.467
0.303
0.309
0.349
0.315
0.516
0.363
0..31
0.347
0.770
0. 0.499
VAR. DROPOUT
VAR. DROPOUT
VAR. DROPOUT
VAR. DROPOUT
PRUNING METHOD
RANDOM
RANDOM
M MAGNITUDE
M MAGNITUDE
L. REG.
REG.
RANDOM
RANDOM
MA MAGNITUDE
MAGNITUDE
LO REG.
LO REG.
ENC2/SELF ATT/OUTPUT
ENC2/ ATT/OUTPUT
ENC2/SELF ATT/OUTPUT
DEC3/SELF ATT/Q
DEC3/SELF_ DAC////EF_ATTA ATT/Q
DEC3/SBLF L ATT/Q
DECS/SBLF ATT/
DEC2/SBLF ATT/V
DECE/FEN2
3/FF/2
DEC3/FEN2
DECT/FENI
DECS/FEN2
DECS/TTN2
D/CS/FEN2
DEC4/FRNI
LAYER
NAME
0,700
0.700
0.700
0.700
(112, 0.699
(512, 0.698
(512,312) 0.703
0.697
0.900
0.900
0 3.000
0.900
0.904
0.896
906
0 0.904
S
(512, 512)
(2048. 512)
(512, 512)
(2048, 512)
(2048, 512)
(512, 512)
(2048, 512)
(12,,122 512)
(2048, 512)
5122
(S12,
(512,512)
(2048, 512)
SHAPE
Nin; Nout
(8, 26)
(8, 80)
20

---

Published as a conference paper at ICLR 2022
Table S.5: Coefficient of variation of Thu and E of selected layers of the ResNet-50 pruned by random, magnitude- baseebbbbdd.....- or variational dropout, pruning method.
N.=2
99 99.2%
99.5%
98 9%
99.0%
99.1%
99.1 1
98 00
98.1 %
99.8%
99 8%
99.6%
98.
N,=1
98 58.6%
98 8%
98.4%
98.4%
98.6%
96.8%
97.4%
99.2%
99.2%
98.3%
98.9%
98
N,=0
94.2%
94.3%
93.2%
93.8%
94.2%
94.4%
92.3%
92. 2%
94.6%
94.6%
94.
94.5%
COEFF
0.347
0.334
0.505
0.428
0. 0.403
0.361
0.683
0 0.407
0.303
0.299
0.366
0.324
VAR. DROPOUT
VAR. DROPOUT
M MAGNITUDE
VAR. DROPOUT
VAR. DROPOUT
PRUNING METHOD
RANDOM
RANDOM
MAGNITUDE
MAGNITUDE
RANDOM
RANDOM
MAGNITUDE
GROUP2 LAYERS BN2
GROUP3 LAYERS BN3
GROUP2 LAYERS BN2
GROUPS LAYERS BN3
GROUP2 LAYERS BN2
GROUP3 LAYERS BN3
GROUP3 LAVERS BBN2
GROUP4 LAYERO BN3
GROUP3 LAYER3 BN2
GROUP4 LAYERO BN3
GROUP3 LAVERS BN2
GROUP4 LAYERO BN3
NAME
0.700
0.700
0.700
0.700
0.709
0.706
0.900
0.900
0.900
0.900
0.913
0.896
S
(1,1, 1024,02,,56,
256, 21,, T
T.1,1024,256,
(1,1,256. 1024)
(3.3,512.312)
1,,, 1024) 1024)
(3,3, 256. 256)
(1, 1,211, 2048)
(3, 3, 256. 256)
(1, 512. 2048)
(3, 3,6, 256)
(1. 1,12,
SHAPE
Non Nowt
(8, 26)
(8. 80)
21

---

Published as a conference paper at ICLR 2022
(e) N,
N;
(c) N,
[6) N,
B1%
(d) N.
64 N
bit Index
bits,
10-32: fraction bits)
index
(1ssggn
bit, 2-9:
bits, 10-32:
fraction bits)
(a) Transformer (FP32, Magnitude-basee Pruning)
ResNet-50 (FP32, Magnitude-basse Pruning)
(o)
(b)N
bit Index (Treign bit, 2-8: magnitude hits)
(c) ResNet-50 (INT8, Magnitude-hased Pruning)
Figure S.13: E of the Transformer and ResNet-50 (pruned by 5=70%) measured for each bit index (S 32 for FP32) individually with various N₂ while inverting technique is also considered. It can be observed that the inverting technique improves E' for N, 0 and N, 1. When N. 2. the improvement on is not noticeable.
22


Reviews:
[{"review_id": "yB7KeHwrqk5", "reviewer": "Reviewer_ieBc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "At a high level, the paper has two sides: a method and the context in which it is intended to be used. The authors do a good job at presenting the first. The technique is described in (sometimes intense) detail, and the evaluation gives straight answers to clearly-defined questions. The latter (context) is a bit weaker. The authors choose to treat their problem in isolation, which means that the paper sometimes loses sight of why the method was proposed to begin with. Computational aspects are glossed over completely, despite being the nominal motivator for the paper, and outside of a couple of statistical assumptions, there's not much connection to the ML models they test. The optimistic view is that their approach is successful regardless of input; the pessimistic view is that the impacts of various model characteristics which this community cares about are largely unknown. Appendix E does add a bit of insight here.\n\nStrengths:\n\n- The authors are fairly comprehensive in explaining the factors involved in choosing the method's tuning parameters. They clearly explain trade-offs and provide instructions on how to arrive at ideal values.\n\n- I appreciated the minor analyses the authors ran. The bit inversion technique, for instance, concisely raised a problem and summarily offered a solution. Walking the reader through the pitfalls of a new technique makes the paper more enjoyable to read.\n\n- The prose is generally clean and easy to read.\n\nWeaknesses:\n\n- No mention of the actual computational performance of the method. This seems important to the paper, considering the whole motivation for fixed encoding is memory access regularity. I don't necessarily expect a highly-tuned implementation that beats vendor kernels, but if the nominal goal of pursuing fixed-sized encoding is to improve speed via improved memory behavior, I would expect some concrete evidence that the proposed method achieves that purpose and some notion of the computational costs it pays for that benefit. From the method described, it looks efficient (especially if offloaded to specialized hardware), but it hurts the paper not to see quantitative support.\n\n- I was expecting to see a mention of end-to-end model accuracy. With best the $E$ values listed, I anticipate the end-to-end effect is (hopefully) marginal, but it would be good to confirm that this is the case.\n- In some cases, the paper's math could be clearer. Terms occasionally appeared in figures before their introduction in text, and I would've appreciated a brief mention of word length somewhere in section 2 or 3. It didn't help that many important terms were $N_{foo}$ or $n_{bar}$. This is minor and admittedly subjective.\n\nQ: This work seems to share many parts with the references it seems to build on: Kwon20 and to a lesser extent Ahn19. While I have a general sense of where this paper diverges, can the authors briefly summarize what they feel the novel contributions to the community over those works are?\n\nAnd as feedback: given the overlap, it might strengthen the paper to be more explicit about the differentiating factors. I would probably have appreciated a direct comparison (perhaps in a related works section, seeing as one is not supplied).\n\nQ: Many other aggressive encoding schemes leverage the pruning mechanism to improve encoding behavior (e.g., weight sharing to reduce indexing cost for CSR schemes). These reduce encoding costs to lower than would otherwise be statistically expected. What's the analog here? I.e., with additional manipulation of non-zero weights (lossy or not), does this method offer avenues for improvement?", "summary_of_the_paper": "The authors propose a sparse weight encoding scheme based on XOR-gate networks and a method for finding the requisite sequence which minimizes encoding error. They show that their method can achieve near-zero overhead at low encoding-error rates.", "summary_of_the_review": "The paper does a reasonable job of presenting its sparse encoding scheme, and the analyses and evaluation seem reasonable. The paper feels a bit isolated and theoretical, which is odd given its stated goals. The method doesn't seem bad, but the reader is left with a lot of open questions about putting it into practice.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "rjVTTXORQlb", "reviewer": "Reviewer_NvPC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "I like the motivation of this paper which is a very important problem in practice. To the best of my knowledge, the solution is novel and interesting, and I believe it is an orthogonal contribution to many other literatures in the compression community (e.g., magnitude-based compression, variational dropout etc). The experimental results look promising and the theoretical analysis is sound to me. I have a couple of comments regarding how the paper can be improved in the revised version. First, the paper starts with an motivation of improving the parallelism running the pruned network. However, it's a pity that the paper doesn't show any practical acceleration on ImageNet or WMT. Only compression ratio and memory reduction have been showed for various of methods. (Although Appendix A kind of showing sparse matrix multiplication is slow, I think it's still better to directly show the runtime reduction using the pruned model on real data). Second, the figures are somewhat cluttered and a bit hard to understand. I would recommend spend some time and revise them. Third, literatures and references spread across sections. An individual section (Related Work) for discussing compression literatures would be preferred. ", "summary_of_the_paper": "This paper tackles an interesting and important question which is how can we make the pruned network regular such that it can run quickly on GPU / common hardwares. The problem essentially originates from the fact that typical computational hardware can be slow when accessing in-contiguous memory address. This paper proposes a sequential encoding-decoding shemes and can compress irregular pruned weights to a regular (block-wise) structure stored in memory and shows experimental results in large-scale models / datasets.", "summary_of_the_review": "The motivation is persuading and the method is novel. The author also demonstrate the effectiveness of their method on large scale datasets with a number of compression techniques. Although the writing can be improved, I think this is a good paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aIS0lmPSX8S", "reviewer": "Reviewer_Qcma", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes a sequential fixed-to-fixed encoding scheme for sparse neural network weight encoding/decoding. The core component of the algorithm is shifted registers that expand the decoding window and extra code for recording unmatched bits. \n\nPros: The proposed shift register structure offers a much better improvement on encoding efficiency than increasing the coding block size. To my knowledge this algorithm is novel.\n\nCons:\nIt is unclear how much actual benefit this algorithm can offer as to my understanding this algorithm requires very high decoding computing and space complexity. With such kind of complexity CSR probably can also overcome its shortcoming. And such kinds of decoders would probably not fit in the very limited space of computing cores such as a GPU. \n\nThe paper is difficult for a reader that is not familiar with prior works such as Kwon et al., 2020 and Ahn et al., 2019. I only managed to comprehend this work after going through those two prior works. I suggest references to those works should be introduced in Sections 1 and 2 along with some related background info to help readers.\n\nI suggest renaming the XOR-gate network to something like XOR-gate decoder, given this community generally associates “network” with neural networks.\n\nP2: Please explain how you arrived at Figure 1A.\n\nP2: Please explain “x with Mask” in Algorithm 2.\n\nP2: Please precisely define memory bandwidth. What you described here seems vague. \n\nP2: “Since higher sparsity leads to higher variance on pruned weights in a block”. Please clarify this sentence. Are you sure this is correct?\n\nP3, last line: “(masked) weights”. Do you mean weights not subjected to pruning? Shouldn’t such weights be called not masked weights?  \n\nFigure 4: “S is entire pruning rate”, I believe “entire” here is not necessary and is causing confusion.\n\nP4: A reference to GF(2) is probably necessary.\n\nP4; the sentence just above Section 3.1. : I believe the logic of this sentence is not valid. Even though the conclusion is correct.\n\nP7: “(Nin × Ns) is empirically limited to be less than 26” What you mean by this? If you chose to have $N_in=8$, does that leave you with $N_s<3$? If you need 32GB memory for decoding, is this algorithm applicable in real-world applications?\n\nTable2 and 3 probably contain too much redundant information. I suggest removing some results so there will be enough space for improved clarity.", "summary_of_the_paper": "This work proposes a sequential fixed-to-fixed encoding scheme for sparse neural network weight encoding/decoding. The core component of the algorithm is shifted registers that expand the decoding window and extra code for recording unmatched bits. ", "summary_of_the_review": "Given the issues I raised in the main review I will not recommend this paper for publication for now. But I would be happy to change my evaluation if the authors can improve the clarity of the paper and address my concerns.\n\nAfter rebuttal:\nI raised my evaluation from 5 to 6, given the improvement included in the new revision. However, there are still two main issues I want to point out. First, the authors built their work upon Kwon20 and Ahn19, but they only cite those two papers in the latter part of their manuscript.  And related works section is only included as an appendix section. This layout is unusual, and it made their manuscript hard to comprehend for an audience that is not familiar with the specific topic. Second, despite my repeated request for clarification on the computing complexity, the authors still only gave a vague description of the issue. I hope the authors can fix those two issues in their camera-ready if the paper is accepted.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QAWouE5jcz", "reviewer": "Reviewer_dSLA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The method is novel.  I have the following: \n\nConcerns:\n\n- The compression scheme with associated encoder/decoder purely solves the communication problem where HW performance is bottlenecked by limited memory bandwidth under irregular access patterns.  How does compute factor into the picture?  How does compute overhead of decoding scale?  \n- Experiments are performed on GPUs.  It would be desirable to understand applicability to other accelerator architectures, specifically spatial architectures.  \n- On page 2: ``higher sparsity leads to higher variance on pruned weights in a block\".  Is this true?  Variance of the number of zero/nonzero should be nonmonotonic w.r.t. sparsity; extremely sparse or dense cases have zero variance.  Am I missing something?  ", "summary_of_the_paper": "The authors proposed an encoding scheme and decoding mechanism for efficient communication of irregular sparse DNN parameters, and demonstrated with sparsified transformer and resnet50.  \n", "summary_of_the_review": "Novel idea of significance and potential practical value.  Presentation could use further clarity (e.g. elaboration of basic concepts such as fixed-to-fixed) since the readership of this conference is probably not experts in communications.  \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: ### Summary

The key idea behind this approach is a new technique to map irregular sparsity to a regular, compressed pattern. The results can, in principle, therefore overcome several standard limitations with irregular data storage formats.  The results improve over existing (though related) techniques.

### Discussion

#### Strenghts

- An interesting and timely topic to study

- Results show non-compute improvements

#### Weakness

The primary weakness noted among the reviewers was the lack of study on actual decoding performance. As I note below, this is a serious oversight that given the already existing theoretical work in the area warrants study as the community should begin to turn towards mapping that theory to practice.

### Recommendation

I recommend Accept (poster). This is a strong piece of theoretical work. However,  I would like to note that while I believe this work meets the current evaluation standards set in the area, it is time for follow on work to take the additional step to validate the practicality of the approach through a performance evaluation (either in simulation or FPGA/ASIC work).
Decision: Accept (Poster)