Title :
Improving Performance of Sparse Matrix-Vector Multiplication
Author :
A. Pinar;M.T. Heath
Author_Institution :
University of Illinois at Urbana-Champaign
fDate :
6/21/1905 12:00:00 AM
Abstract :
Sparse matrix-vector multiplication (SpMxV) is one of the most important computational kernels in scientific computing. It often suffers from poor cache utilization and extra load operations because of memory indirections used to exploit sparsity. We propose alternative data structures, along with reordering algorithms to increase effectiveness of these data structures, to reduce the number of memory indirections. Toledo proposed handling the 1x2 blocks of a matrix separately, doing only one indirection for each block. We propose packing all contiguous nonzeros into a block to reduce the number of memory indirections further. This reduces memory indirections per block to one for the cost of an extra array in storage and a loop during SpMxV. We also propose an algorithm to permute the nonzeros of the matrix into contiguous locations. We state this problem as the traveling salesperson problem and use associated heuristics. Experiments verify the effectiveness of our techniques.
Keywords :
"Sparse matrices","Data structures","Rockets","Kernel","Scientific computing","Costs","Computer science","Computational modeling","Computer simulation","Vectors"
Conference_Titel :
Supercomputing, ACM/IEEE 1999 Conference
Print_ISBN :
1-58113-091-0
DOI :
10.1109/SC.1999.10030