Acta Polytechnica

Performance aspects of sparse matrix-vector multiplication

Author: Ivan Šimeček

Sparse matrix-vector multiplication, code restructuring, loop unrolling, software pipelining, cache hierarchy.


Sparse matrix-vector multiplication (shortly SpMxV) is an important building block in algorithms solving sparse systems of linear equations, e.g., FEM. Due to matrix sparsity, the memory access patterns are irregular and utilization of the cache can suffer from low spatial or temporal locality. Approaches to improve the performance of SpMxV are based on matrix reordering and register blocking [1,2], sometimes combined with software-pipelining [3]. Due to its overhead, register blocking achieves good speedups only for a large number of executions of SpMxV with the same matrix A. We have investigated the impact of two simple SW transformation techniques (software-pipelining and loop unrolling) on the performance of SpMxV, and have compared it with several implementation modifications aimed at reducing computational and memory complexity and improving the spatial locality. We investigate performance gains of these modifications on four CPU platforms.

final version (in .PDF format)

BibTex entry:
@ARTICLE{JA_ACTA2, author = {Ivan \v{S}ime\v{c}ek},
title = {Performance aspects of sparse matrix-vector multiplication},
journal = {Acta Polytechnica},
year = {2007},
volume = {2006},
pages = {3--8},
number = {3},
month = {January},
issn = {1210-2709}