# 笔记：Pure: 改进消息传递以更好地利用节点内的共享内存

# 引用出处

James Psota and Armando Solar-Lezama. 2024. Pure: Evolving Message Passing To Better Leverage Shared Memory Within Nodes. In Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP ‘24). Association for Computing Machinery, New York, NY, USA, 133–146. https://doi.org/10.1145/3627535.3638503

# 关键词

• 并行编程模型
• 分布式运行时系统
• 基于任务的并行模型
• 并发数据结构
• 无锁数据结构

# 摘要

Pure 是一种新的编程模型和运行时系统，旨在在基于消息传递接口（增强使用任务利用空闲核心能力）的环境中充分利用节点内部的共享内存。Pure 通过两种方式利用共享内存：(1) 允许 rank 在等待消息到达时从彼此那里窃取工作；(2) 利用高效无锁的数据结构实现节点内各进程间高性能的消息传递和集合操作。研究者通过 micro benchmark 测试评估了 Pure 的关键消息传递和集合特性，并展示了在 CoMD 分子动力学和 miniAMR 自适应网格细化应用中，当扩展到 4096 个 rank 时，Pure 可实现高达 2.1x 的应用加速。

# 1. 引言

在过去的几十年里，高性能计算领域经历了从大型向量计算机到由单处理器构成的集群的转变，这些集群通过网络互连。MPI 成为了分布式内存系统上并行编程的事实标准。随着硬件的进步，多核集群的出现使得节点内的核心能够共享内存并通过网络进行通信，这促使社区不断寻求新的范式，以更有效地利用现代集群资源。目前主要的策略有两种：一种是维持统一的 MPI 编程方法，通过改进 MPI 运行时系统来更好地利用共享内存；另一种是采用 MPI+X 等混合编程模式，在节点内部采用共享内存并行性，而在节点之间继续使用 MPI。然而，这些方法要么可能受到 MPI 标准对接口行为规定的限制，无法最大化性能；要么给程序员带来了管理两种编程模型的挑战。

社区已经尝试了许多其他方法，其中包括 PGAS 模型，它提供了一种集群范围内的共享内存抽象，以及 Legion 、Chapel 和 X10 等隐式并行编程语言，这些语言提供了高级抽象，并尝试自动高效地协调应用程序。尽管取得了一定的进展，许多现代 HPC 应用仍然依赖于 MPI。MPC 和 AMPI 也尝试通过将线程作为 MPI Rank 来利用内部的共享内存，以提高性能。

然而，仅使用 MPI 的方法往往比混合编程方法表现更佳。这可能是因为接口的局限性和无法充分利用节点内的共享内存，导致 MPI 未能充分发挥其潜在性能。因此，本文提出的 Pure 系统基于 MPI-everywhere 方法构建，打破了一些 MPI 的传统假设，更有效地利用了共享内存，同时避免了对现有程序进行重大重构的需求。Pure 采用了与 MPI 类似的编程模型，从而能够利用 HPC 社区现有的 MPI 知识和应用程序基础。

Pure 的设计灵感源自 MPI，其核心编程模型是基于消息传递的，并可选择性地整合任务并行性。与 MPI 不同，Pure 摒弃了使用进程级别的 rank 和对旧版语言的支持限制，转而采用线程作为 rank 的实现，而非传统的进程。这种转变使得 Pure 能够高效地采用轻量级的无锁同步机制，实现同一节点内各线程间的协调。利用这种线程化的 rank 架构，Pure 构建了高效的节点内集体操作功能，并通过无锁算法来优化这些操作的性能。此外，Pure 支持将应用程序中的一部分并行代码块以标准的 C++ lambda 表达式的形式运行，这些表达式能够被当前拥有 rank 的线程以及其他空闲的 rank 自动且并发地执行，而这一切的操作都由 Pure Runtime 运行时系统自动进行调度。

论文提出的优化策略涵盖了以下几点：

• 一种无锁消息传递方法，适用于小消息和大数据消息的传输。
• 无锁数据结构，用于高效实现集合通信算法。
• 一个无锁任务调度器，允许空闲线程高效地从其他线程中“窃取”工作负载。

作者采用了标准的 C++ 库来确保 Pure 的广泛兼容性，并证明了 Pure 相较于经过高度优化的 MPI 基准测试，在性能上有显著提升。此外，作者还展示了 Pure 编程模型在语义上与 MPI 非常相似，这意味着从现有应用程序迁移到 Pure 是直接且简便的，这一点通过源码到源码的转换工具 mpi2pure 得到了进一步的证明。总体而言，论文的主要贡献可以总结为以下几点：

