PresCount: Effective Register Allocation for Bank Conflict Reduction

文章标题：PresCount: 面向银行冲突减少的高效寄存器分配方法
作者/机构：Xiaofeng Guan†‡, Hao Zhou‡, Guoqing Bao‡, Handong Li†, Liang Zhu†, and Jianguo Yao†‡
†上海交通大学，中国上海
‡上海燧原科技有限公司，中国上海

A1 主要贡献

本文研究的核心问题是现代处理器中多银行寄存器文件（multi-banked register file）带来的银行冲突（bank conflict）问题。硬件解决方案虽然灵活，但会引入运行时开销并限制硬件设计的优化空间；而现有的基于编译器的软件方法在集成到复杂的寄存器分配过程中面临巨大挑战，通常采取保守策略以避免副作用，例如过度依赖寄存器分裂（register splitting）可能引发寄存器溢出（register spilling），或因未考虑寄存器生命周期而增加寄存器压力。

为解决上述问题，本文的研究目标是设计一种新颖的、基于编译器的寄存器银行分配方法，该方法能够在对现有寄存器分配（RA）流程影响最小的情况下，显著减少银行冲突。

本文的主要创新点和贡献如下：
1. 提出了一种名为 PresCount 的新颖寄存器银行分配方法：该方法通过增强寄存器冲突图（Register Conflict Graph, RCG）的着色策略，并引入银行压力跟踪机制，能够进行成本估算和寄存器压力建模。
- 在具有丰富寄存器银行和有限寄存器预算的平台上，与现有方法相比，该方法在 SPECfp 和 CNN-KERNEL 基准测试中分别将银行冲突减少了 43.28% 和 27.76%。

  1. 针对特定领域架构（DSA）提出了子组分裂（subgroup splitting）技术：该方法扩展应用于本文作者所在机构为AI计算设计的、具有“银行-子组”两级寄存器文件结构的DSA。
    • 尽管面临更严格的硬件约束，该技术仍能优化不平衡的寄存器分配，并在特定领域的内核函数上实现了 99.85% 的银行冲突减少。

通过解决寄存器分配中的银行冲突挑战，PresCount 方法在不同寄存器配置和特定领域工作负载的平台上均展现出显著的性能和效率提升，为优化硬件设计探索提供了更大的灵活性。

A3 背景知识与动机

A. 大型寄存器文件构建中的银行冲突

多银行架构的引入与副作用。多银行架构被用于提高计算机内存效率，并已扩展到寄存器硬件，以提升硬件的效率和性能。然而，这种设计也存在弱点。特别是，使用硬件来缓解银行冲突或惩罚会增加硬件设计的复杂性、功耗和延迟挑战。

银行冲突的静态判定与编译器解决方案。在多种架构中，银行冲突作为一种执行期间的硬件资源冒险，通常可以被静态地确定。例如，对于一条中间表示（IR）形式的指令 vr_a = fadd vr_b, vr_c，如果编译器将虚拟寄存器操作数 vr_b 和 vr_c 分配到同一个银行，且硬件微架构不支持从单个银行并行读取，那么在运行时就会产生银行冲突。为了避免这种情况，编译器可以将 vr_b 和 vr_c 分配到不同银行的寄存器中，从而有效解决问题。因此，银行分配过程在最小化此类冲突中扮演着关键角色。


图 1: 不同银行冲突率的工作负载比例。“N-way”代表N路交错寄存器文件的数据。

银行冲突的普遍性。如果不进行银行分配，银行冲突在大型寄存器文件中普遍存在。我们在 SPECfp 和 CNN-KERNEL 测试集上使用 Clang/LLVM 编译器进行了初步实验，如图 1a 和 1c 所示，这些实验证明了银行冲突在各种程序中的普遍性。我们将程序分为以下几类：
* Conflict-irrelevant（冲突无关）：不包含银行冲突指令的程序。
* Conflict-relevant（冲突相关）：包含至少一条银行冲突指令的程序。
* Conflict-free（无冲突）：属于冲突相关但在运行时未触发银行冲突的程序。
* Conflict（有冲突）：属于冲突相关但非无冲突的程序。

实验数据分析。如图 1a 所示，在314个 SPECfp 测试中，有177个（56.37%）是冲突相关的；而图 1c 显示，在64个 CNN-KERNEL 测试中，有53个（85.48%）是冲突相关的。这些初步统计数据表明，银行冲突指令在通用计算和AI计算应用中都很普遍，且后者更为突出。图 1b 和 1d 比较了在四种不同寄存器文件配置（2/4/8/16个银行，寄存器索引交错排列）下，冲突相关程序与无冲突程序的比例。数据显示，SPECfp 测试集中有 50.29% 到 71.18% 的程序并非无冲突，而在 CNN-KERNEL 测试中这一比例为 64.15% 到 84.91%。此外，即使在拥有大量寄存器银行的硬件系统中（通常认为能有效处理银行冲突），实现完全无冲突仍然很困难。因此，基于现有编译器技术设计一种更高效的银行分配方法以减少银行冲突，是非常有必要的。

