Page 65 - 《软件学报》2024年第6期
P. 65

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


                 4   实验评估

                 4.1   实验环境

                    本节将从如下几个角度分别对本文提出的工作进行评估.
                    1) 本文提出的连续多重着色抽象          (CMC  抽象) 相比于第    2  节介绍的  Cong  算法和  Swap  算法的区别是什么, 它
                 们分别划定了怎样的问题求解范围.
                    2) 本文提出的启发式算法        (CMC-h  算法) 的实际分配效果如何, 与      Cong  算法和  Swap  算法相比较效果如何.
                    3) CMC-h  算法进行寄存器绑定需要多长时间.
                    4) CMC-h  算法计算的绑定方案是否可综合, 对逻辑综合会造成怎样的影响.
                    本文寄存器绑定算法应用的单元是一个函数, HLS                中调度与绑定通常被划分为独立的优化过程, 且寄存器绑
                 定通常是在调度之后的资源绑定阶段进行, 因此调度算法的选择并不影响本文寄存器绑定算法的有效性. 为了模
                 拟寄存器绑定的输入, 我们按照尽早调度原则              (ASAP) 进行调度   [1] , 然后再进行寄存器绑定算法的评估.
                    我们在   LLVM 11.0.0 版本中实现了本文提出的技术, 使用           LLVM  自带的位宽分析功能处理前置的分析工作.
                 同时使用了    MiBench [15] 与  Rosetta [16] 套件作为测试集, 如表  1  所示, MiBench  是一组共  35  个具有商业代表性的用
                 于基准测试的嵌入式应用程序, 涉及工业自动化, 消费类设备, 办公, 网络, 安全与通信这                        6  个不同的类别; Rosetta
                 是一组针对真实场景的 FPGA 的基准测试套件, 包括机器学习与视频处理等热门场景下的多个完全开发的应用程
                 序. 实验在  Intel Xeon Gold 6248 CPU 20  核处理器上进行, 时钟为  2.50 GHz. 使用的操作系统是    Ubuntu Linux LTS
                 20.04  版本. 我们的实现将代码生成为       LLVM  机器代码中间表示       (MIR), 并使用  LLVM  中已经存在的寄存器分配
                 基础设施进行分配. 我们并没有将这些结果映射到逻辑门中, 因为我们缺少必要的工具来做这件事. 然而作为一个
                 概念的验证, 我们将一些分配结果手动翻译成了               Verilog  并进行综合分析, 我们将在第      4.5  节进行具体的解释.

                                           表 1 MiBench  测试集  [15] 与  Rosetta 测试集  [16]

                     测试集               测试场景                                测试样例
                                      工业自动化       Rosetta
                                                                    basicmath, bitcount, qsort, susan
                                       消费类                jpeg, lame, mad, tiff2bw, tiff2rgba, tiffdither, tiffmedian, typeset
                                        办公                      ghostscript, ispell, rsynth, sphinx, stringsearch
                     MiBench
                                        网络                        dijkstra, patricia, CRC32, sha, blowfish
                                        安全                       blowfish, pgp sign, pgp verify, rijndael, sha
                                        通信                         CRC32, FFT, IFFT, ADPCM, GSM
                                       3D渲染                              integer arithmetics
                                      数字识别                          Hamming distance, KNN voting
                                     垃圾邮件过滤              dot product, scalar multiplication, vector addition, Sigmoid function
                     Rosetta
                                   光流 (物体运动检测)                       1D convolution, outer product
                                  二值神经网络 (BNN)                 binarized 2D convolution, binarized dot product
                                       人脸检测                        image scaling, cascaded classifiers

                    我们对   MiBench  [15] 中的  609  个函数与   [16] 中的  22 253  个函数进行了分析与测试. 表   2  总结了寄存器绑
                 定的汇总结果, 其中运行时间以毫秒为单位, 寄存器大小以位为单位, “Geo”是几何平均值, “Avg”是算术平均值.
                 结果显示在    MiBench  测试集中  CMC-h  算法相比于    Swap  算法和  Cong  算法分别减少   1.8%  和  1.4%  的寄存器, 同
                 时相比于最优解仅多使用         0.13%  的寄存器资源; 在    Rosetta 测试集中  CMC-h  算法相比于   Swap  算法和  Cong  算法
                 分别减少   1.97%  和  1.98%  的寄存器, 同时在所有的测试用例中       CMC-h  算法均达到了最优解.

                 4.2   CMC  抽象的最优解评估
                    本节评估了     CMC  抽象的最优解相比已有方法的理论最优解的差别, 进而表明我们引入                      CMC  抽象的必要性.
                 其中  CMC  问题的最优解通过对       CMC-h  算法未达到理论下界的样例分析, 采用整数线性规划方法                  (ILP) 精确求解
   60   61   62   63   64   65   66   67   68   69   70