Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Evolutionary Approach to Approximate Digital Circuits Design

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[34]
D. E. Knuth, The Art of Computer Programming: Sorting and Searching, 2nd ed. Reading, MA, USA: Addison Wesley, 1998.

Cited By

View all
  • (2024)Accelerated and Highly Correlated ASIC Synthesis of AI Hardware Subsystems Using CGPIET Computers & Digital Techniques10.1049/2024/66236372024Online publication date: 1-Jan-2024
  • (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
  • (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
  • Show More Cited By

Index Terms

  1. Evolutionary Approach to Approximate Digital Circuits Design
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      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

      Publisher

      IEEE Press

      Publication History

      Published: 01 June 2015

      Author Tags

      1. population seeding
      2. Approximate computing
      3. Cartesian genetic programming (CGP)
      4. digital circuits

      Qualifiers

      • Research-article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 16 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Accelerated and Highly Correlated ASIC Synthesis of AI Hardware Subsystems Using CGPIET Computers & Digital Techniques10.1049/2024/66236372024Online publication date: 1-Jan-2024
      • (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
      • (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
      • (2023)W-AMAComputers and Electrical Engineering10.1016/j.compeleceng.2023.108921111:PAOnline publication date: 1-Oct-2023
      • (2022)Hardware Approximate Techniques for Deep Neural Network Accelerators: A SurveyACM Computing Surveys10.1145/352715655:4(1-36)Online publication date: 21-Nov-2022
      • (2022)Graph-based genetic programmingProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3533657(958-982)Online publication date: 9-Jul-2022
      • (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
      • (2022)SEALSProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530464(439-444)Online publication date: 10-Jul-2022
      • (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
      • (2022)VECBEE: A Versatile Efficiency–Accuracy Configurable Batch Error Estimation Method for Greedy Approximate Logic SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.314971741:11(5085-5099)Online publication date: 1-Nov-2022
      • Show More Cited By

      View Options

      View options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media