分而治之是一种用于解决复杂大规模问题的基本方法。该方法将一个大问题分解为许多较小的子问题，并行解决这些子问题，然后结合它们的解决方案来解决原始问题。常规的分而治之应用通常使用递归算法，例如归并排序、快速排序、大规模矩阵计算和二分搜索。目前，许多并行编程模型可以在集群或多核系统上对这些类型的应用进行并行化，例如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。1 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在多个基准测试中表现出了更优的性能。
