PermDNN: Efficient Compressed DNN Architecture with Permuted Diagonal Matrices
^††thanks: *Chunhua Deng and Siyu Liao contribute equally to the paper. ^††thanks: +Chunhua Deng, Siyu Liao, Yi Xie and Bo Yuan are now with Rutgers University.

Similar to EIE, PermDNN is a customized DNN architecture that targets for FC layers. Specifically, PermDNN accelerates the sparse matrix-vector multiplication ($M\times V$), which is the kernel computation of any FC layers. We justify the importance of FC layer with the following three arguments.

First, FC layer has a wide spectrum of application scenarios. As summarized in Table I, besides being used in convolutional neural network (CNN) for computer vision tasks, FC layer is also the dominant layer in many other types of DNNs (e.g., recurrent neural network (RNN¹¹1In this paper the FC in RNN specifically means the component weight matrices in RNN.) and multi-layer perceptrons (MLP) for speech recognition and natural language processing tasks. Therefore, optimizing FC layer can universally benefit a full spectrum of AI tasks.

Second, real-world industrial needs call for efficient FC layer-targeted DNN architecture. As revealed in Google’s seminal TPU paper [25], more than 95% workload in Google’s datacenters are processed by those FC layer-centered DNNs, such as RNNs and MLPs. Therefore, [25] called for more research efforts on FC layers, which is currently far less active than the effort for convolutional (CONV) layers.

Finally, optimized FC layer-targeted architecture can improve the overall performance of CONV layer-centered models (e.g., CNNs). As analyzed in [20], forcing a CONV layer-targeted architecture to execute FC layers will cause noticeable performance degradation. We believe that, to realize an efficient architecture for CNNs with both CONV and FC layers, a specialized design that optimizes for FC layer is a preferable strategy to maximize hardware performance.

Due to the large memory requirement and the inherent redundancy, FC layers are usually compressed with network sparsification, such as heuristic pruning [15] and conducting certain regularization [18]. The downside of the approach is that the unstructured sparse models are not friendly to be implemented in DNN hardware accelerators.

First, the structure of their generated sparse DNNs is usually highly irregular [15] or only exhibits weak regularity [18]. It incurs significant space/computation overhead due to indexing the irregular sparse weight matrices. For instance, in EIE, each weight requires 4-bit virtual weight tag to represent its actual value and additional 4 bits to record its relative position in the entire weight matrix. Therefore, the overall storage cost for one weight is actually 8 bits instead of 4 bits, significantly limiting the achievable performance.

Second, the compression ratio of DNN sparsification is typically heuristic. This is because the inherent process of weight/neuron pruning or regularization-caused sparsification is usually uncontrollable and unpredictable. Consequently, in the scenario of compression effect is pre-defined, precisely controlling the compression ratio to satisfy the design specification becomes challenging.

Moreover, the existing DNN sparsification approaches introduce large training overhead. Operating on the pre-trained dense model, weight/neuron pruning and retraining are performed iteratively to ensure the original accuracy of the dense model can also be achieved by the sparse model. Clearly, the process is time-consuming, — sometimes it may even take longer time to re-train sparse models than the dense models. For instance, as reported in [26], in order to get a fair compression rate on a pre-trained AlexNet model, it takes 4800K and 700K iterations by using the pruning methods in [15] and [26], respectively, while training this pre-trained model only takes 450K iterations.

An alternative approach to achieve network compression is to directly represent the network with structured matrices. As an example, CirCNN utilizes the mathematical property of circulant matrix to compress DNN models that can be efficiently implemented in hardware. While avoiding the irregularity, CirCNN suffers from a different set of drawbacks. First, it requires high-cost arithmetic operation. The training and inference algorithms of CirCNN are based on FFT computation, which is inherently involved with complex multiplication and addition. Unfortunately, arithmetic operations on complex numbers incur much higher cost than their counterparts on real numbers. For instance, one complex multiplication requires four real multiplications and two real additions.

Moreover, it lacks flexibility on compression ratio. The compression ratio of CirCNN is determined by the size of component circulant matrix. However, since this size also determines the length of FFT, in order to facilitate FFT hardware design that mostly uses $2^{t}$-point FFT²²2 non-$2^{t}$-point FFT has much more complex hardware than $2^{t}$-point FFT., the compression ratio of each layer of CirCNN has to be selected among the values of $2^{t}$. Obviously, such restriction severely limits the potential applications of CirCNN.

Finally, it loses the opportunity of utilizing input sparsity. As discussed in [14][21], utilizing the dynamic input sparsity is an important technique to reduce the power consumption and computational time of DNN hardware. However, since CirCNN processes the input vector in the frequency domain, its original abundant sparsity in time domain is completely lost. It prevents CirCNN from utilizing the important input sparsity for performance improvement.

To address the drawbacks of the current sparsification-based and structured matrix-based methods, we propose PermDNN, a new structured sparse DNN representation, shown in Fig. 1(b). Specifically, we enforce that the weight matrices of the DNN models consist of multiple permuted diagonal sub-matrices, where all the non-zero entries of the permuted diagonal matrices locate in the diagonals or permuted diagonals. In general, the $m$-by-$n$ weight matrix of one layer of PermDNN contains $mn/p^{2}$ $p$-by-$p$ permuted diagonal sub-matrices³³3When $m$ or $n$ is not divided by $p$, zeroes are padded. It will not cause extra overhead since padded zeroes are not involved in computation/storage.. As it will be shown later, this type of block-permuted diagonal weight matrix exhibits strong spatial structure that brings significant reduction in space cost and computational cost.

Based on the representation of PermDNN, we develop the computation procedures of forward and backward propagation that are the key parts for inference and training process.

In general, we assume that the weight matrix of a fully-connected layer of PermDNN is an $m$-by-$n$ block-permuted diagonal matrix $\mathbf{W}\in\mathbb{R}^{m\times n}$. Here $\mathbf{W}$ consists of multiple $p$-by-$p$ permuted diagonal sub-matrices. Considering there are $(m/p)\times(n/p)$ sub-matrices in total and each has its own permutation parameter, we index all the sub-matrices from 0 to $(m/p)\times(n/p)-1$ and denote $k_{l}$ as the value of permutation parameter for the $l$-th permuted diagonal sub-matrix. Then, for arbitrary entry $w_{ij}$ of $\mathbf{W}$, its value can be represented as:

where $c\equiv i\mod p$, $d\equiv j\mod p$ and $l=(i/p)\times(n/p)+(j/p)$. Here $\mathbf{q}=(q_{0},q_{1},\dots,q_{mn/p-1})$ is the vector that contains all the non-zero entries of $\mathbf{W}$.

Forward Propagation for Inference. Recall that the forward propagation during inference phase for FC layer is performed as $\mathbf{y}=\psi(\mathbf{a})=\psi(\textbf{Wx})$⁴⁴4Bias is combined with W for simplicity., where $\psi(\cdot)$ is the activation function and $\mathbf{a}=\mathbf{Wx}=(a_{1},a_{2},\dots,a_{m})^{T}$. In addition, $\mathbf{x}=(x_{1},x_{2},\dots,x_{n})^{T}$ and $\mathbf{y}=(y_{1},y_{2},\dots,y_{m})^{T}$ are the input and output vectors of FC layer, respectively. Accordingly, when $\mathbf{W}$ is the trained block-permuted diagonal weight matrix with entries that are represented by Eqn. (1), the calculation of $a_{i}$, as the key computation in the forward propagation, can now be simplified as $a_{i}=\sum_{g=0}^{n/p-1}w_{ij}x_{j}$, where $j\equiv(i+k_{l})\mod p+gp$ and $l=g+(i/p)\times(n/p)$. Notice that here for weight storage, only the $mn/p$ -length vector $\mathbf{q}$ that contains all the non-zero entries of W needs to be stored in the inference phase. Also, the calculation of $a_{i}$ is significantly simplified from the original computation as $a_{i}=\sum_{g=0}^{n-1}w_{ij}x_{j}$.

Backward Propagation for Training. When the FC layer is imposed with permuted diagonal structure, we need to ensure the FC layer of PermDNN always exhibits permuted diagonal structure in each iteration of training phase. Recall that the forward propagation for FC layer is performed as $\mathbf{y}=\psi(\mathbf{a})$ where $\mathbf{a}=(a_{1},a_{2},\dots,a_{m})^{T}$. Then, the gradient calculation, which is the key step of the backward propagation, is performed as $\frac{\partial J}{\partial w_{ij}}=x_{j}\frac{\partial J}{\partial a_{i}}$, where $J$ is the loss function [27] of the neural network. Notice that according to the principle of backpropagation [27], $x_{i}$ in the current layer will be backward propagated to the previous layer as $a_{i}$. Therefore, together with the above equation, the weight updating rule for the FC layer of PermDNN can be derived as:

where $i\equiv(j+p-k_{l})\mod p+gp$, $l=gn/p+j/p$ and $\epsilon$ is the learning rate. Here in Eqn. (2) the calculation of $\frac{\partial J}{\partial a_{i}}$ is aided with the computation in Eqn. (3) since each $x_{i}$ in the current layer will be backward propagated to the previous layer as $a_{i}$. Notice that here the weight update scheme described in Eqns. (2) (3) theoretically guarantees the trained sparse network always exhibits block-permuted diagonal structure and hence provides attractive end-to-end training solution.

Forward Propagation for Inference on CONV Layer. The idea of imposing permuted diagonal structure on the weight matrix of FC layer can be further generalized and applied to the weight tensor of CONV layer. Recall that the weight tensor of a CONV layer is a 4D tensor that can be viewed as a ”macro” matrix with each entry being a filter kernel; therefore, as illustrated in Fig. 2, the permuted diagonal structure can be imposed on the input channel and output channel dimensions of the weight tensor. Then, similar to the case for FC layer, the forward propagation for inference on CONV layer using permuted diagonal matrix can be described as follows:

where $\mathcal{X}\in\mathbb{R}^{c_{0}\times w_{0}\times h_{0}}$, $\mathcal{Y}\in\mathbb{R}^{c_{2}\times w_{2}\times h_{2}}$, $\mathcal{F}\in\mathbb{R}^{c_{0}\times c_{2}\times w_{1}\times h_{1}}$ represent the input, output and weight tensors of convolutional layer, respectively. Here $w_{i}$ and $h_{i}$ for $i$=0,1,2 are the width and height of the input, kernel and output tensor, respectively. $c_{0}$ and $c_{2}$ are the numbers of input channels and output channels. In addition, $j\equiv(i+k_{l})\mod p+gp$ and $l=g+(i/p)\times(n/p)$.

Backward Propagation for Training on CONV Layer. Similar to the FC layer, in order to ensure the convolutional layer of PermDNN always exhibits the permuted diagonal structure during the training phase, the corresponding weight updating procedure needs to be re-designed. Following the similar steps of deriving training procedure for FC layer, the weight update rule in the back propagation on CONV layer can be described as follows:

where $i=(j+p-k_{l})\mod p+gp$ and $l=gn/p+j/p$. Notice that here in Eqn. 5 the calculation of $\frac{\partial J}{\partial\mathcal{Y}(i,x,y)}$ is aided with the computation in Eqn. 6 since each $\mathcal{X}(j,x,y)$ in the current layer will be backward propagated to the previous layer as $\mathcal{Y}(j,x,y)$. Again, the weight update scheme described in Eqns. (5) (6) theoretically guarantees the trained sparse network always exhibits block-permuted diagonal structure.

By leveraging the forward and backward propagation schemes in Eqns. (2)-(6), the PermDNN models can be trained from scratch and tested. Table II - Table V show the task performance and compression ratio of different PermDNN models on different types of datasets. Notice that for one FC/CONV layer with block size $p$ for its permuted diagonal (PD) weight matrix/tensor, the compression ratio for that layer is $p$. The details of the experimental setting are described as follows:

• •

  AlexNet [28]: The block sizes ($p$) for the permuted diagonal weight matrices of three FC layers (FC6, FC7 and FC8) are set as different values (10, 10 and 4) for different FC layers.

• •

  Stanford Neural Machine Translation (NMT) [29]: This is a stacked LSTM model containing 4 LSTMs with 8 FC weight matrices for each LSTM. In the experiment the value of $p$ for all the FC layers is set as 8.

• •

  ResNet-20 [11]: In this experiment for the group of CONV layers without 1x1 filter kernel, the value of $p$ is set as 2. For the group of CONV layers with 1x1 filter kernel, $p$ is set as 1.

• •

  Wide ResNet-48 [12]: The widening parameter of this model is 8. For the group of CONV layers without 1x1 filter kernel, the value of $p$ is set as 4. For the group of CONV layers with 1x1 filter kernel, $p$ is set as 1.

• •

  Selection of Permutation value ($k_{l}$): $k_{l}$ can be selected via either natural indexing or random indexing. Our simulation results show no difference between task performance for these two setting methods. Table II - Table V are based on natural indexing. For instance, for a 4-by-16 block-permuted diagonal weight matrix with $p=4$, $k_{0}\sim k_{3}$ is set as $0\sim 3$.

Table II - Table V show that imposing permuted diagonal structure to DNN models enables significant reduction in the weight storage requirement for FC or CONV layers. Meanwhile, the corresponding task performance, in terms of test accuracy (for computer vision) or BLEU scores [30] (for language translation), are still retained as the same or only exhibits negligible degradation. In short, PermDNN models can achieve high compression ratios in network size and strong spatial network structure, and simultaneously, preserve high task performance. It makes the corresponding hardware-friendly architecture (Section IV) very attractive.

In CirCNN the universal approximation property of block-circulant matrix-based neural network was given to theoretically prove the effectiveness of using circulant matrices. In this work we discover that the PermDNN also exhibits the universal approximation property, thereby making the rigorous foundation for our proposed permuted diagonal structure-imposing method. The details of the proof will be provided in an individual technical report and this subsection gives a brief outline of the proof as follows. First, we prove that the ”connectedness” of PermDNN, – that means, thanks to the unique permuted diagonal structure of each block, when $k_{l}$ is not identical for all permuted diagonal matrices, the sparse connections between adjacent block-permuted diagonal layers do not block away information from any neuron in the previous layer. Based on this interesting property, we further prove that the function space achieved by the block-permuted diagonal networks is dense. Finally, with the Hahn-Banach Theorem we prove that there always exists a block-permuted diagonal neural network that can closely approximate any target continuous function defined on a compact region with any small approximation error, thereby showing the universal approximation property of block-permuted diagonal networks. Besides, we also derive that the error bound of this approximation error is in the order of $O(1/n)$, where $n$ is the number of model parameters. Consequently, the existence of universal approximation property of PermDNN theoretically guarantees its effectiveness on different DNN types and applications.

Besides training from scratch, the permuted diagonal matrix-based network model can also be obtained from a pre-trained dense model. Fig. 3 illustrates the corresponding procedure, which consists of two steps: permuted diagonal approximation and re-training/fine-tuning. First, the original dense weight matrices/tensors need to be converted to permuted diagonal matrices/tensors via permuted diagonal approximation. The mechanism of permuted diagonal approximation is to convert a non-permuted diagonal matrix/tensor to a permuted diagonal format by only keeping the entries in the desired permuted diagonal positions. Mathematically, such approximation is the optimal approximation in term of $l_{2}$ norm measurement on the approximation error. After that, the converted model already exhibits permuted diagonal structure and then can be further re-trained/fine-tuned by using Eqns. (2)-(6) to finally obtain a high-accuracy permuted diagonal network model. Such two-step generating approach is applied to all types of pre-trained models and can lead to high accuracy. For instance, for pre-trained dense LeNet-5 model on MNIST dataset, with $p=4$ for CONV layer and $p=100$ for FC layer, the finally converted permuted-diagonal network after re-training achieves 99.06% test accuracy and overall $40\times$ compression ratio without using quantization.

Compared to the existing network sparsification approaches, the proposed PermDNN enjoys several attractive advantages:

First, PermDNN is a hardware-friendly model. As illustrated in Fig. 4, due to the inherent regular structure of permuted diagonal matrix, the position of each non-zero entry can now be calculated using very simple modulo operation⁶⁶6As shown in Fig. 9, modulo circuit is simple by using LSB bits., thereby completely eliminating the needs of storing the indices of entries. From the perspective of hardware design, this elimination means that the permuted diagonal matrix-based PermDNN completely avoids the huge space/computation overhead incurred by the complicated weight indexing/addressing in the state-of-the-art sparse DNN accelerator (e.g. EIE), and hence achieves significant reduction in the space requirement and computational cost for DNN implementations.

Second, PermDNN provides controllable and adjustable compression and acceleration schemes. The reductions in the model sizes and number of arithmetic operations are no longer heuristic based and unpredictable. Instead it can now be precisely and deterministically controlled by adjusting the value of $p$. This further provides great benefits to explore the design space exploring the tradeoff between hardware performance and test accuracy.

Finally, PermDNN enables direct end-to-end training while preserving high accuracy. Since the structure of sparse weight matrices of PermDNN can now be pre-determined by the model designers at the initialization stage of training, with our training algorithm that preserves this fixed structure, the entire structured sparse network can be trained from scratch, completely avoiding the increasing complexity incurred by the extra iterative pruning and/or re-training process in the conventional unstructured sparse DNN training schemes.

While PermDNN and CirDNN are both based on the structured matrices, PermDNN does not suffer from the drawbacks of CirDNN. Table VI compares the two methods.

Most importantly, PermDNN uses simpler arithmetic computation. Different from complex number computation-based CirDNN, the computation of PermDNN is purely based on real numbers, thereby requiring significantly lower arithmetic cost than CirDNN with the same workload and same compression ratio.

Second, PermDNN allows compression ratio to be flexibly adjusted. Different from CirDNN, the computation in PermDNN does not have any restrictions on the size of component permuted diagonal matrix. Therefore, the hardware architecture of PermDNN can support different compression ratios based on the needs. This makes PermDNN more attractive for a wide range of applications.

Finally, the fundamental distinction is that PermDNN can fully utilize input sparsity. Since the computation of PermDNN is in the time domain, the important input sparsity can still be leveraged by PermDNN to further reduce computational cost and power consumption. Because sparsity of input vectors widely exists in numerous applications, this benefit greatly expands the advantage of PermDNN over CirDNN.

In general, the proposed computing engine is a scalable array of processing elements (PEs). Each PE performs the forward propagation on part of the weight matrix. Different PEs perform independent and parallel computations to maximize the processing throughput. Fig. 5 illustrates this partition scheme on an 8-by-8 block-permuted diagonal weight matrix with $p=4$. We can see that the 4-by-4 permuted diagonal sub-weight matrices belonging to the same block row are processed by the same PE⁷⁷7In general, each PE can be in charge of multiple permuted diagonal matrices along column direction.. To support such arrangement, the non-zero entries of these sub-matrices are stored in each PE’s associated SRAM. Therefore, the entire weight matrix of the FC layer is stored in a distributed manner across multiple SRAM banks to enable parallel processing of multiple PEs.

Besides, in order to fully utilize the potential dynamic sparsity in the input vector $\mathbf{x}$ (also the activation vector output $\mathbf{y}$ from previous layer), the entire PermDNN adopts column-wise processing style. Specifically, as illustrated in Fig. 5, in each clock cycle all PEs perform the multiplications between $x_{i}$, the non-zero entry of $\mathbf{x}$, and $\mathbf{w_{i}}$, the corresponding column vector of weight matrix $\mathbf{W}$. The products are then accumulated for updating the intermediate values of the corresponding entries in the output vector $\mathbf{a}$. After all the non-zero entries of current $\mathbf{w_{i}}$ have been multiplied with $x_{i}$, the PEs will then move on to perform the multiplications between $x_{j}$ and $\mathbf{w_{j}}$, where $x_{j}$ is the next non-zero entry that follows $x_{i}$ in the $\mathbf{x}$. After all the $x_{j}$ and $\mathbf{w_{j}}$ have been processed, the final calculated values of all the entries of output vector $\mathbf{a}$ are available simultaneously. Obviously, by adopting this column-wise processing scheme, the computations that are involved with zero entries of $\mathbf{x}$ can be completely skipped, thereby leading to significant saving in energy consumption when there exists non-negligible sparsity in $\mathbf{x}$.

Based on the data mapping and processing scheme, the overall architecture of PermDNN computing engine is shown in Fig. 6. The entire design consists of an array of $N_{PE}$ PEs that perform the kernel $M\times V$ operations and the non-linear activation operations. After all the $y_{i}$’s, the entries of output activation vector $\mathbf{y}$ for the current FC layer, have been calculated and stored in the PEs, they are then written to the activation SRAM. The writing operation is performed in a group-writing manner: the entire activation SRAM is partitioned into $N_{ACTMB}$ banks, where each SRAM bank is in charge of the $y_{i}$’s from $N_{ACC}/N_{PE}$ PEs. In each clock cycle, among all the PEs that belong to the same SRAM bank, one of them outputs $W_{ACTM}/q$ activation values $y_{i}$’s to its corresponding SRAM bank, where $W_{ACTM}$ and $q$ are the width of activation SRAM and the bit-width of $y_{i}$, respectively. Consider there are in total $N_{ACTMB}W_{ACTM}/q$ $y_{i}$’s that are simultaneously written to the activation SRAM in one cycle. An activation routing network is designed to ensure each $y_{i}$ is correctly written to the target position in the activation SRAM.

In the reading phase of activation SRAM, as described in Section IV-A, each time only one non-zero activation value $x_{i}$ is fetched and broadcasted to all the PEs. To achieve that, with the help of control signals from main controller, an activation selector is designed to select the correct $x_{i}$ from multiple activation SRAM banks. After the examination from a zero-detector, the non-zero $x_{i}$ is then sent to an activation FIFO for its broadcast to PE arrays. The purpose of using this activation FIFO is to build up a backlog for the non-zero $x_{i}$’s, thereby ensuring that the PEs can always receive their required $x_{i}$ for the current computation in time.

Fig. 7 shows the inner architecture of the PE. Here, each PE is equipped with its own SRAM that stores the non-zero entries of part of block-permuted diagonal weight matrices. Similar to EIE, a weight lookup table (LUT) is located in the PE to support weight sharing strategy [15] if needed. In that case, the weight SRAM of the PE stores the virtual weight tag (or so-called clustered class) that each actual weight has. After being decoded by the weight LUT, $N_{MUL}$ actual weights are multiplied with the input $x_{i}$ and the products are sent to a group of accumulators in each clock cycle. Because each PE is equipped with $N_{ACC}$ accumulators, which corresponds to $N_{ACC}$ rows of weight matrix that one PE is in charge of, $N_{MUL}$ accumulation selectors are designed to ensure those products are routed to the target accumulators. Specifically, as it will be elaborated in detail later, the permutation parameters of the corresponding permuted diagonal weight sub-matrices are used to enable very low-cost selection. For each selector, it is associated with its own accumulator bank, and each accumulator bank contains $g=N_{ACC}/N_{MUL}$ accumulators that always contain a target accumulator for the input product. After all PEs finish their processing for the current column of weight matrix, the calculated $a_{i}$’s in the accumulators are sent to the activation units (ActU) to produce $y_{i}$’s. Here, each activation unit can be reconfigured to act as either Rectified Linear Unit (ReLU) or hypertangent function ($tanh(\cdot)$) unit to support the needs of different applications.

Weight SRAM. To reduce the read/write energy consumption for the weight SRAM, we further break the weight SRAM bank of each PE into multiple weight SRAM sub-banks. By adopting this strategy, in each cycle only one weight SRAM sub-bank is selected while the others are disabled to save energy. Accordingly, in order to achieve the full utilization of all the multipliers in most cases, the width of all the weight SRAM sub-banks is selected to ensure that each row of every SRAM sub-bank at least contains $N_{MUL}$ weight entries.

Besides, to accommodate the column-wise processing scheme and the block-permuted diagonal structure of weight matrix, the non-zero weight is specially arranged in the weight SRAM of each PE. Fig. 8 illustrates the data allocation in one weight SRAM sub-bank for one block-permuted diagonal weight matrix. Here, each row of the weight SRAM sub-bank stores the non-zero entries of the same column of the weight matrix. By adopting this transpose-like data layout, each row access to the weight SRAM sub-bank can fetch the required data for column-wise data processing. Because each column of one permuted diagonal sub-matrix only has one non-zero entry, each PE always receives and processes the same number of non-zero weights, thereby completely eliminating the risk of load imbalance that prior work [14] may suffer from.

Accumulation Selector & Bank. Since the number of accumulators ($N_{ACC}$) is typically much larger than that of multipliers ($N_{MUL}$) in each PE, accumulation selectors are required to route the outputs of multipliers to the target accumulators. As shown in Fig. 9, an accumulation selector consists of two parts, an index calculator and an array of reconfigurable comparators and multiplexers. The index calculator is used to calculate the correct row index of the non-zero entry in the permuted diagonal sub-matrix that the current PE is in charge of. Specifically, due to the unique structure of permuted diagonal matrix, such calculation is essentially the modulo operation between the sum of permutation value and column index and the size of permuted diagonal matrix $p$; and hence it can be easily implemented using a circuit consisting of $b$-width adder, subtractor and comparator, where $b=ceil(\log_{2}p)$ and $ceil(\cdot)$ is the ceiling function. After the row index is calculated, among the bank of accumulators, the target accumulator is first identified by the array of comparators and multiplexers, and then it is updated using the output of the multiplier.

Permutation SRAM. The permutation values (PermVs) sent to accumulation selectors are provided by permutation SRAM. Different from weight SRAM and activation SRAM, in each PE the permutation SRAM consists of a single bank instead of multiple partitions. In addition, each row of permutation SRAM contains multiple permutation values to support the computation in different accumulation selectors. Given that the bit-width of permutation value is typically small (as $\log_{2}p$), the width of permutation SRAM is not very large.

Because the value of $p$ and network size vary with models, the PE of PermDNN is designed to provide flexibility for different needs. In general, designing a flexible PE involves the considerations of several factors: $N_{ACC}$, the number of accumulators in each PE; $N_{MUL}$, the number of multipliers in each PE; $N_{ROWPE}=m/N_{PE}$, the number of rows that each PE is in charge of; and $p$. In the following, we describe the computation scheme of PE in three cases.

Case 1. $N_{ROWPE}\geq pN_{MUL}$ and $N_{ACC}\geq N_{ROWPE}$. In this case, since $N_{ACC}\geq N_{ROWPE}$, each PE has sufficient registers to store all the calculated $y_{i}$’s which it is in charge of. Meanwhile, consider in each cycle one PE processes $N_{MUL}$ size-$p$ permuted diagonal sub-matrices and identifies $N_{MUL}$ non-zero entries among $pN_{MUL}$ rows. Therefore, only $pN_{MUL}$ comparators of one PE are activated to identify the required row indices of non-zero entries. This means that in each accumulation selector of Fig. 9 only $p$ out of $N_{ACC}/N_{MUL}$ comparators and the corresponding multiplexers are used in each cycle. Therefore, if we denote $N_{ROWPE}=k(pN_{MUL})+d$, where $d\equiv N_{ROWPE}\mod k(pN_{MUL})$, then at the $i$-th cycle of every $k$ cycles, only $(p(i-1)+1)$-th to $(pi)$-th comparators and multiplexers in Fig. 9 are activated to identify the target register that should be updated. In other words, different $p$ copies of comparators, selectors and accumulators of Fig. 9 are activated sequentially. Notice that because $N_{ROWPE}=k(pN_{MUL})+d$ and $N_{ACC}\geq N_{ROWPE}$, PEs always have enough hardware resource to continuously process the current column of weight matrix, and it takes $k$ (for $d=0$) or $(k+1)$ (for $d>0$) cycles to fully process one column. For instance, assume we have 2 PEs with $N_{MUL}=1$ and $N_{ACC}=4$ to process an 8-by-8 weight matrix with $p=2$. Then as shown in Fig. 10(a), it takes two cycles to process one column and such column-wise processing is continuous.

Case 2. $N_{ROWPE}\geq pN_{MUL}$ and $N_{ACC}<N_{ROWPE}$. In this case, since $N_{ROWPE}=k(pN_{MUL})+d$, there must exist an integer $f\leq k$ that satisfies $f(pN_{MUL})\leq N_{ACC}<(f+1)(pN_{MUL})$. Therefore, after $f$ cycles of sequential activation described in Case 1, at the $(f+1)$-th cycle the inactivated accumulation selectors and accumulators in Fig. 9 are not sufficient for future processing. Accordingly, as illustrated in Fig. 10(b) with $p=3$, the overall computation scheme needs to be changed for this case: all the other columns need to be first partially processed to calculate part of $y_{i}$’s. Then the accumulators that were once allocated for the previously calculated $y_{i}$’s are released and used to perform the rest unfinished computation. Such procedure may need to be repeated for many times if $f$ is much smaller than $k$.

Case 3. $N_{ROWPE}<pN_{MUL}$. This is a very rare case since the number of PEs should be properly determined to ensure each multiplier is in charge of at least one permuted diagonal sub-matrix. When such case occurs, it means that $p$ is very large (a very sparse model) and some of the PEs become redundant. To solve this problem, we need to change the original single column-processing scheme: different PEs can now process multiple columns simultaneously. Consequently, this strategy leads to two benefits: 1) increase the overall throughput; and 2) equivalently improve $N_{ROWPE}$ for each column processing, and thereby transforming this case to the aforementioned Case 1 or 2.

