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

2642 软件学报 2024 年第 35 卷第 6 期

得到, 在给出的测试集中我们暂未发现实际的最优解不等于我们给出的理论下界的样例, 但我们仍无法在理论上
∗
证明 γ(G) = γ (G) . Cong 算法的最优解我们目前无法准确求解, 但我们可以通过第 2.4 节给出的理论下界 L(G) 代
替, 实际的最优解结果将不小于该值. 而 Swap 算法的分配结果本身就是在其抽象问题下的一种理论最优解.

表 2 绑定测试结果对比汇总 (以函数为单位)

MiBench Rosetta
算法 对比项
Geo Avg Geo Avg
时间 (ms) 0.98 5.87 0.18 0.60
CMC-h 大小 (bit) 320.33 499.19 161.01 219.46
最优解 (bit) 320.00 498.54 161.01 219.46
时间 (ms) 0.53 3.80 0.090 0.33
Swap
大小 (bit) 324.75 506.38 162.26 223.88
时间 (ms) 0.15 0.96 0.025 0.073
Cong
大小 (bit) 325.54 508.13 162.27 223.91

中均取得了最优的分配结果. 这些实验结果表明, CMC-h
图 5 显示了 MiBench 测试集中 CMC 抽象的最优解, Cong 算法的理论下界与 Swap 算法的最优解之间的对
比, Cong 算法的理论下界与 Swap 算法的最优解分配结果是一致的, 因此我们在图 5 中合并展示. 其中, 横轴上的
每个刻度代表一个函数, 按照 CMC 问题最优解需要的比特数从小到大排序; 纵轴代表所需的寄存器比特数量. 结
果显示, 在 22.66% 的样例中, CMC 问题最优解突破了原有 Swap 算法已经达到理论最优解的限制范围, 平均可以
减少 6.96% 寄存器数目, 在其余样例中 CMC 问题最优解等于 Swap 算法的最优解.

Cong 算法下界 (Swap 算法最优解) CMC 最优解
1 920
比特数 480

120
30
0 100 200 300 400 500 600
函数数量
图 5 MiBench 测试集中 CMC 抽象的最优解, Cong 算法下界和 Swap 算法最优解的比较

4.3 绑定方案对比
图 6 对不同的分配器实现在寄存器绑定问题上所需的比特数量进行了比较, 以 Cong 算法为基线进行相对对
比. 图中的每个横向刻度代表一个函数, 按照 CMC-h 算法提升的相对百分比进行排序, 而图的纵轴表示其他算法
相对于 Cong 算法分配结果的提升百分比. 可以观察到, 在 MiBench 测试集中 CMC-h 算法在仅有 1.1% 的样例中
的分配结果略逊于 Swap 算法. 这是由于 CMC-h 算法在变量的分配顺序上存在一定的随机性, 导致在少数样例中
错过最优的分配结果, 产生了寄存器冗余现象. CMC-h 算法与 Swap 算法在 76.4% 的样例中同时取得最优解, 在
0.3% 的样例中二者取得相同的分配结果, 但都不是理论最优. 在 22.2% 的样例中, CMC-h 算法优于 Swap 算法;
在 Rosetta 测试集中, CMC-h 算法在 6.9% 的测试样例中分配了比其他两种方法更少的寄存器, 同时在所有的样例
算法相比于 Cong 算法与 Swap 算法, 能够取得更加优秀
的绑定结果, 进一步减少寄存器资源的使用.
图 7 从另一个角度强调了这一结果, 在 MiBench 测试集中, Cong 与 Swap 算法分别只有 73.56% 和 77.34% 的
样例达到了 CMC 问题的最优解, 而 CMC-h 算法在 96.72% 的样例中达到了最优解, 相比于前两种方法分别将这
一比例提升了 31.5% 和 25.1%. 实验结果表明, CMC-h 算法的绑定结果已接近理论最优, 在所有的测试样例中, 相
比于最优解平均仅多使用 0.13% 的额外资源. 在 Rosetta 测试集中, 相比于 Cong 和 Swap 算法均提高了 7.4%,
CMC-h 在所有测试用例中均达到了理论最优的分配结果.
此外, 我们简单评估了参数 α ∈ [0,1] 对于实验结果的影响. 如图 8 所示, 我们等间距地选择 0–1 之间的 11 个