# Efficient Implementation of Matrix-Based Image Processing Algorithms for IoT Applications
## 2 The Algorithm Description
This can be useful for algorithms based on matrix computation that does not require a large dynamic range. In common CNNs, the values of neural network layers and weights are represented in fixed point with 8 bits. There are certain applications that require more precision. For example, the CS-RANSAC algorithm, presented in previous sections, requires higher precision due the DCT coefficients of lower order. Figure 10: Matrix multiplication CNN-based algorithm (fixed point). Figure 9: Neural network fully interconnected layer used for matrix multiplication (detailed example for \(N=2\)). We proposed an approach that makes matrix multiplication with increased precision possible, considering a floating-point representation of matrix elements. We assume that the values of matrix elements are \(a_{ij}=A_{ij}2^{ea_{ij}}\), \(b_{ij}=B_{ij}2^{eb_{ij}}\) and \(c_{ij}=C_{ij}2^{ea_{ij}}\) with \(A_{ij},B_{ij},C_{ij}\)- mantises and \(ea_{ij},eb_{ij},ec_{ij}\)- exponents represented as fixed-point integers with 8 bits. The output elements are \(c_{ij}=\sum_{k=1}^{N}A_{ik}2^{ea_{ik}}B_{kj}2^{eb_{ij}}=\sum_{k=1}^{N}A_{ik}B_ {kj}2^{ea_{ik}+eb_{ij}}\). The term \(O_{ikj}=A_{ik}B_{kj}\) will be computed using a full interconnected layer, as it has been shown previously (with a slight modification of weights--see Figure 11), and the term \(ea_{ik}+eb_{kj}\) will be computed using the element-wise function (the element-wise function must be enabled in CNN, and the addition function must be selected). Then, the maximum exponent is calculated as \(E_{ij,max}=max_{k=1...N}\left(ea_{ik}+eb_{kj}\right)\), and all the terms \(O_{ikj}\) will multiplied with \(2^{ea_{ik}+eb_{kj}-E_{ij,max}}\) in a second full interconnected layer. The results \(X_{ikj}=O_{ikj}2^{ea_{ik}+eb_{kj}-E_{ij,max}}\) are summed using the element wise CNN features. The sum is calculated iteratively using the element wise addition in \(log_{2}N^{2}\) steps, as in Figure 12.

Finally, in a third full interconnected layer, the elements of matrix products \(c_{ij}=2^{E_{ij,max}a_{ij}}\) are calculated. We assume that in image processing, one matrix (image to process) has sub-unitary mantises and \(ea_{ij}=0,i,j=1\ldots N\). The other matrix's exponents and mantises are constant; therefore, \(E_{ij,max}\) and \(2^{ea_{ik}+eb_{kj}-E_{ij,max}}\) can be passed as parameters in the matrix multiplication function. The complete algorithm is illustrated in Figure 13.

Figure 11: The full interconnected layer for floating point implementation (\(N=2\)). Figure 12: Element wise addition (example for \(N=4\)). The algorithm illustrated in Figure 13 can be efficiently implemented using the MAX78000 chip [24; 25]. The block diagram of MAX7800 is illustrated in Figure 14. The CNN accelerator consists of 64 parallel processors with 512 KB of SRAM-based storage. Each processor includes a pooling unit and a convolutional engine with dedicated weight memory. Four processors share one data memory. These are further organized into groups of 16 processors that share common controls. A group of 16 processors operates as a slave to another group or independently. Data are read from SRAM associated with each processor and written to any data memory located within the accelerator. Any given processor has visibility of its dedicated weight memory and to the data memory instance it shares with the three others. In general, an algorithm (or working task) with \(M\) instructions with \(t_{1}\) average execution time per instruction can be divided into two parts: \(fM\)--running using one processor with \(t_{2}\) average execution time per instruction and \((1-f)M\)--running using \(N\) processors with \(t_{3}\) average execution time per instruction, with \(f<1\). The speedup is calculated as \(s=\frac{Mt_{1}}{fM_{2}+\frac{(1-f)t_{3}}{N}}=\frac{t_{1}}{f_{12}+\frac{(1-f)t_ {3}}{N}}\). Considering \(t_{2}=rt_{1}\) and \(t_{3}=qt_{1}\) with \(r,q<1\), the speedup becomes \(s=\frac{t_{1}}{rt_{1}+\frac{(1-f)t_{3}}{N}}=\frac{1}{f_{7}+\frac{(1-f)t_{3}} {N}}=\frac{N}{Nfr+(1-f)q}=\frac{N}{f(Nr-q)+q}\).