diff options
Diffstat (limited to 'Paper/paper.tex')
| -rw-r--r-- | Paper/paper.tex | 592 |
1 files changed, 592 insertions, 0 deletions
diff --git a/Paper/paper.tex b/Paper/paper.tex new file mode 100644 index 0000000..32e1bf3 --- /dev/null +++ b/Paper/paper.tex @@ -0,0 +1,592 @@ +\documentclass[conference]{IEEEtran} +%\IEEEoverridecommandlockouts +% The preceding line is only needed to identify funding in the first footnote. If that is unneeded, please comment it out. +\usepackage{cite} +\usepackage{amsmath,amssymb,amsfonts} +\usepackage{algorithmic} +\usepackage{graphicx} +\usepackage{textcomp} +\usepackage{xcolor} +\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em + T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}} + +\begin{document} + +\nocite{*} + +\title{EIE: Efficient Inference Engine on Compressed Deep Neural Networks} +\author{\IEEEauthorblockN{Leonard Kugis} +\IEEEauthorblockA{\textit{Abteilung Entwurf Integrierter Systeme} \\ +\textit{Technische Universität Braunschweig}\\ +Braunschweig, Germany \\ +l.kugis@tu-bs.de} +} + +\maketitle + +\begin{abstract} +With an increased use of deep neural networks instead of conventional algorithms for classification tasks, +there is demand for implementation in various environments with different constraints. +Especially high demand for inference in the embedded real time domain has emerged, with its hard +constraints on latency, energy use and storage. +To satisfy these constraints, dedicated hardware architectures need to be implemented to maximize +the efficiency, such as the \emph{Efficient Inference Engine} (\emph{EIE}). +It utilizes various compression techniques to compress existing deep neural network models +and implements a specialized hardware architecture to handle the compressed models +as efficient as possible. +\end{abstract} + +\begin{IEEEkeywords} +deep neural networks, compression, inference, weights, sparsity +\end{IEEEkeywords} + +\section{Introduction} + +This paper gives an overview over different compression methods for \emph{Deep Neural Networks} +(section~\ref{sec:compression}), after discussing the metrices used to measure +inference engines (section~\ref{sec:metrices}) +and shows how they are applied in an actual hardware architecture: the \emph{Efficient Inference Engine} (\emph{EIE}) (section~\ref{sec:implementation}). + +\subsection{Deep Neural Networks} + +\emph{Deep Neural Networks} (\emph{DNNs}) consist of different types of layers, namely +\emph{Convolutional Layers} and \emph{Fully Connected Layers}. +While for common DNNs (e.g. AlexNet \cite{10.1145/3065386}) convolutional layers make +up more than 90\% of computational cost \cite{9082126}, fully connected layers take +up over 90\% of the storage \cite{Cheng_2015_ICCV}. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/fcn}} + \caption{Fully connected layer} + \label{fcn} +\end{figure} + +Fig.~\ref{fcn} shows a fully connected layer in a DNN. +Each fully connected layer consists of an input vector $a$, an output vector $b$ and +a weight matrix $W$. +Essentially, the weight matrix gets multiplied by the input vector, +so that each combination of the entries $W_{ij}$ get multiplied by the component $a_j$, +on which an activation function $f$ is applied, forming a component in the output vector $b_i$. + +\begin{align}\label{mac} + b_i = f(\sum\limits_{j=0}^{n} W_{ij} a_j) +\end{align} + +Equ.~\ref{mac} shows this principle formulated. The process of multiplying the weights +with the components of the input vector is referred to as \emph{Multiply-Accumulate-Operation} (\emph{MAC}). +This is the essential operation in DNNs and therefore in focus for optimization. + +Input and output vectors are considered as dynamic data, while +weights and eventual parameters of the activation function are considered as static data. + +\section{Performance metrices}\label{sec:metrices} + +When it comes to optimization of inference architectures for DNNs, there are four major categories of +metrices to optimize on: + +\begin{itemize} + \item Throughput + \item Latency + \item Model size + \item Energy use +\end{itemize} + +\emph{Throughput}. Throughput measures how much data can be processed by the network in a fixed time. + +\emph{Latency}. Latency measures how long it takes for a fixed amount of data to be processed by the network from start to finish. + +\emph{Model size}. Model size indicates the amount of storage required to store the model. + +\emph{Energy use}. Energy use measures how much energy is needed to process a fixed amount of data. + +\subsection{Memory}\label{sec:memory} + +Since the 1980s there is a more and more evolving gap between memory latency and processing speed. +Recent CPUs are magnitudes faster than their memory counterparts \cite{carvalho2002gap}. +This is problematic, because in general the CPU has to wait during each memory access for the data +to arrive in order to process it further. While this waiting time can be optimized with +efficient pipelining, the principal still remains. +The memory accesses for the weights of the DNN make up the biggest part of energy consumption of the +hardware accelerator, and correlate also with latency and throughput \cite{DBLP:journals/corr/SzeCESZ16}. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/memory_latency}} + \caption{Memory hierarchy and energy cost of hierarchy levels \cite{DBLP:journals/corr/SzeCESZ16}} + \label{memory_latency} +\end{figure} + +Fig.~\ref{memory_latency} shows the energy consumption of each layer of a typical hardware accelerator +consisting of an external \emph{Dynamic Random Access Memory} (\emph{DRAM}) to store the model, +internal buffers (typically \emph{Static Random Access Memory} (\emph{SRAM})) and processing engines (\emph{PEs}). +Memory accesses to DRAM are 200x more costly than register accesses, and 33x more costly than accesses to +the SRAM-buffer. This results in the demand of storing most of the model in SRAM technology. +Because such on-chip SRAM capacity is limited, models must be compressed in order to fit onto the SRAM. + +\subsection{Existing DNNs} + +To put the model sizes of DNNs into perspective, Table~\ref{tab_dnn} gives an overview of +the number of parameters and storage sizes in 32-bit floating point representation. + +\begin{table}[htbp] +\caption{Model sizes of different DNN models} +\begin{center} +\begin{tabular}{|c|c|c|} +\hline +\textbf{DNN} & \textbf{Number of} & \textbf{Size in} \\ +& \textbf{Parameters} & \textbf{32-bit float} \\ +\hline +AlexNet \cite{choudhary2020comprehensive} & 61 M & 240 MB \\ +\hline +VGG-16 \cite{choudhary2020comprehensive} & 138 M & 512 MB \\ +\hline +LeNet-5 (caffe) \cite{NIPS2015_ae0eb3ee} & 431 K & 1.724 MB \\ +\hline +NeuralTalk (zoo) \cite{das2015neuraltalk} & 90 M & 360 MB \\ +\hline +\end{tabular} +\label{tab_dnn} +\end{center} +\end{table} + +These are common models to perform benchmarks on hardware accelerators +and compression algorithms. They will be used for evaluation between different +platforms later. + +\section{Compression}\label{sec:compression} + +Different compression algorithms exist for DNN models. Not only storage size benefits +from model compression, most methods also optimize the amount of MACs (Equ.~\ref{mac}) that need to be +performed. It does so by creating a sparse weight matrix from the original weight matrix. +Multiplication and accumulation with $0$-valued weights can be skipped and therefore it is desired +to have as many $0$s as weights as possible. + +\subsection{Basis projection} + +Basis projection utilizes the fact that row- and column-vectors of the weight matrices can be +represented by the linear combination of its basis vectors. +In common training algorithms, weights (the weight matrices) are trained directly and use the canonical basis vectors. +But this might not be the optimal basis vectors, resulting in the most amount of zeros. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/basis_projection_png}} + \caption{Basis projection and resulting weight distribution \cite{DBLP:journals/corr/SuleimanZS16}} + \label{basis_projection} +\end{figure} + +Fig.~\ref{basis_projection} depicts the method of basis projection and the resulting distributions of +weight values. It can be shown that the column vectors can be represented by projected vectors $\alpha$ +and a-priory known basis vectors $S_d$. As the basis projection is a reversible operation, the reverse +can later be applied to receive the actual results. + +Using this method, experimental results show, that the number of zero-valued weights can be increased from +$7$\% to $56$\% ($8.0$x increase) \cite{DBLP:journals/corr/SuleimanZS16}. +Further experiments have shown that, when used along with other compression methods such as pruning and +weight quantization, $3.6$x compression factor can be archieved. This results in $10$x less MAC operations and +$5$x reduction in power consumption \cite{DBLP:journals/corr/SuleimanZS16}. + +\subsection{Pruning} + +The key idea behind pruning is the removal of unimportant weights from the weight matrices, which have little or +no influence on the output accuracy. This influence is also referred to as \emph{sensitivity}. +For pruning, a common procedure has established \cite{Han2015DeepCC}: + +\begin{enumerate} + \item Train weights + \item Prune network + \item Retrain network + \item Go to 2. or abort if criterion is met +\end{enumerate} + +Under the assumption that there is an already trained network, weights (connections), neurons and convolutional filters +get removed from the network based on their output sensitivity. However, convolutional filters are not in this scope, +since they are not part of the fully connected layers of a DNN. Therefore, the main focus +is on weight/connection based pruning. + +Pruned weights are simply set to value $0$ and not considered in the retraining process. +This way, they can be handled efficiently by the hardware architecture, by just skipping the +MAC-operation for these weights. Neurons are pruned by just deleting the corresponding +row/column of the weight matrix. + +For weight/connection pruning, there are different methods on how to remove the weights and what the +sensitivity is measured on. They can be classified in three different main classes: + +\begin{itemize} + \item Magnitude threshold based pruning \cite{9253578} + \item Optimal Brain Damage \cite{NIPS1989_6c9882bb} / Optimal Brain Surgeon \cite{NIPS1992_303ed4c6} + \item Biased weight decay \cite{NIPS1988_1c9ac015} +\end{itemize} + +\subsubsection{Magnitude threshold based pruning} + +Magnitude threshold based pruning methods remove weights solely based on their magnitude. +The following simple rule is applied for the weight removal: + +\begin{align}\label{mtbp} + &\text{Remove weights $W_{ij}$ for which} \nonumber \\ + &\left| W_{ij} \right| < \vartheta \\ + &\vartheta := \text{Threshold} \nonumber +\end{align} + +Weights $W_{ij}$ with magnitude below the threshold $\vartheta$ are removed (set to $0$). +This assumes that values with low magnitude have a low impact on the accuracy +of the network and/or the objective function. +This is generally not always the case and therefore not the optimal solution. +However, experiments have shown model size decreases of $33$\% for LeNet and up +to $33$\% for DeepSpeech2 \cite{9253578}. + +This approach is often chosen in environments with focus on training speed, because +it does not require the calculation of e.g. gradients. +Therefore, it archives a training cost reduction of $64$\% for LeNet and up to $71$\% +for DeepSpeech2 \cite{9253578}. + +\subsubsection{Optimal Brain Damage} + +The \emph{Optimal Brain Damage} (\emph{OBD}) method removes weights based on their influence on the +objective function. The objective function can be any function formulating the error to be +minimized with training and measures the accuracy of the DNN. + +Formally, the sensitivity is derived from the diagonals of the Hessian of the weight matrix: + +\begin{align}\label{hessian} + & h_{kk} = \sum\limits_{(i,j) \in V_k} \frac{{\partial}^2 E}{\partial w_{ij}^2} \\ + & V_k := \text{Set of index pairs for matrix $W_k$} \nonumber +\end{align} + +After that the \emph{saliencies} are calculated as a measure of sensitivity: + +\begin{align}\label{saliencies} + & s_k = \frac{h_{kk} u_k^2}{2} \\ + & u_k := \text{Element $k$ of parameter vector} \nonumber +\end{align} + +For the pruning, all weight matrices undergo the following algorithm \cite{NIPS1989_6c9882bb}: + +\begin{enumerate} + \item Choose network architecture + \item Train network + \item Compute Hessian diagonals $h_{kk}$ for each parameter + \item Compute saliencies $s_k = \frac{h_{kk} u_k^2}{2}$ for each parameter + \item Sort parameters by saliency and remove low-saliency parameters + \item Go to step 2 or abort when accuracy threshold is reached +\end{enumerate} + +Experiments show that for LeNet a significant decrease in the \emph{Minimum-Mean-Square-Error} (\emph{MSE}) function +can be obtained compared to magnitude based methods with the same level of pruning, especially for high pruning amounts. +For $500$ remaining parameters, the MSE for OBD is $3$ magnitudes smaller than for magnitude based pruning. +However, this results in a generally high error rate and is therefore undesired. Optimal solutions +are obtained for $30$\% network pruning rate using this method. + +\subsubsection{Optimal Brain Surgeon} + +\emph{Optimal Brain Surgeon} (\emph{OBS}) works similar to OBD. Compared to OBD it does not neccessarily delete +the weights, but changes the strength of those weights. + +It does so by computing the inverse of the Hessian of the weight matrix \cite{NIPS1992_303ed4c6}: + +\begin{align}\label{saliencies} + & \textbf{H}_{m+1}^{-1} = \textbf{H}_{m}^{-1} - \frac{\textbf{H}_{m}^{-1} \textbf{X}_{m+1} \textbf{X}_{m+1}^T \textbf{H}_{m}^{-1}}{P + \textbf{X}_{m+1}^T \textbf{H}_{m}^{-1} \textbf{X}_{m+1}} \\ + & \textbf{H}^{-1} = \frac{1}{P} \sum\limits_{k=1}^{P} H_k^{-1} +\end{align} + +For the pruning, all weight matrices undergo the following algorithm \cite{NIPS1992_303ed4c6}: + +\begin{enumerate} + \item Train network. + \item Compute $\textbf{H}^{-1}$. + \item Find $q$ with smallest saliency $L_q = \frac{w_q^2}{2 \textbf{H}_{qq}^{-1}}$. If this gradient increase is much smaller than $E$, + delete $w_q$ and go to step 4. Otherwise go to step 5. + \item Use the $q$ from step 3 and update all weights. Go to step 2. + \item No more weights can be deleted without a large increase in $E$. Go to step 1 or abort if lower threshold in accuracy is reached. +\end{enumerate} + +Experiments show that this method can be used to reduce the number of weights by up to $90$\% without significant +impact on the accuracy, without retraining \cite{NIPS1992_303ed4c6}. + +\subsubsection{Biased weight decay} + +The \emph{Biased weight decay} method works during training-time of the model. +It bases on the backpropagation algorithm and adds a penalty term to the weight update formula: + +\begin{align} + & w_{n+1} = \alpha (- \frac{\partial E}{\partial w_n}) + \beta w_n \label{bwd1} \\ + & w_{n+1} = \alpha (- \frac{\partial E}{\partial w_{ij}} - 2 w_n) + w_n \label{bwd2} \\ + & \alpha < \frac{1}{2} := \text{Learning rate} \nonumber +\end{align} + +Equ.~\ref{bwd1} shows the update term of the backpropagation time considering an equal weight decay +for all values. Equ.~\ref{bwd2} shows the update term considering lower values to decay faster toward +zero while keeping high-valued weights the same. + +\subsection{Weight quantization} + +Storing the weight matrices as 32-bit floating point representation is not the most optimal +way of storage. While it preserves the precision the network was originally trained with, +it can be reduced significantly without high loss of accuracy. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/clustering}} + \caption{Weight quantization using clustering \cite{Han2015DeepCC}} + \label{clustering} +\end{figure} + +A key concept for quantization of weights is \emph{clustering}. Fig.~\ref{clustering} illustrates +this process. Using this method, similar valued weights are grouped into clusters. +The weight matrix then only stores the cluster index instead of the actual 32-bit floating point value. +Each cluster has its own \emph{centroid} for which the index value in the weight matrix +gets substituted. The centroids are the mean of all weight-values belonging to this +respective cluster. Additionally, the centroids can be fine-tuned by applying clustering to the gradient +of the weight matrix aswell, and update the centroid value with the gradient-means. + +This way, only a lookup-array with the cluster centroids and the respective indices in the weight matrix +need to be stored. In the example in Fig.~\ref{clustering} a $4 \times 4$ matrix of 32-bit floating point values +($512$ bit in total) can be reduced to a $4 \times 4$ matrix of 2-bit indices and a 4-value array of 32-bit floating point values +containing the centroids ($4 \cdot 4 \cdot 2 + 4 \cdot 32 = 160$ bit in total). + +Experiments have shown that using this quantization method only, compression factors of $37$x, $31$x and +$33$x can be archieved on AlexNet, VGG-16 and LeNet-5, while the loss in accuracy was +within tolerance \cite{Han2015DeepCC}. + +Technically, this compression method is not lossless, as it generalizes similar weights to their centroids. +So it comes down to the selection of the right centroids and which values to group into. If this is done efficiently, +the impact on accuracy is not measurable. For that, the k-means-algorithm is used. It minimizes +the \emph{Within-Cluster Sum of Squares} (\emph{WCSS}): + +\begin{align} + \text{argmin}_C \sum\limits_{i=1}^{k} \sum\limits_{\omega \in c_i} | \omega - c_i |^2 +\end{align} + +The k-means algorithm performs the following steps: + +\begin{enumerate} + \item Initialize $k$ cluster centroids + \item For all weights: + \begin{enumerate} + \item Assign weight to the cluster with nearest centroid + \item Recalculate cluster centroids + \end{enumerate} +\end{enumerate} + +A crucial degree of freedom for this is the initialization of the centroids. It determines +how fast the algorithm converges and to which values. There are different initialization methods. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/centroid_initialization}} + \caption{Different centroid initialization methods \cite{Han2015DeepCC}} + \label{init} +\end{figure} + +Fig.~\ref{init} depicts the different possible methods for centroid initialization. +Weight value probability density function (PDF) and cumulative distribution function (CDF) are plotted. +Note the peaks for low magnitude weights around 0. +Centroids can be initialized randomly, linear, or by linear sampling of the CDF values. +Generally, sampling the CDF values linearly and taking the corresponding weight values as centroids +minimizes the total error in weight values compared to their centroids. While this makes sense in most cases, +it does not in the case of DNN-weights. Here, weights with high value have a higher impact on the output, +but are underrepresented by occurrence using this method. This would lead to high value-centroid differences for those values, +because there are less centroids used. Because of this, linear initialization in the value domain has been established as the +best initialization method \cite{Han2015DeepCC}. + +\subsection{Huffman encoding} + +Another compression method that can be applied to DNNs is the Huffman encoding. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/huffman}} + \caption{Huffman encoding example} + \label{huffman} +\end{figure} + +Fig.~\ref{huffman} shows an encoding example. As a general principle, weights are encoded +with variable length in bits. Weights with many occurrences are encoded with less bits than +weights with less occurrences. The code book is stored as a binary tree, with edges encoding +$0$s and $1$s. The algorithm is the following: + +\begin{enumerate} + \item Count all weights and sort them by number of occurrence + \item Take the two weights with lowest number of occurrence and make them leafs of the tree + \item Connect the two nodes of the current layer together to a parent node + \item Take the weight with the next lowest occurrence and make it a leaf on the current layer + \item Go to step 3 or abort if no weight values are left +\end{enumerate} + +Weights are then encoded by the edges leading to their respective leafs. E.g. in Fig.~\ref{huffman} +the weight value $0$ is encoded as bit $0$, however weight value $2$ is encoded as bits $101$. +In this particular example, a compression rate of $74.05$\% is archieved. + +This compression method is especially efficient for models, in which one weight value is dominant. +When combined with other compression methods (e.g. pruning), which result in sparse matrices, +this is exactly the case with 0-values. + +Experiments have shown that when used together with pruning and weight quantization, +Huffman encoding archieves $35$x - $49$x compression rate \cite{Han2015DeepCC}. + +Another remarkable advantage of this compression method is that it is lossless and has therefore +no impact on the accuracy of the DNN. + +\subsection{HashNets} + +A relatively recent compression/optimization technique for weights of DNNs are HashNets \cite{10.5555/3045118.3045361}. +Using HashNets, no actual values need to be stored in the weight matrix (not even index values), +so the memory access for accessing these values can be completely omitted. +Instead, the values are depicted via a \emph{one-way hash function} $h$. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/hashnets}} + \caption{HashNets encoding (based on \cite{10.5555/3045118.3045361})} + \label{hashnets} +\end{figure} + +Fig.~\ref{hashnets} shows this principle. The real weight values are stored in an indexed +array. The hash function $h(i,j) := (i,j) \mapsto x$ takes the weight matrix indices $(i,j)$ +and computes the index $x$ for the lookup array, so that the lookup value of the array corresponds +to the actual value of the \emph{virtual weight matrix} $\textbf{V}$: + +\begin{align} + w^{\ell}_{h^{\ell}(i, j)} = \textbf{V}^{\ell}_{ij} +\end{align} + +This way, the weight matrix only exists virtually. Only the dimensions of the weight matrix and +the weight lookup array need to be stored, and there is no additional index lookup +neccessary for the weight matrix. This comes to the cost of computing the hash function, +but as already discussed in section~\ref{sec:memory} computation is not the limiting factor +when compared to memory accesses. + +The compression factor for this method can be variably chosen, depending on accuracy requirements. +The degree of freedom here is the quantization method (how much different values to quantisize to), +thus, the resulting weight array. Also, different hash functions can be used. + +\cite{10.5555/3045118.3045361} discusses effects of compression factors of up to $64$x, and uses +\emph{xxHash} as hash function. + +\subsection{Sparse matrix storage} + +When it comes to compression of weight matrices, the storage of the resulting sparse matrix needs +to be considered aswell. The \emph{Compressed sparse column} (\emph{CSC}) / \emph{Compressed sparse row} (\emph{CSR}) +format has been established for this purpose. + +With this method, a row/column $W_j$ of weight values is encoded as vectors $v$ and $z$. +$v$ contains the non-zero weight values of the column. $z$ is of equal length than $v$ and denotes +the amount of $0$s before the corresponding entry in $v$. +E.g. column $[0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3]$ gets encoded as +$v = [1, 2, 0, 3]$ and $z = [2, 0, 15, 2]$. An additional padding value of $0$ has been added after +$15$ concurrent $0$s, because the entries are assumed to be of 4-bit integer representation, and there are more than +$15$ concurrent $0$s after the value $2$. + +For this example, the method needs storage for $8$ values instead of $23$, which equals a compression rate of +$34.78$\%. This method is also used by the EIE and optimized by its architecture. + +\section{EIE implementation}\label{sec:implementation} + +\begin{figure*}[t] + \centering + \includegraphics[width=\textwidth]{resources/eie_hw} + \caption{Hardware architecture of the EIE \cite{10.1109/ISCA.2016.30}} + \label{eie} +\end{figure*} + +In general, the EIE is an approach to optimize the per-activation formula of DNNs (Equ.~\ref{mac}): + +\begin{align} + & b_i = f(\sum\limits_{j=0}^{n-1} W_{ij} a_j) \overset{!}{=} \text{ReLU}(\sum\limits_{j \in X_i \cap Y} S[I_{ij}] a_j) \\ + & X_i := \text{Set of columns, skipping $W_{ij} = 0$} \nonumber \\ + & Y := \text{Set of indices in $a$ for which $a_j \neq 0$} \nonumber \\ + & I_{ij} := \text{4-bit index} \nonumber \\ + & S := \text{Shared lookup table} \nonumber +\end{align} + +As activation function $f$ the \emph{Rectified Linear Unit} function (\emph{ReLU}) is fixed. +It is defined as $0$ for negative values while keeping positive values unchanged. +The indices $I_{ij}$ decompressed from CSC-format are used to lookup the actual weights from a shared weight lookup table $S$. +Values of $0$ as weights or inputs are skipped for multiplication and accumulation, +as they do not need to be computed. + +Fig.~\ref{eie} shows a block diagram of the hardware architecture of the EIE. +The left side (a) is the \emph{leading non-zero detection unit} (\emph{LNZD}), which detects $0$-values in the input +vector and skips them, while only forwarding non-zero values. The right side (b) is the actual \emph{processing element} (\emph{PE}), which +receives the non-zero input values. + +For parallelism, there are generally multiple PEs working independently. $4$ PEs are grouped together and share one +LNZD-unit. + +\subsection{Leading non-zero detection unit} + +Input activations are distributed to each processing element (PE) in a hierarchical manner. +To utilize the sparsity of the input vector, a leading non-zero detection logic is employed to identify the first non-zero result. +A group of four PEs perform local leading non-zero detection on their respective inputs and the results are sent +to a LNZD node. + +\subsection{Activation queue} + +The non-zero elements of the input activation vector $a_j$, along with their corresponding indexes $j$ are broadcasted +to an activation queue in each PE. However, if any PE has a full queue, the broadcast is disabled. Each PE processes +the activation at the front of its queue at any given time. The activation queue enables each PE to accumulate +some values and indices to balance out any load imbalances that may occur due to variations in the number of non-zeros +in a particular column $j$ among the PEs. + +\subsection{Pointer Read Unit} + +To efficiently access the $v$ and $z$ arrays for a given column $j$ using single-ported SRAM arrays, +the index $j$ at the head of the activation queue is used to look up the start and end pointers ($p_j$ and $p_{j+1}$) +for that column. These are seperately stored along with $v$ and $z$ to mark the iteration boundaries. +To ensure that both pointers can be read in a single cycle, the 16-bit pointers are stored in +two separate SRAM banks and the least significant bit (LSB) of the address is used to select the appropriate bank. +As a result, $p_j$ and $p_{j+1}$ will always be located in different banks. + +\subsection{Sparse Matrix Read Unit} + +The Sparse Matrix Read Unit reads out the actual non-zero weight values from the SRAM, +for the part of the column $W_j$ associated with the respective PE. It uses the pointers +$p_j$ and $p_{j+1}$ fetched before as reading boundaries. + +As the SRAM is of 64-bit word length and an entry in $v$ and $z$ is encoded in 4-bit each, +$8$ complete values can be read out in one cycle. This $(v, z)$ pair is then forwarded +to the arithmetic unit. + +\subsection{Arithmetic Unit} + +The arithmetic unit receives the $(v,z)$ value pair. It calculates the absolute index +$x$ in the output vector $b$ from the relative index $z$ and calculates the multiplication +$b_x = b_x + v \cdot a_j$ for which the output $b_x$ is the accumulation register. + +The values are stored in an encoded and quantisized form, so for calculation they are expanded +to 16-bit floating point representation first. + +\subsection{Activation Read/Write Unit} + +The Activation Read/Write Unit handles the values of the output vector. The target values are buffered +in two register files. For feed-forward layers in NNs the output values of one layer +are the input files of the next layer, so they exchange their roles after each layer to +save memory accesses to the SRAM. + +Access to SRAM is only occurring if the buffer is full. Then the entire buffer batch is written +to the SRAM. + +\subsection{Weight value distribution} + +An important factor is how to distribute the individual values of the weight matrix +to the individual PEs. + +\begin{figure}[htbp] + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/eie_matrix}} + \centerline{\includegraphics[width=\linewidth, keepaspectratio]{resources/eie_layout}} + \caption{Weight matrix segmentation and memory layout \cite{10.1109/ISCA.2016.30}} + \label{eie_segmentation} +\end{figure} + +Fig.~\ref{eie_segmentation} illustrates how the values are distributed to 4 PEs, and the corresponding +memory layout for PE0. Each row belongs to one PE and are distributed sequentially, +repeating after 4 rows. Each PE calculates one element $b_x$ of the output vector $b$ with one entry +of the input vector $a_j$ at a time. The individual PEs perform the MACs for each assigned input entry, +skipping $0$-valued entries using the non-zero detection units. + +On the bottom of Fig.~\ref{eie_segmentation} the memory layout for PE0 is depicted. Each PE stores +the non-zero values assigned to it, together with the relative indices $z$ encoding the number +of zeros before each element in $v$, but only for the respective PE. +To know the iteration boundaries, the column pointers are stored seperately. In the example above, +the first column has pointer $0$ (because it is the first entry in total). The second entry has pointer $3$, +because this PE has $3$ non-zero values assigned to it in the first column. + +\bibliographystyle{IEEEtran} +\bibliography{Paper/references} + +\end{document}
\ No newline at end of file |