N.: CSX: An Extended Compression Format for SpMV on Shared Memory Systems

The Sparse Matrix-Vector multiplication (SpMV) kernel scales poorly on shared memory systems with multiple processing units due to the streaming nature of its data access pattern. Previous re-search has demonstrated that an effective strategy to improve the kernel’s performance is to drastically reduce the data volume in-volved in the computations. Since the storage formats for sparse matrices include metadata describing the structure of non-zero el-ements within the matrix, we propose a generalized approach to compress metadata by exploiting substructures within the matrix. We call the proposed storage format Compressed Sparse eXtended (CSX). In our implementation we employ runtime code generation to construct specialized SpMV routines for each matrix. Experi-mental evaluation on two shared memory systems for 15 sparse matrices demonstrates significant performance gains as the number of participating cores increases. Regarding the cost of CSX con-struction, we propose several strategies which trade performance for preprocessing cost making CSX applicable both to online and offline preprocessing