Sparse Matrices are very large matrices with very few nonzero elements and operations on sparse matrices are central to many numerical and graph algorithms. The fundamental bottleneck in these operations is the usage of specialized storage formats which only store the NonZero (NZ) elements and the indirect memory references required to access those elements. This makes the operations very sensitive to memory latency and bandwidth. Unfortunately, microprocessor trends are not encouraging for sparse matrix operations: latency is increasing and bandwidth is becoming more scarce. This results in many important applications having very poor computation performance. This dissertation describes a new sparse matrix format called Variable Dual Compressed Blocks (VDCB) that divides a matrix into a number of smaller, variable-sized submatrices with a bitmap to indicate the presence of NZ values. When used in conjunction with customized memory subsystem, this converts the memory reference pattern from random look-ups to a serial access pattern. To quantify how detrimental the legacy sparse matrix storage formats are, the proposed system has been implemented on an FPGA device and two common sparse matrix operations, Sparse Matrix Vector Multiplication (SMVM) and Sparse Matrix Matrix Multiplication (SMMM), were evaluated. These two operations represent a number of challenges for the memory and computation subsystems. Results demonstrate gains in bandwidth efficiency, significant impact on the performance of the SMVM and SMMM operations, and the scalability of the approach.
