More Web Proxy on the site http://driver.im/

research-article

Open access

Efficient automated repair of high floating-point errors in numerical libraries

Authors:

Tao JiAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 3, Issue POPL

Article No.: 56, Pages 1 - 29

https://doi.org/10.1145/3290369

Published: 02 January 2019 Publication History

Abstract

Floating point computation is by nature inexact, and numerical libraries that intensively involve floating-point computations may encounter high floating-point errors. Due to the wide use of numerical libraries, it is highly desired to reduce high floating-point errors in them. Using higher precision will degrade performance and may also introduce extra errors for certain precision-specific operations in numerical libraries. Using mathematical rewriting that mostly focuses on rearranging floating-point expressions or taking Taylor expansions may not fit for reducing high floating-point errors evoked by ill-conditioned problems that are in the nature of the mathematical feature of many numerical programs in numerical libraries.

In this paper, we propose a novel approach for efficient automated repair of high floating-point errors in numerical libraries. Our main idea is to make use of the mathematical feature of a numerical program for detecting and reducing high floating-point errors. The key components include a detecting method based on two algorithms for detecting high floating-point errors and a repair method for deriving an approximation of a mathematical function to generate patch to satisfy a given repair criterion. We implement our approach by constructing a new tool called AutoRNP. Our experiments are conducted on 20 numerical programs in GNU Scientific Library (GSL). Experimental results show that our approach can efficiently repair (with 100% accuracy over all randomly sampled points) high floating-point errors for 19 of the 20 numerical programs.

Supplementary Material

WEBM File (a56-yi.webm)

Download
101.24 MB

References

[1]

Milton Abramowitz. 1974. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,. Dover Publications, Inc., New York, NY, USA.

Digital Library

[2]

Christophe Andrieu, Nando de Freitas, Arnaud Doucet, and Michael I. Jordan. 2003. An Introduction to MCMC for Machine Learning. Machine Learning 50, 1 (01 Jan 2003), 5–43.

[3]

Tao Bao and Xiangyu Zhang. 2013. On-the-fly Detection of Instability Problems in Floating-point Program Execution. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages &#38; Applications (OOPSLA ’13). ACM, New York, NY, USA, 817–832.

Digital Library

[4]

Florian Benz, Andreas Hildebrandt, and Sebastian Hack. 2012. A Dynamic Program Analysis to Find Floating-point Accuracy Problems. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’12). ACM, New York, NY, USA, 453–462.

Digital Library

[5]

Florian Cajori. 1911. Horner’s method of approximation anticipated by Ruffini. Bull. Amer. Math. Soc. 17, 8 (1911), 409–414.

[6]

Wei-Fan Chiang, Ganesh Gopalakrishnan, Zvonimir Rakamaric, and Alexey Solovyev. 2014. Efficient Search for Inputs Causing High Floating-point Errors. SIGPLAN Not. 49, 8 (Feb. 2014), 43–52.

Digital Library

[7]

Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’77). ACM, New York, NY, USA, 238–252.

Digital Library

[8]

Nasrine Damouche and Matthieu Martel. 2018. Salsa: An Automatic Tool to Improve the Numerical Accuracy of Programs. In Automated Formal Methods (Kalpa Publications in Computing), Natarajan Shankar and Bruno Dutertre (Eds.), Vol. 5. EasyChair, 63–76.

[9]

Nasrine Damouche, Matthieu Martel, and Alexandre Chapoutot. 2017. Numerical Accuracy Improvement by Interprocedural Program Transformation. In Proceedings of the 20th International Workshop on Software and Compilers for Embedded Systems (SCOPES ’17). ACM, New York, NY, USA, 1–10.

Digital Library

[10]

Favio DeMarco, Jifeng Xuan, Daniel Le Berre, and Martin Monperrus. 2014. Automatic Repair of Buggy if Conditions and Missing Preconditions with SMT. In Proceedings of the 6th International Workshop on Constraints in Software Testing, Verification, and Analysis (CSTVA ’14). ACM, New York, NY, USA, 30–39.

Digital Library

[11]

