D COMPRESSION: COMPRESSING DEEP NEURAL ETWORKS …

1 Published as a conference paper at ICLR 2016 DEEPCOMPRESSION: COMPRESSINGDEEPNEURALNETWORKS WITHPRUNING, TRAINEDQUANTIZATIONANDHUFFMANCODINGSong HanStanford University, Stanford, CA 94305, MaoTsinghua University, Beijing, 100084, J. DallyStanford University, Stanford, CA 94305, USANVIDIA, Santa Clara, CA 95050, networks are both computationally intensive and memory intensive, makingthem difficult to deploy on embedded systems with limited hardware resources. Toaddress this limitation, we introduce deep compression , a three stage pipeline:pruning, trained quantization and Huffman coding , that work together to reducethe storage requirement of NEURAL networks by35 to49 without affecting theiraccuracy. Our method first prunes the network by learning only the importantconnections.

2 Next, we quantize the weights to enforce weight sharing, finally, weapply Huffman coding . After the first two steps we retrain the network to finetune the remaining connections and the quantized centroids. Pruning, reduces thenumber of connections by9 to13 ; Quantization then reduces the number ofbits that represent each connection from 32 to 5. On the ImageNet dataset, ourmethod reduced the storage required by AlexNet by35 , from 240MB to ,without loss of accuracy. Our method reduced the size of VGG-16 by49 from552MB to , again with no loss of accuracy. This allows fitting the modelinto on-chip SRAM cache rather than off-chip DRAM memory. Our compressionmethod also facilitates the use of complex NEURAL networks in mobile applicationswhere application size and download bandwidth are constrained.

3 Benchmarked onCPU, GPU and mobile GPU, compressed network has3 to4 layerwise speedupand3 to7 better energy NEURAL networks have evolved to the state-of-the-art technique for computer vision tasks(Krizhevsky et al., 2012)(Simonyan & Zisserman, 2014). Though these NEURAL networks are verypowerful, the large number of weights consumes considerable storage and memory bandwidth. Forexample, the AlexNet Caffemodel is over 200MB, and the VGG-16 Caffemodel is over 500MB(BVLC). This makes it difficult to deploy deep NEURAL networks on mobile , for many mobile-first companies such as Baidu and Facebook, various apps are updated viadifferent app stores, and they are very sensitive to the size of the binary files. For example, AppStore has the restriction apps above 100 MB will not download until you connect to Wi-Fi.

4 As aresult, a feature that increases the binary size by 100MB will receive much more scrutiny than onethat increases it by 10MB. Although having deep NEURAL networks running on mobile has many great1 [ ] 15 Feb 2016 Published as a conference paper at ICLR 2016 Train ConnectivityPrune ConnectionsTrain WeightsCluster the WeightsGenerate Code BookQuantize the Weights with Code BookRetrain Code BookPruning: less number of weightsQuantization: less bits per weightoriginal size 9x-13x reduction 27x-31x reduction same accuracy same accuracyoriginal networkEncode WeightsEncode IndexHuffman Encoding 35x-49x reduction same accuracyFigure 1: The three stage compression pipeline: pruning, quantization and Huffman coding . Pruningreduces the number of weights by10 , while quantization further improves the compression rate:between27 and31.

5 Huffman coding gives more compression : between35 and49 . Thecompression rate already included the meta-data for sparse representation. The compression schemedoesn t incur any accuracy such as better privacy, less network bandwidth and real time processing, the large storageoverhead prevents deep NEURAL networks from being incorporated into mobile second issue is energy consumption. Running large NEURAL networks require a lot of memorybandwidth to fetch the weights and a lot of computation to do dot products which in turn consumesconsiderable energy. Mobile devices are battery constrained, making power hungry applications suchas deep NEURAL networks hard to consumption is dominated by memory access. Under 45nm CMOS technology, a 32 bitfloating point add , a 32bit SRAM cache access takes5pJ, while a 32bit DRAM memory access takes640pJ, which is 3 orders of magnitude of an add operation.

