# Compressed Learning of Deep Neural Networks for OpenCL-Capable Embedded Systems
## 2 Method
### Optimization Algorithm
Denoting by \(X_{B}\) and \(X_{T}\) the input from the bottom layer and the output to the top layer respectively and following the shapes and orders of matrices according to the original implementation of Caffe, we can summarize the matrix multiplications needed for the forward and the backward propagation steps as follows:

\[\text{Forward} : X_{T}\gets X_{B}W^{\prime}\ \ \text{(dense\times compressed ${}^{\prime}$)},\] \[\text{Backward} : \frac{\partial Loss}{\partial X_{B}}\leftarrow\frac{\partial Loss }{\partial X_{T}}W\ \ \text{(dense\times compressed)}.\]

Figure 1: Compressed matrix representation of a simple matrix \(A\). The entries marked by \(*\) are padding entries ([64], Figure 2). Here, \(X_{B}\) and \(\frac{\partial L\text{ess}}{\partial X_{T}}\) are typically dense matrices, and therefore we essentially need two types of operations: dense\(\times\)compressed\({}^{\prime}\) (\(D\times C^{\prime}\) in short), where \({}^{\prime}\) is the matrix transpose operation, and dense\(\times\)compressed (\(D\times C\) in short). Unfortunately, these operations are not available in the current version of ViennaCL (accessed on 19 October 2018): there exist \(C\times D\) and \(C\times D^{\prime}\) operations in ViennaCL, so we could use a workaround \((C\times D^{\prime})^{\prime}=D\times C^{\prime}\), but this requires extra memory space for transposing the result of \(C\times D^{\prime}\). Furthermore, such a workaround is not available for \(D\times C\) since \((D\times C)^{\prime}=C^{\prime}\times D^{\prime}\), and the transpose operation for compressed sparse matrices (\(C^{\prime}\)) is not available in ViennaCL. As a solution, we provide two new dense-compressed matrix multiplications accelerated by OpenCL. #### 3.2.1 Dense \(\times\) Compressed\({}^{\prime}\)

In our implementation, this operation is used for computing forward propagation. This operation is well suited for GPU acceleration, since the compressed matrix stores nonzero elements rowwise, where we access the nonzero elements stored in the compressed matrix in a rowwise fashion to compute the inner product between a row of the dense matrix and a column of the compressed\({}^{\prime}\) matrix. Figure 2 shows a sketch of the operation and our OpenCL kernel code to perform this multiplication on GPUs: an OpenCL thread group is assigned to each row of Dmat (dense matrix), and multiple threads in the group will handle the assigned columns, one thread per column. For each (row, col) pair, an inner product between the row in Dmat and the column in Cmat\({}^{\prime}\) (compressed\({}^{\prime}\)) will be computed. In our discussion hereafter, we assume that Dmat and result matrices are stored in a rowwise fashion. The column memory access of Cmat\({}^{\prime}\) equals to the row access of Cmat, and therefore we can use Cmat_row_pts to enumerate the nonzero elements corresponding to the variable col. Each thread can access only the required nonzero elements in consecutive memory locations, and therefore thread memory access will be coalesced, leading to efficient parallelism on GPUs. Figure 2: OpenCL kernel for the Dense(Dmat) \(\times\) Compressed(Cmat)\({}^{\prime}\) operation. #### 3.2.2 Dense \(\times\) Compressed

This dense-compressed matrix operation is required for backward propagation. Unlike the previous one, this operation is not ideally suited for GPU parallelism since the OpenCL kernel needs to access the Cmat matrix columnwise, while the nonzero entries of the compressed matrix are stored in a rowwise fashion. Unless we store an extra array for nonzero entries stored columnwise in the compressed matrix data structure, it is unavoidable that the memory access pattern will not coalesce. Still, we can design an OpenCL kernel to parallelize the computation for each (row, col) pair, as shown in \[\text{col\_indices} =[\ 0\ \ 1\ \ 1\ \ 2\ \ 0\ \ 2\ \ 3\ \ 1\ \ 3\ ]\]0

### Prox Operator in OpenCL

The proximal operator discussed in Section 2.2 can be performed in parallel since the outcome can be computed elementwise, as shown in Equation (2).