Input Responsiveness: Using Canary Inputs to Dynamically Steer Approximation

作     者：Laurenzano, Michael A. Hill, Parker Samadi, Mehrzad Mahlke, Scott Mars, Jason Tang, Lingjia 

作者机构：Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA 

出 版 物：《ACM SIGPLAN NOTICES》 (ACM SIGPLAN Not.)

年 卷 期：2016年第51卷第6期

页      面：161-176页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [XPS-1438996] U.S. Department of Energy's Office of Science, Office of Advanced Scientific Computing Research [DE-SC0014134] U.S. Department of Energy (DOE) [DE-SC0014134] Funding Source: U.S. Department of Energy (DOE) 

主　　题：Performance Runtime Systems Compilers Approximate Computing Performance Experimentation Design 

摘      要：This paper introduces Input Responsive Approximation ( IRA), an approach that uses a canary input - a small program input carefully constructed to capture the intrinsic properties of the original input - to automatically control how program approximation is applied on an input-by-input basis. Motivating this approach is the observation that many of the prior techniques focusing on choosing how to approximate arrive at conservative decisions by discounting substantial differences between inputs when applying approximation. The main challenges in overcoming this limitation lie in making the choice of how to approximate both effectively (e.g., the fastest approximation that meets a particular accuracy target) and rapidly for every input. With IRA, each time the approximate program is run, a canary input is constructed and used dynamically to quickly test a spectrum of approximation alternatives. Based on these runtime tests, the approximation that best fits the desired accuracy constraints is selected and applied to the full input to produce an approximate result. We use IRA to select and parameterize mixes of four approximation techniques from the literature for a range of 13 image processing, machine learning, and data mining applications. Our results demonstrate that IRA significantly outperforms prior approaches, delivering an average of 10.2x speedup over exact execution while minimizing accuracy losses in program outputs.