Managing performance vs. accuracy trade-offs with loop perforation

By Stelios Sidiroglou, Sasa Misailovic, H. Hoffmann, Martin C. Rinard. ESEC/FSE '11, 2011

523 citations recorded by the source corpus.

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

Subfields: Computational Theory and Mathematics, Hardware and Architecture, Signal Processing

View Paper: https://www.semanticscholar.org/paper/60d9f3902034f83db5d39ea127aacf2b807d74f1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Hardware and Architecture

In Signal Processing

Citations in the corpus

Neural Acceleration for General-Purpose Approximate Programs (2012, background): “The domains are commensurate with evaluations of previous work on approximate computing [1,11,28,29,41,43].”
Approximate storage in solid-state memories (2013, methodology): “ware [8, 12, 14, 15, 24, 26] and software [2, 17, 41] techniques.”
PerforatedCNNs: Acceleration through Elimination of Redundant Convolutions (2015, methodology): “One of the most prominent methods for this problem is loop perforation [18, 19, 24].”
Coupling proofs are probabilistic product programs (2016, methodology): “the premise for for p 0, but we now have two synchronized loops; we can use the [STRUCT] rule to remove the conditional on p 0 which is always true in this case. 6.2 Loop Perforation Loop perforation [44, 51] is a program transformation that delivers good trade-offs between performance and accuracy,”
A Survey of Techniques for Approximate Computing (2016, methodology): “…2010], noncritical/crucial [Shi et al. 2015], error-resilient/tolerant [Esmaeilzadeh et al. 2012b], error-acceptable [Kahng and Kang 2012], tunable [Sidiroglou et al. 2011], having ‘forgiving nature’ [Venkataramani et al. 2015] and being ‘optional’ (vs. guaranteed/mandatory) [Chakradhar and…”
SnaPEA: Predictive Early Activation for Reducing Computation in Deep Convolutional Neural Networks (2018, background): “In one of the most recent efforts [29], Sidiroglou et al. proposed loop perforation in which the accuracy is traded in return for improvement in performance.”
Analysis and characterization of inherent application resilience for approximate computing (2013, methodology): “Approximate computing techniques in software [10, 11, 12] have been proposed to improve the performance and parallel scalability of applications on general-purpose computing platforms.”