nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Approximate Computing: An Old Job for Cartesian Genetic Programming?

verfasst von : Lukas Sekanina

Erschienen in: Inspired by Nature

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Miller’s Cartesian genetic programming (CGP) has significantly influenced the development of evolutionary circuit design and evolvable hardware. We present key ingredients of CGP with respect to the efficient search in the space of digital circuits. We then show that approximate computing, which is currently one of the promising approaches used to reduce power consumption of computer systems, is a natural application for CGP. We briefly survey typical applications of CGP in approximate circuit design and outline new directions in approximate computing that could benefit from CGP.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Combining Local and Global Search: A Multi-objective Evolutionary Algorithm for Cartesian Genetic Programming

Nächstes Kapitel Breaking the Stereotypical Dogma of Artificial Neural Networks with Cartesian Genetic Programming

Nonlinear image filter, Patent No. 304181, Czech Republic, 2013.

NAnoSCale Engineering for Novel Computation using Evolution, http://www.nascence.eu.

Chippa, V., Venkataramani, S., Chakradhar, S., Roy, K., Raghunathan, A.: Approximate computing: an integrated hardware approach. In: 2013 Asilomar Conference on Signals, Systems and Computers, pp. 111–117. IEEE (2013)

Clegg, J., Walker, J.A., Miller, J.F.: A new crossover technique for cartesian genetic programming. In: Proceedings of GECCO, pp. 1580–1587. ACM (2007)

Dobai, R., Sekanina, L.: Low-level flexible architecture with hybrid reconfiguration for evolvable hardware. ACM Trans. Reconfig. Technol. Syst. 8(3), 1–24 (2015)CrossRef

Esmaeilzadeh, H., Sampson, A., Ceze, L., Burger, D.: Neural acceleration for general-purpose approximate programs. Commun. ACM 58(1), 105–115 (2015)CrossRef

Gajda, Z., Sekanina, L.: An efficient selection strategy for digital circuit evolution. In: Evolvable Systems: From Biology to Hardware, LNCS, vol. 6274, pp. 13–24. Springer (2010)

Goldman, B.W., Punch, W.F.: Analysis of Cartesian genetic programming’s evolutionary mechanisms. IEEE Trans. Evol. Comput. 19(3), 359–373 (2015)

Gupta, P., Agarwal, Y., Dolecek, L., Dutt, N., Gupta, R.K., Kumar, R., Mitra, S., Nicolau, A., Rosing, T.S., Srivastava, M.B., Swanson, S., Sylvester, D.: Underdesigned and opportunistic computing in presence of hardware variability. IEEE Trans. CAD Integr. Circuits Syst. 32(1), 8–23 (2013)CrossRef

Harding, S., Miller, J.F., Banzhaf, W.: Developments in cartesian genetic programming: self-modifying CGP. Genet. Program. Evolvable Mach. 11(3–4), 397–439 (2010)CrossRef

Harding, S.L., Banzhaf, W.: Hardware acceleration for CGP: graphics processing units. In: Cartesian Genetic Programming, pp. 231–253. Springer (2011)

10.

Harding, S.L., Miller, J.F.: Evolution in materio: evolving logic gates in liquid crystal. Int. J. Unconv. Comput. 3(4), 243–257 (2007)

11.

Hilder, J., Walker, J., Tyrrell, A.: Use of a multi-objective fitness function to improve cartesian genetic programming circuits. In: NASA/ESA Conference on Adaptive Hardware and Systems, pp. 179–185. IEEE (2010)

12.

Holik, L., Lengal, O., Rogalewicz, A., Sekanina, L., Vasicek, Z., Vojnar, T.: Towards formal relaxed equivalence checking in approximate computing methodology. In: 2nd Workshop on Approximate Computing (WAPCO 2016), HiPEAC, pp. 1–6 (2016)

13.

Hrbacek, R., Sekanina, L.: Towards highly optimized cartesian genetic programming: from sequential via SIMD and thread to massive parallel implementation. In: Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, pp. 1015–1022. ACM(2014)

14.

Kaufmann, P., Platzner, M.: Advanced techniques for the creation and propagation of modules in cartesian genetic programming. In: Genetic and Evolutionary Computation (GECCO), pp. 1219–1226. ACM Press (2008)

15.

Kaufmann, P., Plessl, C., Platzner, M.: EvoCaches: application-specific adaptation of cache mappings. In: Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems, pp. 11–18. IEEE Computer Society, Los Alamitos, CA, USA (2009)

16.

Kaufmann, P., Knieper, T., Platzner, M.: A novel hybrid evolutionary strategy and its periodization with multi-objective genetic optimizers. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2010)

17.

Kaufmann, P., Glette, K., Gruber, T., Platzner, M., Torresen, J., Sick, B.: Classification of electromyographic signals: comparing evolvable hardware to conventional classifiers. IEEE Trans. Evol. Comput. 17(1), 46–63 (2013)CrossRef

18.

Khan, G.M., Miller, J.F., Halliday, D.M.: Evolution of Cartesian genetic programs for development of learning neural architecture. Evol. Comput. 19(3), 469–523 (2011)

19.

Knieper, T., Kaufmann, P., Glette, K., Platzner, M., Torresen, J.: Coping with resource fluctuations: the run-time reconfigurable functional unit row classifier architecture. In: Proceedings of the 9th International Conference on Evolvable Systems: From Biology to Hardware, LNCS, vol. 6274, pp. 250–261. Springer (2010)

20.

Koza, J.R.: Genetic Programming: On The Programming of Computers by Means of Natural Selection. MIT press (1992)

21.

Louis, S., Rawlins, G.J.E.: Designer genetic algorithms: genetic algorithms in structure design. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 53–60. Morgan Kauffman (1991)

22.

Markov, I.: Limits on fundamental limits to computation. Nature 512, 147–154 (2014)CrossRef

23.

Miller, J.F.: An empirical study of the efficiency of learning Boolean functions using a cartesian genetic programming approach. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation, vol. 2, pp. 1135–1142. Morgan Kaufmann Publishers Inc. (1999)

24.

Miller, J.F.: On the filtering properties of evolved gate arrays. In: 1st NASA-DoD Workshop on Evolvable Hardware, pp. 2–11. IEEE Computer Society (1999)

25.

Miller, J.F.: Cartesian Genetic Programming. Springer (2011)

26.

Miller, J.F., Downing, K.: Evolution in materio: looking beyond the silicon box. In: Proceedings of the 2002 NASA/DoD Conference on Evolvable Hardware (EH’02), pp. 167–176. IEEE Computer Society (2002)

27.

Miller, J.F., Smith, S.L.: Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans. Evol. Comput. 10(2), 167–174 (2006)CrossRef

28.

Miller, J.F., Thomson, P.: Cartesian Genetic Programming. In: Proceedings of the 3rd European Conference on Genetic Programming EuroGP2000, LNCS, vol. 1802, pp. 121–132. Springer (2000)

29.

Miller, J.F., Thomson, P., Fogarty, T.: Designing electronic circuits using evolutionary algorithms. Arithmetic circuits: A case study. In: Genetic algorithms and evolution strategy in engineering and computer science. Wiley (1998)

30.

Miller, J.F., Job, D., Vassilev, V.K.: Principles in the evolutionary design of digital circuits—part II. Genet. Program. Evolvable Mach. 1(3), 259–288 (2000)CrossRefMATH

31.

Mittal, S.: A survey of techniques for approximate computing. ACM Comput. Surv. 48(4), 62:1–62:33 (2016)

32.

Mohid, M., Miller, J.F., Harding, S.L., Tufte, G., Massey, M.K., Petty, M.C.: Evolution-in-materio: solving computational problems using carbon nanotube-polymer composites. Soft Comput. 20(8), 3007–3022 (2016)CrossRef

33.

Mrazek, V., Vasicek, Z.: Automatic design of low-power vlsi circuits: Accurate and approximate multipliers. In: Proceedings of 13th IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, pp. 106–113. IEEE (2015)

34.

Mrazek, V., Vasicek, Z., Sekanina, L.: 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, pp. 795–801. ACM (2015)

