FIXED-TO-FIXED MODEL COMPRESSION
Year: 2022

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 finegrained pruning methods such that sparse neural networks can be stored in a highly regular structure. We first estimate the maximum compression ratio of encodingbased 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.

heading: 1 INTRODUCTION
text: 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., 2015), various practical pruning methods have been studied to 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 to a deeper understanding of weight initialization. Based on the Lottery Winning Ticket hypothesis (Frankle and Carbin, 2018), (Renda et al., 2020) suggests a weight-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 is dominated by matrix multiplications (Gale et al., 2020). Algorithm 1 presents a conventional sparse matrix-vector multiplication (SpMV) algorithm using CSR format which involves irregular and data-dependent memory accesses. Correspondingly, performance gain using a sparse matrix multiplication (based on CSR) is a lot smaller than the compression ratio of pruning (Yu et 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 et 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-grained pruning.
In this paper, as an efficient method to compress sparse NNs pruned by fine-grained pruning, we consider weight encoding techniques. As shown in Algorithm 2, encoded weights are multiplied by a fixed binary matrix M⊕ to reconstruct the original weights. We propose an encoding method and M⊕ design methodology to compress sparse weights in a regular format. It should be noted that a sparse matrix multiplication can be even slower than a dense matrix multiplication unless pruning rate is high enough (Yu et al., 2017; Gale et al., 2020) that does not happen with Algorithm
∗Equal contribution.
2 for memory-intensive workloads. We study the maximum compression ratio of such encoding-based compression using entropy and propose a sequential fixed-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 a block.
Algorithm 1: SpMV (CSR format) In: Dense vector x,
CSR vectors dat, row, col Out: Dense vector y for i← 1 to n do
for j ← rowi to rowi+1 do yi ← yi + dat[j]× x[col[j]]
/*Irregular, data-dependent access*/
Algorithm 2: Proposed SpMV (using encoded weights) In: Dense vector x∈Rm, Encoded vectors we1..n∈Rk
Fixed matrix M⊕ ∈ {0, 1}k×m, Mask ** (k m) Out: Dense vector y for i← 1 to n do
Wi ← wei ×M⊕ over GF(2) yi = Wi · x with Mask (for zero skipping)
/* Decoding m elements using wei (Regular access)*/

heading: 2 FIXED-TO-FIXED SPARSITY ENCODING
text: Data compression is a process of encoding original data into a smaller size. If a fixed number of original bits are encoded into a fixed number of (smaller) bits, such a case is categorized into a “fixed-to-fixed” compression scheme. Similarly, “fixed-to-variable”, “variable-to-fixed”, and “variableto-variable” 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 fixed-to-variable scheme, Lempel-Ziv (LZ)-based coding (Ziv and Lempel, 2006) as variable-to-fixed scheme, and Golomb codes (Golomb, 1966) as variable-to-variable scheme).
Among those 4 categories, “fixed-to-fixed” 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 a translation would demand non-uniform memory accesses that lead to significantly degraded memory bandwidth utilization as shown in Figure 1.
Specifically, in the case of fixed-to-variable sparsity format (e.g., CSR) in Figure 1, we observe that memory bandwidth is low because fine-grained pruning induces a variable number of pruned weights for a certain block or row while memory is designed to access a 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 a significant issue even though the amount of data to be stored is reduced (see Appendix A). As a result, for fixed-to-variable sparsity format, it is difficult to implement fine-grained 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 1 can maintain the same memory bandwidth regardless of sparsity.
In this work, we propose a “fixed-to-fixed” compression scheme as shown in Figure 2 when the number of pruned weights in a 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 a fixed-to-variable scheme as we discuss in Appendix D). Suppose that a block to be encoded contains (fixed) nb bits among which (fixed) nu bits are unpruned. A fixed-to-fixed encoding scheme is required to support high compression close to (nb/nu) (estimated by entropy). Fixed-to-fixed decoding, then, accepts (fixed) Nin bits as an input and produces Nout bits as an output while Nout/Nin = nb/nu.
• (Variation tolerance) For a fine-grained pruning, nu is given as a random variable whose distribution is affected by pruning rate, nb size, a particular pruning method, and so on. Our goal is to maintain a fixed-to-fixed scheme with a high compression ratio even under Var[nu] 6= 0. In Figure 2, for example, 5 blocks of original data have various nu values while the size of an encoded block is fixed to be 4 (=E[nu]). We will discuss how to design a variation tolerant encoding.

