Paper Info
Title
CSX: an extended compression format for spmv on shared memory systems
Abstract
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 research has demonstrated that an effective strategy to improve the kernel's performance is to drastically reduce the data volume involved in the computations. Since the storage formats for sparse matrices include metadata describing the structure of non-zero elements 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. Experimental 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 construction, we propose several strategies which trade performance for preprocessing cost making CSX applicable both to online and offline preprocessing.
Year
DOI
Venue
2011
10.1145/1941553.1941587
PPOPP
Keywords
Field
DocType
csx construction,spmv routine,shared memory system,sparse extended,sparse matrix,trade performance,compress metadata,extended compression format,sparse matrix-vector multiplication,significant performance gain,data access pattern,shared memory,sparse matrices,smp,data access,code generation,compression
Kernel (linear algebra),Metadata,Shared memory,Computer science,Sparse matrix-vector multiplication,Parallel computing,Sparse approximation,Theoretical computer science,Code generation,Data access,Sparse matrix
Conference
Volume
Issue
ISSN
46
8
0362-1340
Citations 
PageRank 
References 
28
1.16
18
Authors
4
Name
Order
Citations
PageRank
Kornilios Kourtis134029.44
Vasileios Karakasis213810.24
Georgios Goumas326822.03
N. Koziris41015107.53