Managing performance vs. accuracy trade-offs with loop perforation

TLDR

Modern computations such as video/audio encoding, Monte Carlo simulations, and machine learning routinely trade accuracy for performance, yet existing methods are ad‑hoc and domain‑specific. Loop perforation generalizes this trade‑off by executing only a subset of loop iterations, using criticality testing to exclude essential loops and a space‑exploration algorithm to identify Pareto‑optimal perforation policies. Across diverse applications, the technique delivers more than double performance—up to sevenfold—while keeping output error below ten percent.

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