Exploration of Cache Line Size for Sawtooth Compressed Row Storage based SpMV Multiplication

Chinthala, R., Datta, A. and Nandy, S.K.

Sparse Matrix Vector Multiplication (SpMV) is an important kernel in Sparse Linear Algebra. Cache based systems performance is poor during SpMV multiplication due to poor data locality of sparse matrix storage formats. In this paper, we propose a Sawtooth Compressed Row Storage (SCRS) data structure to represent sparse matrix which requires less memory and improves temporal locality compared to Compressed Row Storage (CRS), Incremental CRS (ICRS), Zig-Zag ICRS (ZZICRS) (A. Yzelman et al. 2009). We also propose a SCRS based Sawtooth Sparse Matrix Vector (SpMV) multiplication algorithm to exploit the improved temporal locality. The simulation results indicate that our proposed SCRS based SpMV algorithm achieves fewer cache misses and shorter execution time than the state of the art storage format based SpMV algorithms.

Cite as: Chinthala, R., Datta, A. and Nandy, S.K. (2015). Exploration of Cache Line Size for Sawtooth Compressed Row Storage based SpMV Multiplication. In Proc. 13th Australasian Symposium on Parallel and Distributed Computing (AusPDC 2015) Sydney, Australia. CRPIT, 163. Javadi, B. and Garg, S.K. Eds., ACS. 93-96

(from crpit.com) (local if available)