Retargeting and Respecializing GPU Workloads for Performance Portability

作者/机构: Ivan R. Ivanov (Tokyo Institute of Technology, RIKEN R-CCS), Oleksandr Zinenko (Google DeepMind), Jens Domke (RIKEN R-CCS), Toshio Endo (Tokyo Institute of Technology), William S. Moses (University of Illinois Urbana-Champaign, Google DeepMind)

A1 主要贡献

为了在GPU等加速器上达到接近峰值的性能，需要进行大量的架构特定调优，这要求对共享内存、并行性、张量核心等有深入的理解。然而，硬件架构的多样化（即使是同一供应商）给性能可移植性带来了挑战，特别是对于那些为特定架构设计的程序。即使程序可以在不同架构上无缝执行，也可能因为未能适当适应硬件资源（如快速内存和寄存器）的大小而遭受性能损失。

核心问题: 现有的（尤其是旧的）CUDA程序在现代或不同供应商的GPU上执行时，由于其并行粒度（如每线程工作量、共享内存和寄存器使用量）未针对新硬件进行优化，导致性能不佳，存在性能可移植性问题。

研究目标: 提出一种基于编译器的方法，自动调整GPU程序的并行粒度，以适应目标硬件架构，从而提高（遗留）CUDA程序在现代机器上的性能，并实现跨不同供应商GPU（特别是NVIDIA和AMD）的性能可移植性。

创新点/主要贡献:
1. 提出一种新的编译器机制来“重塑”GPU程序：该机制能够自动调整每个并行线程所做的工作量，以及它所需的内存和寄存器资源，而无需更改编程模型。
2. 基于MLIR的统一表示和转换：工作建立在Polygeist编译器【【索引7，Polygeist: Raising C to Polyhedral MLIR，2021，PACT】；【索引8，High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel Constructs，2023，PPoPP】】之上，将CUDA代码转换为基于MLIR【【索引9，MLIR: Scaling Compiler Infrastructure for Domain Specific Computation，2021，CGO】】的与目标无关的表示。这种表示显式地表达了GPU的多级并行性和共享内存，允许通过一个通用的“粗化”（coarsening）变换来改变每线程的工作量和内存资源使用。
3. 自动跨厂商重定向：利用MLIR表示，该方法能够将在CUDA中编写的程序自动重定向到AMD GPU上运行，并同时调整程序粒度以适应目标GPU的规模。
4. 结合后端信息进行自动调优：该方法与后端GPU编译器连接，提取寄存器使用量和溢出等底层信息，进行编译时自动调优，以过滤掉因资源利用不当而导致性能灾难的程序版本。同时支持基于实际运行时间的传统自动调优，以选择在给定硬件上的最佳粒度。

A3 背景知识

A. GPU编程模型和架构

本文的输入是使用CUDA编程模型编写的程序，输出是CUDA和ROCm可执行文件。尽管本文不研究其他模型，但该系统可以适应其他输入编程模型，如SYCL【【索引6，SYCL: Single-source C++¨ accelerator programming，2016，Parallel Computing: On the Road to Exascale】】或OpenCL【【索引10，From CUDA to OpenCL: Towards a performance-portable solution for multi-platform GPU programming，2012，Parallel Computing】】。

1. GPU执行结构：传统的CUDA编程模型要求程序员以层次化结构表示计算。每个内核执行固定数量的线程，这些线程被组织成块（block），块又构成网格（grid），网格中的块数可以是可变的（如图1所示）。每个块的线程数和每个网格的块数都必须在内核启动时指定。线程以称为warp的组并行执行，块本身的执行也可能重叠。由于块的大小（即线程数）是有限且固定的，因此在为GPU编程时，扩展问题规模最常用的方法是改变块的数量。GPU包含多个流式多处理器（SM），SM被分配执行块。每个SM可以被分配多个块，并在块终止时分配新的块。SM以锁步方式执行warp中的所有线程，每个线程执行相同的指令。当一个warp执行高延迟指令（如内存加载）时，SM可以切换到执行另一个warp，从而隐藏指令级延迟。
2. 合并内存访问（Coalesced Memory Access）：当warp中的线程执行加载操作时，如果满足特定要求（加载大小、步幅、全局偏移量），加载可以被合并，以更少的内存事务执行，从而减少带宽消耗【【索引13，How to Access Global Memory Efficiently in CUDA C/C++ Kernels，NVIDIA Blog】】。尽管较新的架构对实现良好性能的要求更为宽松，但内存局部性对于最佳利用内存带宽仍然至关重要【【索引14，CUDA-MicroBench: Microbenchmarks to Assist CUDA Performance Programming，2021，IPDPSW】】。
3. 占用率（Occupancy）：当块被分配到SM时，它们必须遵守某些约束以避免耗尽SM的资源。这些约束包括：每个SM的寄存器数、每个SM的最大驻留线程数、每个块的最大线程数、每个SM的最大共享内存量以及每个块的最大共享内存量。另一方面，每个块执行需要一定量的共享内存、寄存器和线程。因此，一个给定的内核在单个SM上可以驻留的最大块数是有限的。占据一个SM的块的线程被称为活动线程，活动线程数与每个SM最大线程数的比率即为内核的占用率。虽然SM有资源限制占用率，但它也有一组独立的资源（称为执行资源），这些资源不限制占用率，而是由SM上的块共享，包括：内存带宽、算术逻辑单元（ALU）和浮点单元（FPU）。为了从GPU中获得最高性能，活动线程必须产生足够的工作来饱和SM的执行资源并隐藏延迟。这需要在每线程工作负载和占用率之间取得平衡。
4. 性能可移植性：内核在不同于程序员预期目标硬件上的性能受到限制，因为不同占用率限制资源和执行资源的容量在不同GPU供应商之间，甚至在同一供应商内部都存在差异（例如，Fermi之前的CUDA硬件每个warp有16个线程，当前有32个，而AMD GPU有64个）。这种可变性使得编写在各种目标硬件上都表现良好的内核变得困难。在C/C++ CUDA编程中，动态共享内存比静态大小的共享内存更难实现，这一事实加剧了问题，导致内核倾向于采用固定的粒度。我们提出的变换在块和线程级别上自动改变计算的粒度，以充分利用给定目标的可用资源。