Simulation and CAD Tools. We developed a cycle-accurate bit-accurate simulator to model the functional behavior of PermDNN architecture. This simulator also serves as the golden reference for the correctness of Verilog implementation. After verifying the RTL model via validating its outputs against the outputs of the simulator, we synthesized our design using Synopsis Design Compiler with CMOS 28nm library. Here the switching activity was extracted from simulation and we annotated the toggle rate to the gate-level netlist. For place and route, we used Synopsis IC compiler to generate layout (see Fig. 11). The power consumption was estimated using Prime-Time PX. Notice that the area and power consumption of SRAM part, including weight SRAM, activation SRAM and permutation SRAM, were estimated and reported by Cacti.

Benchmarks. Our evaluation uses a set of PermDNN models with the FC layer described in Section III-D. Specifically, similar to EIE, we evaluate the FC layers of these compressed sparse models individually, and the layers with different sizes are viewed as different workloads. Accordingly, the information of six benchmark layers, including the sizes, constant weight sparsity ratio and statistically calculated activation sparsity ratio⁸⁸8Lower sparsity ratio means more sparsity., are listed in Table VII.

Design Configuration. Table VIII lists the design configuration parameters for PE and the overall PermDNN computing engine. Here one PE is equipped with eight 16-bit multipliers and 128 24-bit accumulators. In addition, each PE is also designed to contain $16\times 32$ bit$\times 2048=128$KB weight SRAM and 48bit$\times 2048=12$KB permutation SRAM. It should be noted that the sizes of SRAM are selected by using the “over-design” strategy to ensure the architecture can support a wide range of applications. For instance, by using 4-bit weight sharing strategy a 32-PE PermDNN computing engine can store a compressed layer with 8M parameters, which has the double size of the famous large-size compressed VGG FC6 layer [32]. Similarly, the activation SRAM is also designed with large capacity to facilitate the execution on very large models. As illustrated in Table VIII, the activation SRAM in this design has $8\times 64$bit$\times 2048=128$KB, which corresponds to a 16-bit 64K-length vector. Such large size is usually sufficient for the FC layers in most practical models.

