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