Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Adders are one of the key components in arithmetic circuits. Enhancing their performance can significantly improve the quality of arithmetic designs. This is the reason why the theoretical lower bounds on the delay and area of an adder have been analysed, and circuits with performance close to these bounds have been designed. In this paper, we present a novel adder design that is exponentially faster than traditional adders; however, it produces incorrect results, deterministically, for a very small fraction of input combinations. We have also constructed a reliable version of this adder that can detect and correct mistakes when they occur. This creates the possibility of a variable-latency adder that produces a correct result very fast with extremely high probability; however, in some rare cases when an error is detected, the correction term must be applied and the correct result is produced after some time. Since errors occur with extremely low probability, this new type of adder is significantly faster than state-of-the-art adders when the overall latency is averaged over many additions. <s> BIB001 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Error tolerance formally captures the notion that -- for a wide variety of applications including audio, video, graphics, and wireless communications -- a defective chip that produces erroneous values at its outputs may be acceptable, provided the errors are of certain types and their severities are within application-specified thresholds. All previous research on error tolerance has focused on identifying such defective but acceptable chips during post-fabrication testing to improve yield. In this paper, we explore a completely new approach to exploit error tolerance based on the following observation: If certain deviations from the nominal output values are acceptable, then we can exploit this flexibility during circuit design to reduce circuit area and delay as well as to increase yield. The specific metric of error tolerance we focus on is error rate, i.e., how often the circuit produces erroneous outputs. We propose a new logic synthesis approach for the new problem of identifying how to exploit a given error rate threshold to maximally reduce the area of the synthesized circuit. Experiment results show that for an error rate threshold within 1%, our approach provides 9.43% literal reductions on average for all the benchmarks that we target. <s> BIB002 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> In modern VLSI technology, the occurrence of all kinds of errors has become inevitable. By adopting an emerging concept in VLSI design and test, error tolerance (ET), a novel error-tolerant adder (ETA) is proposed. The ETA is able to ease the strict restriction on accuracy, and at the same time achieve tremendous improvements in both the power consumption and speed performance. When compared to its conventional counterparts, the proposed ETA is able to attain more than 65% improvement in the Power-Delay Product (PDP). One important potential application of the proposed ETA is in digital signal processing systems that can tolerate certain amount of errors. <s> BIB003 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> The conventional digital hardware computational blocks with different structures are designed to compute the precise results of the assigned calculations. The main contribution of our proposed Bio-inspired Imprecise Computational blocks (BICs) is that they are designed to provide an applicable estimation of the result instead of its precise value at a lower cost. These novel structures are more efficient in terms of area, speed, and power consumption with respect to their precise rivals. Complete descriptions of sample BIC adder and multiplier structures as well as their error behaviors and synthesis results are introduced in this paper. It is then shown that these BIC structures can be exploited to efficiently implement a three-layer face recognition neural network and the hardware defuzzification block of a fuzzy processor. <s> BIB004 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Contrary to the existing techniques to realize inexact circuits that relied mostly on scaling of supply voltage or pruning of "least-significant" components in conventional correct circuits to achieve cost (energy, delay and/or area) and accuracy tradeoffs, we propose a novel technique called Probabilistic Logic Minimization which relies on synthesizing an inexact circuit in the first place resulting in zero hardware overhead. Extensive simulations of the datapath elements designed using the proposed technique demonstrate that normalized gains as high as 2X- 9.5X in the Energy-Delay-Area product can be obtained when compared to the corresponding correct designs, with a relative error magnitude percentage as low as 0.001% upto 1%. <s> BIB005 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> We propose a novel multiplier architecture with tunable error characteristics, that leverages a modified inaccurate 2x2 building block. Our inaccurate multipliers achieve an average power saving of 31.78% ? 45.4% over corresponding accurate multiplier designs, for an average error of 1.39%?3.32%. Using image filtering and JPEG compression as sample applications we show that our architecture can achieve 2X - 8X better Signal-Noise-Ratio (SNR) for the same power savings when compared to recent voltage over-scaling based power-error tradeoff methods. We project the multiplier power savings to bigger designs highlighting the fact that the benefits are strongly design dependent. We compare this circuit-centric approach to power quality tradeoffs with a pure software adaptation approach for a JPEG example. We also enhance the design to allow for correct operation of the multiplier using a residual adder, for non error resilient applications. <s> BIB006 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Recent interest in approximate computation is driven by its potential to achieve large energy savings. This paper formally demonstrates an optimal way to reduce energy via voltage over-scaling at the cost of errors due to timing starvation in addition. We identify a fundamental trade-off between error frequency and error magnitude in a timing-starved adder. We introduce a formal model to prove that for signal processing applications using a quadratic signal-to-noise ratio error measure, reducing bit-wise error frequency is sub-optimal. Instead, energy-optimal approximate addition requires limiting maximum error magnitude. Intriguingly, due to possible error patterns, this is achieved by reducing carry chains significantly below what is allowed by the timing budget for a large fraction of sum bits, using an aligned, fixed internal-carry structure for higher significance bits. We further demonstrate that remaining approximation error is reduced by realization of conditional bounding (CB) logic for lower significance bits. A key contribution is the formalization of an approximate CB logic synthesis problem that produces a rich space of Pareto-optimal adders with a range of quality-energy tradeoffs. We show how CB logic can be customized to result in over-and under-estimating approximate adders, and how a dithering adder that mixes them produces zero-centered error distributions, and, in accumulation, a reduced-variance error. We demonstrate synthesized approximate adders with energy up to 60% smaller than that of a conventional timing-starved adder, where a 30% reduction is due to the superior synthesis of inexact CB logic. When used in a larger system implementing an image-processing algorithm, energy savings of 40% are possible. <s> BIB007 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Approximation can increase performance or reduce power consumption with a simplified or inaccurate circuit in application contexts where strict requirements are relaxed. For applications related to human senses, approximate arithmetic can be used to generate sufficient results rather than absolutely accurate results. Approximate design exploits a tradeoff of accuracy in computation versus performance and power. However, required accuracy varies according to applications, and 100% accurate results are still required in some situations. In this paper, we propose an accuracy-configurable approximate (ACA) adder for which the accuracy of results is configurable during runtime. Because of its configurability, the ACA adder can adaptively operate in both approximate (inaccurate) mode and accurate mode. The proposed adder can achieve significant throughput improvement and total power reduction over conventional adder designs. It can be used in accuracy-configurable applications, and improves the achievable tradeoff between performance/power and quality. The ACA adder achieves approximately 30% power reduction versus the conventional pipelined adder at the relaxed accuracy requirement. <s> BIB008 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Approximate computing has emerged as a new design paradigm that exploits the inherent error resilience of a wide range of application domains by allowing hardware implementations to forsake exact Boolean equivalence with algorithmic specifications. A slew of manual design techniques for approximate computing have been proposed in recent years, but very little effort has been devoted to design automation. We propose SALSA, a Systematic methodology for Automatic Logic Synthesis of Approximate circuits. Given a golden RTL specification of a circuit and a quality constraint that defines the amount of error that may be introduced in the implementation, SALSA synthesizes an approximate version of the circuit that adheres to the pre-specified quality bounds. We make two key contributions: (i) the rigorous formulation of the problem of approximate logic synthesis, enabling the generation of circuits that are correct by construction, and (ii) mapping the problem of approximate synthesis into an equivalent traditional logic synthesis problem, thereby allowing the capabilities of existing synthesis tools to be fully utilized for approximate logic synthesis. In order to achieve these benefits, SALSA encodes the quality constraints using logic functions called Q-functions, and captures the flexibility that they engender as Approximation Don't Cares (ADCs), which are used for circuit simplification using traditional don't care based optimization techniques. We have implemented SALSA using two off-the-shelf logic synthesis tools - SIS and Synopsys Design Compiler. We automatically synthesize approximate circuits ranging from arithmetic building blocks (adders, multipliers, MAC) to entire datapaths (DCT, FIR, IIR, SAD, FFT Butterfly, Euclidean distance), demonstrating scalability and significant improvements in area (1.1X to 1.85X for tight error constraints, and 1.2X to 4.75X for relaxed error constraints) and power (1.15X to 1.75X for tight error constraints, and 1.3X to 5.25X for relaxed error constraints). <s> BIB009 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Recent interest in approximate circuit design is driven by its potential for large energy savings. In this paper, we address the problem of approximate logic synthesis (ALS). ALS is concerned with formally synthesizing a minimum-cost approximate Boolean network whose behavior deviates in a well-defined manner from a specified exact Boolean function, where in this work, we allow the deviation to be constrained by both the magnitude and frequency of the error. We make two contributions in solving this general ALS problem: The first contribution is to establish that the approximate synthesis problem un-constrained by the frequency of errors is isomorphic with the Boolean relations (BR) minimization problem. That equivalence allows us to exploit recently developed fast algorithms for BR problems to solve the error magnitude-only constrained ALS problem. The second contribution is an efficient heuristic algorithm for iteratively refining the magnitude-constrained solution to arrive at a solution also satisfying the error frequency constraint. Our combined greedy approximate logic synthesis (GALS) approach is able to operate on any Boolean network for which the deviation measures can be specified and is most immediately applicable to arithmetic blocks. Experiments on adder and multiplier blocks demonstrate literal count reductions of up to 60% under tight error frequency and magnitude constraints. <s> BIB010 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Low power is an imperative requirement for portable multimedia devices employing various signal processing algorithms and architectures. In most multimedia applications, human beings can gather useful information from slightly erroneous outputs. Therefore, we do not need to produce exactly correct numerical outputs. Previous research in this context exploits error resiliency primarily through voltage overscaling, utilizing algorithmic and architectural techniques to mitigate the resulting errors. In this paper, we propose logic complexity reduction at the transistor level as an alternative approach to take advantage of the relaxation of numerical accuracy. We demonstrate this concept by proposing various imprecise or approximate full adder cells with reduced complexity at the transistor level, and utilize them to design approximate multi-bit adders. In addition to the inherent reduction in switched capacitance, our techniques result in significantly shorter critical paths, enabling voltage scaling. We design architectures for video and image compression algorithms using the proposed approximate arithmetic units and evaluate them to demonstrate the efficacy of our approach. We also derive simple mathematical models for error and power consumption of these approximate adders. Furthermore, we demonstrate the utility of these approximate adders in two digital signal processing architectures (discrete cosine transform and finite impulse response filter) with specific quality constraints. Simulation results indicate up to 69% power savings using the proposed approximate adders, when compared to existing implementations using accurate adders. <s> BIB011 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Approximate computing leverages the intrinsic resilience of applications to inexactness in their computations, to achieve a desirable trade-off between efficiency (performance or energy) and acceptable quality of results. To broaden the applicability of approximate computing, we propose quality programmable processors, in which the notion of quality is explicitly codified in the HW/SW interface, i.e., the instruction set. The ISA of a quality programmable processor contains instructions associated with quality fields to specify the accuracy level that must be met during their execution. We show that this ability to control the accuracy of instruction execution greatly enhances the scope of approximate computing, allowing it to be applied to larger parts of programs. The micro-architecture of a quality programmable processor contains hardware mechanisms that translate the instruction-level quality specifications into energy savings. Additionally, it may expose the actual error incurred during the execution of each instruction (which may be less than the specified limit) back to software. As a first embodiment of quality programmable processors, we present the design of Quora, an energy efficient, quality programmable vector processor. Quora utilizes a 3-tiered hierarchy of processing elements that provide distinctly different energy vs. quality trade-offs, and uses hardware mechanisms based on precision scaling with error monitoring and compensation to facilitate quality programmable execution. We evaluate an implementation of Quora with 289 processing elements in 45nm technology. The results demonstrate that leveraging quality-programmability leads to 1.05×–1.7× savings in energy for virtually no loss (< 0.5%) in application output quality, and 1.18×–2.1× energy savings for modest impact (<2.5%) on output quality. Our work suggests that quality programmable processors are a significant step towards bringing approximate computing to the mainstream. <s> BIB012 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Approximate computing has been recognized as an effective low power technique for applications with intrinsic error tolerance, such as image processing and machine learning. Existing efforts on this front are mostly focused on approximate circuit design, approximate logic synthesis or processor architecture approximation techniques. This work aims at how to make good use of approximate circuits at system and block level. In particular, approximation aware scheduling, functional unit allocation and binding algorithms are developed for data intensive applications. Simple yet credible error models, which are essential for precision control in the optimizations, are investigated. The algorithms are further extended to include bitwidth optimization in fixed point computations. Experimental results, including those from Verilog simulations, indicate that the proposed techniques facilitate desired energy savings under latency and accuracy constraints. <s> BIB013 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> A multiplier has a significant impact on the speed and power dissipation of an arithmetic processor. Precise results are not always required in many algorithms, such as those for classification and recognition in data processing. Moreover, many errors do not make an obvious difference in applications such as image processing due to the perceptual limitations of human beings. Error-tolerant algorithms and applications have promoted the development of approximate multipliers to tradeoff accuracy for speed, implementation area and/or power efficiency. This paper briefly reviews the current designs of approximate multipliers and provides a comparative evaluation of their error and circuit characteristics. Image sharpening is performed using the considered approximate multipliers to assess their performance in such applications. <s> BIB014 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> This paper presents an architectural-space exploration methodology for designing approximate multipliers. Unlike state-of-the-art, our methodology generates various design points by adapting three key parameters: (1) different types of elementary approximate multiply modules, (2) different types of elementary adder modules for summing the partial products, and (3) selection of bits for approximation in a wide-bit multiplier design. Generation and exploration of such a design space enables a wide-range of multipliers with varying approximation levels, each exhibiting distinct area, power, and output quality, and thereby facilitates approximate computing at higher abstraction levels. We synthesized our designs using Synopsys Design Compiler with a TSMC 45nm technology library and verified using ModelSim gate-level simulations. Power and quality evaluations for various designs are performed using PrimeTime and behavioral models, respectively. The selected designs are then deployed in a JPEG application. For reproducibility and to facilitate further research and development at higher abstraction layers, we have released the RTL and behavioral models of these approximate multipliers and adders as an open-source library at https://sourceforge.net/projects/lpaclib/. <s> BIB015 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Energy-efficiency is a critical concern for many systems, ranging from Internet of things objects and mobile devices to high-performance computers. Moreover, after 40 years of prosperity, Moore’s law is starting to show its economic and technical limits. Noticing that many circuits are over-engineered and that many applications are error-resilient or require less precision than offered by the existing hardware, approximate computing has emerged as a potential solution to pursue improvements of digital circuits. In this regard, a technique to systematically tradeoff accuracy in exchange for area, power, and delay savings in digital circuits is proposed: gate-level pruning (GLP). A CAD tool is build and integrated into a standard digital flow to offer a wide range of cost-accuracy tradeoffs for any conventional design. The methodology is first demonstrated on adders, achieving up to 78% energy-delay-area reduction for 10% mean relative error. It is then detailed how this methodology can be applied on a more complex system composed of a multitude of arithmetic blocks and memory: the discrete cosine transform (DCT), which is a key building block for image and video processing applications. Even though arithmetic circuits represent less than 4% of the entire DCT area, it is shown that the GLP technique can lead to 21% energy-delay-area savings over the entire system for a reasonable image quality loss of 24 dB. This significant saving is achieved thanks to the pruned arithmetic circuits, which sets some nodes at constant values, enabling the synthesis tool to further simplify the circuit and memory. <s> BIB016 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> In recent years, approximate computing has emerged as a promising approach to trade off quality of computed outputs for energy savings. In this paper, we present an approximate high-level synthesis (AHLS) approach that outputs a quality-energy optimized register-transfer-level implementation from an accurate high-level C description. Existing AHLS work only considers switching activity for energy savings under hardware approximations. By contrast, we aim to provide a general AHLS solution that also considers voltage scaling given a reduced processing time. To maximize voltage and associated energy reductions, we include both operation-level approximations by bit rounding and more aggressive operation eliminations as approximation techniques. Optimally exploiting scaling opportunities under such approximations requires tight interaction with scheduling tasks. We address this problem by combining an optimization pass that estimates the scheduling impact of approximations with fast yet accurate quality-energy models and an efficient optimization solver to find near-optimal solutions constructively. Results show that when considering voltage scaling, up to 24.5% higher energy savings can be achieved compared to approaches that only consider switching activity. Our heuristic solver is able to find solutions within 0.1% of average energy savings compared to an exhaustive search, all while being up to 1,400 χ faster than simulation-based methods. <s> BIB017 </s> Exploiting Errors for Efficiency: A Survey from Circuits to Algorithms <s> Pruned circuits for efficiency at the expense of precision and accuracy <s> Numerous application domains (e.g., signal and image processing, computer graphics, computer vision, and machine learning) are inherently error tolerant, which can be exploited to produce approximate ASIC implementations with low power consumption at the expense of negligible or small reductions in application quality. A major challenge is the need for approximate and high-level design generation tools that can automatically work on arbitrary designs. In this article, we provide an expanded and improved treatment of our ABACUS methodology, which aims to automatically generate approximate designs directly from their behavioral register-transfer level (RTL) descriptions, enabling a wider range of possible approximations. ABACUS starts by creating an abstract syntax tree (AST) from the input behavioral RTL description of a circuit, and then applies variant operators to the AST to create acceptable approximate designs. The devised variant operators include data type simplifications, arithmetic operation approximations, arithmetic expressions transformations, variable-to-constant substitutions, and loop transformations. A design space exploration technique is devised to explore the space of possible variant approximate designs and to identify the designs along the Pareto frontier that represents the trade-off between accuracy and power consumption. In addition, ABACUS prioritizes generating approximate designs that, when synthesized, lead to circuits with simplified critical paths, which are exploited to realize complementary power savings through standard voltage scaling. We integrate ABACUS with a standard ASIC design flow, and evaluate it on four realistic benchmarks from three different domains—machine learning, signal processing, and computer vision. Our tool automatically generates many approximate design variants with large power savings, while maintaining good accuracy. We demonstrate the scalability of ABACUS by parallelizing the flow and use of recent standard synthesis tools. Compared to our previous efforts, the new ABACUS tool provides up to 20.5× speed-up in runtime, while able to generate approximate circuits that lead to additional power savings reaching up to 40 percent. <s> BIB018
Pruning circuits refers to deleting or simplifying parts of a circuit based on the probability of their usage or importance to output quality. Recent research has shown how circuit pruning improves latency, energy, and area without the overheads associated with voltage scaling BIB005 BIB010 BIB016 BIB002 . Pruning can be applied to digital circuit building blocks such as adders and multipliers, enabling quality-cost tradeoff opportunities through different logic simplification and pruning techniques. Approximate adders attempt to simplify carry chains BIB001 BIB003 or to use approximate 1-bit full adders BIB011 BIB004 BIB007 at lower significant digits of a sum computation. Accuracy-configurable adders have also been proposed for adaptive-accuracy systems that require a functional unit like an adder or multiplier to vary the degree of tradeoff between correctness and resource usage based on the quality demand of computation BIB008 . Unlike approximate adders, approximate multipliers have a higher design space exploration requirement, as they are composed of 2×2 partial products that are summed up by deploying an adder tree to compute the final result BIB006 . Correctness versus resource usage tradeoffs can be deployed in multipliers (partial products) or adders, or both, for a chosen number of least-significant bits BIB014 BIB015 . Approximate adders and multipliers provide the combinational building blocks for approximate datapath and processor designs. At the sequential logic level, the challenge is in determining the amount of approximation to apply to each addition or multiplication operation in a larger computation in order to minimize output quality loss while maximizing energy savings. For example, in a larger computation that consists of multiple accumulations, using an adder with a zero-centered error distribution BIB007 will result in positive and negative errors canceling each other and thus averaging in the final output of a larger accumulation. By contrast, in other computations, an approximate adder that always over-or under-estimates may be beneficial. Determining the best tradeoff for each functional unit has been investigated for fixed register transfer level (RTL) designs BIB018 BIB009 . Pure RTL optimizations, on the other hand, do not exploit changes in approximated component characteristics for a complete RTL re-design. In the context of custom hardware/accelerator designs, selection of optimal approximated operator implementations can instead be folded into existing C-to-RTL high-level synthesis (HLS) tools BIB017 BIB013 . For programmable processors, accuracy configuration of the datapath can be exposed through the instruction-set architecture (ISA) BIB012 . A compiler then has to determine the precision of each operation in a given application (see Section 6 and Section 7).