Fast Sparse Matrix-Vector Multiplication on GPUs for Graph Applications
Fast Sparse Matrix-Vector Multiplication on GPUs for Graph Applications
复制标题
DOI：
10.1109/sc.2014.69
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Arash Ashari;N. Sedaghati;John Eisenlohr;S. Parthasarathy;P. Sadayappan
中科院分区：
文献类型：
--
作者：
Arash Ashari;N. Sedaghati;John Eisenlohr;S. Parthasarathy;P. Sadayappan
稀疏矩阵向量乘法（SpMV）是一种广泛使用的计算内核。稀疏矩阵最常用的格式是CSR（压缩稀疏行），但最近开发了许多其他表示，以实现更高的SpMV性能。然而，替代表示通常强加显著的预处理开销。虽然对于需要使用相同矩阵的SpMV的多次迭代调用的应用程序，可以分摊高预处理开销，但它并不总是可行的-例如在分析大型动态演化图时。本文介绍了ACSR，自适应SpMV算法，使用标准的CSR格式，但减少线程的分歧，结合成组（箱），具有类似数量的非零元素的行。此外，对于跨越宽范围的非零计数的仓中的行，利用动态并行性。ACSR相对于其他提出的SpMV方法的一个显著优点是，它直接与标准CSR格式一起工作，从而避免了显著的预处理开销。ACSR的CUDA实现在表示幂律图的一组稀疏矩阵上的表现优于NVIDIA CUSP和cuSPARSE库中的SpMV实现。我们还演示了使用ACSR的动态图的分析，其中现有的方法的改进甚至更高。
Sparse matrix-vector multiplication (SpMV) is a widely used computational kernel. The most commonly used format for a sparse matrix is CSR (Compressed Sparse Row), but a number of other representations have recently been developed that achieve higher SpMV performance. However, the alternative representations typically impose a significant preprocessing overhead. While a high preprocessing overhead can be amortized for applications requiring many iterative invocations of SpMV that use the same matrix, it is not always feasible -- for instance when analyzing large dynamically evolving graphs. This paper presents ACSR, an adaptive SpMV algorithm that uses the standard CSR format but reduces thread divergence by combining rows into groups (bins) which have a similar number of non-zero elements. Further, for rows in bins that span a wide range of non zero counts, dynamic parallelism is leveraged. A significant benefit of ACSR over other proposed SpMV approaches is that it works directly with the standard CSR format, and thus avoids significant preprocessing overheads. A CUDA implementation of ACSR is shown to outperform SpMV implementations in the NVIDIA CUSP and cuSPARSE libraries on a set of sparse matrices representing power-law graphs. We also demonstrate the use of ACSR for the analysis of dynamic graphs, where the improvement over extant approaches is even higher.