Top

Published in:

2019 | OriginalPaper | Chapter

9. Automated Search-Based Functional Approximation for Digital Circuits

Authors : Lukas Sekanina, Zdenek Vasicek, Vojtech Mrazek

Published in: Approximate Circuits

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The problem of developing an approximate implementation of a given combinational circuit can be formulated as a multi-objective design problem and solved by means of a search algorithm. This approach usually provides many solutions showing high-quality tradeoffs between key design objectives; however, it is very computationally expensive. This chapter presents a general-purpose method based on genetic programming for an automated functional approximation of combinational circuits at the gate and register-transfer levels. It surveys relevant error metrics and circuit parameters that are typically optimized by genetic programming. A special attention is given to the techniques capable of providing formal guarantees in terms of error bounds and accelerating the search process. Case studies dealing with approximate implementations of arithmetic circuits and image operators are presented to highlight the quality of results obtained by the search-based functional approximation in completely different application domains.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Approximate Hardware Generation Using Formal Techniques

next chapter Approximate High-Level Synthesis of Custom Hardware

Note that the SAT problem can be solved using a solver based on ROBDDs. By a SAT-based solver, we mean a variant of SAT algorithm typically based on DPLL backtracking operating at the level of CNF.

Ceska M, Matyas J, Mrazek V, Sekanina L, Vasicek Z, Vojnar T (2017) Approximating complex arithmetic circuits with formal error guarantees: 32-bit multipliers accomplished. In: Proceedings of 36th IEEE/ACM international conference on computer aided design. IEEE, Piscataway, pp 416–423

Chan WTJ, Kahng AB, Kang S, Kumar R, Sartori J (2013) Statistical analysis and modeling for error composition in approximate computation circuits. In: 31st IEEE international conference on computer design (ICCD), pp 47–53

Chandrasekharan A, Soeken M, Große D, Drechsler R (2016) Precise error determination of approximated components in sequential circuits with model checking. In: Proceedings of DAC’16. ACM, New York, pp 129:1–129:6

Chen TH, Alaghi A, Hayes JP (2014) Behavior of stochastic circuits under severe error conditions. Inf Technol 56:182–191

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197CrossRef

Hrbacek R, Mrazek V, Vasicek Z (2016) Automatic design of approximate circuits by means of multi-objective evolutionary algorithms. In: Proceedings of the 11th international conference on design and technology of integrated systems in nanoscale era. IEEE, Piscataway, pp 239–244

Huang T, Yang G, Tang G (1979) A fast two-dimensional median filtering algorithm. IEEE Trans Acoust Speech Signal Process 27(1):13–18. https://doi.org/10.1109/TASSP.1979.1163188 CrossRef

Hwang H, Haddad R (1995) Adaptive median filters: new algorithms and results. IEEE Trans Image Process 4(4):499–502. https://doi.org/10.1109/83.370679 CrossRef

Jiang H, Liu C, Maheshwari N, Lombardi F, Han J (2016) A comparative evaluation of approximate multipliers. In: IEEE/ACM international symposium on nanoscale architectures. IEEE, Piscataway, pp 191–196

10.

Ko S, Lee Y (1991) Center weighted median filters and their applications to image enhancement. IEEE Trans Circuits Syst 15:984–993. https://doi.org/10.1109/31.83870 CrossRef

11.

Kulkarni P, Gupta P, Ercegovac MD (2011) Trading accuracy for power in a multiplier architecture. J Low Power Electron 7(4):490–501. https://doi.org/10.1166/jolpe.2011.1157 CrossRef

12.

Lotfi A, Rahimi A, Yazdanbakhsh A, Esmaeilzadeh H, Gupta RK (2016) Grater: an approximation workflow for exploiting data-level parallelism in FPGA acceleration. In: 2016 design, automation and test in Europe conference and exhibition, DATE 2016, pp 1279–1284. https://doi.org/10.3850/9783981537079_0805 CrossRef

13.

Mahdiani HR, Ahmadi A, Fakhraie SM, Lucas C (2010) Bio-inspired imprecise computational blocks for efficient VLSI implementation of soft-computing applications. IEEE Trans Circuits Syst I Reg Papers 57(4):850–862. https://doi.org/10.1109/TCSI.2009.2027626 MathSciNetCrossRef

14.

Miller JF (2011) Cartesian genetic programming. Springer, Berlin. https://doi.org/10.1007/978-3-642-17310-3 MATH

15.

Miller JF, Thomson P, Fogarty T (1998) Designing electronic circuits using evolutionary algorithms. Arithmetic Circuits: A Case Study. Wiley, New York, pp 105–131

16.

Monajati M, Fakhraie SM, Kabir E (2015) Approximate arithmetic for low-power image median filtering. Circuits Syst Signal Process 34(10):3191–3219. https://doi.org/10.1007/s00034-015-9997-4 CrossRef

17.

Mrazek V, Vasicek Z (2016) Automatic design of arbitrary-size approximate sorting networks with error guarantee. In: 2016 26th international workshop on power and timing modeling, optimization and simulation. IEEE Computer Society, Piscataway, pp 221–228

