Performance aspects of sparse matrix-vector multiplication

Result code in IS VaVaI

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

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Performance aspects of sparse matrix-vector multiplication

Original language description

Sparse matrix-vector multiplication (shortly SpMV) is an important building block in algorithms solving sparse systems of linear equations, e.g., FEM. Due to matrix sparsity, the memory access patterns are irregular and utilization of the cache can suffer from low spatial or temporal locality. Approaches to improve the performance of SpMV are based on matrix reordering and register blocking, sometimes combined with software-pipelining. Due to its overhead, register blocking achieves good speedups only for a large number of executions of SpMV with the same matrix A. We have investigated the impact of two simple SW transformation techniques (software-pipelining and loop unrolling) on the performance of SpMV, and have compared it with several implementation modifications aimed at reducing computational and memory complexity and improving the spatial locality. We investigate performance gains of these modifications on four CPU platforms.

Czech name

Výkonnostní aspekty násobení řídké matice vektorem

Czech description

Násobení řídké matice hustým vektorem je jednou ze základní operací numerické lineární algebry. Kvůli řídkosti vstupní matice, je schéma přístupu do paměti velmi nerovnoměrné, což znamená nízkou úspěšnost skrytých pamětí a z toho plyne nízká výkonnost celého algoritmu. Přístupy ke zvýšení rychlosti algoritmu jsou vesměs založeny na reorganizaci matice (matrix reordering) nebo nalezení hustých bloků v matici (register blocking) někdy v kombinaci s přednačtením prvků (software-pipelining). Tyto přístupy jsou časově velmi náročné proto se vyplatí pouze pro vykonání velkého počtu násobení stejnou maticí. V tomto článku jsme prozkoumali dopad 2 jednoduchých SW transformačních technik (sw-pipelining a loop unrolling) na výkonnost násobení a porovnali jsme tento dopad se změnami způsobenými rozdílnými implementacemi. Tyto dopady jsme změřili na 4 různých procesorových platformách.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

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ů

Name of the periodical

Acta Polytechnica

ISSN

1210-2709

e-ISSN

—

Volume of the periodical

2006

Issue of the periodical within the volume

3

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

6

Pages from-to

3-8

UT code for WoS article

—

EID of the result in the Scopus database

—