## 2 Literature Review
### Related Work  
Over the years, different optimization techniques have been proposed, primarily focusing on register/cache blocking [21; 22], reordering of rows/columns [19], compression [23; 24], and introduction of new storage schemes. The storage formats are generic in nature and thus can be used to store any structure of sparse matrix, but with certain performance penalty. On the other hand, most storage schemes target the optimization of matrices with specific patterns. Numerous blocking optimization techniques have been proposed but primarily focused on proposing new storage scheme. There is very little research conducted on the use of machine learning for the optimization of SpMV computation, and most of the efforts are dedicated only to automated format selection and execution time prediction based on sparse matrix features. In BCSR matrix is divided into blocks of fixed sizes and optimal block size is dependent on structure of the matrix and underlying platform. BCSR provides many advantages including loop unrolling per block, compressing indexing and other low-level optimizations but also requires excessive padding to fill the blocks with explicit zero values [24]. Bitmap based sparse matrix storage format [25] uses blocks of fixed size and only non-zero elements need to be stored in values array. Bitmaps needs to be stored that encode the non-zero structure using Bruijn sequences. Reduce memory usage resulted in the additional computation time. Similarly Block Compressed Common Coordinate (BCCOO) storage format [26] uses bit flags to point to start of the row. The use of bit array achieves high compression but ultimately requires additional array to executed in parallel with SpMV Computation. Other optimization based on BCSR [27] applicable to sparse matrices with multiple blocks appear in recurring pattern. Variable Block Length (VBL) format [28] does not have fixed size blocks and requires execution of additional loop in SpMV computation to proceed through each block. The Compressed sparse eXtended format (CSX) [29] reduces the memory footprints of a sparse matrix by compressing index information using Compressed Sparse Row Delta Unit (CSR-DU). Index reduction is achieved but on the expense of high complexity in determining the substructures with considerable overhead. Other optimizations in the literature include Compressed Sparse block (CSB) format [30] and Recursive Sparse Blocks (RSB) [31], while pattern based representation (PBR) [32] aims to reduce storage overhead and keeping locality but with additional computation overhead. All these optimization techniques required alteration at algorithmic level on the expense of additional data structure or extra computation. With fixed size blocking techniques, selection of optimal block size is still not addressed in the literature. Trial and error based manual selection of blocks size is error prone and time consuming. Even after considerable efforts we may settle up with the block size which is not optimal. The proposed methodology does not change the SpMV algorithm but instead use the matrix structure only to select the optimal block size before actual execution of SpMV computation. Recently, researchers started using machine/deep-learning techniques to optimize the performance of the SpMV kernel in both shared and distributed memory environments [33; 34; 35]. To estimate the optimal number of processes for SpMV computations of an arbitrary sparse matrix on a distributed memory computer system, in our previous work we [36] proposed a data-driven, machine learning method and tool known as ZAKI for SpMV computations. Experimental data from 2000 real-world matrices were collected from 45 heterogeneous application domains. The matrix sparsity structure was used to predict the optimum number of processes in distributed memory environments for a given matrix using various base and ensemble machine learning approaches [36].