Automated Design Methodology for Approximate Low Power Circuits
Vojtech Mrazek - Brno University of Technology

This thesis was defended in 2018. The work was supervised by prof. Ing. Lukas Sekanina, Ph.D. and by doc. Ing. Zdenek Vasicek, Ph.D.

Thesis Thesis reviews Curriculum vitae Websites

Abstract

The rapid expansion of modern embedded and battery-powered systems has brought new challenges for design methods oriented to low power circuits and systems. Although these methods systematically apply various power optimization techniques, the overall power requirements are still growing because of the increased complexity of integrated circuits. It has been shown that many applications are inherently error resilient and this property can be exploited for further power consumption reduction. This principle is systematically investigated in the nascent field of approximate computing. This thesis deals with efficient design methods for approximate circuits. The proposed methods are based on evolutionary algorithms (EAs). Although EAs have been applied in logic synthesis and optimization of common as well as approximate circuits, their scalability is limited in these areas. The goal of this dissertation is to show that approximate logic synthesis based on evolutionary algorithms (particularly on genetic programming) can provide excellent tradeoffs between the error and power consumption of complex digital circuits. We analyzed four different applications that use digital circuits described at three different levels of abstraction. By means of Cartesian genetic programming we reduced power consumption of small transistorlevel circuits that are typically used in a technology library. We combined evolutionary approximation with formal verification techniques in order to evolve high quality gate-level approximate circuits such as adders and multipliers and provide formal guarantees on the approximation error. These circuits were employed to reduce power consumption in neural image classifiers and discrete cosine transform blocks of the HEVC encoder. We proposed a new data-independent error metric – the distance error - and used it in the evolutionary approximation of complex median circuits that are suitable for low power signal processing. This doctoral thesis presents a coherent methodology for the design of approximate circuits at different levels of description which is also capable of providing formal guarantees on the approximation error.

Motivation

Many computationally intensive applications (e.g. image recognition, signal processing or datamining) are now implemented in embedded systems. The expansion of battery-powered and smart devices such as mobile systems, IoT nodes and wearable electronic requires low power solutions. Energy efficiency thus becomes a crucial design objective. Many computationally intensive applications feature an intrinsic property – the error resilience. Users are often willing to accept certain errors in some cases.

Approximate computing - a new design paradigm for energy-efficient system.

Approximate computing in image processing ( Image Courtesy: Institut für Technische Informatik - Universität Stuttgart )

Design objectives in the approximate computing

Open problems
Evolutionary algorithms in circuit design/optimization Design of approximate circuits

Research summary

