计算机科学 ›› 2024, Vol. 51 ›› Issue (4): 86-94.doi: 10.11896/jsjkx.221200072
郝江伟1,2, 杨鸿儒1,2, 夏媛媛3, 刘毅1,2, 许瑾晨1,2, 庞建民1,2
HAO Jiangwei1,2, YANG Hongru1,2, XIA Yuanyuan3, LIU Yi1,2, XU Jinchen1,2 , PANG Jianmin1,2
摘要： 表达式重写是精度优化领域的新兴方法,其核心思想是在不改变表达式精度类型的前提下,将其变换为语义上等价的表达式以尝试提升精度。然而,面对庞大的变换规则和变换空间,如何选取合适的变换策略成为了重写方法的问题所在。针对上述问题,提出了一个基于多类型计算重写的浮点表达式精度优化方法,支持包括函数计算、四则运算的表达式,并实现了表达式重写工具exprAuto。区别于其他精度优化工具侧重于对子表达式的替换,exprAuto更注重对表达式运算顺序的变换。exprAuto在对表达式化简和数学变换后,通过多项式变换获取不同的计算顺序,并尝试减少运算次数以提升精度,最终生成一个包含不同计算顺序的等价表达式集合,通过排序筛选和误差检测从中选出最终的精度优化结果。文中选取41个FPBench标准集中的表达式和18个常见数学函数的近似多项式作为测试用例,在经exprAuto优化后,所提方法相比原式最大误差降低了45.92%,平均误差降低了34.98%;针对其中的18个近似多项式,相比原式最大误差降低了58.35%,平均误差降低了43.73%。实验结果表明,exprAuto可以有效提升表达式尤其是多项式的精度。
中图分类号:
| [1]YI X.Research on Automated Repair Techniques[D].Changsha:National University of Defense Technology,2020. [2]BENZ F,HILDEBRANDT A,HACK S.A Dynamic ProgramAnalysis to Find Floating-Point Accuracy Problems[C]// Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation.Association for Computing Machinery,2012,47(6):453-462. [3]DAMOUCHE N,MARTEL M,PANCHEKHA P,et al.To-ward a Standard Benchmark Format and Suite for Floating-Point Analysis[C]// International Workshop on Numerical Software Verification.2016. [4]MULLER J M,BRISEBARRE N,DINECHIN F D,et al.Handbook of Floating-point Arithmetic[M].Birkhäuser,2009. [5]GOLDBERG D.What Every Computer Scientist Should Know About Floating-point Arithmetic [J].ACM Computer Surveys,1991,23(1):5-48. [6]FOUSSE L,HANROT G,LEFEVRE V,et al.MPFR:A Multiple-Precision Binary Floating-Point Library with Correct Rounding [J].ACM Transactions on Mathematical Software,2007,33(2):13.1-13.15. [7]ANSI/IEEE 754-2019.IEEE Standard for Floating-Point Arithmetic[S].Institute of Electrical and Electronics Engineers,2019. [8]BACKUS J W,BAUER F L,GREENJ,et al.Revised Report on the Algorithmic Language Algol 60[EB/OL].https://www.masswerk.at/algol60/report.htm. [9]HAMMING R W.Numerical Methods for Scientists and Engineers [M].Dover Publications,2nd edition,1987. [10]AHO A V,LAM M S,SETHI R,et al.Compilers:Principles,Techniques,and Tools(2nd Edition)[M].Addison-Wesley Longman Publishing Co.Inc.,2006. [11]PANCHEKHA P,SANCHEZ-STERN A,WILCOX J R,et al.Automatically Improving Accuracy for Floating Point Expressions[J].ACM SIGPLAN Notices.Association for Computing Machinery,2015,50(6):1-11. [12]LI Z,DONG X X,HUANG C C,et al.Design space exploration method for floating-point expression based on heuristic search[J].Journal of Computer Applications,2020,40(9):2665-2669. [13]XIAO A X,ZHANG S X,TANG E Y,et al.An Experience-Guided Acceleration Strategy for Floating-Point Optimization[J].Chinese Journal of Computers,2022,45(9):2014-2028. [14]WANG X,WANG H J,SU Z D,et al.Global Optimization of Numerical Programs via Prioritized Stochastic Algebraic Transformations[C]//Proceedings of the 41st International Confe-rence on Software Engineering(Montreal,Quebec,Canada)(ICSE' 19).IEEE Press,2019:1131-1141. [15]ROBERT R,ANASTASIIA I,EVA D.Regime Inference forSound Floating-Point Optimizations [J].ACM Trans.Embed Computing System,2021,20(5):1-23. [16]YI X,CHEN L Q,MAO X G,et al.Automated Repair of High Inaccuracies in Numerical Programs[C]//IEEE International Conference on Software Maintenance & Evolution.IEEE Computer Society,2017. [17]HIDA Y,LI X S,BAILEY D H.Algorithms for quad-doubleprecision floating point arithmetic [C]//Proceedings of the 15th Symposium on Computer Arithmetic.San Diego,CA,2001:155-162. [18]LAUTER C.Basic building blocks for a triple-double interme-diate format,200538 [R].2005. [19]DARAMY L C,DEFOUR D,DINECHIN F D,et al.CR-LIBM A library of correctly rounded elementary functions in double-precision.Research Report,ensl-01529804 [R].Paris:LIP,2006. |
|
||
首页