heading: 3 RANDOM NUMBER GENERATOR
text: Before we discuss compression schemes, let us assume that a binary masking matrix is given to represent which weights are pruned or not (note such a binary masking matrix can be compressed significantly (Lee et al., 2019a)). Then, a pruned weight can be described as a don’t care value (5) that is to be masked. We also assume that 1) pruning each weight is performed independently with pruning rate S and 2) unpruned weight is 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-fixed compression scheme is considered, we adopt random number generator schemes that enable encoding/decoding of weights. A random number generator accepts a fixed number of inputs and produces nb bits so as to implement a fixed-to-fixed compression scheme. As shown in Figure 3, a weight block is compared with every output of a random number generator. If there is an output vector matching original (partially masked) weights, then a corresponding input vector of a random number generator can be 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), 2nu outputs out of 2nb
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 (Morelos-Zaragoza, 2006). Since then, practical error correction coding techniques have been proposed to implement random-like 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 (2) (Morelos-Zaragoza, 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 (Kwon et al., 2020). Another example is to 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 a compressed one by a random number generator, we can attach patch data to fix unmatched bits (Kwon et al., 2020) or re-train the model to improve the accuracy (Ahn et al., 2019).
To compare the random number generation capability of various block-level compression schemes, we introduce ‘encoding efficiency’ given as a percentage.
E (Encoding Efficiency) = # of correctly matched bits
# of unpruned bits × 100(%) (1)
Let S be pruning rate (0 ≤ S ≤ 1). To measure 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 − S). 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 a block missing a matching output of a 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.

heading: 3.1 FIXED PRUNING RATE IN A BLOCK
text: For simplicity, we assume that nu in a block is a fixed number. Let us study E when nu is fixed using an XOR-gate decoder introduced in (Kwon et al., 2020). For an XOR-gate decoder, when Nout is the number of output bits and Nin is the number of input bits, a matrix M⊕ ∈ {0, 1}Nout×Nin presents connectivity information between an input vector wx(∈ {0, 1}Nin) and an output vector wy(∈ {0, 1}Nout) such that we have wy = M⊕ ·wx over GF (2). For example, if the second row of M⊕ (with Nin = 4 and Nout = 8) is given as [1 0 1 1], then w y 2 = w x 1 ⊕wx3 ⊕wx4 (‘⊕’ indicates a binary XOR operation or an addition over GF (2) equivalently). An element of M⊕ is randomly filled with 0 or 1 as a simple random number generator design technique (Kwon et al., 2020).
To measure E, let Nin/Nout ≈ 1− S such that Nout = bNin · (1/(1−S))c. Correspondingly, for a certain S, a block size (=Nout) increases as Nin increases. When nb = Nout and nu = Nin,
Figure 4a describes statistics of E when random M⊕ matrices are associated with random blocks. From Figure 4a, it is clear that increasing Nin is the key to improving encoding efficiency. Note that, however, increasing Nin and Nout complicates the decoding complexity (due to large M⊕) and the encoding complexity as well (due to an exponentially large search space).

heading: 3.2 VARIABLE PRUNING RATE IN A BLOCK
text: Now we allow nu in a block to fluctuate. For Figure 4b, we assume that pruning each weight is a Bernoulli event (with S probability) such that nu in a block follows a binomial distribution B(Nout, 1−S) (thus, E[nu] = Nout(1−S) and Var[nu] = NoutS(1−S)). Nin is given as E[nu] in Figure 4b. Compared to Figure 4a, E 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 (= √ Var[nu]/E[nu] = √ S/(Nout(1−S))) decreases as Nout increases. Indeed, the gap between E in Figure 4a and E in Figure 4b tends to be slightly reduced when Nin (as well as corresponding Nout) increases. To illustrate, as shown in Figure 5, when there are two blocks of different nu, concatenating two blocks into a block (thus, increasing Nout) can increase the probability of successful encoding due to efficient usage of Nin. Increasing Nin and Nout by n times, however, requires an XOR-gate decoder
to be larger by n2 times with only a marginal gain in E.
Another way to improve E under the variation on nu is to decrease Nout and increase Nin. In this case, however, the compression ratio is reduced consequently. We need a solution to design a fixed-to-fixed sparsity compression technique that can improve E of a random number generator under the variation on nu without sacrificing compression ratio (i.e., Nin/Nout = 1−S). To validate our observations obtained by synthetic random data, we compute E of an XOR-gate decoder using the Transformer model (Vaswani et al., 2017). The first fully-connected layer of the Transformer is pruned by a magnitude-based pruning method (Han et al., 2015) with pruning rate S. Interestingly, E described in Figure 4c is similar to that of Figure 4b. As such, our assumption that pruning a weight is a Bernoulli event is valid for the context of magnitude-based pruning.