Anthony Di Franco, Hui Guo, and Cindy Rubio-González. 2017. A Comprehensive Study of Real-world Numerical Bug Characteristics. In Proceedings of the 32Nd IEEE/ACM International Conference on Automated Software Engineering (ASE ’17). IEEE Press, Piscataway, NJ, USA, 509–519. http://dl.acm.org/citation.cfm?id=3155562.3155627

Digital Library

[12]

Thomas Durieux and Martin Monperrus. 2016. DynaMoth: Dynamic Code Synthesis for Automatic Program Repair. In Proceedings of the 11th International Workshop on Automation of Software Test (AST ’16). ACM, New York, NY, USA, 85–91.

Digital Library

[13]

Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann. 2007. MPFR: A Multipleprecision Binary Floating-point Library with Correct Rounding. ACM Trans. Math. Softw. 33, 2, Article 13 (June 2007).

Digital Library

[14]

Zhoulai Fu, Zhaojun Bai, and Zhendong Su. 2015. Automated Backward Error Analysis for Numerical Code. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’15). ACM, New York, NY, USA, 639–654.

Digital Library

[15]

Zhoulai Fu and Zhendong Su. 2017. Achieving High Coverage for Floating-point Code via Unconstrained Programming. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’17). ACM, New York, NY, USA, 306–319.

Digital Library

[16]

David Goldberg. 1991. What Every Computer Scientist Should Know About Floating-point Arithmetic. ACM Comput. Surv. 23, 1 (March 1991), 5–48.

Digital Library

[17]

Divya Gopinath, Muhammad Zubair Malik, and Sarfraz Khurshid. 2011. Specification-based Program Repair Using SAT. In Proceedings of the 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems: Part of the Joint European Conferences on Theory and Practice of Software (TACAS’11/ETAPS’11). Springer-Verlag, Berlin, Heidelberg, 173–188. http://dl.acm.org/citation.cfm?id=1987389.1987408

Digital Library

[18]

Fredrik Johansson et al. 2013. mpmath: a Python library for arbitrary-precision floating-point arithmetic (version 0.18). http://mpmath.org/.

[19]

William Kahan. 1996. IEEE standard 754 for binary floating-point arithmetic. Lecture Notes on the Status of IEEE 754, 94720-1776 (1996), 11.

[20]

Wonyeol Lee, Rahul Sharma, and Alex Aiken. 2017. On Automatically Proving the Correctness of Math.H Implementations. Proc. ACM Program. Lang. 2, POPL, Article 47 (Dec. 2017), 32 pages.

Digital Library

[21]

Fan Long and Martin Rinard. 2015. Staged Program Repair with Condition Synthesis. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE ’15). ACM, New York, NY, USA, 166–178.

Digital Library

[22]

Fan Long and Martin Rinard. 2016. Automatic Patch Generation by Learning Correct Code. SIGPLAN Not. 51, 1 (Jan. 2016), 298–312.

Digital Library

[23]

Sebastian R. Lamelas Marcote and Martin Monperrus. 2015. Automatic Repair of Infinite Loops. CoRR abs/1504.05078 (2015). arXiv: 1504.05078 http://arxiv.org/abs/1504.05078

[24]

Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. DirectFix: Looking for Simple Program Repairs. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (ICSE ’15). IEEE Press, Piscataway, NJ, USA, 448–458. http://dl.acm.org/citation.cfm?id=2818754.2818811

Digital Library

[25]

Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable Multiline Program Patch Synthesis via Symbolic Analysis. In Proceedings of the 38th International Conference on Software Engineering (ICSE ’16). ACM, New York, NY, USA, 691–701.

Digital Library

[26]

Nicholas Nethercote and Julian Seward. 2007. Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation. SIGPLAN Not. 42, 6 (June 2007), 89–100.

Digital Library

[27]

Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. 2013. SemFix: Program Repair via Semantic Analysis. In Proceedings of the 2013 International Conference on Software Engineering (ICSE ’13). IEEE Press, Piscataway, NJ, USA, 772–781. http://dl.acm.org/citation.cfm?id=2486788.2486890

Digital Library

