Sparse Matrix Vector Processing Formats

In this dissertation we have identified vector processing shortcomings related to the efficient storing and processing of sparse matrices. To alleviate existent problems we propose two storage formats denoted as Block Based Compression Storage (BBCS) format and Hierarchical Sparse Matrix (HiSM) storage. Furthermore we propose vector architectural instruction set extensions and microarchitecture mechanisms to speed up frequently used sparse matrix operations using the proposed formats. Finally we identified the lack of benchmarks that cover both format and sparse matrix operations. We introduced a benchmark that covers both. To evaluate our proposal we developed a simulator based on SimpleScalar, extended so that it incorporates our proposed changes and established the following. Regarding storage space our proposed formats require 72% to 78% of the storage space needed for Compressed Row Storage (CRS) or the Jagged Diagonal (JD) storage, both commonly used sparse matrix storage formats. Regarding Sparse Matrix Vector Multiplication (SMVM) both BBCS and HiSM achieve a considerable performance speedup when compared to CRS and JD. More in particular, when performing the SMVM using the HiSM format and the newly proposed instructions we can achieve a speedup of 5.3 and 4.07 versus CRS and JD respectively. Additionally, the operation of element insertion using HiSM can be sped up by a factor of 2-400 depending on the sparsity of the matrix. Furthermore, we show that we can increase the performance of the transposition operation by a factor of 17.7 when compared to CRS