Error metrics determination in functionally approximated circuits using SAT solvers
Autoři:
Sa’ed Abed aff001; Ali A. M. R. Behiry aff001; Imtiaz Ahmad aff001
Působiště autorů:
Computer Engineering Department, College of Engineering and Petroleum, Kuwait University, Kuwait, Kuwait
aff001
Vyšlo v časopise:
PLoS ONE 15(1)
Kategorie:
Research Article
doi:
https://doi.org/10.1371/journal.pone.0227745
Souhrn
Approximate computing is an emerging design paradigm that offers trade-offs between output accuracy and computation efforts by exploiting some applications’ intrinsic error resiliency. Computation of error metrics is of paramount importance in approximate circuits to measure the degree of approximation. Most of the existing techniques for evaluating error metrics apply simulations which may not be effective for evaluation of large complex designs because of an immense increase in simulation runtime and a decrease in accuracy. To address these deficiencies, we present a novel methodology that employs SAT (Boolean satisfiability) solvers for fast and accurate determination of error metrics specifically for the calculation of an average-case error and the maximum error rate in functionally approximated circuits. The proposed approach identifies the set of all errors producing assignments to gauge the quality of approximate circuits for real-life applications. Additionally, the proposed approach provides a test generation method to facilitate design choices, and acts as an important guide to debug the approximate circuits to discover and locate the errors. The effectiveness of the approach is demonstrated by evaluating the error metrics of several benchmark-approximated adders of different sizes. Experimental results on benchmark circuits show that the proposed SAT-based methodology accurately determines the maximum error rate and an average-case error within acceptable CPU execution time in one go, and further provides a log of error-generating input assignments.
Klíčová slova:
Algorithms – Computing methods – Electrical circuits – Electrical faults – Logic circuits – Monte Carlo method – Probability distribution – Simulation and modeling
Zdroje
1. Mittal S. A survey of techniques for approximate computing. ACM Computing Surveys. 2016; 48(4): 62:1–62:33.
2. Chippa VK, Chakradhar ST, Roy K, Raghunathan A. Analysis and characterization of inherent application resilience for approximate computing. 50th ACM/EDAC/IEEE Design Automation Conference (DAC), Austin, TX, 2013; 1–9. doi: 10.1145/2463209.2488873
3. Keszocze O, Soeken M, Drechsler R. The complexity of error metrics. Information Processing Letters, 2018; 139: 1–7.
4. Holik L, Lengal O, Rogalewicz A, Sekanina L, Vasicek Z, Vojnar T. Towards formal relaxed equivalence checking in approximate computing methodology. 2nd Workshop on Approximate Computing (WAPCO 2016), 2016; HiPEAC, 1–6.
5. Chandrasekharan A, Soeken M, Große D, Drechsler R. Precise error determination of approximated components in sequential circuits with model checking. Proceedings of the 53rd Annual Design Automation Conference (DAC '16), Austin, Texas, ACM, NY, USA, 2016; Article 129, 1–6.
6. Lingamneni A, Enz C, Nagel JL, Palem K, Piguet C. Energy parsimonious circuit design through probabilistic pruning. Design, Automation & Test in Europe, Grenoble, 2011; 1–6.
7. Han J, Orshansky M. Approximate computing: An emerging paradigm for energy-efficient design. 18th IEEE European Test Symposium (ETS), Avignon, 2013: 1–6.
8. Yu C; Ciesielski M. Analyzing imprecise adders using BDDs—A Case Study. IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Pittsburgh, PA, 2016; 152–157.
9. Gebregiorgis A, Tahoori MB. Test pattern generation for approximate circuits based on Boolean Satisfiability," 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), Florence, Italy, 2019; 1028–1033. doi: 10.23919/DATE.2019.8714898
10. Chandrasekharan A, Soeken M, Große D, Drechsler R. Approximation-aware rewriting of AIGs for error tolerant applications. Proceedings of the 35th International Conference on Computer-Aided Design (ICCAD '16), ACM, New York, NY, USA, 2016; Article 83, 1–8.
11. Choudhury MR, Mohanram K. Low cost concurrent error masking using approximate logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013; 32(8):1163–1176.
12. Jiang H, Liu C, Maheshwari N, Lombardi F, Han J. A comparative evaluation of approximate multipliers. IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH), Beijing, 2016; 191–196.
13. Momeni A, Han J, Montuschi P, Lombardi F. Design and analysis of approximate compressors for multiplication. IEEE Transactions on Computers, 2015; 64(4):984–994.
14. Huang J, Lach J, Robins G. A methodology for energy-quality tradeoffs using imprecise hardware. Proceedings of the 49th Annual Design Automation Conference (DAC '12), 2012; 504–509.
15. Venkatesan R, Agarwal A, Roy K, Raghunathan A. MACACO: Modeling and analysis of circuits for approximate computing. IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, 2011; 667–673.
16. Soeken M, Große D, Chandrasekharan A, Drechsler R. BDD minimization for approximate computing. 21st Asia and South Pacific Design Automation Conference (ASP-DAC), Macau, 2016; 474–479.
17. Froehlich S, Große D, Drechsler R. One method—all error-metrics: A three-stage approach for error-metric evaluation in approximate computing. 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), Florence, Italy, 2019; 284–287. doi: 10.23919/DATE.2019.8715138
18. Mazahir S, Hasan O, Hafiz R, Shafique M, Henkel J. Probabilistic error modeling for approximate adders. IEEE Transactions on Computers, 2017; 66(3):515–530. doi: 10.1109/TC.2016.2605382
19. Qureshi A, Hasan O. Formal probabilistic analysis of low latency approximate adders. IEEE Transactions on Computers-Aided Design of Integrated Circuits and Systems, 2019; 38(1):177–189.
20. Mazahir S, Hasan O, Hafiz R, Shafique M. Probabilistic error Analysis of approximate recursive multipliers. IEEE Transactions on Computers, 2017; 66(11):1982–1990. doi: 10.1109/TC.2017.2709542
21. Celia D, Vasudevan V, Chandrachoodan N. Probabilistic error modeling for two-part segmented approximate adders. 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, 2018; 1–5. doi: 10.1109/ISCAS.2018.8351273
22. Wu Y, Li Y, Ge X, Qian W. An accurate and efficient method to calculate the error statistics of block-based approximate adders. arXiv preprint arXiv:1703.03522 [Preprint]. 2017 [cited 2019]. Available from: https://arxiv.org/pdf/1703.03522.
23. Akbari O, Kamal M, Afzali-Kusha A, Pedram M. RAP-CLA: A Reconfigurable approximate carry look-ahead adder. IEEE Transactions on Circuits and Systems II: Express Briefs, 2018; 65(8): 1089–1093. doi: 10.1109/TCSII.2016.2633307
24. Schlachter J, Camus V, Palem KV, Enz C. Design and applications of approximate circuits by gate-level pruning. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2017; 25(5):1694–1702. doi: 10.1109/TVLSI.2017.2657799
25. Chandrasekharan A, Eggersglüß S, Große D, Drechsler R. Approximation-aware testing for approximate circuits. 2018 23rd Asia and South Pacific Design Automation Conference (ASP-DAC), Jeju, 2018; 239–244. doi: 10.1109/ASPDAC.2018.8297312
26. Cabodi G, Camurati P, Quer S. Can BDDs compete with SAT solvers on bounded model checking?. Proceedings of the 39th annual Design Automation Conference (DAC '02). Austin, Texas. ACM, New York, NY, USA, 2002; 117–122.
27. Bem VD, Marranghello FS, Reis AI, Ribas RP. SAT-based formulation for logical capacity evaluation of VIA-configurable structured ASIC. IEEE Transactions on Emerging Topics in Computing, 2017; 5(2):247–259. doi: 10.1109/TETC.2016.2644381
28. Afonso J, Monteiro J. Analysis of short-circuit conditions in logic circuits. Design, Automation & Test in Europe Conference & Exhibition (DATE 2017), Lausanne, 2017; 824–829. doi: 10.23919/DATE.2017.7927102
29. Toda T, Soh T. Implementing efficient all solutions SAT solvers. J. Exp. Algorithmics, 2016; 21(1.12):1–44. https://doi.org/10.1145/2975585.
30. Wolf C. Yosys open synthesis suite, 2016.
31. Shafique M, Ahmad W, Hafiz R, Henkel J. A Low latency generic accuracy configurable adder. 52nd ACM/EDAC/IEEE Design Automation Conference & Exhibition (DAC), San Francisco, CA, 2015; 1–6. doi: 10.1145/2744769.2744778
32. Berkeley Logic Synthesis and Verification Group (2019) ABC: A System for Sequential Synthesis and Verification. Release YMMDD. http://www.eecs.berkeley.edu/~alanmi/abc/. Accessed 22 April 2019.
Článek vyšel v časopise
PLOS One
2020 Číslo 1
- Proč se v Česku šíří několik „vymýcených“ infekcí najednou? Ptáme se odborníků
- ADHD jako evoluční výhoda? Výzkum se zaměřil na lovce a sběrače
- Není migréna jako migréna: Co pociťují ženy a co muži?
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Není statin jako statin aneb praktický přehled rozdílů jednotlivých molekul
Nejčtenější v tomto čísle
- Severity of misophonia symptoms is associated with worse cognitive control when exposed to misophonia trigger sounds
- Chemical analysis of snus products from the United States and northern Europe
- Calcium dobesilate reduces VEGF signaling by interfering with heparan sulfate binding site and protects from vascular complications in diabetic mice
- Effect of Lactobacillus acidophilus D2/CSL (CECT 4529) supplementation in drinking water on chicken crop and caeca microbiome
Zvyšte si kvalifikaci online z pohodlí domova
Všechny kurzy