1. 提出了一种新的编程模型和运行时系统，该系统有效地结合了消息传递和任务并行性，并且利用了标准 C++ 的特性来实现。
2. 展示了现代 C++ 如何支持更加灵活的并行运行时系统接口。
3. 描述了一个设计精良的无锁、多线程和分布式运行时系统，该系统在节点内部相比 MPI 显示出了显著的速度提升。
4. 证明了通过仅对现有的 MPI 应用程序进行最小的源代码修改，就能在 micro benchmark 测试和三个实际应用中实现与最先进的 MPI 实现相比的显著性能提升。

# 2. Pure 使用示例

本节通过一个简单的 1-D Stencil 算法示例来阐释 Pure 的使用方法。该示例虽然简单，但能够清晰展示 Pure 的核心概念及其与 MPI 的相似之处，为开发者编写更复杂的应用程序奠定了基础。

在 MPI 版本的实现代码 rand_stencil_mpi 中，计算工作主要集中在函数 random_work 中执行。简单来说，rand_stencil_mpi 函数首先会进入一个循环，迭代次数为 iters ，在数组 a 的每个元素上计算 random_work 。值得注意的是，random_work 执行的时间长度是可变且未知的，因此会引入负载不平衡。此外，random_work 不会修改数组 a 的内容，而是接着通过对相邻元素求平均值更新数组 a 。最后，程序利用 MPI_Send 和 MPI_Recv 交换 temp 数组的首尾元素，以便计算数组 a 的首尾元素。由于 random_work 所需时间长短不一，某些处理单元会提前完成任务，有时会在等待发送方较慢的 MPI_Recv 调用时陷入阻塞状态。

注释

示例 1：1-D Stencil with Random Work, MPI Version

void rand_stencil_mpi(double* const a, size_t arr_sz, size_t iters, int my_rank,
                      int n_ranks) {
  double temp[arr_sz];
  for (auto it = 0; it < iters; ++it) {
    for (auto i = 0; i < arr_sz; ++i) {
      temp[i] = random_work(a[i]);
    }
    for (auto i = 1; i < arr_sz - 1; ++i) {
      a[i] = (temp[i - 1] + temp[i] + temp[i + 1]) / 3.0;
    }
    if (my_rank > 0) {
      MPI_Send(&temp[0], 1, MPI_DOUBLE, my_rank - 1, 0, MPI_COMM_WORLD);
      double neighbor_hi_val;
      MPI_Recv(&neighbor_hi_val, 1, MPI_DOUBLE, my_rank - 1, 0, MPI_COMM_WORLD,
               MPI_STATUS_IGNORE);
      a[0] = (neighbor_hi_val + temp[0] + temp[1]) / 3.0;
    }  // ends if not first rank
    if (my_rank < n_ranks - 1) {
      MPI_Send(&temp[arr_sz - 1], 1, MPI_DOUBLE, my_rank + 1, 0,
               MPI_COMM_WORLD);
      double neighbor_lo_val;
      MPI_Recv(&neighbor_lo_val, 1, MPI_DOUBLE, my_rank + 1, 0, MPI_COMM_WORLD,
               MPI_STATUS_IGNORE);
      a[arr_sz - 1] =
          (temp[arr_sz - 2] + temp[arr_sz - 1] + neighbor_lo_val) / 3.0;
    }  // ends if not last rank
  }    // ends for all iterations
}

示例 2 则展示了实现同样功能的 Pure 版本。其中存在一些关键差异。首先，消息调用函数接口不同，使用的是相应的 Pure 消息传递函数 pure_send_msg 和 pure_recv_msg ，而非 MPI 调用，但参数实质上与 MPI 对应函数基本相同。Pure 的消息传递语义类似于 MPI：发送端缓冲区被复制到接收端缓冲区。实现区别主要在于：Pure 在节点内部采用了轻量级的消息传递方法，从而在节点内的消息传递比 MPI 的延迟更低。

注释

示例 2：Pure 版本

void rand_stencil_pure(double* a, const int arr_sz, const int n_iter,
                       const int my_rank, const int n_ranks) {
  double temp[arr_sz];
  PureTask rand_work_task = [a, temp, arr_sz, my_rank](
                                chunk_id_t start_chunk, chunk_id_t end_chunk,
                                std::optinal<void> cont_params) {
    auto [min_idx, max_idx] =
        pure_aligned_idx_range<double>(arr_sz, start_chunk, end_chunk);
    for (auto i = min_idx; i < max_idx; i++) {
      temp[i] = random_work(a[i]);
    }
  };  // ends definding the Pure Task for rand_work_task
  for (auto it = 0; it < n_iter; it++) {
    rand_work_task.execute();  // execute all chunks of rank_work_task
    for (auto i = 1; i < arr_sz - 1; ++i) {
      a[i] = (temp[i - 1] + temp[i] + temp[i + 1]) / 3.0;
    }
    if (my_rank > 0) {
      pure_send_msg(&temp[0], 1, MPI_DOUBLE, my_rank - 1, 0, PURE_COMM_WORLD);
      double neighbor_hi_val;
      pure_recv_msg(&neighbor_hi_val, 1, MPI_DOUBLE, my_rank - 1, 0,
                    PURE_COMM_WORLD);
      a[0] = (neighbor_hi_val + temp[0] + temp[1]) / 3.0;
    }  // ends if not first rank
    if (my_rank < n_ranks - 1) {
      pure_send_msg(&temp[arr_sz - 1], 1, MPI_DOUBLE, my_rank + 1, 0,
                    PURE_COMM_WORLD);
      double neighbor_lo_val;
      pure_recv_msg(&neighbor_lo_val, 1, MPI_DOUBLE, my_rank + 1, 0,
                    PURE_COMM_WORLD);
      a[arr_sz - 1] =
          (temp[arr_sz - 2] + temp[arr_sz - 1] + neighbor_lo_val) / 3.0;
    }  // ends if not last rank
  }    // ends definding the Pure Task for rand_work_task
}

更重要的差异在于 Pure 中增加的 Pure Task ，用带有一组特定参数定义的 lambda 表达式，其利用 lambda 的捕获参数特性，允许外部于 lambda 体内的变量以值或引用形式被捕获并在 lambda 执行时使用。Pure Task 可以被视为由 Pure Runtime 运行时系统负责执行应用程序代码片段，可以通过多线程并发执行。因此，Pure 任务应结构化为类似数据并行的形式。此外，Pure Task 需要由程序员保证线程安全。

在以上 Pure 实现中，程序员可以利用 chunk ranges 来描述并发性。这些子范围或 chunk 是通过 start_chunk 和 end_chunk 参数传递给 Pure Task 的，而它们是由 Pure Runtime 运行时系统提供。Pure Runtime 运行时系统负责确保所有工作顺利完成。由于可能涉及到不同的多个线程，Pure Runtime 运行时系统会通过追踪哪些 chunk 已分配和完成来实现这一点。

其次，程序员需要将 Pure Runtime 运行时系统提供的 start_chunk 和 end_chunk 参数映射到与应用计算相关的具体内容上。在这里，代码使用了 pure_aligned_idx_range 辅助函数将其转化为循环索引子范围。这个辅助函数考虑到了缓存行，所以有利于避免伪共享问题。

由于 random_work 可能导致负载分布不均，某些 rank 可能会在等待消息时处于空闲状态。Pure 的任务调度器会自动利用这些空闲的 rank，以执行同一节点内其他待处理的 Pure 任务块。以下图中在同一节点内的三个 rank 为例：rank 0 正在执行一个被划分为 6 个 chunks 的 Pure Task，而 rank 1 和 rank 2 因为接收消息而阻塞。

从图中可以清晰地看到以下执行流程：

• rank 0 开始处理第一个 chunk（chunk 0） 。
• 同时，rank 1 窃取并行执行第二个 chunk（chunk 1）。
• 任务调度器随后为 rank 0 分配第三个 chunk（chunk 2），为 rank 1 分配第四个 chunk（chunk 3）。
• rank 2 尝试窃取一个任务，并成功执行第五个 chunk（chunk 4）。由于 random_work 的执行随机性，chunk 2 和 chunk 4 可能是耗时较长的任务。
• rank 0 完成 chunk 5 的处理，这是一个较小的任务块，它在 rank 2 完成 chunk 4 之前就已经结束了。
• 任务调度器确保在所有 chunks 完成之前，rank 0 不会结束执行。实际上，rank 0 要等到 chunk 4 完成后才能继续。
• 在 rank 1 和 rank 2 等待消息的过程中，它们会尝试从其他任何可用的 rank 中窃取更多的 chunks。
• 得益于 lambda 表达式的变量捕获功能，不同 rank 之间可以高效地共享上下文信息。

实验结果显示，在单节点上配置 32 个 rank 的 Pure 版本因为更快的消息传递和 Pure Task 的并行执行，相比于 MPI 版本，Pure 版本实现了 10% 的性能提升。在负载分布不均的情境下，Pure 的加速比甚至超过了 200%。这些性能提升的程度虽然受到负载不平衡的影响，但在实际应用场景中，Pure 仍展现出了显著的性能改进。这归功于 Pure Runtime 运行时系统的能力，它能够自动检测并高效利用未被充分利用的计算资源。

# 3. 编程模型

Pure 的编程模型核心是“消息传递结合可选的任务并行性”。在语义上，Pure 的消息传递和集合通信操作与 MPI 等同，差异主要体现在语法上的一些细节。

尽管 Pure 在节点内部采用线程，但其 rank 命名空间在整个集群中保持非层级结构。在 Pure 程序的执行周期内，rank 的数量保持不变。

Pure 应用程序采用 C++ 编写，并通过 SPMD（单程序多数据）模式运行，实现了内部的多线程化。在同一个节点上，所有的 rank 都是通过内核线程实现的。

需要注意的是，Pure 应用程序并不支持全局变量。因此，开发者应当移除全局变量或者使用 thread_local 关键字来限制变量的作用域，确保线程之间的安全性。

对于存在负载不均衡问题的应用程序，开发者可以在满足以下特定条件的程序部分使用 Pure Task：

1. 计算密集型的热点区域。
2. 可以并发执行的任务。

# 消息传递和集合通信操作

在 Pure 中，pure_send_msg 和 pure_recv_msg 函数在功能上与 MPI 的 MPI_Send 和 MPI_Recv 相对应，同时 Pure 也提供了相应的非阻塞版本。

Pure Runtime 运行时系统确保所有消息都会被送达，并且按照发送的顺序进行交付。Pure 还实现了一系列的集合通信操作，包括：

• Reduce
• All-Reduce
• Barrier
• Broadcast

此外，Pure 引入了通信子（communication subgroup）的概念，允许开发者通过 pure_comm_split 函数将一个通信子集进一步细分为更小的子集。

为了使用 Pure，应用程序需要采用现代 C++ 标准进行编写，推荐使用 std=c++11 或更高版本进行编译。Pure 提供了一个基于 Make 的构建系统，它会自动配置合适的编译器选项，并链接到 Pure Runtime 运行时系统（libpure），同时定义了一系列用于调试和性能分析的 target。

# Pure Task

Pure Task 允许开发者定义应用程序中的计算部分，并将其分解为可并行执行的 chunks。这些 chunks 可以由 Pure Runtime 运行时系统自动并发执行。

然而，Pure Task 不是必需的，只有在任务可以划分为多个小块，并且这样做有助于缓解负载不均衡问题时，才推荐使用 Pure Task。

Pure Task 通过 C++ Lambda 表达式实现，并在拥有该任务的 rank 调用 execute 方法时同步执行。每个 rank 同一时间只能执行一个 Pure Task。Lambda 表达式的变量捕获功能使得不同 rank 在执行不同 chunks 时能够高效共享上下文信息。通常，一个 Pure Task 在应用程序的运行过程中会被定义一次，然后在每个时间步或其他迭代中多次执行。

定义 Pure Task 时，需要指定 chunk 的数量和额外的应用程序参数。任务之间应避免相互依赖，不过因为它们会在 execute 调用期间完全执行，所以它们不会与任务外部的代码发生冲突。

Pure Task 包含一个 execute 方法，该方法接受一个 optional<void*> 类型的参数 per_exe_args ，用于每次执行任务时传递额外的参数。这在任务主体的输入值在连续执行中发生变化时非常有用。例如，开发者可以将指向局部结构体的指针传递给 execute 方法。

Pure Task 的前两个参数 start_chunk 和 end_chunk 是无符号整数，用于指定要执行的 chunk 范围。这些 chunk 由 Pure Runtime 运行时系统分配，确保每个 chunk 只被执行一次，即使它们可能并发执行。