Hardware Performance. Table IX shows the power and area breakdowns for one PE and overall PermDNN computing engine. It is seen that each PE occupies 0.271mm² and consumes 21.874mW. For the overall 32-PE computing engine, it occupies 8.85mm² and consumes 703.4mW, where the PE array is the most resource-consuming part (99.5% power and 97.9% area).

Regarding the throughput, being equipped with 32 PEs running at 1.2GHz, the PermDNN computing engine can achieve 614.4GOPS for a compressed DNN model. For the equivalent processing power on dense model, since it varies with different compression ratios, we adopt a pessimistic conversion scheme of assuming 8$\times$ weight sparsity and 3$\times$ activation sparsity. Consequently, the equivalent application throughput of PermDNN achieves 14.74TOPS. Notice that our selected conversion scheme is quite conservative. For instance, EIE adopts conversion scheme of assuming 10$\times$ weight sparsity and 3$\times$ input sparsity, which is more optimistic than ours.

In this subsection we compare PermDNN with two most relevant compressed DNN-oriented architectures: EIE and CirCNN. The reasons for selecting these two works as reference are: 1) similar to PermDNN, EIE is a type of FC layer-targeted DNN architecture and it is the state-of-the-art design in this category; 2) similar to PermDNN, CirCNN also imposes structure to the weight matrix of DNN to gain improved hardware performance.

