More Web Proxy on the site http://driver.im/

research-article

Complete hardware evolution based SoPC for evolvable hardware

Authors:

A. Swarnalatha,

A.P. ShanthiAuthors Info & Claims

Applied Soft Computing, Volume 18, Issue C

Pages 314 - 322

Published: 01 May 2014 Publication History

Abstract

First CHE for EH based on the CGP model, and hence, the complete algorithm, including the required memory is realized on the CLB logic of a single FPGA.No other hard/soft resource (microcontroller or Power PC) usage for the implementation.Memory requirements for the chromosomes and their fitness remain the same irrespective of the number of generations traversed to reach the optimum.Architecture supports evolution with no limit on the number of generations.Computational delays of the architecture are of the order of a few nanoseconds. Evolvable hardware (EH) is a thriving area of research which uses the genetic algorithm (GA) to construct novel circuits without manual engineering. These algorithms have been widely implemented using software but have not gained an appreciable edge because of the huge computation time involved. This has been a major hindrance to real-time applications. A major speed-up could be achieved by shifting the implementation to hardware. Major issues to be addressed in hardware implementation are scalability, providing flexibility and reduced computational delays. Presented here is the first complete hardware evolution (CHE) based system on programmable chip (SoPC) for EH. The architecture includes the required memory and modules for performing all operations of the algorithm. It is completely built on the configurable logic blocks (CLB) of a single commercial off the shelf (COTS) field programmable gate array (FPGA). The coding is done using Verilog hardware description language (HDL). Xilinx ISE 9.1i has been used for synthesis and simulation. As a proof of concept, the architecture has been synthesized for evolving three combinational circuits. The results show that the architecture is able to cater to evolution with no limit on the number of generations, accompanied with no scaling in the resource utilization. The results present computational delays of the order of a few nanoseconds for this CHE based architecture.

References

[1]

D. Fouskakis, D. Draper, Stochastic optimisation: a review, International Statistical Review, 70 (2002) 315-349.

[2]

N.J. Radcliffe, P.D. Surry, Fundamental limitations on search algorithms: evolutionary computing in perspective, in: Computer Science Today: Recent Trends & Development, Springer-Verlag LNCS 1000, 1995, pp. 275-291.

[3]

C. Darwin, On the Origin of Species by means of Natural Selection, 1859.

[4]

C. Ortega, A. Tyrrell, Evolvable hardware for fault-tolerant applications, in: IEE Colloquium on Evolvable Hardware Systems. Digest No. 98/233, March 1988, pp. 4/1-4/5.

[5]

S.D. Scott, A. Samal, S. Seth, HGA: a hardware-based genetic algorithm, in: Proc. of 3rd ACM/SIGDA Int. Symp. on FPGAs, 1995, pp. 53-59.

Digital Library

[6]

G. Koonar, S. Ariebi, M. Moussa, Hardware implementation of genetic algorithms for VLSI CAD design, Computer Applications in Industry and Engineering, ISCA (2002) 197-200.

[7]

P. Graham, B. Nelson, A hardware genetic algorithm for travelling salesman problem on SPLASH 2, in: Proceedings of the 5th International Workshop on Field-Programmable Logic and Applications, 1995, pp. 352-361.

Digital Library

[8]

K. Glette, J. Torresen, M. Yasunaga, Online evolution of a high-speed image recognition system implemented on a Vertex II Pro FPGA, in: Second NASA/ESA Conference on Adaptive Hardware and Systems, 2007, pp. 463-470.

Digital Library

[9]

M. Vavouras, K. Papadimitriou, I. Papaefstathiou, High speed FPGA-based implementations of a genetic algorithm, IEEE Conference on Embedded Computer Systems Architecture Modeling and Simulation (2009) 9-16.

Digital Library

[10]

P.R. Fernando, S. Katkoori, D. Keymeulen, R. Zubulum, A. Stoica, Customizable FPGA IP core implementation of a general-purpose genetic algorithm engine, IEEE Transactions on Evolutionary Computation (2010) 133-149.

Digital Library

[11]

K. Raman, A. Wagner, The evolvability of programmable hardware, Journal of the Royal Society Interface, 8 (2011) 269-281.

[12]

T.G.W. Gordon, P.J. Bentley, Towards development in evolvable hardware, in: Proceedings of IEEE Conference on Evolvable Hardware, 2002, pp. 241-250.

Digital Library

[13]

A. Thompson, Exploring beyond the scope of human design: automatic generation of FPGA configurations through artificial evolution, in: 8th Annual Advanced PLD and FPGA Conference, 1998, pp. 5-8.

[14]

T. Higuchi, T. Niwa, T. Tanaka, H. Iba, H. de Garis, T. Furuya, Evolving hardware with genetic learning: a first step towards building a Darwin machine, in: Proc. of the 2nd International Conference on Simulated Adaptive Behaviour, 1993, pp. 417-424.

Digital Library

[15]

H. de Garis, Evolvable hardware-genetic programming of a Darwin machine, in: International Conference on Artificial Neural Networks and Genetic Algorithms ICANNGA'93, 1993.

[16]

Evolvable Hardware, Series: Genetic and Evolutionary Computation, in: Evolvable Hardware, Series: Genetic and Evolutionary Computation, Springer, New York, USA, 2006.

[17]

X. Yao, Following the path of evolvable hardware, Communications of the ACM, 42 (1999) 47-49.

Digital Library

[18]

