Efficient Localization for Codes Causing Compilation Optimization-induced Result Inconsistency
-
摘要: 编译器是程序开发人员最依赖的性能优化工具之一. 然而, 受限于浮点数有限精度编码问题, 很多编译优化选项会改变浮点计算的语义, 进而导致程序计算结果不一致. 定位程序中导致编译优化结果不一致的语句对于程序性能优化和结果可复现具有重要意义. 当前最先进的方法PLiner采用基于语句精度增强的二分搜索来定位导致编译优化结果不一致的代码段, 受限于对多源问题代码的定位支持不够和搜索效率不高问题. 提出一种浮点指令差异性引导的Delta调试定位方法FI3D, 利用Delta调试中的回溯机制更好地支持多源问题代码定位, 基于不同编译优化选项下函数浮点指令序列的差异性来引导定位. 使用NPB基准测试集中的6个应用、GSL数学库中的10个程序和floatsmith混合精度测试集中的2个程序对FI3D进行了评测, 实验结果显示FI3D能够成功定位PLiner失效的4个测试用例, 且对PLiner成功定位的14个测试用例获得了平均26.8%的性能提升.Abstract: The compiler is one of the most relied-upon performance tuning tools for program developers. However, due to the limited precision encoding of floating-point numbers, many compiler optimization options can alter the semantics of floating-point calculations, leading to result inconsistency. Locating the program statements that cause compilation optimization-induced result inconsistency is crucial for performance tuning and result reproducibility. The state-of-the-art approach employs precision enhancement-based binary search to locate the code snippets causing result inconsistency but suffers from insufficient support for multi-source localization and low search efficiency. This study proposes a floating-point instruction difference-guided Delta-Debugging localization method, FI3D, which utilizes the backtracking mechanism in Delta-Debugging to better support multi-source problem code localization and exploits the differences in floating-point instruction sequences under different compiler optimization options to guide the localization. FI3D is evaluated using 6 applications from the NPB benchmark, 10 programs from the GNU scientific library, and 2 programs from the floatsmith mixed-precision benchmark. Experimental results demonstrate that FI3D successfully locates the 4 applications where PLiner fails and achieves an average 26.8% performance improvement for the 14 cases successfully located by PLiner.
-
编译优化会将程序代码段转换为功能等价的更高质量的代码段, 已经成为开发人员优化程序性能最主要的途径之一. 然而, 开发人员往往并不知道每个编译优化选项背后所执行的具体优化策略, 特别是认识不到相同的编译选项在不同编译器内的优化含义也是不同的, 例如Intel编译器ICC与GNU编译器GCC在-O3选项下会执行不同的优化策略. 很多激进编译优化策略会改变浮点操作的语义, 导致程序的计算结果发生改变, 这种现象称为编译优化结果不一致性(compilation optimization-induced result inconsistency)[1].
浮点数是实数在计算机内部存储表示的事实标准. 受限于浮点数的有限精度编码问题, 舍入误差(rounding error)不可避免. 浮点运算不满足实数运算相关的优化理论, 例如结合律和分配率. 浮点融合乘加(fused multiply add, fma)是高性能计算领域广泛应用的性能优化手段, 然而fma操作比fmul和fadd序列少了一个浮点舍入步骤, 会导致计算结果产生差异性. 为了解决融合乘加所带来的结果差异性, 工程实践中常通过-ffp-contract=off选项来禁用浮点表达式收缩优化. 为了提升程序性能, 程序开发人员在编译时会使用一些IEEE-Unsafe的激进编译优化选项(例如-freciprocal-math和-fassociative-math)[2,3], 这也会导致结果不一致性. 例如GCC编译运行单精度表达式1.23+1E10–1E10时, -O0选项的结果为0 (1.23会在第1步求和时被舍入), 而-O3 -ffast-math选项会将表达式直接优化为1.23.
有效发现编译优化结果不一致性并定位导致结果不一致性的问题代码对于科学计算的结果可复现性和性能优化具有重要意义[4]; Varity[5]使用随机差分测试来检测编译优化结果不一致性, CIV[6]在输入空间内进行启发式搜索获得触发编译优化结果不一致性的输入. 编译优化结果不一致性问题代码定位主要基于代码精度增强或者编译选项回归的二分搜索(例如FLiT[2,3]、PLiner[4]和CIEL[7]). 在定位到导致编译优化结果不一致性的代码后, 程序开发人员可以仅对该部分问题代码进行高精度浮点执行(例如PLiner[4])或者浮点表达式精度增强重写(例如Herbie[8]、AutoRNP[9]和ACESE[10]), 使得程序既能获得高级别编译优化所带来的性能提升也满足计算结果的可复现性.
本文主要关注如何更高效地定位导致编译优化结果不一致性的代码段. 当前最先进的定位工作是PLiner[4], 一种基于浮点语句精度增强的二分搜索定位工具; PLiner会将可疑代码段中的浮点语句提升为高精度(long double)执行, 如果程序精度增强变换后编译优化结果不一致性消失, 则表示触发结果不一致性的问题代码位于被精度提升的代码段中, PLiner会进一步采用二分搜索来缩小问题代码范围; PLiner会在函数级、循环级、基本块级和语句级不断采用二分精化搜索来定位问题代码.
然而, PLiner主要存在两方面不足: (1)不能有效支持多源问题代码段的定位. 例如当导致编译优化结果不一致性的问题代码分布在两个不同的函数内时, 可能会导致二分搜索定位失效; (2)对搜索域内的所有代码进行二分搜索导致问题代码定位效率不高. 激进编译优化对不同代码段的影响程度不同, 考虑到高精度浮点的巨大执行开销, 将浮点计算行为未发生改变的浮点代码段也转换为高精度模式并执行会显著增加问题代码定位的时间开销.
为了解决现有编译优化结果不一致性问题代码定位方法存在的问题, 本文提出了一种浮点指令差异性引导的Delta-Debugging[11]定位方法FI3D (floating-point instruction difference guided Delta-Debugging). 一方面, 与传统的二分搜索定位不同, FI3D采用Delta-Debugging搜索策略, 借助其内部的回溯机制解决了现有方法对多源问题代码定位支持不够的问题; 另一方面, FI3D基于函数在编译优化前后的浮点指令序列差异性对函数进行过滤排序, 过滤掉那些编译优化前后浮点计算行为未发生改变的函数, 并优先对浮点指令序列差异性大的函数进行搜索, 显著提升了问题代码定位效率. 在开源NPB测试集(https://www.nas.nasa.gov/software/npb.html)、GSL数学库[12]和floatsmith[13]混合精度测试集上的对比实验显示, FI3D的定位能力和定位效率都显著优于当前最先进工具PLiner.
本文的主要贡献可归纳如下.
(1) 提出了一种基于Delta-Debugging搜索的编译优化结果不一致性问题代码定位方法, 与当前最先进工具PLiner相比, 该方法能够有效支持多源问题代码的定位.
(2) 提出了一种基于编译优化前后函数浮点指令序列差异性的代码过滤和排序机制, 能够有效提升问题代码的搜索定位效率.
(3) 基于NPB测试集中的6个典型应用、GSL数学库中的10个函数和floatsmith混合精度测试集中的2个程序对本文方法进行了评测, 实验结果表明: 本文方法能够成功定位PLiner失效的4个测试用例, 且对PLiner定位成功的14个测试用例能够获得平均26.8%的性能提升.
本文第1节介绍相关工作, 包括基于高精度浮点差异测试的误差检测、编译优化结果差异性分析和浮点精度修复. 第2节介绍本文所需的基础知识, 包括编译优化结果差异性概念和基于浮点精度增强的问题代码二分搜索. 第3节介绍本文提出的浮点指令差异性引导的Delta-Debugging搜索定位方法. 第4节通过对比实验展示本文方法的有效性和高效性. 最后总结全文.
1. 编译优化结果差异性分析相关工作
本节详细介绍编译优化结果差异性分析的相关工作, 包括基于高精度浮点差异测试的误差检测、触发编译优化结果差异性的输入生成方法、面向编译优化结果差异性的问题代码定位方法和基于程序变换的浮点精度问题修复技术.
(1)基于高精度浮点差异测试的浮点误差检测. FPDebug[14]和Herbgrind[15]在实际执行程序每条浮点指令时会同时基于高精度数学库(MPFR[16])做影子执行, 通过对比影子执行和实际执行结果的差异来评估浮点操作的舍入误差; BGRT[17]、EAGT[18]、LGSA[19]和DEMC[9]设计了不同的启发式搜索策略在输入域内采样获取触发高浮点误差的输入, FPGen[20]将触发浮点误差的输入生成问题转换为程序分支覆盖问题, 并基于符号执行[21]进行求解. 这些方法都会执行搜索得到的输入并与高精度模式下的执行结果进行对比, 依此来评估浮点输入所产生的误差. 与上述方法直接将高精度浮点执行作为测试预言(test oracle)不同, FI3D是根据代码段的高精度版本是否会解决结果不一致性问题来判定该段代码是否是触发编译优化结果差异性的问题来源. 此外, FI3D基于编译优化前后浮点指令差异性优先对浮点计算行为改变大的代码段进行精度增强测试, 有效减少了高精度浮点代码变换和执行的开销.
(2)触发编译优化结果差异性的输入生成方法. Varity[5]能够生成随机测试用例, 对随机采样得到的输入对比不同编译优化选项下的执行结果, 评估该输入是否触发了编译优化结果不一致性; CIV[6]基于输入空间划分和马尔可夫链蒙特卡洛(Markov chain Monte Carlo, MCMC)[22] 采样快速产生触发编译优化结果差异性的输入; CIGEN[23]基于浮点输入域划分和覆盖率引导的输入采样来产生触发编译优化结果不一致性的输入区间. 与这些触发编译优化结果不一致性的输入生成方法不同, FI3D是对已发现的编译优化结果不一致性进行问题代码定位; Bintuner[24]研究编译优化选项对编译生成的二进制指令序列的影响, 并基于遗传算法来产生触发二进制指令序列最大差异性的编译优化配置. 与Bintuner关注通过编译优化配置来最大化二进制指令序列差异性不同, FI3D关注面向编译优化结果差异性的问题代码定位.
(3)编译优化结果差异性的问题代码段定位. FLiT[2,3]通过模糊测试发现触发两个编译优化选项结果不一致的输入, 然后通过对文件和函数的二分搜索来定位导致结果差异性的文件和函数; FLiT在搜索过程中观察将给定文件/函数的编译选项恢复成基础编译选项后结果不一致性是否消失来判定问题代码是否在当前文件/函数列表内. 显然FLiT只能在文件/函数级别定位问题代码, 且不适用于代码文件中包含大量函数或者函数体语句较多的场景; PLiner[4]是一种基于浮点精度增强的二分搜索定位工具; PLiner在搜索过程中会将可疑问题代码段自动转换为高精度版本, 然后使用激进编译优化选项编译执行, 如果结果不一致性消失则表示问题代码包含在提升精度的代码中, 会对该段代码进一步进行二分搜索; PLiner会在函数级、循环级、基本块级和语句级分层进行精化搜索, 适用场景更全面且代码定位粒度更细; PLiner的二分搜索策略不能有效支持多源问题代码的定位, 且二分搜索的效率不高问题会加重定位过程中高精度浮点运算引入的巨大执行开销; FI3D从两个方面对PLiner进行提升, 一方面采用Delta-Debugging搜索来支持多源问题代码的定位, 另一方面基于编译优化前后的浮点指令差异性来引导搜索, 提升问题代码定位效率; CIEL[7]是一个面向GPU程序编译优化结果差异性的问题代码定位工具, 定位思想与PLiner基于语句增强的二分搜索类似. 与CIEL不同, FI3D面向传统的CPU程序, 且FI3D浮点指令差异性指导的Delta-Debugging搜索方法可以直接用于优化CIEL.
(4)基于程序变换的浮点精度修复技术. 程序变换被广泛应用于浮点精度问题修复, 最直接方式是将程序转换为高精度浮点执行; AutoRNP[9]会针对给定输入下的浮点误差生成补丁代码, 基于插值技术拟合高精度计算结果; Herbie[8]为了提升浮点表达式的计算准确性, 会将输入区间划分成不同子区间, 然后在不同输入子区间内使用精度更高的浮点表达式替换重写; ACESE[10]基于误差微结构和统计信息来获取浮点误差分布, 并通过程序综合生成多项式补丁代码来修复精度问题. 在FI3D定位到导致编译优化结果不一致性的问题代码段后, 可以使用上述浮点精度修复技术对这些代码段进行重写, 使得程序既可以获得高级别编译优化带来的性能提升又能够确保结果可复现性. 需要特别指出的是高精度浮点执行在绝大部分情况下可以解决浮点舍入误差问题, 但是并不适用于那些罕见的浮点特定精度(precision-specific)[25]运算场景. 例如, GLIBC库的exp函数定义了双精度浮点变量n=6755399441055744.0, 使用语句(x+n)–n来对双精度浮点数x取整, 显然该取整功能只面向双精度浮点数, 将变量x和n提升为更高精度则会破坏程序原有语义.
2. 背景知识
本节主要介绍浮点表示、编译优化结果差异性和基于精度增强的编译优化结果差异性定位.
2.1 浮点表示和编译优化结果差异性
浮点数是实数在计算机内部的近似表示. IEEE-754[26]是应用最广泛的浮点数编码标准, 一个浮点数可以表示为: (–1)S×M×2E. 符号位S为1表示负数, 0表示正数; M=m0.m1m2…mn是尾数, 其中m0为隐藏位, .m1m2…mn是n位尾数位; E=e–bias是p位阶码, 其中e是按位存储的偏置阶码, 偏置值bias为2p–1–1. 表1给出了不同精度浮点数IEEE-754的编码格式.
表 1 IEEE-754浮点编码格式精度 符号位 阶码 尾数 fp16 1 5 10 float 1 8 23 double 1 11 52 由于浮点数采用有限精度编码, 舍入误差不可避免. 当一个实数不能被浮点数精确编码表示时, 会根据系统的舍入模式(例如就近舍入)对其进行近似表示. 假定R和F分别表示实数和浮点数集合, 给定实数x (x∈R), 它的浮点表示为xf (xf∈F), 对应的舍入误差为x–xf. 绝对误差(absolute error,
$ {Err}_{{\mathrm{abs}}} $ )和相对误差(relative error,$ {Err}_{{\mathrm{rel}}} $ )被广泛用来衡量舍入误差. 给定浮点函数f(x), 假定fr(x)表示函数的精确计算结果, 绝对误差$ {Err}_{{\mathrm{abs}}} $ 和相对误差$ {Err}_{{\mathrm{rel}}} $ 的定义如下:$$ Er{r_{{\mathrm{abs}}}}(f(x), {f_r}(x)) = |{f_r}(x) - f(x)| $$ (1) $$ Er{r_{{\mathrm{rel}}}}(f(x), {f_r}(x)) = \left|\frac{{{f_r}(x) - f(x)}}{{{f_r}(x)}}\right| $$ (2) 由于浮点舍入误差的存在, 浮点运算并不满足实数运算的相关优化理论, 因此编译器的激进优化会改变浮点计算行为, 例如常用的-ffast-math优化选项; Intel科技报告[1]中专门介绍了ICC编译器各种编译优化选项可能导致的结果差异性. 需要特别指出的是相同的编译选项在不同编译器中的优化含义有可能不同, 例如-O3选项在IBM XLC编译器中会执行IEEE-754不安全的优化遍, 而在GCC编译器中则不会.
美国劳伦斯利弗莫尔国家实验室(LLNL)在使用XLC编译器和-O3选项编译运行流体动力学应用Laghos (https://github.com/CEED/Laghos)时产生了明显不一致的能量计算结果, 开发人员耗费了大量的精力来分析汇编代码查找-O3选项产生结果不一致性的原因. 图1给出了Laghos应用中提取的触发编译优化结果不一致性的核心代码示例[4]. 当使用XLC编译器基于-O2选项编译运行该示例程序时输出−
1.3507 , 而XLC编译器基于-O3选项编译运行则输出-inf. 通过检查代码生成的汇编代码发现第6行代码中的除法操作在-O3选项下被优化为了求倒数操作和乘法操作. 由于gradv10是一个非规格化浮点数, 2*gradv10求倒数时发生了浮点上溢出异常. 实验室开发人员分析后通过将代码中的浮点变量由double类型提升为long double类型在-O3选项下编译运行也能够产生与-O2一致的能量计算结果.
图 1 Laghos应用中提取的编译优化结果不一致性示例程序
下载:
全尺寸图片
2.2 PLiner编译优化结果差异性定位
高效定位导致编译优化结果差异性的代码对于数值程序的结果可复现性和性能优化具有重要意义, 即开发人员可以仅对定位到的代码片段进行基于精度提升或者表达式重写的浮点精度修复, 使得程序在进行高级别编译优化时仍具有结果的可复现性; PLiner[4]是现有最先进的编译优化结果差异性定位工具, 能够进行语句级问题代码定位.
图2给出了PLiner框架图; PLiner的出发点是浮点表达式在提升为高精度后, 浮点舍入误差问题会极大缓解, 浮点运算行为接近相应的实数运算, 从而避免了激进编译优化对浮点计算行为的影响(忽略特殊的precision-specific操作). 因此, PLiner基于浮点表达式精度增强来不断搜索定位导致编译优化结果不一致性的代码.
图 2 PLiner编译优化结果差异性问题代码定位框架图下载:
全尺寸图片
PLiner的输入包括待分析的程序P、导致计算结果不一致的编译优化选项C1和C2 (假定C2为高级别编译优化选项); PLiner会对程序进行分层二分搜索定位. 首先, 在函数层面会将P中所有函数都定位为可疑代码Plocated; 然后, 调用LLVM优化遍(optimization pass)自动将可疑代码中的浮点操作提升为long double类型, 生成精度增强后的程序Penhanced. 为了便于扩展支持更多的编译器和硬件架构, PLiner在源代码层面做语句精度提升变换; 接着, 会采用激进编译优化选项C2编译运行Penhanced, 如果结果不一致性消失, 则表明问题代码段位于当前定位的可疑代码Plocated内, 会在后续搜索时将Plocated中函数列表均分, 再重复该定位过程, 否则返回最近通过精度提升解决结果不一致性的函数列表. 在定位到问题函数后, PLiner会依次对问题函数内部的循环体、基本块、基本块内的语句依次采用类似的基于精度提升的二分搜索进一步定位, 最终得到导致编译优化结果不一致的问题语句集.
PLiner存在如下3个主要不足.
(1) 缺乏对多源问题代码的定位支持. 假设程序P包含4个函数<func1, func2, func3, func4>且问题代码位于函数func2和func3中. 4个函数都转换为高精度能够修正结果不一致性问题, 二分搜索会将函数列表均分, 而对均分后的两个函数列表<func1, func2>和<func3, func4>分别提升精度均不能修正结果不一致性问题, 最终会导致PLiner返回全部4个函数的列表<func1, func2, func3, func4>, 不能有效精确定位导致结果不一致性的函数func2和func3.
(2) 搜索效率不高. 二分搜索效率依赖函数列表的排序布局, 由于缺乏每个函数浮点计算行为受激进编译优化的影响程度信息, 默认的函数排序会导致问题函数定位效率低. 例如, 假设程序P包含4个函数<func1, func2, func3, func4>且问题代码位于函数func4内, 二分搜索过程中会尝试5次精度增强转换和编译执行才会定位到func4. {<func1>, √}表示提升func1精度成功解决了结果不一致性问题, {<func1>, ×}表示提升func1精度没有解决结果不一致性问题; PLiner对程序P的精度提升定位过程为 {<func1, func2, func3, func4>, √} → {<func1, func2>, ×} → {<func3, func4>, √} → {<func3>, ×} → {<func4>, √}. 而如果列表顺序变为<func4, func1, func2, func3>, 二分搜索过程只需要3次精度增强转换和编译执行即可定位到func4. 精度提升定位过程为{<func4, func1, func2, func3>, √} → {< func4, func1>, √} → {< func4>, √}.
(3) 缺乏对多问题文件的精化搜索支持. 当前PLiner的实现机制中没有很好地支持多文件程序, 其搜索逻辑中没有设计如何对定位到的多个问题代码文件进行精化定位. 考虑到实际浮点应用往往包含多个源代码文件, 从提高工具实用性的角度需要扩展支持多问题文件的精化搜索.
3. 浮点指令差异性引导的Delta-Debugging搜索定位
3.1 方法框架介绍
为了有效应对现有编译优化结果差异性定位工具存在的不足, 本文给出了浮点指令差异性引导的Delta-Debugging搜索定位方法FI3D. FI3D的核心思想是使用Delta-Debugging中的回溯机制实现对多源问题代码定位的支持, 使用函数不同编译选项下浮点指令序列差异性系数来引导搜索进而提升定位效率. 图3给出了FI3D的框架图; FI3D的输入包含待分析程序P (程序输入为了简洁性略去)、编译优化选项C1和C2; Execute(P, C)表示基于选项C编译运行程序P的执行结果. 编译优化结果不一致性是指Execute(P, C1)≠Execute(P, C2). 需要指出的是判定浮点结果一致性会评估两种编译优化模式下运行结果的相对误差是否超过给定的相对误差阈值. 首先, FI3D内部的指令记录优化遍会记录程序P中每个函数funci基于编译优化选项C1和C2生成的浮点指令序列
$ {{t}{r}{a}{c}{e}}_{{i}} $ 和$ {{t}{r}{a}{c}{e}}'_{{i}}{{{}}} $ ; 接着通过指令序列差异性评估模块计算每个函数的浮点指令序列在不同编译选项下的差异性系数, 过滤掉那些不存在差异性的函数, 并将函数按照差异性系数从大到小排列; 最后调用Delta-Debugging搜索模块对输入的函数列表进行搜索定位, 获取导致编译优化结果差异性的代码段.
图 3 FI3D编译优化结果差异性问题代码定位框架图下载:
全尺寸图片
在FI3D的框架中, 浮点指令记录优化遍和浮点指令序列差异性评估模块能够过滤掉那些浮点计算行为没有被激进编译优化改变的文件/函数, 并将浮点计算行为改变程度大的文件/函数放置待搜索文件/函数列表的前部, 这会提升Delta-Debugging搜索定位效率(详情参见第3.2和3.3节); Delta-Debugging搜索引擎中的回溯机制能够很好地解决多源问题代码的定位问题, 内部的精化机制能够不断缩小可疑代码的范围(详情参见第3.3节). 需要特别指出的是Delta-Debugging分层搜索引擎中扩展了对多问题文件的精化定位支持(详情参见第3.4节).
3.2 编译优化浮点指令序列差异性评估
激进编译优化导致程序结果发生改变, 根本原因是改变了程序中的浮点计算行为. 浮点指令序列是浮点计算行为最直接的描述. 浮点计算行为改变程度越大的函数越有可能是导致程序结果发生改变的原因. 无论是二分搜索还是Delta-Debugging, 搜索定位效率与文件/函数的排列顺序有直接关系. 为了提升搜索定位效率, 本文对待搜索文件/函数进行过滤排序.
以函数级为例, 算法1给出了过滤排序过程, 输入包括目标程序P、函数列表flist、编译优化选项C1和C2, 输出包括过滤和排序后的新的函数列表list. 列表list和字典score_dict初始为空. 首先, 分别基于编译优化选项C1和C2在编译程序P时记录每个函数的浮点指令序列(第3, 4行). 需要说明的是本文通过静态扫描函数指令序列的方式来获取函数的浮点指令序列, 并非在运行时检查记录浮点指令. 因为包含循环体的程序动态执行时会产生大量浮点指令, 极大增加浮点指令序列差异性系数的计算开销. 接着, Diff函数会计算每个待搜索函数在不同编译优化选项下的浮点指令序列差异性系数, 并作为该函数的优先级评分(第5行). 差异性为0表示该函数在不同编译优化选项下浮点计算行为未发生改变, 直接过滤掉(第6, 7行). 最后sort(list, score_dict)会按照差异性系数的降序对列表list进行排序(第9行). 函数的差异性系数高意味着该函数的浮点计算行为受高级别编译优化改变的程度大, 将这些函数放置在待定位函数列表的前部, 会被Delta-Debugging优先探索定位.
算法1. 基于浮点指令序列差异性的函数过滤和排序FilterSort(P, flist, C1, C2).
输入: 目标程序P、函数列表flist、编译优化选项C1和C2;
输出: 过滤排序后的待搜索定位函数列表list.
FilterSort(P, flist, C1, C2)
1. list = [], score_dict = {}
2. for func in flist do
3. tf1← compileRecord(P, func, C1)
4. tf2← compileRecord(P, func, C2)
5. score_dict[func] = Diff(tf1, tf2)
6. if score_dict[func] ≠ 0 then
7. list.add(func)
8. end for
9. sort(list, score_dict)
10. return list
下面详细介绍浮点指令差异性系数计算函数Diff. 给定两个浮点指令序列tf1和tf2, 函数Ratio(tf1, tf2)会计算两个浮点指令序列的相似值; Diff(tf1, tf2)=1.0–Ratio(tf1, tf2). Ratio(tf1, tf2)计算基于经典的最长匹配迭代计算策略(https://docs.python.org/3/library/difflib.html#sequencematcher-objects), 具体步骤如下.
(1) 队列QS包含待计算相似值的序列对, 初始为{(tf1, tf2)}. 队列MS存放计算得出的匹配序列, 初始为空队列. 执行步骤2.
(2) 判定QS是否为空, 若为空则跳转执行步骤4; 否则, 从QS中取出一个待匹配指令序列对(t1, t2), Match(t1,t2)会获取t1和t2中的最长匹配序列, 记为ms, 并将ms加入到MS中. 执行步骤3.
(3) ExcludeL(t1, t2, ms)计算序列t1和t2排除掉ms后得到的左侧指令序列, 记录为
$ {{t}}_{1}^{{l}} $ 和$ {{t}}_{2}^{{l}} $ , 若果$ {{t}}_{1}^{{l}} $ 和$ {{t}}_{2}^{{l}} $ 均不为空, 则将$( {{t}}_{1}^{{l}},\; {{t}}_{2}^{{l}} )$ 加入到QS中. 类似的, ExcludeR(t1, t2, ms)计算序列t1和t2排除掉ms后得到的右侧指令序列, 记录为$ {{t}}_{1}^{{r}} $ 和$ {{t}}_{2}^{{r}} $ , 若果$ {{t}}_{1}^{{r}} $ 和$ {{t}}_{2}^{{r}} $ 均不为空, 则将$ ({{t}}_{1}^{{r}}, \;{{t}}_{2}^{{r}}) $ 加入到QS中. 跳转至步骤2.(4) 计算MS中所有指令序列的长度和, 记为M. 计算tf1和tf2的指令长度和, 记为T; Ratio(tf1, tf2)=2×M/T.
假定存在两个浮点指令序列tf1=<fsub, fadd, fma, fmov, fdiv, fmul>, tf2=<fadd, fma, fdiv, fmul>. 首先计算得出最长匹配序列为<fadd, fma>加入到MS中, 此时
$ {{t}}_{1}^{{l}} $ =<fsub>,$ {{t}}_{2}^{{l}} $ =<>,$ {{t}}_{1}^{{r}} $ =<fmov, fdiv, fmul>,$ {{t}}_{2}^{{r}} $ =<fdiv, fmul>. 因为$ {{t}}_{1}^{{r}} $ 和$ {{t}}_{2}^{{r}} $ 均非空, 故将$( {{t}}_{1}^{{r}}, \;{{t}}_{2}^{{r}}) $ 加入到QS中; 接着从QS取出待计算匹配对(<fmov, fdiv, fmul>, <fdiv, fmul>), 得出最长匹配对<fdiv, fmul>, 将其加入到MS中, 此时$ {{t}}_{1}^{{l}} $ =<fmov>,$ {{t}}_{2}^{{l}} $ =<>,$ {{t}}_{1}^{{r}} $ =<>,$ {{t}}_{2}^{{r}} $ =<>, 因此QS不会再加入新的待计算匹配对并变为空. 最终MS={<fadd, fma>, <fdiv, fmul>}, 其所有序列的长度和M为4, tf1和tf2的指令长度和为10, 因此Ratio(tf1, tf2)=2×4/10=0.8. 计算得到相似值Ratio后, 差异值Diff(tf1, tf2)=1.0–Ratio(tf1, tf2)=0.2.3.3 基于Delta-Debugging的编译优化结果不一致性搜索定位
Delta-Debugging[11]由Zeller教授提出, 用于在软件迭代开发过程中精确定位导致测试用例测试失效的代码改动位置. 搜索配置是一组代码改动位置的集合, Delta-Debugging假定搜索配置满足单调性(若配置c导致了测试失效则任何包含c的配置都会导致测试失效)、无歧义性(若配置
$ {{c}}_{1} $ 和$ {{c}}_{2} $ 均能导致测试失效则$ {{c}}_{1} $ ∧$ {{c}}_{2} $ 也能导致失效, 即要求产生失效的改动集是唯一的)和一致性(任何配置的测试结果是确定的, 即通过或失效).给定原始程序P和对P进行代码改动的位置集合{l1, l2,…, ln}更新后测试失效. Delta-Debugging调试DD(P, {l1, l1,…, ln})会返回导致测试失效的最小代码改动位置集合. 如果n=1则返回l1. 否则令
$ {{P}}_{1} $ ← P⊕{l1,…, ln/2},$ {{P}}_{2} $ ←P⊕{ln/2+1,…, ln}, 其中⊕表示代码合并. 如果$ {{P}}_{1} $ 测试失效返回DD(P, {l1,…, ln/2}), 如果$ {{P}}_{2} $ 测试失效返回DD(P, {ln/2+1,…, ln}), 否则返回DD($ {{P}}_{2} $ , {l1,…, ln/2})∪DD($ {{P}}_{1} $ , {ln/2+1,…, ln}). Delta-Debugging本质是一种带回溯的分治搜索过程.本文将Delta-Debugging思想移植应用到导致编译优化结果差异性的问题代码定位上. 搜索过程仍然是沿用PLiner的分层搜索, 即先定位问题文件、函数列表, 再依次定位函数内部的循环、基本块和语句. 为了简洁性, 本文以函数级的Delta-Debugging搜索为例进行说明.
算法2展示了基于Delta-Debugging的函数级代码定位过程. 算法输入包括程序P、函数列表flist和触发结果不一致性的不同编译选项C1和C2, 这里假定C2为高级别编译优化选项, 输出包括定位是否成功标识和触发编译优化结果不一致性的问题函数列表. 给定函数列表list1和list2, list1∪list2表示将两个列表中的函数序列求并集后生成的函数列表. 函数transform(P, list)会将程序P中在列表list里的函数都提升为高精度, 生成精度提升版程序. 如果在高级别编译优化选项C2下执行所有函数都精度增强后的程序仍然存在结果不一致性则返回定位失败和flist (第2, 3行), 否则基于Delta-Debugging来搜索定位flist中触发结果不一致性的函数.
DDFuncLoc定位是一个递归分治过程. 首先, 如果当前成功修复结果不一致性问题的增强函数列表flist只包含一个函数, 则直接返回true和该列表(第4, 5行). 接着, 函数partition(flist)会将flist中的函数均分成left和right. 如果增强left中的函数精度能解决结果不一致性, 则递归调用DDFuncLoc(P, left, C1, C2)来对left列表继续精化搜索(第7–10行). 类似的, 如果增强right中的函数精度能解决结果不一致性, 则递归调用DDFuncLoc(P, right, C1, C2)来对right列表继续精化搜索(第11–14行). 当列表left和right单独增强精度都不能解决结果不一致性时, 按照Delta-Debugging思路通过回溯递归来搜索定位. 具体而言, 将P中left列表所包含的函数精度增强得到新的代码基准Pleft, 递归调用DDFuncLoc(Pleft, right, C1, C2)来搜索right列表中导致结果不一致性的函数(第16行). 类似的, 将P中right列表所包含的函数精度增强得到新的代码基准Pright, 递归调用DDFuncLoc(Pright, left, C1, C2)来搜索left列表中导致结果不一致性的函数(第17行). 最后, 定位成功情况为左右两侧定位情况的逻辑与flag1∧flag2, 定位结果为左右两侧定位结果的并集list1∪list2 (第18–20行).
算法2. 基于Delta-Debugging的函数级搜索定位算法DDFuncLoc.
输入: 目标程序P、函数列表flist、编译优化选项C1和C2;
输出: 定位是否成功标识、触发编译优化结果差异性的问题函数列表.
DDFuncLoc(P, flist, C1, C2)
1. Penhanced ← transform(P, flist)
2. if Execute(Penhanced, C2) ≠ Execute(P, C1) then
3. return false, flist
4. if size(flist)==1 then
5. return true, flist
6. left, right ← partition(flist)
7. Pleft ← transform(P, left)
8. if Execute(Pleft, C2) == Execute(P, C1) then
9. flag, list = DDFuncLoc(P, left, C1, C2)
10. return flag, list
11. Pright ← transform(P, right)
12. if Execute(Pright, C2) == Execute(P, C1) then
13. flag, list = DDFuncLoc(P, right, C1, C2)
14. return flag, list
15. else
16. flag1, list1 = DDFuncLoc(Pleft, right, C1, C2)
17. flag2, list2 = DDFuncLoc(Pright, left, C1, C2)
18. flag = flag1 ∧ flag2
19. list = list1 ∪ list2
20. return flag, list
回到二分搜索不能有效定位多源问题代码的例子, 即程序P包含4个函数<func1, func2, func3, func4>且问题代码位于函数func2和func3中; Delta-Debugging在判定元组(<func1, func2>, <func3, func4>)和(<func3, func4>, <func1, func2>)不能消除不一致性后, 会回溯递归搜索. 首先, 在增强左侧列表<func1, func2>精度的前提下, 递归搜索右侧列表<func3, func4>. 显然元组(<func1, func2, func3>, <func4>)修复成功, 因此基于左侧精度增强的右侧搜索会返回true和<func3>. 类似的, 在增强右侧列表<func3, func4>精度的前提下, 递归搜索左侧列表<func1, func2>. 显然元组(<func3, func4, func2>, <func1>)修复成功, 因此基于右侧精度增强的左侧搜索会返回true和<func2>. 因此, Delta-Debugging搜索最终会成功返回true和<func2, func3>.
3.4 多文件项目支持
现有最先进编译优化结果不一致性定位工具PLiner不支持多问题文件的精化搜索定位; FI3D在文件层面扩展了Delta-Debugging搜索定位机制. 首先, 基于第3.3节介绍的Delta-Debugging搜索定位到触发结果不一致性的文件列表filelist=<file1, file2,…, filen>. 接着按照如下策略进行每个文件上的精化搜索(i初始取值为0):
(1) 如果i>n跳转执行步骤4, 否则, 精化搜索filei. 对于列表中其他文件filej (j≠i∧1≤j≤n), 首先对其进行备份, 接着如果存在已经定位好的
$ {\mathit{file}}_{{j}}^{{l}} $ , 则使用$ {\mathit{{f}{i}{l}{e}}}_{{j}}^{{l}} $ 替换filej, 否则直接使用filej的高精度版本进行替换.(2) 对filei进行单文件精化搜索定位, 即依次在函数级、循环级、基本块级和语句级依次进行精化搜索, 记录只将filei最终定位的问题语句进行精度提升的文件版本为
$ {\mathit{{f}{i}{l}{e}}}_{{i}}^{{l}} $ .(3) 将文件filej (j≠i ∧ 1≤j≤n)恢复成备份的原始文件, 执行i=i+1并跳转执行步骤1.
(4) 多文件最终的搜索定位结果记录为
$ \{{\mathit{{f}{i}{l}{e}}}_{{i}}^{{l}} $ | 1≤i≤n} ($ {\mathit{{f}{i}{l}{e}}}_{{i}}^{{l}} $ 和filei差异性即为每个文件的定位结果).显然, 多文件精化搜索定位的过程是一个增量式控制变量定位过程, 每次都将当前搜索定位文件外的其他文件替换为针对定位结果进行高精度修复的版本或者完全高精度版本, 然后再对当前文件进行单文件上的精化搜索定位. 实验中选取了多文件用例进行了评测, FI3D成功定位到了多个目标文件中触发编译优化结果不一致性的代码, 显示了本文方法的有效性.
4. 实验分析
4.1 工具实现
本文基于LLVM编译器、Python difflib模块和经典编译优化结果不一致性定位工具PLiner实现了FI3D. 如图4所示, FI3D主要包括3个模块: 不同编译选项下的浮点指令记录模块、浮点指令序列差异性计算模块、基于Delta-Debugging的代码搜索定位模块; FI3D支持用户指定待搜索文件/函数列表, 并且设置差异性系数阈值来过滤待搜索函数/文件(默认情况FI3D会过滤掉差异性系数为0的函数/文件).
图 4 FI3D实现架构下载:
全尺寸图片
(1) 浮点指令记录模块. 本文在LLVM 17.0.1中实现了一个函数优化遍fpids, 该优化遍能够在LLVM IR层面记录每个函数的浮点指令序列. 给定待分析程序P和编译选项C1和C2, 首先调用LLVM中的Clang前端生成不同编译优化选项对应的IR文件(当有多个源代码文件时会基于llvm-link将其链接为一个IR文件). 接着, 使用LLVM中的opt工具调用优化遍fpids解析IR文件, 生成不同编译优化选项下每个函数对应的浮点指令序列.
(2) 浮点指令序列差异性计算模块. 本文基于Python (版本3.8.10) difflib模块的sequenceMatcher类来计算不同函数浮点指令序列的差异性系数; FI3D会过滤掉那些差异性系数为零的文件/函数, 并将文件/函数按照差异性系数降序进行排列.
(3) Delta-Debugging代码搜索定位模块. 本文在PLiner中扩展实现了Delta-Debugging搜索定位机制, 复用了PLiner的语句精度增强变换模块. 此外, 为了提高FI3D的可用性, 在PLiner中扩展了对多问题文件的精化搜索支持, 解决了PLiner不支持单精度浮点类型的问题, 修正了PLiner精度增强变换接口在实现上的一些缺陷(例如PLiner对浮点数组精度增强存在缺陷).
4.2 研究问题
本文实验主要回答如下2个研究问题.
(1) 研究问题1: 本文工具FI3D是否能有效定位触发编译优化结果差异性的代码, 特别是多源问题代码?
(2) 研究问题 2: 本文工具FI3D定位触发编译优化结果差异性的代码是否比当前最先进工具PLiner更高效?
4.3 实验设计
表2给出了实验所使用的测试用例.
表 2 实验程序集程序 #文件/#函数个数 行数 功能简介 CG.A 1/7 1066 共轭梯度不规则存取和通信 (A规模) CG.B 1/7 1066 共轭梯度不规则存取和通信 (B规模) MG.A 1/15 1385 多重网格长、短距离通信 (A规模) SP.A 13/13 3440 标量五对角线求解器 (A规模) SP.B 13/13 3440 标量五对角线求解器 (B规模) LU.A 13/13 3926 下上高斯-赛德尔求解器 (A规模) sin 1/5 286 正弦计算函数 sinc 1/6 351 辛格计算函数 cos 1/5 295 余弦计算函数 dilog 1/8 340 二重对数计算函数 expint_E1 1/6 482 指数积分E1计算函数 expint_E2 1/7 522 指数积分E2计算函数 clausen 1/6 278 克劳森积分计算函数 Ci 1/8 647 余弦积分计算函数 bessel_J1 1/6 335 贝塞尔J1计算函数 bessel_y0 1/6 307 贝塞尔y0计算函数 arclength 1/3 75 弧长计算函数 dft 1/3 86 离散傅里叶变换 总计 54/138 18329 18个开源测试用例 表2的4列分别给出了程序名、程序包含的代码文件/函数个数、程序代码行数和程序功能简介. 我们选取了美国航空航天局NASA推出的高性能计算基准测试集NAS parallel benchmarks (NPB)中的6个应用(涵盖了PLiner使用的CG和SP应用)、开源GNU scientific library (GSL)中能够触发编译优化结果差异性的10个函数和floatsmith混合精度测试集中能够触发编译优化结果差异性的2个程序, 共计
18329 行代码. 其中CG、MG、SP和LU来自NPB测试集, 分别为共轭梯度不规则存取和通信、多重网格长短距离通信、标量五对角线求解器和下上高斯-赛德尔求解器. 需要特别指出的是NPB应用不同规模下的浮点计算行为和结果校验均不同. 函数sin、sinc、cos、dilog、expint_E1、expint_E2、clausen、Ci、bessel_J1和bessel_y0来自GSL数学库中Specfunc类函数, 分别为正弦、辛格、余弦、二重对数、指数积分E1、指数积分E2、克劳森、余弦积分、贝塞尔J1和贝塞尔y0计算函数; arclength和dft来自floatsmith测试集, 分别用于弧长计算和离散傅里叶变换计算. 实验选取的测试用例均为多文件或多函数程序; PLiner实验所使用的其他100个简单合成用例都是数十行代码的单一函数, FI3D可直接定位这些简单用例, 考虑到FI3D是面向实际数值程序的编译优化结果差异性定位, 为了简洁性, 未在实验中列出这些简单函数的定位情况.实验基于LLVM编译器(版本17.0.1)编译运行测试程序, 触发测试用例结果不一致性的基础编译优化选项和激进编译优化选项分别为-O0和-O3 -ffast-math. 因为-O0是最基础的编译选项, 会关闭几乎全部编译优化策略, 能够最直接反映程序计算行为, 而-O3 -ffast-math是开发人员最常用的激进编译优化选项, 会开启绝大部分浮点激进编译优化(例如-freciprocal-math和-fassociative-math等). -O0和-O3 -ffast-math便于触发编译优化结果不一致性来评测FI3D; PLiner实验中也是选取了该组编译选项来进行实验.
NPB程序和GSL函数结果不一致性的定义如下.
(1) NPB程序: NPB程序运行结束后会将计算结果与预存的标准结果进行校验, 如果相对误差不超过给定阈值则输出successful, 否则输出fail. 因此, NPB程序编译优化结果不一致性是指-O0选项下编译运行程序结果校验为successful, 而-O3 -ffast-math选项下编译运行结果校验为fail; NPB程序内部为不同规模定义了对应的输入和标准计算结果. 为了更好地评估FI3D的有效性, 与PLiner类似, 本文调整了NPB程序的相对误差阈值, 使得-O0和-O3 -ffast-math两组选项能够产生结果不一致性. 误差阈值的设置是基于二分搜索获取的, 即在误差阈值范围区间内不断二分搜索直到获取的误差阈值能够使得-O0返回successful, 而-O3 -ffast-math返回fail.
(2) GSL函数和floatsmith函数: 实验为这些函数定义了相对误差阈值, 函数的标准结果采用long double模式和-O0编译运行得出并在函数中预存, 当函数运行结果与标准结果的相对误差超过阈值则返回fail, 否则返回successful. 误差阈值的设置策略与NPB类似.
本文实验的硬件运行环境为12代酷睿i7处理器, 拥有16个CPU核心, 主频2.5 GHz. 软件环境为Ubuntu 20.04.6操作系统.
4.4 实验结果
(1) 研究问题1: 有效性
表3给出了编译优化结果不一致性的定位结果, [func1:line1–line2]表示问题代码位于函数func1 中的line1行到line2行. 第2列和第3列分别是PLiner和FI3D的定位结果. FI3D能够有效定位所有程序触发结果不一致性的代码段, 而PLiner则存在4个程序(CG.A、MG.A、dilog和bessel_J1)不能有效精确定位. 不难发现, PLiner定位失败的程序, 触发结果不一致性的问题代码分布在多个函数内, 这也反映了PLiner的二分搜索定位存在的不足和FI3D的Delta-Debugging搜索的有效性. 对于PLiner定位成功的程序, FI3D的定位结果与其一致, 这也反映出了FI3D实现的正确性. 实验发现浮点乘加优化、结合律优化和倒数优化等优化模式容易导致浮点程序结果的不一致性.
表 3 编译优化结果不一致性定位结果Program Localization results Time (s) PLiner FI3D PLiner FI3D Improvement (%) CG.A failed [sparse, sprnvc] NA 8.3 NA CG.B [sparse:741-795] [sparse:741-795] 369.8 256.4 30.7 MG.A failed [resid:499, psinv: 1191 ]NA 76.8 NA SP.A [exact_solution:44] [exact_solution:44] 282.8 184.9 34.6 SP.B [exact_solution:44] [exact_solution:44] 1331.3 847.1 36.4 LU.A [blts:109-197] [blts:109-197] 546.8 445.1 18.6 sin [sin_e:254] [sin_e:254] 2.4 1.9 20.8 sinc [sin_e:319] [sin_e:319] 2.7 2.2 18.5 cos [cos_e:262] [cos_e:262] 2.0 1.5 25.0 dilog failed [xge0:234-245, series_2:195] NA 2.5 NA expint_E1 [expint_E1_impl:419] [expint_E1_impl:419] 3.6 3.1 13.9 expint_E2 [cheb_eval_e:all] [cheb_eval_e:all] 1.5 1 33.3 clausen [angle_res_pos_err_e] [angle_res_pos_err_e] 1.5 0.9 40 Ci [sin_e:601] [sin_e:601] 2.9 2.5 13.8 bessel_J1 failed [cheb_eval_e:216, bessel_J1_e:290] NA 3.9 NA bessel_y0 [cos_e:230] [cos_e:230] 1.9 1.5 21.1 arclength [do_fun] [do_fun] 2.6 1.2 53.8 dft [dft:82] [dft:82] 3.4 2.9 14.7 研究问题1: FI3D能够有效定位NPB应用、GSL数学函数和floatsmith测试程序触发编译优化结果不一致性的代码, 对于PLiner定位失效的4个包含多源问题代码的程序CG.A、MG.A、dilog和bessel_J1, FI3D能够进行有效定位.
(2) 研究问题2: 高效性
浮点指令差异性引导对搜索效率的提升主要来自两个方面原因: 通过过滤计算行为未被编译优化改变的文件/函数来缩小问题代码搜索空间和通过将浮点计算行为改变程度大的文件/函数放置在待定位列表的前部来引导定位优先搜索. 图5给出了每个程序中FI3D基于函数浮点指令差异性分析过滤掉的函数数目所占程序中总的函数个数的比例; FI3D平均能够过滤44.1%的函数, 过滤比例范围为7.7%–66.7%, 这能有效缩小后续Delta-Debugging的搜索空间.
图 5 FI3D过滤函数比例示意图下载:
全尺寸图片
表3中Time列给出了PLiner和FI3D的定位时间开销, Improvement列给出了FI3D对于PLiner的性能提升百分比(PLiner定位时间减去FI3D定位时间再除以PLiner定位时间). 对于 PLiner定位失效的情况, 时间开销和性能提升比例均设置为NA. 对于PLiner定位成功的14个测试用例, FI3D能够获得平均26.8%的性能提升, 性能提升比例范围为13.8%–53.8%. 这有效反映了浮点指令差异性引导对问题代码搜索定位效率提升的作用.
表4给出了每个测试程序中问题函数在所有函数浮点指令差异性系数中的排名, m/n表示问题函数在所有n个函数的浮点指令差异性系数中位于第m位, 多个问题函数使用&连接. 所有程序的问题函数均排在函数指令差异性系数序列的前部, 特别是MG.A、SP.A、SP.B和LU.A, 其问题函数在全部10余个函数中排名前几位. 排名较差的CG和Ci, 其问题函数也位于差异性系数排名的前半部分. 这充分说明基于函数编译优化前后浮点指令序列的差异性系数对待定位文件/函数进行排序, 能够有效引导Delta-Debugging快速定位问题代码.
表 4 问题函数的浮点指令差异性系数排名情况问题函数 排名 问题函数 排名 CG.A 3/7&4/7 dilog 2/8&3/8 CG.B 3/7 expint_E1 2/6 MG.A 3/15&4/15 expint_E2 1/7 SP.A 1/13 clausen 2/6 SP.B 1/13 Ci 4/8 LU.A 2/13 bessel_J1 1/5&3/5 sin 2/5 bessel_y0 2/6 sinc 2/6 arclength 1/3 cos 2/5 dft 1/3 消融实验: 为了进一步评估浮点指令差异性引导对搜索定位的贡献, 本文进一步实验了将浮点指令差异性引导直接作用于PLiner, 记为PLiner+. 图6给出了
$ {\mathrm{P}\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{r}}^{+} $ 相比PLiner在定位成功的14个测试用例上的性能提升情况,$ {\mathrm{P}\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{r}}^{+} $ 能够获得平均21.5%的性能提升. 除了Ci函数外, 其余13个测试用例均能获得性能提升, 提升范围为8.3%–53.8%. 对于Ci函数, 尽管浮点指令差异性过滤掉了3个冗余函数, 但是考虑到其问题函数本身就位于二分搜索容易定位的位置,$ {\mathrm{P}\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{r}}^{+} $ 由于指令差异性分析存在一定的开销, 相比PLiner有1.7%的轻微性能下降. 总体来说, 实验结果显示了浮点指令差异性引导能够有效提升问题代码的搜索定位效率.
图 6 PLiner+相对PLiner的性能提升情况下载:
全尺寸图片
研究问题2: FI3D能够比当前最先进的工具PLiner更高效地定位NPB应用、GSL数学函数和floatsmith测试程序触发编译优化结果不一致性的代码, 且对于PLiner定位成功的14个测试用例, FI3D能够获取平均26.8%的性能提升. 将浮点指令差异性引导直接作用于PLiner, 能够带来平均21.5%的性能提升.
4.5 有效性威胁
FI3D的有效性威胁主要分为外部威胁和内部威胁两类. 外部威胁主要来源是选取的实验对象和对比的编译优化选项有限. 尽管选取了有限的测试用例, NPB测试集是高性能计算领域应用最广泛的性能评测程序集之一, 而GSL数学库则被广泛用于浮点分析工具有效性评测, floatsmith测试集被广泛用于混合精度优化工具评测, 这些程序被广泛用于编译优化相关工具的评测[4,6,27]. 本文所选取的触发编译优化结果不一致性选项为-O0和-O3 -ffast-math, 这是因为-O0会关闭几乎所有编译优化策略, 而-O3 -ffast-math是开发人员使用最广泛的激进编译优化选项, 开启了绝大部分激进编译优化策略, 这组选项能够更好地触发结果不一致性和评测工具定位问题代码的能力; FI3D的内部威胁来自工具的实现正确性, 为了控制内部威胁, FI3D在开发过程中进行了多轮内部正确性测试, 且FI3D实验的结果也都经过了人工验证. 另一方面, FI3D与PLiner在14个测试应用上定位结果的一致性也反映了FI3D实现的正确性.
5. 总 结
激进编译优化会改变程序中的浮点计算行为, 导致计算结果不一致性问题. 本文提出了一种浮点指令序列差异性引导的Delta-Debugging定位方法FI3D, 能够高效定位程序中导致编译优化结果不一致性的代码. 一方面, FI3D基于Delta-Debugging中的回溯搜索机制有效支持了多源问题代码的定位. 另一方面, FI3D利用函数编译优化前后浮点指令序列的差异性过滤掉冗余代码并优先搜索浮点计算行为改变程度高的代码, 提升了问题代码搜索定位效率. 本文基于LLVM编译器、Python difflib模块和编译优化结果不一致性代码定位工具PLiner实现了FI3D, 并基于NPB测试集、GSL数学库和floatsmith测试集中的典型用例进行了评测. 相比当前最先进的工具PLiner, FI3D能够有效定位PLiner失效的4个用例, 且对PLiner成功定位的14个用例FI3D获得了平均26.8%的性能提升. 实验结果显示了FI3D的有效性和高效性. 未来主要工作是将FI3D的分析定位思想移植支持其他开源编译器, 例如GNU编译器GCC等.
-
图 1 Laghos应用中提取的编译优化结果不一致性示例程序
下载:
全尺寸图片
图 2 PLiner编译优化结果差异性问题代码定位框架图
下载:
全尺寸图片
图 3 FI3D编译优化结果差异性问题代码定位框架图
下载:
全尺寸图片
图 4 FI3D实现架构
下载:
全尺寸图片
图 5 FI3D过滤函数比例示意图
下载:
全尺寸图片
图 6 PLiner+相对PLiner的性能提升情况
下载:
全尺寸图片
表 1 IEEE-754浮点编码格式
精度 符号位 阶码 尾数 fp16 1 5 10 float 1 8 23 double 1 11 52 表 2 实验程序集
程序 #文件/#函数个数 行数 功能简介 CG.A 1/7 1066 共轭梯度不规则存取和通信 (A规模) CG.B 1/7 1066 共轭梯度不规则存取和通信 (B规模) MG.A 1/15 1385 多重网格长、短距离通信 (A规模) SP.A 13/13 3440 标量五对角线求解器 (A规模) SP.B 13/13 3440 标量五对角线求解器 (B规模) LU.A 13/13 3926 下上高斯-赛德尔求解器 (A规模) sin 1/5 286 正弦计算函数 sinc 1/6 351 辛格计算函数 cos 1/5 295 余弦计算函数 dilog 1/8 340 二重对数计算函数 expint_E1 1/6 482 指数积分E1计算函数 expint_E2 1/7 522 指数积分E2计算函数 clausen 1/6 278 克劳森积分计算函数 Ci 1/8 647 余弦积分计算函数 bessel_J1 1/6 335 贝塞尔J1计算函数 bessel_y0 1/6 307 贝塞尔y0计算函数 arclength 1/3 75 弧长计算函数 dft 1/3 86 离散傅里叶变换 总计 54/138 18329 18个开源测试用例 表 3 编译优化结果不一致性定位结果
Program Localization results Time (s) PLiner FI3D PLiner FI3D Improvement (%) CG.A failed [sparse, sprnvc] NA 8.3 NA CG.B [sparse:741-795] [sparse:741-795] 369.8 256.4 30.7 MG.A failed [resid:499, psinv: 1191 ]NA 76.8 NA SP.A [exact_solution:44] [exact_solution:44] 282.8 184.9 34.6 SP.B [exact_solution:44] [exact_solution:44] 1331.3 847.1 36.4 LU.A [blts:109-197] [blts:109-197] 546.8 445.1 18.6 sin [sin_e:254] [sin_e:254] 2.4 1.9 20.8 sinc [sin_e:319] [sin_e:319] 2.7 2.2 18.5 cos [cos_e:262] [cos_e:262] 2.0 1.5 25.0 dilog failed [xge0:234-245, series_2:195] NA 2.5 NA expint_E1 [expint_E1_impl:419] [expint_E1_impl:419] 3.6 3.1 13.9 expint_E2 [cheb_eval_e:all] [cheb_eval_e:all] 1.5 1 33.3 clausen [angle_res_pos_err_e] [angle_res_pos_err_e] 1.5 0.9 40 Ci [sin_e:601] [sin_e:601] 2.9 2.5 13.8 bessel_J1 failed [cheb_eval_e:216, bessel_J1_e:290] NA 3.9 NA bessel_y0 [cos_e:230] [cos_e:230] 1.9 1.5 21.1 arclength [do_fun] [do_fun] 2.6 1.2 53.8 dft [dft:82] [dft:82] 3.4 2.9 14.7 表 4 问题函数的浮点指令差异性系数排名情况
问题函数 排名 问题函数 排名 CG.A 3/7&4/7 dilog 2/8&3/8 CG.B 3/7 expint_E1 2/6 MG.A 3/15&4/15 expint_E2 1/7 SP.A 1/13 clausen 2/6 SP.B 1/13 Ci 4/8 LU.A 2/13 bessel_J1 1/5&3/5 sin 2/5 bessel_y0 2/6 sinc 2/6 arclength 1/3 cos 2/5 dft 1/3 -
[1] Corden MJ, Kreitzer D. Consistency of floating-point results using the intel compiler or why doesn’t my application always give the same answer. 2009. https://software.intel.com/sites/default/files/article/164389/fp-consistency-102511.pdf [2] Sawaya G, Bentley M, Briggs I, Gopalakrishnan G, Ahn DH. FLiT: Cross-platform floating-point result-consistency tester and workload. In: Proc. of the 2017 IEEE Int’l Symp. on Workload Characterization. Seattle: IEEE, 2017. 229–238. [doi: 10.1109/IISWC.2017.8167780] [3] Bentley M, Briggs I, Gopalakrishnan G, Ahn DH, Laguna I, Lee GL, Jones HE. Multi-level analysis of compiler-induced variability and performance tradeoffs. In: Proc. of the 28th Int’l Symp. on High-performance Parallel and Distributed Computing. Phoenix: ACM, 2019. 61–72. [doi: 10.1145/3307681.3325960] [4] Guo H, Laguna I, C. Rubio-González. PLiner: Isolating lines of floating-point code for compiler-induced variability. In: Proc. of the 2020 Int’l Conf. for High Performance Computing, Networking, Storage and Analysis. Atlanta: IEEE, 2020. 1–14. [doi: 10.1109/SC41405.2020.00053] [5] Laguna I. Varity: Quantifying floating-point variations in HPC systems through randomized testing. In: Proc. of the 2020 IEEE Int’l Parallel and Distributed Processing Symp. NewOrleans: IEEE, 2020. 622–633. [doi: 10.1109/IPDPS47924.2020.00070] [6] Yu HB, Yi X, Yin BH, Li F, Chen ZB, Huang C. Efficient generation of floating-point inputs for compiler-induced variability. In: Proc. of the 2023 IEEE Int’l Conf. on Software Analysis, Evolution and Reengineering. Macao: IEEE, 2023. 224–235. [doi: 10.1109/SANER56733.2023.00030] [7] Miao D, Laguna I, Rubio-González C. Expression isolation of compiler-induced numerical inconsistencies in heterogeneous code. In: Proc. of the 38th Int’l Conf. on High Performance Computing. Hamburg: Springer, 2023. 381–401. [doi: 10.1007/978-3-031-32041-5_20] [8] Panchekha P, Sanchez-Stern A, Wilcox JR, Tatlock Z. Automatically improving accuracy for floating point expressions. In: Proc. of the 36th ACM SIGPLAN Conf. on Programming Language Design and Implementation. Portland: ACM, 2015. 1–11. [doi: 10.1145/2737924.2737959] [9] Yi X, Chen LQ, Mao XG, Ji T. Efficient automated repair of high floating-point errors in numerical libraries. Proc. of the ACM on Programming Languages, 2019, 3(POPL): 56. [doi: 10.1145/3290369] [10] Zou DM, Gu YC, Shi YF, Wang MZ, Xiong YF, Su ZD. Oracle-free repair synthesis for floating-point programs. Proc. of the ACM on Programming Languages, 2022, 6(OOPSLA2): 159. [doi: 10.1145/3563322] [11] Zeller A. Yesterday, my program worked. Today, it does not. Why? In: Proc. of the 7th European Software Engineering Conf. Held Jointly with the 7th ACM SIGSOFT Symp. on the Foundations of Software Engineering. Toulouse: Springer, 1999. 253–267. [doi: 10.1007/3-540-48166-4_16] [12] Galassi M, Davies J, Theiler J, Gough B, Jungman G, Alken P, Booth M, Rossi F. GNU Scientific Library Reference Manual. 3rd ed., Godalming: Network Theory Ltd., 2009. 1–572. [13] Lam MO, Vanderbruggen T, Menon H, Schordan M. Tool integration for source-level mixed precision. In: Proc. of the 3rd Int’l Workshop on Software Correctness for HPC Applications. Denver: IEEE, 2019. 27–35. [doi: 10.1109/CORRECTNESS49594.2019.00009] [14] Benz F, Hildebrandt A, Hack S. A dynamic program analysis to find floating-point accuracy problems. In: Proc. of the 33rd ACM SIGPLAN Conf. on Programming Language Design and Implementation. Beijing: ACM, 2012. 453–462. [doi: 10.1145/2254064.2254118] [15] Sanchez-Stern A, Panchekha P, Lerner S, Tatlock Z. Finding root causes of floating point error. In: Proc. of the 39th ACM SIGPLAN Conf. on Programming Language Design and Implementation. Philadelphia: ACM, 2018. 256–269. [doi: 10.1145/3192366.3192411] [16] Fousse L, Hanrot G, Lefèvre V, Pélissier P, Zimmermann P. MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans. on Mathematical Software (TOMS), 2007, 33(2): 13–es. [doi: 10.1145/1236463.1236468] [17] Chiang WF, Gopalakrishnan G, Rakamaric Z, Solovyev A. Efficient search for inputs causing high floating-point errors. In: Proc. of the 19th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. Orlando: ACM, 2014. 43–52. [doi: 10.1145/2555243.2555265] [18] Yi X, Chen LQ, Mao XG, Ji T. Efficient global search for inputs triggering high floating-point inaccuracies. In: Proc. of the 24th Asia-Pacific Software Engineering Conf. Nanjing: IEEE, 2017. 11–20. [doi: 10.1109/APSEC.2017.7] [19] Zou DM, Wang R, Xiong YF, Zhang L, Su ZD, Mei H. A genetic algorithm for detecting significant floating-point inaccuracies. In: Proc. of the 37th IEEE/ACM Int’l Conf. on Software Engineering. Florence: IEEE, 2015. 529–539. [doi: 10.1109/ICSE.2015.70] [20] Guo H, Rubio-González C. Efficient generation of error-inducing floating-point inputs via symbolic execution. In: Proc. of the 42nd Int’l Conf. on Software Engineering. Seoul: IEEE, 2020. 1261–1272. [doi: 10.1145/3377811.3380359] [21] Cadar C, Dunbar D, Engler D. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In: Proc. of the 8th USENIX Conf. on Operating Systems Design and Implementation. San Diego: USENIX Association, 2008. 209–224. [22] Kaas RE, Carlin BP, Gelman A, Neal RM. Markov chain Monte Carlo in practice: A roundtable discussion. The American Statistician, 1998, 52(2): 93–100. [doi: 10.1080/00031305.1998.10480547] [23] Miao D, Laguna I, Rubio-González C. Input range generation for compiler-induced numerical inconsistencies. In: Proc. of the 38th ACM Int’l Conf. on Supercomputing. Kyoto: ACM, 2024. 201–212. [doi: 10.1145/3650200.3656618] [24] Ren XL, Ho M, Ming J, Lei Y, Li L. Unleashing the hidden power of compiler optimization on binary code difference: An empirical study. In: Proc. of the 42nd ACM SIGPLAN Int’l Conf. on Programming Language Design and Implementation. ACM, 2021. 142–157. [doi: 10.1145/3453483.3454035] [25] Wang R, Zou DM, He XR, Xiong YF, Zhang L, Huang G. Detecting and fixing precision-specific operations for measuring floating-point errors. In: Proc. of the 24th ACM SIGSOFT Int’l Symp. on Foundations of Software Engineering. Seattle: ACM, 2016. 619–630. [doi: 10.1145/2950290.2950355] [26] IEEE. IEEE Std 754-2019 IEEE standard for floating-point arithmetic. 2019. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8766229 [doi: 10.1109/IEEESTD.2019.8766229] [27] Zhou H, Xue JL. Exploiting mixed SIMD parallelism by reducing data reorganization overhead. In: Proc. of the 2016 Int’l Symp. on Code Generation and Optimization. Barcelona: ACM, 2016. 59–69. [doi: 10.1145/2854038.2854054]
