Optimization Techniques for GPU Programming
【综述解析·III】Optimization Techniques for GPU Programming
本文是一篇 CSUR长文，80 页，400+文献整理而成。作者来自阿姆斯特丹自由大学，QS209.
本文前四章营养较少，可以从第五章看起
摘要： 在过去十年中，图形处理器（GPU）在高性能计算领域中发挥了重要作用，并持续推动物联网、自动驾驶和百亿亿次计算等新兴领域的发展。因此，深入理解如何高效地挖掘这些处理器的性能具有重要意义，而这并非易事。本文综述了过去14年中发表的450篇相关文献，系统梳理了其中提出的各类优化技术。我们从多个视角对这些优化策略进行了分析，结果表明各类优化手段之间存在高度关联性，这也凸显了诸如自动调优等技术的必要性。
一、引言
图形处理器（GPU）在过去数十年间彻底改变了高性能计算（HPC）的格局，并被认为是近年来人工智能（AI）领域取得诸多进展的重要推动因素。GPU 最初作为游戏图形处理的专用处理器而诞生，随后被适配为高性能计算系统中的协处理器，用于处理更为广泛的计算任务。近十年来，GPU 再次开始渗透到诸如物联网设备与自动驾驶汽车等新兴市场。当前，第一代百亿亿次超级计算机正在部署之中，其中大多数采用 GPU 作为主要的计算平台。然而，与以 NVIDIA 占据主导地位的 pre-exascale 时代不同，现阶段的部分系统开始采用来自 Intel 和 AMD 的 GPU，这些硬件伴随着相对新颖且各异的编程模型。因此，在 GPU 硬件、应用场景与编程体系快速多样化的背景下，总结过去十四年在 GPU 优化方面积累的经验变得尤为迫切。
自 2007 年 CUDA 编程模型引入以来，GPU 编程逐渐变得更为普及。紧随其后的 OpenCL 标准于 2008 年底发布，使得在更多种类的处理器上执行 GPU 程序成为可能。尽管随后出现了许多用于简化应用开发的高级语言与领域特定语言，CUDA 与 OpenCL 仍是目前主流的 GPU 编程语言。GPU 编程通常被视为一个专业化领域，尤其在性能优化方面，需要深入理解底层硬件的运行机制，并在众多权衡因素中做出合理取舍。因此，已有大量研究提出了被统称为“优化”的代码变换、编程技术与方法，旨在提升 GPU 应用程序的性能。
本综述首次对该类优化技术进行了系统性的总结与分析，重点关注可由程序员在现有硬件平台上借助 CUDA 和 OpenCL 等编程语言实现的软件层面优化技术。不涵盖编译器中间表示上的变换或底层架构层面的性能优化。本文采用 CUDA 的术语体系进行表述，但所讨论的大多数优化策略同样适用于 OpenCL 及非 NVIDIA 硬件平台。
本综述面向多个研究与实践群体：一方面，GPU 程序员可从中了解多种可应用于实际开发的性能优化方法；另一方面，编程语言与编译器研究者可识别 GPU 编程中的关键挑战，并据此改进语言设计以进一步简化性能优化过程；此外，计算机体系结构研究者与硬件制造商可据此观察体系结构可编程性的演进路径，并探讨其未来的增强方向。
本文首先介绍与本研究相关的已有工作，随后描述我们从450篇文献中提取优化技术并构建数据库以供分析的方法。接着，我们简要介绍 GPU 编程基础，并对各类优化技术进行详细分类与分析。最后，我们从多个视角对优化进行综合性讨论，指出不同优化策略之间具有高度的相互关联性，许多关键因素相互依赖，因此诸如自动调优（auto-tuning）等技术在实现高效利用方面具有重要价值。
二、相关工作
本节回顾了以往关于 GPU 优化技术，或更广义上的并行体系结构优化的研究工作。Bacon 等人综述了面向编译器的高级程序重构技术，并指出这些技术对于手动优化同样具有实际意义。他们将“优化”定义为“优化性变换”的简写（注：optimization→optimizing transformation），认为优化的总体目标是在最大化计算资源利用率的同时，最小化操作次数、内存带宽的使用以及整体内存占用。他们还指出，随着体系结构日益复杂，优化过程也变得愈加困难。
Kowarschik 等人在 Bacon 提出的基于循环的优化基础上，进一步引入了关于缓存与数据局部性的优化。尽管其工作主要面向 CPU，但其中提出的优化策略对于 GPU 编程也具有重要参考价值。2008 年，Ryoo 等人发表了两篇专门面向 GPU 优化的综述文章。这些工作是早期关于 GPU 编程优化的研究之一，发表于 CUDA 编程模型发布后不久，主要关注哪些代码适合在 GPU 上运行，以及如何通过调整实现高性能，强调在性能优化中需合理权衡多个因素，并提出自动调优对于性能提升的重要性。
2012 年，Stratton 等人对多个 GPU 应用与计算核（kernels）进行了调查，提出了一系列优化模式及其所针对的性能问题，并逐一分析了每种模式所要解决的瓶颈。同年，Brodtkorb 等人探讨了基于 GPU 架构特性的优化策略，特别强调了多线程对内存延迟的隐藏能力以及内存层级结构对性能的影响。他们提出一种以性能分析为导向的方法，通过比较三个版本的计算核（原始版本、移除内存访问的版本以及仅包含内存访问的版本），来构造一个在多种性能需求之间取得平衡、可自动调优的高效内核。2008 年与 2012 年的这些研究总结了作者在 GPU 编程中的实践经验，并归纳出一系列普适的优化原则。
与此不同，本文的研究基础是我们所分析的文献中提取出的 GPU 优化方法。此外，还有若干面向特定应用领域的综述也讨论了 GPU 优化策略。例如，Tran 等人分析了图处理领域中 GPU 的使用，重点强调数据布局与负载分布在性能优化中的重要作用；Al-Mouhamed 等人回顾了结构化网格计算中的优化技术与高级编译器，区分了面向体系结构的通用优化（如带宽与局部性优化）与面向具体领域的定制优化（如迭代间同步）；Mittal 等人针对深度学习领域，总结了 GPU 上的优化策略，并区分了计算瓶颈与存储瓶颈两大类，分别提出了针对性的优化方案。
尽管本综述聚焦于程序员手动实施的优化方法，仍有大量研究专注于通过改进 GPU 硬件架构以提升整体性能。Khairy 等人对 GPU 架构层面的优化进行了系统综述，其研究不仅为本文所讨论的软件优化提供了背景信息，也为读者深入理解 CPU 与 GPU 之间的体系结构差异提供了有益参考。
三、方法论
本节概述了本文在文献检索、筛选与处理过程中所采用的方法。我们借助文献分析工具 litstudy 在 Scopus 数据库中进行文献查询与组织，从而建立一个涵盖 GPU 优化研究的文献集合。该方法分为多个阶段，旨在尽可能全面地覆盖与 GPU 优化相关的研究成果。
之所以采用如此系统的方法，原因在于我们观察到许多研究在描述类似概念时使用了不同的术语，通过广泛收集文献，有助于我们理解不同作者对相似或重叠概念的命名差异。此外，该方法还使我们能够识别出在不同研究中更为常见的优化技术（详见第4节的数据分析）。我们还特别关注对 AMD GPU 及 OpenCL 编程的文献覆盖，以补充这些在现有综述中相对缺失的内容。
图1展示了我们在附录B中详细介绍的文献筛选流程。在第一阶段，我们基于 GPU 优化相关关键词，在 Scopus 数据库中进行了两次查询，分别于2019年11月29日和2021年5月27日执行，以涵盖最新发表的研究成果。初始检索得到 3,973 篇文献，我们首先根据标题、发表会议/期刊和关键词进行初筛，保留了 1,120 篇。
第二阶段中，我们进一步加入摘要与作者信息作为筛选依据，最终选定 532 篇核心文献，并将 202 篇未入选但包含其他相关信息的文献标记为辅助文献。从这些辅助文献中，我们进一步选取了10篇，第二阶段结束后共获得 542 篇候选文献。
在第三阶段，我们对候选文献进行深入浏览，依据预设标准（详见图1及附录B）筛选出确实包含 GPU 优化内容的文献，最终得到 401 篇。在此基础上，我们分析了这些文献所引用的其他高频文献，识别出 149 篇尽管未在初选集中，但被频繁引用且内容重要的文献，并最终纳入其中的 49 篇。经过第二与第三阶段的筛选，我们共获得 450 篇用于优化分析的文献。
在第四阶段，我们从这 450 篇文献中提取相关信息，包括所采用的优化技术、使用的 GPU 类型以及明确提及的性能瓶颈等，并将这些信息整理入数据库。
第五阶段对上述优化技术进行分析与归纳。针对感兴趣的读者，附录A提供了完整的优化技术参考材料。由于篇幅限制，第6节仅给出该参考材料的简要摘要。第7节则分析了这些优化与性能瓶颈之间的关联。
四、数据分析
本节对基于检索查询所选定的文献集进行分析，补充细节及图表见附录C。图2展示了根据 Scopus 数据库中记录的发表年份统计的年度文献数量。从图中可见，GPU 优化相关研究始于2008年，随后年度发表数量持续增长，并在2013年左右趋于稳定。2016年的文献数量呈现出显著上升，但进一步分析表明该年度的数据未存在异常，仅是该年发表数量高于平均水平。在撰写本文时，2021年的全部文献尚未完全收录。
Scopus 同时提供了文献的发表来源信息，结果显示，GPU 优化研究最常见的会议为 IPDPS、SC 和 PPoPP，最常见的期刊为 Concurrency & Computation: Practice and Experience (CPE)、IEEE Transactions on Parallel and Distributed Systems (TPDS) 和 Journal of Parallel and Distributed Computing (JPDC)。整体来看，GPU 优化的研究成果广泛分布于多个出版平台，表明该研究主题具有高度的跨领域性质，并非局限于某一特定学术社区或会议。
图4统计了不同 GPU 架构在各年度文献中被提及的频率。从图中可以看出，NVIDIA 是最常被引用的 GPU 厂商，其在文献中的出现频率远高于其他厂商；而 AMD 与 Intel 被归类为“其他”类别，在全部文献中出现频率略高于10%。此外，不同架构在各年度的热度呈现明显的兴衰变化，尽管 GPU 架构通常具有较长的生命周期。例如，即使到了2019年，Kepler 架构仍然是文献中最常被提及的 GPU 架构，尽管该架构发布距今已有七年。
第6节将详细讨论我们从文献中归纳出的28类优化技术。图3则展示了各类优化在文献中被提及的比例。从中可以看出，最常见的优化技术包括：访问合并（coalesced access）、使用专用存储器、减少分支发散以及自动调优（autotuning），这些策略在多个研究中被广泛采用。
GPU 编程的介绍
5.1 GPU 架构
GPU 架构发展迅速，为避免过度聚焦于某一具体架构，本文采用一种“代表性”GPU 架构进行讨论，该架构虽在现实中并不存在，但足以揭示优化过程中所需关注的核心结构与问题。如图5所示，该代表性架构为一高层次的结构示意图。一般而言，GPU 作为 PCIe 扩展卡集成于主机系统中，与主机端的 CPU 和内存协同工作。GPU 本身包含片上处理器与设备内存，并通过 PCIe 总线与主机通信。
芯片由较大的二级缓存（L2 Cache）与多个流处理多处理器（Streaming Multiprocessors, SMs）组成，在本模型中设有 16 个 SM。每个 SM 包含 64 个用于算术运算（如单精度浮点运算）的核心，32 个用于数据加载/存储的单元（Load/Store Units, LS），16 个支持双精度计算的运算单元（Dual Precision Units, DP），以及 8 个用于计算超越函数的特殊功能单元（Special Function Units, SFUs）。此外，SM 还具备片上存储器资源，该资源作为共享内存使用，与一级缓存（L1）共享物理空间。
5.2 编程抽象
在 CUDA 或 OpenCL 编程模型中，核函数（kernel）是从主机端发起、在 GPU 上并行执行的函数。核函数通常针对单个线程编写，在执行时会以一个或多个线程并行启动。GPU 中的线程组织呈层次结构：线程首先被组织成线程块（thread block），多个线程块再组成网格（grid），如图6所示。
以示例配置为例，一个二维线程块包含 个线程，而整个网格由 个线程块构成。每个线程依据其所在线程块编号、线程块维度以及线程在块内的编号获取唯一标识符，从而在程序中定位对应的数据或任务。
同一线程块内的线程可通过共享内存进行通信：一个线程写入的值可被其他线程读取。然而，由于线程无法主动获知其他线程何时完成写操作，因此需要通过同步屏障（barrier）机制来协调数据访问。在传统 GPU 架构中，不同线程块之间在单次核函数执行过程中无法直接通信（尽管现代架构对此限制已有一定程度的放宽，详见第6.3.10节）。因此，实现跨线程块的同步通常需要通过多次核函数调用实现。
图7(a) 展示了一个简单的 CUDA 核函数示例，实现数组 aa 与 bb 的按元素加法并将结果存入数组 cc。每个线程基于其全局线程编号（由线程块编号、块内线程编号及线程块维度计算）处理一个数组元素，实现并行加法操作。图7(b) 展示了主机端代码，用于设定线程块和网格规模并启动 vecadd 核函数。此例中每个线程块包含 1024 个线程，核函数以约 1000 个线程块的规模并行执行。这种并行度在实际 GPU 应用中较为常见。
尽管编程模型中未显式体现，但了解线程的实际调度单位对性能优化有重要意义。在 NVIDIA 架构中，线程块内的线程被划分为 32 个线程一组的 warp，AMD 架构中通常为 64 个线程一组。指令以 warp 为调度单位执行，因此同一 warp 内的所有线程将执行相同的指令流。
5.3 编程抽象与 GPU 架构的映射关系
在 GPU 编程模型中，线程块（thread block）这一编程抽象映射至架构层面的流处理多处理器（Streaming Multiprocessor, SM）。SM 中的各类功能单元（如算术核心）负责执行 warp 级别的指令，而共享内存则位于片上存储器中，并按线程块粒度进行分配。编译器负责确定每个线程所需的私有寄存器数量。一般而言，线程间无法通过寄存器直接通信。
在 NVIDIA GPU 架构中，提供了 warp-shuffle 函数，使得同一 warp 内的线程可在不依赖共享内存的情况下进行数据交换（详见第6.1.2节）。若线程所需寄存器数量超出寄存器文件的容量，则部分寄存器值将被“溢出”存储至设备内存中，从而导致性能开销增加，尽管这些值通常会被缓存以减轻影响。
GPU 属于面向吞吐量的处理器架构，其调度机制以 warp 为单位进行。每当某一 warp 执行高延迟操作（如访问设备内存）时，调度器可采取以下两种方式继续执行：（1）在该 warp 的指令流中调度下一条独立指令；或（2）切换至其他可执行的 warp。由此，GPU 通过调度其他 warp 来隐藏高延迟操作，这种机制被称为线程级并行性（Thread-Level Parallelism, TLP）；而在单个线程指令流中调度独立指令的机制则被称为指令级并行性（Instruction-Level Parallelism, ILP）。需要指出的是，后者常常在厂商提供的编程文档中被忽视。
每个 SM 可同时执行多个线程块，通常为 8 或 16 个。具体可并发线程块数量受以下三个因素限制：（1）每个线程块中的线程数；（2）每个线程所需寄存器数量；（3）每个线程块所分配的共享内存大小。线程块大小的上限通常为 1,024 个线程；当线程块达到此上限时，SM 往往只能并发执行 1 或 2 个线程块。适当减小线程块规模有助于提升 SM 的并发度。线程块的寄存器需求由单个线程的寄存器数量与线程数共同决定。最后，SM 上的共享内存也需在线程块之间划分；若某一线程块独占全部共享内存资源，则该 SM 在该时刻只能承载一个线程块。
5.4 性能参数的平衡
从上述讨论可以明显看出，许多参数之间存在相互作用，而在各种参数之间实现适当的平衡对于性能而言至关重要。由于我们所讨论的典型GPU拥有16个SM（Streaming Multiprocessor），每个SM都能够处理多个线程块，因此通常需要网格中包含大量线程块。这也表明，从负载均衡的角度出发，SM的配置通常是过度的。
通常认为，如果所选择的寄存器数量、共享内存大小和/或线程块大小导致低占用率（occupancy），那么就无法实现高性能。然而，Volkov指出，占用率作为利用率的衡量标准仅反映了线程级并行性（TLP），而指令级并行性（ILP）同样重要。更进一步，Volkov还指出，在某些核函数中，为了实现高性能，反而需要较低的占用率。
实现高性能往往是一种平衡的艺术，其中TLP与ILP在一定程度上构成“连通器”，但其间存在“水桶”结构，使得最终的结果并不总是立竿见影，除非某一水桶溢出。例如，提高ILP通常是有益的，直到达到SM的某个资源限制，如寄存器数量限制，从而减少了可同时激活的线程块数量，进而降低了TLP。
在附录D中，我们进一步介绍了Volkov的性能模型，该模型从TLP和ILP两个方面对利用率进行了定义。
六、优化技术
本节概述了从现有文献中提取的优化技术，并根据四个主题对这些技术进行了组织，分别为：内存访问（第6.1节）、不规则性（第6.2节）、平衡性（第6.3节）以及主机交互（第6.4节）。由于内存访问通常远慢于计算操作，因此“内存访问”是最为关键的优化主题之一。我们将该主题进一步细分为片上（On-Chip）和片外（Off-Chip）两个子主题，两者各自面临不同的挑战与应对策略。
考虑到GPU是一种高度规则的体系结构，另一个重要主题是“不规则性”，该部分讨论了如何高效地将不规则算法映射至GPU架构上。在“平衡性”主题中，我们探讨了若干优化技术，并进一步划分为三个子主题：指令流的平衡——这是影响性能的关键因素，详见第5.4节；与并行性相关的平衡——在粒度控制与负载均衡中尤为重要；以及与同步相关的平衡——这一方面对提升性能具有重要意义。
最后，在“主机交互”主题中，我们讨论了GPU作为加速器与主机之间的协同机制。
需要指出的是，我们并不将这些主题视为一种严格的分类体系，而更倾向于将其作为组织优化技术的方式。某些技术的归属并非绝对明确。例如，负载均衡被归入“平衡性”主题，但在不规则应用中也常常不可或缺，因此也可将其视为“不规则性”的一部分。我们在此选择将其归入“平衡性”。
希望深入了解各项优化技术的读者可参考附录A，该附录按照相同的主题结构编排，并附有所述技术的目录索引。