# Compressed Learning of Deep Neural Networks for OpenCL-Capable Embedded Systems
## 2 Method
### Optimization Algorithm
We used OpenCL-Caffe with an open source OpenCL back-end library called ViennaCL [62], which provides efficient implementations of basic linear algebra operations and some of the sparse matrix functionality. ### Compressed Sparse Matrix

In Section 2, we discussed how we could apply sparse coding to fix the values of irrelevant learning weights of DNNs at zero. However, if the zero values are explicitly stored in memory, the model will use the same amount of memory as the original model without compression. That is, for model compression, we need a special data structure to store only the nonzero weight values in GPU memory. For our implementation, we have considered several popular formats, in particular, DIA, ELL, CSR, and COO matrix formats to store the sparse weight matrices [63] (see Figure 1 for comparisons of the formats). Among these, DIA is suitable for the case when nonzero values are at a small number of diagonals, and ELL is for the case when matrix rows have similar numbers of nonzero entries. Since there is usually no particular pattern of zero entries in weight matrices produced by sparse coding, we have concluded that these formats are unsuitable. The compressed sparse row (CSR) format is probably the most popular format for representing unstructured sparse matrices. This format stores column indices and nonzero values in indices and data, respectively, while in ptr it stores the indices where new rows begin. Compared to DIA and ELL, the CSR format can store variable numbers of nonzeros in rows efficiently. The coordinate (COO) format is similar to CSR, but operations on COO can be made simpler as it also stores row indices in row for every nonzero entry. The extra storage required by COO for the row indices appears to be less economical than CSR, as our target platforms include small embedded systems. Therefore, we conclude that the CSR format will be the best for representing compressed sparse weight matrices in small, GPU-enabled devices. In ViennaCL, the CSR format is implemented as the C++ class compressed_matrix, and we have adapted this class to implement our new matrix operations for forward/backward passes of deep neural networks. Matrix:

\[A= \begin{bmatrix}1&7&0&0\\ 0&2&8&0\\ 5&0&3&9\\ 0&6&0&4\end{bmatrix} \]

Compressed Matrix Representations:

(i) DIA format:

\[\text{data}= \begin{bmatrix}*&1&7\\ *&2&8\\ 5&3&9\\ 6&4&*\end{bmatrix} ,\ \ \text{offsets}=[-2\ \ 0\ \ 1]\]

(ii) ELL format:

\[\text{data}= \begin{bmatrix}1&7&*\\ 2&8&*\\ 5&3&9\\ 6&4&*\end{bmatrix} ,\ \ \text{indices}= \begin{bmatrix}0&1&*\\ 1&2&*\\ 0&2&3\\ 1&3&*\end{bmatrix} \]

(iii) CSR format:

\[\text{row\_ptrs} =[\ 0\ \ 2\ \ 4\ \ 7\ \ 9\ ]\] \[\text{col\_indices} =[\ 0\ \ 1\ \ 1\ \ 2\ \ 0\ \ 2\ \ 3\ \ 1\ \ 3\ ]\] \[\text{elements} =[\ 1\ \ 7\ \ 2\ \ 8\ \ 5\ \ 3\ \ 9\ \ 6\ \ 4\ ]\]

(iv) COO format:

\[\text{row} =[\ 0\ \ 0\ \ 1\ \ 1\ \ 2\ \ 2\ \ 2\ \ 3\ \ 3\ ]\] \[\text{indices} =[\ 0\ \ 1\ \ 1\ \ 2\ \ 0\ \ 2\ \ 3\ \ 1\ \ 3\ ]\] \[\text{data} =[\ 1\ \ 7\ \ 2\ \ 8\ \ 5\ \ 3\ \ 9\ \ 6\ \ 4\ ]\]

### Sparse Matrix Multiplication in OpenCL

For training a deep neural network, we need efficient sparse matrix operations to deal with the compressed sparse weight matrices in the CSR format. To simplify notations, let us use \(W\) to denote the sparse weight matrix that coordinates the transfer between two consecutive DNN layers, we call the bottom and the top layers (bottom \(\rightarrow\) top is the forward pass direction).