ABSTRACT
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).
- Y. K. Chen, J. Chhugani, P. Dubey, C. J. Hughes, D. Kim, S. Kumar, V. W. Lee, A. D. Nguyen, and M. Smelyanskiy. Convergence of recognition, mining, and synthesis workloads and its implications. Proc. IEEE, 96(5):790--807, May 2008.Google ScholarCross Ref
- S. T. Chakradhar and A. Raghunathan. Best-effort computing: Re-thinking parallel software and hardware. In Proc. DAC, pages 865--870, June 2010. Google ScholarDigital Library
- M. A. Breuer. Multi-media applications and imprecise computation. In Proc. Euromicro Conf. on Digital System Design, pages 2--7, Aug.- Sept. 2005. Google ScholarDigital Library
- K. Palem et. al. Sustaining moore's law in embedded computing through probabilistic and approximate design: Retrospects and prospects. In Proc. CASES, pages 1--10, 2009. Google ScholarDigital Library
- L. Leem, H. Cho, J. Bau, Q. A. Jacobson, and S. Mitra. ERSA: Error resilient system architecture for probabilistic applications. In Proc. DATE '10, pages 1560--1565, Mar. 2010. Google ScholarDigital Library
- H. Hoffmann et. al. Dynamic knobs for responsive power-aware computing. In Proc. ASPLOS, pages 199--212, 2011. Google ScholarDigital Library
- V. K. Chippa, D. Mohapatra, A. Raghunathan, K. Roy, and S. T. Chakradhar. Scalable effort hardware design: Exploiting algorithmic resilience for energy efficiency. In Proc. DAC, pages 555--560, June 2010. Google ScholarDigital Library
- R. Hegde and N. R. Shanbhag. Energy-efficient signal processing via algorithmic noise-tolerance. In Proc. ISLPED, pages 30--35, 1999. Google ScholarDigital Library
- V. Gupta, D. Mohapatra, S. P. Park, A. Raghunathan, and K. Roy. IMPACT: Imprecise adders for low-power approximate computing. In Proc. ISLPED 2011, pages 409--414, Aug. 2011. Google ScholarDigital Library
- D. Shin and S. K. Gupta. A re-design technique for datapath modules in error tolerant applications. In Proc. ATS, pages 431--437, Nov. 2008. Google ScholarDigital Library
- P. Kulkarni, P. Gupta, and M. Ercegovac. Trading accuracy for power with an underdesigned multiplier architecture. In Proc. VLSI Design, pages 346--351, Jan. 2011. Google ScholarDigital Library
- A. B. Kahng, S. Kang, R. Kumar, and J. Sartori. Slack redistribution for graceful degradation under voltage overscaling. In Proc. ASP-DAC, pages 825--831, Jan. 2010. Google ScholarDigital Library
- R. Venkatesan, A. Agarwal, K. Roy, and A. Raghunathan. MACACO: Modeling and analysis of circuits for approximate computing. In Proc. ICCAD, pages 667--673, Nov. 2011. Google ScholarDigital Library
- D. Shin and S. K. Gupta. Approximate logic synthesis for error tolerant applications. In Proc. DATE, pages 957--960, Mar. 2010. Google ScholarDigital Library
- D. Shin and S. K. Gupta. A new circuit simplification method for error tolerant applications. In Proc. DATE, Mar. 2011.Google Scholar
- A. Lingamneni, C. Enz, J.-L. Nagel, K. Palem, and C. Piguet. Energy parsimonious circuit design through probabilistic pruning. In Proc. DATE, 2011, Mar. 2011.Google ScholarCross Ref
- Giovanni De Micheli. Synthesis and Optimization of Digital Circuits. McGraw-Hill Higher Education, 1st edition, 1994. Google ScholarDigital Library
- H. Savoj and R. K. Brayton. The use of observability and external don't cares for the simplification of multi-level networks. In Proc. DAC, pages 297--301, 1990. Google ScholarDigital Library
- K. H. Chang, V. Bertacco, I. L. Markov, and A. Mishchenko. Logic synthesis and circuit customization using extensive external don't-cares. ACM TODAES, 15:26:1--26:24, June 2010. Google ScholarDigital Library
- S. C. Chang and M. M. Sadowska. Perturb and simplify: optimizing circuits with external don't cares. In Proc. ED TC, pages 402--406, mar 1996. Google ScholarDigital Library
- E. M. Sentovich and K. J. Singh. SIS: A system for sequential circuit synthesis. Technical report, EECS, UCB, 1992.Google Scholar
- Design Compiler. Synopsys inc.Google Scholar
Index Terms
- SALSA: systematic logic synthesis of approximate circuits
Recommendations
Substitute-and-simplify: a unified design paradigm for approximate and quality configurable circuits
DATE '13: Proceedings of the Conference on Design, Automation and Test in EuropeMany applications are inherently resilient to in-exactness or approximations in their underlying computations. Approximate circuit design is an emerging paradigm that exploits this inherent resilience to realize hardware implementations that are highly ...
ASLAN: synthesis of approximate sequential circuits
DATE '14: Proceedings of the conference on Design, Automation & Test in EuropeMany applications produce acceptable results when their underlying computations are executed in an approximate manner. For such applications, approximate circuits enable hardware implementations that exhibit improved efficiency for a given quality. ...
Systematic synthesis of approximate adders and multipliers with accurate error calculations
AbstractIn this study, we perform logic synthesis and area optimization of approximate ripple-carry adders and Wallace-tree multipliers with a given error constraint. We first implement approximate 1-bit adders having different error rates as ...
Highlights- Logic synthesis and area optimization of approximate ripple-carry adders and Wallace-tree multipliers is presented.
Comments