GSOFA: Scalable Sparse Symbolic LU Factorization on GPUs
GSOFA: Scalable Sparse Symbolic LU Factorization on GPUs
复制标题
GSOFA：GPU 上的可扩展稀疏符号 LU 分解
DOI：
10.1109/tpds.2021.3090316
复制
发表时间：
2022
影响因子：
5.3
通讯作者：
Liu, Hang
中科院分区：
文献类型：
--
作者：
Gaihre, Anil;Li, Xiaoye S;Liu, Hang
将一个矩阵分解为一个下矩阵和一个上矩阵，也称为LU分解，是数值线性代数中的一个基本运算。对于一个稀疏矩阵，LU分解通常会在因子中引入比原矩阵更多的非零元素。需要一个符号分解步骤来识别和矩阵的非零结构.由于图形处理单元（GPU）的巨大潜力，一系列努力已经激增，以在GPU上部署除符号因式分解之外的各种LU因式分解步骤。本文介绍了gSoFa，这是第一个基于GPU的符号因式分解设计，具有以下三项优化，可为GPU上的非对称模式稀疏矩阵实现可扩展的LU符号因式分解。首先，我们介绍了一种新的细粒度并行符号因式分解算法，非常适合于单指令多线程（SIMT）架构的GPU。其次，我们将超级节点检测定制为SIMT友好过程，并努力平衡工作负载，最大限度地减少通信，并在超级节点检测期间饱和GPU计算资源。第三，我们引入了一个三管齐下的优化，以减少多源并发符号因式分解所面临的过度空间消耗问题。总的来说，gSoFa从1到44个Summit节点（6到264个GPU）实现了高达31倍的加速比，平均比最先进的CPU项目高出5倍。值得注意的是，gSoFa还实现了Summit超级计算机中V100 GPU峰值内存吞吐量的47%。
Decomposing a matrixinto a lower matrixand an upper matrix, which is also known as LU decomposition, is an essential operation in numerical linear algebra. For a sparse matrix, LU decomposition often introduces more nonzero entries in theandfactors than in the original matrix. Asymbolic factorizationstep is needed to identify the nonzero structures ofandmatrices. Attracted by the enormous potentials of the Graphics Processing Units (GPUs), an array of efforts have surged to deploy various LU factorization steps except for the symbolic factorization, to the best of our knowledge, on GPUs. This article introducesgSoFa, the firstGPU-basedsymbolicfactorization design with the following three optimizations to enable scalable LU symbolic factorization fornonsymmetric patternsparse matrices on GPUs. First, we introduce a novel fine-grained parallel symbolic factorization algorithm that is well suited for theSingle Instruction Multiple Thread(SIMT) architecture of GPUs. Second, we tailor supernode detection into a SIMT friendly process and strive to balance the workload, minimize the communication and saturate the GPU computing resources during supernode detection. Third, we introduce a three-pronged optimization to reduce the excessive space consumption problem faced by multi-source concurrent symbolic factorization. Taken together,gSoFaachieves up to 31× speedup from 1 to 44 Summit nodes (6 to 264 GPUs) and outperforms the state-of-the-art CPU project, on average, by 5×. Notably,gSoFaalso achieves up to 47 percent of the peak memory throughput of a V100 GPU in the Summit Supercomputer.