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

article

A three-step decomposition method for the evolutionary design of sequential logic circuits

Authors:

Xufa WangAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 10, Issue 3

Pages 231 - 262

https://doi.org/10.1007/s10710-009-9083-4

Published: 01 September 2009 Publication History

Abstract

Evolvable hardware (EHW) refers to an automatic circuit design approach, which employs evolutionary algorithms (EAs) to generate the configurations of the programmable devices. The scalability is one of the main obstacles preventing EHW from being applied to real-world applications. Several techniques have been proposed to overcome the scalability problem. One of them is to decompose the whole circuit into several small evolvable sub-circuits. However, current techniques for scalability are mainly used to evolve combinational logic circuits. In this paper, in order to decompose a sequential logic circuit, the state decomposition, output decomposition and input decomposition are united as a three-step decomposition method (3SD). A novel extrinsic EHW system, namely 3SD---ES, which combines the 3SD method with the ( μ , ) ES (evolution strategy), is proposed, and is used for the evolutionary designing of larger sequential logic circuits. The proposed extrinsic EHW system is tested extensively on sequential logic circuits taken from the Microelectronics Center of North Carolina (MCNC) benchmark library. The results demonstrate that 3SD---ES has much better performance in terms of scalability. It enables the evolutionary designing of larger sequential circuits than have ever been evolved before.

References

[1]

A. Stoica, R. Andrei, Adaptive and evolvable hardware--a multifaceted analysis. In Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2007) , (5-8 August 2007), pp. 486-498.

Digital Library

[2]

X. Yao, T. Higuchi, Promises and challenges of evolvable hardware. IEEE Trans. Syst. Man Cybern C: Appl. Rev. 29 (1), 87-97 (1999).

Digital Library

[3]

J. Zhu, Y. Li, G. He, X. Xia, An intrinsic evolvable hardware based on multiplexer module array. In Proceedings of the 7th International Conference on Evolvable Systems: From Biology to Hardware (ICES 2007) , vol. 4684 (Wuhan, China, 21-23 September 2007), pp. 35-44.

[4]

V.K. Vassilev, D. Job, J. F. Miller, Towards the automatic design of more efficient digital circuits. In Proceedings of the Second NASA/DoD workshop on Evolvable Hardware (Palo Alto, California, 2000), pp. 151-160.

[5]

J.F. Miller, P. Thomson, Discovering novel digital circuits using evolutionary techniques. In Proceedings of IEE Colloquium on Evolvable Systems , vol. 3 (3 March 1998).

[6]

J.F. Miller, P. Thomson, T. Fogarty, Designing electronic circuits using evolutionary algorithms. Arithmetic circuits: a case study. Genet. Algorithm. Evol. Strateg. Eng. Comput. Sci. 10 , 105-131 (1997).

[7]

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

Digital Library

[8]

A.T. Soliman, H.M. Abbas, Synchronous sequential circuits design using evolutionary algorithms. In Proceedings of Electrical and Computer Engineering , vol. 4 (2-5 May 2004), pp. 2013-2016.

[9]

