research-article

Evolutionary Approach to Approximate Digital Circuits Design

Authors:

Zdenek Vasicek,

Lukas SekaninaAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 19, Issue 3

Pages 432 - 444

https://doi.org/10.1109/TEVC.2014.2336175

Published: 01 June 2015 Publication History

Abstract

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 that 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 that show very good parameters in comparison with other available implementations were constructed by means of the proposed method.

References

[1]

J. Han and M. Orshansky, “Approximate computing: An emerging paradigm for energy-efficient design,” in Proc. 18th IEEE Eur. Test Symp., Avignon, France, 2013, pp. 1–6.

[2]

V. Gupta, D. Mohapatra, A. Raghunathan, and K. Roy, “Low-power digital signal processing using approximate adders,” IEEE Trans. Computer-Aided Design Integr. Circuits Syst., vol. 32, no. 1, pp. 124–137, Jan. 2013.

Digital Library

[3]

P. Kulkarni, P. Gupta, and M. D. Ercegovac, “Trading accuracy for power in a multiplier architecture,” J. Low Power Electron., vol. 7, no. 4, pp. 490–501, 2011.

[4]

S. Venkataramani, A. Sabne, V. J. Kozhikkottu, K. Roy, and A. Raghunathan, “SALSA: Systematic logic synthesis of approximate circuits,” in Proc. 49th Annu. Design Autom. Conf. (DAC), San Francisco, CA, USA, 2012, pp. 796–801.

[5]

H. Esmaeilzadeh, A. Sampson, L. Ceze, and D. Burger, “Neural acceleration for general-purpose approximate programs,” in Proc. 2012 45th Annu. IEEE/ACM Int. Symp. Microarchitect., Vancouver, BC, Canada, pp. 449–460.

[6]

A. Sampson et al., “EnerJ: Approximate data types for safe and general low-power computation,” in Proc. 32nd ACM SIGPLAN Conf. Program. Lang. Design Implement., San Jose, CA, USA, 2011, pp. 164–174.

[7]

S. Venkataramani, K. Roy, and A. Raghunathan, “Substitute-and-simplify: A unified design paradigm for approximate and quality configurable circuits,” in Design Autom. Test Europe (DATE), Grenoble, France, 2013, pp. 1367–1372.

[8]

J. D. Lohn and G. S. Hornby, “Evolvable hardware: Using evolutionary computation to design and optimize hardware systems,” IEEE Comput. Intell. Mag., vol. 1, no. 1, pp. 19–27, Feb. 2006.

Digital Library

[9]

P. C. Haddow and A. M. Tyrrell, “Challenges of evolvable hardware: Past, present and the path to a promising future,” Genet. Program. Evolvable Mach., vol. 12, no. 3, pp. 183–215, 2011.

Digital Library

[10]

L. Sekanina and Z. Vasicek, “Approximate circuits by means of evolvable hardware,” in Proc. 2013 IEEE Int. Conf. Evolvable Syst., pp. 21–28.

[11]

V. Venkatachalam and M. Franz, “Power reduction techniques for microprocessor systems,” ACM Comput. Surv., vol. 37, no. 3, pp. 195–237, 2005.

Digital Library

[12]

N. R. Shanbhag, R. A. Abdallah, R. Kumar, and D. L. Jones, “Stochastic computation,” in Proc. 47th Annu. Design Autom. Conf. (DAC), Anaheim, CA, USA, 2010, pp. 859–867.

[13]

R. Venkatesan, A. Agarwal, K. Roy, and A. Raghunathan, “MACACO: Modeling and analysis of circuits for approximate computing,” in Proc. 2011 IEEE/ACM Int. Conf. Comput.-Aided Design (ICCAD), San Jose, CA, USA, pp. 667–673.

[14]

M. Murakawa et al., “Evolvable hardware at function level,” in Parallel Problem Solving from Nature—PPSN IV, LNCS 1141. Berlin, Germany: Springer Verlag, 1996, pp. 62–71.

[15]

A. P. Shanthi and R. Parthasarathi, “Practical and scalable evolution of digital circuits,” Appl. Soft Comput., vol. 9, no. 2, pp. 618–624, 2009.

Digital Library

[16]

E. Stomeo, T. Kalganova, and C. Lambert, “Generalized disjunction decomposition for evolvable hardware,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 36, no. 5, pp. 1024–1043, Oct. 2006.

Digital Library

[17]

T. Gordon, “Exploiting development to enhance the scalability of hardware evolution,” Ph.D. dissertation, Dept. Comput. Sci., Univ. College London, London, U.K., 2005.

[18]

K. Imamura, J. A. Foster, and A. W. Krings, “The test vector problem and limitations to evolving digital circuits,” in Proc. 2nd NASA/DoD Workshop Evolvable Hardware, Palo Alto, CA, USA, 2000, pp. 75–79.

[19]

Z. Vasicek and L. Sekanina, “Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware,” Genet. Program. Evolvable Mach., vol. 12, no. 3, pp. 305–327, 2011.

Digital Library

[20]

Z. Vasicek and K. Slany, “Efficient phenotype evaluation in Cartesian genetic programming,” in Proc. 15th Eur. Conf. Genet. Program., Malaga, Spain, 2012, pp. 266–278.

[21]

J. F. Miller, “On the filtering properties of evolved gate arrays,” in Proc. 1st NASA-DoD Workshop Evolvable Hardw., Pasadena, CA, USA, 1999, pp. 2–11.

[22]

G. Greenwood and A. M. Tyrrell, Introduction to Evolvable Hardware. Piscataway, NJ, USA: IEEE Press, 2007.

[23]

T. Knieper, P. Kaufmann, K. Glette, M. Platzner, and J. Torresen, “Coping with resource fluctuations: The run-time reconfigurable functional unit row classifier architecture,” in Proc. 9th Int. Conf. Evolvable Syst., LNCS 6274. York, U.K., 2010, pp. 250–261.

[24]

A. Thompson, P. Layzell, and S. Zebulum, “Explorations in design space: Unconventional electronics design through artificial evolution,” IEEE Trans. Evol. Comput., vol. 3, no. 3, pp. 167–196, Sep. 1999.

Digital Library

[25]

E. M. Sentovich, “SIS: A system for sequential circuit synthesis,” EECS Dept., Univ. California, Berkeley, Berkeley, CA, USA, Tech. Rep. UCB/ERL M92/41, 1992.

[26]

J. Petrlik and L. Sekanina, “Multiobjective evolution of approximate multiple constant multipliers,” in Proc. IEEE Int. Symp. Design Diagnostics Electron. Circuits Syst., Karlovy Vary, Czech Republic, 2013, pp. 116–119.

[27]

J. Hilder, J. Walker, and A. Tyrrell, “Use of a multi-objective fitness function to improve Cartesian genetic programming circuits,” in Proc. NASA/ESA Conf. Adapt. Hardw. Syst., Anaheim, CA, USA, 2010, pp. 179–185.

[28]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002.

Digital Library

[29]

J. F. Miller, D. Job, and V. K. Vassilev, “Principles in the evolutionary design of digital circuits—Part II,” Genet. Program. Evolvable Mach., vol. 1, no. 3, pp. 259–288, 2000.

Digital Library

[30]

J. F. Miller, D. Job, and V. K. Vassilev, “Principles in the evolutionary design of digital circuits—Part I,” Genet. Program. Evolvable Mach., vol. 1, no. 1, pp. 8–35, 2000.

[31]

J. F. Miller, Cartesian Genetic Programming. New York, NY, USA: Springer-Verlag, 2011.

[32]

J. F. Miller and S. L. Smith, “Redundancy and computational efficiency in Cartesian genetic programming,” IEEE Trans. Evol. Comput., vol. 10, no. 2, pp. 167–174, Apr. 2006.

Digital Library

[33]

S. Zhao and L. Jiao, “Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm,” Genet. Program. Evolvable Mach., vol. 7, no. 3, pp. 195–210, 2006.

Digital Library

[34]

D. E. Knuth, The Art of Computer Programming: Sorting and Searching, 2nd ed. Reading, MA, USA: Addison Wesley, 1998.

Digital Library

Cited By

