Parallelization of Reordering Algorithms for Bandwidth and Wavefront Reduction
Parallelization of Reordering Algorithms for Bandwidth and Wavefront Reduction
复制标题
DOI：
10.1109/sc.2014.80
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
Konstantinos I. Karantasis;Andrew Lenharth;Donald Nguyen;M. Garzarán;K. Pingali
中科院分区：
文献类型：
--
作者：
Konstantinos I. Karantasis;Andrew Lenharth;Donald Nguyen;M. Garzarán;K. Pingali
如果首先对矩阵进行重新排序，则可以加速许多稀疏矩阵计算。重新排序最初是为直接方法开发的，但最近为了改善并行迭代求解器的缓存局部性而流行起来，因为重新排序矩阵以减少带宽和波前可以改善稀疏矩阵-向量乘(SpMV)的引用局部性，稀疏矩阵向量乘法是迭代求解器中的关键核心。在本文中，我们提出了两个广泛使用的重排算法的首次并行实现：反向切割Hill-McKee(RCM)算法和Sloan算法。在Stampede超级计算机的16核上，我们的并行RCM平均比HSL库中最先进的RCM顺序实现快5.56倍。SLON比RCM有更多的限制，但我们的并行实现比顺序HSL-SLON平均加速2.88倍。使用我们的并行RCM重新排序矩阵，然后执行100次SpMV迭代比使用HSL-RCM然后执行SpMV迭代的速度快一倍，也比不重新排序矩阵的情况下执行SpMV迭代快1.5倍。
Many sparse matrix computations can be speeded up if the matrix is first reordered. Reordering was originally developed for direct methods but it has recently become popular for improving the cache locality of parallel iterative solvers since reordering the matrix to reduce bandwidth and wave front can improve the locality of reference of sparse matrix-vector multiplication (SpMV), the key kernel in iterative solvers. In this paper, we present the first parallel implementations of two widely used reordering algorithms: Reverse Cut hill-McKee (RCM) and Sloan. On 16 cores of the Stampede supercomputer, our parallel RCM is 5.56 times faster on the average than a state-of-the-art sequential implementation of RCM in the HSL library. Sloan is significantly more constrained than RCM, but our parallel implementation achieves a speedup of 2.88X on the average over sequential HSL-Sloan. Reordering the matrix using our parallel RCM and then performing 100 SpMV iterations is twice as fast as using HSL-RCM and then performing the SpMV iterations, it is also 1.5 times faster than performing the SpMV iterations without reordering the matrix.