A comprehensive analysis of Sparse Matrix by Vector multiplication on FPGA with different compression formats

Today in many applications the edge devices are used from cloud computing, internet of things (IoT) to manufacturing sectors to monitor, analyse processes through applying machine learning and other algorithms. The edge devices usually run light software’s like quantized and small machine learning algorithms due to their limited performance, energy consumption and memory. The algorithms containing the matrix to vector multiplication operation, especially, the quantized fully connected stage of Neural Networks have weighted matrices which are usually consists of high percentage of zero elements. For the sake of reduction of resource usage, energy consumption and increasing the performance, the only non-zero elements can be used in these operations. Therefore, the sparse storage formats are helpful in avoiding multiplication operations involving zero elements. In this thesis work the dataflow of Sparse Matrix by Vector multiplication (SpMV) is analysed where the sparse matrices having different size and different sparsity are stored in different sparse storage formats. The sparse matrices are randomly generated with different sizes and different sparsity using probability algorithm and Mersenne Twister 19937 generator. The sparsity of matrices is chosen between 50% and 80%. And the sizes of the matrices were 30 by 30, 60 by 60, and 120 by 120. The C++ and Xilinx Vitis HLS are used to convert sparse matrices into ELL, CSC (compressed sparse column), CSR (compressed sparse row), COO (coordinate) sparse storage formats. Furthermore, Xilinx Vitis HLS is used also used to create the IP, estimate the resource utilization, and establish the input output ports. The generated IP then utilized by Xilinx Vivado Design Suite to simulate the hardware design and obtain the bitstream of the corresponding storage format. The obtained bitstream is used to configure the PL of the PYNQ-Z2 board. The sparse storage formats obtained from C++ are used to program the PYNQ-Z2 board. The performance estimation is done on the PYNQ-Z2 board. The sparse storage formats which are used in this thesis work are following: 1. ELL. 2. COO. 3. CSC. 4. CSR. 1.The ELL sparse storage format consists of 2 matrices, where the first matrix contains only the column indeces of non-zero elements and the second matrix contain the values of the non-zero elements. And both matrices have the same row number as primary sparse matrix. 2. The COO sparse matrix storage format consists of 3 arrays which are row, column, and value arrays. The row array contains the row indeces of the non-zero elements, whereas the column and value arrays contain column indeces and corresponding values of the non-zero element. 3. The CSC sparse matrix storage format consists also 3 arrays which are column pointer, row, and value arrays. The row array contains the row indeces of the non-zero elements, the value array contains values of the non-zero elements. The column pointer array contains pointer to the column, and it points to the first non-zero element in that column. The advantage is that the 3rd array contains less elements if compared to the COO format. And the is computation done of SpMV is totally different from formats which are mentioned above. 4. The CSR format is the same as CSC format, the difference between CSC format is in compression and the compression done through the rows. This format also contains 3 arrays, which are row pointer, column, and value arrays. The row pointer array contains pointer to the row, and it points