18.

Mrazek V, Sarwar SS, Sekanina L, Vasicek Z, Roy K (2016) Design of power-efficient approximate multipliers for approximate artificial neural networks. In: Proceedings of the IEEE/ACM international conference on computer-aided design. ACM, New York, pp 811–817. https://doi.org/10.1145/2966986.2967021

19.

Mrazek V, Hrbacek R, Vasicek Z, Sekanina L (2017) Evoapprox8b: library of approximate adders and multipliers for circuit design and benchmarking of approximation methods. In: Design, automation and test in Europe conference and exhibition, DATE 2017, pp 258–261. https://doi.org/10.23919/DATE.2017.7926993 CrossRef

20.

Nepal K, Li Y, Bahar RI, Reda S (2014) ABACUS: a technique for automated behavioral synthesis of approximate computing circuits. In: Proceedings of the conference on design, automation and test in Europe, EDA consortium, DATE’14, pp 1–6

21.

Nepal K, Hashemi S, Tann H, Bahar RI, Reda S (2017) Automated high-level generation of low-power approximate computing circuits. IEEE Trans Emerg Top Comput. https://doi.org/10.1109/TETC.2016.2598283

22.

Poli R, Langdon WB, McPhee NF (2008) A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk

23.

Sekanina L, Vasicek Z (2013) Approximate circuits by means of evolvable hardware. In: 2013 IEEE international conference on evolvable systems, IEEE CIS, Proceedings of the 2013 IEEE symposium series on computational intelligence (SSCI), pp 21–28

24.

Sekanina L, Vasicek Z, Mrazek V (2017) Approximate circuits in low-power image and video processing: the approximate median filter. Radioengineering 26(3):623–632CrossRef

25.

Vasicek Z (2017) Relaxed equivalence checking: a new challenge in logic synthesis. In: 2017 IEEE 20th international symposium on design and diagnostics of electronic circuits systems (DDECS), pp 1–6. https://doi.org/10.1109/DDECS.2017.7968435

26.

Vasicek Z, Mrazek V (2017) Trading between quality and non-functional properties of median filter in embedded systems. Genet Program Evolvable Mach 18(1):45–82. https://doi.org/10.1007/s10710-016-9275-7 CrossRef

27.

Vasicek Z, Sekanina L (2007) An area-efficient alternative to adaptive median filtering in FPGAs. In: Proceedings of 2007 international conference on field programmable logic and applications. IEEE, Piscataway, pp 216–221CrossRef

28.

Vasicek Z, Sekanina L (2011) A global postsynthesis optimization method for combinational circuits. In: Proceedings of the design, automation and test in Europe DATE 2011, EDAA, pp 1525–1528

29.

Vasicek Z, Sekanina L (2014) Evolutionary design of approximate multipliers under different error metrics. In: IEEE international symposium on design and diagnostics of electronic circuits and systems. IEEE, Piscataway, pp 135–140

30.

Vasicek Z, Sekanina L (2015) Evolutionary approach to approximate digital circuits design. IEEE Trans Evol Comput 19(3):432–444. https://doi.org/10.1109/TEVC.2014.2336175 CrossRef

31.

Vasicek Z, Sekanina L (2016) Evolutionary design of complex approximate combinational circuits. Genet Program Evolvable Mach 17(2):1–24CrossRef

32.

Vasicek Z, Slany K (2012) Efficient phenotype evaluation in Cartesian genetic programming. In: Proceedings of the 15th European conference on genetic programming. LNCS, vol 7244. Springer, Berlin, pp 266–278

33.

Vasicek Z, Bidlo M, Sekanina L (2013) Evolution of efficient real-time non-linear image filters for FPGAs. Soft Comput 17(11):2163–2180. https://doi.org/10.1007/s00500-013-1040-8 CrossRef

34.

Vasicek Z, Mrazek V, Sekanina L (2017) Towards low power approximate DCT architecture for HEVC standard. In: Design, automation and test in Europe conference and exhibition, DATE 2017, pp 1576–1581. https://doi.org/10.23919/DATE.2017.7927241 CrossRef

35.

Venkataramani S, Roy K, Raghunathan A (2013) Substitute-and-simplify: a unified design paradigm for approximate and quality configurable circuits. In: Design, automation and test in Europe, DATE’13, EDA consortium, pp 1367–1372

36.

Venkatesan R, Agarwal A, Roy K, Raghunathan A (2011) MACACO: modeling and analysis of circuits for approximate computing. In: 2011 IEEE/ACM international conference on computer-aided design (ICCAD). IEEE, Piscataway, pp 667–673CrossRef

Title: Automated Search-Based Functional Approximation for Digital Circuits
Authors: Lukas Sekanina
Zdenek Vasicek
Vojtech Mrazek
Publisher: Springer International Publishing
Book: Approximate Circuits
Print ISBN: 978-3-319-99321-8

Electronic ISBN: 978-3-319-99322-5

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-319-99322-5_9