T. Kalganova, J.F. Miller, Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness. In Proceedings of the First NASA/DoD Workshop on Evolvable Hardware (EH'99) (Pasadena, California, 1999), pp. 54-63.

[10]

C.A. Coello Coello, A.D. Christiansen, A. Hernández Aguirre, Automated design of combinational logic circuits using genetic algorithms. In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms (ICANNGA '97) (1997), pp. 335-338.

[11]

A.T. Soliman, H.M. Abbas, Combinational circuit design using evolutionary algorithms. In Proceedings IEEE Canadian Conference on Electrical ond Computer Engineering (CCECE 2003) vol. 1 (Montreal, Canada, 4-7 May 2003), pp. 251-254.

[12]

B. Ali, A.E.A. Almaini, T. Kalganova, Evolutionary Algorithms and Their Use in the Design of Sequential Logic Circuits. Genet. Program Evol. Mach. 5 (1), 11-29 (2004).

[13]

A. Djupdal, P.C. Haddow, Evolving redundant structures for reliable circuits--lessons learned. In Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems (AHS 2007) , (5-8 August 2007), pp. 455-462.

Digital Library

[14]

G.W. Greenwood, Attaining fault tolerance through self-adaption: the strengths and weaknesses of evolvable hardware approaches. In Proceedings of the IEEE World Congress on Computational Intelligence (WCCI 2008) , vol. 5050 (Hong Kong, China, 1-6 June 2008), pp. 368-387.

[15]

Q. Ji, Y. Wang, M. Xie, J. Cui, Research on fault-tolerance of analog circuits based on evolvable hardware. In Proceedings of the 7th International Conference on Evolvable Systems: From Biology to Hardware (ICES 2007) , vol. 4684 (Wuhan, China, 21-23 September 2007), pp. 100-108.

[16]

Z. Vasicek, L. Sekanina, Hardware accelerators for cartesian genetic programming. In Proceedings of the 11th European Conference on Genetic Programming (EuroGP 2008) , vol. 4971 (Naples, Italy, 26-28 March 2008), pp. 230-241.

[17]

T. Kalganova, Bidirectional incremental evolution in extrinsic evolvable hardware. In Proceedings of the Second NASA/DoD Workshop on Evolvable Hardware (EH 2000) (Palo Alto, CA, USA, 13-15 July 2000), pp. 65-74.

[18]

C.A. Coello Coello, A.D. Christiansen, A.H. Aguirre, Towards automated evolutionary design of combinational circuits. In Proceedings of the computers and electrical engineering , vol. 27 (30 November 2000), pp. 1-28.

[19]

D. Jackson, Partitioned incremental evolution of hardware using genetic programming. In Proceedings of the 11th European Conference on Genetic Programming (EuroGP 2008) , vol. 4971 (Naples, Italy, 26-28 March 2008), pp. 86-97.

[20]

J.F. Miller, P. Thomson, Cartesian genetic programming. In Proceedings of the Third European Conference on Genetic Programming (Edinburgh, Berlin, 2000), pp. 121-132.

Digital Library

[21]

O. Muntean, L. Diosan, M. Oltean. Solving the even-N-parity problems using best subtree genetic programming. In Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems (5-8 August 2007), pp. 511-518.

Digital Library

[22]

L. Sekanina. Evolutionary design of gate-level polymorphic digital circuits. In Proceedings of the Applications of Evolutionary Computing , vol. 3449 (Lausanne, Switzerland, 31 March 2005), pp. 185-194.

[23]

E. Stomeo, T. Kalganova, C. Lambert, N. Lipnitsakya, Y. Yatskevich. On evolution of relatively large combinational logic circuits. In Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware (EH'05) (29 June -1 July 2005), pp. 59-66.

Digital Library

[24]

P. Chongstitvatana, C. Aporntewan, Improving correctness of finite-state machine synthesis from multiple partial input/output sequences. In Proceedings of the First NASA/DoD Workshop on Evolvable Hardware (Pasadena, CA, USA, 19-21 July 1999), pp. 262-266.

[25]

C. Manovit, C. Aporntewan, P. Chongstitvatana, Synthesis of synchronous sequential logic circuits from partial input/output sequences. In Proceedings of the Second International Conference on Evolvable Systems: From Biology to Hardware , vol. 1478 (1998), pp. 98-105.

[26]

C. Aporntewan, P. Chongstitvatana, An on-line evolvable hardware for learning finite-state machine. In Proceedings of International Conference on Intelligent Technologies (Bangkok, 13-15 December 2000) pp. 125-134.

[27]

A.P. Shanthi, L. Karthik Singaram, Evolution of asynchronous sequential circuits. In Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware (29 June -1 July 2005), pp. 93-96.

Digital Library

[28]

K. Slany, L. Sekanina, Fitness landscape analysis and image filter evolution using functional-level CGP. In Proceedings of the 10th European Conference on Genetic Programming , vol. 4445 (Valencia, Spain, 11-13 April 2007), pp. 311-320.

[29]

T.G.W. Gordon, P.J. Bentley, Development brings scalability to hardware evolution. In Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware (EH'05) (29 June-1 July 2005), pp. 272-279.

[30]

V.K. Vassilev, J.F. Miller, Scalability problems of digital circuit evolution evolvability and efficient designs. In Proceedings of the Second NASA/DoD workshop on Evolvable Hardware (Palo Alto, California, 2000), pp. 55-64.

[31]

M. Hartmann, P.K. Lehre, P.C. Haddow, Evolved digital circuits and genome complexity. In Proceedings of the NASA/DoD Conference on Evolvable Hardware (EH'05) (29 June-1July 2005), pp. 79-86.

[32]

T. Higuchi, M. Iwata, I. Kajitani, M. Murakawa, S. Yoshizawa, T. Furuya, Hardware evolution at gate and function levels. In Proceedings of the Biologically Inspired Autonomous Systems: Computation, Cognition and Action , Durham, North Carolina (March 1996).

[33]

M. Murakawa, S. Yoshizawa, I. Kajitani, T. Furuya, M. Iwata, T. Higuchi. Hardware evolution at function level. In Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature , vol. 1141 (1996), pp. 62-71.

[34]

J. Li, S. Huang, Adaptive salt-&-pepper noise removal: a function level evolution based approach. In Proceedings of the 2008 nasa/esa conference on adaptive hardware and systems (22-25 June 2008), pp. 391-397.

[35]

J. Torresen, A divide-and-conquer approach to evolvable hardware. In Proceedings of the Second International Conference on Evolvable Systems: From Biology to Hardware , vol. 1478 (1998), pp. 57-65.

[36]

J. Wang, C.H. Piao, C.H. Lee, Implementing multi-VRC cores to evolve combinational logic circuits in parallel. In Proceedings of the 7th International Conference on Evolvable Systems: From Biology to Hardware (ICES 2007) vol. 4684 (Wuhan, China, 21-23 September 2007), pp. 23-34.

[37]

D. Levi, Hereboy: A fast evolutionary algorithm. In Proceedings of the Second NASA/DoD Workshop on Evolvable Hardware (EH'00) (Palo Alto, CA, USA, 13-15 July 2000), pp. 17-24.

[38]

J.C. Gallagher, S. Vigraham, G. Kramer, A family of compact genetic algorithms for intrinsic evolvable hardware. IEEE Trans. Evol. Comput. 8 (2), 111-126 (2004).

Digital Library

[39]

A.M. Tyrrell, R.A. Krohling, Y. Zhou, Evolutionary algorithm for the promotion of evolvable hardware. In Proceedings of Computers and Digital Techniques , vol. 151 (18 July 2004), pp. 267-275.

[40]

T.G.W. Gordon, P.J. Bentley, Bias and scalability in evolutionary development. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005) (25-29 June 2005), pp. 83-90.

[41]

Sue-Hong Chow, Yi-Cheng Ho, Ting Ting Hwang, C.L. Liu, Low power realization of finite state machines-a decomposition approach. ACM Trans. Des. Autom. Electron. Syst. (TODAES) 1 (3), 315-340 (1996).

[42]

L. Benini, G. De Micheli, E. Macii, Designing low-power circuits: practical recipes. IEEE Circuit. Syst. Mag. 1 (1), 6-25 (2001).

[43]

L. Benini, G. De Micheli, F. Vermeulen, Finite-state machine partioning for low power. In Proceedings of the International Symposium on Circuits and Systems , (1998), vol. 2, pp. 5-8.

[44]

L. Yuan, G. Qu, T. Villa, A. Sangiovanni-Vincentelli, An FSM reengineering approach to sequential circuit synthesis by state splitting. IEEE Trans. Comput.-Aided Des. Integr. Circuit. Syst. 27 (6), 1159-1164 (2008).

Digital Library

[45]

S. Yang, Logic synthesis and optimisation benchmark user guide version 3.0 (Microelectronics Center of North Carolina, Research Triangle Park, 1991).

[46]

J. Bao, Y. Li, W. Mao, Digitial Logic (High Education Press, Beijing, 1997) (in Chinese).

[47]

E. Stomeo, T. Kalganova, C. Lambert, A novel genetic algorithm for evolvable hardware. In Proceedings of the 2006 IEEE Congress on Evolutionary Computation (Canada, 16-21 July 2006), pp. 134-141.

[48]

M. Murakawa, S. Yoshizawa, T. Higuchi, Adaptive equalization of digital communication channels using evolvable hardware. In Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware , vol. 1259 (1996), pp. 377-389.

[49]

A. Sumathi, R.S.D. Wahida Banu, Digital filter design using evolvable hardware chip for image enhancement. In Proceedings of the International Conference on Intelligent Computing, ICIC 2006 , vol. 4113 (Kunming, China, 16-19 August 2006), pp. 663-671.

[50]

A. Antola, M. Castagna, P. Gotti, M.D. Santambrogio. Evolvable Hardware: A functional level evolution framework based on impulse C. In Proceedings of the 2007 International Conference on Engineering of Reconfigurable Systems & Algorithms, ERSA (Las Vegas, Nevada, USA, 25-28 June 2007), pp. 216-219.

[51]

A. Stoica, D. Keymeulen, R. Zebulum, A. Thakoor, T. Daud, G. Klimeck, Y. Jin, R. Tawel, V. Duong, Evolution of analog circuits on field programmable transistor arrays. In Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware (2000), pp. 99-108.

[52]

J. Langeheine, J. Becker, S. Foiling, K. Meier, J. Schemmel, A CMOS FPTA chip for intrinsic hardware evolution of analog electronic circuits. In Proceedings of the 3rd NASA/DoD Workshop on Evolvable Hardware (EH 2001) (Long Beach, CA, USA, 12-14 July 2001), pp. 172-175.

[53]

M. Trefzer, J. Langeheine, K. Meier, J. Schemmel, A modular framework for the evolution of circuits on configurable transistor array architectures. In Proceedings of the first NASA/ESA conference on Adaptive Hardware and Systems (2006), pp. 32-42.

Digital Library

[54]

J. Wang, Q.S. Chen, C.H. Lee, Design and implementation of a virtual reconfigurable architecture for different applications of intrinsic evolvable hardware. Comput. Digit. Tech. IET 2 (5), 386-400 (2008).

[55]

T. Higuchi, M. Iwata, D. Keymeulen, H. Sakanashi, M. Murakawa, I. Kajitani, E. Takahashi, K. Toda, M. Salami, N. Kajihara, N. Otsu, Real-world applications of analog and digital evolvable hardware. IEEE Trans. Evol. Comput. 3 (3), 220-235 (1999).

Digital Library

[56]

L. Sekanina, Towards evolvable IP cores for FPGAs. In Proceedings of NASA/DoD Conference on Evolvable Hardware (9-11 July 2003).

Cited By

Tao YZhang Y(2018)An extrinsic EHW system for the evolutionary optimization and design of sequential circuitProceedings of the 2018 Artificial Intelligence and Cloud Computing Conference10.1145/3299819.3299832(174-180)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3299819.3299832
Tao YZhang LZhang Y(2018)A projection-based decomposition for the scalability of evolvable hardwareSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1636-220:6(2205-2218)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-015-1636-2
Tao YZhang QZhang LZhang Y(2016)A systematic EHW approach to the evolutionary design of sequential circuitsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1791-520:12(5025-5038)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s00500-015-1791-5
Show More Cited By

A three-step decomposition method for the evolutionary design of sequential logic circuits
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Generalized Disjunction Decomposition for Evolvable Hardware

Evolvable hardware (EHW) refers to self-reconfiguration hardware design, where the configuration is under the control of an evolutionary algorithm (EA). One of the main difficulties in using EHW to solve real-world problems is scalability, which limits ...
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 ...
Fast evolution of large digital circuits

Evolvable hardware (EHW) refers to self-reconfiguration hardware design, where the configuration is under the control of an evolution algorithm. One of the main difficulties in using EHW to solve real-world problems is scalability, which limits the size ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 10, Issue 3

September 2009

107 pages

ISSN:1389-2576

Issue’s Table of Contents

Copyright © Copyright © 2009 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tao YZhang Y(2018)An extrinsic EHW system for the evolutionary optimization and design of sequential circuitProceedings of the 2018 Artificial Intelligence and Cloud Computing Conference10.1145/3299819.3299832(174-180)Online publication date: 21-Dec-2018
https://dl.acm.org/doi/10.1145/3299819.3299832
Tao YZhang LZhang Y(2018)A projection-based decomposition for the scalability of evolvable hardwareSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1636-220:6(2205-2218)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s00500-015-1636-2
Tao YZhang QZhang LZhang Y(2016)A systematic EHW approach to the evolutionary design of sequential circuitsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1791-520:12(5025-5038)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s00500-015-1791-5
Tao YZhang YZhang LGu CArnold D(2014)A projection-based decomposition in EHW method for design of relatively large circuitsProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2598411(153-154)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2598411
Liang HLuo WLi ZWang X(2010)Designing combinational circuits with an evolutionary algorithm based on the repair techniqueProceedings of the 9th international conference on Evolvable systems: from biology to hardware10.5555/1885332.1885354(193-201)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.5555/1885332.1885354

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents