Page 61 - 《软件学报》2024年第6期

高猛 等: 位宽感知的寄存器绑定算法 2637

最优的绑定方案, 该方案将寄存器空间视为一个连续的线性空间, 任何访问都通过一段区间来表示, 不同的变量共
b, c, d, e 错位地共享了一部分寄存器, 共需 15 位寄存器, 相
享同一个寄存器的不同比特位. 在该分配方案中, 变量
比于 Swap 算法进一步减少了 1 位寄存器, 且无需插入额外的指令. 这是 WIGC 抽象方法所无法实现的寄存器绑
定方案. 因此我们需要提出一种新的抽象, 该抽象能够更加自由地描述变量之间的共享关系, 且不会产生额外的寄
存器约束.

3 图的连续多重着色抽象

在本节中, 为了解决已有算法中存在的问题, 我们引入了图的连续多重着色模型. 首先, 我们给出了连续多重
着色问题的明确定义. 接下来, 我们对连续多重着色问题的理论下界进行了详细分析, 以作为评估和设计我们算法
的依据. 最后, 为了实际解决寄存器绑定问题, 我们提出了一种基于优先度的启发式算法, 该算法不需要插入额外
的拷贝指令, 且相比于已有算法能够进一步减少寄存器的数量.

3.1 连续多重着色抽象
根据第 2.5 节的分析结果, 我们提出一种图的连续多重着色抽象来对寄存器绑定问题进行求解. 为了更清晰
R[9:4] , 变量 被分配到了寄存器
地阐述我们的思路, 我们首先引入图的多重着色问题 (multi-coloring, MC) 的定义.
定义 3. 图的多重着色问题. 给定加权图 G(V,E,W) , 对每个顶点 v ∈ V 染 w(v) 种不同颜色, 记颜色集合为 C(v) ,

求解符合条件的着色方案, 使得对于任意边 (a,b) ∈ E , 都有 C(a)∩C(b) = ∅ 成立.
我们记 MC 问题的最小色数为 γ(G) . MC 问题强调了我们对于寄存器绑定问题中变量之间更为灵活的共享
方式的建模, 它可以很好地描述比特粒度的寄存器共享问题. 在 MC 问题中, 每个顶点 v 的颜色集合 C(v) 可以视为
按比特粒度分配的寄存器, 而每个边 (a,b) 则可以视为两个变量 a,b 的访问冲突. 但是, MC 问题并不能实际地解决
寄存器绑定问题, 因为该问题中的颜色集合 C(v) 是离散的, 而寄存器的访问则是连续的, 无法满足寄存器绑定问
题中的区间约束.
为了实际地解决寄存器绑定问题, 我们进一步定义颜色集的连续性. 我们称颜色集合 C(v) 是连续的, 当且仅
当存在某个 k ∈ N , 使得 |C(v)∩[k,k +w(v))| = w(v) . 在此基础上, 我们提出了图的连续多重着色问题, 其定义如下.
定义 4. 图的连续多重着色问题. 给定加权图 G(V,E,W) , 求解满足条件的多重着色方案, 使得任意顶点 v ∈ V
的颜色集合 C(v) 是连续的.
连续多重着色问题在某些研究工作中也被称为区间着色 (interval coloring) 问题 [37] . 该问题与寄存器绑定问题
P 可以一一映射为 CMC G(V,E,W) , 其中变量集合映射
是等价的, 因为寄存器绑定问题中的程序 问题中的加权图
为图的顶点集合, 变量的位宽映射为顶点权重, 变量的冲突关系映射为图的边, 寄存器集合映射为颜色集合, 区间
约束则映射为颜色集合的连续约束. 我们记 CMC 问题的最小色数为 γ (G) .
∗
CMC 抽象精确描述了每个变量分配在寄存器中的位宽与活跃区间, 无需遵循额外的对齐约束. 对于任意一
个 WIGC 问题的解 C , 总是可以通过将 C 中的每个寄存器拼接成为一个大寄存器得到一个 CMC 问题的解, 反之
CMC 问题的解却不一定是 WIGC 问题的解. 因此 CMC 抽象相比于 WIGC 抽象更加契合寄存器绑定问题, 能够更
加灵活地描述变量之间的复用关系.
图 2(c) 显示了 CMC 抽象的一种多重着色方案. 在该着色方案中, 变量 a 被分配到了寄存器 R[14:10] , 变量 b
e
被分配到了寄存器 c R[3:0] , 变量 d 被分配到了寄存器 R[9:7] , 变量 被分配到了
R[6:0] . 该着色方案的色数为 15, 而 WIGC L(G) = 16 , 因此 CMC 抽
寄存器 抽象对该样例限定的理论下界范围为
象突破了 WIGC 抽象限定的理论下界.

3.2 理论下界分析
即使对于区间图, CMC 问题仍然已被证明是 NPC 问题 [36,37] , 因此我们无法在多项式时间内给出该问题的解.
但作为参考, 在我们可以在多项式时间内给出该问题的理论下界.
由于 CMC 问题是 MC 问题的特例, γ(G) ⩽ γ (G) , 因此, MC 问题的最优解即为 CMC 问题的理论下界. 对于
∗