B. Polygeist/MLIR中的GPU编译

1. MLIR：MLIR是一个用于定义和混合编译器内部使用的抽象的框架【【索引9，MLIR: Scaling Compiler Infrastructure for Domain Specific Computation，2021，CGO】】。与其他IR不同，它拥有一套开放的计算原语（称为操作）和类型。MLIR提供了许多可重用的抽象，这些抽象组织在方言（dialects）中，并期望在程序中并存，以模拟其不同方面。例如，一个简单的GPU内核可以使用以下方言表示：
   • arith：用于整数和浮点算术。
   • memref：用于内存访问的操作和类型。
   • scf：用于结构化控制流。
   • gpu：用于通用的GPU编程模型（SIMT）。
     用MLIR构建的编译器通常会定义额外的方言。这种混合抽象模型对于在编译器中针对GPU等加速器特别有用，因为它允许编译器同时对可在同一翻译单元中表示的主机和设备代码进行推理【【索引15，Domain-Specific Multi-Level IR Rewriting for GPU: The Open Earth Compiler for GPU-Accelerated Climate Simulation，2021，ACM Trans. Archit. Code Optim.】】。它支持一系列基于静态单赋值（SSA）形式的经典优化，如公共子表达式消除和循环不变量代码移动，这些优化可以跨越主机/设备边界应用，并支持新的加速器感知变换【【索引8，High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel Constructs，2023，PPoPP】；【索引16，Structured Operations: Modular Design of Code Generators for Tensor Compilers，2023，Languages and Compilers for Parallel Computing】】。
2. Polygeist：Polygeist是一个使用MLIR构建的C++及其扩展的编译器【【索引7，Polygeist: Raising C to Polyhedral MLIR，2021，PACT】】。它为GPU屏障同步原语引入了一种基于MLIR的编译器抽象，从而实现了GPU到CPU的转译和屏障优化【【索引8，High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel Constructs，2023，PPoPP】】。具体来说，它使用scf.parallel循环操作来表示GPU的块和线程，并使用其自定义的polygeist.barrier操作来进行线程同步（等同于CUDA的__syncthreads）。并行循环的一次迭代对应于内核配置中的一个GPU块或线程。这并不意味着所有迭代都并发执行，而是它们受制于跨SM的块和warp调度。parallel操作本身并未规定这一点，仅表示各个操作之间的相互独立性。因此，我们将区分并行循环的迭代和线程。根据GPU编程模型，屏障操作必须由同步范围内的所有线程执行，通常是块或warp。这通常被称为控制流收敛，因为它有效地排除了线程之间围绕屏障的控制流变化。换句话说，影响屏障的控制流不应依赖于线程ID。由于Polygeist对多级并行建模，其屏障还额外引用了需要同步的并行循环迭代器（解释为线程标识符），如图2所示。尽管能够表示GPU编程模型，但由于缺少优化和目标信息，Polygeist一直无法从CUDA输入生成高效的GPU代码，并且只专注于向CPU的翻译。
   

C. 线程粗化（Thread Coarsening）

GPU程序可以看作是使用大量线程在更多的工作单元上执行相似的计算，以便每个线程处理多个单元。线程粗化，即增加一个线程处理的单元项目数量，已被用于通过隐藏昂贵的内存访问操作的延迟来提高GPU内核的性能，最初是手动进行的【【索引17，Understanding Latency Hiding on GPUs，2016，PhD thesis】】，后来在编译器中自动实现【【索引18，Cost-Driven Thread Coarsening for GPU Kernels，2018，PACT】；【索引19，A Large-Scale Cross-Architecture Evaluation of Thread-Coarsening，2013，SC ’13】；【索引20，Automatic Optimization of Thread-Coarsening for Graphics Processors，2014，PACT ’14】】。然而，线程粗化可能对性能产生不利影响，例如，通过引入跨步内存加载，妨碍合并访问，或通过增加寄存器压力从而降低GPU占用率。

A2 方法细节

III. POLYGEIST-GPU流水线概览

端到端GPU编译器扩展。我们扩展了Polygeist，提供了一个端到端的GPU编译器，该编译器接受CUDA代码，执行优化和内核粒度选择，并同时针对NVIDIA和AMD GPU。与将主机（CPU）和设备（GPU）代码视为独立翻译单元的传统编译器（图3）相反，我们的方法将两部分代码保持在一起，从而允许同时更新内核配置、启动以及内核代码本身（图4）。

