Optimizing sparse data structures for matrix-vector multiply

Sparse matrix-vector multiply is an important operation in a wide range of problems. One of the key factors determining the performance of this operation is sustained memory bandwidth. In the IBM POWER architecture, there is a hardware component called a prefetch data stream that can significantly increase sustained memory bandwidth. We have developed a new family of storage formats for sparse matrices that exploits this capability. Test results show that our new streamed storage formats can significantly improve the performance of sparse matrix and vector multiply on IBM POWER processors, compared to traditional compressed sparse row and block compressed sparse row formats. The new formats also provide a benefit on x86 processors.