Randomized accuracy-aware program transformations for efficient approximate computations

Zeyuan Allen Zhu, Sasa Misailovic, Jonathan A. Kelner, Martin Rinard

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

Abstract

Despite the fact that approximate computations have come to dominate many areas of computer science, the field of program transformations has focused almost exclusively on traditional semantics-preserving transformations that do not attempt to exploit the opportunity, available in many computations, to acceptably trade off accuracy for benefits such as increased performance and reduced resource consumption. We present a model of computation for approximate computations and an algorithm for optimizing these computations. The algorithm works with two classes of transformations: substitution transformations (which select one of a number of available implementations for a given function, with each implementation offering a different combination of accuracy and resource consumption) and sampling transformations (which randomly discard some of the inputs to a given reduction). The algorithm produces a (1 +ε) randomized approximation to the optimal randomized computation (which minimizes resource consumption subject to a probabilistic accuracy specification in the form of a maximum expected error or maximum error variance).

Original languageEnglish (US)
Title of host publicationPOPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
Pages441-454
Number of pages14
DOIs
StatePublished - Mar 12 2012
Externally publishedYes
Event39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'12 - Philadelphia, PA, United States
Duration: Jan 25 2012Jan 27 2012

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

Other

Other39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'12
CountryUnited States
CityPhiladelphia, PA
Period1/25/121/27/12

Fingerprint

Computer science
Substitution reactions
Semantics
Sampling
Specifications

Keywords

  • Discretization
  • Error-time tradeoff
  • Optimization
  • Probabilistic

ASJC Scopus subject areas

  • Software

Cite this

Zhu, Z. A., Misailovic, S., Kelner, J. A., & Rinard, M. (2012). Randomized accuracy-aware program transformations for efficient approximate computations. In POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (pp. 441-454). (Conference Record of the Annual ACM Symposium on Principles of Programming Languages). https://doi.org/10.1145/2103656.2103710

Randomized accuracy-aware program transformations for efficient approximate computations. / Zhu, Zeyuan Allen; Misailovic, Sasa; Kelner, Jonathan A.; Rinard, Martin.

POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012. p. 441-454 (Conference Record of the Annual ACM Symposium on Principles of Programming Languages).

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

Zhu, ZA, Misailovic, S, Kelner, JA & Rinard, M 2012, Randomized accuracy-aware program transformations for efficient approximate computations. in POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, pp. 441-454, 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'12, Philadelphia, PA, United States, 1/25/12. https://doi.org/10.1145/2103656.2103710
Zhu ZA, Misailovic S, Kelner JA, Rinard M. Randomized accuracy-aware program transformations for efficient approximate computations. In POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012. p. 441-454. (Conference Record of the Annual ACM Symposium on Principles of Programming Languages). https://doi.org/10.1145/2103656.2103710
Zhu, Zeyuan Allen ; Misailovic, Sasa ; Kelner, Jonathan A. ; Rinard, Martin. / Randomized accuracy-aware program transformations for efficient approximate computations. POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012. pp. 441-454 (Conference Record of the Annual ACM Symposium on Principles of Programming Languages).
@inproceedings{231f748686bd444383773424a0784b77,
title = "Randomized accuracy-aware program transformations for efficient approximate computations",
abstract = "Despite the fact that approximate computations have come to dominate many areas of computer science, the field of program transformations has focused almost exclusively on traditional semantics-preserving transformations that do not attempt to exploit the opportunity, available in many computations, to acceptably trade off accuracy for benefits such as increased performance and reduced resource consumption. We present a model of computation for approximate computations and an algorithm for optimizing these computations. The algorithm works with two classes of transformations: substitution transformations (which select one of a number of available implementations for a given function, with each implementation offering a different combination of accuracy and resource consumption) and sampling transformations (which randomly discard some of the inputs to a given reduction). The algorithm produces a (1 +ε) randomized approximation to the optimal randomized computation (which minimizes resource consumption subject to a probabilistic accuracy specification in the form of a maximum expected error or maximum error variance).",
keywords = "Discretization, Error-time tradeoff, Optimization, Probabilistic",
author = "Zhu, {Zeyuan Allen} and Sasa Misailovic and Kelner, {Jonathan A.} and Martin Rinard",
year = "2012",
month = "3",
day = "12",
doi = "10.1145/2103656.2103710",
language = "English (US)",
isbn = "9781450310833",
series = "Conference Record of the Annual ACM Symposium on Principles of Programming Languages",
pages = "441--454",
booktitle = "POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages",

}

TY - GEN

T1 - Randomized accuracy-aware program transformations for efficient approximate computations

AU - Zhu, Zeyuan Allen

AU - Misailovic, Sasa

AU - Kelner, Jonathan A.

AU - Rinard, Martin

PY - 2012/3/12

Y1 - 2012/3/12

N2 - Despite the fact that approximate computations have come to dominate many areas of computer science, the field of program transformations has focused almost exclusively on traditional semantics-preserving transformations that do not attempt to exploit the opportunity, available in many computations, to acceptably trade off accuracy for benefits such as increased performance and reduced resource consumption. We present a model of computation for approximate computations and an algorithm for optimizing these computations. The algorithm works with two classes of transformations: substitution transformations (which select one of a number of available implementations for a given function, with each implementation offering a different combination of accuracy and resource consumption) and sampling transformations (which randomly discard some of the inputs to a given reduction). The algorithm produces a (1 +ε) randomized approximation to the optimal randomized computation (which minimizes resource consumption subject to a probabilistic accuracy specification in the form of a maximum expected error or maximum error variance).

AB - Despite the fact that approximate computations have come to dominate many areas of computer science, the field of program transformations has focused almost exclusively on traditional semantics-preserving transformations that do not attempt to exploit the opportunity, available in many computations, to acceptably trade off accuracy for benefits such as increased performance and reduced resource consumption. We present a model of computation for approximate computations and an algorithm for optimizing these computations. The algorithm works with two classes of transformations: substitution transformations (which select one of a number of available implementations for a given function, with each implementation offering a different combination of accuracy and resource consumption) and sampling transformations (which randomly discard some of the inputs to a given reduction). The algorithm produces a (1 +ε) randomized approximation to the optimal randomized computation (which minimizes resource consumption subject to a probabilistic accuracy specification in the form of a maximum expected error or maximum error variance).

KW - Discretization

KW - Error-time tradeoff

KW - Optimization

KW - Probabilistic

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

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

U2 - 10.1145/2103656.2103710

DO - 10.1145/2103656.2103710

M3 - Conference contribution

AN - SCOPUS:84857880446

SN - 9781450310833

T3 - Conference Record of the Annual ACM Symposium on Principles of Programming Languages

SP - 441

EP - 454

BT - POPL'12 - Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

ER -