A New Diagonal Blocking Format and Model of Cache Behavior for Sparse Matrices

Result code in 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>

Alternative codes found

RIV/68407700:21110/06:03118854

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

A New Diagonal Blocking Format and Model of Cache Behavior for Sparse Matrices

Original language description

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.

Czech name

Nový formát diagonálního uložení řídkých matic

Czech description

Násobení řídké matice vektorem je velice častou úlohou v lineární řešičích. Kvůli nepřímému adresování je však výkonnost násobení v klasických formátech nízká. Proto byl zavedeny formáty pro diagonálního uložení řídkých matic. Tato zpráva popisuje nový formát diagonálního uložení řídkých matic, který rozšiřuje možnosti předcházejících formátů.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/IBS3086102" target="_blank" >IBS3086102: Parallel Algorithms for Large Scale Simulation on PC Clusters</a><br>

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2006

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Parallel Processing and Applied Mathematics

ISBN

3-540-34141-2

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

164-171

Publisher name

Springer

Place of publication

Berlin

Event location

Poznan

Event date

Sep 11, 2005

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—