内联的MLIR表示。具体来说，我们将GPU代码的MLIR表示内联到CPU代码的表示中，同时将其封装在一个携带区域（region-carrying）的操作中，如图5所示。此操作允许跨区域边界进行代码移动，但与并行和屏障相关的构造除外。与之前通过gpu.launch【【索引15，Domain-Specific Multi-Level IR Rewriting for GPU: The Open Earth Compiler for GPU-Accelerated Climate Simulation，2021，ACM Trans. Archit. Code Optim.】】在MLIR中内联表示GPU内核的方式不同，我们的方法使用显式的并行循环，这些循环直接适用于循环分析和优化。

编译流程。在这种表示上进行优化后，内核被外提（outline）并由MLIR中可用的目标特定遍（pass）流水线处理，以生成嵌入在IR中作为全局数据的目标特定二进制文件。剩余的主机代码随后由目标特定的流水线处理，以将外提的gpu_wrapper替换为相应的GPU运行时调用，并使用LLVM进一步降低为自包含的优化二进制文件。除了本文贡献的优化之外，并行的GPU表示还启用了Polygeist和MLIR中许多其他已有的优化，例如消除屏障、围绕屏障的代码移动、跨屏障的内存到寄存器提升，以及并行循环不变量代码移动【【索引8，High-Performance GPU-to-CPU Transpilation and Optimization via High-Level Parallel Constructs，2023，PPoPP】】。

IV. 嵌套并行循环的展开与交错（UNROLL-AND-INTERLEAVE）

并行循环的展开与交错。我们为嵌套的并行循环专门化了经典的循环展开变换，同时处理了GPU风格的屏障同步。首先考虑图6中展开因子为2的简单顺序循环。为了保留副作用的顺序并保证变换的有效性，来自第一次展开迭代的所有带副作用的语句都先于它们在第二次展开迭代中的对应语句。而并行循环不意味着并行迭代之间有任何副作用顺序，只要求在一次迭代内部有序，这允许我们任意交错来自不同操作的语句，只要它们的相对顺序得以保留，如图7所示。特别是，我们可以将它们分组，以产生独立展开每个语句的效果，这在概念上类似于循环向量化。

A. 嵌套控制流：展开、合并与交错

处理嵌套控制流。现在考虑一个具有恒定循环次数的嵌套for循环（图8）。直接展开外层循环（如图9）会复制嵌套循环，这因代码尺寸增加和额外的控制流而不总是可取的。另一种经典的循环变换，展开与合并（unroll-and-jam），将嵌套的循环重新融合成一个。我们可以进一步将循环展开与合并与语句交错结合起来，像之前一样将语句分组。这个过程可以递归地应用于嵌套的for循环、具有更少副作用排序约束的并行循环以及可以根据条件被视为零次或一次迭代的if/else条件。当循环次数不能静态确定时（除了if/else特殊情况），我们将嵌套循环视为单个语句并进行复制。值得注意的是，展开-合并-交错也可以通过剥离序言（prologue）和尾声（epilogue）来处理具有可变循环次数的循环，但我们在面向GPU的基准测试中没有观察到这种需求。

B. 同步

处理屏障同步。到目前为止，我们假设并行循环中不存在同步原语。GPU编程模型允许跨线程（但非块）进行屏障同步。然而，编程模型要求屏障必须由所有线程执行。也就是说，屏障不能嵌套在依赖于块内不同线程变化的值（如线程索引或在线程索引相关地址加载的值）的控制流中。因此，屏障只能嵌套在线程间条件相同的控制流中，即使该条件在编译时无法确定。我们利用这一信息来对包含嵌套在对应于GPU线程的并行循环中的屏障的循环执行展开-合并-交错。由于polygeist.barrier明确指定了同步范围的循环归纳变量，我们可以将其推广到处理围绕屏障的控制流，当展开任何由这些屏障同步的外部并行循环时。这使得当不同的线程维度（x,y,z）被映射到嵌套的并行for循环而不是单个多维并行循环时，交错能够无缝工作。现在考虑交错情况下的嵌套循环体，如图10所示。屏障的存在要求变换保留受屏障保护的语句的相对顺序。这个条件可以通过将来自不同迭代的语句副本分组在一起来满足，如图10左侧所示。此外，多个最终连续的屏障可以被简单地替换为单个屏障。相反，如果一个屏障被复制，例如当不同的块运行不同次数的内层循环迭代时，外层循环的展开与交错可能变得非法，如图10右侧所示。因此，如果并行循环（对应于GPU块）嵌套了条件在编译时未知的控制流，我们不应用该变换。

C. 多维循环

处理多维循环。CUDA编程模型允许程序员指定块和网格可以划分的三个维度：x、y和z。因此，我们在并行内核表示中遇到的并行循环是具有3个（或更少）维度的多维并行循环。这就引出了我们应该在哪些维度上执行线程和块粗化的问题。在我们的实现中，我们提供了两种指定方式。可以指定多维并行的总粗化因子，Polygeist-GPU将尝试在非恒定大小1的维度间平衡这些因子。另一个选项是明确指定x、y和z的因子。

V. 作为粒度变化的粗化

嵌套并行展开与交错变换让我们实现了两种专门的粗化变换，它们增加了每个GPU线程或块执行的工作量。也就是说，这些变换影响了内核相对于工作单元的粒度。

