Managing performance vs. accuracy trade-offs with loop perforation

Stelios Sidiroglou, Sasa Misailovic, Henry Hoffmann, Martin Rinard

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

Abstract

Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10%.

Original languageEnglish (US)
Title of host publicationSIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering
Pages124-134
Number of pages11
DOIs
StatePublished - Sep 30 2011
Externally publishedYes
Event19th ACM SIGSOFT Symposium on Foundations of Software Engineering, SIGSOFT/FSE'11 - Szeged, Hungary
Duration: Sep 5 2011Sep 9 2011

Publication series

NameSIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering

Other

Other19th ACM SIGSOFT Symposium on Foundations of Software Engineering, SIGSOFT/FSE'11
CountryHungary
CitySzeged
Period9/5/119/9/11

Fingerprint

Learning algorithms
Learning systems
Testing
Monte Carlo simulation

Keywords

  • Loop perforation
  • Profiling
  • Quality of service

ASJC Scopus subject areas

  • Software

Cite this

Sidiroglou, S., Misailovic, S., Hoffmann, H., & Rinard, M. (2011). Managing performance vs. accuracy trade-offs with loop perforation. In SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering (pp. 124-134). (SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering). https://doi.org/10.1145/2025113.2025133

Managing performance vs. accuracy trade-offs with loop perforation. / Sidiroglou, Stelios; Misailovic, Sasa; Hoffmann, Henry; Rinard, Martin.

SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering. 2011. p. 124-134 (SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering).

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

Sidiroglou, S, Misailovic, S, Hoffmann, H & Rinard, M 2011, Managing performance vs. accuracy trade-offs with loop perforation. in SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering. SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering, pp. 124-134, 19th ACM SIGSOFT Symposium on Foundations of Software Engineering, SIGSOFT/FSE'11, Szeged, Hungary, 9/5/11. https://doi.org/10.1145/2025113.2025133
Sidiroglou S, Misailovic S, Hoffmann H, Rinard M. Managing performance vs. accuracy trade-offs with loop perforation. In SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering. 2011. p. 124-134. (SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering). https://doi.org/10.1145/2025113.2025133
Sidiroglou, Stelios ; Misailovic, Sasa ; Hoffmann, Henry ; Rinard, Martin. / Managing performance vs. accuracy trade-offs with loop perforation. SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering. 2011. pp. 124-134 (SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering).
@inproceedings{b9f3e56df0ae43b7aaf5e4e4094a1839,
title = "Managing performance vs. accuracy trade-offs with loop perforation",
abstract = "Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10{\%}.",
keywords = "Loop perforation, Profiling, Quality of service",
author = "Stelios Sidiroglou and Sasa Misailovic and Henry Hoffmann and Martin Rinard",
year = "2011",
month = "9",
day = "30",
doi = "10.1145/2025113.2025133",
language = "English (US)",
isbn = "9781450304436",
series = "SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering",
pages = "124--134",
booktitle = "SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering",

}

TY - GEN

T1 - Managing performance vs. accuracy trade-offs with loop perforation

AU - Sidiroglou, Stelios

AU - Misailovic, Sasa

AU - Hoffmann, Henry

AU - Rinard, Martin

PY - 2011/9/30

Y1 - 2011/9/30

N2 - Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10%.

AB - Many modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-specific techniques developed specifically for the computation at hand. Loop perforation provides a general technique to trade accuracy for performance by transforming loops to execute a subset of their iterations. A criticality testing phase filters out critical loops (whose perforation produces unacceptable behavior) to identify tunable loops (whose perforation produces more efficient and still acceptably accurate computations). A perforation space exploration algorithm perforates combinations of tunable loops to find Pareto-optimal perforation policies. Our results indicate that, for a range of applications, this approach typically delivers performance increases of over a factor of two (and up to a factor of seven) while changing the result that the application produces by less than 10%.

KW - Loop perforation

KW - Profiling

KW - Quality of service

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

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

U2 - 10.1145/2025113.2025133

DO - 10.1145/2025113.2025133

M3 - Conference contribution

AN - SCOPUS:80053213080

SN - 9781450304436

T3 - SIGSOFT/FSE 2011 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering

SP - 124

EP - 134

BT - SIGSOFT/FSE'11 - Proceedings of the 19th ACM SIGSOFT Symposium on Foundations of Software Engineering

ER -