research-article

RAIVE: runtime assessment of floating-point instability by vectorization

Authors:

Rajiv GuptaAuthors Info & Claims

OOPSLA 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

Pages 623 - 638

https://doi.org/10.1145/2814270.2814299

Published: 23 October 2015 Publication History

Abstract

Floating point representation has limited precision and inputs to floating point programs may also have errors. Consequently, during execution, errors are introduced, propagated, and accumulated, leading to unreliable outputs. We call this the instability problem. We propose RAIVE, a technique that identifies output variations of a floating point execution in the presence of instability. RAIVE transforms every floating point value to a vector of multiple values – the values added to create the vector are obtained by introducing artifi- cial errors that are upper bounds of actual errors. The propagation of artificial errors models the propagation of actual errors. When values in vectors result in discrete execution differences (e.g., following different paths), the execution is forked to capture the resulting output variations. Our evaluation shows that RAIVE can precisely capture output variations. Its overhead (340%) is 2.43 times lower than the state of the art

References

[1]

D. An, R. Blue, M. Lam, S. Piper, and G. Stoker. Fpinst: Floating point error analysis using dyninst. 2008.

[2]

T. Bao and X. Zhang. On-the-fly detection of instability problems in floating-point program execution. In OOPSLA ‘13.

Digital Library

[3]

T. Bao, Y. Zheng, and X. Zhang. White box sampling in uncertain data processing enabled by program analysis. In OOPSLA ’12.

Digital Library

[4]

E. T. Barr, T. Vo, V. Le, and Z. Su. Automatic detection of floating-point exceptions. In POPL ’13

Digital Library

[5]

F. Benz, A. Hildebrandt, and S. Hack. A dynamic program analysis to find floating-point accuracy problems. In PLDI ’12

Digital Library

[6]

J. Bornholt, T. Mytkowicz, and K. S. McKinley. A first-order type for uncertain data. In ASPLOS ’14.

Digital Library

[7]

S. Chaudhuri, S. Gulwani, R. Lublinerman, and S. Navidpour. Proving programs robust. In ESEC/FSE ’11.

Digital Library

[8]

W.-F. Chiang, G. Gopalakrishnan, Z. Rakamaric, and A. Solovyev. Efficient search for inputs causing high floatingpoint errors. In PPoPP ’14.

Digital Library

[9]

P. Cousot, R. Cousot, J. Feret, L. Mauborgne, A. Miné, D. Monniaux, and X. Rival. The ASTR ÉE Analyzer. In ESOP ‘05.

[10]

E. Darulova and V. Kuncak. Trustworthy numerical computation in scala. In OOPSLA ’11.

Digital Library

[11]

E. Darulova and V. Kuncak. Sound compilation of reals. In POPL ’14.

Digital Library

[12]

L. H. de Figueiredo and J. Stolfi. Affine Arithmetic: Concepts and Applications. Numerical Algorithms, 37:147–158, 2004.

[13]

M. de Hoon. Cluster 3.0. http://bonsai.hgc.jp/ ˜mdehoon/software/cluster/software.htm.

[14]

L. Pages, S. Brin, R. Motwani, and T .Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.

[15]

D. Delmas, E. Goubault, S. Putot, J. Souyris, K. Tekkal, and F. Védrine. Towards an industrial use of fluctuat on safetycritical avionics software. In FMICS ’09.

Digital Library

[16]

F. D. Dinechin and L. P. Arnaire. Assisted verification of elementary functions using gappa. In SAC ‘06.

Digital Library

[17]

C. F. Fang, T. Chen, and R. A. Rutenbar. Floating-point error analysis based on affine arithmetic. In Proc. IEEE Int. Conf. on Acoust., Speech, and Signal Processing, pages 561–564, 2003.

[18]

E. Goubault and S. Putot. Static analysis of finite precision computations. In VMCAI’11.

Digital Library

[19]

IEEE Task P754. IEEE 754-2008, Standard for Floating-Point Arithmetic. 2008.

[20]

Intel Corporation. Intel R 64 and IA-32 Architectures Optimization Reference Manual. Number 248966-028. July 2013.

[21]

L. Jaulin, M. Kieffer, O. Didrit, and E. Walter. Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics. Springer-Verlag New York Incorporated, 2012.

[22]

M. O. Lam, J. K. Hollingsworth, and G. Stewart. Dynamic floating-point cancellation detection. Parallel Computing, 39 (3):146 – 155, 2013.

Digital Library

[23]

M. Martel. Propagation of roundoff errors in finite precision computations: A semantics approach. In ESOP ’02.

Digital Library

[24]

G. Melquiond and C. Munoz. Guaranteed proofs using interval arithmetic. In ARITH ’05.

Digital Library

[25]

D. Monniaux. The pitfalls of verifying floating-point computations. ACM TOPLAS, 30(3):12:1–12:41, May 2008.

Digital Library

[26]

R. Moore. Interval analysis. Prentice-Hall series in automatic computation. Prentice-Hall, 1966.

[27]

C. Rubio-González, C. Nguyen, H. D. Nguyen, J. Demmel, W. Kahan, K. Sen, D. H. Bailey, C. Iancu, and D. Hough. Precimonious: Tuning assistant for floating-point precision. In SC ’13.

[28]

S. Sankaranarayanan, A. Chakarov, and S. Gulwani. Static analysis for probabilistic programs: Inferring whole program properties from finitely many paths. In PLDI ’13.

Digital Library

[29]

E. Tang, E. Barr, X. Li, and Z. Su. Perturbing numerical calculations for statistical analysis of floating-point program (in)stability. In ISSTA ’10.

Digital Library

Cited By

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
Chowdhary SNagarakatte S(2022)Fast shadow execution for debugging numerical errors using error free transformationsProceedings of the ACM on Programming Languages10.1145/35633536:OOPSLA2(1845-1872)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563353
Kloberdanz EKloberdanz KLe WDwyer MDamian DZeller A(2022)DeepStabilityProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510095(586-597)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510095
Show More Cited By

Index Terms

RAIVE: runtime assessment of floating-point instability by vectorization

Recommendations

RAIVE: runtime assessment of floating-point instability by vectorization
OOPSLA '15

Floating point representation has limited precision and inputs to floating point programs may also have errors. Consequently, during execution, errors are introduced, propagated, and accumulated, leading to unreliable outputs. We call this the ...
On-the-fly detection of instability problems in floating-point program execution
OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

The machine representation of floating point values has limited precision such that errors may be introduced during execution. These errors may get propagated and magnified by the following operations, leading to instability problems, e.g., control flow ...
On-the-fly detection of instability problems in floating-point program execution
OOPSLA '13

The machine representation of floating point values has limited precision such that errors may be introduced during execution. These errors may get propagated and magnified by the following operations, leading to instability problems, e.g., control flow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications

October 2015

953 pages

ISBN:9781450336895

DOI:10.1145/2814270

General Chair:
Jonathan Aldrich
Carnegie Mellon University, USA
,
Program Chair:
Patrick Eugster
Purdue University, USA

ACM SIGPLAN Notices Volume 50, Issue 10
OOPSLA '15
October 2015
953 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2858965
Editor:
Andy Gill
University of Kansas, Lawrence, KS
Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

SPLASH '15

Sponsor:

SIGPLAN

SPLASH '15: Conference on Systems, Programming, Languages, and Applications: Software for Humanity

October 25 - 30, 2015

PA, Pittsburgh, USA

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
301
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Chowdhary SNagarakatte S(2022)Fast shadow execution for debugging numerical errors using error free transformationsProceedings of the ACM on Programming Languages10.1145/35633536:OOPSLA2(1845-1872)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563353
Kloberdanz EKloberdanz KLe WDwyer MDamian DZeller A(2022)DeepStabilityProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510095(586-597)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510095
Dinda PWanninger NMa JBernat ABernat CGhosh SKraemer CElmasry YWeissman JChandra AGavrilovska ATiwari D(2022)FPVMProceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing10.1145/3502181.3531469(16-29)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3502181.3531469
Chowdhary SNagarakatte SSpinellis DGousios GChechik MDi Penta M(2021)Parallel shadow execution to accelerate the debugging of numerical errorsProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468585(615-626)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468585
Guo HLaguna IRubio-González CCuicchi CQualters IKramer W(2020)pLinerProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433766(1-14)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433766
Chowdhary SLim JNagarakatte SDonaldson ATorlak E(2020)Debugging and detecting numerical errors in computation with positsProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386004(731-746)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386004
Guo HRubio-González CRothermel GBae D(2020)Efficient generation of error-inducing floating-point inputs via symbolic executionProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380359(1261-1272)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380359
Dinda PBernat AHetland CParashar MVlassov VIrwin DMohror K(2020)Spying on the Floating Point Behavior of Existing, Unmodified Scientific ApplicationsProceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3369583.3392673(5-16)Online publication date: 23-Jun-2020
https://dl.acm.org/doi/10.1145/3369583.3392673
Guo HLaguna IRubio-Gonzalez C(2020)PLINER: Isolating Lines of Floating-Point Code for Compiler-Induced VariabilitySC20: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41405.2020.00053(1-14)Online publication date: Nov-2020
https://doi.org/10.1109/SC41405.2020.00053
Show More Cited By

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents