A New Approach for Accelerating the Sparse Matrix-vector Multiplication

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03127682" target="_blank" >RIV/68407700:21230/07:03127682 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

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 ke 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ů.

Type

D - Article in proceedings

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

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

Proceedings of Workshop 2007

ISBN

978-80-01-03667-9

ISSN

—

e-ISSN

—

Number of pages

2

Pages from-to

—

Publisher name

ČVUT

Place of publication

Praha

Event location

Praha

Event date

Feb 19, 2007

Type of event by nationality

EUR - Evropská akce

UT code for WoS article

—