Statistical Algorithmic Profiling for Randomized Approximate Programs

Keyur Joshi, Vimuth Fernando, Sasa Misailovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many modern applications require low-latency processing of large data sets, often by using approximate algorithms that trade accuracy of the results for faster execution or reduced memory consumption. Although the algorithms provide probabilistic accuracy and performance guarantees, a software developer who implements these algorithms has little support from existing tools. Standard profilers do not consider accuracy of the computation and do not check whether the outputs of these programs satisfy their accuracy specifications. We present AXPROF, an algorithmic profiling framework for analyzing randomized approximate programs. The developer provides the accuracy specification as a formula in a mathematical notation, using probability or expected value predicates. AXPROF automatically generates statistical reasoning code. It first constructs the empirical models of accuracy, time, and memory consumption. It then selects and runs appropriate statistical tests that can, with high confidence, determine if the implementation satisfies the specification. We used AXPROF to profile 15 approximate applications from three domains - data analytics, numerical linear algebra, and approximate computing. AXPROF was effective in finding bugs and identifying various performance optimizations. In particular, we discovered five previously unknown bugs in the implementations of the algorithms and created fixes, guided by AXPROF.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019
PublisherIEEE Computer Society
Pages608-618
Number of pages11
ISBN (Electronic)9781728108698
DOIs
StatePublished - May 2019
Event41st IEEE/ACM International Conference on Software Engineering, ICSE 2019 - Montreal, Canada
Duration: May 25 2019May 31 2019

Publication series

NameProceedings - International Conference on Software Engineering
Volume2019-May
ISSN (Print)0270-5257

Conference

Conference41st IEEE/ACM International Conference on Software Engineering, ICSE 2019
Country/TerritoryCanada
CityMontreal
Period5/25/195/31/19

Keywords

  • profiler
  • randomized algorithms

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Statistical Algorithmic Profiling for Randomized Approximate Programs'. Together they form a unique fingerprint.

Cite this