TY - GEN
T1 - Statistical Algorithmic Profiling for Randomized Approximate Programs
AU - Joshi, Keyur
AU - Fernando, Vimuth
AU - Misailovic, Sasa
N1 - Publisher Copyright:
© 2019 IEEE.
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
T2 - 41st IEEE/ACM International Conference on Software Engineering, ICSE 2019
Y2 - 25 May 2019 through 31 May 2019
ER -