Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free MPGA: an evolutionary state assignment for dynamic and leakage power reduction in FSM synthesis

  • Author(s): Yanyun Tao 1 ; Yuzhen Zhang 2 ; Qinyu Wang 3 ; Jian Cao 4
    • View affiliations
  • Source: Volume 12, Issue 3, May 2018, p. 111 – 120
    DOI:  10.1049/iet-cdt.2016.0199 , Print ISSN 1751-8601, Online ISSN 1751-861X
© The Institution of Engineering and Technology
Received 03/01/2017, Accepted 10/02/2018, Revised 18/01/2018, Published 14/02/2018

As the development of deep-submicron and nano-technology, leakage power minimisation becomes as important as dynamic power reduction in IC design. In order to achieve low-power state assignment for finite-state machine (FSM) synthesis, a multi-population genetic algorithm (MPGA)-based state assignment method is proposed. MPGA consists of an outer-loop and a set of inner-GAs. In MPGA, inner-GA is a local search component for finding low-power state assignment. Selection, crossover and mutation are used to perform variations on individuals. Cost function is defined based on power dissipation formulation of complementary metal oxide semiconductor (CMOS) gate for dynamic power and leakage power estimation. The outer-loop is used to optimise the parameters of inner-genetic algorithm (GA) through population variation schema, intra-specific competition and newborn. Twenty-three FSMs that were commonly used as benchmarks are employed to test the effectiveness of MPGA and compare different state assignment methods. Experimental results show MPGA achieves a significant improvement over the previous publications both on dynamic power and leakage power reduction in most benchmarks.

Inspec keywords: logic design; finite state machines; genetic algorithms

Other keywords: population variation schema; intraspecific competition; MPGA; FSM synthesis; multipopulation genetic algorithm; mutation operator; evolutionary state assignment; CMOS gate; selection operator; crossover operator; finite-state machine; leakage power reduction

Subjects: Digital circuit design, modelling and testing; Logic design methods; Optimisation techniques; Optimisation techniques

