Joint direct and transposed sparse matrix-vector multiplication for multithreaded CPUs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F21%3A00346816" target="_blank" >RIV/68407700:21240/21:00346816 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1002/cpe.6236" target="_blank" >https://doi.org/10.1002/cpe.6236</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1002/cpe.6236" target="_blank" >10.1002/cpe.6236</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Joint direct and transposed sparse matrix-vector multiplication for multithreaded CPUs

Popis výsledku v původním jazyce

Repeatedly performing sparse matrix-vector multiplication (SpMV) followed by transposed sparse matrix-vector multiplication (SpMᵀV) with the same matrix is a part of several algorithms, for example, the Lanczos biorthogonalization algorithm and the biconjugate gradient method. Such algorithms can benefit from combining parallel SpMV and SpMᵀV into a single operation we call `joint direct and transposed sparse matrix-vector multiplication’ (SpMMᵀV). In this article, we present a parallel SpMMᵀV algorithm for shared-memory CPUs. The algorithm uses a sparse matrix format that divides the stored matrix into sparse matrix blocks and compresses the row and column indices of the matrix. This sparse matrix format can be also used for SpMV, SpMᵀV, and similar sparse matrix-vector operations. We expand upon existing research by suggesting new variants of the parallel SpMMᵀV algorithm and by extending the algorithm to efficiently support symmetric matrices. We compare the performance of the presented parallel SpMMᵀV algorithm with alternative approaches, which use state-of-the-art sparse matrix formats and libraries, using sparse matrices from real-world applications. The performance results indicate that the median performance of our proposed parallel SpMMᵀV algorithm is up to 45% higher than of the alternative approaches.

Název v anglickém jazyce

Joint direct and transposed sparse matrix-vector multiplication for multithreaded CPUs

Popis výsledku anglicky

Repeatedly performing sparse matrix-vector multiplication (SpMV) followed by transposed sparse matrix-vector multiplication (SpMᵀV) with the same matrix is a part of several algorithms, for example, the Lanczos biorthogonalization algorithm and the biconjugate gradient method. Such algorithms can benefit from combining parallel SpMV and SpMᵀV into a single operation we call `joint direct and transposed sparse matrix-vector multiplication’ (SpMMᵀV). In this article, we present a parallel SpMMᵀV algorithm for shared-memory CPUs. The algorithm uses a sparse matrix format that divides the stored matrix into sparse matrix blocks and compresses the row and column indices of the matrix. This sparse matrix format can be also used for SpMV, SpMᵀV, and similar sparse matrix-vector operations. We expand upon existing research by suggesting new variants of the parallel SpMMᵀV algorithm and by extending the algorithm to efficiently support symmetric matrices. We compare the performance of the presented parallel SpMMᵀV algorithm with alternative approaches, which use state-of-the-art sparse matrix formats and libraries, using sparse matrices from real-world applications. The performance results indicate that the median performance of our proposed parallel SpMMᵀV algorithm is up to 45% higher than of the alternative approaches.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

Kód důvěrnosti údajů

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

Název periodika

Concurrency and Computation: Practice and Experience

ISSN

1532-0626

e-ISSN

1532-0634

Svazek periodika

33

Číslo periodika v rámci svazku

13

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

26

Strana od-do

1-26

Kód UT WoS článku

000620329400001

EID výsledku v databázi Scopus

2-s2.0-85101241296