Many modern applications (such as multimedia processing, machine learning, and big-data analytics) exhibit an inherent tradeoff between performance and the accuracy of the produced results. These applications allow us to investigate new, more aggressive program optimizations. We present a novel approximate optimization framework based on accuracy-aware program transformations. These transformations reduce accuracy of computation in return for improved performance, energy efficiency, and/or resilience. The optimization framework includes program analyses that characterize the accuracy of transformed programs, and search techniques that navigate the tradeoff space induced by transformations to find approximate programs with profitable tradeoffs. Our research shows that this approach can significantly improve program performance while providing acceptably accurate results. Traditionally, developers of approximate applications have been manually designing algorithms that can trade accuracy of the application's result for reduced execution time or energy consumption. More recently, researchers have started exploring complementary system-level approximation approaches that open new points in the underlying accuracy versus performance tradeoff space. This includes approximate hardware components (such as approximate accelerators, ALUs, or memories, e.g., [6, 7, 10, 11, 17] ) and programming systems (such as languages, verification systems, runtime systems, and compilers, e.g., [1-4, 8, 18, 21, 22]). Accuracy-aware program transformations are compiler-level optimizations that automatically generate approximate versions of programs. They therefore depart from the traditional approach to program optimization in which the transformations always preserve program semantics. Performance-oriented transformations reduce the amount of work that a program does [5, 8, 12, 14, 16, 19, 21, 23, 24] . For instance, loop perforation [16, 23] can instruct a loop of the form for (int i = 0; i < n; i++) {...} to execute fewer iterations. To execute only a half of the loop's iterations, loop perforation can change the induction variable increment from i++ to i+=2. Energy-oriented transformations instruct a program to use hardware components that aggressively save energy by allowing errors in their results [4, 13, 22] . Resiliency-oriented transformations allow a program to continue execution after otherwise fatal errors and produce at least a part of the original result [9, 20] . Automatically optimizing approximate programs using accuracyaware transformations provides a new opportunity to reduce engineering effort and resource consumption and increase program resilience. But, this opportunity comes at a price, because the transformations introduce uncertainty into the program's execution and the results it produces. This emerging uncertainty raises a number of new research questions, including (1) how to identify parts of a program that are good candidates for accuracy-aware transformations; (2) how to characterize the effects of a transformation on the program's execution, especially the result's accuracy; and (3) how to automatically discover transformations that provide maximum performance gains for acceptable accuracy losses. To address these challenges, our research presents two conceptual approaches to program analysis and optimization: Testing-Based Approach. To find profitable tradeoffs, these techniques first generate a transformed program and then dynamically validate that its executions satisfy the developer's accuracy requirement [8, 14, 16, 23] . Typically, the validation procedures run the transformed program on a set of developer-provided representative inputs, compare the accuracy of the results with that produced by the original program, and check whether the executions exhibited any undesired behavior via dynamic analysis (and optionally lightweight static analysis). While such techniques work for arbitrary programs and can effectively navigate the tradeoff space, they do not provide guarantees on program's behavior beyond the tested representative inputs. Analysis-Based Approach. To find profitable tradeoffs, these techniques use static program analysis to reduce the problem of applying accuracy-aware program transformations to standard numerical optimization problems [13, 15, 24] . Specifically, the optimization framework starts by performing probabilistic static analysis that quantifies the probability of unacceptable output deviation caused by the candidate transformations. The expressions generated by the static analysis constitute the constraints in the numerical optimization problem. Program analysis also produces the estimate of the performance/energy savings, which constitutes the optimization problem's objective function. The framework can then call an off-the-shelf solver to find the set of transformations to apply. In contrast to the testing-based approach, the analysis-based approach can provide guarantees for all relevant inputs (and not just the tested inputs) and can explore more complex tradeoff spaces. However, currently it can provide guarantees only for the computations that have specific structure (e.g., computations with statically bounded loops or sequences of map and reduce operators). Together, these approaches lay down the foundation for program optimization with accuracy-aware transformations. While accuracyaware optimization departs from the traditional view that transformations must preserve program semantics, it has demonstrated that it can significantly improve performance and energy efficiency of approximate programs while preserving developer's accuracy requirements. Acknowledgements. The research on accuracy-aware transformations is the result of the team effort of many researchers, including major contributions from
They also propose compiler-level, accuracy-aware transformations that automatically generate approximate versions of programs REF .
Accuracy-aware optimization of approximate programs
CASES '15
Computer Science