## 1 Introduction
To the best of our knowledge, no other work exists that used the Freedman-Diaconis rule for SpMV computations the way we used, or used adaptive kernels the way we have done in this paper. The segments are assembled into three groups based on the mean \(npr\) of the segments. For each group, we use multiple kernels to execute the group segments on different streams. Hence, the number of threads to execute each segment is adaptively chosen. Dynamic parallelism available in Nvidia GPUs (Major Version 3.5, NVIDIA Corporation, Santa Clara, CA, USA) is utilized to execute the group containing segments with the largest mean \(npr\), providing improved load balancing and coalesced memory access, and hence more efficient SpMV computations on GPUs. Note that the row segments in SURAA are dynamically scheduled by the dynamic kernel and are executed at the same time using the hardware streams on the GPU. The use of multiple streams provides higher performance by hiding the kernel launch overhead. This could be considered as reducing the kernel launch overhead, with the exception that the number of dynamic kernels that can be executed on GPU in parallel depends on the number of available Streaming Processors because the number is fixed for a given GPU. The number of segments that are added to the dynamically executed group is tunable. In our experiments, we find that depending upon the structure of the matrices, tuning the size of dynamically executed group enhances the performance of the scheme; see Section 4.4. We implement the SURAA method as a tool and compare its performance with the de facto best commercial (cuSPARSE) and open source (CUSP) tools using widely used benchmarks comprising 26 matrices from 13 diverse domains. A total of seven other SpMV storage and computation techniques have been compared with SURAA. We have used three widely used performance metrics to evaluate SURAA and other techniques; throughput in Giga Floating Point Operations per second(GFLOP/s), speedup, and effective memory bandwidth (GB/s). Each scheme is also evaluated in terms of their performance with increasing \(npr\ variance\) (variance in the number of non-zeros per row) and \(nnz\) (the total number of non-zeros in the matrix). On average, SURAA outperforms all other seven SpMV computation methods by achieving an average speedup of \(40\times\) for SELL-P, \(29.89\times\) against WPK1, \(12.98\times\) for CSR, \(11.33\times\) for BSR, \(1.50\times\) for HYB, \(1.15\times\) for WPK2, and \(1.1\times\) for CSR5. SURAA provides the best throughput for 20 matrices out of the 26 matrices in the benchmark dataset. The average collective speedup of SURAA against all the other schemes is \(13.99\times\). The highest speedups achieved by SURAA against other schemes for any single matrix are \(562\times\), \(531.56\times\), \(147\times\), \(26.70\times\), \(3.06\times\), \(1.97\times\), and \(1.94\times\) against SELL-P, WPK1, CSR, BSR, HYB, WPK2, and CSR5, respectively. We repeat for clarity that these are SURAA's peak performance values against specific storage schemes for any single matrix. SURAA provides the highest \(mean\) throughput (GFLOP/s) of \(15.75\), followed by \(14.28\) for CSR5. SURAA also leads the table with the highest \(max\) throughput value of \(36.70\) GFLOP/s, followed by \(26.8\) for SELL-P. SURAA also provides the highest effective memory bandwidth of \(226.25\) GB/s compared to the second best \(160.75\) GB/s for SELL-P. SURAA also demonstrates a much lower setup overhead, equal to five SpMV execution time, compared to \(69\) and \(95.5\) SpMV executions for SELL-P and CSR5. An important aspect of our analysis reveals (see Section 5.4, Page 24) that SURAA comparatively delivers higher performance with the increase in the \(npr\ variance\) and \(nnz\). SURAA achieved the highest throughput (GFLOP/s) among all the schemes for the highest \(npr\ variance\) matrices. We note that the speedup of SURAA against CSR5 and WPK2 was small, however, SURAA provided the highest throughput for 20 out of 26 matrices.