A New Approach for Accelerating the Sparse Matrix-vector Multiplication
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03120767" target="_blank" >RIV/68407700:21230/07:03120767 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A New Approach for Accelerating the Sparse Matrix-vector Multiplication
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
Nový přístup k zrychlení násobení řídké matice vektorem
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
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
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
Article name in the collection
Proceedings of 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
ISBN
978-0-7695-2740-6
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
156-163
Publisher name
IEEE Computer Society
Place of publication
Los Alamitos
Event location
Timisoara (Temesvar)
Event date
Sep 26, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—