计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (6A): 240800070-8.doi: 10.11896/jsjkx.240800070

• 计算机软件&体系架构 • 上一篇    下一篇

CNFED:一种基于条件数的浮点表达式误差检测工具

王盼龙1, 王磊1, 英津瑞1, 刘博文1, 高志勇2   

  1. 1 中原工学院网络空间安全学院 郑州 450007
    2 郑州大学计算机与人工智能学院、软件学院 郑州 450001
  • 出版日期:2025-06-16 发布日期:2025-06-12
  • 通讯作者: 王磊(pl_wang2024@163.com)
  • 作者简介:(qq541701501@163.com)
  • 基金资助:
    基于高性能计算的基础数学库软件研发(22001742)

CNFED:An Error Detection Tool for Floating-point Expressions Based on Condition Number

WANG Panlong1, WANG Lei1, YING Jinrui1, LIU Bowen1, GAO Zhiyong2   

  1. 1 School of Cyberspace Security,Zhongyuan University of Technology,Zhengzhou 450007,China
    2 School of Computer and Artificial Intelligence,School of Software,Zhengzhou University,Zhengzhou 450001,China
  • Online:2025-06-16 Published:2025-06-12
  • About author:WANG Panlong,born in 2000,postgra-duate.His main research interests include high performance computing and so on.
    WANG Lei,born in 1977,professor,is a member of CCF(No.12516M).His main research interests include research and development of highperformance computing and domestic independent and controlable basic software.
  • Supported by:
    Research and Development of Basic Mathematical Library Software Based on High-Performance Computing(22001742).

PDF (PC)

83

摘要： 浮点数使用有限的精度来表示实数,其固有的舍入误差会在计算过程中累积,可能导致严重错误,从而危及程序的安全性和可靠性。理论上,最精准的浮点误差检测方法是穷举搜索所有可能的浮点数输入,以确定实际计算结果与理论值之间的最大误差,但搜索空间巨大,因此有效且高效地检测最大浮点误差一直是一个挑战。基于对条件数的研究,设计并实现了一种用于浮点表达式的误差检测工具CNFED。CNFED将输入区间划分成多个子区间,对每个子区间进行随机采样和评估,快速定位多个热点子区间;然后分层对这些热点子区间调用全局搜索算法和局部搜索算法,并结合相应评估函数进行筛选,最终找到可能的浮点误差极大值及相应的输入值并报告。实验选取FPBench标准测试集中26个表达式作为测试用例,并与先进检测工具ATOMU和HSED进行了比较。实验结果表明,CNFED 检测效果优于 ATOMU 的比例为 96.15%(25/26)。与针对浮点表达式的检测工具HSED相比,CNFED 检测效果优于 HSED 的比例为 34.62%(9/26),同时HSED所花平均时间是CNFED的4.8倍。

关键词: 误差检测, 浮点运算, 条件数, 动态分析, 分层搜索

Abstract: Floating-point numbers use finite precision to represent real numbers,and their inherent rounding errors can accumulate during calculations,potentially leading to serious errors that jeopardize program safety and reliability.Theoretically,the most precise method for detecting floating-point errors is exhaustive search of all possible floating-point inputs to determine the maximum error between actual computation results and theoretical values.However,the search space is enormous.Effectively and efficiently detecting maximum floating-point errors has been a challenge.Based on the study on condition numbers,a tool for floating-point expression error detection,CNFED,has been designed and implemented.CNFED divides the input interval into multiple sub-intervals,conducts random sampling and evaluation for each sub-interval to quickly locate multiple hotspot sub-intervals.It then hierarchically applies global and local search algorithms to these hotspot sub-intervals,using corresponding evaluation functions for filtering,ultimately identifying potential maximum floating-point errors and reporting the corresponding input values.Experiment selects 26 expressions from the FPBench standard test suite as test cases and compare CNFED with advanced detection tools ATOMU and HSED.The experimental results indicate that CNFED outperforms ATOMU in 96.15% of cases(25/26).Compared to the detection tool HSED for floating-point expressions,CNFED surpasses HSED in 34.62% of cases(9/26),while the average time taken by HSED is 4.8 times that of CNFED.

Key words: Error detection, Floating-point arithmetic, Condition number, Dynamic analysis, Hierarchical search

中图分类号: 

  • TP311
[1]XIAO A X,ZHANG S X,TANG E Y,et al.An empirical library-guided floating-point program optimization acceleration strategy [J].Chinese Journal of Computers,2022,45(9):2014-2028.
[2]HAO J W,YANG H R,XIA Y Y,et al.A floating point expression precision optimization method based on multiple types of computation rewriting [J].Computer Science,2024,51(4):86-94.
[3]NETHERCOTE N,SEWARD J.Valgrind:a framework forheavy weight dynamic binary ins-trumentation[J].SIGPLAN Not,2007,42(6):89-100.
[4]BENZ F,HILDEBRANDT A,HACK S.2012.A dynamic program analysis to find floating-point accuracy problems[J].SIGPLAN Not,2012,47(6):453-462.
[5]ZOU D,WANG R,XIONG Y,et al.AG-enetic Algorithm forDetecting Significant Floating-Point Inaccuracies[C]//2015 IEEE/ACM 37th IEEE International Conference on Software Engineering.Florence,Italy,2015:529-539.
[6]SANCHEZ-STERN A,PANCHEKHA P,LERNER S,et al.Finding root causes of floating point error[C]//Proceedings of the 39th ACMSIGPLAN Conference on Programming Language Design and Implementation(PLDI 2018).Association for Computing Machinery,New York,NY,USA,2018:256-269.
[7]PANCHEKHA P,SANCHEZ-STERN A,WILCOX J R,et al.Automatically improving accuracy for floating point expressions[J].SIGPLAN Not,2015,50(6):1-11.
[8]ZOU D,ZENG M,XIONG Y,et al.Detecting floating-point errors via atomic conditions[C]//Proceedings of the ACM on Programming Languages(POPL).2020.
[9]CHIANG W F,GOPALAKRISHNAN G,RAKAMARIC Z,et al.Efficient search for inputs causing high floating-point errors[J].SIGPLAN Not,2014,49(8):43-52.
[10]YI X,CHEN L,MAO X,et al.Efficient automated repair of high floating-point errorsin numerical libraries[C]//Proceedings of the ACM on Programming Languages(POPL).2019.
[11]WANG Z,YI X,YU H,et al.Detecting High Floating-Point Errors via Ranking Analysis[C]//2022 29th Asia-Pacific Software Engineering Conference(APSEC).Japan,2022:397-406.
[12]ZHANG Z,XU J,HAO J,et al.Hierarchical search algorithm for error detection in floating-point arithmetic expressions[J].J Super Comput,2024,80:1183-1205.
[13]COUSOT P,COUSOT R..Abstract interpretation:past,pre-sent and future[C]//Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic(CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science(LICS)(CSL-LICS’14).Association for Computing Machinery,New York,NY,USA,2004:1-10.
[14]HICKEY T,JU Q,VAN EMDEN M H.Interval arithmetic:From principles to implementation[J].J.ACM,2001,48(5):1038-1068.
[15]BALDONI R,COPPA E,D’ELIA D C,et al.A Survey of Symbolic Execution Techniques[C]//ACM Computing Surveys.2018:39.
[16]IEEE Computer Society.IEEE Standard for Floating-PointArithmetic:IEEE Std 754-2008[S].Piscataway,NJ:IEEE,2008:1-70.
[17]LEE W,SHARMA R,AIKEN A.On automatically proving the correctness of math.h implementations[C]// Proc.ACM Program.Lang.,2017:247:1-47:32.
[18]GOLDBERG D.What every computer scientist should knowabout floating-point arithmetic[J]ACM Computing Surveys,1991,23(1):5-48.
[19]HIGHAM N J.Accuracy and stability of numerical algorithms(2.ed.)[M].SIAM,2002.
[20]KLINE M.Calculus:an intuitive and physical approach[J].Courier Corporation,1998.
[21]FU Z,BAI Z,SU Z.Automated back ward error analysis for nu-merical code[J].SIGPLAN Not.,2015,50(10):639-654.
[22]BAO T,ZHANG X.On-the-fly detectionofinstability problems in floating-point program execution[C]//Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &Applications(OOPSLA).2013:817-832.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发