Bekzod Fazilov
A comprehensive analysis of Sparse Matrix by Vector multiplication on FPGA with different compression formats.
Rel. Luciano Lavagno, Filippo Minnella. Politecnico di Torino, Corso di laurea magistrale in Mechatronic Engineering (Ingegneria Meccatronica), 2023

PDF (Tesi_di_laurea)
 Tesi
Licenza: Creative Commons Attribution Noncommercial No Derivatives. Download (2MB)  Preview 

Archive (ZIP) (Documenti_allegati)
 Other
Licenza: Creative Commons Attribution Noncommercial No Derivatives. Download (216kB) 
Abstract: 
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 nonzero 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 PYNQZ2 board. The sparse storage formats obtained from C++ are used to program the PYNQZ2 board. The performance estimation is done on the PYNQZ2 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 nonzero elements and the second matrix contain the values of the nonzero 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 nonzero elements, whereas the column and value arrays contain column indeces and corresponding values of the nonzero 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 nonzero elements, the value array contains values of the nonzero elements. The column pointer array contains pointer to the column, and it points to the first nonzero 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 

Relators:  Luciano Lavagno, Filippo Minnella 
Academic year:  2022/23 
Publication type:  Electronic 
Number of Pages:  62 
Subjects:  
Corso di laurea:  Corso di laurea magistrale in Mechatronic Engineering (Ingegneria Meccatronica) 
Classe di laurea:  New organization > Master science > LM25  AUTOMATION ENGINEERING 
Aziende collaboratrici:  Politecnico di Torino 
URI:  http://webthesis.biblio.polito.it/id/eprint/26674 
Modify record (reserved for operators) 