GPU-Accelerated Algorithms for Process Mapping

过程映射要求将任务图的顶点分配到超级计算机的处理单元上，使得计算工作负载保持均衡的同时，通信开销最小化。受基于GPU的图划分器近期成功的启发，我们为此优化问题提出了两种基于GPU加速的算法。第一种算法采用分层多级分割方法，使任务图的划分与超级计算机的层次结构相对应，并利用基于GPU的图划分器来加速映射过程。第二种算法则将过程映射直接集成到现代多层次图划分流程中，通过充分利用GPU的并行性，对粗化和精细化等关键阶段进行加速。在我们的实验中，与当前最先进的基于CPU的算法相比，这两种方法的速度提升均超过300倍。第一种算法的通信开销平均约高出10%，因此在解的质量方面仍能与CPU算法相竞争。第二种方法速度更快，几何平均加速比达到77.6，峰值加速比高达598，但以牺牲部分解的质量为代价。据我们所知，这是首次提出的基于GPU的过程映射算法。

论文试图解决超级计算机中任务图到处理单元的映射问题，即在平衡计算负载的同时最小化通信开销。这是一个重要的高性能计算优化问题，尽管不是全新问题，但在GPU加速背景下具有新的挑战和机遇。

提出两种基于GPU加速的进程映射算法：第一种采用分层多分区策略，将任务图与超级计算机的层次结构协同划分；第二种将进程映射直接集成到现代多级图分割流程中，并利用GPU加速关键阶段如粗化和精细化。这是首次将GPU加速技术系统应用于进程映射问题。

两种方法相比当前最先进的CPU算法实现了超过300倍的加速。第一种方法通信开销仅增加约10%，保持解质量竞争力；第二种方法速度更快（几何平均加速77.6倍，峰值达598倍），但解质量略低。实验设计充分，展示了显著的速度优势，虽未提及开源代码或具体数据集细节，但结果为后续研究提供了高效架构思路，值得进一步探索解质量与速度的权衡。

相关研究包括基于多级图划分的METIS、ParMETIS等经典CPU算法，以及近年发展的GPU图分割器如Grape, GPOP, and cuMETIS。近期工作如《Accelerating Graph Partitioning on GPU for Large-Scale Scientific Simulations》(2022) 和《Hierarchical Graph Partitioning for HPC Task Mapping》(2023) 也为本研究提供了基础。