# Adaptive Hybrid Storage Format for Sparse Matrix-Vector Multiplication on Multi-Core SIMD CPUs
## 3 Motivation  
This section presents the motivation of our work and outlines the design choices of our approach. **Why using a hybrid format? ** Studies have shown that no single matrix storage format performs best across matrix datasets and/or architectures [11; 12]. As a result, work has been proposed to build an analytical model to pick an optimal storage format for a given dataset and architecture [18]. However, such an approach requires managing various storage formats in a single program, and the overhead of format conversion could be non-negligible during the runtime. As an alternative, a hybrid storage format works by mixing two (or more) native formats in a single framework. Recent works [4; 11] have demonstrated the promising results of a hybrid scheme. Our work builds upon these recent works by proposing a new hybrid scheme to target the emerging multi-core architectures. Why combine SELL-C-\(\sigma\) and CSR5?As we will show later in Section 6, CSR5 [8] and SELL-C-\(\sigma\)[9] are two well-performing sparse matrix storage format on multi-core architectures. Figure 2 shows the performance measurements of the two storage formats on KNL when applying the respective SpMV kernel to 956 matrices. Here, the x-axis shows the regularity (denoted as variation) of the input matrix. The variation is calculated by computing the standard deviation of non-zero elements on the row dimension of the input matrix. Therefore, the larger the variation is, the more irregular the matrix will be. Overall, we see that CSR5 (marked with red triangles) performs better than SELL-C-\(\sigma\) (marked with blue plus) for irregular matrices (i.e., when variation is large), while SELL-C-\(\sigma\) performs better for the regular matrices (i.e., when variation is small). It can be observed from Figure 2 that CSR5 works better when variation is large. Therefore, we expect that a hybrid storage format combining these native formats would exploit the advantages of both worlds by storing the left few non-zero elements per row in SELL-C-\(\sigma\) and the remaining (possibly irregular) non-zero elements in CSR5. Figure 3 shows that our approach, namely HYB5 (SELL-C-\(\sigma\)+CSR5), significantly outperforms HYB (ELL+COO) on KNL when using a right-partitioning parameter \(K\). Why is choosing the right K important?Figure 3 shows how the SpMV performance changes over the partition parameter K for the cage12 and Cube_Coup_dt0 matrix from the SuiteSparse matrix collection [23] on Intel KNL (Section 6.1). We note that using a right K gives significant performance benefit over SELL-C-\(\sigma\) and CSR5. However, an inappropriate K setting can also hurt performance seriously, as shown by the point marked with **A**. Thus, selecting a suitable partitioning parameter K is of great significance for the SpMV performance. Therefore, to unlock the potential of our hybrid scheme, we also develop a scheme to dynamically determine the right K on a per matrix basis. Figure 3 also shows the performance of the prior analytical models: average[12], histogram[4], and opt_storage[19]. We note that the histogram model outperforms the  
Figure 2: SpMV performance of SELL-8-512 and CSR5 for SpMV performs on matrices with different irregularities (variations). The larger the variation is, the more irregularity a matrix has. average and opt_storage one for cage12, while their performance is the other way around for Cube_Coup_dt0. For both cases, the obtained SpMV performance via the analytical models is not the best. This is due to the fact that the selection of K depends not only on the input matrix features, but also on the underlying architectures and native storage formats. These first two models can only capture the input matrix features. The opt_storage threshold selection is based on minimizing the memory footprint of the HYB matrix format.