A. 线程粗化（Thread Coarsening）

线程粗化的实现。对代表GPU线程的并行循环（图2中的第4-5行）执行展开与交错，可以实现与先前工作（II-C节）类似的线程粗化。由于该变换展开了与屏障关联的循环，并且考虑到GPU上的控制流收敛标准，该变换总是合法的。线程粗化增加了单个线程处理的工作单元数量，减小了块的大小，并保持了块的数量不变。换句话说，一个线程处理了同一块中多个线程的工作负载。

B. 块粗化（Block Coarsening）

块粗化的实现与合法性。对代表GPU块的并行循环（图2中的第1-2行）执行展开与交错，产生了一种新颖的变换——块粗化。当该变换无法交错与线程相关的屏障而需要复制它时，可能变得非法。也就是说，如果（线程）屏障被（可传递地）依赖于块标识符的控制流所包围。在多个嵌套并行循环的一般情况下，如果变换会复制一个同步了除正在展开的循环之外的其他循环的屏障，那么该变换是非法的。块粗化增加了单个块处理的工作单元数量，保持了每块的线程数，并减少了块的数量。换个角度看，每个线程现在处理来自不同块的多个线程的工作负载，因此合法性要求块之间的控制流是非发散的。

C. 块粗化与线程粗化的权衡

权衡分析。与线程粗化不同，块粗化会合并来自不同块的共享内存分配，从而增加共享内存的使用量。这可能会在共享内存容量或带宽未被充分利用的内核中提高性能，但在已使用大量共享内存的内核中可能会降低性能，因为共享内存成为主要的占用率限制因素。需要注意的是，两种粗化都会增加每个线程的寄存器使用量，这是另一个占用率限制因素，但不能在平台特定编译器之外直接控制。根据实现方式，线程粗化可能会通过引入跨步访问模式来干扰内核中原有的合并友好访问模式。而块粗化保留了独立块中存在的内存访问模式。

剩余迭代的处理。当粗化因子不是并行循环上界的约数时，如何执行剩余迭代会产生一个额外问题。在执行线程粗化时，剩余的迭代必须在同一个块内执行，以保留块内同步。然而，让额外的线程执行剩余工作会干扰线程间工作负载的平衡，影响满warp的形成，并引入由收敛分支执行带来的复杂性。因此，我们将线程粗化因子限制为上界的约数。相反，在进行块粗化时，我们会生成一个尾声（epilogue）内核来完成剩余块的工作。因此，我们将块粗化扩展到任何粗化因子，而不仅仅是上界的约数。在第七节中，我们将看到这种选择因子的灵活性如何让我们进一步提高性能。
并行度利用率。由于线程粗化减少了每块的线程数，大的粗化因子或原本线程数较少的块最终可能运行少于一个warp的线程。这将导致并行线程利用不足和性能下降。类似地，块粗化减少了网格中的块数，可能导致内核的块数少于SM数，从而导致性能下降。我们的初步观察表明，内核通常被设计为尽可能利用块级并行性，因此更多的并行性和粗化机会可以在该级别找到。最后，块和线程粗化可以结合使用，以兼顾两者的优点或减轻其缺点。

VI. 备选代码路径（ALTERNATIVE CODE PATHS）

备选区域的概念。由于展开与交错变换是在一个相对较高的抽象层次上执行的，我们在中间表示中引入了备选区域（alternative regions）的概念，以支持编译时的多版本化。然后，我们可以对不同的区域应用具有不同因子的块和线程粗化，使得每个区域都以不同的粒度捕获相同的计算。这使我们能够将选择最佳备选方案推迟到编译流水线中某个点，在该点，较低级的抽象提供了足够详细的信息，例如关于寄存器使用情况。否则，我们将不得不在高抽象层次上开发一个性能模型，并依赖一个很大程度上不精确的启发式方法来选择最佳的粗化因子。
实现与决策点。实际上，备选方案在一个新的多区域MLIR操作中表示（图12）。在我们的流程中，它们通过简单地多次复制内核主体区域并对不同区域应用不同因子的粗化来产生。编译流水线可以正常进行，每个区域都与其他区域分开进行优化和降低，直到达到以下决策点之一。
* 基于共享内存使用的早期剪枝：鉴于静态共享内存必须在编译时以已知大小预先分配，我们能够在生成备选方案后立即对其进行分析，以计算所使用的共享内存总量。此时可以丢弃那些需要超过目标硬件可用共享内存的备选方案。
* 内核统计信息：在并行循环表示中，我们可以使用循环的封闭形式表达式来收集关于算术和内存操作数量的信息，如果循环边界在编译时未知，则为符号表达式。在LLVM表示中，我们还可以收集有关GPU控制流中分支操作数量的信息，已知这些操作会对性能产生负面影响，因为控制流发散可能实现为依次执行分支，而无关线程被屏蔽。最后，使用特定于平台的后端（如ptxas）将表示编译为二进制文件，可以为我们提供有关寄存器使用和溢出、估计占用率等信息。在此阶段，我们会丢弃那些导致新溢出的备选方案，因为GPU上的溢出会将数据放入比寄存器慢几个数量级的局部内存中。
* 时序驱动优化（TDO）或自动调优：最后，通过初步过滤的备选方案将作为独立的内核包含在最终的二进制文件中。我们的编译器提供一个“分析”模式，在该模式下，它会生成额外的逻辑来允许选择一个备选实现。每个备选方案可以在不同的数据上执行一次或多次以测量平均执行时间，然后选择性能最好的一个。之后可以再次调用编译器，以移除所有其他备选方案，并提供一个没有额外分派的单一版本。