References

    1. 1)
      • 15. Yang, J., Davis, J., Kulkarni, N., et al: ‘Dynamic and leakage power reduction of ASICs using configurable threshold logic gates’. Custom Integrated Circuits Conf., 2015.
    2. 2)
      • 20. Tao, Y., Zhang, L., Zhang, Y.: ‘An evolutionary strategy based state assignment for area-minimization finite state machines’. 2015 IEEE Symp. Series on Computational Intelligence (IEEE SSCI 2015), 2015, pp. 1491–1498.
    3. 3)
      • 32. Choudhury, P., Pradhan, S.N.: ‘Power modeling of power gated FSM and its low power realization by simultaneous partitioning and state encoding using genetic algorithm’. Int. Conf. Progress in VLSI Design and Test, 2012, pp. 19–29.
    4. 4)
      • 9. Synopsys: ‘FPGA compiler II/FPGA express VHDL reference manual’. 1999.
    5. 5)
      • 34. Klimowicz, A., Solov'Ev, V., Grzes, T.: ‘Minimization method of finite state machines for Low power design’. Euromicro Conf. Digital System Design, 2015, pp. 259–262.
    6. 6)
      • 35. Her, T.D., Wei, K.T., Kurdahi, F., et al: ‘Low-power driven state assignment of finite state machines’. 1994 IEEE Asia-Pacific Conf. Circuits and Systems, 1994. APCCAS ‘94, 1994, pp. 454–459.
    7. 7)
      • 38. Tao, Y., Zhang, L., Wang, Q., et al: ‘A multi-population evolution strategy and its application in low area/power FSM synthesis’, Nat. Comput., 2017, 4, pp. 1–23.
    8. 8)
      • 6. Tao, Y., Zhang, Y., Wang, Q.: ‘Fuzzy c-mean clustering-based decomposition with GA optimizer for FSM synthesis targeting to low power’, Eng. Appl. Artif. Intell., 2018, 68, pp. 40–52.
    9. 9)
      • 31. Pradhan, S.N., Kumar, M.T., Chattopadhyay, S.: ‘Low power finite state machine synthesis using power-gating’, Integr. VLSI J., 2011, 44, (3), pp. 175–184.
    10. 10)
      • 21. Nedjah, N., Mourelle, L.D.M.: ‘Evolutionary state assignment for synchronous finite state Machines’ (Springer, Berlin, Heidelberg, Germany, 2004).
    11. 11)
      • 36. Ahmad, I., Ali, F.M., Ul-Mustafa, R.: ‘An integrated state assignment and flip-flop selection technique for FSM synthesis⋆’, Microproc. Microsyst., 2000, 24, (3), pp. 141–152.
    12. 12)
      • 27. Wang, S.J., Horng, M.D.: ‘State assignment of finite state machines for low power applications’, Electron. Lett., 1996, 32, (25), pp. 2323–2324.
    13. 13)
      • 1. Shiue, W.T.: ‘Power/area/delay aware FSM synthesis and optimization’, Microelectron. J., 2005, 36, (2), pp. 147–162.
    14. 14)
      • 3. Villa, T., Sangiovanni-Vincentelli, A.: ‘NOVA: state assignment of finite state machines for optimal two-level logic implementation’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 1990, 9, (9), pp. 905–924.
    15. 15)
      • 5. Xia, Y, Almaini, A.E.A.: ‘Genetic algorithm based state assignment for power and area optimisation’, IEE Proc.– Comput. Digit. Tech., 2002, 149, (4), pp. 128–133.
    16. 16)
      • 16. Adil, B.: ‘Evolutionary computation for modeling and optimization’, Comput. J., 2008, 51, (6), p. 743.
    17. 17)
      • 8. Reddy, P.N., Chattopadhyay, S.: ‘Partitioning based approach for finite state machine state encoding targeting low power’, IETE J. Res., 2015, 49, (6), pp. 379–385.
    18. 18)
      • 18. Sait, S.M., Oughali, F.C., Arafeh, A.M.: ‘FSM state-encoding for area and power minimization using simulated evolution algorithm’, J. Appl. Res. Technol., 2012, 10, (6), pp. 845–858.
    19. 19)
      • 11. Lin, B, Newton, A.R.: ‘Synthesis of multiple level logic from symbolic high-level description languages’, Very Large Scale Integr., 1990, pp. 187–196.
    20. 20)
      • 19. El-Maleh, A.H., Sheikh, A.T., Sait, S.M.: ‘Binary particle swarm optimization (BPSO) based state assignment for area minimization of sequential circuits’, Appl. Soft Comput., 2013, 13, (12), pp. 4832–4840.
    21. 21)
      • 12. Sentovich, E.M., Singh, K.J., Lavagno, L., et al: ‘SIS: a system for sequential circuit synthesis’, 1998. Available at http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/ERL-92-41.pdf.
    22. 22)
      • 28. Bacchetta, P., Daldoss, L., Sciuto, D., et al: ‘Low-power state assignment techniques for finite state machines’. Proc. ISCAS IEEE Int. Symp. Circuits and Systems, 2000, 2000, vol. 642, pp. 641–644.
    23. 23)
      • 13. Kundu, S., Krishna Kumar, S., Chattopadhyay, S.: ‘Test pattern selection and customization targeting reduced dynamic and leakage power consumption’. Asian Test Symp., 2009, pp. 307–312.
    24. 24)
      • 26. Olson, E., Kang, S.M.: ‘State assignment for low-power FSM synthesis using genetic local search’. Proc. IEEE Custom Integrated Circuits Conf., 1994, 1994, pp. 140–143.
    25. 25)
      • 25. Araujo, M.P.M., Nedjah, N., Mourelle, L.D.M.: ‘Quantum-Inspired evolutionary state assignment for synchronous finite state machines’, J. Univ. Comput., 2008, 14, (15), pp. 2532–2548.
    26. 26)
      • 2. Wimer, S.: ‘On optimal flip-flop grouping for VLSI power minimization’, Oper. Res. Lett., 2013, 41, (5), pp. 486–489.
    27. 27)
      • 33. Pradhan, S.N., Choudhury, P.: ‘Low power and high testable finite state machine synthesis’. Int. Conf. Workshop on Computing and Communication, 2015, pp. 1–5.
    28. 28)
      • 24. Motta Toledo, C.F., Da Silva Arantes, M., Ribeiro de Oliveira, R.R., et al: ‘Glass container production scheduling through hybrid multi-population based evolutionary algorithm’, Appl. Soft Comput., 2013, 13, (3), pp. 1352–1364.
    29. 29)
      • 37. Mcelvain, K.: ‘Lgsynth93 benchmark set: version 4’, 1993. Available at http://www.cbl.ncsu.edu/pub/Benchmark_dirs/LGSynth93/.
    30. 30)
      • 10. Xilinx Inc.: ‘Xilinx software manual, Synth. and Sim. Design guide: encoding state’. 2000.
    31. 31)
      • 29. Kajstura, K., Kania, D.: ‘Binary tree-based low power state assignment algorithm’. Int. Conf. Computational Methods in Sciences and Engineering, 2016, p. 030007.
    32. 32)
      • 7. Xia, Y., Ye, X., Wang, L., et al: ‘A uniform framework of Low power FSM partition approach’. Int. Conf. Communications, Circuits and Systems Proc., 2006, pp. 2642–2647.
    33. 33)
      • 23. Wu, Y., Wang, Y., Liu, X.: ‘Multi-population based univariate marginal distribution algorithm for dynamic optimization problems’, J. Intell. Robot. Syst., 2010, 59, (2), pp. 127–144.
    34. 34)
      • 22. Khan, F.N.: ‘FSM state assignment for area, power and testability using iterative algorithms’, 2005, pp. 1–175.
    35. 35)
      • 14. Li, L., Choi, K., Nan, H.: ‘Effective algorithm for integrating clock gating and power gating to reduce dynamic and active leakage power simultaneously’. Int. Symp. Quality Electronic Design, 2011, pp. 1–6.
    36. 36)
      • 4. Almaini, A.E.A., Miller, J.F., Thomson, P., et al: ‘State assignment of finite state machines using a genetic algorithm’, IEE Proc. Comput. Digit. Tech., 1995, 142, (4), pp. 279–286.
    37. 37)
      • 17. El-Maleh, A., Sait, S.M., Nawaz Khan, F.: ‘Finite state machine state assignment for area and power minimization’. IEEE Int. Symp. Circuits and Systems, 2006. ISCAS 2006. Proc., 2006, 4 pp.
    38. 38)
      • 30. Jassani, A., Urquhart, N., Almaini, A.E.A.: ‘State assignment for sequential circuits using multi-objective genetic algorithm’, Comput. Digit. Tech. IET2011, 5, (4), pp. 296–305.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2016.0199
Loading

Related content

content/journals/10.1049/iet-cdt.2016.0199
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address