Comparison with EIE. Table X summarizes the hardware parameters and performance of EIE and PermDNN. For fair comparison, our design adopts the weight sharing strategy and quantization scheme that are the same to EIE’s configuration. Also, because EIE uses a different technology node from ours (45nm vs 28nm), we adopt the scaling strategy used in EIE to project EIE to the same 28nm technology.

Fig. 12 compares the hardware performance of EIE and PermDNN on executing three FC layers of AlexNet¹²¹²12They are the benchmark layers that both EIE and PermDNN evaluate. in terms of speedup, area efficiency and energy efficiency. It can be seen that compared with the projected EIE using 28nm, PermDNN achieves $3.3\times\sim 4.8\times$ higher throughout, $5.9\times\sim 8.5\times$ better area efficiency and $2.8\times\sim 4.0\times$ better energy efficiency on different benchmark layers. As analyzed in Section III-G, such improvement is mainly due to the elimination of unnecessary storage for weight index, inconvenient address calculation and load imbalance.

Comparison with CirCNN. Table XI summarizes the hardware performance of CirCNN and PermDNN. Again, for fair comparison we project CirCNN to the same 28nm technology. Notice that because CirCNN reported synthesis results, here in Table XI the listed performance characteristics of PermDNN are also from synthesis reports. Meanwhile, because CirCNN only provides power and throughput information, we compare our PermDNN and CirCNN on overall throughput (TOPS) and energy efficiency (TOPS/W). Table XI shows that PermDNN achieves 11.51$\times$ higher throughput and 3.89$\times$ better energy efficiency.

