Computer Science ›› 2025, Vol. 52 ›› Issue (9): 152-159.doi: 10.11896/jsjkx.240800018

• High Performance Computing • Previous Articles     Next Articles

Maximum Error Parallel Detection Method Based on Locality Principle

JI Liguang, YANG Hongru, ZHOU Yuchang, CUI Mengqi, HE Haotian, XU Jinchen   

  1. School of Cyberspace Security,University of Information Engineering,Zhengzhou 450001,China
  • Received:2024-08-05 Revised:2024-10-16 Online:2025-09-15 Published:2025-09-11
  • About author:JI Liguang,born in 1992,master.His main research interests includes high-performance computing.
    XU Jinchen,born in 1987,Ph.D,associate professor.His main research interests includes high-performance computing.

Abstract: Floating-point numbers use a finite number of digits to represent infinite real numbers for computation,so floating-point computation is inherently inaccurate,which can be measured by the maximum error.The traditional floating-point maximum error detection algorithm uses serial computing thinking combined with classical search algorithm.When the number of sampling points is small,it is easy to treat the local maximum as the global maximum,thus omitting the maximum error value.If the number of sampling points is increased on a large scale,the time of the detection program will be greatly increased and the perfor-mance will be reduced.In this paper,the parallel computing mode is used to exponentially increase the number of sampling points,and the floating-point dynamic sampling strategy is used to near the error hot spot in combination with the principle of synchronization and locality,which greatly improves the accuracy of the detection results.This method can maximize the computing power of parallel computing,which can not only improves the detection accuracy of the maximum error of floating-point number calculation,but also reduces the execution time of the detection program and improves the performance,and the acceleration ratio can reach 1 136.3.The maximum error value detected is better than the current mainstream detection tools,which provides a new detection method for measuring the floating-point number calculation index.

Key words: Floating point arithmetic, Parallel optimization, Interval sampling, Error detection, Sunway heterogeneous architecture

CLC Number: 

  • TP314
