Nový formát diagonálního uložení řídkých matic
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F06%3A03118854" target="_blank" >RIV/68407700:21230/06:03118854 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21110/06:03118854
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A New Diagonal Blocking Format and Model of Cache Behavior for Sparse Matrices
Popis výsledku v původním jazyce
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 suffersfrom 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.
Název v anglickém jazyce
A New Diagonal Blocking Format and Model of Cache Behavior for Sparse Matrices
Popis výsledku anglicky
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 suffersfrom 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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/IBS3086102" target="_blank" >IBS3086102: Paralelní algoritmy pro rozsáhlé simulace na svazcích (klastrech) PC</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2006
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Parallel Processing and Applied Mathematics
ISBN
3-540-34141-2
ISSN
—
e-ISSN
—
Počet stran výsledku
8
Strana od-do
164-171
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Poznan
Datum konání akce
11. 9. 2005
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—