B. 不平衡的银行分配

基于着色的银行分配方法。基于着色的寄存器银行分配类似于寄存器着色分配。它构建了一个寄存器冲突图（Register Conflict Graph, RCG），其中图 $G_{RCG} = (V, E)$ 的边集 $E$ 代表寄存器银行之间的冲突，顶点集 $V$ 包括所有寄存器及其银行信息。


图 2: 示例代码及其对应的RIG和RCG

不平衡分配问题示例。给定图 2a 中的代码片段，编译器可以构建如图 2b 所示的相应寄存器干涉图（Register Interference Graph, RIG）。此外，图 2c 展示了相关的寄存器冲突图（RCG），它恰好是 RIG 的一个子图，表示寄存器之间的银行冲突。基于 RCG 的银行分配可以在寄存器分配流水线中用于减少银行冲突。如果银行分配阶段在寄存器分配之前，它会将虚拟寄存器映射到特定的银行，从而限制了它们后续只能被分配到指定银行内的寄存器。这给寄存器分配带来了约束，使得无冲突的分配更具挑战性。


图 3: 两种可能的银行分配以及图2b对应子RIG的可着色性

不平衡分配导致分配失败。假设有四个寄存器，其索引交错分布在两个银行中（BANK0 包含 r0, vr2；BANK1 包含 r1, vr3），进行银行分配等同于对图 2c 中的 RCG 进行2-着色。银行分配后，RIG 会被简化，因为不同银行中的寄存器不再相互干涉。图 3a 和图 3b 展示了两种可能的银行分配及其对应的简化 RIG。由于每个银行中有足够数量的寄存器，分配图 3a 所示的 RIG 是可行的，且不会产生银行冲突。然而，图 3b 是不可2-着色的，这表明如果不进行寄存器的分裂/溢出，就不可能实现无冲突的银行分配。

不平衡分配的影响。值得注意的是，原始的 RIG 可以用四种颜色进行着色。然而，如上例所示，一次无冲突的银行分配给 RIG 的着色带来了挑战。这种被称为“不平衡”银行分配的挑战，是现有基于 RCG 的银行分配器中的一个严重问题，导致它们在某些场景下无法应用。银行分配阶段对寄存器分配的明显影响，要求我们设计一种像 PresCount 这样的银行分配器，以最小化对寄存器分配的负面影响。

A2 方法细节

A. 整体工作流程

工作流程概述。我们寄存器分配流水线的整体工作流程如图 4 所示。我们提出了新颖的方法来改进 LLVM 的默认寄存器分配器（即贪心寄存器分配器）以进行寄存器银行分配。为了在实际场景中更具适用性，我们将改进后的寄存器分配流水线应用于我们的 DSA 硬件。考虑到定制的 DSA 硬件对寄存器使用有更严格的子组对齐约束（稍后详细解释），因此提出了一个可选阶段（虚线模块）用于 DSA 优化的子组分裂。


图 4: 整合到LLVM贪心寄存器分配流水线中的组合工作流

流水线各阶段。如图 4 所示，整个流水线包括五个阶段，其中包含 LLVM 的两个标准组件（白色表示），即寄存器合并（Register Coalescing）和分配前调度（Pre-allocation Scheduling），一个增强的寄存器分配（Enhanced Register Allocation）阶段，以及两个新的阶段（蓝色模块表示）：
* RCG-based Bank Assignment（基于RCG的银行分配）：这是一个优化阶段，用于构建 RCG 并执行图着色，以跟踪寄存器银行的压力。该阶段在分配前调度之后触发，在此阶段后可以决定其专用寄存器的银行分配。
* SDG-based Subgroup Splitting（基于SDG的子组分裂）：这是专为定制 DSA 硬件设计的。它接收由寄存器合并产生的 LLVM Machine IR，用于构建相同位移图（Same Displacement Graph, SDG）（稍后解释），收集“寄存器分组”信息，并在必要时应用启发式方法来分裂大组。此模块对于非 DSA 硬件是可选的。

核心设计思想。其中，基于 RCG 的银行分配旨在以一种粗粒度模式跟踪寄存器银行压力，以改善不平衡的银行分配问题，这对于我们的银行分配器设计至关重要。这种设计灵感来源于使用分配前指令调度器的朴素寄存器压力跟踪方法。

增强的寄存器分配阶段。增强的寄存器分配（Enhanced Register Allocation）阶段用于根据基于 RCG 的银行分配阶段决定的银行分配来执行寄存器分配。如果目标是定制的 DSA，该阶段还会考虑寄存器子组压力，进行子组分配。

阶段顺序。在寄存器分配（RA）流水线中，阶段顺序至关重要。为了防止寄存器副本被重新合并，基于 SDG 的子组分裂阶段被置于寄存器合并之后。此外，为了最大化地重用现有的活跃范围信息，基于 RCG 的银行分配阶段被放置在分配前调度和增强的寄存器分配之间，因为它不修改这些信息。


图 5: 带有银行冲突的伪代码及相关的2-着色过程

B. 实现银行分配

银行冲突成本估算。银行冲突的成本取决于代码的位置。循环内的银行冲突相比不常执行的循环中的冲突，对性能和能耗的影响更大。在 PresCount 中，由指令 $I$ 引入的银行冲突成本 $Cost_I$ 定义在公式1中，其中 $tripcount(i)$ 表示其在 n 级循环嵌套中第 i 层循环的总执行次数 ($i \geq 0, n \geq 0$)。寄存器 $R$ 的银行冲突成本 $Cost_R$ 通过对所有访问寄存器 $r$ 的指令成本求和计算得出，如公式2所示。PresCount 利用 $Cost_R$ 值作为优先进行银行分配的判断依据之一，以最小化银行冲突的运行时实例。

$Cost_I = 10^n$ (1)
$Cost_R = \sum_{r \in R} Cost_{I_r}$ (2)

带成本标注的RCG着色。在用冲突成本标注寄存器后，银行分配过程开始。与传统的 Chaitin-Briggs 着色方法不同，我们的方法主要基于冲突成本生成一个优先的分配列表 AssignList。例如，在图 5a 中，我们有五个与冲突相关的指令（A-E），其对应的 RCG 如图 5b 所示。图中的节点代表带有计算出的冲突成本的寄存器。假设有一个双银行寄存器文件，我们根据寄存器冲突成本的降序（即 $b \to c \to d \to e$）对 RCG 进行2-着色，如图 5b 所示。最终，由访问寄存器 $e$ 引入的剩余银行冲突无法被消除，因为它是不可着色的。如果我们假设每次冲突在硬件中产生1个周期的延迟，那么总共会产生2个周期的开销。这代表了在没有应用其他优化时引入的最小成本。

银行压力计数启发式。在实践中，遇到相等的冲突成本是很常见的，特别是当银行冲突主要与最内层循环中的热点算术操作相关时。为了优化银行分配并确保 RIG 子图的可着色性（见第二章B节），我们引入了银行压力计数的概念。这个计数表示在一个银行内，考虑到已分配给该银行的寄存器，寄存器活跃范围的最大重叠数。它在 RCG 可着色性方面存在多种相同选择的情况下，为银行分配器提供指导。当一个寄存器可以被分配到多个银行时，选择压力计数最小的银行。这种方法有效解决了第二章B节中讨论的不可着色情况。

银行分配算法。算法1详细说明了基于 RCG 的银行分配过程。在实践中，RCG 由多个不相交的子图组成。我们按冲突成本的降序处理每个子图。图着色从工作列表 workList 中选择一个节点开始，选择的依据是更高的冲突成本，其次是更高的度。这种优先级排序确保了 PresCount 在考虑 RCG 可着色性之前，首先解决银行冲突成本问题。接着，算法会排除分配给该节点邻居的任何冲突颜色，并根据银行压力计数创建一个优先的分配列表 colors。如前所述，RCG 中不平衡的银行分配可能会阻止后续的寄存器分配器完成无冲突的银行分配，使得银行分配结果不符合预期。不当处理银行分配也可能在实现过程中引发寄存器溢出。因此，动态评估银行压力以确保正确分配至关重要。算法会测试所有可能的银行分配，并为寄存器选择那个增加银行压力计数最少的银行。

不可着色节点的处理。不可着色节点会使用启发式方法分配冲突颜色。为了在最小化寄存器压力和减少银行冲突成本之间进行权衡，我们会对整体寄存器压力 regPressure 进行综合评估。评估结果决定：如果寄存器压力超过预定义阈值 THRES，则从所有候选颜色 ALLCOLORS 中选择一个最优颜色以最小化寄存ter压力。否则，启发式方法会选择那个使累积成本 $Cost_R$ 最小的颜色，其中 $R$ 包含了所有共享此颜色的邻居节点。这集中于减少与银行冲突相关的惩罚。然后，PresCount 用决定的颜色分配节点，并相应地更新银行压力计数。最后，任何未着色的邻居节点被添加到 workList 中。这个过程迭代进行，直到 workList 为空。

处理自由寄存器。值得注意的是，算法1只处理 RCG 中存在的寄存器。然而，为了实现平衡的银行分配，银行分配器还必须考虑那些不在 RCG 中但属于同一寄存器类别的寄存器。这些通常被称为自由寄存器（free registers）的寄存器需要被妥善处理，以防止寄存器分配器从随机的银行中为它们分配寄存器。忽略对自由寄存器的妥善处理同样会导致不平衡的银行分配。


算法 1: PresCount 中的银行分配

C. 针对定制DSA的子组银行分配

定制DSA及其寄存器使用约束。本文讨论的 DSA 旨在提高大规模 AI 模型的处理效率。它通过集成一个大的片上寄存器文件来利用 AI 操作中观察到的时间局部性，从而实现中间输出的重用。该 DSA 的微架构设计接近现代 GPU，但与 SIMT 不同，它引入了具有大向量长度的 SIMD 向量指令来利用指令级并行性。DSA 的每个处理元件（PE）拥有一个 128KB 的向量寄存器文件，分为1024个128字节的向量寄存器。两个并发线程以锁步、共享 PC 的方式共享每个向量寄存器，这使得向量寄存器对每个线程来说有效地表现为一个64字节的寄存器。与 GPU 类似，当指令读取两个向量寄存器操作数时，多银行向量寄存器可能会遇到银行冲突。

微架构简化与“银行-子组”设计。为了避免实现用于寄存器文件和算术逻辑单元（ALU）之间数据路由的交叉开关网络所带来的复杂性和功耗，我们采用了一种微架构简化方案。替代交叉开关的是一种直接的1对1的银行到ALU的模式，主要目标是降低复杂性和功耗。然而，这种硬件简化进一步细分了多银行寄存器文件，使得寄存器使用更具限制性。寄存器文件在概念上被构建为一个两级的“银行-子组”设计，如图 6 所示的 2-4 银行-子组寄存器文件。该图展示了银行和子组如何根据寄存器索引交错排列，以及根据寄存器号计算寄存器的银行号和子组号的方法。


图 6: 银行和子组的寄存器号交错方式


图 7: 银行冲突与子组对齐

银行-子组寄存器文件的约束。银行-子组寄存器文件对寄存器使用施加了两个关键约束：
* 银行冲突约束：每条指令的输入操作数必须属于不同的银行。
* 子组对齐约束：每条指令操作数的子组必须相同。

约束示例。例如，考虑图 7b 中的代码。寄存器 vr1, vr5, vr9, vr10 和 vr13 的银行/子组号分别为 0/1, 1/1, 0/1, 0/2 和 1/1。基于此，我们可以分析如下：
* 指令 I1 满足所有约束，被认为是无冲突的。
* 指令 I2 违反了银行冲突约束，因为它的两个输入操作数都来自银行1。
* 指令 I3 违反了子组对齐约束，因为其输入操作数的子组号不同。
因此，由于寄存器使用受到更严格的约束，它更容易发生银行冲突。为了缓解高寄存器冲突率带来的挑战并消除子组对齐违规，接下来的小节将介绍解决这些问题所必需的优化方法。

用于子组对齐的SDG。子组对齐约束使用相同位移图（Same Displacement Graph, SDG）来表示。SDG，表示为 $G_{SDG} = (V, A)$，是一个有向图，其中顶点集 $V$ 包含所有需要子组对齐的寄存器，而集合 $A$ 由表示子组间对齐约束的有序对组成。有向边连接输入操作数到输出操作数，表明相连的顶点共享相同的位移对齐要求。每条边都从输入操作数指向指令的相应输出操作数。

平衡的子组分配。子组分配是寄存器分配过程中不可或缺的一部分。在我们的实现中，寄存器银行分配在子组分配之前确定。算法2概述了在寄存器分配期间使用寄存器提示进行子组分配的伪实现。该算法监控寄存器分配，跟踪子组利用率，并指导寄存器分配器分配使用较少的子组的寄存器。子组的平衡通过 groupDispls 的簿记和在函数 MinUsed 中选择最小使用子组来维持。用于银行分配的 Hints 列表包含从子组分配中派生的物理寄存器候选。现有的寄存器分配机制在考虑寄存器活跃范围干涉的同时利用 Hints 来完成分配。这确保了银行冲突、子组和活跃范围干涉约束的满足。

子组分配中的其他交互。算法2没有提供寄存器分配操作中其他交互的细节，例如寄存器重分配、寄存器分裂和寄存器溢出。特别是寄存器分裂可能存在问题，因为它会引入新的、活跃范围更短的虚拟寄存器。为了维持子组对齐，新创建的寄存器必须被分配与它们所复制的寄存器相同的子组，这在某些情况下需要动态的子组管理。


算法 2: 生成寄存器分配提示以确保银行分配和子组对齐约束

基于SDG的子组分裂。遇到由大量寄存器组成的大型子组并不罕见。然而，拥有这样的大型子组通常会导致不平衡的子组分配。为了解决这个问题，我们采用子组分裂来避免这种情况。我们确定了大型子组的两种主要模式：
* 输入共享（Input Sharing）：操作共享相同的输入操作数，如图 8 中的“a”操作数。
* 输出共享（Output Sharing）：操作涉及值归约，并通常共享输出，如图 9 中的“a”操作数。


图 8: 解决“输入共享”的示例


图 9: 解决“输出共享”的示例

子组分裂的启发式方法。图 8 和图 9 分别提供了解决输入共享和输出共享场景的示例。在这两种情况下，单个子组包含了所有寄存器。输入共享场景表现为一个具有大量出边的“中心”顶点，而输出共享场景则表现为一个具有大量入边的“中心”顶点。为了处理图 8 中具有大量出边（6条）的子组，我们引入一条复制指令，将图分成两个各含三个顶点的组。图 9 中也应用了类似的分裂启发式方法。这种方法在分配过程（算法2）中有效地创建了平衡的子组，确保了均匀的子组分配。

A4 实验环境

1. 测试套件

我们使用了三个不同的测试套件进行评估：
* SPECfp: 包含来自 SPEC CPU 基准测试的计算密集型浮点测试，重点关注8个主要用 C/C++ 编写的测试。
* CNN-KERNEL: 包含来自卷积神经网络 MobileNet 的64个内核，涵盖了常用的 AI 计算内核，如卷积、池化和激活。
* DSA-OP: 专为在 DSA 硬件上运行而设计，包含高性能手写 AI 计算内核的 C/C++ 实现，如逐元素、归约和特殊操作（如逆离散傅里叶变换）。

表 I 总结了所用测试套件的特性，包括生成的可执行文件、编译的模块、编译的函数、冲突相关指令以及使用默认 LLVM 寄存器分配时的浮点寄存器溢出情况。

Table I: SPECfp 和 CNN-KERNEL 的特性

Exes - 可执行文件。Mods - 模块。Fns - 函数。Reles - 冲突相关指令。Sp32 - 在 RV-Platform#1 上的溢出。Sp1k - 在 RV-Platform#2 上的溢出。† 列中的值（不包括“Exes”）代表冲突相关可执行文件的几何平均值。冲突无关的可执行文件被排除在计算之外。

2. 平台配置

  • Platform-RV:

    • 用途: 测试 PresCount 方法的通用性并与其他实现进行比较。
    • 硬件模拟: 使用 QEMU (7.0.50) 模拟器运行 riscv-64 可执行文件。
    • 软件: LLVM/Clang (11.0.0) 编译器，集成了 PresCount 寄存器分配方法。
    • 配置 #1 (富寄存器): 1024 个浮点寄存器，分为 2、4 或 8 个银行（每个银行分别有 512、256、128 个寄存器），模拟类似 GPU 的富寄存器环境。
    • 配置 #2 (紧缺寄存器): 32 个浮点寄存器，符合 riscv-64 ISA 标准，分为 2 或 4 个银行（每个银行分别有 16、8 个寄存器），模拟单个银行寄存器数量紧张的情况。
    • 对比方法:
      • non: 默认 LLVM 寄存器分配，不缓解银行冲突。
      • bcr: 贪心银行分配方法，部分模仿 Intel 图形编译器的银行冲突减少方法。
      • bpc: 应用 PresCount 方法进行寄存器分配。

  • Platform-DSA:

    • 用途: 在特定的银行-子组 DSA 寄存器设计上测试 PresCount 方法，评估其在更严格微架构下的性能。
    • 硬件: 真实的定制 DSA 硬件，其向量寄存器为 2-4 分区。
    • 软件: LLVM/Clang (11.0.0) 编译器，集成了 PresCount 方法并包含 SDG 子组对齐功能。
    • 对比方法: 比较 non 和 bpc 实现的性能，评估指标包括银行冲突、寄存器拷贝、寄存器溢出以及精确的周期数。

A4 实验结果

1. Platform-RV#1 (富寄存器) 上的结果

  • 银行冲突减少:

    • 图 10a 和 10b 显示，与基线 non 相比，bcr 和 bpc 方法都有效地减少了静态银行冲突。bpc 的效果优于 bcr。增加物理银行数量也能线性减少冲突（银行数翻倍，冲突减半）。
    • 在 CNN-KERNEL 测试中，冲突减少效果更明显，表明这些方法在处理冲突相关指令较少的测试时表现良好。
    • 根据表 II，bcr 方法在 2/4/8 银行设置下，总体银行冲突减少率（几何平均值）分别为 94.16%, 76.51%, 73.23%。
    • bpc 的表现更优，与 bcr 相比，冲突减少量分别提升了 51.21%, 38.64%, 40.98%（几何平均值）。

  • 寄存器溢出影响:

    • 表 III 分析了银行冲突减少与寄存器溢出增加之间的权衡。
    • 在 2-银行设置下，bpc 实现了显著的冲突减少，同时溢出增加量极小。
    • 在 8-银行设置下，bcr 在控制溢出方面表现更好。
    • 在 CNN 测试中观察到负的冲突减少值，主要原因是某些卷积案例中存在大量（约5000条）冲突相关指令，PresCount 由于考虑了银行压力，能够实现比 bcr 更多的无冲突分配。


(a) SPECfp 中不同银行数量下的静态银行冲突：比较 non, bcr, brc 和 bpc 在 Platform-RV#1 上的表现。

(b) SPECfp 基准测试的最大银行冲突数

Table II: 在组合的 SPECfp 和 CNN-KERNEL 基准测试中比较不同银行设置下 RA 方法的冲突和减少量

Table III: Platform-RV#1: 比较银行冲突减少与溢出增量

2. Platform-RV#2 (紧缺寄存器) 上的结果

  • 银行冲突减少:

    • 图 11 展示了动态银行冲突实例。bcr 和 bpc 仍然显著减少了冲突，但效果不如富寄存器环境。在 gromacs 和 dealII 等案例中效果尤为明显。
    • 根据表 IV，在静态冲突方面，bpc 相较于 bcr 在 2-银行和 4-银行设置下分别提升了 59.75% 和 18.99%。在动态冲突方面，提升分别为 22.36% 和 15.19%。静态与动态结果的差距是因为动态执行只运行部分代码，导致遇到的冲突被放大。

  • 寄存器溢出影响:

    • 表 V 显示，溢出增量通常远小于冲突减少实例。但在 4-银行设置下，两者差距变小，bcr 和 bpc 都出现了负的冲突减少。这是因为随着寄存器预算减少，寄存器重分配、分裂、溢出等操作显著增加，使得启发式方法更难与寄存器分配行为保持一致，导致银行分配效率降低。


(a) SPECfp中不同银行数量下的动态银行冲突：比较 non, bcr, brc 和 bpc 在 Platform-RV#2 上的表现。

(b) SPECfp 基准测试的最大银行冲突数

Table IV: 在组合的 SPECfp 和 CNN-KERNEL 基准测试中比较不同银行设置下 RA 方法的冲突和减少量

Table V: 比较银行冲突减少与溢出增量

3. Platform-DSA 上的结果

  • 银行冲突减少:

    • 表 VI 显示，在 2-4 分区银行的 DSA 上，PresCount (2x4-bpc) 几乎消除了所有银行冲突（除 tr18987 外），达到了 99.85% 的几何平均减少率。
    • 相比之下，单纯增加物理银行数量的硬件方案（如 16-non），虽然能减少冲突，但通常无法完全消除，其最佳减少率约为 90%。这表明 PresCount 在拥有大量寄存器时进行无冲突分配非常有效。

  • 成本与性能影响:

    • 表 VII 分析了寄存器溢出、拷贝和周期数。对于计算密集型内核（如 reduce），减少银行冲突对周期数有益。
    • 对于数据并行工作负载（如 shruse），尽管银行冲突减少显著，但由于 AI DSA 能够并行化独立数据计算，性能影响较小。
    • 在银行和子组压力都很大的情况下（如 tr15651 和 idft），子组分裂启发式被调用以避免寄存器溢出。idft 虽然溢出大幅减少，但由于产生了大量拷贝指令，导致周期增加。从软硬件协同设计的角度看，这种权衡是合理的。
    • 架构特定的 VLIW 捆绑约束（禁止捆绑访问同一银行的指令）对 dwconv2d 和 tr18987 造成了性能下降，这是 RCG 方法难以解决的跨指令约束。

Table VI: 比较 bpc 和 non 在多种银行设置下的银行冲突

Table VII: bpr 和 2/4-non 在 Platform-DSA 上的溢出、拷贝和周期数

A7 补充细节

相关工作

大型寄存器文件的使用。大型寄存器文件被划分为SIMD向量，是现代计算架构的基础范式。GPU通过线程共享高效利用这些向量寄存器，而CPU则通过显式编程或自动向量化过程（如循环向量化【14, D. Nuzman等人, Auto-vectorization of interleaved data for simd, PLDI'06】【15, A. E. Eichenberger等人, Vectorization for simd architectures with alignment constraints, PLDI'04】、超字级并行（SLP）向量化【16, S. Larsen等人, Exploiting superword level parallelism with multimedia instruction sets, SIGPLAN Not., 2000】【17, H. Zhou等人, A compiler approach for exploiting partial simd parallelism, ACM Trans. Archit. Code Optim., 2016】【18, H. Zhou等人, Exploiting mixed simd parallelism by reducing data reorganization overhead, CGO'16】等）来利用它们。

GPU架构中的多银行寄存器文件。多银行寄存器文件【19, J.-L. Cruz等人, Multiple-banked ´ register file architectures, 2000】在GPU架构中得到了广泛研究，因为GPU拥有比CPU更大的寄存器文件【20, M. A. Ibrahim等人, Analyzing and leveraging decoupled l1 caches in gpus, HPCA'21】。许多GPU软硬件协同设计研究致力于解决寄存器重用和利用率不足的问题。Gebhart等人在其操作数寄存器文件（ORF）研究中提出了一种由编译器控制的寄存器文件层次结构【5, M. Gebhart等人, A compile-time managed multi-level register file hierarchy, MICRO-44, 2011】，作为寄存器文件缓存（RFC）【21, M. Gebhart等人, Energy-efficient mechanisms for managing thread context in throughput processors, ISCA'11】的替代方案。Esfeden等人【22, H. Asghari Esfeden等人, Corf: Coalescing operand register file for gpus, ASPLOS'19】结合了编译器寄存器分配和寄存器合并硬件来减少寄存器读取。J. Klosterman等人【23, J. Kloosterman等人, Regless: Just-in-time operand staging for gpus, MICRO-50'17】通过编译器提示将指令操作数预加载到暂存单元中，加速了对短生命周期操作数的访问。Xie等人【24, X. Xie等人, Enabling coordinated register allocation and thread-level parallelism optimization for gpus, MICRO-48, 2015】试图通过探索寄存器分配和线程节流来解决GPU上的寄存器文件利用率不足问题。C. Yu等人【25, C. Yu等人, Improving thread-level parallelism in gpus through expanding register file to scratchpad memory, ACM Trans. Archit. Code Optim., 2018】将GPU寄存器扩展到暂存存储器以提高寄存器文件的利用率。

寄存器分配技术的发展。寄存器分配已被广泛研究数十年。Chaitin等人【7, G. J. Chaitin等人, Register allocation via coloring, Computer languages, 1981】实现了第一个将寄存器分配视为图着色问题的寄存器分配器。Briggs等人【26, P. Briggs等人, Improvements to graph coloring register allocation, ACM Trans. Program. Lang. Syst., 1994】通过乐观着色方法改进了寄存器溢出处理。Polleto等人【27, M. Poletto等人, Linear scan register allocation, ACM Trans. Program. Lang. Syst., 1999】开发了线性扫描方法以提高时间复杂度。

基于SSA形式的寄存器分配。然而，一些GPU编译器更倾向于基于SSA形式的寄存器分配器，因为它能够在多项式时间内识别所需寄存器，以促进动态线程级寄存器分配【28, C. Abbott等人, SSA-based register allocation for ¨ gpu architectures, http://X.Org Developer Conference 2021】。Hack等人【29, S. Hack等人, Optimal register allocation for ssa-form programs in polynomial time, Inf. Process. Lett., 2006】是首批证明SSA程序的干涉图是弦图的研究者之一，因此在基于SSA的程序中，着色、溢出和合并可以分开进行。Pereira等人【30, F. M. Q. Pereira等人, Register allocation via coloring of chordal graphs, APLAS 2005】观察到大多数Java库方法的干涉图都是弦图。

针对不规则架构的寄存器分配。上述所有寄存器分配方法都试图解决活跃范围干涉问题。额外的架构寄存器限制被建模为活跃范围干涉【7, G. J. Chaitin等人, Register allocation via coloring, Computer languages, 1981】。Scholz等人【31, B. Scholz等人, Register allocation for irregular architectures, LCTES/SCOPES'02】将不规则架构的全局寄存器分配问题表述为分区布尔二次问题（PBQP），并采用一种启发式方法试图在线性运行时间内解决这个NP完全问题。Hames等人【32, L. Hames等人, Nearly optimal register allocation with pbqp, JMLC'06】提出了一种启发式和分支界限求解器来提高寄存器分配质量。LLVM【33, C. Lattner等人, Llvm: a compilation framework for lifelong program analysis transformation, CGO 2004】采用PBQP寄存器分配器来处理寄存器别名、寄存器配对等不规则性问题【34, F. M. Q. Pereira, A survey on register allocation, Tech. Rep., 2008】。

基于RCG的寄存器分配。基于RCG的寄存器分配通常用于处理寄存器银行冲突的不规则性。虽然RCG是RIG的子图【8, A. P. et al., Conflict-free register allocation using a multi-bank register file with input operand alignment, US Patent, 2013】，但它是为银行分配目的独立构建的。分配前和分配后方法被用于将基于RCG的银行分配集成到寄存器分配器中。F. Zhou等人【9, F. Zhou等人, A register allocation framework for banked register files with access constraints, 2005】在寄存器分配之前，使用成本评估方法和活跃范围分裂方法为双银行寄存器文件构建了RCG。Zhuang和Pande【10, X. Zhuang等人, Resolving register bank conflicts for a network processor, PACT'03】证明了以最小代价构建一个二分RCG是NP完全的。分配前方法中的不平衡银行分配和寄存器溢出可能导致寄存器分配质量不佳。Patney等人【8, A. P. et al., Conflict-free register allocation using a multi-bank register file with input operand alignment, US Patent, 2013】选择了分配后寄存器重编号，尽管这使得RCG更难着色，其中会生成大量寄存器拷贝来分裂未着色的RCG并对齐子组，这需要许多未分配的寄存器作为结果。Sadrosadati等人提出的延迟容忍寄存器文件（LTRF）【3, M. Sadrosadati等人, Highly concurrent latency-tolerant register files for gpus, ACM Trans. Comput. Syst., 2021】【35, M. Sadrosadati等人, Ltrf: Enabling high-capacity register files for gpus via hardware/software cooperative register prefetching, ASPLOS'18】构建了一个区间冲突图（ICG）并在不同区间内重编号物理寄存器以避免银行冲突。然而，它与分配后方法有类似的局限性。

Intel图形编译器的启发式方法。Intel图形编译器使用了一种银行冲突减少（BCR）启发式方法，仅在寄存器分配时可行的情况下，将指令操作数分配到不同的银行，以避免寄存器溢出并缓解银行冲突【12, W.-Y. Chen等人, Register allocation for intel processor graphics, CGO 2018】。然而，它没有对超过单条指令的银行冲突限制进行建模。

寄存器压力跟踪。关于寄存器压力跟踪，它被用于在增加ILP的同时避免寄存器溢出，许多启发式方法已应用于分配前指令调度。Touati提出了在数据依赖图（DDG）中使用有限同时活跃范围的寄存器饱和（RS）分析【36, S.-A.-A. Touati, Register saturation in instruction level parallelism, International Journal of Parallel Programming, 2005】。类似地，Gavindarajan等人【37, R. Govindarajan等人, Minimum register instruction sequencing to reduce register spills in out-of-order issue superscalar architectures, IEEE Transactions on Computers, 2003】在线性干涉图（LIG）上使用着色方法来找到启发式寄存器界限（HRB）以实现类似的目标。

A5 结论

本文解决了多银行寄存器文件中的银行冲突问题，并提出了有效的解决方案。实验证实了在具有多银行寄存器文件的系统中，银行冲突是普遍存在的。为了减轻由银行冲突引起的性能下降和运行时开销，本文引入了 PresCount 方法，该方法利用基于 RCG 的银行分配和银行压力跟踪。

实验结果表明，PresCount 的性能优于现有方法。此外，本文还提出了一种新颖的子组分配技术，使得定制的 DSA 能够在微架构简化的前提下，达到与全功能银行寄存器文件架构相当的性能。

研究发现，跟踪银行压力是实现平衡银行分配的一种有价值的启发式方法，而早期分裂共享值在实现平衡子组分配中起着关键作用。

未来工作展望：
* 可以专注于进一步增强这些启发式方法，因为当前的寄存器分配过程在高寄存器银行压力下可能会遇到挑战。
* 研究将 PresCount 与其他寄存器分配（RA）方法相结合可能会提供进一步的见解。