State assignment for sequential circuits using multi-objective genetic algorithm

B.A. Al Jassani; N. Urquhart; A.E.A. Almaini

State assignment for sequential circuits using multi-objective genetic algorithm

Access Full Text

State assignment for sequential circuits using multi-objective genetic algorithm

Author(s): B.A. Al Jassani ; N. Urquhart ; A.E.A. Almaini
DOI: 10.1049/iet-cdt.2010.0045

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): B.A. Al Jassani ¹ ; N. Urquhart ¹ ; A.E.A. Almaini ¹
- Affiliations: 1: Edinburgh Napier University, Edinburgh, UK
Source: Volume 5, Issue 4, July 2011, p. 296 – 305
DOI: 10.1049/iet-cdt.2010.0045 , Print ISSN 1751-8601, Online ISSN 1751-861X

Published

In this study, a new approach using a multi-objective genetic algorithm (MOGA) is proposed to determine the optimal state assignment with less area and power dissipations for completely and incompletely specified sequential circuits. The goal is to find the best assignments which reduce the component count and switching activity. The MOGA employs a Pareto ranking scheme and produces a set of state assignments, which are optimal in both objectives. The ESPRESSO tool is used to optimise the combinational parts of the sequential circuits. Experimental results are given using a personal computer with an Intel CPU of 2.4 GHz and 2 GB RAM. The algorithm is implemented using C++ and fully tested with benchmark examples. The experimental results show that saving in components and switching activity are achieved in most of the benchmarks tested compared with recent published research.

References

1. 1)
  - Z. Michalewicz . (1996) Genetic algorithms+data structures=evolutionary programs.
2. 2)
  - J.-K. Rho , G. Hachtel , F. Somenzi , R. Jacoby . Exact and Heuristic algorithms for the minimization of incompletely specified state machines. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 2 , 167 - 177
3. 3)
  - W.M. Aly . Solving the state assignment problem using stochastic search aided with simulated annealing. Am. J. Eng. Appl. Sci. , 4 , 710 - 714
4. 4)
  - http://sontrak.com/download_esp.aspx, Sontrak, Technical software, accessed March 2010.
5. 5)
  - J. Hartmains , R.E. Stearns . (1966) Algebraic structure theory of sequential machines.
6. 6)
  - A.E.A. Almaini , J.F. Miller , P. Thomson , S. Billina . State assignment of finite state machines using a genetic algorithm. IEE Proc. Comput. Digit, Tech. , 4 , 279 - 286
7. 7)
  - K. Abdullah , W.C. David , A.E. Smith . Multi-objective optimization using genetic algorithms: a tutorial. Reliability Engineering and System Safety 91 , 992 - 1007
8. 8)
  - W.-T. Shiue . Novel state minimization and state assignment in finite state machine design for low power portable devices. Integr. VLSI J. , 549 - 570
9. 9)
  - A.E.A. Almaini . Sequential machine implementations using universal logic modules. IEEE Trans. Comput. , 10 , 951 - 960
10. 10)
  - C. Tsui , M. Pedram , C. Chen , A.M. Despain . Low power state assignment targeting two and multi-level logic implementations. ICCAD , 82 - 87
11. 11)
  - T. Villa , A. Sangiovanni-Vincentelli . NOVA: state assignment of finite state machine for optimal two-level logic implementation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 9 , 905 - 924
12. 12)
  - S. Chow , Y. Ho , T. Hwang , C. Liu . Low power realization of finite state machines – a decomposition approach. ACM Trans. Des. Autom. Electron. Syst. , 3 , 315 - 340
13. 13)
  - K. Deb , A. Pratap , S. Agarwal , T. Meyarivan . A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. , 2 , 182 - 197
14. 14)
  - X. Yinshui , A.E.A. Almaini , W. Xunwei . Power optimization of finite state machines based on genetic algorithm. J. Electron. , 3 , 194 - 201
15. 15)
  - Olson, E.P.: `Optimal state assignment of sequential circuits using a genetic local search with flexible cost functions', 1995, Phd, Urbana-Champaign, University of Illinois.
16. 16)
  - S. Chattopadhyay . Area conscious state assignment with flip flop and output polarity selection for finite state machine synthesis genetic algorithm approach. Comput. J. , 4 , 443 - 450
17. 17)
  - B. Ali , A.E.A. Almaini , T. Kalganova . Evolutionary algorithms and their use in the design of sequential logic circuits. Genet. Program. Evol. Mach. , 11 - 29
18. 18)
  - Z. Michalewicz , D.B. Fogel . (2004) How to solve it: modern heuristics.
19. 19)
  - D.E. Goldberg . (1989) Genetic algorithms in search, optimisation, and machinelearning.
20. 20)
  - L. Jóźwiak , A. Ślusarczyk . General decomposition of incompletely specified sequential machines with multi-state behaviour realization. J. Syst. Archit. , 445 - 492
21. 21)
  - L. Benini , G. Micheli De . State assignment for low power dissipation. IEEE Custom. Integr. Circuits Conf. , 3 , 136 - 139
22. 22)
  - S. Cho , S. Park . A new synthesis technique of sequential circuits for low power and testing. Curr. Appl. Phys. , 83 - 86
23. 23)
  - Xia, Y., Ye, X., Wang, L., Tao, W., Almaini, A.E.A.: `A uniform framework of low power FSM partition approach', IEEE Int. Conf. on Commun., Circuits and Systems, 2006, China, p. 2642–2646.
24. 24)
  - S.K. Hong , I.C. Park , S.H. Hwang , C.M. Kyung . State assignment in finite state machines for minimal switching power consumption. IEE Electron. Lett. , 8 , 627 - 629
25. 25)
  - S. Chattopadhyay , P.N. Reddy . Finite state machine state assignment targeting low power consumption. IEE Proc. Comput. Dig. Technol. , 1 , 61 - 70
26. 26)
  - T.A. Dolotta , E.J. McCluskey . The coding of inernal states of sequential circuits. IEEE Trans. Electron. Comput. , 549 - 562
27. 27)
  - S. Gören , F.J. Ferguson . On state reduction of incompletely specified finite state machines. Comput. Electr. Eng. , 58 - 69

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

State assignment for sequential circuits using multi-objective genetic algorithm

State assignment for sequential circuits using multi-objective genetic algorithm

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content