下载本文的PDF版本 PDF

数据并行计算

数据并行性是利用当今多核 GPU 强大功能的一个关键概念。

CHAS. BOYD，微软

用户始终关心性能。

虽然通常只是确保软件只做它应该做的事情，但在许多情况下，深入底层并利用处理器的基本特性至关重要。

直到最近，性能提升还并不困难。处理器不断变得更快。等待一年让客户的硬件升级是一种有效的优化策略。然而，如今，单个处理器不会变得更快；系统只是拥有更多的处理器。

关于针对多处理器内核的编码范式已经有很多评论，但数据并行范式是一种较新的方法，可能最终更容易编码，也更容易让处理器制造商实现。

本文提供了数据并行计算的高级描述以及关于如何以及在何处使用它的一些实用信息。它还涵盖了数据并行编程环境，特别关注那些基于可编程图形处理器的环境。

一点背景知识

虽然处理器性能增长率看起来几乎是神奇的，但它受到物理基本定律的限制。在整个 90 年代，由于每芯片门数、时钟速度和指令级并行性的改进，这些定律使处理器的性能呈指数级增长。然而，从 2003 年开始，物理定律（功耗和热量）结束了时钟速度的增长。然后，日益复杂的 ILP（指令级并行性）方案（分支预测、推测执行等）的硅面积需求变得过高。今天，性能提升的唯一剩余基础是门数。

认识到这一点，制造商已经调整结构，停止推动时钟频率，转而关注门数。预测表明，至少在未来六到八年内，每芯片门数每两年可以翻一番。如何处理所有这些门？您制造更多的内核。因此，每个芯片的内核数量将每两年翻一番，到 2012 年将达到今天的四倍内核数（最多 32 个内核）。

客户会欣赏这种增长速度，但只有当软件能够跨所有这些新内核扩展时，他们才会受益。这是未来五到十年性能软件面临的挑战。在未来十年，软件性能的限制因素将是软件开发人员重构代码以使其扩展速度与内核数量增长速度保持同步的能力。

并行编程

并行编程很困难。我们反对在大多数语言中使用 GOTO 语句，但并行执行就像在执行期间随机地将它们洒在整个代码中。程序员从早期教育开始就形成的关于执行顺序的假设不再适用。

单线程冯·诺依曼模型是可理解的，因为它是确定性的。并行代码容易出现死锁和活锁、竞争条件等错误，这些错误可能非常微妙且难以识别，通常是因为 bug 是不可重复的。这些问题非常严重，以至于尽管经过数十年的努力和数十种不同的方法，但没有一种方法真正获得广泛采用，甚至没有就它是解决问题的最佳方案达成一致。

一个同样微妙的挑战是性能扩展。阿姆达尔定律指出，并行性可达到的最大加速比是不可并行化代码比例的倒数。如果给定代码库的 10% 不可并行，即使在无限数量的处理器上，它也无法获得超过十倍的加速。

虽然这是一个有用的指导原则，但确定有多少代码最终以并行方式运行非常困难。由于对共享资源的争用或访问过多远程存储器位置的要求，序列化可能会意外发生。

传统的并行编程方法（通过锁进行线程控制、消息传递接口等）通常具有有限的扩展能力，因为这些机制可能需要序列化阶段，而这些阶段实际上会随着内核数量的增加而增加。如果每个内核都必须与单个内核同步，则会产生串行代码的线性增长，但如果每个内核都必须与所有其他内核同步，则串行化可能会呈组合式增长。

毕竟，任何序列化代码在四核机器上都会慢四倍，但在 40 核机器上会慢 40 倍。

性能扩展的另一个问题更加根本。多核并行编程在游戏中的一个常用方法是从自上而下的分解开始。相对隔离的子系统被分配到单独的内核，但是一旦代码库中的子系统数量达到极限会发生什么？由于在这个级别重构代码可能是普遍存在的，因此通常需要进行重大重写才能在下一个更精细的级别分解子系统，并且对于每个硬件世代都是如此。

由于所有这些原因，将主要代码库转换为并行范式非常耗时。将不确定性的所有细微影响降至可接受的水平可能需要数年时间。到那时，内核数量的增长可能已经超过了新代码结构可以扩展到的并行度水平。不幸的是，内核数量的增长速度可能超过我们适应它的能力。

因此，现在是寻找新范式的时候了——理想情况下，这种范式可以随着内核数量的增加而扩展，而无需在每次针对新的内核数量时都重构应用程序架构。毕竟，这不仅仅是选择一种在固定内核数量下运行良好的范式；而是选择一种在内核数量不断增加的情况下继续扩展而无需更改代码的范式。我们需要确定更精细的并行性粒度。

数据并行编程

考虑到难以找到足够的子系统任务来分配给数十个内核——其中唯一数量相当的元素是数据元素——数据并行方法只是将单个数据元素分配给单独的逻辑内核进行处理。我们不是按子系统分解代码，而是寻找每个子系统内的细粒度内部循环并将其并行化。

对于某些任务，可能有数千到数百万个数据元素，从而可以分配给数千个内核。（虽然这在未来可能会成为一个限制，但它应该能够使代码扩展到未来十年左右。）例如，现代 GPU 可以支持数百个 ALU（算术逻辑单元），每个 ALU 有数百个线程，从而在芯片上同时处理近 10,000 个数据元素。

数据并行处理器的历史始于创建更宽更宽的向量机的努力。硬件和数据并行算法的早期工作大部分是由 MasPar、Tera 和 Cray 等公司开创的。

今天，各种细粒度或数据并行编程环境都可用。其中许多环境通过支持 GPU 最近获得了关注。它们可以分为以下几类

旧语言（C*、MPL、Co-Array Fortran、Cilk 等）。已经开发了几种用于细粒度并行编程和向量处理的语言。许多语言仅在语法上与众所周知的语言略有不同。它们很少支持各种平台，并且可能无法商用或长期支持更新、文档和材料。

新语言（XMT-C、CUDA、CAL 等）。这些语言由相关的硬件公司开发，因此得到了很好的支持。它们在语法上也与当前的 C++ 编程模型非常接近；然而，这可能会导致问题，因为该语言随后没有明确表示数据并行编程或处理器硬件的独特方面。虽然这可以减少初始端口所需的更改，但生成的代码隐藏了并行行为，使其更难以理解、调试和优化。通过语法简化串行代码的初始端口一开始就不是那么有用，因为为了获得最佳性能，通常必须用数据并行版本替换整个算法。此外，为了简单起见，这些 API 可能不会公开特定于图形的硅的全部功能，这意味着硅面积未得到充分利用。

基于数组的语言（RapidMind、Acceleware、Microsoft Accelerator、Ct 等）。这些语言基于数组数据类型和对其进行操作的特定内部函数。转换为这些语言的算法通常会生成比以前更短、更清晰且很可能更快的代码。然而，将设计概念重构为数组范式的挑战仍然是采用这些语言的障碍，因为它必须在很高的抽象级别上完成。

图形 API（OpenGL、Direct3D）。最近在 GPGPU（图形处理单元上的通用计算）方面的研究发现，虽然使用图形 API 的初始启动可能很困难，但它们确实提供了到硬件的直接映射，从而可以进行非常具体的优化，并访问其他方法可能不允许的硬件功能。例如，Naga Govindaraju1 和 Jens Krüger2 的工作依赖于对固定功能三角形插值器和混合单元的访问，而此处提到的较新语言通常不公开这些单元。此外，还有良好的商业支持以及已经使用它们的大量经验丰富的开发人员社区。

GPU 作为数据并行机器

GPU 是典型 PC 中使用率第二高的处理器。在过去十年中，它的发展非常迅速，性能水平可以大大超过 CPU，至少在适当的工作负载下是这样。3 GPU 的发展是由 3D 渲染驱动的，这是一个非常适合数据并行的问题，这使得 GPU 成为数据并行代码的绝佳目标。由于这种显着不同的工作负载设计点（处理模型、I/O 模式和引用局部性），GPU 具有显着不同的处理器架构和存储器子系统设计，通常具有更宽的 SIMD（单指令，多数据）宽度和更高延迟、更高带宽的流式存储器系统。通过图形 API 公开的处理模型是任务串行流水线，由几个数据并行阶段组成，这些阶段根本不使用线程间通信机制。虽然出现了用于处理顶点或像素的单独阶段，但实际架构更简单一些。

如图 1 所示，现代 DirectX10 类 GPU 具有一个处理器阵列，它与专用硬件结合执行每个阶段的计算工作。在多边形顶点处理之后，使用专用硬件插值器单元将每个多边形转换为像素以用于像素处理阶段。该单元可以被认为是地址生成器。在流水线的末端，另一个专用单元将完成的像素混合到图像缓冲区中。此硬件通常用于将结果累积到目标数组中。此外，所有处理阶段都可以访问专用的纹理采样单元，该单元以各种数据元素格式对 1D、2D 或 3D 源数组执行线性插值读取。

在这些特殊工作负载要求的塑造下，现代 GPU 具有

GPU 的存储器子系统设计用于更高的 I/O 延迟，以实现更高的吞吐量。它假设非常有限的数据重用（读/写访问中的局部性），具有小型输入和输出缓存，这些缓存更多地设计为 FIFO（先进先出）缓冲区，而不是避免往返存储器的机制。

最近的研究已经研究了将这些处理器应用于 3D 渲染以外的其他算法。已经有一些应用程序显示出比 CPU 代码显着的优势。一般来说，那些最接近 3D 图形的原始设计工作负载（例如图像处理）并且可以找到利用十倍计算优势或十倍带宽优势的方法的应用程序表现良好。（这项工作的大部分都编目在 Web 上，网址为 http://www.gpgpu.org。）

这项研究已经确定了一些有趣的算法。例如，压缩可变长度记录数组是一项在并行前缀和或扫描上具有数据并行实现的任务。前缀和算法计算所有先前数组元素的总和（即，行 r 中的第一个输出元素是 r0，而第二个输出元素是 o1 = r0 + r1，第 n 个输出元素是 on = r0 + r1 + … + rn）。使用此方法，可以累积记录大小列表以计算每个记录元素要写入的绝对地址。然后，写入可以完全并行地进行。请注意，如果写入按顺序完成，则内存访问模式仍然是完全顺序的。4

使代码数据并行

在开始编写代码之前，请检查是否存在已知的数据并行情况的任务。通常，您可以找到现有的库例程，用于使用数据并行硬件加速常见任务。大多数数据并行编程环境都包含此类库，作为用户开始采用其技术的便捷方式。

如果您需要编写自定义数据并行代码，则该过程类似于局部优化工作。您可以逐步采用数据并行编程，因为您可以一次识别和优化关键的内部循环，而不会扰乱代码库的更大规模结构。以下是将代码转换为数据并行模型的基本步骤

  1. 步骤 1：识别看起来是数据并行的关键任务。
  2. 步骤 2：为此任务识别数据并行算法。
  3. 步骤 3：选择数据并行编程环境。
  4. 步骤 4：实现代码。
  5. 步骤 5：评估性能扩展率。
  6. 步骤 6：转到步骤 1。

步骤 1：识别看起来是数据并行的关键任务

查找不严重依赖数据元素之间交叉通信的代码段，或者相反，查找可以处理而无需过多了解彼此的一组数据元素。查找可以规则化的数据访问模式，而不是任意/随机的模式（例如线性数组与稀疏树数据结构）。

在搜索要并行化的候选对象时，您可以使用阿姆达尔定律评估性能潜力：只需注释掉此候选任务（模拟无限并行性）并检查总性能变化。如果没有显着改进，那么付出并行化的努力将不会得到回报。

步骤 2：为此任务识别数据并行算法

通常，一个好的查找地点是历史书籍（数学）或 Tera/Cray 为其向量处理器开发的例程。例如，在计算机开发之前，已经确定了双调排序很有趣，但在当前基于缓存的机器兴起期间，双调排序失宠了。其他示例是基数排序和用于打包稀疏数据的前缀和（扫描）操作。

步骤 3：选择数据并行编程环境

今天，许多数据并行编程环境都可用。在评估中使用的许多标准与任何开发环境的标准相同。要查找的领域是

步骤 4：实现代码

将其编码，至少在伪代码级别。如果实现结果表明需要一个或两个以上需要线程间通信的地方，那么这可能不是一个足够的数据并行算法。在这种情况下，可能需要寻找另一种算法（步骤 2）或另一个要并行化的任务（步骤 1）。

步骤 5：评估性能扩展