Pure Task 使用 chunk 范围为调度器提供了灵活性，允许一次性分配多个 chunks。chunks 的数量由 Pure 任务调度器决定，但不会超过在 Makefile 文件中预定义的 PURE_MAX_TASK_CHUNKS 。

目前，Pure Task 的接口需要手动将 chunk 编号映射到数组索引，这在处理多维数组时可能比较繁琐。因此，未来的工作目标是扩展接口，提供类似于 TBB 的 parallel_for 那样更简洁、更高级的接口。

最后，开发者需要确保 Pure Task 内部的实现是线程安全的，以避免同一任务的多个并发执行的 chunks 之间的相互竞争。例如，在 CoMD 分子动力学 Benchmark 中，需要处理多个线程同时写入同一内存位置的问题，这时可以使用 std::atomic 数组来替代普通 int 数组。

# 4. 运行时系统

Pure 运行时系统是一个多线程和分布式运行时的动态库，用于支持 Pure 应用程序的开发。开发者在使用时需要包含 pure.h 头文件，并使用 C++17 标准进行编译，同时链接到 libpure 库。Pure 运行时系统能够自动地在计算和通信操作之间寻找并利用重叠执行的机会，尤其是在通信延迟较高的情况下。

Pure 运行时系统的主要职能包括：

• 初始化并配置必要的进程和线程，启动应用程序。
• 管理节点内部的 rank 间通信和集合操作。
• 管理内部的内存缓冲区和数据结构。
• 如果应用程序中定义了 Pure Task，运行时系统还需负责这些任务的调度和执行。

# Rank 初始化与映射

Pure 中的 rank 实现为 MPI 进程的内核线程。在多节点应用中，Pure 运行 MPI 来处理跨节点通信，而在单节点应用中则不使用 MPI，尽管如此，Pure 应用程序并不直接调用 MPI 函数。通过 Makefile 配置，Pure 程序可以在一个节点或 NUMA 节点上启动一个 MPI 进程，并根据每个节点或 NUMA 节点的核心数来创建相应数量的线程。对于应用程序开发者而言，他们只需了解非层次化的 rank 命名空间，而节点、线程、MPI 进程和通信延迟等底层概念都被抽象化，对开发者透明。

Pure 支持灵活的 rank 到节点的映射策略，并且默认采用 SMP 风格的分配策略。同时，Pure 也支持自定义的 rank 映射，包括使用 CrayPAT 的 rank 重排文件。虽然这些硬件相关的细节对开发者来说是不可见的，但 Pure 内部会利用这些信息来优化关键功能。

在 Pure 应用程序启动时，不会直接执行应用程序的原始 main 函数。相反，底层的 MPI 程序会调用 Pure 运行时系统中定义的 main 函数，该函数负责初始化 Pure 的核心数据结构，然后创建并绑定线程，每个线程执行一个 original_main 函数，这是从应用程序代码中的原始 main 函数重命名而来的版本。应用程序执行完毕后，original_main 函数返回到 Pure 运行时系统，后者负责完成 MPI 的清理和终止过程。

# Spin-Steal Waiting Loop (SSW-Loop)

当 Pure 的 rank 遇到阻塞事件，如等待消息到达，它将执行一个称为 自旋、窃取等待循环（SSW-Loop） 的机制，而不是简单地进入空闲状态。在此循环中，rank 会检查是否满足阻塞条件，例如是否有消息到达，如果没有，它会尝试从其他 rank 窃取任务。如果一个阻塞的 rank 能够协助其进程中正在并发执行的其他线程完成任务，它就会参与这种协助工作。

由于线程是绑定到特定的 CPU 的，并且每个 rank 只运行一个应用程序，Pure 选择让 rank 主动自旋等待，而不是放弃 CPU。SSW-Loop 让计算中的 rank 具有“多态性”：它既可以作为主程序的计算节点，也可以协助其他 rank 执行窃取到的任务块，然后再返回检查自身的阻塞事件。

Pure 遵循优先处理当前 rank 拥有的窃取任务负载的策略，坚持任务负载优先的调度原则。

与那些使用辅助线程来实现工作负载窃取或通信的系统不同，Pure 的特点是允许应用级别的计算节点直接进行任务窃取操作。

# 实现说明

Pure 是使用 C++17 标准库编写的。Pure 运行时系统由大约 21,000 行源代码构成，而 Pure 工具则包含了约 14,000 行源代码。Pure 已在多种环境下进行测试，包括笔记本电脑和集群，其运行仅需要一个支持 C++17 的编译器、类 Unix 操作系统以及 MPI 环境。Pure 的源代码可以在 GitHub 上公开获取，链接为： https://github.com/psota/pure 。

# 点对点通信

Pure 提供了阻塞和非阻塞的点对点消息传递功能，其语义与 MPI 的消息传递相一致。

Pure 内部采用三种不同的策略来进行消息传递，选择哪种策略取决于消息的大小以及发送方和接收方是否位于同一节点。

Pure 在整个程序的生命周期中分配并复用一个持久的 Channel 对象，该对象存储于运行时系统中。内部的 Channel Manager 负责将消息参数映射到合适的数据结构，并根据需要创建这些结构。

• 短消息（小于 8KB）：
  • 采用无锁循环队列（PureBufferQueue，PBQ），具有 acquire-release 内存语义。发送线程在有可用空间时将消息复制到 PBQ，接收线程则在消息准备好时将其取出。
    • 在短消息传递中，拷贝的开销相对较小，这样可以让发送方调用返回后立即执行执行其它有用的工作。
  • 发送和接收线程都使用 SSW-Loop 进行等待，以尽可能地实现计算与通信的重叠执行。
  • 所有消息的 slot 存储在一个连续的缓冲区中，通过指针算术确保每个 slot 与缓存行边界对齐，避免发送和接收线程之间的伪共享。
• 大消息（大于等于 8KB）：
  • 类似于 PBQ 的策略，但使用直接从发送方到接收方的单次内存拷贝，灵感来自 MPI 的 rendezvous 模式。
  • 使用无锁的固定大小循环缓冲区来存储接收方的接收调用参数。
  • 发送方通过 SSW-Loop 等待元数据队列项，然后将消息内容直接复制到接收方的缓冲区。发送方通过在无锁队列中插入传输的字节数来通知接收方传输已完成。
• 跨节点消息
  • 透明地使用 MPI 接口进行消息传递。
  • 在 Pure 初始化期间，使用分布式一致性算法创建 thread-rank-process-node 映射数据结构，将 Pure rank 映射到 MPI rank。
  • 为了确保在接收节点上正确的接收线程能够接收到消息，在 MPI_TAG 中编码发送和接收线程的 ID，解决多线程路由问题。

# 集合通信

Pure 的集体通信操作在语义上与 MPI 相同，但在节点内部通过自下而上构建的数据结构来实现，这在单节点和多节点基准测试中都显示出了显著的性能提升，即使在跨节点通信时仍然依赖于 MPI 的集合操作。

Pure 采用一个领导者线程来协调集体通信过程，其他线程则协助进行计算并按需调用 MPI 集合函数。

• Pure 使用静态领导者选举方法，这比基于比较和交换的“首先进入”方法更为高效。

以下仅以 All-Reduce 为例子，其它集合通信操作思想类似。

对于小数据的 All-Reduce 操作，Pure 设计了名为 Sequenced Per-Thread Dropbox (SPTD) 的并发数据结构，提供了一种高效的无锁机制，用于在领导线程和其他非领导线程之间对偶同步和可选共享数据。

该方法借鉴了 flat-combinding 技术，将通信器中的线程 0 作为领导者线程。

• 对于大小不超过 2KB 的小数组：
  • 非领导者线程首先将数据复制到 SPTD，然后与领导者线程同步，表明输入数据已就绪（使用原子序列号而非共享原子计数器）。
  • 领导者线程执行所有输入数组的逐元素 Reduce 操作。
  • 每个节点的领导者线程使用 MPI_Allreduce 对局部 Reduce 结果进行全局 Reduce。
  • 领导者线程同步，非领导者线程将最终的 Reduce 结果复制到私有缓冲区。
  • 所有线程在等待时执行 SSW-Loop。
• 对于超过 2KB 的大数组，Reduce 计算可能成为性能瓶颈，因此需要所有线程并发执行 Reduce 计算，并通过共享内存直接从每个线程的缓冲区中读取或写入数据。
  • Reduce 工作被划分为大小相等的块，避免伪共享并实现向量化计算。
  • 线程使用 SPTD 报告准备状态，并通过原子序列号标记计算完成。
  • 领导者线程调用 MPI_Allreduce 执行跨节点的 All-Reduce 操作，并通过另一个原子序列号传播最终结果。

# 任务调度器

