点击数: 更新日期: 2023-11-06
中文题目：PanguLU：一个面向异构分布式平台的开源直接法解法器
论文题目：PanguLU: A Scalable Regular Two-Dimensional Block-Cyclic Sparse Direct Solver on Distributed Heterogeneous Systems
录用期刊/会议：36th ACM/IEEE International Conference for High Performance Computing, Networking, Storage, and Analysis (SC '23, CCF-A类期刊) Best Paper Finalist. 最佳论文提名
录用/见刊时间： 2023-06-17（录用时间）
封面图片：
封面摘要：
稀疏直接求解器在大规模高性能科学和工程计算中发挥着重要作用。现有的分布式稀疏直接求解方法采用多波前/超节点的方法来聚合结构相似的列，并利用稠密线性代数子程序（BLAS）进行计算。然而，当输入的矩阵结构不理想时，这样的方法可能会带来更多不均匀性，并且使用稠密 BLAS 会填充上更多的零元导致许多不必要的浮点运算。
为此，我们开发了一个名为 PanguLU 的新型稀疏直接求解器（注：软件包命名取“盘古开天地”之意，经矩阵分解后，“天”为U矩阵，“地”为L矩阵）。通过在128 个A100 GPU 的异构平台上进行的实验表明，与最新的 SuperLU_DDI 相比，PanguLU 的速度最高可以提升 11.7 倍。此外，PanguLU也具有一定的可扩展性，能在 128 个 GPU 上比单个 GPU 扩展 47.5 倍。
作者列表：
1） 付 旭 中国石油大学 信息科学与工程学院 计算机技术系 硕21
2） 张冰彬 中国石油大学 信息科学与工程学院 计算机技术系 硕 22
3） 王腾程 中国石油大学 信息科学与工程学院 计算机技术系 硕 21
4） 李文豪 中国石油大学 信息科学与工程学院 计算机技术系 硕 22
5） 伊恩鑫 中国石油大学 信息科学与工程学院 计算机技术系 硕 21
6） 卢玥辰 中国石油大学 信息科学与工程学院 计算机技术系 博 22
7） 赵健崎 中国石油大学 信息科学与工程学院 计算机技术系 硕 20
8） 耿晓晗 中国石油大学 信息科学与工程学院 计算机技术系 硕 20
9） 黎芳莹 中国石油大学 信息科学与工程学院 计算机技术系 硕 20
10） 张经文 中国石油大学 信息科学与工程学院 计算机技术系 硕 22
11） 金 洲 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系教师
12） 刘伟峰 中国石油大学（北京） 信息科学与工程学院 计算机科学与技术系教师
背景与动机:
稀疏LU分解是使用直接法求解非对称线性系统的关键步骤之一，经常是众多科学与工程应用中相当耗时的一个操作。由于稀疏LU分解的数据依赖和计算模式十分复杂，所以将其在异构分布式平台上进行性能优化一直极具挑战。为此，我们设计了一个新的在GPU加速的异构分布式集群上的稀疏LU分解算法，并开源了直接法解法器软件包PanguLU（注：软件包命名取“盘古开天地”之意，经矩阵分解后，“天”为U矩阵，“地”为L矩阵）。
设计与实现:
我们的方法使用二维规则稀疏分块的数据布局，如图1所示。该数据布局需要将原矩阵切割为等大的矩阵块，以稀疏格式存储块，以防止任何不必要的填充。PanguLU由于存储的矩阵块是稀疏的，因此我们使用稀疏 BLAS 进行计算。这样做的好处是能更好地利用原矩阵的稀疏特性，提高计算效率。
图1.二维规则稀疏分块的LU分解方法
此外为了提高PanguLU在异构分布式系统上的求解效率，我们还做出了以下三点优化：（1）为了使 PanguLU 更具可扩展性，我们设计了一个块映射方案来调整每个进程的任务，来更好地平衡它们之间的负载；（2）我们为PanguLU开发并设计了专用的稀疏BLAS，包含了许多不同的并行方法，此外还设计了一个选择树的方法根据矩阵的稀疏结构特性选择更快的稀疏BLAS；（3）我们还关注在分布式系统上不同子任务之间的依赖关系，设计了一种无同步调度策略，在分布式系统中尽可能多地进行计算，从而减少整个计算过程的延迟成本；
图2. PanguLU的无同步调度策略算法流程图
实验结果及分析:
我们分别使用128 个 A100 NVIDIA GPU 对 PanguLU 和最新版 SuperLU_DIST 8.1.2 进行测试，测试结果如图3所示。
图 3. PanguLU和最新SuperLU_DIST 8.1.2在128个A100 GPU上的性能对比
与最新版SuperLU_DIST相比，PanguLU在这16个来自Suitsparse矩阵集的矩阵上达到了平均3.86倍，最高11.70倍的加速比。此外，PanguLU还展示了不错的可扩展性，128个GPU上比单GPU能提升47.5倍。
结论:
本文提出了在分布式异构平台上可扩展的直接法求解器 PanguLU。在 PanguLU 中，我们采用了映射方法来平衡负载，通过一个自适应稀疏BLAS 方法来提高 GPU 的效率，并采用了无同步通信策略来降低整体延迟成本。通过在128 个A100 GPU 的异构平台上进行的实验表明，与最新的 SuperLU_DDI 相比，PanguLU 的速度最高可以提升 11.7 倍。此外，PanguLU也具有一定的可扩展性，能在 128 个 GPU 上比单个 GPU 扩展 47.5 倍。
作者简介:
付旭，中国石油大学（北京）硕士生。2021年于中国石油大学（北京）获计算机系学士学位。2021年至今于中国石油大学（北京）攻读硕士研究生，主要研究领域为高性能计算，大规模异构分布式解法器。在此期间开发了异构分布式直接法解法器PanguLU，使用稀疏的方法求解稀疏LU分解问题，目前最新版本3.5已经开源在github上。
联系方式：xu.fu@student.cup.edu.cn
通讯作者简介:
刘伟峰，博士、中国石油大学（北京）教授、博士生导师，欧盟玛丽居里学者。2002年和2006年于中国石油大学（北京）计算机系获学士与硕士学位。2006年至2012年在中国石化石油勘探开发研究院历任助理工程师、工程师和高级研究师，其间主要研究领域为石油地球物理勘探的高性能算法。2016年于丹麦哥本哈根大学获计算科学博士学位，主要研究方向为数值线性代数和并行计算，其中尤其关注稀疏矩阵的数据结构、并行算法和软件。研究工作发表于SC、PPoPP、DAC、ASPLOS、ICS、IPDPS、ICPP、TPDS、JPDC、FGCS和Parco等重要国际会议和期刊。担任TPDS、SISC和TKDE等多个重要国际期刊审稿人，以及SC、ICS、IPDPS和ICPP等多个重要国际会议的程序委员会委员。他是IEEE高级会员、CCF高级会员、ACM和SIAM会员。
联系方式：weifeng.liu@cup.edu.cn。