US 2018/0121388 A1 · SYMMETRIC BLOCK SPARSE MATRIX-VECTOR MULTIPLICATION

Abstract

Embodiments of the present invention are directed to methods and systems for performing block sparse matrix-vector multiplications with improved efficiency through the use of a specific re-ordering the matrix data such that matrix symmetry can be exploited while simultaneously avoiding atomic memory operations or the need for inefficient memory operations in general. One disclosed method includes reordering the matrix data such that, for any column of non-transpose data, and for any row of transpose data simultaneously processed within a single thread-block on a GPU, all matrix elements update independent elements of the output vector. Using the method, the amount of data required to represent the sparse matrix can be reduced by as much as 50%, thereby doubling the effective performance on the GPU, and doubling the size of the matrix that can be accelerated by the GPU.

Claims27

Dependent claims

A method for performing block sparse matrix calculations on a symmetric portion of a block sparse matrix, the method comprising:

receiving, as input, a linear system represented by the block sparse matrix and an input vector, wherein the block sparse matrix comprises a plurality of dense matrix blocks, wherein the dense matrix blocks comprise the symmetric portion;
re-arranging a plurality of values of the block sparse matrix such that for each column of a matrix block of the plurality of symmetric matrix blocks, each successive row of the matrix block is offset by a constant value from an immediately preceding row;
re-arranging one or more of the symmetric matrix blocks such that none of the plurality of symmetric matrix blocks share row values with a transpose of a concurrently processed matrix block;
calculating a product of the block sparse matrix with the input vector in a plurality of streaming multi-processors (SMs) disposed in the GPU;
and
storing the product in an output vector,
wherein the output vector is distributed in a plurality of portions, a portion corresponding to an SM and being stored in registers and/or the shared memory corresponding to the SM.

4 more elements

Dependencies are inferred from the claim text.

Symmetric block sparse matrix-vector multiplication

Life of this patent

Symmetric block sparse matrix-vector multiplication

Life of this patent

Abstract

Claims27