Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> This article, based on a study of the characteristics of each step a person takes, describes a reference design using the 3-axis ADXL345 accelerometer in a full-featured pedometer that can recognize and count steps, as well as measure distance, speed, and—to an extent—calories burned. The ADXL345’s proprietary (patent pending), on-chip, 32-level first-in, first-out (FIFO) buffer can store data and operate on it for pedometer applications to minimize host processor intervention, thus saving system power—a big concern for portable devices. Its 13-bit resolution (4 mg/LSB) allows pedometers to even measure low-speed walking (where each step represents about 55 mg of acceleration change) with reasonable accuracy. Understanding the Model From the characteristics that can be used to analyze running or walking, we choose acceleration as the relevant parameter. The three components of motion for an individual (and their related axes) are forward (roll), vertical ( yaw), and side (pitch), as shown in Figure 1. The ADXL345 senses acceleration along its three axes: x, y, and z. The pedometer will be in an unknown orientation, <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> Energy is increasingly a first-order concern in computer systems. Exploiting energy-accuracy trade-offs is an attractive choice in applications that can tolerate inaccuracies. Recent work has explored exposing this trade-off in programming models. A key challenge, though, is how to isolate parts of the program that must be precise from those that can be approximated so that a program functions correctly even as quality of service degrades. We propose using type qualifiers to declare data that may be subject to approximate computation. Using these types, the system automatically maps approximate variables to low-power storage, uses low-power operations, and even applies more energy-efficient algorithms provided by the programmer. In addition, the system can statically guarantee isolation of the precise program component from the approximate component. This allows a programmer to control explicitly how information flows from approximate data to precise data. Importantly, employing static analysis eliminates the need for dynamic checks, further improving energy savings. As a proof of concept, we develop EnerJ, an extension to Java that adds approximate data types. We also propose a hardware architecture that offers explicit approximate storage and computation. We port several applications to EnerJ and show that our extensions are expressive and effective; a small number of annotations lead to significant potential energy savings (10%-50%) at very little accuracy cost. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <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> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> Energy efficiency is a primary constraint in modern systems. Approximate computing is a promising approach that trades quality of result for gains in efficiency and performance. State- of-the-art approximate programming models require extensive manual annotations on program data and operations to guarantee safe execution of approximate programs. The need for extensive manual annotations hinders the practical use of approximation techniques. This paper describes FlexJava, a small set of language extensions, that significantly reduces the annotation effort, paving the way for practical approximate programming. These extensions enable programmers to annotate approximation-tolerant method outputs. The FlexJava compiler, which is equipped with an approximation safety analysis, automatically infers the operations and data that affect these outputs and selectively marks them approximable while giving safety guarantees. The automation and the language–compiler codesign relieve programmers from manually and explicitly an- notating data declarations or operations as safe to approximate. FlexJava is designed to support safety, modularity, generality, and scalability in software development. We have implemented FlexJava annotations as a Java library and we demonstrate its practicality using a wide range of Java applications and by con- ducting a user study. Compared to EnerJ, a recent approximate programming system, FlexJava provides the same energy savings with significant reduction (from 2× to 17×) in the number of annotations. In our user study, programmers spend 6× to 12× less time annotating programs using FlexJava than when using EnerJ. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> Communicating data from sensors such as gyroscopes and accelerometers, to processors, typically occurs over printed circuit board traces. This communication can cost up to 40 µW at data rates of 1 Mb/s. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> Transferring data between integrated circuits (ICs) accounts for an important fraction of the power dissipation in wearable and mobile systems. Reducing signal transitions reduces the dynamic power dissipated in the data transfer between ICs. Techniques such as Gray coding to reduce transitions between two parallel words cannot be applied when the signal transitions are between bits of a single serialized word. This paper introduces value-deviation-bounded serial encoding (VDBS encoding). VDBS encoding significantly reduces signal transitions between bits of a single serialized word, trading power efficiency for data accuracy. This tradeoff is worthwhile when the data are from signal sources such as sensors and destined for consumption by signal processing algorithms that are error-tolerant. We present analytic formulas for the Pareto-optimal VDBS encoders and introduce an efficient algorithm, Rake, that reduces transitions almost as much as the optimum transition-reducing encoder. We evaluate Rake by encoding data in a pedometer system and in a text-recognition system. For the pedometer, Rake reduces transitions by 54% on average, in exchange for step count errors smaller than 5%. For the text recognizer, Rake reduces transitions by 55% on average, while maintaining OCR accuracy above 90 %. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Example: a pedometer application <s> When computing systems can tolerate the effects of errors or erasures in their communicated data values, they can trade this tolerance for improved resource efficiency. One method for enabling this tradeoff in the I/O subsystems of computing systems, is to use channel codes that reduce the power needed to send bits on a channel in exchange for bounded errors and erasures on numeric program values---value-deviation-bounded (VDB) codes. Unlike rate distortion codes, which guarantee a bound on the expected value of channel distortion, the probabilistic VDB codes we present guarantee any desired tail distribution on integer distances of words transmitted over a channel. We extend prior work to present tighter upper bounds on the efficiency for VDB codes. We present a new probabilistic VDB encoder that lowers power dissipation in exchange for bounded channel integer distortions. The code we present takes the peculiar approach of changing the channel bit error rate across the ordinal bit positions in a word to reduce power dissipation. We implement the code table generator in a software tool built on the dReal SMT solver and we validate the generated codes using Monte Carlo simulation. We present one realization of hardware to implement the technique, requiring 2 mm$^2$ of circuit board area and dissipating less than 0.5 $\mu$W. <s> BIB007
Applications which process data measured from the physical world must often contend with noisy inputs. Signals such as temperature, motion, etc., which are analyzed by such sensor-driven systems, are usually the result of multiple interacting phenomena which measurement equipment or sensors can rarely isolate. At the same time, the results of these sensor signal processing applications may not have a rigid reference for correctness. This combination of input noise and output flexibility leads to many sensor signal processing applications having tradeoffs between correctness and resource usage. One concrete example of such an application is a pedometer (step counter). Modern pedometers typically use data from 3-axis accelerometers to determine the number of steps taken during a given period of time. Even when a pedometer's wearer is nominally motionless, these accelerometers will detect some distribution of (noisy) measured acceleration values. At the same time, small errors in the step count reported by a pedometer are often inconsequential and therefore acceptable. Figure 1 shows a block diagram for an implementation of one popular approach BIB001 . Our implementation takes as input 3-axis accelerometer data and returns a step count for time windows of 500 ms. The pedometer algorithm first selects the accelerometer axis with the maximum peakto-peak variation (the maximum activity axis selection block in Figure 1 ). The algorithm uses the selections to create a new composite sequence of accelerometer samples. Next, the pedometer algorithm performs low-pass filtering, and then, for each 500 ms window, computes the maximum and minimum acceleration values and the midpoint of this range (the extremal value marking block in Figure 1) . Finally, the algorithm counts how many times the low-pass filtered signal crosses the per-window midpoints in one direction (e.g., from above the midpoint to below it), and it reports this count as the number of steps. Figure 2 (a-c) show the progression of a sequence of accelerometer samples through the stages of the pedometer algorithm, which outputs a step count of 19 at the end. Figure 2(d-f) show a modified version of the data where we have replaced 5% of the samples with zeros to simulate intermittent failures at a sensor. Even though the data in the final stage of the algorithm (Figure 2 (c) and Figure 2 (f)) looks qualitatively different, the final output of the algorithm is relatively close the noise-free output. Applying individual tradeoffs. The hardware and system stack for a typical pedometer comprises sensors (e.g., accelerometers), I/O links (e.g., SPI or I2C) between those sensors and a processor, a runtime or embedded operating system, the implementation of the pedometer algorithm, and a display. A system's designer may exploit the resource versus correctness tradeoffs at each of these layers or components independently, using the techniques surveyed in Sections 5-8 of this article. (a) All three axes of data (shown low-pass filtered). (b) Maximum activity axes combined across the 500 ms windows. (c) Extremal value marking of the maximum-activity axis data. Step count: 19. All three axes of data with added noise (shown low-pass filtered). (e) Maximum activity axes combined, for data with added noise. (f) Extremal value marking for the data with added noise. Step count: 16. Fig. 2 . Intermediate stages of data from a pedometer application. For example, a system designer could apply Lax BIB003 to sensors, VDBS encoding BIB005 BIB007 BIB006 to the I2C or SPI communication between sensors and a microcontroller, and could ensure that the potentially inexact data does not affect the overall safety of the application using EnerJ BIB002 or FlexJava BIB004 . Potential for end-to-end optimization. This survey argues for exploring the end-to-end combination of techniques for trading correctness for efficiency, across the levels of abstraction of computing systems. Rather than treating each layer of the hardware and system software stack as an independent opportunity, this article argues that greater resource-correctness tradeoffs are possible when the entire system stack is considered end-to-end. For example, the insensitivity of the pedometer algorithm to input noise highlighted in Figure 2 might be determined by program analyses. These analyses could in turn be used to inform instruction selection for generated code as well as determining sensor operating settings (e.g., sampling rate, operating voltage, on-sensor averaging) and sensor I/O settings (e.g., choices for the I/O encoding for the sensor samples as they are transferred from a sensor).