给定内核数量下的性能很有趣，但不是关键点。（如果您要检查这一点，请务必使用真实的“之前”情况进行比较。）要检查的更重要的指标是新代码如何随着内核数量的增加而扩展。如果没有性能平台期的迹象，则系统将具有一定的扩展空间。毕竟，相对于单核的绝对性能不如它随时间推移的内核数量增长的扩展程度重要。

总结

GPU 性能提示

如果目标是 GPU，是否有可以利用现有图形相关硬件的操作？您的数据类型是否足够小？GPU 旨在处理小型数据元素，因此媒体数据（图像/视频像素或音频样本）非常适合。或者，在 GPU 上排序时，单独处理键索引对通常是一种胜利。然后，数据记录的实际移动可以在 CPU 上完成，也可以在 GPU 上作为单独的通道完成。

GPU 针对处理相似数据元素的 1D、2D 或 3D 数组进行了优化。数组操作通常在使用 GPU 硬件时更快，因为它可以透明地优化它们以实现空间相干访问。

在读取此类数组时，GPU 可以轻松地线性插值规则数组数据。这有效地启用了浮点（模糊）数组索引。许多数学算法使用数组元素的简单线性插值或略微更高阶的方案，这些方案可以实现为几个线性插值。GPU 硬件已将很大一部分硅分配用于优化这些操作的性能。

涉及将值累积或求和到一组结果中（而不是仅仅写入/复制）的算法可以利用 GPU 上另一个大的特殊硅块：混合器旨在有效地将值合成或累积到数组中。一些矩阵数学算法和归约运算已在此处显示出优势。

寄存器压力

某些架构（例如 GPU）很灵活，因为它们可以根据每个线程使用的寄存器数量将可变数量的线程分配给内核。这使得可以在需要较少临时寄存器时使用更多线程，但对于需要更多寄存器的算法，则会减少可用的线程（和并行性）。关键是将任务分解为更简单的步骤，这些步骤可以在更多的并行线程中执行。这是数据并行编程的本质。

例如，标准的 8x8 图像 DCT（离散余弦变换）算法在其后半部分对转置数据进行操作。转置可能需要数十个寄存器才能就地执行，但将其分解为两个通道，以便转置发生在中间 I/O 中，则每个半部分只需要少量寄存器。这种方法将性能从远低于 CPU 提高到高度优化的 SSE 汇编例程的三倍。

归约提示

归约是常见的操作：查找一组数据的总和、平均值、最小值、最大值或直方图。计算很容易数据并行，但输出写入是必须仔细管理的线程间通信的示例

初始实现为所有线程分配了一个共享位置以写入，但执行完全被对该位置的写入争用序列化。发现分配归约目标的多个副本，然后在单独的步骤中将这些副本归约下来要快得多。关键是分配足够的中间位置来覆盖您想要扩展到的内核数量（数百个），从而达到性能水平。

编程存储器子系统

数据并行范式也扩展到存储器子系统。完整的数据并行机器不仅能够单独处理各个数据元素，而且还能够并行读取和写入这些元素。存储器子系统的这种特性与执行模型对于性能同样重要。例如，I/O 端口是共享资源，如果多个线程不争用同一个端口，则性能会提高。

操作的数据结构暗示着内存访问模式。我们已经看到过这样的情况：从基于指针的数据结构（如链表或稀疏树）切换到数据并行友好的数据结构（规则数组、网格、打包流等）允许代码变为计算密集型而不是内存密集型（在 GPU 上可能快 10 倍）。这是因为内存通常组织成页面，并且在页面之间切换存在一些开销。对数据元素和线程进行分组，以便可以从同一页面读取（或写入）许多结果有助于提高性能。

许多类型的树和其他稀疏数据结构都具有数据并行友好的基于数组的实现。虽然使用这些结构非常传统，但它们的实现对于接受过基于指针的方案培训的开发人员来说是非直观的。5

GPU 存储器子系统最重要的特性是缓存架构。与 CPU 不同，GPU 几乎没有任何读/写缓存。假设将有大量数据流经处理器，以至于它会溢出几乎任何缓存。因此，唯一存在的缓存是单独的直读和直写缓冲区，它们平滑了数据流。因此，选择不依赖于大于可用少量本地寄存器规模的数据重用的算法至关重要。例如，直方图计算需要比典型寄存器分配支持更多的读/写存储来包含直方图 bin。即将推出的 GPU 架构开始添加读/写缓存，以便更多算法可以工作，包括合理大小的直方图，但由于这些缓存仍然比 CPU 上的缓存小 10 到 100 倍，因此这仍然是选择算法时的关键标准。

GPU 作为数据并行硬件

GPU 系统便宜且广泛可用，许多程序员（例如游戏开发人员）已经确定了高效编程的关键方法。

首先，利用芯片上的所有硅可能很重要。与 CPU 相比，不点亮图形特定门的应用程序已经处于劣势。例如，Govindaraju 的排序实现显示出使用混合硬件的显着优势。6

确保编程效率的另一种方法是保持数据元素较小。这种额外的硬件假设图形数据类型在大小为 16 字节或更少时是最佳的，理想情况下为 4 字节。如果您可以使您的数据看起来像 GPU 通常处理的数据，您将获得巨大的好处。

不幸的是，GPU 的高速存储器系统（吞吐量比 CPU 前端总线快 10 倍）通常通过比 CPU 存储器慢 10 倍的链路连接到 CPU。在低延迟场景中，最大限度地减少通过此链路的数据和控制流量对于 GPU 性能至关重要。秘诀是尽可能将数据保留在 GPU 的存储器中，仅在需要持久存储时才将其带回 CPU。有时这可能涉及在 GPU 上执行小型非数据并行任务，因为将所需数据交叉发送到 CPU、同步它并将其发送回来的成本甚至可能更高。

GPU 通用性

由于设计周期较短，GPU 的发展速度比 CPU 更快。这种发展通常朝着通用性增加的方向发展。现在我们看到 GPU 通用性正在超越基本渲染的需求，扩展到更通用的应用程序。例如，在过去一年中，已经出现了新的 GPU 环境，它们公开了图形 API 未公开的功能。有些现在支持线程之间的数据共享和更灵活的内存访问选项。

这使得 GPU 上出现了全新的算法类别。最明显的是，更通用的 3D 处理方法变得可行，包括操作用于光线追踪、辐射度或碰撞检测的加速数据结构。其他明显的应用是在媒体处理（照片、视频和音频数据）中，其中数据类型与 3D 渲染的数据类型相似。使用类似数据类型的其他领域是地震和医学分析。

未来硬件演进：CPU/GPU 融合？

由于对一致编程模型的需求压力，指令格式等处理器功能可能会融合。GPU 可能会迁移到更窄的 SIMD 宽度，以提高分支代码的性能，而 CPU 则转向更宽的 SIMD 宽度，以提高指令效率。

然而，事实仍然是，某些任务可以使用数据并行算法更有效地执行。由于效率在这个功耗受限的时代至关重要，因此可以实现任务到每个处理器模型的最佳映射的两点设计可能会持续一段时间。

此外，如果硬件继续领先于软件，则系统很可能在给定时间点拥有比应用程序可以处理的更多的内核，因此提供处理器类型的选择会增加更多内核被使用的机会。

可以想象，数据并行系统可以支持现代串行 CPU 内核的整个功能集，包括丰富的线程间通信和同步机制集。然而，这些功能的存在可能在长期来看并不重要，因为使用的传统同步功能越多，性能扩展到高内核数量的速度就越慢。最快的应用程序不是那些将其现有单线程甚至双线程代码移植过来的应用程序，而是那些切换到不同的并行算法的应用程序，这些算法扩展性更好，因为它对通用同步功能的依赖性更小。

图 2 显示了已使用数据并行范式实现且具有不同程度成功的算法列表。它们大致按照与数据并行模型匹配程度的顺序排序。

数据并行处理器正变得越来越普及，尤其是现在消费级 GPU 支持数据并行编程环境。这种范式转变为及时适应的程序员带来了新的机会。

数据并行行业正在发展，但没有软件开发人员的太多指导。先到者将有最好的机会驱动和塑造即将到来的数据并行硬件架构和开发环境，以满足其特定应用领域的需求。

当有效地编程时，GPU 可以比当前的 PC CPU 更快。现在是利用这种新型处理器的时候了，方法是确保代码库中的每个任务都分配给最适合该任务的处理器和存储器模型。问

