1 INTRODUCTION

The key ingredient of the new storage technique is the observation that many matrices arising in, for example, finite element simulations have a very low matrix bandwidth (under certain permutations). That means, potentially after permutation, all non-zero matrix entries are located close to the matrix diagonal. This motivates storing the indices of these entries relative to the matrix diagonal rather than as an absolute position, which we call Diagonally-Addressed (DA) storage. Due to the small matrix bandwidth, the relative indices may be stored in a smaller (integer) data type. This technique is easily applicable to many sparse formats, for example, Compressed Sparse Rows (CSR), Block CSR (BSR), or (one of the vectors of) Coordinate (COO) storage. In this paper we apply DA storage to the Compressed Sparse Rows (CSR) format; obtaining the Diagonally-Addressed CSR (DA-CSR) format; and compare the SpMV performance against our implementation of CSR as well as the Intel Math Kernel Library (MKL) [4].

DA storage differs from Diagonal (DIA) storage in that the new technique still requires one index per non-zero, depending on the underlying technique, instead of one index per diagonal. Also, it does not impose a diagonal-major order of the entries, or require a potentially padded and full/dense storage for each of the diagonals. The Recursive Sparse Blocks (RSB) format [5] is another data structure for sparse matrices motivated by a cache-efficient and parallel implementation of the SpMV product. It divides a sparse matrix into a tree structure of sparse blocks, whose leaves are iterated in a Z- or Morton-order. The leaf blocks are stored in the COO, CSR, or Compressed Sparse Columns (CSC) format.

RSB was designed for arbitrary sparse matrices, in particular, matrices without an inherent low bandwidth (under certain permutations). RSB allows 16 bit indices as well, but only for its leaf matrices. Meanwhile, DA-CSR has a conceptually simpler non-recursive design, allowing 16 bit indices throughout, which leads to a much lower overhead in terms of Byte per non-zero. Therefore, DA storage does not directly compete with the RSB format, but could be used in the leaf blocks within the RSB format, to allow for an even smaller index type.

The remainder of this paper is structured as follows. Section 2 applies DA storage to the CSR format. Section 3 describes the selection of test matrices. Section 4 describes how to compute the SpMV product using that new DA-CSR format, and measures the performance of SpMV. We conclude the paper in Section 5.

2 DIAGONALLY-ADDRESSED STORAGE

The CSR storage of a matrix $$A\in {\mathbb{F}}^{\mathrm{nrows}\ensuremath{\times{}}\mathrm{ncols}}$$ comprises three vectors, compare Listing 1, where nnz denotes the number of non-zero entries, oindex_t and iindex_t are integer data types, and scalar_t is an approximation of $$\mathbb {F}$$, for example, IEEE 754 $$\mathtt {double}$$ or $$\mathtt {float}$$ for $$\mathbb {F}=\mathbb {R}$$. The “row pointers” stored in $$\mathtt {rowptr}$$ and “column indices” stored in $$\mathtt {colids}$$ do the bookkeeping imposed by only storing non-zero matrix entries.

The rth entry $$0 \le \texttt {rowptr}\,[r] < \texttt {nnz}$$ is the index into $$\mathtt {colids}$$ and $$\mathtt {values}$$ corresponding to the first non-zero of row r, $$0\le r\le \mathrm{nrows}$$.1 The ith entry $$\mathtt {colids}[i]$$ is the column index and $$\mathtt {values}[i]$$ is the value of the ith non-zero, $$0\le i<\mathrm{nnz}$$. Let w denote the matrix bandwidth of $$A=(a_{rc})$$, i.e. the farthest distance of a non-zero matrix entry from the matrix diagonal,

$$$$\begin{equation} w:=\max \operatorname{\{}|c-r|:{a}_{\textit{rc}}\ne 0\}\ll \mathrm{ncols}. \end{equation}$$$$(2)

For CSR storage, $$\text{\texttt {colids[$i$]}} = c_i$$, which lies in the range [0, ncols). For DA-CSR storage, $$\text{\texttt {colids[$i$]}} = c_i - r_i$$, which instead lies in the range $$[-w,w]$$. We illustrate this transformation in the following example.

Example 2.1.The sample matrix shown in Figure 1 has $$\mathrm{nrows}=\mathrm{ncols}=4$$, nnz = 5, and $$w=1$$. Its CSR representation is given by

(3)

while the DA storage replaces colids to become

(4)

Observe that colids covers its full range in either storage scheme: [0, ncols − 1] for CSR and $$[-w,w]$$ for DA-CSR.

Sometimes it is necessary to reduce the bandwidth of a matrix before DA storage can be applied effectively, which we observe in the next example.