As discussed in Section III-H, compared with CirCNN the PermDNN enjoys the benefits of utilizing input sparsity and real-number arithmetic computation. Because the architecture of PermDNN and CirCNN are quite different, and the two implementations have their individual design configurations (e.g., compression ratios, size of SRAM, number of multipliers etc.), the contributions of these two advantages to the overall performance improvement are analyzed roughly as follows: 1) Because the utilization of dynamic input sparsity can bring linear reduction in computational cost, if all the other factors that affect throughput and energy efficiency, including compression ratio, clock frequency, number of multipliers and power, were the same for PermDNN and CirCNN designs, $3\times$ input sparsity of PermDNN would enable about $3\times$ increase of throughput and energy efficiency; 2) For the simplicity of real number arithmetic computation, recall that a complex multiplication consists of 4 real multiplications and 2 real additions. Also, notice that performing inference on the same-size compressed weight matrix (e.g., $p$-by-$p$), the permuted diagonal matrix-based approach needs $p$ real multiplications, while circulant matrix-based method requires $p$ complex multiplications in element-wise multiplication phase plus $plogp$ constant complex multiplications in FFT/IFFT phases, Therefore, when the compression ratio is the same, the use of real-number arithmetic computation can roughly bring about $4\times$ reduction in computational cost, which can translate to a significant improvement in hardware performance.

As the size of weight matrix of FC layer grows, it is easy to scale up PermDNN by adding more PEs. In general, thanks to block-permuted diagonal matrix’s unique characteristic of even distribution of non-zero entries along row and column directions, PermDNN enjoys strong scalability since the load imbalance problem [14] that challenges other sparse DNN accelerators does not exist for PermDNN at all. Fig. 13 shows the speedup of PermDNN architecture using different numbers of PEs. We see that our design achieves very good scalability on all benchmarks.