Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
A New Diagonal Blocking Format and Model of Cache Behavior for Sparse Matrices
verfasst von : Pavel Tvrdík, Ivan Šimeček
Erschienen in: Parallel Processing and Applied Mathematics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Algorithms for the sparse matrix-vector multiplication (shortly
SpM
×
V
) 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
SpM
×
V
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.