6 Large networksdo not fit in on-chip storage and hence require the more costly DRAM accesses. Running a 1 billionconnection NEURAL network, for example, at 20fps would require(20Hz)(1G)(640pJ) = DRAM access - well beyond the power envelope of a typical mobile goal is to reduce the storage and energy required to run inference on such large networks so theycan be deployed on mobile devices. To achieve this goal, we present deep compression : a three-stage pipeline (Figure 1) to reduce the storage required by NEURAL network in a manner that preservesthe original accuracy. First, we prune the networking by removing the redundant connections, keepingonly the most informative connections. Next, the weights are quantized so that multiple connectionsshare the same weight, thus only the codebook (effective weights) and the indices need to be , we apply Huffman coding to take advantage of the biased distribution of effective main insight is that, pruning and trained quantization are able to compress the network withoutinterfering each other, thus lead to surprisingly high compression rate.

7 It makes the required storageso small (a few megabytes) that all weights can be cached on chip instead of going to off-chip DRAM which is energy consuming. Based on deep compression , the EIE hardware accelerator Han et al.(2016) was later proposed that works on the compressed model, achieving significant speedup andenergy efficiency pruning has been widely studied to compress CNN models. In early work, network pruningproved to be a valid way to reduce the network complexity and over-fitting (LeCun et al., 1989;Hanson & Pratt, 1989; Hassibi et al., 1993; Str om, 1997). Recently Han et al. (2015) pruned state-of-the-art CNN models with no loss of accuracy. We build on top of that approach. As shown onthe left side of Figure 1, we start by learning the connectivity via normal network training.

8 Next, weprune the small-weight connections: all connections with weights below a threshold are removedfrom the network. Finally, we retrain the network to learn the final weights for the remaining sparseconnections. Pruning reduced the number of parameters by9 and13 for AlexNet and as a conference paper at ICLR 2016 Figure 2: Representing the matrix sparsity with relative index. Padding filler zero to prevent weights (32 bit float)centroidsgradient3021110303103122c luster index (2 bit uint) byfine-tuned :lr0:2:3:Figure 3: Weight sharing by scalar quantization (top) and centroids fine-tuning (bottom).We store the sparse structure that results from pruning using compressed sparse row (CSR) orcompressed sparse column (CSC) format, which requires2a+n+ 1numbers, whereais the numberof non-zero elements andnis the number of rows or compress further, we store the index difference instead of the absolute position, and encode thisdifference in 8 bits for conv layer and 5 bits for fc layer.

9 When we need an index difference largerthan the bound, we the zero padding solution shown in Figure 2: in case when the difference exceeds8, the largest 3-bit (as an example) unsigned number, we add a filler ANDWEIGHTSHARINGN etwork quantization and weight sharing further compresses the pruned network by reducing thenumber of bits required to represent each weight. We limit the number of effective weights we need tostore by having multiple connections share the same weight, and then fine-tune those shared sharing is illustrated in Figure 3. Suppose we have a layer that has 4 input neurons and 4output neurons, the weight is a4 4matrix. On the top left is the4 4weight matrix, and on thebottom left is the4 4gradient matrix. The weights are quantized to 4 bins (denoted with 4 colors),all the weights in the same bin share the same value, thus for each weight, we then need to store onlya small index into a table of shared weights.

10 During update, all the gradients are grouped by the colorand summed together, multiplied by the learning rate and subtracted from the shared centroids fromlast iteration. For pruned AlexNet, we are able to quantize to 8-bits (256 shared weights) for eachCONV layers, and 5-bits (32 shared weights) for each FC layer without any loss of calculate the compression rate, givenkclusters, we only needlog2(k)bits to encode the index. Ingeneral, for a network withnconnections and each connection is represented withbbits, constrainingthe connections to have onlykshared weights will result in a compression rate of:r=nbnlog2(k) +kb(1)For example, Figure 3 shows the weights of a single layer NEURAL network with four input units andfour output units. There are4 4 = 16weights originally but there are only4shared weights: similarweights are grouped together to share the same value.