Abstract
Finding a low area/power state assignment is a NP-hard problem in finite-state machines synthesis. In order to solve this problem, this study proposes a multi-population evolution strategy, denoted as MPES. MPES accomplishes the task by using inner-ES and outer-ES. In inner-ES, subpopulations evolve separately and are responsible for local search in different regions. Alternating (μ + λ) strategy and (μ, λ) strategy are employed to select parental individuals from the ranked population for mutation. Three mutation operators, ‘replacement’, ‘2-exchange’ and ‘shifting’, perform on the parental individuals to generate offspring. Different fitness functions are defined for area and power evaluation, respectively. Outer-ES acts as a shell to optimize the subpopulations of inner-ES for better and better solutions. In outer-ES, the parameters of evolving subpopulations are represented by individuals of outer-population. Outer-ES performs selection and mutation on the outer-population to change the parameters of evolving subpopulations in inner-ES for generating better solutions. Two assistant operators, competition and newborn, work together for poor subpopulations elimination and creating new subpopulations. By using two-level ES, MPES is able to obtain multiple good solutions. We test the MPES extensively on benchmarks, and compare it with previous state assignment methods from various aspects. The experimental results show MPES achieved a significant cost reduction of area and power dissipation over the previous publications.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
ABC:A system for sequential synthesis and verification. Berkeley logic synthesis and verification group. http://www.eecs.berkeley.edu/~alanmi/abc/
Al Jassani BA, Urquhart N, Almaini AEA (2011) State assignment for sequential circuits using multi-objective genetic algorithm. IET Comput Digital Tech 5(4):296–305
Ali B, Almaini AEA, Kalganova T (2004) Evolutionary algorithms and their use in the design of sequential logic circuits. Genet Program Evolvable Mach 05:11–29
Almaini AEA, Miller JF, Thomson P (1995) State assignment of finite state machines using a genetic algorithm. IEE Proc Comput Digit Tech 142(4):279–286
Amaral JN, Tumer K, Ghosh J (1995) Designing genetic algorithms for the state assignment problem. IEEE Trans Syst Man Cybern 25(4):100–108
Ashlock D (2006) Evolutionary computation for modeling and optimization. Springer, Berlin. ISBN 0-387-22196-4
Bacchetta P, Daldoss L, Sciuto D et al (2000) Low-power state assignment techniques for finite state machines. In: IEEE international symposium on circuits and systems, 2000. Proceedings. ISCAS. IEEE, 2000:641–644 vol.2
Berkeley (1992) Electronics Research Laboratory, SIS: a system for sequential circuit synthesis, Release 1992.05. http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/ERL-92-41.pdf
Beyer HG (1992) Some aspects of the ‘evolution strategy’ for solving tsp-like optimization problems. In: Männer R, Manderick B (eds) Parallel problem solving from nature, 2. Elsevier, Amsterdam, pp 361–370
Beyer HG, Schwefel HP (2002) Evolution strategies: a comprehensive introduction. J Nat Comput 1(1):3–52
Chattopadhyay S (2005) Area conscious state assignment with flip flop and output polarity selection for finite state machine synthesis genetic algorithm approach. Comput J 48(4):443–450
Chattopadhyay S, Reddy P (2004) Finite state machine state assignment targeting low power consumption. IEEE Proc Comput Digit Tech 151:61–70
Cho S, Park A (2004) New synthesis technique of sequential circuits for low power and testing. Curr Appl Phys. 04:83–86
Devadas, Ma HT, Newton AR, Vincentelli Sangiovanni (1987) MUSTANG: state assignment of finite state machines for optimal multi-level logic implementations. In: International conference on computer-aided design
Du X, Hactel G, Lin B (1990) MUSE: a multilevel symbolic encoding algorithm for state assignment. IEEE Trans Comput Aided Des Integr Circuits Syst 10(1):367–376
El-Maleh AH, Sait SM, Nawaz Khan F (2006)“Finite state machine state assignment for area and power minimization. In: Proceeding of IEEE international symposium on circuits and systems, ISCAS 2006, 21–24 May
El-Maleh AH, Sheikhb Ahmad T, Sait Sadiq M (2013) Binary particle swarm optimization (BPSO) based state assignment for area minimization of sequential circuits. Appl Soft Comput 13:4832–4840
El-Maleh AH, Sait SM, Bala A (2015) State assignment for area minimization of sequential circuits based on cuckoo search optimization. Comput Electr Eng 44(C):13–23
Gergel N, Craft S, Lach J (2003) Modeling QCA for area minimization in logic synthesis. In: ACM Great Lakes symposium on VLSI 2003, Washington, DC, USA, April. 2003, pp 60–63
Li L, Tang K (2015) History-based topological speciation for multimodal optimization. IEEE Trans Evol Comput 19(1):136–150
Li B, Shi X, Chen J et al (2016) On the unbiasedness of multivariant optimization algorithm. Appl Soft Comput 48:230–239
Lin B, Newton AR (1989) Synthesis of multi-level logic from symbolic high-level description languages. In Proceedings of the IFIP TC 10/WG 10.5 International Conference on Very Large Scale Integration. Federal Republic of Germany, 1989 August, pp 187–196
Mashiko H, Kohira Y (2016) Area minimization method for CMOS circuits using constraint programming in ID-layout style. In: International symposium on Vlsi design, Automation and Test
Nawaz Khan F (2005) FSM state assignment for area, power and testability using iterative algorithms. Thesis. Master of Science. King Fahd Unversity of Petroleum and Minerals
Olson E, Kang SM (1994) State assignment for low-power FSM synthesis using genetic local search. In: IEEE custom integrated circuits conference, pp 140–143
Sait SM, Oughali FC, Arafeh AM (2012) FSM state-encoding for area and power minimization using simulated evolution algorithm. J Appl Res Technol 10(6):845–858
Shang R, Wang Y, Wang J et al (2014) A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem. Inf Sci 277(2):609–642
Shiue WT (2005) Power/area/delay aware FSM synthesis and optimization. Microelectron J 36(2):147–162
Tao Y, Zhang Y, Cao J et al (2013a) A module-level three-stage approach to the evolutionary design of sequential logic circuits. Genet Program Evolvable Mach 14(2):191–219
Tao Y, Li M, Cao J (2013b) A new dynamic population variation in genetic programming. Comput inform 32:1001–1025
Tao Y, Zhang Q, Zhang L et al (2015a) A systematic EHW approach to the evolutionary design of sequential circuits. Soft Comput. https://doi.org/10.1007/s00500-015-1791-5
Tao Y, Zhang L, Zhang Y (2015) An evolutionary strategy based state assignment for area-minimization finite state machines. In: Proceeding of 2015 IEEE symposium series on computational intellgience(SSCI2015). pp 1491–1498
Toledo CFM, Arantes MDS, Almada-Lobo B (2012) Glasscontainer production scheduling through hybrid multi-population based evolutionary algorithm. Appl Soft Comput 13(3):1352–1364
Villa T, Sangiovanni-Vincentelli A (1990) NOVA: state assignment of finite state machines for optimal two-level logic implementation. IEEE Trans Comput Aided Des Integr Circuits Syst 9(9):905–924
Wang SJ, Horng MD (1996) State assignment of finite state machines for low power applications. Electron Lett 32(25):2323–2324
Wu Y, Wang Y, Liu X (2010) Multi-population based univariate marginal distribution algorithm for dynamic optimization problems. J Intell Robot Syst 59(2):127–144
Xia Y, Almaini AEA (2002) Genetic algorithm based state assignment for power and area optimization. IEEE Proc Comput Digit Tech 149(4):128–133
Xia Y, Almaini AEA, Wu X (2003) Power optimization of finite state machines based on genetic algorithm. J Electron 20(3):194–201
Xia Y, Ye X, Wang L (2006) A uniform framework of low power FSM partition approach. In: Proceeding of IEEE International Conference on communication, circuits and systems, China, 2006, pp 2642–2646
Yang M, Wang LL, Tong JR et al (2008) Techniques for dual forms of Reed–Muller expansion conversion. Integr VLSI J 41(1):113–122
Acknowledgements
This research is supported by the Natural Science Found of the Jiangsu Higher Education Institutions of China (Grant No. 13KJB520023) and National Natural Science Found of China(Grant No. 61502327)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tao, Y., Zhang, L., Wang, Q. et al. A multi-population evolution stratagy and its application in low area/power FSM synthesis. Nat Comput 18, 139–161 (2019). https://doi.org/10.1007/s11047-017-9659-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-017-9659-5