Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> Technology trends and especially portable applications drive the quest for low-power VLSI design. Solutions that involve algorithmic, structural or physical transformations are sought. The focus is on developing low-power circuits without affecting too much the performance (area, latency, period). For CMOS circuits most power is dissipated as dynamic power for charging and discharging node capacitances. This is why many promising results in low-power design are obtained by minimizing the number of transitions inside the CMOS circuit. While it is generally accepted that because of the large capacitances involved much of the power dissipated by an IC is at the I/O little has been specifically done for decreasing the I/O power dissipation. We propose the bus-invert method of coding the I/O which lowers the bus activity and thus decreases the I/O peak power dissipation by 50% and the I/O average power dissipation by up to 25%. The method is general but applies best for dealing with buses. This is fortunate because buses are indeed most likely to have very large capacitances associated with them and consequently dissipate a lot of power. > <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> This paper contains a tutorial on bus-encoding techniques that target low power dissipation. Three general classes of codes, i.e., algebraic, permutation-based, and probability-based, are reviewed. A new mathematical framework for unifying the power-aware algebraic coding techniques based on the notion of leader sets is also presented. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <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> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> As semiconductor technology scales towards ever-smaller transistor sizes, hardware fault rates are increasing. Since important application classes (e.g., multimedia, streaming workloads) are data-error-tolerant, recent research has proposed techniques that seek to save energy or improve yield by exploiting error tolerance at the architecture/microarchitecture level. Even seemingly error-tolerant applications, however, will crash or hang due to control-flow/memory addressing errors. In parallel computation, errors involving inter-thread communication can have equally catastrophic effects. Our work explores techniques that mitigate the impact of potentially catastrophic errors in parallel computation, while still garnering power, cost, or yield benefits from data error tolerance. Our proposed CommGuard solution uses FSM-based checkers to pad and discard data in order to maintain semantic alignment between program control flow and the data communicated between processors. CommGuard techniques are low overhead and they exploit application information already provided by some parallel programming languages (e.g. StreamIt). By converting potentially catastrophic communication errors into potentially tolerable data errors, CommGuard allows important streaming applications like JPEG and MP3 decoding to execute without crashing and to sustain good output quality, even for errors as frequent as every 500μs. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <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> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <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> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> Off-chip serial buses are common in embedded systems, and due to the long physical lines, can contribute significantly to their energy consumption. However, these buses are often connected to analog sensors, whose data is inherently affected by noise and A/D errors. Thus, communication can tolerate small approximations, without a significant impact on the system outputs quality. In this paper we propose an energy-efficient approximate serial encoding for sensors data, inspired by the T0 technique for parallel buses. Despite its small encoder/decoder overheads, this method is capable of significantly reducing dynamic power (> 90%) in off-chip serial lines, with negligible average error (<1%) on decoded data. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> Mobile, wearable, and implantable devices integrate an increasing number and variety of sensors such as microphones, image sensors, and accelerometers. These devices spend substantial amounts of time reading the sensors within them, thereby incurring significant energy dissipation over off-chip serial interconnects. This paper proposes AXSERBUS, a quality-configurable approximate serial bus that exploits the locality of sensory data and the error resiliency of sensing applications to reduce energy dissipation. AXSERBUS significantly reduces signal transitions by encoding the differentials of sensory data in three encoding modes, depending on the magnitude of the differentials: very small differentials are zeroed out, incurring no energy dissipation; intermediate differentials are encoded using special low-transition count patterns; and for high differentials, the absolute value (not the differential) of the data is transmitted. Compared to previous schemes, the proposed multi-level encoding results in more data being encoded as low-energy patterns. In addition, in the intermediate differential encoding mode, the differentials are encoded in an approximate manner, and the approximation bounds are proportional to the magnitude of the differentials. Since small differentials are more frequent than large differentials in sensory data, the proposed encoding scheme also minimizes quality degradation. We demonstrate that AXSERBUS achieves improved energy vs. quality tradeoffs compared to previous schemes. In the context of an optical character recognition (OCR) application, AXSERBUS achieves 79.4% reduction in dynamic power dissipation, while maintaining accuracy above 95%. <s> BIB008 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> The trend of unsustainable power consumption and large memory bandwidth demands in massively parallel multicore systems, with the advent of the big data era, has brought upon the onset of alternate computation paradigms utilizing heterogeneity, specialization, processor-in-memory and approximation. Approximate Computing is being touted as a viable solution for high performance computation by relaxing the accuracy constraints of applications. This trend has been accentuated by emerging data intensive applications in domains like image/video processing, machine learning and big data analytics that allow inaccurate outputs within an acceptable variance. Leveraging relaxed accuracy for high throughput in Networks-on-Chip (NoCs), which have rapidly become the accepted method for connecting a large number of on-chip components, has not yet been explored. We propose APPROX-NoC, a hardware data approximation framework with an online data error control mechanism for high performance NoCs. APPROX-NoC facilitates approximate matching of data patterns, within a controllable value range, to compress them thereby reducing the volume of data movement across the chip. Our evaluation shows that APPROX-NoC achieves on average up to 9% latency reduction and 60% throughput improvement compared with state-of-the-art NoC data compression mechanisms, while maintaining low application error. Additionally, with a data intensive graph processing application we achieve a 36.7% latency reduction compared to state-of-the-art compression mechanisms. <s> BIB009 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <s> Computational applications are subject to various kinds of numerical errors, ranging from deterministic round-off errors to soft errors caused by non-deterministic bit flips, which do not lead to application failure but corrupt application results. Non-deterministic bit flips are typically mitigated in hardware using various error correcting codes (ECC). But in practice, due to performance and cost concerns, these techniques do not guarantee error-free execution. On large-scale computing platforms, soft errors occur with non-negligible probability in RAM and on the CPU, and it has become clear that applications must tolerate them. For some applications, this tolerance is intrinsic as result quality can remain acceptable even in the presence of soft errors (e.g., data analysis applications, multimedia applications). Tolerance can also be built into the application, resolving data corruptions in software during application execution. By contrast, today's optical networks hold on to a rigid error-free standard, which imposes limits on network performance scalability. In this work we propose high-bandwidth, low-latency approximate networks with the following three features:(1) Optical links that exploit multi-level quadrature amplitude modulation (QAM) for achieving high bandwidth, (2) Avoidance of forward error correction (FEC), which makes optical link error-prone but affords lower latency, and(3) The use of symbol mapping coding between bit sequence and QAM to ensure data integrity that is sufficient for practical soft-error-tolerant applications. Discrete-event simulation results for application benchmarks show that approx networks achieve speedups up to 2.94 when compared to conventional networks. <s> BIB010 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Approximate communication <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> BIB011
As in the case of approximate memory elements, approximate communication systems may perform non-identity transformation f * of input I to efficiently transfer the input through a communication channel or network. The idealized computation function f corresponds to an identity transformation over an infinitely large input. Examples of inputs include signals on intra-and inter-chip wires, such as memory buses and on-chip networks. The architectural techniques trading resource usage for correctness in such systems usually rely on more efficient but less reliable links, network buffers, and other network elements, or employ lossy in-network compression to minimize data movement, while overlapping the compression and communication. The conventional approach to trade resource usage for correctness in communication over a channel is to employ lossy compression at the source and decompression at the destination, with the goal of reducing the amount of data transferred through the channel, as well as to reduce latency. Such approaches have been widely used for decades in long-distance communication, such as media streaming applications. However, when the communicating parties are two processors on a board, two cores on a chip, or a core and a cache, the communication latency is in the order of nanoseconds and any compression/decompression latency added to the critical path of program execution may be prohibitive. At the circuit level, transmitting bits over a wire on-chip or over a printed circuit board trace costs energy. For single-ended I/O interfaces, where the signaling of information is with voltage levels, the energy cost is typically due to the need to charge the wire capacitance when driving a logic '1', and to discharge that capacitance when driving a logic '0'. Building on this observation, and on the body of work on low-power bus encodings BIB002 BIB001 , value-deviation-bounded serial encoding (VDBS encoding) BIB003 BIB005 trades correctness for improved communication energy efficiency by lossy filtering of values to be transmitted on an I/O link. VDBS encoding reduces the number of '0' to '1' and '1' to '0' signal transitions and hence reduces the energy cost of I/O. Because VDBS encoding requires no decoder, it can be implemented with low overhead, requiring less than a thousand gates for a typical implementation BIB006 . Extensions of VDBS encoding have extended the basic concept to exploit temporal information in information streams BIB008 BIB007 and to employ probabilistic encoding techniques BIB011 . A recent study leverages data similarity between cache blocks to perform lossy compression in networks-on-chip (NoCs) BIB009 . The key idea is in simple data-type aware approximation using approximate matching between data to be sent and data items that have been recently sent to perform a quick lossy compression. Performing approximation at the network layer allows a significant data movement reduction without losing the precise copy of the data and without extending the critical path, as the communication and compression are overlapped. An orthogonal approach to trading resource usage for correctness in communication by compression, is to reduce the safety margins of communication links to trade off their reliability for bandwidth, latency, or both. For on-chip networks, achieving reliable transmission in low-latency high-bandwidth interconnects requires features like forward error correction (FEC), but FEC can increase communication latency, by up to three fold in one study BIB010 . An approach to counteract such high overheads is to allow higher bit error rates at the link layer by removing forward error correction or employing a weaker but more efficient error correction mechanisms, with a variable amount of redundancy based on application needs BIB010 . A low-diameter network is one approach to keep the end-to-end bit error rate under control, minimizing the number of hop counts, and thus prevent excessive accumulation of errors BIB010 . Allowing errors in communication can be particularly challenging in parallel programs, which rely on communication for synchronization. In such contexts, failure to deliver correct messages on time can affect control flow and lead to catastrophic results BIB004 . Yetim et al. propose a mechanism to mitigate inter-processor communication errors in parallel programs by converting potentially catastrophic control flow or communication errors into likely tolerable data errors BIB004 . Their main insight is that data errors have much less impact on the application output compared to errors in control flow. Their approach is to monitor inter-processor communication in terms of message count, and to ensure that the number of communicated items is correct, either by dropping excess packets or by generating additional packets with synthetic values. Ensuring the correct number of exchanged messages improves the integrity of control flow in the presence of communication errors and consequently improves the output quality of approximate parallel programs.