[28]

Pavel Panchekha, Alex Sanchez-Stern, James R. Wilcox, and Zachary Tatlock. 2015. Automatically Improving Accuracy for Floating Point Expressions. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’15). ACM, New York, NY, USA, 1–11.

Digital Library

[29]

Yuhua Qi, Xiaoguang Mao, Yan Lei, Ziying Dai, and Chengsong Wang. 2014. The Strength of Random Search on Automated Program Repair. In Proceedings of the 36th International Conference on Software Engineering (ICSE ’14). ACM, New York, NY, USA, 254–265.

Digital Library

[30]

Alex Sanchez-Stern, Pavel Panchekha, Sorin Lerner, and Zachary Tatlock. 2018. Finding Root Causes of Floating Point Error. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’18). ACM, New York, NY, USA, 256–269.

Digital Library

[31]

Eric Schkufza, Rahul Sharma, and Alex Aiken. 2014. Stochastic Optimization of Floating-point Programs with Tunable Precision. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). ACM, New York, NY, USA, 53–64.

Digital Library

[32]

Pat H Sterbenz. 1973. Floating-point computation. Prentice Hall, Englewood Cliffs, N.J.

[33]

Rainer Storn and Kenneth Price. 1997. Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces. Journal of Global Optimization 11, 4 (01 Dec 1997), 341–359.

Digital Library

[34]

Enyi Tang, Xiangyu Zhang, Norbert Th. Muller, Zhenyu Chen, and Xuandong Li. 2017. Software Numerical Instability Detection and Diagnosis by Combining Stochastic and Infinite-Precision Testing. IEEE Transactions on Software Engineering 43, 10 (Oct 2017), 975–994.

[35]

David J. Wales and Jonathan P. K. Doye. 1997. Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms. The Journal of Physical Chemistry A 101, 28 (1997), 5111–5116.

[36]

Ran Wang, Daming Zou, Xinrui He, Yingfei Xiong, Lu Zhang, and Gang Huang. 2016. Detecting and Fixing Precision-specific Operations for Measuring Floating-point Errors. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE ’16). ACM, New York, NY, USA, 619–630.

Digital Library

[37]

Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009. Automatically Finding Patches Using Genetic Programming. In Proceedings of the 31st International Conference on Software Engineering (ICSE ’09). IEEE Computer Society, Washington, DC, USA, 364–374.

Digital Library

[38]

Jifeng Xuan, Matias Martinez, Favio DeMarco, Maxime Clement, Sebastian Lamelas Marcote, Thomas Durieux, Daniel Le Berre, and Martin Monperrus. 2017. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs. IEEE Trans. Softw. Eng. 43, 1 (Jan. 2017), 34–55.

Digital Library

[39]

Xin Yi, Liqian Chen, Xiaoguang Mao, and Tao Ji. 2017a. Automated Repair of High Inaccuracies in Numerical Programs. In 2017 IEEE International Conference on Software Maintenance and Evolution (ICSME ’17). 514–518.

[40]

Xin Yi, Liqian Chen, Xiaoguang Mao, and Tao Ji. 2017b. Efficient Global Search for Inputs Triggering High Floating-Point Inaccuracies. In 2017 24th Asia-Pacific Software Engineering Conference (APSEC ’17). 11–20.

[41]

Daming Zou, Ran Wang, Yingfei Xiong, Lu Zhang, Zhendong Su, and Hong Mei. 2015. A Genetic Algorithm for Detecting Significant Floating-point Inaccuracies. In Proceedings of the 37th International Conference on Software Engineering -Volume 1 (ICSE ’15). IEEE Press, Piscataway, NJ, USA, 529–539. http://dl.acm.org/citation.cfm?id=2818754.2818820

Digital Library

Cited By

Yi XYu HChen LMao XWang J(2024)FPCC: Detecting Floating-Point Errors via Chain ConditionsProceedings of the ACM on Programming Languages10.1145/36897648:OOPSLA2(1504-1531)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689764
Wang XYi XYu HHuang CPeng L(2024)Parallel Optimization for Accelerating the Generation of Correctly Rounded Elementary FunctionsProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673125(21-31)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673125
Xu JCui MLi FZhang ZYang HZhou BZhao JChristakis MPradel M(2024)Arfa: An Agile Regime-Based Floating-Point Optimization Approach for Rounding ErrorsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680378(1516-1528)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680378
Show More Cited By

