EFFICIENT SPARSE MATRIX-VECTOR MULTIPLICATION ON PARALLEL PROCESSORS

摘要

A method of multiplication of a sparse matrix and a vector to obtain a new vector and a system for implementing the method are claimed. Embodiments of the method are intended to optimize the performance of sparse matrix-vector multiplication in highly parallel processors, such as GPUs. The sparse matrix is stored in compressed sparse row (CSR) format.

主权项

1. A method of multiplication of a sparse matrix and a vector to obtain a new vector, the sparse matrix being stored in compressed sparse row (CSR) format, the method to be executed on a parallel processor, the method comprising:
partitioning the matrix into blocks of consecutive rows; and for each of said blocks having more than a minimum number of rows:
determining a number of non-zero matrix elements in the block;executing a first process for sparse-matrix vector multiplication on rows of the block if a number of non-zero matrix elements in the block is less than or equal to a maximum; andexecuting a second process for sparse-matrix vector multiplication, distinct from the first process, if the number of non-zero matrix elements is greater than the maximum.