2013/12/04 by Albert-Jan N. Yzelman, Dirk Roose · 1 citation
Computer Science · #Parallel Computing and Optimization Techniques #Distributed and Parallel Computing Systems #Advanced Data Storage Technologies
paper · doi:10.1109/tpds.2013.31
openalex publication_date 2013/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
The sparse matrix-vector multiplication is an important computational kernel, but is hard to efficiently execute even in the sequential case. The problems--namely low arithmetic intensity, inefficient cache use, and limited memory bandwidth--are magnified as the core count on shared-memory parallel architectures increases. Existing techniques are discussed in detail, and categorized chiefly based on their distribution types. Based on this, new parallelization techniques are proposed. The theoretical scalability and memory usage of the various strategies are analyzed, and experiments on multiple NUMA architectures confirm the validity of the results. One of the newly proposed methods attains the best average result in experiments on a large set of matrices. In one of the experiments it obtains a parallel efficiency of 90 percent, while on average it performs close to 60 percent.