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 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- Limited scalability of circuits that can be processed by EA
- importance of fast evaluation of candidate circuits
- importance of efficient representation of candidate circuits
- Optimization criteria are too simplified (e.g. the number of nodes)
- importance of accurate and fast estimation of HW parameters (e.g. power, area …)
- importance of focusing on target application in which the circuits are applied
- How to determine the approximation error of a digital circuit?
- How to construct a suitable error metric for a given application?
Research summary
The goal of the research is to improve the evolutionary circuit design methodology based on CGP in the following directions.- The method should work at various levels of circuit description.
- The resulting approximate circuits should provide an excellent tradeoff between quality and power consumption.
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).