AUTHORS: Pablo A. Salvadeo, Angel Veca, Rafael Castro-López

Download as PDF

ABSTRACT: This paper analyzes the complexity of a new phenotype for evolvable hardware with more plasticity than the traditional phenotype. The plasticity is due to that fact that this phenotype is unstructured and that property allows it to perform combinational and sequential tasks. The complexity is evaluated in relation to Shannon’s limit (lower) and Lupanov’s limit (upper). These limits define a bounded and sufficient search space for the combinational circuits. However, in the studied case (multipliers with 2-bits word width operands) the lowest number of iterations is achieved when the number of cells available is around four-times the Shannon’s limit. Moreover, at calculate the mutation rate of digital organisms using the Lynch’s equation, which relates the mutation rate to the genome length of the species, the circuit size stays around Lupanov’s limit. Finally, it important to note that compact circuits are obtained directly, with an evolutionary algorithm that only follows a wished-for functionality, where the economy of the phenotypes is an emergent property of the process.

KEYWORDS: Circuit Size, Complexity Limits, Evolvable Hardware, Iterations, Lupanov’s limit, Phenotype, Shannon’s limit

REFERENCES:

[1] T. G. W. Gordon and P. J. Bentley, “On Evolvable Hardware,” in in Soft Computing in Industrial Electronics, S. Ovaska and L. Sztandera, 2002, pp. 279-323.

[2] Y. Bar-Cohen, “Nature as a Model for Mimicking and Inspiration of New Technologies,” Int’l J. of Aeronautical & Space Sci., vol. 13, no. 1, pp. 1-13, 2012.

[3] A. Upegui and E. Sanchez, “Evolvable FPGAs,” in Reconfigurable Computing: The Theory and Practice of FPGA-based Computation, S. Hauck and A. DeHon, Eds.: Morgan Kaufmann: Elsevier, 2008, ch. 33, pp. 725-752.

[4] C. O. Wilke and C. Adami, “The biology of digital organisms,” Trends in Ecology & Evolution, vol. 17, pp. 528-532, 2002.

[5] H. de Garis, “Circuits of Production Rule GenNets,” in Artificial Neural Nets and Genetic Algorithms: Proceedings of the International Conference in Innsbruck, Austria, 1993, R. F. Albrecht, C. R. Reeves, and N. C. Steele, Eds. Vienna: Springer Vienna, 1993, pp. 699-705.

[Online]. http://dx.doi.org/10.1007/978-3-7091- 7533-0_101

[6] J.F. Miller, “Cartesian Genetic Programming,” in Natural Computing Series, J.F. Miller, Ed.: Springer-Verlag Berlin Heidelberg, 2011, ch. 2.

[7] T. Kalganova and J. Miller, “Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness,” in Evolvable Hardware, 1999. Proceedings of the First NASA/DoD Workshop on, 1999, pp. 54- 63.

[8] C. A. Coello-Coello, A. D. Christiansen, and A. Hernández, “Use of Evolutionary Techniques to Automate the Design of Combinational Circuits,” International Journal of Smart Engineering System Design, vol. 2, no. 4, pp. 299-314, 2000.

[9] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, 1st ed. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989.

[10] N. Hansen, D. V. Arnold, and A. Auger, “Evolution Strategies,” in Handbook of Computational Intelligence, J. Kacprzyk and W. Pedrycz, Eds.: Springer, 2015, ch. 44, pp. 871-898.

[11] J. Torresen, “Evolving Multiplier Circuits by 133 83 152 32 93 59 47 50 275 1.712 939 8 7 8 7 8 16 8 0 2 4 6 8 10 12 14 16 18 0 500 1.000 1.500 2.000 8 12 15 16 17 18 19 20 24 36 40 Size (in gates) Iterations (in thousands) Available Nodes iterations size Training Set and Training Vector Partitioning,” in Evolvable Systems: From Biology to Hardware, A. M. Tyrrell, P. C. Haddow, and J. Torresen, Eds.: Springer Berlin Heidelberg, 2003, vol. 2606, pp. 228-237.

