Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> A bicycle handle bar comprises resilient material such that it may be flexed up and down by a rider so that the rider will exercise his arms as well as his legs when riding the bicycle. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> When logic upsets (faults) affect digital representations of numbers, it is possible to consider their effects in terms of the magnitude of the value deviation they induce. When some upper limit on such a change in value is tolerable, one may consider techniques for encoding to limit value deviations in the presence of faults. Examples of applications with tolerance to value deviation include computer graphics computations, and the computation, communication and storage of analog sensor values in sensor networks. This article presents upper bounds for the achievable efficiency of encoding under the constraint relaxation of a tolerable value deviation. Closed-form expressions and numerical evaluations for upper bounds on the achievable encoding efficiency under a maximum tolerable value deviation, for several different conditions under which logic upsets may occur, are presented. The bounds demonstrate the possibility of significant gains in encoding efficiency, when some semantic deviation of values is tolerable. Lower and upper bounds on the possible absolute value of deviation resulting from a given number of upsets in words of a known size are provided. It is shown that, if possible to bias the physical design of a system such that logic upsets in both high and low logic direction may occur simultaneously (versus only one or the other), the minimum values of the resulting deviations will be reduced. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> Smart phones comprise a large and rapidly growing market. These devices provide unprecedented opportunities for sensor mining since they include a large variety of sensors, including an: acceleration sensor (accelerometer), location sensor (GPS), direction sensor (compass), audio sensor (microphone), image sensor (camera), proximity sensor, light sensor, and temperature sensor. Combined with the ubiquity and portability of these devices, these sensors provide us with an unprecedented view into people's lives---and an excellent opportunity for data mining. But there are obstacles to sensor mining applications, due to the severe resource limitations (e.g., power, memory, bandwidth) faced by mobile devices. In this paper we discuss these limitations, their impact, and propose a solution based on our WISDM (WIireless Sensor Data Mining) smart phone-based sensor mining architecture. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> Transferring data between integrated circuits accounts for a growing proportion of system power in wearable and mobile systems. The dynamic component of power dissipated in this data transfer can be reduced by reducing signal transitions. Techniques for reducing signal transitions on communication links have traditionally been targeted at parallel buses and can therefore not be applied when the transfer interfaces are serial buses. In this article, we address the issue of the best-case effectiveness of techniques to reduce signal transitions on serial buses, if these techniques also allow some error in the numeric interpretation of transmitted data. For many embedded applications, exchanging numeric accuracy for power reduction is a worthwhile tradeoff. We present a study of the efficiency of these value-deviation-bounded approximate serial data encoders (VDBS data encoders) and proofs of their properties. The bounds and proofs we present yield new insights into the best possible tradeoffs between dynamic power reduction and approximation error that can be achieved in practice. The insights are important regardless of whether actual practical VDBS data encoders are implemented in software or in hardware. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> High performance approximate adders typically comprise of multiple smaller sub-adders, carry prediction units and error correction units. In this paper, we present a low-latency generic accuracy configurable adder to support variable approximation modes. It provides a higher number of potential configurations compared to state-of-the-art, thus enabling a high degree of design flexibility and trade-off between performance and output quality. An error correction unit is integrated to provide accurate results for cases where high accuracy is required. Furthermore, an associated scheme for error probability estimation allows convenient comparison of different approximate adder configurations without requiring the need to numerically simulate the adder. Our experimental results validate the developed error model and also the lower latency of our generic accuracy configurable adder over state-of-the-art approximate adders. For functional verification and prototyping, we have used a Xilinx Virtex-6 FPGA. Our adder model and synthesizable RTL are made open-source. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> We present a survey of approximate techniques and discuss concepts for building power-/energy-efficient computing components reaching from approximate accelerators to arithmetic blocks (like adders and multipliers). We provide a systematical understanding of how to generate and explore the design space of approximate components, which enables a wide-range of power/energy, performance, area and output quality tradeoffs, and a high degree of design flexibility to facilitate their design. To enable cross-layer approximate computing, bridging the gap between the logic layer (i.e. arithmetic blocks) and the architecture layer (and even considering the software layers) is crucial. Towards this end, this paper introduces open-source libraries of low-power and high-performance approximate components. The elementary approximate arithmetic blocks (adder and multiplier) are used to develop multi-bit approximate arithmetic blocks and accelerators. An analysis of data-driven resilience and error propagation is discussed. The approximate computing components are a first steps towards a systematic approach to introduce approximate computing paradigms at all levels of abstractions. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> We present Warp, a hardware platform to support research in approximate computing, sensor energy optimization, and energy-scavenged systems. Warp incorporates 11 state-of-the-art sensor integrated circuits, computation, and an energy-scavenged power supply, all within a miniature system that is just 3.6 cm x 3.3 cm x 0.5 cm. Warp's sensor integrated circuits together contain a total of 21 sensors with a range of precisions and accuracies for measuring eight sensing modalities of acceleration, angular rate, magnetic flux density (compass heading), humidity, atmospheric pressure (elevation), infrared radiation, ambient temperature, and color. Warp uses a combination of analog circuits and digital control to facilitate further tradeoffs between sensor and communication accuracy, energy efficiency, and performance. This article presents the design of Warp and presents an evaluation of our hardware implementation. The results show how Warp's design enables performance and energy efficiency versus ac- curacy tradeoffs. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> CHALLENGES <s> The sizes of compressed images depend on their spatial resolution (number of pixels) and on their color resolution (number of color quantization levels). We introduce DaltonQuant, a new color quantization technique for image compression that cloud services can apply to images destined for a specific user with known color vision deficiencies. DaltonQuant improves compression in a user-specific but reversible manner thereby improving a user's network bandwidth and data storage efficiency. DaltonQuant quantizes image data to account for user-specific color perception anomalies, using a new method for incremental color quantization based on a large corpus of color vision acuity data obtained from a popular mobile game. Servers that host images can revert DaltonQuant's image requantization and compression when those images must be transmitted to a different user, making the technique practical to deploy on a large scale. We evaluate DaltonQuant's compression performance on the Kodak PC reference image set and show that it improves compression by an additional 22%-29% over the state-of-the-art compressors TinyPNG and pngquant. <s> BIB008
We identify eight challenges facing both research and applications of techniques to trade correctness for resource usage. Challenge 1: Holistic cross-layer approaches. A whole-system view to trading errors for efficiency requires expertise in the target application domain and in multiple levels of the computing stack. Most of the existing approximation and error-handling mechanisms are designed in the context of a single layer in the stack. This is likely to be suboptimal. Techniques in different layers can easily negate each other, where gains reported in isolation may not translate into real systemlevel benefits in the end. At the same time, techniques in different layers may complement each other, where significant opportunities for cross-layer optimizations can be expected. A full-stack view of error-efficient system design requires less insular approaches. A cross-layer approach will however significantly increase the size of the design space and could introduce significant additional design complexity. Challenge 2: Hardware models, hardware platforms, and measurement data. Most software-level techniques employ models or abstractions of the errors and performance of the underlying hardware in order to achieve modularity and scalability. Examples of hardware error models assumed today include assumptions about the distribution of locations and values of errors caused by voltage overscaling in microarchitectural structures and memories, or assumptions about the distribution of errors in DRAMs that are not refreshed as regularly as they should be. Similarly, lower levels of the software stack may expose higher-level models to, e.g., application developers. Today, different research efforts often use different models, which makes comparisons between research results difficult and raises questions about the validity of reported resource savings. Error and performance models which have been validated by the hardware community, e.g., by hardware measurements and which are suitable for the software levels of the stack would be an invaluable contribution to the research directions described in this survey. In order to make credible claims about across-the-stack approximations, the proposed techniques need to be evaluated end-to-end either on actual state-of-the-art hardware platforms or with realistic simulations. Such end-to-end evaluations with an agreed-upon platform is missing today. Early examples in this direction include measurement results from open hardware platforms explicitly designed to expose accuracy, precision, performance, and energy efficiency tradeoffs BIB007 . Challenge 3: Hardware emulation/simulation, software tools, languages, and compiler infrastructure. Applying error versus resource tradeoffs in software requires tools that help programmers and systems builders take advantage of techniques in a systematic and controlled way. It also requires hardware simulators or emulators that help bridge the gap between the fidelity of hardware prototypes and the flexibility of software simulation. On the hardware simulation side, these tools would ideally provide support for end-to-end evaluation of entire systems, to be used in comparing different proposed techniques. Language and compiler tools would include those to support testing, debugging, and dynamic quality monitoring. First steps in this direction for compiler tools include ACCEPT  . Challenge 4: Application domains and algorithmic patterns. Today, there is insufficient consensus on well-defined classes of application domains and algorithmic patterns that constitute a preferential target for relaxations. First steps include the definition of "Recognition, Mining, and Synthesis" application classes BIB001 . A standard benchmark set which has been agreed upon by the wider community would increase progress and comparability of different techniques, like it has done for SAT/SMT solving. Such a benchmark set should ideally cover different domains and include also real-world 'challenge applications' which cannot be solved today, but which would convincingly demonstrate the viability of error-efficient computing. Challenge 5: Large-scale user studies to provide empirical characterization of acceptability. User studies with thousands of participants will be necessary to provide quantitative data BIB003 , which researchers can use when proposing techniques that exploit tolerance of human observers to deviations from correctness of program results. Initial steps in this direction include the "Specimen" dataset of color perception data used in color approximation techniques BIB008 . Challenge 6: Metrics. When applying techniques to an application, it would be useful to have a reliable error metric to guide the optimization process. In the ideal case, that error metric would be binary: "correct" and "not correct." But in reality, correctness and its boundaries are not well known for many applications. The metrics in question might be broadly applicable to many systems, or might be application-specific metrics used to measure Pareto-optimality. Early work in this direction includes the work of Akturk et al.  . Challenge 7: Studies of the theoretical bounds on resource usage. Theoretical upper and lower bounds are invaluable in guiding research as they set the bar for what is achievable. Such bounds are needed for a given formally-defined specification of deviation from correctness. One promising direction are bounds on encoding overhead for communication encoding techniques which trade communication energy use or performance (data rate) for integer deviations in communicated values. Examples of first steps in this direction include work on the bounds of encoding efficiency for deterministic and probabilistic approximate communication techniques BIB002 BIB004 . Challenge 8: Reproducibility and deployment of techniques. This survey describes a broad range of techniques, from circuits to algorithms. For many of the research results across these layers, it can be challenging to replicate the setup, tools, or benchmarks employed in evaluations. Beyond good scientific practice of describing experiments in sufficient detail to be reproducible, because there is today no common consensus even on many aspects of terminology, it is challenging to compare, replicate, and build upon research results. This survey attempted to address the challenge of terminology with a consistent set of formal definitions across the layers of a system (Section 4). Further progress is however needed. Opportunities include greater availability of open-source libraries. First steps for low-power and high-performance approximate arithmetic components include synthesizable Verilog/VHDL files and behavioral models in C/MATLAB BIB005 BIB006 .