Index Terms

Efficient automated repair of high floating-point errors in numerical libraries

Recommendations

Decimal Floating-Point Multiplication

Decimal multiplication is important in many commercial applications including financial analysis, banking, tax calculation, currency conversion, insurance, and accounting. This paper presents the design of two decimal floating-point multipliers: one ...
An Efficient Hardware-Based Higher Radix Floating Point MAC Design

This article proposes an effective way of implementing a multiply accumulate circuit (MAC) for high-speed floating point arithmetic operations. The real-world applications related to digital signal processing and the like demand high-performance ...
Hardware Designs for Decimal Floating-Point Addition and Related Operations

Decimal arithmetic is often used in commercial, financial, and Internet-based applications. Due to the growing importance of decimal floating-point (DFP) arithmetic, the IEEE 754 Draft Standard for Floating-Point Arithmetic (IEEE P754) includes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 3, Issue POPL

January 2019

2275 pages

EISSN:2475-1421

DOI:10.1145/3302515

Issue’s Table of Contents

Copyright © 2019 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 January 2019

Published in PACMPL Volume 3, Issue POPL

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
National Key R&D Program of China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1,674
Total Downloads

Downloads (Last 12 months)183
Downloads (Last 6 weeks)18

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yi XYu HChen LMao XWang J(2024)FPCC: Detecting Floating-Point Errors via Chain ConditionsProceedings of the ACM on Programming Languages10.1145/36897648:OOPSLA2(1504-1531)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689764
Wang XYi XYu HHuang CPeng L(2024)Parallel Optimization for Accelerating the Generation of Correctly Rounded Elementary FunctionsProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673125(21-31)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673125
Xu JCui MLi FZhang ZYang HZhou BZhao JChristakis MPradel M(2024)Arfa: An Agile Regime-Based Floating-Point Optimization Approach for Rounding ErrorsProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680378(1516-1528)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680378
Miao DLaguna IRubio-González C(2024)Input Range Generation for Compiler-Induced Numerical InconsistenciesProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656618(201-212)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656618
Xia ZChen YNie PWang Z(2024)Detecting Numerical Deviations in Deep Learning Models Introduced by the TVM Compiler2024 IEEE 35th International Symposium on Software Reliability Engineering (ISSRE)10.1109/ISSRE62328.2024.00018(73-83)Online publication date: 28-Oct-2024
https://doi.org/10.1109/ISSRE62328.2024.00018
Song YXie XXu B(2024)When debugging encounters artificial intelligence: state of the art and open challengesScience China Information Sciences10.1007/s11432-022-3803-967:4Online publication date: 21-Feb-2024
https://doi.org/10.1007/s11432-022-3803-9
Zhang ZXu JHao JQu YHe HZhou B(2024)Hierarchical search algorithm for error detection in floating-point arithmetic expressionsThe Journal of Supercomputing10.1007/s11227-023-05523-680:1(1183-1205)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11227-023-05523-6
Titolo LMoscato MFeliu MMasci PMuñoz C(2024)Rigorous Floating-Point Round-Off Error Analysis in PRECiSA 4.0Formal Methods10.1007/978-3-031-71177-0_2(20-38)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71177-0_2
Yu HYi XYin BLi FChen ZHuang C(2023)Efficient Generation of Floating-Point Inputs for Compiler-Induced Variability2023 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER56733.2023.00030(224-235)Online publication date: Mar-2023
https://doi.org/10.1109/SANER56733.2023.00030
Zhang ZZhou BHao JYang HCui MZhou YSong GLi FXu JZhao JBissyandé TKlein JBird CSarro F(2023)Eiffel: Inferring Input Ranges of Significant Floating-Point Errors via Polynomial ExtrapolationProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00139(1441-1453)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00139
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents