Weight pruning has proven to be an effective method in reducing the model size and computation cost while not sacrificing the model accuracy. Conventional sparse matrix formats, however, involve irregular index structures with large storage requirement and sequential reconstruction process, resulting in inefficient use of highly parallel computing resources. Hence, pruning is usually restricted to inference with a batch size of one, for which an efficient parallel matrix-vector multiplication method exists. In this paper, a new class of sparse matrix representation utilizing Viterbi algorithm that has a high, and more importantly, fixed index compression ratio regardless of the pruning rate, is proposed. In this approach, numerous sparse matrix candidates are first generated by the Viterbi encoder, and then the one that aims to minimize the model accuracy degradation is selected by the Viterbi algorithm. The model pruning process based on the proposed Viterbi encoder and Viterbi algorithm is highly parallelizable, and can be implemented efficiently in hardware to achieve low-energy, high-performance index decoding process. Compared with the existing magnitude-based pruning methods, index data storage requirement can be further compressed by 85.2% in MNIST and 83.9% in AlexNet while achieving similar pruning rate. Even compared with the relative index compression technique, our method can still reduce the index storage requirement by 52.7% in MNIST and 35.5% in AlexNet. Deep neural networks (DNNs) demand an increasing number of parameters as the required complexity of tasks and supporting number of training data continue to grow BID2 . Correspondingly, DNN incurs a considerable number of computations and amount of memory footprint, and thus requires high performance parallel computing systems to meet the target response time. As an effort to realize energy-efficient DNN, researchers have suggested various low-cost hardware implementation techniques. Among them, pruning has been actively studied to reduce the redundant connections while not degrading the model accuracy. It has been shown that pruning can achieve 9× to 13× reduction in connections BID9 .After pruning, the remaining parameters are often stored in sparse matrix formats. Different ways of representing indices of non-zero values constitute the different sparse matrix format, and have a significant impact on the level of achievable computational parallelism when a sparse matrix is used as an input operand BID1 . If the format is not properly designed, then the performance of DNN with a sparse matrix can be even lower than the case with dense matrix BID28 . The two most important characteristics of a hardware-friendly sparse matrix format are 1) reducing index storage footprint and 2) parallelizable index decoding process. As a compromise between index size reduction and index decoding complexity, numerous formats have been proposed BID1 . DNN after pruning heavily involves sparse matrix-vector and matrix-matrix multiplications (SpMV and SpMM, respectively). Despite the sparse content, the computation time for SpMM is longer than that of dense matrix multiplication in the modern graphic processing unit (GPU), due to its serialized index decoding process and irregular memory access patterns. For example, the inference latency of AlexNet and VGG16 with SpMM can be increased by 2× to 5× on GPUs or CPUs BID10 . The traditional pruning technique, therefore, is only attractive in the case where SpMV can be utilized (i.e., batch size of 1) BID11 ) BID28 . Therefore, a sparse matrix representation associated with parallelizable dense-matrix reconstruction in a wide range of computing operations is the key to extending the use of pruning. We propose a new DNN-dedicated sparse matrix format and a new pruning method based on errorcorrection coding (ECC) techniques. A unique characteristic of this sparse matrix format is the fixed, yet high (as shown in Section 3) index compression ratio, regardless of the pruning rate. Moreover, sparse-to-dense matrix conversion employing the proposed format becomes a parallel process and is no longer the performance bottleneck. Notice that conventional sparse matrix formats entail at least one column or row index value for each non-zero parameter such that the amount of index data is larger than that of non-zero values. On the other hand, the proposed approach compresses the locations of non-zero values with a convolutional code which is a type of ECC code. Consequently, the size of the sparse matrix index becomes negligible. Conventional pruning approaches first identify the parameter candidates to be pruned, then construct a matrix (often sparse) using formats such as Compressed Sparse Row (CSR) to represent the survived parameters. On the contrary, in the proposed scheme, pruning is performed in a restricted manner since a specific sparse matrix format is first constructed. A DNN-specific Viterbi encoder takes an input pattern and generates a sequence of random-number, where a "1" indicates the parameter had survived, and had been pruned otherwise. Depending on the length of the input pattern, a vast (but limited) number of output patterns (hence candidates of the final sparse matrix representations) are considered. In this case, the input pattern is used as the sparse matrix index. The content of the input pattern, which generates a deterministic output random number sequence, is chosen such that the accuracy degradation is minimized based on a user-defined cost function (more details on Section 2). Both the Viterbi encoder and the algorithm have been shown to be computationally efficient with an inherent parallelizable characteristic, as demonstrated in the digital communication applications BID27 . In this work, we further extend its application and demonstrate how the Viterbi algorithm can be modified to perform energy-efficient DNN pruning.2 PRUNING USING VITERBI-BASED APPROACH Figure 1 illustrates the proposed Viterbi decompressor (VD), which is based on the Viterbi encoder widely used in digital communication. VD has a simple structure consisting only of FlipFlops (FFs) and XOR gates. In this configuration, VD takes one input bit and produces four output bits every clock cycle. Notice that FFs and XOR gates intermingle input bits and generate pseudo random number outputs. Assume that a dense matrix is formed after pruning, as shown in Figure 2 , and an input sequence of {0, 1, 1, 0} is applied to VD through four clock cycles to generate the outputs, where '1' implies that the corresponding parameter has survived. In this case, the overhead in the index for the proposed Viterbi-Compressible Matrix (VCM) format is significantly less than that of CSR. In the VCM format, the input sequence to the VD becomes the index information. This index size is independent of the number of non-zero values and can be determined in advance based on the target index compression ratio 1 . Unlike the CSR format, the available VD-compressible dense matrix representation is limited, meaning that not all possible dense matrix representations after conventional magnitude-based pruning (such as BID9 ) can be reconstructed by VD. Therefore, the pruning method considering VCM may result in a matrix that contains different survived parameters compared to a pruning method using the CSR format. Thus, the key to the success of VCM is to design a VD that allows diversified parameters to survive, and to efficiently search for the optimal VD input sequence that minimizes the accuracy degradation 2 . If the input sequence length and the total output sequence length of a VD are denoted as p and q, respectively, then the index compression ratio can be calculated as q/p. Achieving a high index compression ratio (i.e., q >> p) implies that the possible 2 p VD-compressible dense matrix representations need to be uniformly distributed inside the 2 q space to maximize the likelihood of finding a dense matrix representation that is closely matched to the optimal case. In other words, the goal of VD is to act as a random number generator using the input sequence. It is interesting to note that such an effort has already been studied in ECC design BID24 . Since "random coding" has been introduced by C. Shannon to prove his channel capacity model BID26 , practical ECC techniques with a fixed encoding rate was proposed to simulate random coding with an allowed decoding complexity. We choose the Viterbi encoder, which is the base model of VD, as a controllable random number generator because of its simplicity and flexible design when increasing the number of outputs. The randomness of VD outputs is determined by the number of FFs and the XOR gates configuration. We present the details of the VD design methodology in Appendix A.1.The basic structure of VD is similar to the design introduced in BID17 . VD targeting DNN applications, however, requires the number and/or distribution of 1 (i.e., pruning rate) to be a user-defined parameter, whereas in the typical applications that require random number generation, such as ECC and VLSI testing, the number of 1s and 0s should be approximately the same. In order to control the pruning rate, the VD outputs are connected to binary number comparators. For instance, in Figure 1 , one input of the comparator takes a two-bit number {out2, out1}, while the other input takes a user-defined threshold value (TH c ). If {out2, out1} (or {out4, out3}) is larger than TH c , the comparator produces a "1", and a "0" otherwise. A trade-off occurs between the granularity of the pruning rate and the index compression ratio. If the number of VD outputs, the number of comparator input bits, and the number of comparators (i.e., index compression ratio) are denoted as NUM v , NUM c , and R, respectively, then NUM v = NUM c × R (see Figure 10 ). The proposed index decoding operation utilizing VD is inherently a parallel process with a small hardware overhead. Unlike CSR or other similar formats that employ an irregular index structure, decoding VCM using VD does not incur significant buffer/memory overhead for indices and/or nonzero values, and most importantly, can be performed with a fixed and predictable rate. A fixed index compression ratio is also desirable for efficient memory bandwidth utilization and for applying the tiling technique to further improve the level of parallelism.1 As an example, the structure shown in Figure 1 provides four output bits per one input bit, achieving an index compression ratio of four 2 In the context of magnitude-based pruning, the objective of pruning using the VD is to identify a set of VD input sequences that preserves maximum number of larger value weights The basic idea of our proposed pruning method is to assign a cost function to each pruning case enabled by VD and evaluate all possible (2 p ) pruning cases with a "Branch-and-Cut" algorithm. The pruning case that has the optimal (i.e., lowest) cost function should lead to minimal accuracy degradation. The Viterbi algorithm computes the maximum-likelihood sequence in a hidden Markov model BID7 , and can be utilized as a fast and efficient pruning exploration technique for our pruning method. Pruning using Viterbi algorithm follows the next 3 steps. The first step involves constructing a trellis diagram which is a time-indexed version of a state diagram. A state of VD can be represented using FF values, where the leftmost FF value becomes the least significant bit. If VD has k FFs, the total number of states is 2 k . Hence, VD in Figure 1 has a total of 32 states as shown in FIG1 , where T is the time index. Each possible transition with an input bit (0 or 1) produces multiple corresponding output bits. A trellis diagram holds the entire operations inside VD in a compact fashion. The next step involves computing a cost function for possible transitions using the branch metric and the path metric. The branch metric is expressed as λ i,j t where t is a time index and i is a predecessor state of j. λ i,j t denotes the cost of traversing along a transition from i to j at the time index t. By accumulating the branch metrics and selecting one of two possible transitions reaching the same state at the same time index, the path metric is defined as DISPLAYFORM0 where i1 and i2 are two predecessor states of j. In practice, path metrics can be normalized to avoid overflow. Note that we use max function for the path metric instead of min function in Eq.(1) because the metric values in our method describe a degree of 'reward' rather than 'cost'. For the entire "survived path" selections during the path metric update, the decisions are stored in the memory and the old path metrics can be discarded. The objective of this Viterbi algorithm is to find a path maximizing the accumulation of the branch metrics (λ i,j t ), which is expressed as: DISPLAYFORM1 where DISPLAYFORM2 is the magnitude of a parameter at the m th comparator output and time index t, normalized by the maximum magnitude of all parameters inside the dense matrix to be pruned, and TH p is the pruning threshold value. Intuitively, β i,j,m t favors(discourages) the survival(pruning) of parameters with larger magnitude through the skewed tanh function. Pruning with the Viterbi algorithm is flexible such that different cost function can be assigned to the branch metric, depending on the type of pruning approach, providing the pruning algorithm follows a hidden Markov model BID19 3 . The two constants, S 1 and S 2 , are the scaling factors, and are empirically determined to be 4 , respectively, for our experiments. Note that exploring diversified states (and hence, various pruning cases) is achieved by maintaining approximately 50% of the '1' and '0' distributions for both inputs and outputs of VD BID7 . Consequently, the target pruning rate is mainly controlled by the comparator threshold value, TH c (e.g., if TH c is a 4-bit number and TH c =3, then 25%(= (3 + 1)/2 4 ) is the target pruning rate). TH p is determined by considering the distribution of parameters and the given target pruning rate (e.g., if the parameters follow a Gaussian distribution and the target pruning rate is 68.3%, TH p corresponding to one sigma is recommended).Once the final time index is reached, as the last step of Viterbi pruning, the state with the maximum path metric is chosen, and the previous state is traced by reading the surviving path selection data. We continue this trace-back procedure to the first time index of a trellis diagram. Note that if the initial states of FFs are all 0s, then the number of available states (hence the number of sparse matrix representations in the first few time indices) may be limited. As an alternative, a dummy input sequence having the length equal to the number of FFs 4 in VD can be inserted such that every state of VD is reachable (refer to Figure 11 ). In this case, the compressed input index of the VCM is a combination of the survived dummy sequence and the input sequence. It should be noted that the Viterbi algorithm can be implemented using a dynamic programming technique. The time complexity required to find the best pruning method becomes O(l · 2 f ) where l is the length of the input sequence and f is the number of FFs. As can be seen in Appendix A.1, f is small even with a large number of VD outputs. In this section, the impact of different VD configurations and branch metric selections on model accuracy and the index compression ratio is analyzed. We empirically study the weight distribution after pruning and the sensitivity of accuracy using MNIST. Then, the observations from MNIST are applied to AlexNet to validate the scalability of our proposed method. We perform experiments using the LeNet-5-like convolutional MNIST model 5 . For simplicity, both the minimum Hamming distance and the XOR taps (introduced in Appendix A.1) are fixed to be 4, and NUM c is 4 (i.e., NUM v = 4 × R). These parameters are selected for fast design exploration, and increasing them will enhance randomness of VD output and target pruning rate resolution which are critical to improving pruning rate with minimal accuracy degradation. Number of VD outputs (NUM v ): Immediately after training, we prune the weights with different NUM v for VD. Figure 4 shows the weight distributions after pruning in the FC1 layer with fixed TH c and TH p . Lower NUM v (i.e, lower index compression ratio) leads to sharper pruning around 4 The storage overhead of this dummy input sequence is negligible compared to the index data storage 5 https://github.com/tensorflow/tensorflow/blob/r1.3/tensorflow/examples/tutorials/mnist/mnist deep.py the weight determined by TH p . Hence, NUM v provides a trade-off between accuracy and the index compression ratio. Extensive experiments indicate that for the Conv layer, a low NUM v is desired, while for the FC layer, a wide range of NUM v can lead to minimal accuracy degradation as shown in Figure 5 (magnitude-based pruning is from BID9 ). For MNIST, NUM v =8 for Conv layers and NUM v =40 for FC layers have been chosen to achieve optimal trade-off between the index compression ratio and accuracy. Pruning threshold value (TH p ): Even when the parameters before pruning follow a known distribution (e.g., Gaussian), it may still be an iterative task to search for an optimal TH p that results in the target pruning rate, especially with high NUM v , as evident from Figure 4 . Thus, it is necessary to investigate the sensitivity of accuracy to TH p . In FIG3 , TH p affects distributions of survived weights and pruning rates given the same TH c . Note that if the actual pruning rate differs from the target pruning rate, then VD outputs exhibit skewed supply of '1's or '0's to the comparators and the trellis diagram path exploration is also biased. In contrast, Figure 7 clearly shows that all the retraining processes converge, despite the minor discrepancy between the target and actual pruning rate (target pruning rate is 93.75%).Skip state (Appendix A.2): Up to now, we have only considered the case where one input bit is supplied to VD at every clock cycle. However, if n input bits are provided to VD at every clock cycle, then n − 1 time indices in a trellis diagram are skipped. While this results in a lower index compression ratio, which is defined as R / (skip state + 1), the skip state allows for a more diverse state exploration and improves the pruning quality. As can be seen in FIG4 , a greater number of larger magnitude weights are preserved with increasing number of skip states while fixing both TH p and NUM v . In this work, the default skip state is one. Table 2 : Sparse matrix comparison with MNIST using magnitude-based pruning BID9 and our proposed Viterbi-based pruning. We assume that 16 bits are used for the non-zero values and index for magnitude-based pruning. Branch Metric: For the branch metric, a variety of functions, such as e x and the sigmoid function σ(x), has been investigated, as shown in FIG5 . Among them, the "tanh" function is selected due to its pruning sharpness and low sensitivity to TH p and NUM v .Based on the observations discussed above, we conducted a pruning and retraining process, and compared the test errors of the magnitude-based pruning method BID9 and the proposed Viterbi-based pruning method. For every round of pruning, all the weights, including the ones pruned in the previous run, are considered. (MIN=0, MAX=15 with NUM c =4) used for each pruning round and test error results. Since Conv1 is close to the input nodes, we choose a smaller TH c to reduce the target pruning rate of Conv1. From TAB1 , it is clear that the proposed pruning method successfully maintains accuracy during the entire training process. The final pruning rate and memory requirement for CSR and VCM for each layer are summarized in Table 2 . Notice that the sparse matrix represented using the VCM format leads to a significant memory footprint reduction (by 53.1%) compared to the sparse matrix represented with CSR with a similar pruning rate. This is because VCM's index storage is reduced by 85.2% compared to CSR's index size. Even if the CSR is represented with relative index using 5 bits BID11 , at the expense of increased index decoding complexity, the VCM index size is still smaller by 52.7%6 .In summary, VCM is superior to CSR due to its encoded index format that requires a smaller storage requirement and parallel dense matrix reconstruction process through VD while maintaining a comparable model accuracy. We verified the scalability of the VCM and Viterbi-based pruning methods using the AlexNet model on ImageNet. The number of VD outputs is 50 for both the FC1 and FC2 layers (NUM v =50, NUM c =5, R=10) and 8 for the other layers (NUM v =8, NUM c =4, R=2). Similar to the MNIST results, a higher index compression ratio is set for layers with larger number of weights. Since the skip state is one, the index compression ratio becomes R/2. The minimum Hamming distance and the XOR taps are 4. TAB4 presents the pruning rates and matrix sizes assuming that non-zero weights and CSR index are stored with 16-bit format. The 38.1% reduction in matrix size achieved using VCM is mainly due to the significant reduction in the index storage requirement (83.9%). Compared with the 4-bit relative index scheme introduced in BID11 , the index size of VCM is reduced by 35.5%. The advantage of the index compression ratio of the proposed technique is largely attributed to the VD's limited search space out of all possible encodable index formats, while pruning methods employing traditional sparse matrix formats do not consider such restriction. Despite such limitation, both methods achieve similar top-1 and top-5 classification accuracy with the same retraining time.4 RELATED WORK BID5 demonstrated that most neural networks parameters have significant redundancy. The redundancy increases the system complexity, and causes overfitting with small training dataset. Several approaches have been suggested to prune deep neural networks and increase the sparsity of parameters in order to minimize both the memory overhead and the computation time, and avoid overfitting. Chauvin FORMULA0 and BID12 introduced additional cost biases to the objective function to decay the unimportant parameters. BID16 and BID13 suggested pruning parameters while minimizing the increase of error approximated by Hessian matrix. Optimal Brain Damage (OBD) BID16 restricts the Hessian matrix, forcing it to be diagonal to reduce the computational burden, at the cost of additional performance degradation. Optimal Brain Surgeon (OBS) BID13 ) used a full Hessian matrix with additional computation cost to improve the pruning performance. Han et al. FORMULA0 proposed pruning of deep neural networks by removing parameters based on the magnitude of their absolute values and then iteratively retraining the pruned network. A 9× and 13× pruning rate was achieved for AlexNet and VGG-16, respectively, without loss of accuracy on ImageNet dataset. A follow-up paper compressed the pruned network further with weight sharing and Huffman coding BID11 . Although an impressive compression rate is achieved by these suggested methods, the irregular sparsity of the survived parameters and the associated complicated index decoding process prevent common hardware such as GPUs from achieving noticeable speed-up improvement. Alternatively, BID10 designed a dedicated hardware accelerator to circumvent this problem. Recently, several papers suggested iterative hardware-efficient pruning methods to realize a faster inference speed and smaller model size. BID23 suggested iterative pruning on a feature-map level based on a heuristic approach to evaluate the importance of parameters. This paper, which shares a similar idea as that of OBS, uses first-degree Taylor polynomial to estimate the importance of each parameter with reduced computational burden. Since the method prunes feature maps rather than each parameter, a sparse matrix format is not required at the cost of a lower pruning rate. suggested pruning all the convolution kernels together with corresponding feature maps in CNN. Similar to BID23 , this coarse-level pruning avoids the use of a sparse matrix format, at the expense of a lower pruning rate. BID25 introduced a high-performance sparse convolution algorithm, where the sparse convolution was formulated as sparse-matrix-dense-matrix multiplication with the dense matrix generated on the fly. The paper shows that this method can improve the inference speed of pruned networks with moderate sparsity, and can prune each parameter independently, leading to a better pruning rate. However, in the paper, the results were only demonstrated on CPUs; it was not shown whether the proposed method can also be applied to throughput-oriented hardware such as GPUs. BID0 proposed a scheme to generate a masking matrix using linear-feedback shift registers (LFSRs) to randomly prune some of the synaptic weights connections. Even though the hardware structure for pruning can be simplified, it is not possible to selectively prune connections to improve the pruning quality. In addition, the scheme can only be applied to the fully-connected layer, not to the convolution layer. BID15 explained Gaussian Dropout as a special case of Bayesian regularization. Unlike Gaussian Dropout which considers dropout rates as a hyperparameter, Variational Dropout theoretically allows training dropout rates layer-wise, or even weight-wise. However, the paper did not include any experimental result on weight-wise variational dropout. BID21 extended BID15 and showed the working case of weight-wise Variational Dropout. BID21 suggested the use of this characteristic of Variational Dropout to prune deep neural networks. By pruning out weights with a high dropout rate, high sparsity on a deep neural network was achieved for the CIFAR-10 classification task. BID22 and BID20 suggested pruning deep neural networks in a structured format with new Bayesian models. The papers could prune deep neural networks either neuron-wise or channelwise, keeping the weight matrices in dense format. Both papers showed state-of-the-art sparsity on deep neural networks for the CIFAR-10 classification task. In multiple works, attempts have been made to reduce the redundancy with popular lossy compression methods. BID6 applies low rank approximations to pre-trained weights. BID8 uses vector quantization to compress deep convolution neural networks. BID4 suggests HashedNets, which applies hashing tricks to reduce the model sizes. Iandola et al. FORMULA0 achieves AlexNet-level accuracy using 50x fewer parameters with SqueezeNet, which is comprised of custom convolution filters called Fire modules. These methods are orthogonal to the network pruning, and can be combined to achieve further model compression. For example, SqueezeNet combined with Deep Compression BID11 ) achieves 510× compression ratio compared to the original AlexNet. Many other ECC techniques have been reported that can also be potentially used to search for sparse matrix forms with high index compression BID24 . Efficient parallel ECC decoding and encoding implementation have also been proposed and realized BID29 . We believe that efforts to combine existing and new ECC techniques/algorithms with DNN pruning methods create a new dimension in realizing energy-efficient and high-performance DNN. Even though the proposed approach is best for dedicated ASIC or FPGA, the inherent parallel characteristics of VD and the Viterbi algorithm can also be utilized in GPUs through the construction of new kernels and libraries. We have not considered quantization of non-zero weight values or entropy-related coding design in this paper. In the future, such considerations can be embedded into the branch metric or path metric equations. We proposed a new DNN-dedicated sparse matrix format and pruning method using the Viterbi encoder structure and Viterbi algorithm. Unlike previous methods, we first consider only limited choices of pruning results, all of which have the advantage of a significant index compression ratio by our proposed index decompressing structures. One particular pruning result is selected from the limited pruning solution space based on the Viterbi algorithm with user-defined branch metric equations that aim to minimize the accuracy degradation. As a result, our proposed sparse matrix, VCM, shows noticeable index storage reduction even compared with the relative index scheme. Fixed index compression ratio and inherently parallel reconstruction scheme allows a wide range of applications, such as SpMM, since sparse matrices can be converted into dense matrices efficiently. A APPENDIX In Figure 1 , each VD output is generated by a series of 2-input XOR gates which accept input bits from either input of VD or FF outputs. Hence, there are 6 possible input candidates in total for XOR gates and each candidate is called an XOR tap. Using input as x 0 and n th FF output (from the left) as x n , out2 can be represented as a polynomial of x 5 + x 3 + x or equivalently, a vector [101010] . By combining such vectors of all 4 outputs, we can construct a VD Matrix to represent VD (of Figure 1) The number of 1s (i.e., the XOR taps) is 3 in every row of VD Matrix and the Hamming distance 7 of any pair of two rows is 4. Increasing the number of XOR taps and minimum Hamming distance in VD Matrix improves the randomness of VD outputs BID17 . Given the number of XOR taps, the minimum Hamming distance, and the number of VD outputs, VD Matrix can be generated as Algorithm 1.Algorithm 1: VD Matrix generation input : number of outputs N , number of XOR taps t, minimum Hamming distance h output: VD Matrix S i = 0, S = φ ; while (number of vectors of S) < N do i++ ; a = binary representation of i ; if (number of 1s' of a) == t then isValid = true ; for (j=0; j <number of vectors of S; j++) do d = Hamming distance between S(j) and a; if d < h then isValid = false ; end end if (isValid == true) then put a in S; end end end TAB5 shows the minimum number of FFs generated by Algorithm 1, given the number of XOR taps, the minimum Hamming distance, and the number of VD outputs. Note that the number of VD outputs increases exponentially, while the number of FFs increases linearly. Thus, the hardware resource for implementing VD is not expensive even with a high index compression ratio. Note that the number of XOR taps for pruning should always be an even number (otherwise, the Viterbi algorithm chooses a trivial input sequence of all '1's to ensure make all the weights survive to maximize the path metric. In Figure 10 , as further bits are consumed for the two inputs of the comparators (NUM c bits) in order to enhance controllable target pruning rates (i.e., sparsity in R outputs) resolution, the number of VD outputs (NUM v ) needs to be increased. 7 Hamming distance between two vectors is the number of positions where two values are different Figure 10: Index decompressing using VD and comparators to control the sparsity. A comparator threshold value TH c can have a range of 0 to 2 NUMc − 1. Accuracy degradation can be reduced by increasing the number of states to be explored in trellis diagram, primarily because of the increased search space dimension. In Figure 11 , inserting dummy inputs as an initial input sequence increases the number of available states from which we start index encoding with weight parameters (i.e., the number of available states increases from 1 to 4 with 2 dummy input bits). The maximum size of the dummy inputs is the number of FFs and all the dummy paths exhibit the same preference with the same branch metrics. The size of the dummy inputs is negligible if the number of FFs in VD is much smaller than the number of weight matrix elements divided by R.In addition to the dummy input sequence, the skip state, which is defined as the number of times the time index in the trellis diagram is skipped, can also lead to reduced accuracy degradation. Similar to the concept of the dummy input, the skip state increases the number of available states in the trellis diagram search. FIG0 describes a case of (Skip State=1) where at every even-number time index, the output of VD is discarded. If the branch metrics are set to 0, following Eq. (1), the Viterbi algorithm will select the paths that lead to an increased number of states with a higher path metric value. In the case of magnitude-based pruning, this implies that a larger magnitude weight has a higher chance of being preserved. In the case of the k skip states, VD outputs are discarded for k consecutive time indices. The entire length of the time index is increased by (k + 1) times and the index compression ratio is reduced by (k + 1) times. Assume that the normalized magnitudes of parameters before pruning are given as {0.1, 0.2, 0.6, 1.0} at a certain time index and TH p is 0.3. We calculate the branch met- On the other hand, if we use x instead of tanh(x), then the branch metrics with V 1 and V 2 are −600 and 600, respectively. Compared with x, tanh assigns greater importance to parameters with higher magnitude. Note that in this example, tanh has been chosen in the context of the magnitude-based pruning method, and the branch metric equations can be made differently depending on the underlying pruning principle. We test our proposed VCM and Viterbi-based pruning method with highly sparse DNNs by combining our method with the Variational dropout-based pruning method BID21 . The LeNet-300-100 and LeNet-5-Caffe architectures 8 on the MNIST dataset are used in the test. The Viterbi-based pruning based in Eq. (2) is additionally performed to obtain VCM data, after pruning weights and neurons using the Variational dropout method BID21 as shown in TAB6 . The main VD parameters for each layer are also presented in TAB6 . The minimum Hamming distance and XOR taps are 4. TAB7 and 7 describe the pruning rate and the memory footprint comparisons for each layer. The storage requirement for VCM is reduced by 22.6 % and 21.0 %, respectively, compared with CSR, due to the reduction in index size (63.0 % and 53.6 %, respectively). Almost the same classification accuracy is achieved with a short retraining time in both LeNet-300-100 and LeNet-5-Caffe. Note that this result demonstrates that the proposed Viterbi-based techniques can be combined with existing pruning methods to extract VCM formats even without modifying Eq. (2).
We present a new pruning method and sparse matrix format to enable high index compression ratio and parallel index decoding process. The authors use Viterbi encoding to dramatically compress the sparse matrix index of a pruned network, reducing one of the main memory overheads and speeding up inference in the parallel setting.