[Online]. http://dx.doi.org/10.1007/3-540-36553-2_21

[12] F. Cancare, S. Bhandari, D. B. Bartolini, M. Carminati, and M. D. Santambrogio, “A bird's eye view of FPGA-based Evolvable Hardware,” in Adaptive Hardware and Systems (AHS), 2011 NASA/ESA Conference on, June 2011, pp. 169-175.

[13] M. Karnaugh, “A map method for synthesis of combinational logic circuits,” Transactions of the AIEE, Communications and Electronics, vol. 72, no. 1, pp. 593-599, 1953.

[14] E. J. McCluskey, “Minimization of boolean functions,” Bell Systems Technical Journal, vol. 35, no. 5, pp. 1417-1444, 1956.

[15] W. V. Quine, “A way to simplify truth functions,” American Mathematical Monthly, vol. 62, no. 9, pp. 627-631, 1955.

[16] K. Glette and J. Torresen, “A Flexible On-Chip Evolution System Implemented on a Xilinx Virtex-II Pro Device,” in Evolvable Systems: From Biology to Hardware, J. M. Moreno, J. Madrenas, and J. Cosp, Eds.: Springer Berlin Heidelberg, 2005, vol. 3637, pp. 66-75.

[Online]. http://dx.doi.org/10.1007/11549703_7

[17] J. F. Miller, P. Thomson, and T. Fogarty, “Designing Electronic Circuits Using Evolutionary Algorithms. Arithmetic Circuits: A Case Study,” in Genetic Algorithms and Evolution Strategy in Engineering and Computer Science, D. Quagliarella et al., Eds. Chichester, England: Morgan Kaufmann, 1998, pp. 105-131.

[18] Z. Gajda and L. Sekanina, “An Efficient Selection Strategy for Digital Circuit Evolution,” in Evolvable Systems: From Biology to Hardware, G. Tempesti, A. M. Tyrrell, and J. F. Miller, Eds.: Springer Berlin Heidelberg, 2010, vol. 6274, pp. 13-24.

[Online]. http://dx.doi.org/10.1007/978-3-642- 15323-5_2

[19] T. Kalganova, “An Extrinsic Function-Level Evolvable Hardware Approach,” in 3° European Conference on Genetic Programming, EuroGP2000, Edinburgh, UK, 2000.

[20] C. E. Shannon, “The synthesis of two-terminal switching circuits,” Bell System Technical Journal, vol. 28, pp. 59-98, 1949.

[21] O. B. Lupanov, “On a method of circuit synthesis,” Izvestia VUZ (Radiofizika), vol. 1, pp. 120-140, 1958.

[22] IEEE Standard Association, 1076-2008 VHDL Language Reference Manual, 2008.

[23] S. Malik, “Analysis of cyclic combinational circuits,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 13, no. 7, pp. 950-956, Jul 1994.

[24] R. L. Rivest, “The Necessity of Feedback in Minimal Monotone Combinational Circuits,” IEEE Transactions on Computers, vol. C-26, no. 6, pp. 606-607, June 1977.

[25] M. D. Riedel and J. Bruck, “The synthesis of cyclic combinational circuits,” in Design Automation Conference, 2003. Proceedings, June 2003, pp. 163-168.

[26] M. D. Riedel, “Combinational Circuits with Feedback,” Caltech, Ph.D. dissertation 2004.

[27] S. Brown and Z. Vranesic, Fundamentals of digital logic with VHDL design, 3rd ed.: McGraw-Hill, 2008.

[28] J. Morris, Reconfigurable Computing, Resolution Functions, 2009, University of Auckland.

[29] M. Lynch, “Evolution of the mutation rate,” Trends in Genetics, vol. 26, no. 8, pp. 345-352, 2010.

[Online]. http://dx.doi.org/10.1016/j.tig.2010.05.003