# Adaptive Hybrid Storage Format for Sparse Matrix-Vector Multiplication on Multi-Core SIMD CPUs
## 7 Related Work  
SpMV has been extensively investigated on multi-core CPUs with SIMDs [10; 31; 32]. Recently, the effort was dedicated to new storage formats and/or adaptive autotuning frameworks for performant and scalable SpMV.  
**New sparse matrix storage formats** have been designed to enable efficient SpMV by matching various inputs to multi-core CPUs with SIMDs [3; 4; 10; 33]. [PERSON] et al. propose a sparse matrix representation CVR [21] for efficient vectorization. CVR is insensitive to the irregularity and sparseness of SpMV, so it can handle a large number of scale-free matrices on Intel Knights Landing. [PERSON] et al. proposed CSR5 [8], which is a tile-based format. This format enables high-throughput SpMV on both CPUs and GPUs for both regular  
Figure 10: The scatter diagrams show the speedup ratio of performance of HYB5-based SpMV with the optimal K and the optimal performance from using the other compared formats for each matrix on three target platforms.  
and irregular matrices. The format conversion from CSR to CSR5 is claimed to be a few SpMV operations. On Intel KNC, [PERSON] et al. identified and addressed several performance bottlenecks of SpMV [5]. They exploited the salient architecture features of KNC and used specialized data structures with careful load balancing to obtain satisfactory performance. [PERSON] et al. proposed a SIMD-friendly format SELL-C-\(\sigma\)[9]. This format is a variant of Sliced ELLPACK by reordering the rows of a matrix stored in Sliced ELLPACK, which aims to decrease the padding overhead and increase the utilization of vector units. The sorting range is determined by \(C\) and \(\sigma\). [PERSON] et al. designed a new format AAC[34] to improve the SpMV performance for Intel Xeon Phi. AAC improves the SpMV performance by avoiding indirect access to vector \(\mathbf{x}\) and reducing cache misses. This format can outperform CSR for 12 data sets. [PERSON] et al. proposed the CSR-SIMD[35] format to utilize SIMD units of ARMv8-based FT1500A and x86-based Intel Xeon Phi fully. This format compresses the non-zero elements into many variable-length pieces of data with consecutive memory access addresses to improve the accessing locality of vector \(\mathbf{x}\).  
**Adaptive optimization methods** of SpMV based on machine learning techniques have attracted interests in recent years [15; 36; 37; 38; 39; 40; 41]. This is due to the fact that the SpMV performance is determined by a combination of the storage format, the platform architecture, and the input dataset. For different architectures, there is no single format that can enable consistently better performance for all datasets. It is thus necessary to select the best matrix representation for a given architecture and data input. [PERSON] et al. employed a decision tree to build a predictive model to help choose an optimal matrix representation from five widely-used formats: CSR, CSR5, ELLPACK, SELL-C-\(\sigma\), and HYB for FT2000+ and Intel KNL [12]. Then, they analyzed the working process of the decision tree in detail [42]. [PERSON] et al. presented a deep learning mechanism for SpMV format selection best suited for a given data set [39]. They converted the matrices into graphs and directly made them inputs to the neural network eliminating the need for manually selecting features. [PERSON] et al. designed regression models and neural network-based time series prediction models to capture the influence imposed on the existing SpMV program performance by the overhead and benefits of format prediction and conversions [17].  
**Using hybrid storage formats** can leverage the advantages of both formats. HYB is the first hybrid format for SpMV optimization on the GPU [4]. It combines ELLPACK and COO as a new format HYB, which can outperform its native formats. HYB determines the segmentation position of sparse matrices with a histogram algorithm, which is outperformed by our model (Section 6.3). Our work upgrades HYB with two new native storage formats and uses machine learning to select the cutting factor.