An Entry for the 12th Annual (2015) "Humies" Awards for Human-Competitive Results Produced by Genetic and Evolutionary Computation
(1) the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result:
“Evolutionary Approach to Approximate Digital Circuits Design”
(2) the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper:
Zdenek Vasicek
Faculty of Information Technology
Brno University of Technology
Bozetechova 2
612 66 Brno, Czech Republic
e-mail: vasicek@fit.vutbr.cz
tel: +420541141354
Lukas Sekanina
Faculty of Information Technology
Brno University of Technology
Bozetechova 2
612 66 Brno, Czech Republic
e-mail: sekanina@fit.vutbr.cz
tel: +420541141215
(3) the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition):
Lukas Sekanina
(4) the abstract of the paper(s):
In approximate computing, the requirement of perfect functional behavior can be relaxed because some applications are inherently error resilient. Approximate circuits, which fall into the approximate computing paradigm, are designed in such a way that they do not fully implement the logic behavior given by the specification and hence their accuracy can be exchanged for lower area, delay or power consumption. In order to automate the design process, we propose to evolve approximate digital circuits which show a minimal error for a supplied amount of resources. The design process which is based on Cartesian Genetic Programming (CGP) can be repeated many times in order to obtain various tradeoffs between the accuracy and area. A heuristic seeding mechanism is introduced to CGP which allows for improving not only the quality of evolved circuits, but also reducing the time of evolution. The efficiency of the proposed method is evaluated for the gate as well as the functional level evolution. In particular, approximate multipliers and median circuits which show very good parameters in comparison with other available implementations were constructed by means of the proposed method.
(5) a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies:
B, D, G
(6) a statement stating why the result satisfies the criteria that the contestant claims:
Energy consumption reduction is one of the key driving factors of current computer design industry. Hence various approaches to energy consumption reduction have been developed. In recent 5 years, a new research field –- approximate computing -- was established to investigate how computer systems can be made better -- more energy efficient, faster, and less complex -- by relaxing the requirement that they are exactly correct. Approximate computing exploits the fact that some applications are error resilient which means that their users are willing to accept less than perfect solutions, simply because the inaccuracies in the output are not recognizable, or they are well justified under some circumstances. Approximate circuits, which fall into the approximate computing paradigm, are designed in such a way that they do not fully implement the logic behavior given by the specification and hence their accuracy can be exchanged for lower area, delay or power consumption. A current trend which can be observed at classic hardware conferences (DAC, DATE, ICCAD) is approximating circuit components (such as arithmetic circuits, elementary processing blocks) and using them as building blocks of more complex approximate circuits and systems. This is easier than approximating complex circuits without any decomposition.
In our paper, we proposed Cartesian GP-based method to approximate gate-level and functional-level combinational circuits. Contrasted to other methods proposed by the approximate circuit design community, it is possible to (exactly) specify how much resources (and consequently, energy) can be used in the resulting approximate circuit. Note that the approximation process of current methods is purely guided by the error, the resulting area is not under control. Our method was evaluated in the task of multiplier and median-outputting circuit (median) approximation. Evolved approximate circuits satisfy the following criteria:
B:
By CGP we rediscovered exactly the same 2-bit approximate multiplier as the original 2-bit approximate multiplier introduced in [KGE11], Fig. 2. This circuit is important because it shows the optimal tradeoff between the error, area and delay. This 2-bit approximate multiplier (M2, for short) was used as a building block of more complex multipliers in [KGE11], in particular, a 4-bit approximate multiplier (C4), an 8-bit approximate multiplier (C8) and a 16-bit approximate multiplier (C16).
Contrasted to [KGE11], we were able to find (i.e. evolve) 4-bit approximate multipliers and use them as building blocks in more complex multipliers. Our paper shows that 4-bit, 8-bit and 16-bit approximate multipliers composed of the evolved 4-bit approximate multipliers represent better tradeoffs (area vs. delay vs. error vs. power consumption) than multipliers C4, C8 and C16 (see Table III in our paper).
Hence we can claim that our “result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal”.
[KGE11] P. Kulkarni, P. Gupta, M. D. Ercegovac: Trading accuracy for power in a multiplier architecture. Journal of Low Power Electronics, vol. 7, no. 4, pp. 490–501, 2011. ISSN 1546-1998
D:
The evolved approximate multipliers presented in the previous section are publishable in their own right as a new scientific result -- independent of the fact that they were mechanically created -- because a clear improvement in circuit parameters can be demonstrated with respect to the state-of-the-art.
We also evolved various approximate implementations of 9-input and 25-input median circuits (roughly corresponding with circuits containing 2,800 and 16,000 gates assuming fully functional implementations). The evolved approximate median circuits are publishable in their own right as a new scientific result -- independent of the fact that they were mechanically created -- because such approximate median circuits are currently highly requested in journals dealing with low power circuits for signal processing, as demonstrated by a recent paper [MFK15] which was published after the acceptance of our paper. Our method provided more high-quality compromise solutions for the 9-input median than the method presented in [MFK15].
[MFK15] M. Monajati, S. M. Fakhraie, E. Kabir: Approximate Arithmetic for Low-Power Image Median Filtering. Circuits, Systems, and Signal Processing, Springer, February 2015, In press, ISSN: 0278-081X
Moreover, approximate software implementations of median functions developed exactly according to the structure of our evolved approximate median circuits, were accepted for publication at Genetic Improvement Workshop at GECCO 2015 [MVS15].
[MVS15] V. Mrazek, Z. Vasicek, L. Sekanina: Evolutionary Approximation of Software for Embedded Systems: Median Function. In Proc. of the Genetic Improvement Workshop at GECCO 2015 (to appear).
G:
Despite the fact that various logic synthesis and optimization tools were proposed in recent 50 years and several circuit approximation methods were introduced in recent 5 years, the approximate logic synthesis/optimization problem is considered as very difficult. In particular, finding good compromises between key circuit parameters is very difficult. We presented detailed Pareto fronts for approximate multipliers and median circuits in our paper. We claim that the proposed method solves a problem of indisputable difficulty in its field.
(7) a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable):
Zdenek Vasicek, Lukas Sekanina: Evolutionary Approach to Approximate Digital Circuits Design. IEEE Transactions on Evolutionary Computation, in press, URL http://dx.doi.org/10.1109/TEVC.2014.2336175
Date of Publication: 08 July 2014
(8) a statement either that “any prize money, if any, is to be divided equally among the co-authors” OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors:
Any prize money is to be divided equally among the co-authors.
(9) a statement stating why the judges should consider the entry as “best” in comparison to other entries that may also be “human-competitive”:
(i) We contributed to solving one of the key challenges discussed globally -– how to reduce energy requirements of current society which requires powerful computer systems as well as low power mobile and ubiquitous devices.
(ii) Because of the nature of approximate circuits (in fact, partially working circuits are sought) and principles of evolutionary circuit design (evolutionary-based improving of partially working circuits), we observe a synergy effect which could lead to establishing the evolutionary design as a competitive systematic design method for approximate circuits. Moreover, an advantage of evolutionary algorithms is that they are capable of producing many different compromise solutions which is not visible in other methods. Hence we believe that approximate computing is a killer application for evolutionary circuit design.
(iii) The proposed evolutionary approximation method is applicable not only for circuits, but also for certain classes of software as we have already shown in [MVS15].
(10) An indication of the general type of genetic or evolutionary computation used:
Genetic Programming (GP)