PPAM'05
- SIXTH INTERNATIONAL CONFERENCE ON Parallel Processing and Applied
Mathematics
A new diagonal blocking format and model of
cache behavior for sparse matrices
Authors: Ivan Šimeček and Pavel Tvrdík
Keywords
Diagonal register blocking, sparse matrix-vector multiplication,
cache locality, analytical cache model.
Abstract
Algorithms for the sparse matrix-vector multiplication (shortly spMV) are important building blocks
in solvers of sparse systems of linear equations. Due to matrix
sparsity, the memory access patterns are irregular and the utilization
of a cache suffers from low spatial and temporal locality. To reduce
this effect, the diagonal register
blocking format was designed. This paper introduces a new
combined format, called CARB,
for storing sparse matrices that extends possibilities of the diagonal
register blocking format.
We have also developed a probabilistic model for estimating the numbers
of cache misses during the spMV
in the CARB format. Using HW cache monitoring tools, we compare the
predicted numbers of cache misses with real numbers on Intel x86
architecture with L1 and L2 caches. The average accuracy of our
analytical model is around 95% in case of L2 cache and 88% in case of
L1 cache.
.
Download:
final version ( in .PDF format)
BibTex entry:
@INPROCEEDINGS{JA_PPAM05,
author = {P. Tvrd\'{\i}k and I. \v{S}ime\v{c}ek},
title = {A new diagonal blocking format and model of cache
behavior for sparse
matrices},
booktitle = {Parallel Processing and Applied Mathematics},
year = {2006},
volume = {3911},
series = {Lecture Notes of Computer Science},
pages = {164-171},
address = {Poznan, Poland},
publisher = {Springer},
isbn = {3-540-34141-2},
}