35.

Mrazek, V., Sarwar, S.S., Sekanina, L., Vasicek, Z., Roy, K.: Design of power-efficient approximate multipliers for approximate artificial neural networks. In: 2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). pp. 811–817 (2016)

36.

Mrazek, V., Hrbacek, R., Vasicek, Z., Sekanina, L.: Evoapprox8b: library of approximate adders and multipliers for circuit design and benchmarking of approximation methods. In: 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 258–261 (2017)

37.

Murakawa, M., Yoshizawa, S., Kajitani, I., Furuya, T., Iwata, M., Higuchi, T.: Evolvable hardware at function level. In: Parallel Problem Solving from Nature—PPSN IV, LNCS, vol. 1141, pp. 62–71. Springer (1996)

38.

Nawab, S., Oppenheim, A., Chandrakasan, A., Winograd, J., Ludwig, J.: Approximate signal processing. J. VLSI Signal Process. 15(1–2), 177–200 (1997)CrossRef

39.

Nepal, K., Li, Y., Bahar, R.I., Reda, S.: ABACUS: a technique for automated behavioral synthesis of approximate computing circuits. In: Proceedings of the Conference on Design, Automation and Test in Europe, EDA Consortium, DATE’14, pp. 1–6 (2014)

40.

Salvador, R., Otero, A., Mora, J., la De, E.T., Riesgo, T., Sekanina, L.: Self-reconfigurable evolvable hardware system for adaptive image processing. IEEE Trans. Comput. 62(8), 1481–1493 (2013)CrossRefMATHMathSciNet

41.

Sampson, A., Dietl, W., Fortuna, E., Gnanapragasam, D., Ceze, L., Grossman, D.: EnerJ: approximate data types for safe and general low-power computation. In: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 164–174. ACM (2011)

42.

Sekanina, L.: Evolvable components: from theory to hardware implementations. Nat. Comput. Ser. (2004)

43.

Sekanina, L.: Evolvable hardware. In: Handbook of Natural Computing, pp. 1657–1705. Springer (2012)

44.

Sekanina, L., Ruzicka, R., Gajda, Z.: Polymorphic fir filters with backup mode enabling power savings. In: Proceedings of the 2009 NASA/ESA Conference on Adaptive Hardware and Systems, pp. 43–50. IEEE Computer Society (2009)

45.

Shubham, J., Venkataramani, S., Raghunathan, A.: Approximation through logic isolation for the design of quality configurable circuits. In: Proceedings of the 2016 Design, Automation & Test in Europe Conference and Exhibition (DATE), pp. 1–6. EDA Consortium (2016)

46.

Sikulova, M., Sekanina, L.: Acceleration of evolutionary image filter design using coevolution in Cartesian GP. In: Parallel Problem Solving from Nature-PPSN XII, no. 7491 in LNCS, pp. 163–172. Springer (2012)

47.

Slany, K., Sekanina, L.: Fitness landscape analysis and image filter evolution using functional-level CGP. In: Proceedings of European Conference on Genetic Programming. LNCS, vol. 4445, pp. 311–320. Springer (2007)

48.

Soeken, M., Grosse, D., Chandrasekharan, A., Drechsler, R.: BDD minimization for approximate computing. In: 21st Asia and South Pacific Design Automation Conference ASP-DAC 2016, pp. 474–479. IEEE (2016)

49.

Stomeo, E., Kalganova, T., Lambert, C.: Generalized disjunction decomposition for evolvable hardware. IEEE Trans. Syst. Man Cybern. Part B 36(5), 1024–1043 (2006)CrossRef

50.

Thompson, A., Layzell, P., Zebulum, S.: Explorations in design space: unconventional electronics design through artificial evolution. IEEE Trans. Evol. Comput. 3(3), 167–196 (1999)CrossRef

51.

Turner, A.J., Miller, J.F.: Recurrent cartesian genetic programming. In: Parallel Problem Solving from Nature—PPSN XIII, pp. 476–486. Springer (2014)

52.