A4 实验环境

实验设置

我们在两个供应商的四种不同GPU上进行了评估，具体规格如表I所示。Polygeist-GPU是基于LLVM 15版本（git commit 00a1258）编译的。

硬件配置:
* GPU: NVIDIA A4000, AMD RX6800 (消费级), NVIDIA A100, AMD MI210 (HPC级)。详细参数见下表。
* 平台1: 2x Intel Xeon Gold 6252 CPU, 192 GB RAM, NVIDIA A100 40GB。
* 平台2: 2x Intel Xeon Silver 4215 CPU, 384 GB RAM, AMD MI250。
* 平台3: AMD EPYC 7302 16-Core CPU, 256 GB RAM, AMD RX6800, NVIDIA RTX A4000。

软件配置:
* 代码实现: Polygeist-GPU（已合并至Polygeist），基于LLVM 15。
* 对比基线: clang（用于NVIDIA），hipify+clang（用于AMD）。
* 操作系统: AlmaLinux 8.4, Fedora 37。
* 依赖库: CUDA 11.4, CUDA 12.1, ROCm 5.3.4。

数据集与基准测试:
* Rodinia v3 【【索引21，Rodinia: A benchmark suite for heterogeneous computing，2009，IISWC】】: 包含24个CUDA基准测试，其中9个被排除。这些基准测试针对旧的CUDA架构优化，我们的目标是调整它们以在现代GPU上高效运行。
* HeCBench 【【索引22，A Benchmark Suite for Improving Performance Portability of the SYCL Programming Model，2023，ISPASS】】: 包含400个基准测试。我们成功用clang编译了303个，其中112个可以通过Polygeist-GPU编译和运行。

测量方法:
* 内核测量: 单个内核运行的时间。
* 复合测量: 应用程序整个计算部分的时间，包括多次内核启动、之间的逻辑以及主设备通信。
* 报告复合测量的5次运行中位数，内核测量的3次运行中位数。运行时间小于0.0001秒的测量被丢弃。
* 除非另有说明，否则应用时序驱动优化（自动调优）。
* 通过比较不同配置下Polygeist-GPU和clang编译的Rodinia基准测试的输出来验证变换的正确性。

表 I 用于评估的GPU及其规格。

A4 实验结果

B. 结合块粗化和线程粗化

• 实验内容: 评估块粗化和线程粗化组合变换的效果，并与单独应用线程粗化或块粗化进行对比。我们独立为线程和块粗化设置了1, 2, 4, 8, 16, 32的总因子。
• 实验结果: 在181个内核变体中，组合粗化实现了11.3%的几何平均加速，单独线程粗化为4.4%，单独块粗化为8.9%。在75个有显著加速（>1%）的内核中，组合策略系统性地优于单独的线程粗化（见图13）。
• 分析与结论:
  • 以Rodinia的lud基准测试为例，在A100 GPU上，组合粗化（块因子7，线程因子2）达到了峰值性能，而单独的线程或块粗化无法达到。最佳块因子7是一个素数，这显示了块粗化在因子选择上的灵活性。
• 当线程粗化因子过大（≥16）时，会导致产生的线程数少于一个warp（32个线程），从而性能下降（见图14）。
• 根据NVIDIA Nsight Compute的分析数据（表II），块粗化能更好地利用共享内存，减少了L2到L1缓存的数据传输，从而提升了性能。
  • 通过对lud内核的块维度进行更精细的控制（x和y维度），发现在x维度上进行块粗化能更好地保持内存局部性，峰值性能在块因子为9时达到1.64倍加速。进一步结合线程粗化，在（块x=2，线程=8）的配置下，峰值加速达到了1.94倍（见图15）。这表明需要自动调优来找到最佳配置，避免因缓存利用不佳导致的性能骤降。
    
    
    
    

C. 与主流CUDA编译器的比较

• 实验内容: 比较Polygeist-GPU（P-G）和clang在NVIDIA GPU（A4000和A100）上编译的复合运行时性能，以评估我们优化的影响。
• 实验结果:
• 在没有优化的情况下，由于共享相同的前后端，P-G生成的代码性能与clang相似。
• 启用并行优化后，P-G在NVIDIA A4000上实现了17%的几何平均加速，在A100上实现了27%的几何平均加速（见图16）。
• 分析与结论:
  • lavaMD的加速是由于Polygeist更好的循环不变量代码移动，将多个共享内存加载操作提升出内层循环，显著改善了内存特性。
  • srad_v1 reduce的性能差异源于地址计算顺序的不同，影响了寄存器分配和使用。
  • gaussian内核算术强度低，发散严重，且块大小仅为16。块粗化通过让单个线程执行更多工作，显著提高了资源利用率和性能。
    

D. 翻译到AMD：hipify+clang vs. Polygeist-GPU