[1]KOTIPALLI P V,SINGH R,WOOD P,et al.AMPT-GA:Automatic Mixed Precision Floating Point Tuning for GPU Applications[C]//Proceedings of the ACM International Conference on Supercomputing.New York:ACM,2019:160-170.
[2]DAMOUCHE N,MARTEL M.Salsa:An Automatic Tool toImprove the Numerical Accuracy of Programs[J].Automated Formal Methods,2018,5:63-76.
[3]SANCHEZ-STERN A,PANCHEKHA P,LERNER S,et al.Finding Root Causes of Floating-Point Error[C]//Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation.ACM,2018:256-269.
[4]GUO H,RUBIO-GONZÁLEZ C.Exploiting Community Structure for Floating-Point Precision Tuning[C]//Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis.New York:ACM,2018:333-343.
[5]SAIKI B,FLATT O,NANDI C,et al.Combining Precision Tuning and Rewriting[C]//2021 IEEE 28th Symposium on Computer Arithmetic(ARITH).2021:1-8.
[6]MAGRON V,CONSTANTINIDES G,DONALDSON A.Certified Roundoff Error Bounds Using Semidefinite Programming[J].ACM Transactions on Mathematical Software,2017,43(4):34.
[7]DARULOVA E,HORN E,SHARMA S.Sound Mixed-Precision Optimization with Rewriting[C]//Proceedings of the 9th ACM/IEEE International Conference on Cyber-Physical Systems.2018:208-219.
[8]YI X,CHEN L Q,MAO X G,et al.Efficient automated repair of high floating-point errors in numerical libraries[C]//Proceedings of the ACM on Programming Languages.2019:1-29.
[9]CHIANG W F,GOPALAKRISHNAN G,RAKAMARIC Z,et al.Efficient search for inputs causing high floating-point errors[J].ACM SIGPLAN Notices,2014,49(8):43-52.
[10]ZOUD,ZENG M,XIONG Y,et al.Detecting floating-point errors via atomic conditions[C]//Proceedings of the ACM on Programming Languages.2019:1-27.
[11]PANCHEKHA P,SANCHEZ-STERN A,WILCOX J R,et al.Automatically improving accuracy for floating point expressions[J].ACM SIGPLAN Notices,2015,50(6):1-11.
[12]WAGNER J,NISSAN M I,RASIN A.Database memory forensics:Identifying cache patterns for log verification[J].Forensic Science International:Digital Investigation,2023,45(S):301567.
[13]MENON H,LAM M O,OSEI-KUFFUOR D,et al.ADAPT:Algorithmic Differentiation Applied to Floating-Point Precision Tuning[C]//International Conference for High Performance Computing,Networking,Storage and Analysis.IEEE,2018.
[14]LIUX,GUO H,SUN R J,et al.Large-scale Application Characteristics Analysis and E-level Scalability Research of “Shenwei Taihu Light” computer system[J].Journal of Computer Science,2018,41(10):2209-2220.
[15]SOLOVYEV A,JACOBSEN C,RAKAMARIĆ Z,et al.Rigorous Estimation of Floating-Point Round-off Errors with Symbolic Taylor Expansions[C]//Proceeding in 20th International Symposium on Formal Methods.New York:ACM,2015:532-550.
[16]CHIANG W F,BARANOWSKI M,BRIGGS I,et al.Rigorous floating-point mixed-precision tuning[C]//Symposium on Principles of Programming Languages.New York:ACM,2017:300-315.
[17]IZYCHEVA A,DARULOVA E.On Sound Relative ErrorBounds for Floating-Point Arithmetic[C]//2017 Formal Methods in Computer Aided Design.IEEE,2017:15-22.
[18]CHERUBIN S,CATTANEO D,CHIARI M,et al.TAFFO:Tuning Assistant for Floating to Fixed Point Optimization[J].IEEE Embedded Systems Letters,2020,12(1):5-8.
[19]CATTANEO D,BELLO A D,CHERUBIN S,et al.Embedded Operating System Optimization through Floating to Fixed Point Compiler Transformation[C]//21st Euromicro Conference on Digital System Design.IEEE,2018:172-176.
[20]ZHANG Z Y,XU J C,HAO J W,et al.Hierarchical search algorithm for error detection in floating-point arithmetic expressions[J].Supercomput,2023,80:1183-1205.
[21]DENIS C,CASTRO P D O,PETIT E.Verificarlo:CheckingFloating Point Accuracy through Monte Carlo Arithmetic[C]//2016 IEEE 23nd Symposium on Computer Arithmetic(ARITH).IEEE,2016:55-62.
[1] WANG Panlong, WANG Lei, YING Jinrui, LIU Bowen, GAO Zhiyong. CNFED:An Error Detection Tool for Floating-point Expressions Based on Condition Number [J]. Computer Science, 2025, 52(6A): 240800070-8.
[2] HUANG Lulu, TANG Shuyu, ZHANG Wei, DAI Xiangguang. Non-negative Matrix Factorization Parallel Optimization Algorithm Based on Lp-norm [J]. Computer Science, 2024, 51(2): 100-106.
[3] ZHANG Zhou, ZHU Jun-guo, YU Zheng-tao. Incorporating Part of Speech and Tonal Features for Vietnamese Grammatical Error Detection [J]. Computer Science, 2022, 49(11): 221-227.
[4] LV Xiao-jing, LIU Zhao, CHU Xue-sen, SHI Shu-peng, MENG Hong-song, HUANG Zhen-chun. Extreme-scale Simulation Based LBM Computing Fluid Dynamics Simulations [J]. Computer Science, 2020, 47(4): 13-17.
[5] WEI Lin-jing, NING Lu-lu, GUO Bin, HOU Zhen-xing, GAN Shi-run. K-mediods Cluster Mining and Parallel Optimization Based on Shuffled Frog Leaping Algorithm [J]. Computer Science, 2020, 47(10): 126-129.
[6] YANG Si-yan,HE Guo-qi,LIU Ru-yi. Video Stitching Algorithm Based on SIFT and Its Optimization [J]. Computer Science, 2019, 46(7): 286-291.
[7] KE Cheng-song, WU Wen-yuan, FENG Yong. Low Expansion Rate Encryption Algorithm Based on MLWE [J]. Computer Science, 2019, 46(4): 144-150.
[8] LIU Yu-cheng, Richard·DING, ZHANG Ying-chao. Research on Pan-real-time Problem of Medical Detection Based on BPNNs Recognition Algorithm [J]. Computer Science, 2018, 45(6): 301-307.
[9] JIN Xin, LI Long-wei, SU Guo-hua, LIU Xiao-lei and JI Jia-nan. Prediction about Network Security Situation of Electric Power Telecommunication Based on Spark Framework and PSO Algorithm [J]. Computer Science, 2017, 44(Z6): 366-371.
[10] JIANG Wen-chao, LIN Sui, WANG Duo-qiang, LI Dong-ming and JIN Hai. Three-level Parallel Optimization and Application of Calculix in TH-2 Super-computing Environments [J]. Computer Science, 2017, 44(3): 32-35.
[11] ZHANG Guang-mei and LI Jing-xia. Data-flow Analysis for Software Error Detection [J]. Computer Science, 2016, 43(Z6): 497-501.
[12] LI Shu-Hai WANG Yu-Min (State Key Lab. of Integrated Service Networks, Xidian Univ. , Xi'an 710071). [J]. Computer Science, 2008, 35(1): 75-76.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!