A New GPU Algorithm to Compute a Level Set-Based Analysis for the Parallel Solution of Sparse Triangular Systems
A New GPU Algorithm to Compute a Level Set-Based Analysis for the Parallel Solution of Sparse Triangular Systems
复制标题
一种新的 GPU 算法来计算稀疏三角形系统并行解的基于水平集的分析
DOI：
10.1109/ipdps.2018.00101
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Ezzatti
中科院分区：
文献类型：
--
作者：
Ernesto Dufrechu;P. Ezzatti
科学和工程中的无数问题都涉及到稀疏三角形线性系统的解。它们经常作为线性系统和特征值问题的直接和迭代求解的一部分出现，因此可以被认为是稀疏数值线性代数的关键组成部分。这就是为什么从早期开始，他们的并行解决方案就被详尽地研究，并且几乎可以在每个硬件平台上找到该内核的有效实现。在GPU上下文中，该内核最广泛的实现是分布在NVIDIA CUSPARSE库中的内核，它依赖于预处理阶段将三角形系统的未知数聚合为水平集。这决定了系统解决方案的执行时间表，其中关卡集必须按顺序处理，而属于一个关卡集的未知数可以并行解决。CUSPARSE实现的缺点之一是，与求解阶段的运行时相比，这个预处理阶段通常非常慢。在这项工作中，我们提出了一种并行GPU算法，该算法能够计算与CU S PARSE相同的水平集，但运行时间显著减少。我们对来自SuiteSparse集合的一组矩阵进行的实验显示加速因子高达44倍。此外，我们还提供了一个能够在用于计算水平集的同一通道上解决三角形线性系统的例程，从而产生重要的性能优势。
A myriad of problems in science and engineering, involve the solution of sparse triangular linear systems. They arise frequently as part of direct and iterative solvers for linear systems and eigenvalue problems, and hence can be considered as a key building block of sparse numerical linear algebra. This is why, since the early days, their parallel solution has been exhaustively studied, and efficient implementations of this kernel can be found for almost every hardware platform. In the GPU context, the most widespread implementation of this kernel is the one distributed in NVIDIA CUSPARSE library, which relies on a preprocessing stage to aggregate the unknowns of the triangular system into level sets. This determines an execution schedule for the solution of the system, where the level sets have to be processed sequentially while the unknowns that belong to one level set can be solved in parallel. One of the disadvantages of the CUSPARSE implementation is that this preprocessing stage is often extremely slow in comparison to the runtime of the solving phase. In this work, we present a parallel GPU algorithm that is able to compute the same level sets as CU S PARSE but takes significantly less runtime. Our experiments on a set of matrices from the SuiteSparse collection show acceleration factors of up to 44×. Additionally, we provide a routine capable of solving a triangular linear system on the same pass used to calculate the level sets, yielding important performance benefits.