More Web Proxy on the site http://driver.im/

research-article

Approximation-aware rewriting of AIGs for error tolerant applications

Authors:

Arun Chandrasekharan,

Mathias Soeken,

Rolf DrechslerAuthors Info & Claims

2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

Pages 1 - 8

https://doi.org/10.1145/2966986.2967003

Published: 07 November 2016 Publication History

Abstract

Approximation circuits offer superior performance (speed and area) compared to traditional circuits at the cost of computational accuracy. The accuracy of the results in approximation circuits is evaluated based on several error metrics such as worst-case error, bit-flip error, or error-rate. Several applications have varied requirements in error metrics, i.e., all the error criteria have to be met together at a time, or in combinations. Nevertheless, all applications benefit from improved delay and area. An automated synthesis approach with formal guarantees on error metrics is very helpful in generating circuits that meet these criteria. Furthermore, each of these metrics are independent quantities (value of one metric does not correlate with the other), and automated synthesis can discover opportunities to trade off one or more of the relaxed metrics with a strict requirement on the other, resulting in better performance. In this paper, we present an automatic synthesis approach using And-Inverter Graphs (AIGs) based rewriting that not only improves the performance but also guarantees the bounds of approximation errors introduced. Our synthesis approach is evaluated on a wide range of designs and standard benchmark circuits to show the usefulness and applicability. In particular, we show that our synthesis results are even comparable with the optimization achieved with hand crafted adhoc approximation circuits such as approximation adders in a case study on image compression.

References

[1]

Aoki Laboratory-Graduate School of Information Sciences. Tohoku University, 2016. http://www.aoki.ecei.tohoku.ac.jp/arith.

[2]

A. Bernasconi and V. Ciriani. 2-SPP approximate synthesis for error tolerant applications. In EUROMICRO Symposium on DigitalSystem Design, pages 411–418, Aug 2014.

[3]

M. Breuer. Determining error rate in error tolerant VLSI chips. In Electronic Design, Test and Applications, pages 321–326, Jan 2004.

[4]

A. Chandrasekharan, M. Soeken, D. Große, and R. Drechsler. Precise error determination of approximated components in sequential circuits with model checking. In Design Automation Conf., 2016.

[5]

J. Cong and Y. Ding. Combinational logic synthesis for lut based field programmable gate arrays. ACM Trans. Des. Autom. Electron. Syst., 1 (2):145–204, Apr. 1996.

[6]

N. Een. Cut sweeping. Cadence Design Systems, Tech. Rep, 2007.

[7]

GeAr-ApproxAdderLib. Chair for Embedded Systems-Karlsruhe Institute of Technology, 2015. http://ces.itec.kit.edu/1025.php.

[8]

V. Gupta, D. Mohapatra, S. P. Park, A. Raghunathan, and K. Roy. Impact: Imprecise adders for low-power approximate computing. In Low Power Electronics and Design (ISLPED) 2011 InternationalSymposium on, pages 409–414, Aug 2011.

[9]

A. Kahng and S. Kang. Accuracy-configurable adder for approximate arithmetic designs. In Design Automation Conf., pages 820–825, June 2012.

[10]

P. Kulkarni, P. Gupta, and M. Ercegovac. Trading accuracy for power with an underdesigned multiplier architecture. In VLSI Design, pages 346–351, Jan 2011.

[11]

N. Li and E. Dubrova. AIG rewriting using 5-input cuts. In Computer Design (ICCD), 2011 IEEE 29th International Conference on, pages 429–430, Oct 2011.

[12]

A. Lingamneni, C. Enz, J. L. Nagel, K. Palem, and C. Piguet. Energy parsimonious circuit design through probabilistic pruning. In 2011 Design, Automation Test in Europe, pages 1–6, March 2011.

[13]

D. Lundgren. OpenCore JPEG Encoder-Open-Cores community, 2016. http://opencores.org/project.jpegencode.

[14]

S. Malik, A. R. Wang, R. K. Brayton, and A. Sangiovanni-Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In, IEEE InternationalConference on Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers, pages 6–9.

[15]

J. Miao, A. Gerstlauer, and M. Orshansky. Approximate logic synthesis under general error magnitude and frequency constraints. In International Conference on Computer-Aided Design, pages 779–786. IEEE, 2013.

[16]

J. Miao, K. He, A. Gerstlauer, and M. Orshansky. Modeling and synthesis of quality-energy optimal approximate adders. In 2012 IEEE/ACM InternationalConference on Computer-Aided Design (ICCAD), pages 728–735, Nov 2012.

[17]

A. Mishchenko, M. Case, R. K. Brayton, and S. Jang. Scalable and scalably-verifiable sequential synthesis. In International Conference on Computer-Aided Design, pages 234–241, Nov 2008.

[18]

A. Mishchenko, S. Chatterjee, and R. K. Brayton. Dag-aware aig rewriting a fresh look at combinational logic synthesis. In Proceedings of the 43rd Annual Design Automation Conference, DAC ‘06, pages 532–535, New York, NY, USA, 2006. ACM.

[19]

P. Pan and C.-C. Lin. A new retiming-based technology mapping algorithm for LUT-based FPGAs. In Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays, FPGA ‘98, pages 35–42, New York, NY, USA, 1998. ACM.

[20]

A. Ranjan, A. Raha, S. Venkataramani, K. Roy, and A. Raghunathan. ASLAN: Synthesis of approximate sequential circuits. In Design, Automation and Test in Europe, pages 1–6, March 2014.

[21]

M. Shafique, W. Ahmad, R. Hafiz, and J. Henkel. A low latency generic accuracy configurable adder. In Design Automation Conf., pages 1–6, June 2015.

[22]

D. Shin and S. Gupta. Approximate logic synthesis for error tolerant applications. In Design, Automation and Test in Europe, pages 957–960, March 2010.

[23]

D. Shin and S. K. Gupta. A new circuit simplification method for error tolerant applications. In Design, Automation and Test in Europe, pages 1–6, 2011.

[24]

M. Soeken, D. Große, A. Chandrasekharan, and R. Drechsler. BDD minimization for approximate computing. In ASP Design Automation Conf., 2016.

[25]

http://baldur.iti.kit.edu/sat-race-2015/SAT-Race 2015, International Conference on Theory and Applications of Satisfiability Testing, 2015.

[26]

S. Venkataramani, A. Sabne, V. Kozhikkottu, K. Roy, and A. Raghunathan. Salsa: Systematic logic synthesis of approximate circuits. In Design Automation Conf., pages 796–801, June 2012.

[27]

R. Venkatesan, A. Agarwal, K. Roy, and A. Raghunathan. MACACO: modeling and analysis of circuits for approximate computing. In International Conference on Computer-Aided Design, pages 667–673, 2011.

[28]

C. Wolf. Yosys-Yosys Open SYnthesis Suite, 2015. http://www.clifford.at/yosys/about.html.

[29]

S. Yang. Logic synthesis and optimization benchmarks user guide version 3.0, 1991.

[30]

R. Ye, T. Wang, F. Yuan, R. Kumar, and Q. Xu. On reconfiguration-oriented approximate adder design and its application. In International Conference on Computer-Aided Design, pages 48–54, Nov 2013.

[31]

N. Zhu, W. L. Goh, and K. S. Yeo. An enhanced low-power high-speed adder for error-tolerant application. In Integrated Circuits, ISIC ‘09. Proceedings of the 2009 12th InternationalSymposium on, pages 69–72, Dec 2009.

Cited By

Chao WKourfali ALylina NWu JYang JWang CHsieh TWunderlich H(2024)Pattern Generation for Efficient Acceptability Verification of Approximate Circuits2024 International VLSI Symposium on Technology, Systems and Applications (VLSI TSA)10.1109/VLSITSA60681.2024.10546386(1-4)Online publication date: 22-Apr-2024
https://doi.org/10.1109/VLSITSA60681.2024.10546386
Dalloo AJaleel Humaidi AAl Mhdawi AAl-Raweshidy H(2024)Approximate Computing: Concepts, Architectures, Challenges, Applications, and Future DirectionsIEEE Access10.1109/ACCESS.2024.346737512(146022-146088)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3467375
Hanif MMrazek VShafique M(2024)Approximate Computing ArchitecturesHandbook of Computer Architecture10.1007/978-981-97-9314-3_27(1027-1067)Online publication date: 21-Dec-2024
https://doi.org/10.1007/978-981-97-9314-3_27
Show More Cited By

Index Terms

Approximation-aware rewriting of AIGs for error tolerant applications
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
    2. Logic synthesis
  2. Integrated circuits
    1. Logic circuits

Index terms have been assigned to the content through auto-classification.

Recommendations

2-SPP Approximate Synthesis for Error Tolerant Applications
DSD '14: Proceedings of the 2014 17th Euromicro Conference on Digital System Design

We propose an approximate logic synthesis heuristic for synthesizing a 2-SPP circuit under a given error rate threshold. 2-SPP circuits are three-level EXOR-AND-OR forms with EXOR gates restricted to fan-in 2. They represent a direct generalization of ...
Designs of Approximate Floating-Point Multipliers with Variable Accuracy for Error-Tolerant Applications

Approximate/inexact computing has become an attractive approach for designing high performance and low power arithmetic circuits. Floating-point (FLP) arithmetic is required in many applications, such as digital signal processing, image processing and ...
Approximate logic synthesis for error tolerant applications
DATE '10: Proceedings of the Conference on Design, Automation and Test in Europe

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

Nov 2016

946 pages

Copyright © 2016.

Publisher

IEEE Press

Publication History

Published: 07 November 2016

Permissions

Request permissions for this article.

Request Permissions

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
103
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chao WKourfali ALylina NWu JYang JWang CHsieh TWunderlich H(2024)Pattern Generation for Efficient Acceptability Verification of Approximate Circuits2024 International VLSI Symposium on Technology, Systems and Applications (VLSI TSA)10.1109/VLSITSA60681.2024.10546386(1-4)Online publication date: 22-Apr-2024
https://doi.org/10.1109/VLSITSA60681.2024.10546386
Dalloo AJaleel Humaidi AAl Mhdawi AAl-Raweshidy H(2024)Approximate Computing: Concepts, Architectures, Challenges, Applications, and Future DirectionsIEEE Access10.1109/ACCESS.2024.346737512(146022-146088)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3467375
Hanif MMrazek VShafique M(2024)Approximate Computing ArchitecturesHandbook of Computer Architecture10.1007/978-981-97-9314-3_27(1027-1067)Online publication date: 21-Dec-2024
https://doi.org/10.1007/978-981-97-9314-3_27
Meng CSun JMai YQian W(2023)MECALS: A Maximum Error Checking Technique for Approximate Logic Synthesis2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10136950(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10136950
Barbareschi MBarone SMazzocca NMoriconi A(2023)A Catalog-Based AIG-Rewriting Approach to the Design of Approximate ComponentsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2022.317050211:1(70-81)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TETC.2022.3170502
Meng CZhou ZYao YHuang SChen YQian W(2023)HEDALS: Highly Efficient Delay-Driven Approximate Logic SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.326822142:11(3491-3504)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3268221
Li LLi RHa Y(2023)A Recursion and Lock Free GPU-Based Logic Rewriting Framework Exploiting Both Intranode and Internode ParallelismIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.325174142:11(3972-3984)Online publication date: Nov-2023
https://doi.org/10.1109/TCAD.2023.3251741
Rezaalipour MFerretti LScarabottolo IConstantinides GPozzi L(2023)Multi-Metric SMT-Based Evaluation of Worst-Case-Error for Approximate Circuits2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W)10.1109/DSN-W58399.2023.00055(199-202)Online publication date: Jun-2023
https://doi.org/10.1109/DSN-W58399.2023.00055
Rezaalipour MBiasion MScarabottolo IConstantinides GPozzi L(2023)A Parametrizable Template for Approximate Logic Synthesis2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W)10.1109/DSN-W58399.2023.00049(175-178)Online publication date: Jun-2023
https://doi.org/10.1109/DSN-W58399.2023.00049
Heil AKeszocze O(2023)Fast AIG-Based Approximate Logic SynthesisAdvanced Boolean Techniques10.1007/978-3-031-28916-3_2(17-32)Online publication date: 24-Feb-2023
https://doi.org/10.1007/978-3-031-28916-3_2
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents