Martin Rinard

Approximate Computing



Many computations exhibit an inherent trade off between accuracy, performance, and power consumption - if the client is willing to accept a slightly less accurate result, it is often possible to adapt the computation to deliver that result while consuming substantially less power or compute time. But most implementations of these computations operate at only one point in this underlying tradeoff space. In many cases the implementer of the computation is not even aware that this tradeoff space exists and that the computation has the ability to operate successfully at a variety of points in this space. The field of approximate computing investigates techniques for discovering and exploiting these tradeoffs.

My research group developed many of the foundational techniques and systems in this area, including rich program transformations for generating efficient and accurate approximate program execution, techniques for reasoning about the performance and accuracy of approximate computations, and approximate programming languages that enable developers to specify and verify approximate computations. My group also pioneered foundational techniques in approximate parallel computing.

Rich Program Transformations for Approximate Computing

Approximate computing is often enabled by rich program transformations (program transformations that may change the semantics of the program). Rich transformations induce a search space of programs surrounding the original program. An automated search of this space can find programs with desirable accuracy, performance, and power consumption characteristics.

My research group pioneered the first rich transformations, including loop perforation, which increases performance by skipping loop iterations, task skipping, which increases performance and robustness by skipping tasks, dynamic knobs , which enable programs to dynamically switch between different performance and accuracy settings, implementation selection and reduction sampling, which enable programs to execute at a range of points in the accuracy versus performance space, and synchronzation elimination, which identifies acceptable race conditions in parallel programs, then removes synchronization designed to prevent those race conditions.

Reasoning About Approximate Computations

It is often desirable to understand and characterize the potential effects of rich program transforms (such as loop perforation or synchronization elimination) on the end to end performance or accuracy of the computation. To this end, my group pioneered techniques for reasoning about approximate computations. These techniques provide models or guarantees that characterize the accuracy and performance effects of various approximate computing techniques as applied to specific computations. We have implemented these techniques in programming systems that enable developers to obtain approximate computations with prectable and desirable performance and accuracy properties.

Our initial research in this area was empirical, using dynamic analysis on executions of the program on representative inputs to derive empirical performance versus accuracy models that characterized the performance and accuracy effects of rich transformations. Our seminal task skipping research, for example, produced empirical statistical models that characterized the performance and accuracy impact of skipping specific percentages of specific tasks.

We next moved on to develop static techniques that analyze the program before it executes to obtain performance and accuracy models with (often probabilistic) guarantees that hold over all program executions.

Probabilistically Accurate Program Transformations: This research uses random variables to model the values that the program manipulates. The static analysis reasons about how these proability distributions propagate through the program in the presence of various rich program transformations (such as loop perforation). The end result is a probabilistic characterization of the accuracy of the result that the transformed program produces. This characterization is guaranteed to be accurate whenever the probability distributions accurately model the inputs.

Approximate Programming Languages

Integrating approximate computing concepts into programming languages can enable developers to precisely express the desired range of acceptable approximate computations. This integration can also enable the productive specification and verification of important reliability and accuracy properties of the resulting approximate computations. My research group delivered much of the early foundational research in this area:

Approximate Parallel Computing

Parallel computing provides a fertile area for the application of approximate computing. Phenomena such as nondeterminism, synchronization, and data races can all be exploited to obtain profitable approximation opportunities.