• 实验内容: 比较我们的IR级翻译方法（Polygeist-GPU）与AMD提供的源码到源码翻译工具hipify【【索引23，HIPify，AMD】】后用clang编译的性能，目标平台是AMD RX6800和MI210 GPU。
• 易用性比较: Polygeist-GPU的使用更便捷。它在IR层面进行翻译，避免了hipify在处理复杂宏、模板和预处理器指令时需要手动修复源文件和头文件依赖的问题。
• 性能结果:
  • 与hipify+clang基线相比，启用优化的Polygeist-GPU在AMD RX6800上实现了16%的几何平均加速，在MI210上实现了17%的几何平均加速（见图16）。
• 跨厂商性能对比:
• 在规格相当的NVIDIA A4000和AMD RX6800上进行比较，以clang在A4000上的性能为基线（见图17）。
• 使用Polygeist-GPU编译的RX6800比使用clang编译的A4000性能高出25%（几何平均），比使用Polygeist-GPU编译的A4000快9%。
• 分析与结论:
  • nw_*内核在AMD上性能差异巨大，是因为其每个线程的共享内存使用量极高（136字节/线程）。AMD后端优化器将此共享内存卸载到全局内存，避免了因L1缓存（16KB）过小而导致的占用率严重受限问题。
  • particlefilter*、lavaMD、hotspot3D在AMD上性能更好，是因为这些基准测试使用了双精度浮点运算，而RX6800的双精度计算能力远高于A4000。
    

A7 补充细节

VIII. 相关工作

A. 线程和块粗化

线程粗化作为一种GPU优化技术，最早由Volkov【【索引17，Understanding Latency Hiding on GPUs，2016，PhD thesis】】作为手动优化提出，用于隐藏延迟。随后，Barua, Shirako, 和 Sarkar【【索引18，Cost-Driven Thread Coarsening for GPU Kernels，2018，PACT】】以及Magni, Dubach, 和 O’Boyle【【索引19，A Large-Scale Cross-Architecture Evaluation of Thread-Coarsening，2013，SC ’13】；【索引20，Automatic Optimization of Thread-Coarsening for Graphics Processors，2014，PACT ’14】】将其实现为针对OpenCL和OpenACC的自动变换。块粗化变换最早由Unkule, Shaltz, 和 Qasem【【索引24，Automatic Restructuring of GPU Kernels for Exploiting Inter-thread Data Locality，2012】】提出，并由Stawinoga和Field【【索引25，Predictable Thread Coarsening，2018，ACM Trans. Archit. Code Optim.】】首次实现。然而，先前的工作没有讨论在存在块级同步时块粗化的合法性。此外，我们的工作是第一个将线程和块粗化结合起来的，展示了复合效益，并且在我们的并行表示中得到了简化。此外，已有文献描述了选择最优因子的各种启发式方法【【索引18，Cost-Driven Thread Coarsening for GPU Kernels，2018，PACT】；【索引20，Automatic Optimization of Thread-Coarsening for Graphics Processors，2014，PACT ’14】；【索引25，Predictable Thread Coarsening，2018，ACM Trans. Archit. Code Optim.】】，但我们未能直接将其应用于我们的组合粗化变换方法，这部分留作未来工作。

B. 粒度控制

领域特定语言（DSLs）和编程框架提供了计算粒度的控制。Triton【【索引1，Triton: an intermediate language and compiler for tiled neural network computations，2019，Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages】】提供了一个tile的抽象，并能无缝扩展其粒度以调整计算以适应目标硬件。Kokkos【【索引26，Kokkos: Enabling manycore performance portability through polymorphic memory access patterns，2014，Journal of Parallel and Distributed Computing】】和RAJA【【索引27，RAJA: Portable Performance for Large-Scale Scientific Applications，2019，2019 IEEE/ACM International Workshop on Performance, Portability and Productivity in HPC (P3HPC)】】是提供多种并行抽象（如多级并行原语）的编程模型，能够为GPU生成高性能代码。Halide【【索引28，Halide: A Language and Compiler for Optimizing Parallelism, Locality, and Recomputation in Image Processing Pipelines，2013，Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation】】提供了一种将计算和调度分开指定的方式，这在某种程度上允许控制计算的粒度，以最好地适应目标硬件。然而，这些都需要程序员用他们的新编程模型重写软件，这通常很费力，并且可能无法表示任意程序。相比之下，我们的解决方案适用于现有的CUDA代码。

C. 翻译到AMD

Hipify【【索引23，HIPify，AMD】】是一个源码到源码的工具，用于在源代码或抽象语法树（AST）阶段将CUDA代码翻译为在AMD GPU上运行。这两种表示都有缺点。基于源码的翻译无法处理复杂的语言特性，如宏或模板，而基于AST的翻译在为AMD和CUDA编译时预处理器选项（例如#defines）不同时无法正确工作。相比之下，我们在IR层面工作，可以解决这两种方法的问题。OpenCL【【索引10，From CUDA to OpenCL: Towards a performance-portable solution for multi-platform GPU programming，2012，Parallel Computing】】、SYCL【【索引6，SYCL: Single-source C++¨ accelerator programming，2016，Parallel Computing: On the Road to Exascale】】和OpenACC【【索引29，Achieving Portability and Performance through OpenACC，2014，2014 First Workshop on Accelerator Programming using Directives】】都提供了一种与目标无关的方式来编写GPU代码，但如果软件已经用CUDA编写，它们仍然需要重写。Doerfert等人【【索引30，Breaking the Vendor Lock: Performance Portable Programming through OpenMP as Target Independent Runtime Layer，2023，Proceedings of the International Conference on Parallel Architectures and Compilation Techniques】】提出将CUDA代码翻译成OpenMP，然后使用LLVM【【索引31，LLVM: a compilation framework for lifelong program analysis & transformation，2004，International Symposium on Code Generation and Optimization, 2004. CGO 2004】】中现有的OpenMP卸载基础设施来针对不同硬件，如NVIDIA或AMD GPU。他们使用OpenMP作为通用并行表示，类似于我们的并行表示。然而，我们的方法更容易保留GPU特定的概念，例如设备常量内存、同步原语、共享内存，并将它们纳入优化中。

A5 结论

GPU在高性能计算（HPC）中变得越来越关键，尤其是在人工智能的最新进展下。然而，近年来供应商和相应架构的多样性不断增加，许多HPC系统现在选择使用AMD GPU。这种软硬件生态系统给程序员带来了问题，他们需要不断重写应用程序以跟上不同架构的步伐——这是一个成本高昂且耗时的过程！为了有效地使现有程序能够利用硬件特定参数，我们在编译器内部结合了细粒度的线程和块粗化。基于编译器的解决方案可以在比以往更精细的尺度上操作，并且我们已成功地将其应用于将CUDA代码重新调整到不同的CUDA架构以及AMD架构。我们在Rodinia基准测试套件上实现了高达27%的几何平均性能提升，并能够在不牺牲性能的情况下自动将其翻译到AMD GPU上运行。该解决方案有助于防止供应商锁定，并降低了将软件移植到不同硬件的相关成本。

A6 附录

A. 摘要

此附件包含我们的编译器工具（Polygeist）的源代码，我们评估变换所用的基准测试套件（Rodinia + HeCBench），以及用于自动编译、执行和评估的脚本。它还包含基准测试套件的数据集和代码依赖项。我们在Polygeist/MLIR中实现了一个组合的线程和块粗化变换以及GPU内核的时序驱动优化。我们比较了我们的组合粗化方法与传统的仅线程粗化方法以及与主流编译器（clang）在Rodinia和HeCBench上的表现。

B. 附件清单（元信息）

我们使用三个系统进行实验：
* 系统1：2颗Intel(R) Xeon(R) Gold 6252 CPU，192 GB RAM，NVIDIA A100 PCIe 40GB，运行AlmaLinux 8.4。
* 系统2：2颗Intel(R) Xeon(R) Silver 4215 CPU，384 GB RAM，AMD MI250，运行AlmaLinux 8.4。
* 系统3：AMD EPYC 7302 16核CPU，256 GB RAM，AMD RX6800，NVIDIA RTX A4000，运行Fedora 37。

其他信息：
* 程序：Rodinia 和 HeCBench。
* 编译器：Polygeist（我们的工作），clang（用于比较）。
* 变换：在MLIR中实现的粗化变换。
* 数据集：作为附件提供。
* 输出：基准测试时序信息和图表。
* 所需磁盘空间：约30GB。
* 准备工作流所需时间：1到6小时（高度依赖于编译性能）。
* 完成实验所需时间：约2到3天。
* 是否公开可用：是，如下所列。
* 是否存档（提供DOI）：10.5281/zenodo.10465934

C. 实验总结

我们在工作中进行了三个实验：
* 实验1：图13：主要实验。比较我们的组合块和线程粗化方法与仅线程粗化方法，在系统1上进行。
* 实验2：图16：比较我们的编译器编译的CUDA代码与clang编译的CUDA代码，在系统1和系统3上进行。
* 实验3：图16：比较我们的编译器翻译并编译的CUDA代码与hipify处理后由clang编译的HIP代码，在系统2和系统3上进行。

D. 依赖项

1. 硬件依赖：clang 16支持的AMD和/或NVIDIA GPU。
2. 软件依赖：能够构建clang 16的Linux系统。LLD。CUDA 11.4。CUDA 12.1。ROCm 5.3.4（仅CUDA的实验不需要ROCm）。

E. 附件

组合的附件存档可在 https://doi.org/10.5281/zenodo.10465934 获取。它包括以下组件：
1. Polygeist：我们工具的源代码。公开可用于 https://github.com/llvm/Polygeist (commit ba9953a08c9b)。
2. 评估基准：可在 https://github.com/ivanradanov/rodinia (commit a97759e7) 获取。
3. 基准数据集和依赖项：可在组合附件的以下目录中找到：data, cuda-10.2-samples, 和 cuda-10.2-hip-samples。

F. 安装

1. 获取代码：

cd $HOME && git clone https://github.com/llvm/Polygeist
cd Polygeist
git checkout ba9953a08c9b
git submodule update --init --recursive

1. 构建LLVM：首先需要构建我们工具所依赖的LLVM编译器工具链。

cd $HOME/Polygeist
mkdir mlir-build && cd mlir-build

cmake配置步骤取决于系统上的GPU。
对于CUDA：

CUDACXX=<path_to_nvcc-11.4> CUDA_PATH=<path_to_cuda-11.4> cmake ../llvm-project/llvm -GNinja -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS="mlir;clang;openmp" -DLLVM_TARGETS_TO_BUILD="host;NVPTX;AMDGPU" -DMLIR_ENABLE_CUDA_RUNNER=1 -DLLVM_USE_LINKER=lld

对于AMD：

