The acceleration of the sparse matrix-vector multiplication by the region traversal
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03151548" target="_blank" >RIV/68407700:21230/08:03151548 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
The acceleration of the sparse matrix-vector multiplication by the region traversal
Original language description
Sparse matrix-vector multiplication (shortly spMV) is one of most common subroutines in the numerical linear algebra. The problem is that the memory access patterns during the spMV are irregular and the utilization of cache can suffer from low spatial ortemporal locality. This paper introduces new approach for the acceleration the spMV. This approach consists of 3 steps: 1) dividing matrix A into non-empty regions, 2) choosing an efficient way to traverse these regions (in another words choosing an efficient ordering of partial multiplications), 3) choosing the optimal type of storage for each region. In this paper, we describe aspects of these 3 steps in more detail (including fast and time-inexpensive algorithms for all steps). Our measurements proved that our approach gives a significant speedup for almost all matrices arising from various technical areas.
Czech name
The acceleration of the sparse matrix-vector multiplication by the region traversal
Czech description
Tato zpráva popisuje nový přístup ke zrychlení násobení řídké matice vektorem. Princip spočívá ve 3 krocích: 1) rozdělení původní matice na regiony, 2) zvolení efektivního způsobu průchodu těhto regionů, 3) volba optimální způsobu uložení jednotlivých regionů. Naše měření prokázala, že daná metoda dosahuje podstatného zrychlení u matic z různých technických oborů.
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Acta Polytechnica
ISSN
1210-2709
e-ISSN
—
Volume of the periodical
48
Issue of the periodical within the volume
4/2008
Country of publishing house
CZ - CZECH REPUBLIC
Number of pages
8
Pages from-to
—
UT code for WoS article
—
EID of the result in the Scopus database
—