File SellMatrix.h

↰ Parent directory (ADS/numeric)

A sparse matrix in the format SELL-C-sigma of Kreutzer, Hager, Wellein, Fehske and Bishop, beyond the book: the rows, sorted by their number of nonzeros within windows of sigma consecutive rows, go in chunks of C rows, and each chunk keeps its nonzeros by columns of the chunk, the k-th nonzero of its C rows side by side, padded with zeros to the longest of its rows.

Definition (ADS/numeric/SellMatrix.h)

Detailed Description

The product y = A x then runs the C rows of a chunk in the C lanes of the vector registers (C = 8 doubles for AVX-512, 4 for AVX2), the values and the columns of a step loaded in one stream and x gathered, instead of one row at a time with a reduction at its end, as in CSR [see File CsrMatrix.h]. The sort within the windows makes the rows of a chunk nearly as long, so that the padding, :math:` sum_c C max_{i in c} r_i - nnz ` for the chunks c and the row lengths :math:` r_i , is small (none on the rows of equal length of a stencil), while a window of :math: sigma ll m ` rows keeps the rows near their place and so the reads of x and the writes of y near each other.

  • The matrix is built from a CsrMatrix in O( nnz + m log sigma ) time: the sort of each window by row length (stable, so that rows of equal length keep their order), the widths of the chunks, and the placement of the nonzeros; it takes :math:` 12 ( nnz + pad ) + 8 m / C + 4 m ` bytes: the values and the columns, the offset and the width of each chunk, and the permutation of the rows.

  • multiply() is y = A x: for each chunk, C sums in the lanes over the width of the chunk, then each sum written to its row; :math:` 2 ( nnz + pad ) ` operations, all of them in full vectors.

The contracts [see File Contract.h]: sigma >= 1 and m < 2^32; x has n entries and y m entries. The functions are defined in SellMatrix.tpp.

  1. Kreutzer, G. Hager, G. Wellein, H. Fehske, A. R. Bishop, A unified sparse matrix data format for efficient general sparse matrix-vector multiplication on modern processors with wide SIMD units, SIAM Journal on Scientific Computing 36(5), C401-C423, 2014, doi:10.1137/130930352

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes