Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> We consider the problem of scheduling tasks in the imprecise computation model to minimize the maximum error. Given a task system and a schedule of it, the maximum error of the task system is equal to the error of the task that has the largest error when the task system is executed according to the schedule. We describe two preemptive algorithms for scheduling on a processor n dependent tasks with rational ready times, deadlines, and processing times. Each schedule found by our algorithms is an optimal schedule with the minimum total error, and according to this schedule the maximum error is minimized. The run times of our algorithms are O(n/sup 3/) and O(n/sup 2/). > <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> The imprecise computation technique, which prevents timing faults and achieves graceful degradation by giving the user an approximate result of acceptable quality whenever the system cannot produce the exact result in time, is considered. Different approaches for scheduling imprecise computations in hard real-time environments are discussed. Workload models that quantify the tradeoff between result quality and computation time are reviewed. Scheduling algorithms that exploit this tradeoff are described. These include algorithms for scheduling to minimize total error, scheduling periodic jobs, and scheduling parallelizable tasks. A queuing-theoretical formulation of the imprecise scheduling problem is presented. > <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Department of Computer Science University of Illinois at Urbana-Champaign 1304 West Springfield Avenue Urbana, Illinois 61801 USA The imprecise computation technique was introduced as a way to handle transient overload and to enhance the fault-tolerance of real-time systems. In a system based on this technique, each time-critical task is designed in such a way that it can produce a usable, approximate result in time whenever a failure or overload prevents it from producing the desired, precise result. This paper describes an architecture that integrates the mechanism for the generation and use of approximate results with the traditional checkpointing mechanism. It then describes a system we are currently developing that implements this architecture. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> We describe optimal algorithms for incorporating error recovery in the imprecise computation model. In this model each task comprises a mandatory and an optional part. The mandatory part must be completed within the task's deadline even in the presence of faults and a reward function is associated with the execution of each optional part. We address the problem of optimal scheduling in an imprecise computation environment so as to maximize total reward while simultaneously guaranteeing timely completion of recovery operations when faults occur. Furthermore, in order to prevent run-time overhead we enforce that no changes in the optimal schedule should be necessary as long as no error is detected in mandatory parts. Independent imprecise computation tasks as well as tasks with an end-to-end deadline and linear precedence constraints are considered. We present polynomial-time optimal algorithms for models with upper and lower bounds on execution times of the optional parts and for reward functions represented by general nondecreasing linear and concave functions. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Embedded systems can operate perpetually without being connected to a power source by harvesting environmental energy from motion, the sun, wind, or heat differentials. However, programming these perpetual systems is challenging. In response to changing energy levels, programmers can adjust the execution frequency of energy-intensive tasks, or provide higher service levels when energy is plentiful and lower service levels when energy is scarce. However, it is often difficult for programmers to predict the energy consumption resulting from these adjustments. Worse, explicit energy management can tie a program to a particular hardware platform, limiting portability. This paper introduces Eon, a programming language and runtime system designed to support the development of perpetual systems. To our knowledge, Eon is the first energy-aware programming language. Eon is a declarative coordination language that lets programmers compose programs from components written in C or nesC. Paths through the program ("flows") may be annotated with different energy states. Eon's automatic energy management then dynamically adapts these states to current and predicted energy levels. It chooses flows to execute and adjusts their rates of execution, maximizing the quality of service under available energy constraints. We demonstrate the utility and portability of Eon by deploying two perpetual applications on widely different hardware platforms: a GPS-based location tracking sensor deployed on a threatened species of turtle and on automobiles, and a solar-powered camera sensor for remote, ad-hoc deployments. We also evaluate the simplicity and effectiveness of Eon with a user study, in which novice Eon programmers produced more efficient efficient energy-adaptive systems in substantially less time than experienced C programmers. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Energy-efficient computing is important in several systems ranging from embedded devices to large scale data centers. Several application domains offer the opportunity to tradeoff quality of service/solution (QoS) for improvements in performance and reduction in energy consumption. Programmers sometimes take advantage of such opportunities, albeit in an ad-hoc manner and often without providing any QoS guarantees. We propose a system called Green that provides a simple and flexible framework that allows programmers to take advantage of such approximation opportunities in a systematic manner while providing statistical QoS guarantees. Green enables programmers to approximate expensive functions and loops and operates in two phases. In the calibration phase, it builds a model of the QoS loss produced by the approximation. This model is used in the operational phase to make approximation decisions based on the QoS constraints specified by the programmer. The operational phase also includes an adaptation function that occasionally monitors the runtime behavior and changes the approximation decisions and QoS model to provide strong statistical QoS guarantees. To evaluate the effectiveness of Green, we implemented our system and language extensions using the Phoenix compiler framework. Our experiments using benchmarks from domains such as graphics, machine learning, signal processing, and finance, and an in-production, real-world web search engine, indicate that Green can produce significant improvements in performance and energy consumption with small and controlled QoS degradation. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> We present PowerDial, a system for dynamically adapting application behavior to execute successfully in the face of load and power fluctuations. PowerDial transforms static configuration parameters into dynamic knobs that the PowerDial control system can manipulate to dynamically trade off the accuracy of the computation in return for reductions in the computational resources that the application requires to produce its results. These reductions translate directly into performance improvements and power savings. Our experimental results show that PowerDial can enable our benchmark applications to execute responsively in the face of power caps that would otherwise significantly impair responsiveness. They also show that PowerDial can significantly reduce the number of machines required to service intermittent load spikes, enabling reductions in power and capital costs. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Several recently proposed design techniques leverage the inherent error resilience of applications for improved efficiency (energy or performance). Hardware and software systems that are thus designed may be viewed as "scalable effort systems", since they offer the capability to modulate the effort that they expend towards computation, thereby allowing for tradeoffs between output quality and efficiency. We propose the concept of Dynamic Effort Scaling (DES), which refers to dynamic management of the control knobs that are exposed by scalable effort systems. We argue the need for DES by observing that the degree of resilience often varies significantly across applications, across datasets, and even within a dataset. We propose a general conceptual framework for DES by formulating it as a feedback control problem, wherein the scaling mechanisms are regulated with the goal of maintaining output quality within a certain specified limit. We present an implementation of Dynamic Effort Scaling in the context of a scalable-effort processor for Support Vector Machines, and evaluate it under various application scenarios and data sets. Our results clearly demonstrate the benefits of the proposed approach --- statically setting the scaling mechanisms leads to either significant error overshoot or significant opportunities for energy savings left on the table unexploited. In contrast, DES is able to effectively regulate the output quality while maximally exploiting the time-varying resiliency in the workload. <s> BIB008 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Approximate computing can be employed for an emerging class of applications from various domains such as multimedia, machine learning and computer vision. The approximated output of such applications, even though not 100% numerically correct, is often either useful or the difference is unnoticeable to the end user. This opens up a new design dimension to trade off application performance and energy consumption with output correctness. However, a largely unaddressed challenge is quality control: how to ensure the user experience meets a prescribed level of quality. Current approaches either do not monitor output quality or use sampling approaches to check a small subset of the output assuming that it is representative. While these approaches have been shown to produce average errors that are acceptable, they often miss large errors without any means to take corrective actions. To overcome this challenge, we propose Rumba for online detection and correction of large approximation errors in an approximate accelerator-based computing environment. Rumba employs continuous lightweight checks in the accelerator to detect large approximation errors and then fixes these errors by exact re-computation on the host processor. Rumba employs computationally inexpensive output error prediction models for efficient detection. Computing patterns amenable for approximation (e.g., map and stencil) are usually data parallel in nature and Rumba exploits this property for selective correction. Overall, Rumba is able to achieve 2.1x reduction in output error for an unchecked approximation accelerator while maintaining the accelerator performance gains at the cost of reducing the energy savings from 3.2x to 2.2x for a set of applications from different approximate computing domains. <s> BIB009 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> We present Topaz, a new task-based language for computations that execute on approximate computing platforms that may occasionally produce arbitrarily inaccurate results. Topaz maps tasks onto the approximate hardware and integrates the generated results into the main computation. To prevent unacceptably inaccurate task results from corrupting the main computation, Topaz deploys a novel outlier detection mechanism that recognizes and precisely reexecutes outlier tasks. Outlier detection enables Topaz to work effectively with approximate hardware platforms that have complex fault characteristics, including platforms with bit pattern dependent faults (in which the presence of faults may depend on values stored in adjacent memory cells). Our experimental results show that, for our set of benchmark applications, outlier detection enables Topaz to deliver acceptably accurate results (less than 1% error) on our target approximate hardware platforms. Depending on the application and the hardware platform, the overall energy savings range from 5 to 13 percent. Without outlier detection, only one of the applications produces acceptably accurate results. <s> BIB010 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Embedded sensor platforms can dissipate most of their energy in accessing sensor integrated circuits such as gyroscopes. But the algorithms which process the sensor data and the humans who consume the overall output of the system may often be able to tolerate some amount of error in the retrieved sensor values. Because devices are accessed through interfaces provided by system software, exploiting the tolerable error for improvements in energy efficiency requires appropriate system software and hardware support. However, no such support currently exists. ::: ::: We present Lax, a device driver abstraction for interacting with sensors that enables power savings in exchange for occasionally returning erroneous sensor data. Our implementation on a hardware prototype delivers savings in sensor dynamic power dissipation of up to 48% (as compared to precise device access) while providing sensor access error rates lower than 5 data acquisition errors per 100 data accesses. Given the significant proportion of system energy budgets in wearable platforms that are devoted to sensors, approximate sensor data acquisition using Lax can deliver significant system-level energy savings. <s> BIB011 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> We present Crayon, a library and runtime system that reduces display power dissipation by acceptably approximating displayed images via shape and color transforms. Crayon can be inserted between an application and the display to optimize dynamically generated images before they appear on the screen. It can also be applied offline to optimize stored images before they are retrieved and displayed. Crayon exploits three fundamental properties: the acceptability of small changes in shape and color, the fact that the power dissipation of OLED displays and DLP pico-projectors is different for different colors, and the relatively small energy cost of computation in comparison to display energy usage. We implement and evaluate Crayon in three contexts: a hardware platform with detailed power measurement facilities and an OLED display, an Android tablet, and a set of cross-platform tools. Our results show that Crayon's color transforms can reduce display power dissipation by over 66% while producing images that remain visually acceptable to users. The measured whole-system power reduction is approximately 50%. We quantify the acceptability of Crayon's shape and color transforms with a user study involving over 400 participants and over 21,000 image evaluations. <s> BIB012 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Runtime systems: computation <s> Advancements in deep learning have ignited an explosion of research on efficient hardware for embedded computer vision. Hardware vision acceleration, however, does not address the cost of capturing and processing the image data that feeds these algorithms. We examine the role of the image signal processing (ISP) pipeline in computer vision to identify opportunities to reduce computation and save energy. The key insight is that imaging pipelines should be be configurable: to switch between a traditional photography mode and a low-power vision mode that produces lower-quality image data suitable only for computer vision. We use eight computer vision algorithms and a reversible pipeline simulation tool to study the imaging system's impact on vision performance. For both CNN-based and classical vision algorithms, we observe that only two ISP stages, demosaicing and gamma compression, are critical for task performance. We propose a new image sensor design that can compensate for these stages. The sensor design features an adjustable resolution and tunable analog-to-digital converters (ADCs). Our proposed imaging system's vision mode disables the ISP entirely and configures the sensor to produce subsampled, lower-precision image data. This vision mode can save ~75% of the average energy of a baseline photography mode with only a small impact on vision task accuracy. <s> BIB013
Trading timeliness guarantees for reduced resource usage was heavily explored in the 1990s, in research efforts on imprecise realtime systems BIB004 BIB003 BIB002  BIB001 . Much like the recent resurgence of interest in trading correctness for resource usage, these earlier efforts were targeted at an application domain (embedded systems) where the relaxation of correctness requirements was motivated by the inherent nondeterminism of their operating environments. The Eon system BIB005 provides a declarative language which allows users to annotate components with different energy specifications, which are then used at runtime to select suitable components. Hoffman et al. BIB007 turn static configuration parameters into dynamic knobs which can adjust the accuracy and energy usage of a system at runtime. A calibration pass offline minimizes monitoring overhead at runtime. Similarly, Green BIB006 builds a quality of service model during a calibration phase based on approximations supplied by the programmer. This model is used at runtime to select suitable approximations. Chippa et al. BIB008 propose a general framework which phrases the dynamic management as a feedback system and further suggest different quality measurements at the circuit, architecture, and algorithm level which serve as the feedback signal. Most previous runtime approaches consider average errors or only check the errors occasionally during execution, and can thus miss large outliers. Rumba BIB009 checks all results with light-weight checks and proposes an approximate correction mechanism, which is specific to data-parallel applications. Topaz BIB010 also verifies every result, but at a higher granularity, by decomposing a computation into tasks. Topaz checks each task's output with lightweight checks provided by the user. If the error is too large, Topaz automatically re-executes the corresponding task. 8.3 Runtime systems: sensors, actuation, and displays All measurements have some amount of measurement uncertainty and as a result, sensing systems provide many opportunities for trading errors for improved efficiency. These range from trading accuracy and reliability in sensors in the Lax system BIB011 , to trading precision for fidelity in imaging sensors (cameras) BIB013 , to trading the fidelity of display colors and shapes for reduced display panel power dissipation for OLED displays in Crayon BIB012 .