ROCM_PATH=<path_to_rocm> cmake ../llvm-project/llvm -GNinja \
-DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS="mlir;clang;openmp" \
-DLLVM_TARGETS_TO_BUILD="host;NVPTX;AMDGPU" \
-DHIP_CLANG_INCLUDE_PATH=<hip_clang_include_dir> \
-DMLIR_ENABLE_ROCM_RUNNER=1 -DLLVM_USE_LINKER=lld

对于同时有AMD和CUDA GPU的系统，使用AMD和CUDA特定的配置参数。
最后，编译：

ninja
export MLIR_BUILD_DIR="$(pwd)"

1. 构建Polygeist：

cd $HOME/Polygeist
mkdir build && cd build

cmake配置步骤取决于系统上的GPU。
对于带有CUDA GPU的系统：

CUDACXX=<path_to_nvcc-11.4> \
CUDA_PATH=<path_to_cuda-11.4> cmake ../ -GNinja \
-DMLIR_DIR=$MLIR_BUILD_DIR/lib/cmake/mlir \
-DLLVM_EXTERNAL_LIT=$MLIR_BUILD_DIR/bin/llvm-lit \
-DClang_DIR=$MLIR_BUILD_DIR/lib/cmake/clang \
-DCMAKE_BUILD_TYPE=Release \
-DPOLYGEIST_ENABLE_CUDA=1 \
-DCMAKE_CUDA_COMPILER=<path_to_nvcc> \
-DLLVM_USE_LINKER=lld

对于带有AMD GPU的系统：

ROCM_PATH=<path_to_rocm> cmake ../ -GNinja \
-DMLIR_DIR=$MLIR_BUILD_DIR/lib/cmake/mlir \
-DLLVM_EXTERNAL_LIT=$MLIR_BUILD_DIR/bin/llvm-lit \
-DClang_DIR=$MLIR_BUILD_DIR/lib/cmake/clang \
-DCMAKE_BUILD_TYPE=Release -DPOLYGEIST_ENABLE_ROCM=1 \
-DHIP_CLANG_INCLUDE_PATH=<hip_clang_include_dir> \
-DCMAKE_CUDA_TOOLKIT_INCLUDE_DIRECTORIES=<cuda_12.1 include_dir> \
-DLLVM_USE_LINKER=lld

对于同时有AMD和CUDA GPU的系统，需要同时指定ROCm和CUDA特定的cmake配置标志和环境变量。
最后，执行构建步骤：

ninja

G. 实验工作流

1. 获取基准：

cd $HOME
git clone https://github.com/ivanradanov/rodinia
cd rodinia
git checkout a97759e7

1. 获取数据集和依赖项：这些可以从组合附件中获得。数据集目录data应放在基准根目录rodinia下。一些基准测试依赖于cuda samples及其hipified版本，它们位于组合附件的cuda-10.2-samples和cuda-10.2-hip-samples中。
2. 设置基准：我们的基准仓库使用rodinia/common/中的配置文件来指定Polygeist、Clang/LLVM的安装。我们使用的系统的配置文件分别是{memkf02,memkf01,supercomp01a}.polygeist.host.make.config，分别对应系统1、2和3。文件名中的第一个子字符串必须代表机器的主机名。
3. 运行实验：实验可以使用基准仓库中的scripts/run_all_gpu_benches.sh脚本运行。它接受以下参数：
   • Polygeist特定：--targets, --pgo-configs, --pgo-prof-nruns, --configs。
   • 其他：--cuda-benchmarks, --hip-benchmarks, --clang, --hip-clang, --nruns, --host, --dry-run。
     实验1（需要CUDA GPU，约34小时）：

cd $HOME/rodinia
./scripts/run_all_gpu_benches.sh --targets CUDA --host <host_name> \
--cuda-benchmarks ./scripts/cuda_all_apps.sh --pgo-prof-nruns 3 --pgo-configs 15

实验2（需要CUDA GPU，约3小时）：

cd $HOME/rodinia
./scripts/run_all_gpu_benches.sh --targets CUDA --host <host_name> \
-cuda-benchmarks ./scripts/rodinia_cuda_apps.sh \
-pgo-prof-nruns 3 --nruns 5 \
-pgo-configs 11 --configs 2 --clang

实验3（需要AMD GPU，约3小时）：

cd $HOME/rodinia
./scripts/run_all_gpu_benches.sh -targets AMDGPU --host <host_name> \
-cuda-benchmarks ./scripts/rodinia_cuda_apps.sh \
-hip-benchmarks ./scripts/hip_all_apps.sh \
-pgo-prof-nruns 3 --nruns 5 -pgo-configs 11 --configs 2 --hip-clang

所有这些都会将结果输出到$HOME/rodinia_results/下一个带时间戳的子目录中。

H. 评估（生成图表）

要从论文中生成图表，我们可以使用基准仓库中包含的脚本。它们会将生成的图表输出到rodinia/plots/figures/中。
对于实验1：

cd $HOME/rodinia
./scripts/plots/rodinia-kernel-alt-analysis.py ~/rodinia_results/rodinia_results_<timestamp>/

对于实验2：

cd $HOME/rodinia
./scripts/plots/rodinia.py ~/rodinia_results/rodinia_results_<timestamp>/

对于实验3：

cd $HOME/rodinia
./scripts/plots/hip-rodinia.py \
~/rodinia_results/rodinia_results_<timestamp>/