The goal of the research is to improve the evolutionary circuit design methodology based on CGP in the following directions. Four applications were selected to evaluate the proposed methodology:
The optimization and approximation of elementary digital circuits available in the technology library [EuroGP'15, EUC'15] the transistor level
Image classification conducted by a neural network [ICCAD'17] the gate level
Discrete cosine transformation (DCT) used in HEVC encoder [DATE'17] the gate level
Median filtering for image and signal filters [GECCO'15, GPEM 2017] the RTL modules level

General contributions

We contributed to the hardware community that search-based algorithms can provide, in an automated design scenario, better results than the state-of-the-art circuit approximation methods and that various application-specific error metrics and constraints can easily be considered in the EA-based design flow. In addition to that we published an open-source library of approximate arithmetic circuits for low-power application or benchmarking of approximation and error-checking algorithms.

To the evolutionary computing community we bring following ideas: the advanced fitness evaluation based on formal methods can significantly improve the scalability of evolutionary design and considering the state-of-the-art solutions as starting points allows to design and optimize more complex circuits than a randomly seeded EA

Awards

The work was awarded by following national and international awards: The Best Interactive Presentation DATE 2017 (Lausanne), The Best PhD Forum Paper VLSI-SoC 2018 (Verona), 3rd place in Humies competition at GECCO 2018 (Kyoto) and Prof. Ing. Jan Hlavička, DrSc. Award (2015). Author has participated on several project - one of them achieved Czech Science Foundation President Award 2017 for excellent results.

Publications

The results were published in impacted journals – IEEE Transactions on Very Large Scale Integration Systems (IF = 1,744), Genetic Programming and Evolvable Machines (IF = 1,455), IET Computers & Digital Techniques (IF = 0,639), Radioengineering (IF = 1,048). Additionaly, the results were published on the premier conferences ranked in CORE database – e.g. CAV 2018 (A* rating), GECCO 2018 (A), ICCAD 2016 and 2017 (A), DATE 2017 (B), EuroGP 2015 (B). The work was cited in 49 publication indexed by Scopus (excluding self- and all-coauthors' citations).

2019

p1 SEKANINA Lukáš, VAŠÍČEK Zdeněk a MRÁZEK Vojtěch. Automated Search-Based Functional Approximation for Digital Circuits. Approximate Circuits - Methodologies and CAD. Heidelberg: Springer International Publishing, 2019, pp. 175-203. ISBN 978-3-319-99322-5.
c24MRÁZEK Vojtěch, HANIF Muhammad Abdullah, VAŠÍČEK Zdeněk, SEKANINA Lukáš a SHAFIQUE Muhammad autoAx: An Automatic Design Space Exploration and Circuit Building Methodology from Elementary Approximate Components. In: To appear in Proc. of the 2019 Design, Automation Conference (DAC). Las Vegas: IEEE/ACM, 2019.
Core: A; Qualis: A1
c23VAŠÍČEK Zdeněk, MRÁZEK Vojtěch a SEKANINA Lukáš. Automated Circuit Approximation Method Driven by Data Distribution. In: To appear in Proc. of the 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). Lausanne: European Design and Automation Association, 2019.
Core: B; Qualis: A1

2018

j4MRÁZEK Vojtěch, VAŠÍČEK Zdeněk, SEKANINA Lukáš, JIANG Honglan a HAN Jie. Scalable Construction of Approximate Multipliers with Formally Guaranteed Worst-Case Error. IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2018, roč. 26, č. 11, s. 2572-2576. ISSN 1063-8210.
Impact factor: 1.744 (Q2)
j3MRÁZEK Vojtěch, VAŠÍČEK Zdeněk a HRBÁČEK Radek. Role of circuit representation in evolutionary design of energy-efficient approximate circuits. IET Computers & Digital Techniques. Stevenage: The Institution of Engineering and Technology, 2018, roč. 2018, č. 4, s. 1-11. ISSN 1751-8601.
Impact factor: 0.639 (Q3)
c22SEKANINA Lukáš, MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Design Space Exploration for Approximate Implementations of Arithmetic Data Path Primitives. In: 25th IEEE International Conference on Electronics Circuits and Systems (ICECS). Bordeaux: IEEE Circuits and Systems Society, 2018, pp. 377-380. ISBN 978-1-5386-4089-0.
Qualis: B1
c21MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Evolutionary Design of Large Approximate Adders Optimized for Various Error Criteria. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO '18). Kyoto: Association for Computing Machinery, 2018, s. 294-295. ISBN 978-1-4503-5764-7.
c20MRÁZEK Vojtěch, SÝS Marek, VAŠÍČEK Zdeněk, SEKANINA Lukáš a MATYÁŠ Václav. Evolving Boolean Functions for Fast and Efficient Randomness Testing. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). Kyoto: Association for Computing Machinery, 2018, s. 1302-1309. ISBN 978-1-4503-5618-3.
Core: A; Qualis: A1
c19MRÁZEK Vojtěch, VAŠÍČEK Zdeněk a SEKANINA Lukáš. Design of Quality-Configurable Approximate Multipliers Suitable for Dynamic Environment. In: Proceedings of the 2018 NASA/ESA Conference on Adaptive Hardware and Systems. Edinburgh, 2018, s. 1-8. ISBN 978-1-5386-7753-7.
c18ČEŠKA Milan, MATYÁŠ Jiří, MRÁZEK Vojtěch, SEKANINA Lukáš, VAŠÍČEK Zdeněk a VOJNAR Tomáš. ADAC: Automated Design of Approximate Circuits. In: Proceedings of 30th International Conference on Computer Aided Verification (CAV'18). LNCS., 2018, s. 1-9.
Core: A*; Qualis: A1

2017

j2SEKANINA Lukáš, VAŠÍČEK Zdeněk a MRÁZEK Vojtěch. Approximate Circuits in Low-Power Image and Video Processing: The Approximate Median Filter. Radioengineering. 2017, roč. 26, č. 3, s. 623-632. ISSN 1210-2512.
Impact factor: 1.048 (Q3) Cited: 1x
j1VAŠÍČEK Zdeněk a MRÁZEK Vojtěch. Trading between Quality and Non-functional Properties of Median Filter in Embedded Systems. Genetic Programming and Evolvable Machines. Berlin: Springer Verlag, 2017, roč. 18, č. 1, s. 45-82. ISSN 1389-2576.
Impact factor: 1.455 (Q2) Cited: 2x
c17MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Parallel Optimization of Transistor Level Circuits using Cartesian Genetic Programming. In: GECCO Companion '17 Proceedings of the Companion Publication of the 2017 on Genetic and Evolutionary Computation Conference. Berlin: Association for Computing Machinery, 2017, s. 1849-1856. ISBN 978-1-4503-4939-0.
c16MRÁZEK Vojtěch, HRBÁČEK Radek, VAŠÍČEK Zdeněk a SEKANINA Lukáš. EvoApprox8b: Library of Approximate Adders and Multipliers for Circuit Design and Benchmarking of Approximation Methods. In: Proc. of the 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE). Lausanne: European Design and Automation Association, 2017, s. 258-261. ISBN 978-3-9815370-9-3.
Core: B; Qualis: A1 Cited: 15x
c15SHAFIQUE Muhammad, HAFIZ Rehan, JAVED Muhammad Usama, ABBAS Sarmad, SEKANINA Lukáš, VAŠÍČEK Zdeněk a MRÁZEK Vojtěch. Adaptive and Energy-Efficient Architectures for Machine Learning: Challenges, Opportunities, and Research Roadmap. In: 2017 IEEE Computer Society Annual Symposium on VLSI. Los Alamitos: IEEE Computer Society Press, 2017, s. 627-632. ISBN 978-1-5090-6762-6.
Qualis: B1 Cited: 3x
c14VAŠÍČEK Zdeněk, MRÁZEK Vojtěch a SEKANINA Lukáš. Towards Low Power Approximate DCT Architecture for HEVC Standard. In: Proc. of the 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE). Lausanne: European Design and Automation Association, 2017, s. 1576-1581. ISBN 978-3-9815370-9-3.
Core: B; Qualis: A1 Cited: 3x
c13ČEŠKA Milan, MATYÁŠ Jiří, MRÁZEK Vojtěch, SEKANINA Lukáš, VAŠÍČEK Zdeněk a VOJNAR Tomáš. Approximating Complex Arithmetic Circuits with Formal Error Guarantees: 32-bit Multipliers Accomplished. In: Proceedings of 36th IEEE/ACM International Conference On Computer Aided Design (ICCAD). Irvine, CA: Institute of Electrical and Electronics Engineers, 2017, s. 416-423. ISBN 978-1-5386-3093-8.
Core: A; Qualis: A1 Cited: 3x

2016

c12HRBÁČEK Radek, MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Automatic Design of Approximate Circuits by Means of Multi-Objective Evolutionary Algorithms. In: Proceedings of the 11th International Conference on Design & Technology of Integrated Systems in Nanoscale Era. Istanbul: Istanbul Sehir University, 2016, s. 239-244. ISBN 978-1-5090-0335-8.
Cited: 3x
c11MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Automatic Design of Arbitrary-Size Approximate Sorting Networks with Error Guarantee. In: Power and Timing Modeling, Optimization and Simulation (PATMOS), 2016 26rd International Workshop on. Bremen: Institute of Electrical and Electronics Engineers, 2016, s. 221-228. ISBN 978-1-5090-0733-2.
Qualis: B2
c10MRÁZEK Vojtěch, SARWAR Syed Shakib, SEKANINA Lukáš, VAŠÍČEK Zdeněk a ROY Kaushik. Design of Power-Efficient Approximate Multipliers for Approximate Artificial Neural Networks. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Austin, TX: Association for Computing Machinery, 2016, s. 811-817. ISBN 978-1-4503-4466-1.
Core: A; Qualis: A1 Cited: 12x
c9MRÁZEK Vojtěch. Evoluční snižování příkonu: Od obvodů na úrovni tranzistorů po neuronové sítě na čipu. In: Počítačové architektury a diagnostika PAD 2016. Bořetice: Fakulta informačních technologií VUT v Brně, 2016, s. 61-64. ISBN 978-80-214-5376-0.
c8NEVORAL Jan, RŮŽIČKA Richard a MRÁZEK Vojtěch. Evolutionary Design of Polymorphic Gates Using Ambipolar Transistors. In: 2016 IEEE Symposium Series on Computational Intelligence. Athens: Institute of Electrical and Electronics Engineers, 2016, s. 1-8. ISBN 978-1-5090-4240-1.
c7VAŠÍČEK Zdeněk, MRÁZEK Vojtěch a SEKANINA Lukáš. Evolutionary Functional Approximation of Circuits Implemented into FPGAs. In: 2016 IEEE Symposium Series on Computational Intelligence. Athens: Institute of Electrical and Electronics Engineers, 2016, s. 1-8. ISBN 978-1-5090-4240-1.

2015

c6MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Automatic Design of Low-Power VLSI Circuits: Accurate and Approximate Multipliers. In: Proceedings of 13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing. Porto: Institute of Electrical and Electronics Engineers, 2015, s. 106-113. ISBN 978-1-4673-8299-1.
Core: C; Qualis: B2 Cited: 1x
c5MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Evolutionary Design of Transistor Level Digital Circuits using Discrete Simulation. In: Genetic Programming, 18th European Conference, EuroGP 2015. Berlin: Springer International Publishing, 2015, s. 66-77. ISBN 978-3-319-16500-4.
Core: B; Qualis: B1 Cited: 3x
c4MRÁZEK Vojtěch, VAŠÍČEK Zdeněk a SEKANINA Lukáš. Evolutionary Approximation of Software for Embedded Systems: Median Function. In: GECCO Companion '15 Proceedings of the Companion Publication of the 2015 on Genetic and Evolutionary Computation Conference. New York: Association for Computing Machinery, 2015, s. 795-801. ISBN 978-1-4503-3488-4.
Cited: 6x
c3MRÁZEK Vojtěch. Evoluční návrh nízkopříkonových obvodů. In: Počítačové architektury a diagnostika PAD 2015. Zlín: Fakulta aplikované informatiky, Univerzita Tomáše Bati ve Zlíně, 2015, s. 1-6. ISBN 978-80-7454-522-1.

2014

c2MRÁZEK Vojtěch a VAŠÍČEK Zdeněk. Acceleration of Transistor-Level Evolution using Xilinx Zynq Platform. In: 2014 IEEE International Conference on Evolvable Systems Proceedings. Piscataway: Institute of Electrical and Electronics Engineers, 2014, s. 9-16. ISBN 978-1-4799-4480-4.
c1MRÁZEK Vojtěch. Akcelerace evolučního návrhu digitálních obvodů na úrovni tranzistorů s využitím platformy Zynq. In: Proceedings of the 20th Student Conference, EEICT 2014. Brno: Vysoké učení technické v Brně, 2014, s. 229-231. ISBN 978-80-214-4923-7.