T. Kalganova, J. Milllerand, T. Fogarty, Evolution of the digital circuits with variable layouts, in: Proc. of the Genetic and Evolutionary Computation Conference (GECCO'99), 1999.

[19]

J. Koza, F. Bennett, J. Hutchings, S. Bade, M. Keane, D. Andre, Evolving computer programs using rapidly reconfigurable field programmable gate arrays and genetic programming, in: Proceedings of the ACM 6th International Symposium on Field Programmable Gate Arrays, ACM Press, New York, 1998, pp. 209-219.

Digital Library

[20]

A. Thompson, Hardware Evolution: Automatic Design of Electronic Circuits in Reconfigurable Hardware by Artificial Evolution, Springer-Verlag, New York, 1998.

Digital Library

[21]

A. Thompson, P. Layzell, Analysis of unconventional evolved electronics, Communications of the ACM, 42 (1999) 71-79.

Digital Library

[22]

G.W. Greenwood, A.M. Tyrell, Introduction to Evolvable Hardware, A Practical Guide for Designing Self Assigning Systems, IEEE Press Series on Computational Intelligence, A John Wiley & Sons, Inc., 2006.

Digital Library

[23]

G. Tufte, P.C. Haddow, Prototyping a GA pipeline for complete hardware evolution, in: The First NASA/DOD Workshop on Evolvable Hardware, 1999, pp. 18-25.

Digital Library

[24]

H. Tan, R.F. DeMara, A multi-layer framework supporting autonomous runtime partial reconfiguration, IEEE Transactions on Very Large Scale Integration (VLSI) Systems (2008) 504-516.

Digital Library

[25]

J.F. Miller, P. Thomson, Cartesian genetic programming, in: Proceedings of the European Conference on Genetic Programming (ECGP), 2000, pp. 121-132.

Digital Library

[26]

S. Narayanan, C. Purdy, Hardware implementation of genetic algorithm modules for intelligent systems, in: Proc. 2005 IEEE International Midwest Symp. Circuits and Systems (MWSCAS 05), 2005, pp. 1733-1736.

[27]

A.J. Greensted, A.M. Tyrell, Extrinsic evolvable hardware on the RISA architecture, in: Proc. of the 7th International Conference on Evolvable Systems (ICES), 2007, pp. 244-255.

Digital Library

[28]

E. Stomeo, T. Kalganova, C. Lambert, A novel genetic algorithm for evolvable hardware, in: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, 2006, pp. 441-448.

[29]

Z. Bao, T. Watanabe, A new approach for circuit design optimisation using genetic algorithm, International SoC Design Conference, 1 (2008) 1-383-1-386.

[30]

D.B. Bartolini, F. Cancare, M. Carminati, D. Sciuto, HERA: hardware evolution over reconfigurable architectures, in: Proceedings of the Ist Computing in Heterogeneous Autonomous 'N' Goal-oriented Environments Workshop, 2011.

Digital Library

[31]

A. Swarnalatha, A.P. Shanthi, Optimization of single variable functions using complete hardware evolution, Applied Soft Computing, 12 (2012) 1322-1329.

Digital Library

[32]

Xilinx, Inc., 2014.

[33]

J.F. Miller, P. Thomson, T.C. Fogarty, Designing electronic circuits using evo-lutionary algorithms: arithmetic circuits: a case study, in: D. Quagliarella, J.Periaux, C. Poloni, G. Winter (Eds.), Genetic Algorithms and Evolution Strategies in Engineering and Computer Science: Recent Advancements and Industrial Applications, 1998, Wiley: Chechester, UK, pp. 105-131.

[34]

J.F. Miller, An empirical study of the efficiency of learning Boolean functions using a Cartesian genetic programming approach, in: Proc. Genetic and Evolutionary Computation Conference, 1999, pp. 1135-1142.

[35]

S. Lukas, F. Stepan, An evolvable combinational unit for FPGAS, Computing and Informatics, 23 (2004) 461-486.

Cited By

Zhu S(2018)Hardware implementation based on FPGA of semaphore management in μC/OS-II real-time operating systemInternational Journal of Grid and Utility Computing10.1504/IJGUC.2015.0706776:3/4(192-199)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1504/IJGUC.2015.070677

Complete hardware evolution based SoPC for evolvable hardware
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
2. Hardware
  1. Very large scale integration design
    1. Application-specific VLSI designs

Recommendations

Optimization of single variable functions using complete hardware evolution

A genetic algorithm (GA) is a computer based search optimization technique that uses the Darwinian ''Theory of Evolution'' as a model for finding exact and approximate solutions. GAs belong to a large family of heuristic algorithms called evolutionary ...
An evolvable hardware system in Xilinx Virtex II Pro FPGA

In this paper, a new circuit architecture for image filter evolution is proposed. The evolvable system is based on the implementation of a search algorithm in the PowerPC processor which is available in Xilinx Virtex II Pro Field Programmable Gate ...
Evolvable Hardware: From On-Chip Circuit Synthesis to Evolvable Space Systems
ISMVL '00: Proceedings of the 30th IEEE International Symposium on Multiple-Valued Logic

Evolvable Hardware (EHW) refers to HW design and self-reconfiguration using evolutionary/genetic mechanisms. The paper presents an overview of some key concepts of EHW, comments on selected applications, and presents a perspective on the development of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Applied Soft Computing

Applied Soft Computing Volume 18, Issue C

May 2014

338 pages

ISSN:1568-4946

Issue’s Table of Contents

Copyright © Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 May 2014

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu S(2018)Hardware implementation based on FPGA of semaphore management in μC/OS-II real-time operating systemInternational Journal of Grid and Utility Computing10.1504/IJGUC.2015.0706776:3/4(192-199)Online publication date: 16-Dec-2018
https://dl.acm.org/doi/10.1504/IJGUC.2015.070677

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents