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
CountryCanada
CityMontreal
Period5/25/195/31/19

Fingerprint

Specifications
Data storage equipment
Linear algebra
Statistical tests
Processing

Keywords

  • profiler
  • randomized algorithms

ASJC Scopus subject areas

  • Software

Cite this

Joshi, K., Fernando, V., & Misailovic, S. (2019). Statistical Algorithmic Profiling for Randomized Approximate Programs. In Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019 (pp. 608-618). [8811971] (Proceedings - International Conference on Software Engineering; Vol. 2019-May). IEEE Computer Society. https://doi.org/10.1109/ICSE.2019.00071

Statistical Algorithmic Profiling for Randomized Approximate Programs. / Joshi, Keyur; Fernando, Vimuth; Misailovic, Sasa.

Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019. IEEE Computer Society, 2019. p. 608-618 8811971 (Proceedings - International Conference on Software Engineering; Vol. 2019-May).

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

Joshi, K, Fernando, V & Misailovic, S 2019, Statistical Algorithmic Profiling for Randomized Approximate Programs. in Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019., 8811971, Proceedings - International Conference on Software Engineering, vol. 2019-May, IEEE Computer Society, pp. 608-618, 41st IEEE/ACM International Conference on Software Engineering, ICSE 2019, Montreal, Canada, 5/25/19. https://doi.org/10.1109/ICSE.2019.00071
Joshi K, Fernando V, Misailovic S. Statistical Algorithmic Profiling for Randomized Approximate Programs. In Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019. IEEE Computer Society. 2019. p. 608-618. 8811971. (Proceedings - International Conference on Software Engineering). https://doi.org/10.1109/ICSE.2019.00071
Joshi, Keyur ; Fernando, Vimuth ; Misailovic, Sasa. / Statistical Algorithmic Profiling for Randomized Approximate Programs. Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019. IEEE Computer Society, 2019. pp. 608-618 (Proceedings - International Conference on Software Engineering).
@inproceedings{ac288d86d26942efb5617307c9c1f58e,
title = "Statistical Algorithmic Profiling for Randomized Approximate Programs",
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.",
keywords = "profiler, randomized algorithms",
author = "Keyur Joshi and Vimuth Fernando and Sasa Misailovic",
year = "2019",
month = "5",
doi = "10.1109/ICSE.2019.00071",
language = "English (US)",
series = "Proceedings - International Conference on Software Engineering",
publisher = "IEEE Computer Society",
pages = "608--618",
booktitle = "Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019",

}

TY - GEN

T1 - Statistical Algorithmic Profiling for Randomized Approximate Programs

AU - Joshi, Keyur

AU - Fernando, Vimuth

AU - Misailovic, Sasa

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

KW - profiler

KW - randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85069167757&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069167757&partnerID=8YFLogxK

U2 - 10.1109/ICSE.2019.00071

DO - 10.1109/ICSE.2019.00071

M3 - Conference contribution

AN - SCOPUS:85069167757

T3 - Proceedings - International Conference on Software Engineering

SP - 608

EP - 618

BT - Proceedings - 2019 IEEE/ACM 41st International Conference on Software Engineering, ICSE 2019

PB - IEEE Computer Society

ER -