![[arxiv weekly] 分布式，并行计算，集群计算论文速递 [2021.05.31]](https://www.ijkxs.com/wp-content/themes/b2/Assets/fontend/images/default-img.jpg)
摘要：
最近出现了新的 I/O 使用模型。有一种趋势是将计算密集型应用程序卸载到专门的引擎/加速器。如今，许多此类应用程序都在高性能计算领域，例如金融期权建模、地震勘探、博弈物理学和生物信息学。本文说明了对 I/O 加速器的同步原语的需求，以帮助这些新兴的使用模型。它展示了来自实际应用程序的示例以及此类原语的相关性能优势。
1.介绍：
近年来，有一种趋势是将计算密集型工作负载转移到专门的 I/O 设备（例如：数学加速和物理加速）。两个显着的变化促成了这一趋势。首先，加速器受益于摩尔定律，该定律产生了极其强大的引擎，这些引擎越来越多地成为多核/多线程/多卡设备。其次，加速器变得越来越可编程。今天出现的另一个趋势是协作执行模型，其中通过结合 CPU 和加速器资源来实现最短执行时间（例如，双精度单元、分支预测硬件）。
如今，许多此类应用都在高性能计算领域，例如期权建模、地震勘探和博弈物理。这些应用程序和相关库，例如英特尔® 数学核心库（英特尔® MKL），传统上是在多线程环境中运行（通过多个内核/CPU），因此广泛使用同步原语，例如信号量、互斥体和屏障.如果可以将现有算法及其相关交互重新定位到加速器，则可以减少将现有应用程序移植到加速器所涉及的挑战。由于在这些算法中普遍存在信号量、屏障等同步原语，因此很自然地将这些原语扩展到加速器。在本文中，我们研究了此类原语的一些用例。在第二部分中，我们定义了读修改写 (RMW) 原语是什么。在第三节中，我们研究了传统（单线程）I/O 设备的 I/O 设备端 RMW 的使用情况，在第四节中，我们展示了它们在多加速器环境中的用法。
2.什么是 Read-Modify-Write (RMW) ？
读取修改写入 (RMW) 操作是硬件辅助操作，可在其内存位置以原子方式更新变量。这些操作具有悠久的历史，并且它们在广泛的同步算法中的使用已广为人知。这些操作是有效实现同步原语（如信号量、互斥体和屏障）所必需的。我们在本文中提到的 RMW 示例有：
- Compare and Exchange (addr, value1, value2)：读取addr处的值并与value1进行比较，如果value1等于addr处得到的值，则将value2写入addr。
- Atomic_Add(addr, value)：原子地递增（或递减）内存位置addr处的变量
在本文中，我们研究了在 I/O 设备上使用这些原语的必要性和好处。
3.传统 CPU-I/O Device 交互的同步原语
在本节中，我们将研究 RMW 在传统 I/O 设备中的使用。可以将主机/CPU和I/O设备之间的交互分为两类：
- Bulk data transfer (批量数据传输)
- Control information exchange (控制信息交换)
3.1. Bulk Data Transfer
批量数据传输可以根据传输方向进一步分为两个子类别。第一个子类别是从主机/CPU 到 I/O 设备的批量数据传输。这主要取决于 I/O 设备可用的带宽。由于在 I/O 设备上执行的大部分算法都是数据并行的，因此程序员已经能够通过双缓冲等技术成功地隐藏 I/O 设备数据访问延迟。程序员可以通过许多优化技术来提高此数据流的性能，例如流水线数据传输、最大化传输大小以实现更高的链接效率，以及通过放置数据结构来提高内存页面效率。
对于批量数据传输的另一个方向（I/O 设备到主机/CPU），数据访问延迟而不是带宽本身对性能至关重要。在主机上执行的代码由控制（分支）控制，因此对数据访问的延迟具有非常高的敏感性。在 I/O 设备作为主机/CPU 使用的数据生产者的应用程序中（例如：加速器与主机协作以利用其双精度单元），对系统内存的访问可能是性能限制。
另一个例子是高速网络链接，其中小网络数据包以大约内存访问时间的速度到达。传统上使用主机/ CPU 缓存来提高 CPU 延迟的性能。另一篇论文（Merits of Data Reuse Hints）检查了 CPU 缓存的扩展，以供加速器使用，以提高此数据流的性能。 I/O 设备端 RMW 专注于改进同步而不是改进原始带宽或延迟，因此对批量数据传输的性能并不重要。
3.1.1 Control Flow Between Host/CPU and I/O Device
主机/CPU 和 I/O 设备之间的控制有着广泛的使用，例如：
- 设置应用程序参数
- 在 I/O 设备上启动计算。通常称为“工作”
- 检查加速器上的状态位
- 向主机/CPU 发送完成信号，即工作完成指示
- 指示从 I/O 设备到主机/CPU 的错误情况
在传统-I/O使用场景中，利用现有的 Memory Mapped (内存映射) I/O（MMIO）write（doorbells）、中断、轮询等机制来交换控制信息并促进Host/CPU和I/O 设备之间的同步。
这些机制通常在 I/O 设备和 CPU 之间提供预定义数量的离散通信机制。例如，网络接口卡可能被设计为每个 CPU 核心有一个单独的描述符环，以促进 TCP/IP 流到处理器核心的亲和性。促进用户空间应用程序直接使用 I/O 设备的趋势带来了现有机制的可扩展性问题，因为产品设计人员必须预先定义专用于主机/CPU 通信的资源数量。一些平台架构提供了架构增强功能，例如监视器，但这些功能通常在可用性方面也受到限制。
但是，I/O 设备端 RMW 解决了上述缩放中的一些限制，并且还允许开发新的使用模型，从而改进主机 CPU-I/O 交互。例如，为 I/O 设备提供可用的 RMW 有助于创建在 I/O 设备和 CPU 之间共享的无锁队列。这种机制提供了一种可扩展的解决方案，每个 CPU 线程都可以使用驻留在系统内存中的共享队列将工作提交给 I/O 设备。 I/O 设备可以读取无锁队列，而无需昂贵的总线锁（Optimized Lock-Free FIFO Queue, Fober et. al）
重要的是要认识到，所提出的 RMW 原语为 I/O 设备配备了迄今为止仅对 CPU/主机可用的功能。这种能力是算法可以在 CPU 和 I/O 域之间轻松（并且以具有成本效益的方式）迁移的环境的基本要求。
4.多线程环境中的同步原语
接下来我们研究在多线程 I/O 环境中使用 I/O 端 RMW 语义。
4.1 Multiple Accelerators Accessing Host Defined Work Queue
在我们的第一个示例中，我们检查了多线程环境中工作队列的利用率。工作队列是在动态环境中提取粗粒度并行性的常用方法，在这种环境中，负载平衡不能先验地完成，或者这样做效率不高。一个很好的例子是 FLAME 数值线性代数库的实现（Extracting SMP Parallelism for Dense Linear Algebra Algorithms from High-Level Specifications, Tze Meng Low, Robert A. van de Geijn, Field G. Van Zee）。即使要执行的任务的大小不断变化，负载仍然保持平衡，因为工作人员（加速器）一旦完成任务就会获得新的工作。需要同步以确保没有任务被多次执行，并且不会发生饥饿。这是通过对系统内存中的共享变量进行 RMW 操作来完成的，如下面的示例工作队列实现所示。
考虑多个加速器（或加速器线程）Na 正在执行各种大小（循环）的任务（Nt）的情况。主机/CPU 上的主线程充当生产者，填充任务队列，该队列在系统内存中维护为大小为 L (L< Nt ) 的（循环）数组。它确保将新任务添加到队列的末尾，并且不会过早覆盖现有任务。为此，它维护了 producer_index（参见下面的代码）变量，该变量指向要填充的任务数组中的下一个条目，并检查该条目中任务的状态，以确保它在覆盖之前已完成新的一个。加速器（消费者）严格按照任务生成的顺序获取任务。 L 必须至少等于 Na 才能允许消费者完全并发。这种情况如图 1 所示，它描绘了工作队列的中间状态。
4.1.1 Non-RMW-based Implementation
如果没有 RMW，生产者和消费者必须通过中断严格通信，因为生产者协调对共享数据结构的访问。每个消费者都有一个驱动程序与生产者主驱动程序通信，以确保系统内存中操作的原子性。消费者通过向主机发送中断来提交他们准备执行另一个任务的状态。这记录在设备驱动程序中。主驱动程序在多个任务请求之间进行仲裁，选择获胜者，并向获胜者发出信号以开始处理。该模型承载了基于中断的通信的开销。
4.1.2 Atomic RMW-based Implementation
通过 I/O 设备可用的 RMW，生产者和消费者可以在系统内存中原子地读取和更新共享变量，从而避免中断的需要。一些协调可以由 I/O 设备处理而不涉及生产者，这增加了并发性（见图 1a）。任务的获取顺序由共享的 consumer_index 变量强制执行，该变量指示队列中的下一个可用任务。空闲消费者在共享 task_being_acquired 变量上旋转以获得访问队列中下一个任务（consumer_index）的权利。一旦消费者获得访问权限，它就会等待生产者通过旋转其共享状态变量来完成创建任务。接下来，它更改状态，以便生产者在任务完成之前不会覆盖其内容，并增加（模 L）consumer_index。然后它释放 task_being_acquired 变量，该变量在多个消费者之间实现临界区。各个任务状态变量在主动获取的消费者和生产者之间实现关键部分。任务的执行发生在所有关键部分之外。图 1b 显示了生产者和消费者的 RMW 实现的伪代码。每个阴影框都是使用单个原子 RMW 原语实现的。
4.1.3 Performance Analysis
我们使用以下定义和假设。所有周期均指 CPU 周期。获取和执行任务的平均时间是 Ce 周期，从加速器到 LLC 的延迟是 C_LLC 周期，中断传送到设备驱动程序的时间加上处理中断的时间是 C_i 周期，互斥变量 (RMW) 保留在主机缓存中，每个任务获取需要四个非流水线缓存访问（RMW），或一个中断（无 RMW）。因为我们专注于同步，所以我们忽略了创建任务或产生中断的时间。
我们研究了两种不同的场景。
- 所有任务大小相同，由加速器同步执行，或者任务都非常小。在这种情况下，对 task_being_acquired (RMW) 的缓存访问不能与其他加速器的计算重叠。在 task_being_acquired 保护的临界区内发生的对非全局共享变量的一个缓存访问也不能与其他加速器的计算或缓存访问重叠。因此，每个任务的三个访问被公开（序列化），而一个可以重叠。在非 RMW 的情况下，中断都是完全暴露的。
- 任务大小不同且足够大，导致对同步变量（RMW）的交错缓存访问，或交错中断（无RMW）。在这种情况下，与同步变量相关的中断或缓存访问可以与其他加速器的计算同时发生。
我们计算 C_tot 执行两种场景的所有任务的时间，无论有没有 RMW。
对于 C_LLC~300、C_i~4300 的情况，我们绘制了 RMW 性能收益 PG，表示为两种情况下完成时间的比率，作为任务大小的函数。结果如图2所示。
Performance Benefit (Na =number of accelerators)
显然，RMW 操作与基于中断的同步在这两种情况下的性能优势对于小型任务规模最大，而对于超过 25 万个周期的任务则可以忽略不计。对于几百到几千个周期（非常细粒度）范围内的任务大小，RMW 收益超过 100%。
4.2 Multiple Accelerators Synchronizing with Host
接下来，我们检查一个用例，其中多个加速器与主机协作。我们的示例说明了通过障碍协同使用 CPU 和加速器资源。在传统的多线程应用程序中使用率非常高的屏障 ( barriers ) 提供了一种机制，通过该机制，在所有进程都到达屏障之前，任何进程都不能超出同步点。屏障事务具有三个不同的阶段，到达、等待释放和屏障释放。有许多已发布的障碍变体，例如集中式障碍、软件组合树和带有局部旋转的树障碍。下面显示了屏障的一个简单且流行的示例实现。
Barrier Init:
Set counter value to 0; Set lock to 0;
Barrier:
Acquire(lock); [Uses SWAP atomic] - RMW
if counter is zero set flag to zero.
increment counter
Release(lock) ; [ Uses SWAP atomic] - RMW
if counter equals number of waiting processes
set counter to zero
set flag to one
else
repeat:
until flag is one
end if
一个可以利用屏障在工作线程之间进行同步的示例应用程序是 Gauss-Seidel 方程求解器的并行执行。 Gauss-Seidel 是一种迭代求解器，它会继续运行，直到收敛到目标误差范围内的解。该算法由矩阵内周围元素之间的依赖关系组成。
为了并行求解算法的元素，数据相关组以多种方式分组。第一个数据分区称为红黑。这允许将算法分成不具有数据依赖性的两个独立阶段。第二种方法是将阵列分成可能并行发生的单独扫描。扫描 A 和 B 完成后，不得计算与每次扫描相邻的数据点。
图 4 显示了加速器工作线程与数据分区矩阵的示例关联。引入了许多全局同步点，它们可以作为屏障来实现。在每次扫描到与每次扫描相邻的元素的同步处理之间的处理结束时需要一个屏障。
4.2.1 Non-RMW-Based Implementation
在传统（没有 I/O 端 RMW）中，加速器必须在每个工作任务完成时向 IA 处理器发出信号。该信号通常是加速器引发的中断。设备驱动中断处理程序将代表加速器执行并减少屏障计数器。更新的原子性是通过共享中断队列实现的。当计数器达到零时，屏障被同步并且正在等待屏障的主线程被释放。正如读者会注意到的那样，中断（或者总线锁）会带来很大的开销。
4.2.2 RMW-Based Implementation
使用 RMW 原语，加速器可以用系统内存中的共享变量（或系统缓存，如果有适当的硬件可用）中的原子增量替换中断。下一部分显示了因此可实现的性能优势。它还强调了将从这些原语中受益的应用程序的性质。上面代码参考的灰色部分突出显示了 RMW 的潜在用途。本质上，屏障计数变量可以通过使用 RMW 原语就地更新。
4.2.3 Performance Analysis
下图显示了在我们的用例中使用 RMW 操作的好处。从下图中可以明显看出，主要节省来自用更快的 RMW 操作替换代价高昂的中断。还需要注意的是，这些好处主要是针对那些卸载到加速器的小问题的应用程序。
5.结论
我们在本文中研究了几种应用模型。我们相信，要为跨主机和 I/O 设备的多加速器和多线程应用程序的新兴应用程序领域提供最佳服务，I/O 端 RMW 是关键要素。这些原语不仅提供了编程的便利，而且通过克服传统 CPU-I/O 机制（锁、中断）的限制，它们提供了显着的性能提升。对于一些具有代表性的示例并行工作负载（工作队列），我们展示了与基于中断的同步相比，RMW 操作可以提供超过两倍的性能优势。当存在多线程加速器的情况下需要细粒度同步时，这些增益通常在使用中非常重要。