参考文献

  1. Govindaraju, N.K., Gray, J., Kumar, R., Manocha, D. 2006。GPUTeraSort：用于大型数据库管理的高性能图形协处理器排序。2006 年 SIGMOD 国际数据管理会议论文集； http://research.microsoft.com/research/pubs/view.aspx?msr_tr_id=MSR-TR-2005-183）。
  2. Krüger, J., Westermann, R. 2003。用于数值算法 GPU 实现的线性代数运算符。 Transactions on Graphics 22(3)。
  3. Blythe, D. 2008。GPU 的崛起。IEEE 96 论文集(5)。
  4. Shubhabrata, S., Lefohn, A.E., Owens, J.D. 2006。一种工作高效、步骤高效的前缀和算法。使用新型商品架构的边缘计算研讨会论文集：D-26-27。
  5. Lefohn, A.E., Kniss, J., Strzodka, R., Sengupta, S., Owens, J.D. 2006。Glift：通用、高效、随机访问 GPU 数据结构。 Transactions on Graphics 25(1)。
  6. 参见参考文献 1。

建议进一步阅读

GPU Gems 2
http://developer.nvidia.com/object/gpu_gems_2_home.html

GPU Gems 3
http://developer.nvidia.com/object/gpu-gems-3.html 第 39 章关于前缀和

Glift 数据结构
http://graphics.cs.ucdavis.edu/~lefohn/work/glift/

Rapidmind
http://www.rapidmind.net/index.php

Intel Ct
http://www.intel.com/research/platform/terascale/TeraScale_whitepaper.pdf

Microsoft DirectX SDK
http://msdn2.microsoft.com/en-us/library/aa139763.aspx

Direct3D HLSL
http://msdn2.microsoft.com/en-us/library/bb509561.aspx

Nvidia CUDA SDK
http://developer.nvidia.com/object/cuda.html

AMD Firestream SDK
http://ati.amd.com/technology/streamcomputing/stream-computing.pdf

Microsoft Research 的 Accelerator
http://research.microsoft.com/research/pubs/view.aspx?type=technical%20report&id=1040&0sr=a
http://research.microsoft.com/research/downloads/Details/25e1bea3-142e-4694-bde5-f0d44f9d8709/Details.aspx

CHAS. BOYD 是微软的软件架构师。他于 1995 年加入 Direct3D 团队，并为 DirectX 3 以来的版本做出了贡献。在此期间，他与硬件和软件开发人员密切合作，推动了可编程硬件着色器和浮点像素处理等功能在消费级图形中的应用。最近，他一直在研究大众市场消费系统的新的处理架构和应用。

acmqueue

最初发表于 Queue 第 6 卷，第 2 期—
在 数字图书馆 中评论本文




更多相关文章

David Crandall, Noah Snavely - 使用互联网照片集对人和地点进行建模
本文介绍了我们使用在线照片集重建关于世界及其居民（在全球和本地范围内）信息的工作。这项工作受到社交内容共享网站的显着增长的推动，这些网站创建了大量用户生成的在线视觉数据集合。仅 Flickr.com 目前就托管了超过 60 亿张由超过 4000 万独立用户拍摄的图像，而 Facebook.com 表示，它每天增长近 2.5 亿张照片。


Jeffrey Heer, Ben Shneiderman - 用于可视化分析的交互式动态
数字数据规模和可用性的不断提高为公共政策、科学发现、商业策略甚至我们的个人生活提供了非凡的资源。然而，为了充分利用这些数据，用户必须能够理解它：追求问题、发现感兴趣的模式并识别（并可能纠正）错误。与数据管理系统和统计算法相结合，分析需要根据领域特定的意义对数据中发现的集群、趋势和异常值进行情境化的人工判断。


Robert DeLine, Gina Venolia, Kael Rowan - 使用代码地图进行软件开发
为了更好地了解专业软件开发人员如何使用代码的可视化表示，我们采访了微软的九位开发人员，以确定常见的场景，然后调查了 400 多位开发人员，以更深入地了解这些场景。


Brendan Gregg - 可视化系统延迟
当 I/O 延迟以可视化热图的形式呈现时，可能会出现一些有趣而美丽的模式。这些模式提供了对系统实际性能以及最终用户应用程序体验到的延迟类型的深入了解。在这些模式中看到的许多特征仍然不为人所知，但到目前为止，它们的分析揭示了以前未知的系统行为。



© 保留所有权利。

© . All rights reserved.