Enhancing the Sparse Matrix Storage Using Reordering Techniques

Sparse linear algebra kernels are memory-bound routines, and their performance varies significantly according to the non-null pattern of the sparse matrix operands. The impressive computing power and memory bandwidth of modern massively parallel computing devices encourage researchers to develop sparse linear algebra kernels that can exploit these platforms efficiently. In this sense, a main line of work improves the storage of matrices, aiming to optimize the communication between the memory and the cores. In previous work, the use of a strategy consisting of a delta-encoding with matrix reorderings compressed the indexing data of the matrix, saving storage and communications. This work presents an algorithm to improve the reordering strategy and the resulting compression of the indexing data. The results show that this strategy leads to important storage savings, which can also reduce data movements between the main memory and processors.