Leon VHanif MArmeniakos GJiao XShafique MPekmestzi KSoudris D(2025)Approximate Computing Survey, Part II: Application-Specific & Architectural Approximation Techniques and ApplicationsACM Computing Surveys10.1145/371168357:7(1-36)Online publication date: 20-Feb-2025
https://dl.acm.org/doi/10.1145/3711683
Prashanth HRao M(2024)Accelerated and Highly Correlated ASIC Synthesis of AI Hardware Subsystems Using CGPIET Computers & Digital Techniques10.1049/2024/66236372024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1049/2024/6623637
Lee CLi YChen YWang CTakahashi A(2023)Approximate Logic Synthesis by Genetic Algorithm with an Error Rate GuaranteeProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567890(146-151)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567890
Show More Cited By

Index Terms

Evolutionary Approach to Approximate Digital Circuits Design
1. Hardware
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Reducing the number of transistors in digital circuits using gate-level evolutionary design
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

This paper shows that the evolutionary design of digital circuits which is conducted at the gate level is able to produce human-competitive circuits at the transistor level. In addition to standard gates, we utilize unconventional gates (such as the ...
A novel three-input approximate XOR gate design based on quantum-dot cellular automata

Quantum-dot cellular automata (QCA) are one of the most promising emerging nanoelectronic paradigms used for designing computers and very large-scale integration circuits. Many applications can tolerate the errors and imprecision of digital systems; ...
Evolutionary Approximation of Complex Digital Circuits
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Circuit approximation has been developed in recent years as a viable method for constructing energy efficient electronic systems. An open problem is how to effectively obtain approximate circuits showing good compromises between key circuit parameters --...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 19, Issue 3

June 2015

152 pages

ISSN:1089-778X

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Press

Publication History

Published: 01 June 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Leon VHanif MArmeniakos GJiao XShafique MPekmestzi KSoudris D(2025)Approximate Computing Survey, Part II: Application-Specific & Architectural Approximation Techniques and ApplicationsACM Computing Surveys10.1145/371168357:7(1-36)Online publication date: 20-Feb-2025
https://dl.acm.org/doi/10.1145/3711683
Prashanth HRao M(2024)Accelerated and Highly Correlated ASIC Synthesis of AI Hardware Subsystems Using CGPIET Computers & Digital Techniques10.1049/2024/66236372024Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1049/2024/6623637
Lee CLi YChen YWang CTakahashi A(2023)Approximate Logic Synthesis by Genetic Algorithm with an Error Rate GuaranteeProceedings of the 28th Asia and South Pacific Design Automation Conference10.1145/3566097.3567890(146-151)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1145/3566097.3567890
Afzaal UHassan AUsman MLee J(2023)On the Evolutionary Synthesis of Fault-Resilient Digital CircuitsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316964127:2(281-295)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TEVC.2022.3169641
Liu BZhang RShen QLi ZXie NWang YXie CCai H(2023)W-AMAComputers and Electrical Engineering10.1016/j.compeleceng.2023.108921111:PAOnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.compeleceng.2023.108921
Armeniakos GZervakis GSoudris DHenkel J(2022)Hardware Approximate Techniques for Deep Neural Network Accelerators: A SurveyACM Computing Surveys10.1145/352715655:4(1-36)Online publication date: 21-Nov-2022
https://dl.acm.org/doi/10.1145/3527156
Kalkreuth RSotto LVašíček ZWagner M(2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3533657
Elangovan RJain SRaghunathan A(2022)Ax-BxP: Approximate Blocked Computation for Precision-reconfigurable Deep Neural Network AccelerationACM Transactions on Design Automation of Electronic Systems10.1145/349273327:3(1-20)Online publication date: 28-Jan-2022
https://dl.acm.org/doi/10.1145/3492733
Meng CWang XSun JTao SWu WWu ZNi LShen XZhao JQian WOshana R(2022)SEALSProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530464(439-444)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530464
Liu BWang ZWang XZhang RXue AShen QXie NGong YWang ZYang JCai H(2022)An Efficient BCNN Deployment Method Using Quality-Aware Approximate ComputingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.319750941:11(4217-4228)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCAD.2022.3197509
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents