HRPF：一种用于异构CPU-GPU系统上递归算法的并行编程框架

《Parallel Computing》：HRPF: A parallel programming framework for recursive algorithms on heterogeneous CPU–GPU systems

异构CPU-GPU系统上HRPF递归并行框架通过混合DFS/BFS任务生成与动态调度优化负载均衡，实现数据一致与计算传输重叠，实验表明其性能优于OpenMP、StarPU和Taskflow。

　　

王一卓|刘博文|邵森豪|高建华|季伟星|邢洪波

中国北京工业大学

摘要

递归作为一种常见的编程范式，被广泛应用于各种场景中。通过将递归问题视为任务，递归过程会生成许多独立的子任务，这揭示了并行处理的潜力。为了在异构的CPU-GPU系统上利用这种并行性，本文介绍了HRPF（异构递归并行编程框架）。HRPF提供了一组编程接口来定义递归算法，使用户无需关注任务分配、调度和数据传输的复杂性，从而能够高效且直接地在CPU-GPU系统上实现并行递归程序。HRPF结合深度优先搜索（DFS）和广度优先搜索（BFS）策略，在CPU和GPU之间分配任务。它采用了一种混合的工作窃取调度算法，结合了“工作优先”和“辅助优先”策略来实现动态负载均衡。HRPF运行时系统确保了主机和设备之间的数据一致性，并将计算与数据传输重叠进行。此外，HRPF还提供了一组并行循环编程接口。为了评估HRPF的性能，我们实现了几个基准测试，包括归并排序、快速排序、Strassen-Winograd矩阵乘法以及四种常用算法中的并行循环。在CPU-GPU平台上的实验结果表明，与OpenMP、StarPU和Taskflow相比，HRPF在多个基准测试中都表现出更优的性能。

引言

分而治之是一种用于解决复杂大规模问题的基本方法。该方法将一个大问题分解为许多较小的子问题，并行解决这些子问题，然后结合它们的解决方案来解决原始问题。常规的分而治之应用通常使用递归算法，例如归并排序、快速排序、大规模矩阵计算和二分搜索。目前，许多并行编程模型可以在集群或多核系统上对这些类型的应用进行并行化，例如MapReduce [1]、Cilk [2]、Intel TBB [3]以及其他类似Cilk的编程模型 [4]、[5]、[6]。然而，在异构系统上高效实现递归算法颇具挑战性。程序员必须深入了解异构架构，并可能需要分析和重构递归算法本身。此外，他们还需要设计高效的并行化策略，考虑跨异构处理单元的任务划分和调度。这些因素不仅增加了程序员的负担，还使并行化程序的结构变得复杂，难以维护。

尽管存在许多针对异构平台的基于任务的并行编程模型，如OpenMP、StarPU [7]、XKaapi [8]、OmpSs [9] 和 Taskflow [10]，但它们存在以下问题：（1）这些编程模型试图建立一个通用的任务并行编程框架，而没有针对递归问题的特定优化；（2）在这些编程模型中，任务无法在CPU和GPU之间迁移，或者迁移需要程序员处理大量的数据传输操作；（3）有时，程序员需要手动管理CPU和GPU之间的任务划分。虽然像StarPU和PaRSEC这样的高级运行时支持复杂的任务调度和跨CPU和GPU的自动数据管理，但HRPF提出了一个轻量级且高度专门化的模型，专门用于递归算法。它的贡献在于通过从递归结构中推断数据依赖关系并直接管理数据传输来简化用户的任务处理，从而简化了这类问题的开发过程。

针对最常见的CPU-GPU系统，我们的工作提出了一个用于递归算法的并行编程模型——HRPF。¹ HRPF是一个基于任务的并行编程模型。它通过将递归算法抽象为适当的任务，并采用精心设计的任务划分和调度策略来实现高性能。HRPF为开发人员提供了一个简单的编程接口，使他们能够专注于高级算法设计，而无需担心异构系统上任务并行执行的细节，从而提高了开发效率。

本文的主要贡献包括：

(1) 我们提出了HRPF，这是一个使用CUDA和C++20实现的并行编程框架，无需编译器扩展。HRPF的主要创新包括：

• •
  一种结合深度优先和广度优先方法的策略，用于生成和分配子任务。它同时也作为CPU和GPU之间的任务划分策略。
• •
  一种结合“工作优先”和“辅助优先”策略的算法 [11]、[12]，以实现CPU和GPU工作者之间的动态负载均衡。
• •
  在异构环境中的数据管理，包括根据递归问题的特点进行内存分配和管理，使用Modified-Shared-Invalid (MSI) 协议确保CPU和GPU之间的数据一致性，以支持任务迁移。HRPF还维护了一个CUDA流池，以实现CPU计算、GPU计算和数据传输的重叠。

(2) 我们为HRPF设计了一组并行循环接口，将并行循环转换为分而治之的问题。根据循环迭代空间中的计算负载分布，使用均匀或梯形自调度（TSS）类似的策略 [13]、[14] 来进行任务划分。

(3) 我们使用HRPF的核心接口实现了归并排序、快速排序和Strassen-Winograd快速矩阵乘法算法 [15]。使用HRPF并行循环接口实现了4个数值计算测试用例。这些实现与在由AMD EPYC 7402 CPU和NVIDIA GeForce RTX 4090 GPU组成的异构平台上使用OpenMP、StarPU和Taskflow的实现进行了比较。结果表明，HRPF在多个基准测试中表现出了更优的性能。

相关工作

相关工作

迄今为止，已经开发出了数百种并行编程模型。工业界常用的异构系统模型包括CUDA、OpenCL、C++ AMP、OpenACC、OpenMP（4.0及以上版本）、ROCM和SYCL。这些模型为异构系统上的并行编程提供了基本支持。在此基础上，对于更用户友好、性能更高的模型需求日益增长，这些模型需要更好地适应应用程序的特点。这一需求激发了学术界的相关研究。

架构

编程模型作为应用程序和系统架构之间的桥梁，为用户提供了抽象目标系统的API。我们的工作介绍了HRPF，这是一种用于异构CPU-GPU系统上递归算法的并行编程模型。HRPF被设计为一个不需要编译器扩展的库。其架构如图1所示。

在HRPF中，递归算法被抽象为一系列任务。算法的划分和组合阶段

编程接口

HRPF的主要编程接口如图2所示。这些接口分为两部分：应用层接口和运行时系统接口。应用层接口用于用户方便地实现递归算法。这里最重要的类是Task和Framework。Task类用于描述递归问题，而Framework类负责启动和管理任务执行。UML

任务生成和分配

在递归算法执行过程中，任务通过split操作不断生成子任务。这些新生成的子任务必须被放置到各个工作者的任务队列中以进行分配。HRPF为此提供了两种初始分配策略：

• •
  BFS分配：这种策略旨在最大化即时并行性。当父任务生成多个子任务时，它们会立即以轮询方式分配到多个

HRPF中的循环并行化

并行化循环通常是程序并行化的主要目标。许多并行编程模型，如Intel TBB、OpenMP和OpenACC，提供了专门的循环并行化接口。对于完全可并行化的循环，一些编程模型会递归地划分迭代空间以生成并行执行的任务，如Intel TBB所示。类似地，HRPF也为并行循环提供了专门的接口，并递归地划分循环迭代空间。

HRPF仅

评估

为了评估HRPF框架的性能和调度效率，我们进行了一系列全面的实验。我们的评估旨在：（1）将HRPF与已建立的并行编程框架（包括OpenMP、StarPU和Taskflow）在 homogeneous 多核和异构CPU-GPU配置上进行比较；（2）分离并量化HRPF的关键运行时特性（特别是其动态工作窃取调度器和专用调度）对性能的贡献

讨论

讨论1：HRPF中的关键配置参数，如混合BFS-DFS任务生成策略和高水位标记（high_water_mark）用于卸载，目前需要手动指定或离线调整。最佳配置在很大程度上取决于应用程序特点和具体的异构系统环境。我们之前曾探索使用机器学习来预测快速矩阵乘法的最佳策略 [42]，并使用OpenTuner自动

结论

本文提出了HRPF，这是一个用于异构CPU-GPU系统上递归算法的并行编程框架。我们展示了HRPF的编程接口及其运行时系统中的创新技术。使用HRPF，我们实现了归并排序、Strassen-Winograd快速矩阵乘法以及几个并行循环，并在异构CPU-GPU平台上进行了实验。结果表明，HRPF能够高效处理CPU-GPU系统上的复杂递归算法

CRediT作者贡献声明

王一卓：撰写——审阅与编辑，撰写——原始草稿，监督，资源管理，项目管理，方法论，调查，形式分析，数据整理，概念化。刘博文：撰写——审阅与编辑，可视化，验证，软件实现，形式分析，数据整理。邵森豪：验证，软件实现，方法论，数据整理。高建华：撰写——审阅与编辑，可视化，验证，软件实现，资源管理。季伟星：撰写——审阅与编辑，

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文所述的工作。

致谢

本工作得到了国家重点科研项目 （编号：2022ZD0116311）的支持。