End-to-End LU Factorization of Large Matrices on GPUs
End-to-End LU Factorization of Large Matrices on GPUs
复制标题
DOI：
10.1145/3572848.3577486
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Yang Xia;Peng Jiang;G. Agrawal;R. Ramnath
中科院分区：
文献类型：
--
作者：
Yang Xia;Peng Jiang;G. Agrawal;R. Ramnath
稀疏矩阵的LU分解是许多工程和科学问题（如电路模拟）的一个重要计算步骤。在并行化和扩展该算法方面已经做出了很多努力，包括近期针对图形处理器（GPU）的一些尝试。然而，由于高内存需求和数据依赖性，在GPU上部署完整的稀疏LU分解工作流程仍然具有挑战性。在本文中，我们提出了第一个完整的用于稀疏LU分解的GPU解决方案。为了实现这一目标，我们提出了符号执行阶段的核外实现，从而消除了因大型中间数据结构导致的瓶颈。接下来，我们针对GPU上的拓扑排序提出了卡恩算法的动态并行实现。最后，对于数值分解阶段，与现有的实现方法相比，我们通过消除对大型矩阵的内存限制来提高并行度。实验结果表明，与从GLU 3.0修改而来的一种实现相比，我们的核外版本实现了1.13 - 32.65倍的加速。此外，我们的核外实现在GPU上相对于一种优化的统一内存实现达到了1.2 - 2.2倍的加速。最后，我们表明我们为数值分解引入的优化是有效的。
LU factorization for sparse matrices is an important computing step for many engineering and scientific problems such as circuit simulation. There have been many efforts toward parallelizing and scaling this algorithm, which include the recent efforts targeting the GPUs. However, it is still challenging to deploy a complete sparse LU factorization workflow on a GPU due to high memory requirements and data dependencies. In this paper, we propose the first complete GPU solution for sparse LU factorization. To achieve this goal, we propose an out-of-core implementation of the symbolic execution phase, thus removing the bottleneck due to large intermediate data structures. Next, we propose a dynamic parallelism implementation of Kahn's algorithm for topological sort on the GPUs. Finally, for the numeric factorization phase, we increase the parallelism degree by removing the memory limits for large matrices as compared to the existing implementation approaches. Experimental results show that compared with an implementation modified from GLU 3.0, our out-of-core version achieves speedups of 1.13--32.65X. Further, our out-of-core implementation achieves a speedup of 1.2--2.2 over an optimized unified memory implementation on the GPU. Finally, we show that the optimizations we introduce for numeric factorization turn out to be effective.