Pure 运行时系统精心设计了一个任务调度器，它在共享内存中维护了一个名为 active_tasks 的数组。这个数组存储了一系列原子指针，每个指针对应于一个正在执行的任务，并且为系统中的每个节点和每个 rank 分配了一个条目。这些条目最初被设置为 nullptr，表示任务尚未分配。

当一个任务被创建并准备执行时，系统会为其初始化状态，并通过原子操作更新 active_tasks 数组中相应的条目，以反映该任务已被分配。这个更新过程确保了任务的执行状态对系统中的所有线程都是可见的，从而使得任务可以被其他线程“窃取”。

在任务的执行过程中，拥有任务的 rank 会开始执行一系列的 chunk，这些是任务的细分工作单元。同时，其他线程会在它们的 SSL-Loop 期间不断检查 active_tasks 数组，通过原子加载操作来寻找可执行的非空任务。

任务的执行是由两个原子整数 curr_chunk 和 chunks_done 来协调的。拥有任务的 rank（owner rank）和可能的窃取者 rank（thief ranks）都会运行相同的并发执行函数。窃取者线程会执行一个 chunk 后返回，而拥有者线程则持续执行直到所有 chunk 完成。通过使用 fetch_add 操作，线程可以确定自己应该执行哪个 chunk，如果 curr_chunk 的值已经超过了总的 chunk 数量，线程则会停止执行。

每当一个 chunk 被成功完成后，线程会原子性地增加 chunks_done 的值。拥有者线程会更新其本地存储，以避免缓存未命中。最终，拥有者 rank 会等待，直到所有的 chunk 都执行完毕，确保任务的完整执行。

值得注意的是，任务的 chunk 与应用程序的 rank 是在同一硬件线程上执行的。在 Pure 应用中，每个硬件线程都被分配给一个特定的 rank。尽管目前 Pure 还没有利用硬件加速器（如 GPU）来加速任务执行，但设计者相信 Pure 的架构完全有能力支持这种加速。

Pure 的任务调度器提供了多种执行模式和窃取算法，以适应不同的执行需求。例如，作者实现了单 chunk 执行模式和一种引导式自调度模式，后者是一种工作划分算法，它优先分配较大的工作块，然后是较小的工作块。此外，调度器还包括 NUMA 感知窃取模式，它优先从同一 NUMA 节点上的线程窃取任务，以及一种“黏性”窃取模式，允许窃取者线程返回它们最近窃取且仍在活跃状态的任务。这些特性共同确保了任务调度的高效性和灵活性。

# 评估

在伯克利 NERSC 的 Cori HPC 集群上进行了 Pure 的性能评估。该集群包含 2388 个节点，每个节点配置有 2 个插槽、16 个核心和 128GB 内存，通过 Cray Aires 进行节点间互联。实验配置启用了超线程，并采用 256 位向量宽度。每个节点上运行 2 个进程，共 32 个线程。评估使用 Intel 编译器，并将 Cray MPICH 作为性能基线。

# NAS DT 基准测试结果

• 仅通过优化消息传递机制，Pure 取得了 11% 至 25% 的性能加速。
• 引入 Pure Tasks 后，性能加速比提升至 1.7 倍至 2.6 倍。
• 辅助线程能小幅提高性能，不过仅限于剩余未使用的 CPU 核心才能使用。在这里，除了 80 个 rank 的情况下空闲了 24 个核心，其它情况下都充分利用了 CPU 核心。

# CoMD 和 miniAMR 基准测试

-在 CoMD 分子动力学应用中，Pure 在所有 rank 数下的性能均优于仅使用 MPI 及 MPI+OpenMP 的性能，分别实现了 7% 至 25% 以及 35% 至 50% 的加速比，即使在没有负载不均衡的情况下。

• 在 miniAMR 自适应网格细化应用中，Pure 至少实现了 20%，最多 50% 的性能加速。

# 集合通信性能

• Pure 在集合通信操作中的性能表现突出，这些操作的内部优化机制和数据结构设计使得 Pure 在处理大规模并行计算任务时展现出显著的效率和优势。

# 相关工作

# 总结

数十年来，由于其相对的简单性和性能优势，消息传递一直被视为并行编程的标准模型。然而，本文表明，消息传递与共享内存并非不可兼容。实际上，通过设计合适的库，可以在不牺牲大多数消息传递优点的前提下充分利用共享内存。