Turner, A.J., Miller, J.F.: Neutral genetic drift: an investigation using cartesian genetic programming. Genet. Program. Evolvable Mach. 16(4), 531–558 (2015)CrossRef

53.

Vasicek, Z.: Cartesian GP in optimization of combinational circuits with hundreds of inputs and thousands of gates. In: Proceedings of the 18th European Conference on Genetic Programming—EuroGP. LCNS 9025, pp. 139–150. Springer International Publishing (2015)

54.

Vasicek, Z., Sekanina, L.: An evolvable hardware system in Xilinx Virtex II Pro FPGA. Int. J. Innov. Comput. Appl. 1(1), 63–73 (2007)CrossRef

55.

Vasicek, Z., Sekanina, L.: Formal verification of candidate solutions for post-synthesis evolutionary optimization in evolvable hardware. Genet. Program. Evolvable Mach. 12(3), 305–327 (2011)

56.

Vasicek, Z., Sekanina, L.: A global postsynthesis optimization method for combinational circuits. In: Proceedings of the Design, Automation and Test in Europe, DATE, pp. 1525–1528. IEEE Computer Society (2011)

57.

Vasicek, Z., Sekanina, L.: Evolutionary design of approximate multipliers under different error metrics. In: IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems 2013, pp. 135–140. IEEE (2014)

58.

Vasicek, Z., Sekanina, L.: How to evolve complex combinational circuits from scratch? In: 2014 IEEE International Conference on Evolvable Systems Proceedings, pp. 133–140. IEEE (2014)

59.

Vasicek, Z., Sekanina, L.: Circuit approximation using single- and multi-objective cartesian GP. In: Genetic Programming. LNCS 9025, pp. 217–229. Springer (2015)

60.

Vasicek, Z., Sekanina, L.: Evolutionary approach to approximate digital circuits design. IEEE Trans. Evol. Comput. 19(3), 432–444 (2015)

61.

Vasicek, Z., Sekanina, L.: Evolutionary design of complex approximate combinational circuits. Genet. Program. Evolvable Mach. 17(2), 169–192 (2016)CrossRef

62.

Vasicek, Z., Slany, K.: Efficient phenotype evaluation in cartesian genetic programming. In: Proceedings of the 15th European Conference on Genetic Programming. LNCS 7244, pp. 266–278. Springer (2012)

63.

Vassilev, V., Job, D., Miller, J.F.: Towards the automatic design of more efficient digital circuits. In: Proceedings of the 2nd NASA/DoD Workshop on Evolvable Hardware, pp. 151–160. IEEE Computer Society (2000)

64.

Vazirani, V.V.: Approximation Algorithms. Springer (2001)

65.

Venkataramani, S., Roy, K., Raghunathan, A.: Substitute-and-simplify: a unified design paradigm for approximate and quality configurable circuits. Design, Automation and Test in Europe, DATE’13, pp. 1367–1372. EDA Consortium San Jose, CA, USA (2013)

66.

Venkatesan, R., Agarwal, A., Roy, K., Raghunathan, A.: MACACO: modeling and analysis of circuits for approximate computing. In: 2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 667–673. IEEE (2011)

67.

Walker, J.A., Miller, J.F.: The automatic acquisition, evolution and reuse of modules in cartesian genetic programming. IEEE Trans. Evol. Comput. 12(4), 397–417 (2008)CrossRef

68.

Walker, J.A., Hilder, J.A., Tyrrell, A.M.: Evolving Variability-Tolerant CMOS Designs. Springer, Berlin Heidelberg (2008)CrossRef

69.

Walker, J.A., Hilder, J.A., Reid, D., Asenov, A., Roy, S., Millar, C., Tyrrell, A.M.: The evolution of standard cell libraries for future technology nodes. Genet. Program. Evolvable Mach. 12(3), 235–256 (2011)CrossRef

Titel: Approximate Computing: An Old Job for Cartesian Genetic Programming?
verfasst von: Lukas Sekanina
Verlag: Springer International Publishing
Buch: Inspired by Nature
Print ISBN: 978-3-319-67996-9

Electronic ISBN: 978-3-319-67997-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-67997-6_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"