## 4 SURAA: The Proposed Method and Tool  
Load-balanced execution and coalesced memory access are the two crucial factors that we consider to improve the performance of SpMV. A load-balanced execution balances the workload of the threads and eradicates idle threads. When a group of consecutive threads accesses consecutive memory locations, we call it coalesced memory access. Coalesced memory access tremendously improves the throughput of data access from global memory and hence improves the SpMV performance. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Work** & **Coalesced** & **Load** & **Mem.** & **Pre-** & **Cache** & **Thread** \\  & **Access** & **Balanced** & **Bandwidth** & **Processing** & **Locality** & **Divergence** \\ \hline JAD [65; 66] & Yes & No & No & Yes & No & No \\ BCSR [68] & No & No & Yes & No & No & No \\ ELL-R [3] & Yes & No & Yes & No & No & No \\ TJDS [67] & No & No & Yes & Yes & No & No \\ pJDS [70] & Yes & Yes & Yes & Yes & No & No \\ ELLR-T [69; 71] & Yes & Yes & No & No & No & Yes \\ Sliced ELLL 7 [73] & No & Yes & Yes & Yes & No & No \\ SELLL-T [72] & No & Yes & Yes & Yes & No & Yes \\ SELL-C-\(\sigma\) [75] & No & Yes & Yes & Yes & No & No \\ SELL-P [10] & No & Yes & Yes & Yes & No & No \\ Adaptive ELL [11] & No & Yes & No & Yes & Yes & No \\ Adaptive CSR [12] & Yes & No & No & No & Yes & Yes \\ [PERSON] et al. [78] & Yes & Yes & No & Yes & No & No \\ CSR5 [12] & Yes & Yes & Yes & Yes & No & No \\ \hline \hline \end{tabular}  
* 1 Jagged Array Diagonals. 2 Blocked Compressed Sparse Row. 3 Jagged Diagonals. 4 Transposed Jagged Array Diagonals. 5 Padded Jagged Diagonals. 6 Ellpack Rows Thread. 7 Sliced Ellpack. 8 Sliced Ellpack Rows-Thread. 9 Sliced Ellpack-C. 10 Sliced Ellpack-P. 11 Ellpack. 12 Compressed Sparse Row.  
\end{table} 
Table 1: Comparative analysis of various discussed features in discussed sparse matrix-vector (SpMV) multiplication techniques. The two major CSR based algorithms are the CSR scalar and the vector CSR (VCSR). The issue with scalar CSR is that it does not correctly balance workload as one thread is assigned per row. This results in imbalanced workload for the threads in a warp. The vector CSR rectifies this issue by assigning threads equal to the number of warps (32 threads) equal to closest power of the mean number of the non-zero per row on the GPU. Matrices that have a uniform number of non-zeros per row and are a multiple of a warp accelerates the SpMV. However, there are many matrices with less number of nnz per row, especially the matrices with the number of non-zeros per row less than sixteen. These matrices are not efficiently executed by VCSR as many GPU threads remain idle while the other threads in a warp are under execution. Therefore, warps that are assigned to rows with a substantial number of nonzeroes per row lag behind other warps with a fewer number of the non-zero per row. Hence, it is essential to consider the sparsity structure and coalesced memory access to derive benefit from the merits and avoid the flaws of both the scalar and vector CSR techniques. To this end, we develop a load balanced dynamic technique based on the CSR storage format called SUAAA. SUAAA uses sorting, segmentation, asynchronous kernels, streams, and dynamic parallelism. Sorting is used to bring all the rows with similar non-zero elements together and segmentation is used to divide the work into manageable blocks to distribute the workload evenly. Dynamic kernel enables us to launch multiple child kernels from within the parent kernel which can efficiently execute the sorted segments. The terminologies and the data structures used are illustrated in Table 2. The format is very similar to the CSR format, except that we introduce an array named _perm_ to store the sorted indices. _perm_ is of size \(m\). A temporary vector, _nprv_, of size \(m\) is generated to speed up the pre-processing (sorting), which stores the number of non zero elements per row. In the rest of the paper, we shall use the terminologies defined in the Table 2 for our discussions.