For matrices with more than a few non-zeros per row, it is therefore reasonable to ignore the effect of oindex_t, i.e. to assume $${\texttt {sizeof(oindex\_t)}}=0$$. The final percentages of the previous example would then be estimated by $$\tfrac{1}{6}$$ and $$\tfrac{1}{4}$$. Figure 3 shows this approximate reduction in matrix-related traffic by means of formula (5). Note how smaller iindex_t; i.e. lower bookkeeping traffic; yield better approximations of the factor $$\tfrac{1}{2}$$ observed for dense storage.4 Recall that by Equation (1) a traffic reduction is tightly coupled with expected performance gains for memory-bound operations.

While the goal of multi-precision algorithms is to exchange scalar_t for a smaller data type (as in, for example, [8]), i.e. traversing the rows of Figure 3, DA storage focuses on iindex_t, i.e. traversing the columns of Figure 3. However, as the main motivation of multi-precision algorithms is the memory bottleneck, DA storage is expected to enable even larger speedups in that context. CSR using 64 bit scalars and 32 bit indices merely allows for a $$\tfrac{3}{2}\times$$ performance speedup when switching to 32 bit scalars. Meanwhile, if the matrix has a representation in DA-CSR using 16 bit indices, the expected speedup is $$\tfrac{5}{3}\times$$. This speedup is much closer to the 2 × possible for dense storage, when using a scalar type half the size.

3 SELECTION OF MATRICES

The SuiteSparse Matrix Collection [6] contains 1367 square matrices having a CSR representation using 32 bit indices and a full structural rank.5 Only 993 of these matrices (72.6%) have a dimension less than 2¹⁵, i.e. fit into CSR using 16 bit column indices. However, for 1302 matrices (95.2%) there exists a permutation that reduces the matrix bandwidth to below 2¹⁵, such that these matrices fit into DA-CSR using 16 bit column indices. These are the matrices we select for further investigation.

Some of the investigated matrices are already stored in a bandwidth-reduced way. We applied an RCM reordering [7] to the ones that are not. Unfortunately, our implementation of the RCM permutation has not been able to sufficiently reduce the bandwidth of two matrices (Janna/Long_Coup_dt0 and Janna/Long_Coup_dt6), which reduces the number of matrices to 1300 (95.1%).

4 SPARSE MATRIX VECTOR PRODUCT

4.2 Numerical results

For traffic within the size of the L1 cache, a single thread yields the best performance. Up to about 100 KiB, which is well within the size of a single L2 cache, the optimum number of threads increases gradually. For traffic larger than that, the maximum number of threads yields the best performance. This behavior is irrespective of the matrix format and the implementation vendor (ourselves or MKL [4]).

Our implementation of the SpMV product for the CSR format using 32 bit indices performs about the same as the MKL [4], see Table 1. Figure 4 shows the comparison of DA-CSR using 16 bit column indices to CSR. Using DA-CSR shows almost no change for traffic within the combined size of the L2 caches, i.e. up to $$8\cdot 1\ \text{MiB}$$. For traffic larger than that, up to the combined size of all caches, i.e. up to about 8 + 11 MiB, we observe a larger than 1.4 × speedup. For traffic beyond that, we observe an average speedup of about +17.5%, which is reasonably close to the expected +20%. However, the throughput drops slightly, indicating some unused potential on the given hardware. See Table 2 for the comparison of DA-CSR to MKL [4].

TABLE 1. Average relative performance of our best SpMV implementation for CSR using 32 bit indices w.r.t. MKL [4] as the baseline. Values >1 mean we are faster.

Traffic	Singlethreaded	Multithreaded
L1d	1.131	1.129
L2	1.073	1.044
L3	1.012	1.011
Large	0.982	0.994

• Abbreviations: CSR, Compressed Sparse Rows; MKL, Math Kernel Library; SpMV, Sparse Matrix Vector.

TABLE 2. Average relative performance of our best SpMV implementation for DA-CSR using 16 bit column indices w.r.t. MKL [4] as the baseline. Values >1 mean we are faster.

Traffic	Single-threaded	Multithreaded
L1d	1.103	1.098
L2	1.073	1.055
L3	1.052	1.032
Large	1.110	1.172

• Abbreviations: CSR, Compressed Sparse Rows; DA, Diagonally-Addressed; MKL, Math Kernel Library; SpMV, Sparse Matrix Vector.

Remark 4.2. (CSR using 16 bit column indices)Recall that 933 matrices have a direct representation in CSR using smaller column indices. The DA-CSR format performs on par with CSR using the same index types for these matrices.

5 CONCLUSION AND OUTLOOK

DA storage allows to nearly halve the bookkeeping traffic in sparse matrix storage formats, when the matrix bandwidth allows for an index type half the size. On the hardware used, DA-CSR storage with 16 bit column indices improves the multithreaded SpMV performance over CSR storage with 32 bit column indices by more than 17%, for both our implementation and MKL [4] if the traffic exceeds the size of the L3 cache of the CPU. Meanwhile, DA-CSR performs no worse than CSR when using the same data types.