heading: 4 PROPOSED SEQUENTIAL ENCODING SCHEME
text: If Var[nu] is non-zero and Nin is fixed, then blocks of small nu (< Nin) would have many possible input vectors with matching output vectors while other blocks with large nu (> Nin) 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 a block of small nu can be reused for the neighboring blocks of large nu. In other words, by sharing some parts of an input vector for multiple consecutive blocks (of diverse nu 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-fixed compression schemes (for example, XOR-gate-only decoder (Kwon et al., 2020) lacking tolerance for nu variation, and Viterbi encoders (Ahn et al., 2019) that receive only one bit as an input (i.e., Nin is restricted to be 1).
Weight manipulation Since our encoding/decoding techniques process data in a block-level (in the form of a 1-D vector), original sparse weight matrices (or tensors) need to be reshaped through grouping, flattening, and slicing. Assuming that a number format has the precision of nw bits (e.g., nw=32 for FP32), as the first step of weight manipulation, a weight matrix W ∈ Rm×n is grouped into nw binary matrices W b1..nw∈{0, 1}m×n (otherwise, nw successive bits are pruned or unpruned). Then, each binary matrix (or tensor) W bi is flattened to be a 1-D vector and each vector is sliced into wbi,1..l blocks when l (=d mnNout e) indicates the number of blocks in a 1-D (flattened) vector.
Decoding with an input sequence For an XOR-gate decoder (as a non-sequential decoder) at time index t, an output vector wb ′
t (∈ {0, 1}Nout) is a function of an input vector wet (∈ {0, 1}Nin) such that wet is utilized only for one time index. In our proposed sequential encoding scheme, w e t is exploited for multiple time indices using shift registers. Specifically, we copy wet to a shift register whose outputs are connected to the inputs of the next shift register. Let Ns be the number of shift registers. In the proposed scheme, an XOR-gate decoder receives inputs from Ns shift registers as well as wet . Then, as shown in Figure 6, a sequential decoder (consisting of an XOR-gate decoder and shift registers) produces wb ′
t as a function of an input sequence of (w e t , w e t−1, ...) while such a
function can be described as wb ′ t = M ⊕(wet _wet−1 _..._wet−Ns) over GF (2) where A
_B implies a concatenation of A and B and the sequence length is (Ns + 1). Note that in Figure 6, an input vector wet is reused Ns times and an XOR-gate decoder accepts (Ns + 1) ·Nin bits to yield Nout bits (hence, M⊕ ∈ {0, 1}Nout×((Ns+1)·Nin)). Increasing Ns enables 1) a larger XOR-gate decoder (without increasing Nin) that improves E as demonstrated in Figure 4 and 2) multiple paths from an input vector to multiple output vectors (of various nu) 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 al., 2004).
Balanced encoding Figure 7 illustrates a decoding process when Ns=1, Nin=3, and Nout=8. Each weight vector to be encoded contains a different number of unpruned weights. For wb ′
t at time index t (in Figure 7), a less number of unpruned weights tends to enlarge search space for wet . On the other hand for wb ′
t+1 at time index (t + 1), a large number of unpruned weights would highly restrict search space for wet . Correspondingly, compared to the case when wet is associated with only one w b′ block (i.e., non-sequential encoding with Ns=0), search space for wet can be balanced as more wb ′ blocks of various nu are correlated with wet . Note that as Var[nu] of one block increases, ac-
cording to the central limit theorem, Ns is required to be larger to maintain the balance of encoding capability of each wet . As we demonstrate in the next section, under the variation on nu, even small non-zero Ns can enhance E substantially while increasing Nin (and Nout while Ns=0) improves E only marginally (as described in Figure 4).
Encoding algorithm In the case of a non-sequential encoding scheme, because of one-to-one correspondence between wet and w b′ t through M ⊕, encoding can be performed independently for each block (e.g., for a given masked wbt , we select one matching w b′ t out of all available w b′
t sets by a decoder). Such block-wise encoding, however, is not applicable to a sequential encoding scheme that needs to consider the whole sequence of wb blocks to find an input sequence fed into a decoder. Suppose that we find a particular output sequence matching l blocks after exploring all feasible output sequences provided by a generator and the input sequence (we1,w e 2, ...,w e l ), the time-complexity of encoding would be O(2Nin·l). Fortunately, sequential decoding operations shown in Figure 7 can be models as a hidden Markov model, where each state is represented by concatenating wet , w e t−1, ..., wet−Ns and there are 2 Nin paths for the next state transitions (Viterbi, 1998). Consequently, the time- and space-complexity can be reduced to be O(2Nin·(Ns+1) · l) by dynamic programming that computes the maximum-likelihood sequence in a hidden Markov model (Forney, 1973). For details of our encoding algorithm, the reader is referred to Appendix E.
Lossless compression Any random number generators cannot produce outputs perfectly matching all unpruned weights (i.e., E is 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 to 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 a format representing such correction information in Appendix F where each unmatched weight bit requires Nc bits in the correction format (Nc is around 10 in Appendix E). Taking into account a compression ratio of a generator given as Nout/Nin and additional correction information (using Nc bits per one unmatched weight bit), a binary weight matrix W b ∈ {0, 1}m×n can be compressed into ( NinNoutmn+Nerr) bits when Nerr = Nc×(# of unmatched bits) = Ncmn(1− S)(1− E). Subsequently, memory reduction can be expressed as
Memory Save = 1− ((Nin/Nout)mn+Nerr)/(mn) = 1− (1− S)(1 + (1− E)Nc),
(2)
when Nin/Nout 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 to Appendix G.

heading: 5 EXPERIMENTAL RESULTS
text: In this section, we demonstrate the encoding capability of our proposed sequential encoding techniques 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, Nin is selected to be 8 such that we feed a decoder on a byte-level.
5.1 SYNTHETIC RANDOM DATA (Nin=8)
Setup We generate a random weight 1-D vector of 1M 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
an XOR-gate decoder) basically needs to 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 a particular M⊕ of the highest E. Specifically, for a given set of Nin and Nout, an element of M⊕ ∈ RNout×((Ns+1)·Nin) is randomly assigned to 0 or 1 with equal probability. Then, E 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 8 demonstrates the impact of Ns on E and corresponding memory reduction(%) with various Nout and 1M random bits when Nin=8 and S=0.9. Regardless of Ns, as Nout increases (i.e., the compression ratio (=Nout/Nin=Nout/8) of a decoder increases), the number of encoded bits is reduced while the number of unmatched (error) bits increases. Because of such a trade-off between the number of encoded bits and the number of error bits, there exists a certain Nout that maximizes the memory reduction. Note that compared to a non-sequential encoding (of Ns=0), sequential encoding (even with small Ns) significantly reduces the number of error bits and maintains high E (of almost 100%) until Nout reaches Nin×(1/(1−S))=80. Indeed, memory reduction becomes highest (=89.32%) when Ns is highest and Nout is 80 in Figure 8. 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 Nin×(1/(1−S)) to maximize the memory reduction.
Impact of S on memory reduction Table 1 presents memory reduction using various S. For a certain S in Table 1, as Ns increases, the difference between S and memory reduction decreases. In other words, regardless of S, sequential encoding/decoding principles are crucial for memory reduction to approach S which is the maximum. Increasing S also facilitates memory reduction to approach
S in Table 1 as described in Eq. 2 where increasing S with a constant E enhances memory reduction.
Inverting technique So far, we assumed that a binary weight matrix holds equal amounts of zeros and ones. A few representations such as binary-codingbased quantization (Rastegari et al., 2016; Xu et al., 2018) and signed INT8 (Jacob et al., 2018) would inherently justify such an assumption. However, there exist exceptional representations as well (e.g., FP32). We conduct experiments to find a relationship between the ratio of zeros and E using a random weight vector as shown in Figure 9. E increases if a substantial 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 produce zero outputs. Hence, to improve E (especially when Ns is low), we propose an inverting technique
where an entire binary weight vector is inverted if the ratio of zeros is less than 50%.
5.2 SPARSE TRANSFORMER AND RESNET-50 (Nin=8)
We measure compression capability of our proposed sequential encoding scheme using sparse Transformer (Vaswani et al., 2017) on WMT’14 en-de dataset and ResNet-50 (He et al., 2016) on ImageNet. Those two models1 in FP32 format are pruned by various methods including magnitudebased one (Han et al., 2015), L0 regularization (Louizos et al., 2018), and random pruning (Gale et al.,
1https://github.com/google-research/google-research/tree/master/state_of_sparsity
2019) (also variational dropout (Molchanov et al., 2017) in Appendix H). For the ResNet-50 model (on ImageNet), we also consider signed INT8 format (Jacob et al., 2018). Table 2 presents E and memory reduction when every layer of the Transformer and ResNet-50 is pruned by the same pruning rate S. Both E and memory reduction are significantly improved by increasing Ns. Even compared to the case when inverting technique is applied to non-sequential encoding (Ns=0), we observe that sequential encoding (Ns>0) without inverting yields a lot higher compression capability. Note that the compression capabilities of random pruning and magnitude-based pruning methods are similar in Table 2 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 L0 regularization pruning methods exhibit somewhat lower E that is related to higher coefficients of variation of nu. See Appendix H for additional results.
All in all, our proposed encoding method designed in the context of random pruning is also effective 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 a non-sequential XOR-gate decoder of Ns=0 (Kwon et al., 2020) and a Viterbi-based encoder structure where Nin is limited to be 1 (Ahn et al., 2019).

heading: 6 CONCLUSION
text: 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 as a practical fixed-to-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.

heading: A MEMORY BANDWIDTH WITH FIXED-TO-VARIABLE SPARSITY FORMAT
text: 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 of 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 sparsity representation, since all encoded blocks have the same size, full memory bandwidth is utilized. On the other hand, in the case of fixed-to-variable weight representation, encoded blocks have variable sizes such that memory bandwidth can be wasted. To be more specific, let nw, nb, and S be the number of weights to be encoded, the number of unpruned weights in a block, and sparsity, respectively. Assuming that pruning a weight is a Bernoulli trial, for CSR format, we obtain
E[nb] = nw × (1− S) (3) Var[nb] = nw × S × (1− S). (4)
Thus, the coefficient of variation (or relative standard deviation) is given as√ Var[nb]
E[nb] = 1√ nw
√ S
1− S (5)
, which increases as S increases (0 < S < 1). In other words, for fixed-to-variable sparsity format, more memory bandwidth is wasted as more weights are pruned (as shown in Figure 1). Note that for fixed-to-fixed sparsity format, we have Var[nb] = 0, and thus, the memory bandwidth is not wasted at all.

heading: B PERFORMANCE OF SPARSE MATRIX MULTIPLICATION USING CSR FORMAT
text: 0.5 0.6 0.7 0.8 0.9 1.0 Pruning rate
0.0
1.0
2.0
3.0
4.0
5.0
6.0
E x e cu
ti o n
T im
e (n
o rm
a li ze
d )
Dense
MKL(k=1)
MKL(k=16)
MKL(k=32)
CUDA(k=1)
CUDA(k=16) CUDA(k=32)
Figure S.10: Normalized execution time of multiplying a (2048 × 2048) sparse matrix with a (2048× k) dense matrix.
For inference of NNs, it is known that performance (including latency and throughput) is dominated by matrix multiplications. Figure S.10 presents performance when a (2048× 2048) sparse matrix (of CSR format) is multiplied by a (2048× k) dense matrix when k 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 V100) perform sparse matrix multiplications whose execution times are normalized with respect to corresponding dense matrix multiplications (i.e., using a dense (2048 × 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 is critical for parallel computing to achieve performance gain by pruning.

heading: C RELATED WORKS
text: 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 can be expected
by fine-grained (unstructured) pruning, which prunes individual weights at randomly distributed locations.
To represent sparse weights with a reduced memory footprint, recording unpruned weights associated with (binary) masking information may be the simplest way. However, for such a case, a reconstruction 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 to save memory footprints with fine-grained sparsity, by large, there have been two lines of researches, namely, fixedto-variable and fixed-to-fixed formats. The Compressed Sparse Row (CSR) format is a well-known example of fixed-to-variable formats. Since DeepCompression (Han et al., 2016b) 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., 2016a)) 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; Ahn et al., 2019; Zhou et al., 2018; Kwon et al., 2020; Gale et 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 fully-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 communication, VLSI testing, and so on), Viterbi-based compression (Ahn et al., 2019) and XOR-gates-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 et al., 2020), the encoding efficiency of previous XOR-gates-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-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 a simple heuristic algorithm assuming combinational decoding only (i.e., Ns = 0).

heading: D FUNDAMENTAL LIMITS OF COMPRESSION
text: We are interested in the upper bound of compression ratio that can be analyzed by entropy (while allowing fixed-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 (Morelos-Zaragoza, 2006). To investigate the entropy of pruned weight blocks (and the maximum compression ratio correspondingly), a 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 = − n∑
i=1
pi · log2 pi, (6)
where n is the total number of symbols and pi is the occurrence probability of each symbol.
Symbol assignment We concatenate all of k-th bits of weights into a group and produce nw groups when nw is the number of bits to represent a weight (e.g., nw is 32 for single-precision and 8 for INT8) and 1 ≤ k ≤ nw. Symbol assignment is performed in each group independently without referring to other groups. Suppose that a certain block from one of the groups is given as {0551} and corresponding mask bits (that are shared by all nw groups) are {1001} (0 means masking). By filling up 5 with 0 or 1, {0551} is selected to be assigned to one of 4 symbols (i.e., {0001}, {0011}, {0101} or {0111}) while such a symbol selection decides entropy. In the following two examples (where nb=4), we illustrate the symbol assignment method that minimizes the entropy.
Entropy (nu = 1, e.g., {5550}, {5155}) In this case, every block (of nb=4 and nu=1) can be assigned to either one of two symbols ({0000}, {1111}). Since P (0000) = P (1111) = 0.5, from Eq. 6, H = −(0.5× (−1) + 0.5× (−1)) = 1. Thus, a block of nb=4 and nu=1 can be compressed into 1 bit that indicates one of two symbols. There are many other sets of two symbols to meet H = 1, such as ({0010}, {1101}) and ({1010}, {0101}).
Entropy (nu = 2, e.g., {5015}, {1055}) A set of symbols should meet the following requirement: if we choose random n1 and random n2 (1 ≤ n1, n2 ≤ nb, n1 6= n2) and collect {n1-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 is 5 to represent all blocks of nb=4 and nu=2. An example set of 5 symbols with corresponding occurrence probability to minimize entropy is as follows: P (0000) = 6/24, 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 nb=4 and nu=2) is compressed into 3 bits to represent one of 5 symbols.
For nu=3, the minimum number of symbols is 8 and a block can be compressed into 3 bits. All in all, when nu is fixed across blocks, H can be equal to or slightly higher than nu.

heading: E ENCODING ALGORITHM
text: 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 · 2Nin·(Ns+1)) and space-complexity as O(2Nin·Ns). Thus, even though increasing Nin and Ns enhances E, (Nin ×Ns) is empirically limited to be less than 26 under the constraint of 32GB memory of a single GPU. For each binary weight W bi (0 ≤ i ≤ nw), the function ENCODING generates the encoded vectors wi,(1..l+Ns). XOR-gate decoder (M
⊕) is pre-determined and fixed for inference. Note that the number of encoded vectors (we1..(l+Ns)) is l +Ns, not l. w e 1 and w e 2 are pre-determined as BIN(0) and used for encoding the first binary weight vector.
Algorithm 3: Encoding algorithm when Ns = 2. For a binary matrix W bi , the ENCODING function generates encoded bit vectors. For varied Ns, the number of for-loop statements for it (e.g. line 34-36) and the dimensions of arrays (dp and path) are changed to Ns + 1. Parameters W bi is a binary weight vector to be encoded. MASK is pruning mask information for W bi . dp is (Ns+1)-dimensional array. dp[t][a][b] stores the minimum number of error bits when BIN(a) and BIN(b) are fixed as wet and wet−1. path is (Ns+1)-dimensional array for history. Additional Functions SIZE(W ) returns the number of parameters in W . RESHAPE(ar, shape) returns same data (ar) with specified shape, shape. INIT(ar, init) sets a value init to all elements in ar. BIN(dec) returns a binary value of dec. DEC(bin) returns a decimal value of bin.
Function ERR_NUM(x, y,mask): nErr ← 0 for i← 0 to Nout − 1 do
if mask[i] 6= 0 and x[i] 6= y[i] then nErr ← nErr + 1
return nErr
Function ENCODING(W bi ,MASK): l← SIZE(W bi )/Nout data← RESHAPE(W bi , [l, Nout]) . Slicing mask ← RESHAPE(MASK, [l, Nout]) . Slicing INIT (dp, INF ) . Initialize for starting point dp[Ns][0][0]← 0 and we1,we2 ←BIN(0), BIN(0)
. Find the minimum number of errors for t← Ns+1 to l+Ns do
for it ← 0 to 2Nin−1 do for it−1 ← 0 to 2Nin−1 do
for it−2 ← 0 to 2Nin−1 do out←M⊕(BIN(it−2)_BIN(it−1)_BIN(it)) nerr← ERR_NUM(out, data[t],mask[t]) if dp[t][it][it−1] > nerr + dp[t−1][it−1][it−2] then
dp[t][it][it−1]← nerr + dp[t− 1][it−1][it−2] path[t][it][it−1]← BIN(it−2)
. Find the last two(=Ns) encoded vectors minerr ← INF . for it = 0 to 2Nin − 1 do
for it−1 = 0 to 2Nin − 1 do if minerr > dp[l +Ns][it][it−1] then
minerr ← dp[l +Ns][it][it−1] wel+2,w e l+1 ←BIN(it−1),BIN(it)
. Get encoded bits by following history array for t← l to 2Ns + 1 by −1 do
wet ← path[t+Ns][DEC(wet+2)][DEC(wet+1)] return {we1, we2, ..., wel+Ns}

