# Adaptive Hybrid Storage Format for Sparse Matrix-Vector Multiplication on Multi-Core SIMD CPUs
## 2 Background
### Sparse Matrix Storage Format  
Due to a large number of zeros existing in sparse matrices, using dense matrix formats will lead to a waste of storage and computing resources. Thus, researchers have invented various sparse matrix storage formats, i.e., merely storing the non-zero elements and their indices of a matrix. Figure 1: A SpMV example with a \(4\times 4\) matrix and a vector. **COO** The _coordinate_ (COO) format (i.e., JIV format) is a particularly simple storage scheme. The arrays row, col, and data are used to store the row indices, column indices, and values of the non-zero elements. This format is a general sparse matrix representation because the required storage is always proportional to the number of non-zero elements for any sparsity pattern. Different from other formats, COO stores explicitly both row indices and column indices. Table 1 shows an example matrix in the COO format. **CSR** The _compressed sparse row_ (CSR) format is the most popular general-purpose sparse matrix representation. This format explicitly stores column indices and non-zero elements in array indices and data, and uses a third array ptr to store the starting nonzero index of each row in the sparse matrix (i.e., row pointers). For an \(M\times N\) matrix, ptr is sized of \(M+1\) and stores the offset into the \(i^{th}\) row in ptr[i]. Thus, the last entry of ptr is the total number of non-zero elements. Table 1 illustrates an example matrix represented in CSR. We see that the CSR format is a natural extension of the COO format by using a compressed scheme. In this way, CSR can reduce the storage requirement. More importantly, the introduced ptr facilitates a fast query of matrix values and other interesting quantities, such as the number of non-zero elements in a particular row. \begin{table}
\begin{tabular}{c c} \hline \hline
**Representation** & **Specific Values** \\ \hline COO & \(row=[0,0,1,1,1,2,3,3]\) \\  & \(col=[1,2,0,2,3,2,1,2]\) \\  & \(data=[6,1,2,8,3,4,7,5]\) \\  & \(ptr=[0,2,5,6,8]\) \\ CSR & \(indices=[1,2,0,2,3,2,1,2]\) \\  & \(data=[6,1,2,8,3,4,7,5]\) \\  & \(ptr=[0,2,5,6,8]\) \\  & \(ptr=[0,2,5,6,8]\) \\  & \(title\_ptr=[0,2,5,6,8]\) \\ CSR5 & \(title\_des:bit\_flag=[T,T,F,F|T,T,T,F]\), \\  & \(y\_off=[0,1|0,2],seg\_off=[0,0|0,0]\) \\  & \(indices=[1,0,2,2|3,1,2,2]\) \\  & \(data=[6,2,1,8,3,7,4,5]\) \\ ELL & \(data=\left[\begin{array}{ccc}6&1&*\\ 2&8&3\\ 4&*&*\\ 7&5&*\end{array}\right]\) \\  & \(indices=\left[\begin{array}{ccc}1&2&*\\ 0&2&3\\ 2&*&*\\ 1&2&*\end{array}\right]\) \\ SELL & \(data=\left[\begin{array}{ccc}6&1&*\\ 2&8&3\\ 4&*&*\\ 7&5&*\end{array}\right]\) \\  & \(slices=[3,2]\) \\ SELL-C-\(\sigma\) & \(data=\left[\begin{array}{ccc}2&8&3\\ 6&1&*\\ 7&5&*\end{array}\right]\) \\  & \(slices=[3,2]\) \\  & & \(slices=[3,2]\) \\  & & \(slices=[3,2]\) \\ HYB & ELL:\(data=\left[\begin{array}{ccc}6&1\\ 2&8\\ 4&*\\ 7&5\end{array}\right]\) \\  & \(\begin{array}{ccc}\text{COO:}row=[1],col=[3],data=[3]\\ \end{array}\) \\ CVR & \(data=\left[\begin{array}{ccc}6&2\\ 1&8\\ 4&3\\ 7&5\end{array}\right]\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Matrix storage formats and their data structures for the sparse matrix shown in Figure 1.  
**CSR5** To achieve near-optimal load balance for matrices with any sparsity structures, CSR5 first evenly partitions all nonzero entries to multiple 2D tiles of the same size. Thus, when executing parallel SpMV operation, a compute core can consume one or more 2D tiles, and each SIMD lane of the core can deal with one column of a tile. Then the main skeleton of the CSR5 format is simply a group of 2D tiles. The CSR5 format has two tuning parameters, \(\omega\) and \(\sigma\), where \(\omega\) is a tile's width and \(\sigma\) is its height, which is set to the size of the SIMD execution unit and on-chip memory strategy of the processor, respectively. CSR5 is an extension to the CSR format [8]. Apart from the three data structures from CSR, CSR5 introduces another two data structures: a tile pointer tile_ptr and a tile descriptor tile_des.