G-kway：一种利用任务图并行性的多层GPU加速k-way图划分器

《ACM Transactions on Design Automation of Electronic Systems》：G-kway: Multilevel GPU-Accelerated k-way Graph Partitioner using Task Graph Parallelism

本文提出G-kway多级GPU加速k-way图分割算法，通过并查集优化粗化过程和独立集改进细化算法，结合CUDA Graph减少内核开销，实验表明其较现有CPU和GPU方案分别提升8.6倍和3.8倍速度，同时保持相当分割质量，使用CUDA Graph可再加速1.93倍。

　　

摘要

图划分对于许多CAD算法的设计至关重要。然而，随着图规模的不断扩大，图划分的工作量变得日益繁重。最近的研究引入了利用多核CPU或GPU的并行图划分器。不过，现有CPU图划分器的加速效果通常仅限于少数几个核心，而基于GPU的解决方案的性能则受到可用GPU内存的限制。为了解决这些问题，我们提出了G-kway，这是一种高效的多级GPU加速的k-way图划分器。G-kway采用了一种基于并查集的有效粗化算法以及一种新颖的基于独立集的细化算法，显著提升了粗化和细化阶段的处理速度。此外，当细化算法中的内核启动开销较大时，G-kway会使用CUDA Graph技术进行去粗化操作，以降低开销并提升性能。实验结果表明，G-kway的性能优于现有的基于CPU和GPU的并行划分器，平均加速倍数分别为8.6倍和3.8倍，同时仍能保持相当的划分质量。另外，结合CUDA Graph技术的G-kway还能进一步提升图划分速度，相比默认版本的G-kway，最高可实现1.93倍的加速效果。