heading: F MEMORY REDUCTION WITH LOSSLESS COMPRESSION
text: Decoding
Body for Correction
(length = 512)
Reshape
Mask...
Correction
1
idx 1 0
0 1 0 0 ... 1 0 1 0 - Flag bits for each block (k bits)
1 2 3 4 5 k...
1 idx 0idx 3 ... ... 0idxk-3 idx 1 0idxidx 1k-1
- Location information to be flipped
( (log2512+1)x(# of unmatched bits) )
- Encoded bit vectors (Nout x l bits)
Figure S.11: Correction process for lossless compression. After the encoded (compressed) bit vectors are decoded, unmatched bits (that encoding could not target successfully) are flipped by correction information that records the locations of unmatched weight bits.
For lossless compression, the unmatched bits (error bits) should be corrected right after decoding procedures. Since the random number generator produces 0 or 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 a bit position inside a vector. As depicted in Figure S.11, when the block-wise correction is performed while a block size has p-length, the decoded vectors wb ′
1..l are reshaped to w rb′ 1..k(k = dmnp e) and each reshaped vector wrb ′ is corrected by corresponding error bit locations indicating which bit is to be flipped inside a block (of p-length).
The amount of compressed bits can be computed as
Nin · d mn Nout e+ dmn p e+ (log2 p+ 1)× (# of unmatched bits). (7)
The first term is the number of bits of we1..l as the compression results by sequential encoding. The second term is the number of flag bits while each flag bit indicates whether a 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 a p-length block) to be flipped and an additional one bit to specify the end of the streaming error bit locations (i.e., ‘1’ means the following (log2 p) bits contains the next correction information of the same block). Thus, each block of p-length involves (log2 512 + 1)×(# of unmatched bits)) for error bit locations.

heading: G DESIGN COMPLEXITY OF THE PROPOSED COMPRESSION METHOD
text: Encoding Process The time and space complexity of the encoding process (presented in Appendix E with corresponding algorithm description) is 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.
• Time complexity: O(l · 2Nin·(Ns+1)) • Space complexity: O(2Nin·Ns)
Algorithm 3 shown in Appendix E explores all possible 2((l+Ns)·Nin) outputs of an XOR-gate decoder to produce an input vector that can minimize the number of unmatched bits. Note that a partial string of input (of an XOR-gate network) having 2(Nin·(Ns+1)) bits share 2Nin·Ns bits continuously through shift registers. As such, for the time index t+ 1, search space (having the size of 2((t+1+Ns)·Nin)) is overlapped with the search space of the time index t (having the size of 2((t+Ns)·Nin)) as much as 2t·Nin . Accordingly, the time complexity at the time index t + 1 (that optimize the input) is reduced from O(2((t+1+Ns)·Nin)) to O(2((t+1+Ns)·Nin)/2(t·Nin)) = O(2((1+Ns)·Nin)). Then, since we iterate such operation l times, the overall time complexity becomes O(l · 2((1+Ns)·Nin)). To exploit sharing computations between different time indices, we need to store intermediate results having the size of 2Ns×Nin which becomes the space complexity of Algorithm 3.
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, in this section, let us specifically argue hardware design issues of XOR-gate decoders.
• The strongest benefit of employing digital circuits (in the form of ASICs or FPGAs) to implement XOR gates is that all XOR gates can be performed simultaneously (unlike GPUs or CPUs where each core needs to simulate only a few XOR gates). Thus, all XOR operations of our proposed decoder are completed within just one clock cycle.
• Ns (with shift registers) would increase the latency. Throughput, however, maintains to be the same regardless of Ns through pipelining technique which is a 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 Ns, an XOR-gate decoder requires Ns additional clock cycles for the latency. • Since M matrix has the size of Nout ×Nin and an element of M is randomly filled with 0
or 1, the number of XOR gates is (Nout ·Nin/2). Thus, the total number of transistors to design an XOR-gate decoder is (3 ·Nout ·Nin).
• Overall, we can provide full memory bandwidth (based on regular memory access patterns through fixed-to-fixed sparsity formats) while the overall hardware design cost is only marginal.
• While designing DNN inference accelerators is gaining increasing attention, our work can provide a new research direction.

heading: H ADDITIONAL ANALYSIS ON EXPERIMENTS
text: In this section, we provide additional analysis and results for experiments in Section 6.2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
bit index (1:sign bit, 2-9: exponent bits, 10-32: fraction bits)
0.00
0.25
0.50
0.75
1.00 (a) Transformer (FP32, Magnitude-based Pruning)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
bit index (1:sign bit, 2-9: exponent bits, 10-32: fraction bits)
0.00
0.25
0.50
0.75
1.00 (b) ResNet-50 (FP32, Magnitude-based Pruning)
1 2 3 4 5 6 7 8
bit index (1:sign bit, 2-8: magnitude bits)
0.00
0.25
0.50
0.75
1.00 (c) ResNet-50 (INT8, Magnitude-based Pruning)
Figure S.12: Ratio of zeros when weights are divided into k groups when k is the bit-index (i.e., for FP32 number format, k=1 means a sign bit and k=32 means the least significant bit in mantissa). For models, Transformer(FP32), ResNet-50(FP32), and ResNet-50(INT8) are investigated. Most weights consist of similar amounts of 0s and 1s. For the exponent bits of FP32 models, there are 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 to characteristics of DNN models (e.g. regularization such as weight decay). We can gain additional efficiency by adopting the inverting technique for the FP32 models.
Ta bl
e S.
4: C
oe ffi
ci en
to fv
ar ia
tio n
of n u
an d E
of se
le ct
ed la
ye rs
of th
e Tr
an sf
or m
er pr
un ed
by ra
nd om
,m ag
ni tu
de -b
as ed
,L 0
re gu
la ri
za tio
n, or
va ri
at io
na ld
ro po ut pr un in g m et ho d.
N in ,N
o u t
S H
A P
E S
L A
Y E R N A M
E P
R U
N IN G M E T H O
D C
O E
FF E
(% )
N s = 0
N s = 1
N s = 2
(8 ,2
6)
(5 12
,5 12
) 0.
70 0
D E
C 3/
S E
L F _A
T T
/Q R
A N
D O
M 0.
34 1
93 .7
% 98
.7 %
99 .5 % (2 04 8, 51 2) 0. 70 0 D E C 3/ FF N 2 R A N D O M 0. 34 3 93 .7 % 98 .7 % 99 .5 % (5 12 ,5 12 ) 0. 70 0 D E C 3/ S E L F _A T T /Q M A G N IT U D E 0. 39 0 93 .4 % 98 .2 % 99 .0 % (2 04 8, 51 2) 0. 70 0 D E C 3/ FF N 2 M A G N IT U D E 0. 36 3 93 .6 % 98 .5 % 99 .2 % (5 12 ,5 12 ) 0. 69 9 D E C 3/ S E L F _A T T /Q L 0 R E G . 0. 47 6 92 .7 % 97 .6 % 98 .7 % (5 12 ,5 12 ) 0. 69 8 D E C 3/ FF N 2 L 0 R E G . 0. 46 7 92 .7 % 97 .7 % 98 .8 % (5 12 ,5 12 ) 0. 70 5 D E C 5/ S E L F _A T T /K V A R . D R O P O U T 0. 30 3 94 .5 % 99 .1 % 99 .7 % (2 04 8, 51 2) 0. 69 7 D E C 1/ FF N 1 V A R . D R O P O U T 0. 30 9 94 .5 % 99 .1 % 99 .7 %
(8 ,8
0)
(5 12
,5 12
) 0.
90 0
E N
C 2/
S E
L F _A
T T
/O U
T P
U T
R A
N D
O M
0. 34
9 94
.4 %
98 .6
% 99
.3 %
(2 04
8, 51
2) 0.
90 0
D E
C 5/
FF N
2 R
A N
D O
M 0.
31 5
94 .6
% 98
.9 %
99 .5 % (5 12 ,5 12 ) 0. 90 0 E N C 2/ S E L F _A T T /O U T P U T M A G N IT U D E 0. 51 6 92 .5 % 97 .0 % 98 .0 % (2 04 8, 51 2) 0. 90 0 D E C 5/ FF N 2 M A G N IT U D E 0. 36 3 93 .7 % 98 .5 % 99 .1 % (5 12 ,5 12 ) 0. 90 4 E N C 2/ S E L F _A T T /O U T P U T L 0 R E G . 0. 33 1 94 .3 % 98 .7 % 99 .2 % (5 12 ,5 12 ) 0. 89 6 D E C 5/ FF N 2 L 0 R E G . 0. 34 7 94 .5 % 99 .0 % 99 .6 % (5 12 ,5 12 ) 0. 90 6 D E C 2/ S E L F _A T T /V V A R . D R O P O U T 0. 77 0 89 .4 % 93 .6 % 94 .3 % (2 04 8, 51 2) 0. 90 4 D E C 4/ FF N 1 V A R . D R O P O U T 0. 49 9 91 .8 % 96 .4 % 97 .4 %
Ta bl
e S.
5: C
oe ffi
ci en
to fv
ar ia
tio n
of n u
an d E
of se
le ct
ed la
ye rs
of th
e R
es N
et -5
0 pr
un ed
by ra
nd om
,m ag
ni tu
de -b
as ed
,o rv
ar ia
tio na
ld ro
po ut
pr un
in g
m et
ho d.
N in ,N
o u t
S H
A P
E S
L A
Y E R N A M
E P
R U
N IN G M E T H O
D C
O E
FF E
(% )
N s = 0
N s = 1
N s = 2
(8 ,2
6)
(1 ,1
,1 02
4, 25
6) 0.
70 0
G R
O U
P 2_
L A
Y E
R 3_
B N
2 R
A N
D O
M 0.
34 7
94 .2
% 98
.6 %
99 .2 % (1 ,1 ,2 56 ,1 02 4) 0. 70 0 G R O U P 3_ L A Y E R 5_ B N 3 R A N D O M 0. 33 4 94 .3 % 98 .8 % 99 .5 % (1 ,1 ,1 02 4, 25 6) 0. 70 0 G R O U P 2_ L A Y E R 3_ B N 2 M A G N IT U D E 0. 50 5 93 .2 % 98 .0 % 98 .9 % (1 ,1 ,2 56 ,1 02 4) 0. 70 0 G R O U P 3_ L A Y E R 5_ B N 3 M A G N IT U D E 0. 42 8 93 .8 % 98 .4 % 99 .0 % (3 ,3 ,5 12 ,5 12 ) 0. 70 9 G R O U P 2_ L A Y E R 3_ B N 2 V A R . D R O P O U T 0. 40 3 94 .2 % 98 .4 % 99 .1 % (1 ,1 ,2 56 ,1 02 4) 0. 70 6 G R O U P 3_ L A Y E R 5_ B N 3 V A R . D R O P O U T 0. 36 1 94 .4 % 98 .6 % 99 .1 %
(8 ,8
0)
(3 ,3
,2 56
,2 56
) 0.
90 0
G R
O U
P 3_
L A
Y E
R 3_
B N
2 R
A N
D O
M 0.
68 3
92 .3
% 96
.8 %
98 .0 % (1 ,1 ,5 12 ,2 04 8) 0. 90 0 G R O U P 4_ L A Y E R 0_ B N 3 R A N D O M 0. 40 7 92 .9 % 97 .4 % 98 .1 % (3 ,3 ,2 56 ,2 56 ) 0. 90 0 G R O U P 3_ L A Y E R 3_ B N 2 M A G N IT U D E 0. 30 3 94 .6 % 99 .2 % 99 .8 % (1 ,1 ,5 12 ,2 04 8) 0. 90 0 G R O U P 4_ L A Y E R 0_ B N 3 M A G N IT U D E 0. 29 9 94 .6 % 99 .2 % 99 .8 % (3 ,3 ,2 56 ,2 56 ) 0. 91 3 G R O U P 3_ L A Y E R 3_ B N 2 V A R . D R O P O U T 0. 36 6 94 .1 % 98 .3 % 98 .9 % (1 ,1 ,5 12 ,2 04 8) 0. 89 6 G R O U P 4_ L A Y E R 0_ B N 3 V A R . D R O P O U T 0. 32 4 94 .5 % 98 .9 % 99 .6 %
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(a) Ns = 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(b) Ns = 0, Inverted
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100 E (% )
(c) Ns = 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(d) Ns = 1, Inverted
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 bit index (1:sign bit, 2-9: exponent bits, 10-32: fraction bits)
90 92 94 96 98 100
(e) Ns = 2
(a) Transformer (FP32, Magnitude-based Pruning)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(a) Ns = 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(b) Ns = 0, Inverted
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100 E (% )
(c) Ns = 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 90 92 94 96 98 100
(d) Ns = 1, Inverted
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 bit index (1:sign bit, 2-9: exponent bits, 10-32: fraction bits)
90 92 94 96 98 100
(e) Ns = 2
(b) ResNet-50 (FP32, Magnitude-based Pruning)
1 2 3 4 5 6 7 8 90
92
94
96
98
100 (a) Ns = 0
1 2 3 4 5 6 7 8 90
92
94
96
98
100
E (%
)
(b)Ns = 1
1 2 3 4 5 6 7 8
bit index (1:sign bit, 2-8: magnitude bits)
90
92
94
96
98
100 (c)Ns = 2
(c) ResNet-50 (INT8, Magnitude-based Pruning)
Figure S.13: E of the Transformer and ResNet-50 (pruned by S=70%) measured for each bit index (≤ 32 for FP32) individually with various Ns while inverting technique is also considered . It can be observed that the inverting technique improves E for Ns = 0 and Ns = 1. When Ns = 2, the improvement on E is not noticeable.

Review summaries:
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.