## 3 Materials and Methods  
Our proposed methodology consists of three main phases: data preparation, feature extraction, and predictions using different machine learning algorithms. For data preparation, we collected nearly 700 matrices from multi-disciplinary application domains. The features were extracted by exploiting the structure of the sparse matrix. The training set comprises different features along with the block size for which the minimum execution time is obtained. The predictive model predicts the block size and is validated against arbitrary matrices. Selecting the correct set of features is important for the effective implementation of a predictive model. The overfitting issue arises when the number of features is excessively large for the training set. Therefore, dimensionality reduction and feature selection are very important to avoid overfitting.  
Let \(\mathrm{n_{b}}\) be the number of blocks and \(\mathrm{T_{i}}\) represent the execution time of the \(\mathrm{i_{th}}\) matrix where \(0<\mathrm{i}<\mathrm{N}\) and \(\mathrm{N}\) is the total number of matrices in our dataset. Execution time of each matrix is recorded against different number of blocks; minimum and maximum time is recorded accordingly.  
\[\mathrm{t_{i\mathrm{max}}}=\mathrm{max}(\mathrm{t_{i}},\mathrm{t_{2}}\, \ldots,\mathrm{t_{nb}}) \tag{4}\]  
\[\mathrm{t_{i\mathrm{min}}}=\mathrm{min}(\mathrm{t_{i}},\mathrm{t_{2}}\, \ldots,\mathrm{t_{nb}}) \tag{5}\]  
where nb is the Total number of blocks.  
\[\mathrm{t_{i\mathrm{avg}}}=\sum_{\mathrm{i}=1}^{\mathrm{i=nb}}\frac{\mathrm{t_ {i}}}{\mathrm{nb}} \tag{6}\]  
\(\mathrm{t_{i\mathrm{avg}}}\) is calculated time when ever random block size is chosen for the execution.  
For the predictions, related to performance optimization of SpMV in shared memory system via machine learning models, we followed the subsequent key steps:  
1. Collection of real-world matrices from multi-disciplinary domains, sourced from Suit Sparse matrix market Collection (UOF) [35].
2. Conversion of sparse matrices from matrix market format to block CSR and SpMV computation using different block sizes. The SpMV computations are performed 2000 times for each sparse matrix using different block sizes.
3. We prepared sparse matrices dataset by recording SpMV execution time and their corresponding block sizes (Step 4). Furthermore, we utilized them in the training and testing process (Steps 5 and 6).  
* We have extracted set of SpMV features by utilizing the structure of the matrix along with a block size for which the minimum execution time is obtained.
* We used different machine learning models to find the near optimal block size.
* We evaluated the accuracy of the predictive models by using two metrics, mean absolute error and relative mean error.  
SpMV computations, features extraction and training are represented in the following proposed Algorithm 1.  
```
1 A : is the input matrix
2 f : is the output features
3 n: is the number of matrices
4 A\({}^{\prime}\): is matrix in block CSR Format
5 n\({}_{\text{b}}\): is the number of blocks
6 Function feature SpMV(A:in, f:out,tmin :out, n\({}_{\text{b}}\):out)
7 for J = 1 to J \(<=n\) do
8 convert matrix to Block CSR
9 A\({}^{\prime}_{\text{j}}\)\(\leftarrow\)A\({}_{\text{j}}\)
10 extract required features
11 f\({}_{\text{j}}\)\(\leftarrow\)extract features of A\({}^{\prime}_{\text{j}}\)
12 end for
13 for k = 1 to k \(<=n_{\text{b}}\) do
14 for i = 1 to i = 2k do
15 cal_exe_time[i]\(\leftarrow\)Call SPMV(A\({}^{\prime}_{\text{j}}\), x)
16 Where x is the dense vector
```  
**Algorithm 1**Algorithm of SpMV using Block CSR