http://iet.metastore.ingenta.com
1887

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

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

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

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

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 to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • W.T. Shiue .
        1. Shiue, W.T.: ‘Power/area/delay aware FSM synthesis and optimization’, Microelectron. J., 2005, 36, (2), pp. 147162.
        . Microelectron. J. , 2 , 147 - 162
    2. 2)
      • S. Wimer .
        2. Wimer, S.: ‘On optimal flip-flop grouping for VLSI power minimization’, Oper. Res. Lett., 2013, 41, (5), pp. 486489.
        . Oper. Res. Lett. , 5 , 486 - 489
    3. 3)
      • T. Villa , A. Sangiovanni-Vincentelli .
        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. 905924.
        . IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. , 9 , 905 - 924
    4. 4)
      • A.E.A. Almaini , J.F. Miller , P. Thomson .
        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. 279286.
        . IEE Proc. Comput. Digit. Tech. , 4 , 279 - 286
    5. 5)
      • Y Xia , A.E.A. Almaini .
        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. 128133.
        . IEE Proc.– Comput. Digit. Tech. , 4 , 128 - 133
    6. 6)
      • Y. Tao , Y. Zhang , Q. Wang .
        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. 4052.
        . Eng. Appl. Artif. Intell. , 40 - 52
    7. 7)
      • Y. Xia , X. Ye , L. Wang .
        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. 26422647.
        . Int. Conf. Communications, Circuits and Systems Proc. , 2642 - 2647
    8. 8)
      • P.N. Reddy , S. Chattopadhyay .
        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. 379385.
        . IETE J. Res. , 6 , 379 - 385
    9. 9)
      • (1999)
        9. Synopsys: ‘FPGA compiler II/FPGA express VHDL reference manual’. 1999.
        .
    10. 10)
      • (2000)
        10. Xilinx Inc.: ‘Xilinx software manual, Synth. and Sim. Design guide: encoding state’. 2000.
        .
    11. 11)
      • B Lin , A.R. Newton .
        11. Lin, B, Newton, A.R.: ‘Synthesis of multiple level logic from symbolic high-level description languages’, Very Large Scale Integr., 1990, pp. 187196.
        . Very Large Scale Integr. , 187 - 196
    12. 12)
      • E.M. Sentovich , K.J. Singh , L. Lavagno . (1998)
        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.
        .
    13. 13)
      • S. Kundu , S. Krishna Kumar , S. Chattopadhyay .
        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. 307312.
        . Asian Test Symp. , 307 - 312
    14. 14)
      • L. Li , K. Choi , H. Nan .
        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. 16.
        . Int. Symp. Quality Electronic Design , 1 - 6
    15. 15)
      • J. Yang , J. Davis , N. Kulkarni .
        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.
        . Custom Integrated Circuits Conf.
    16. 16)
      • B. Adil .
        16. Adil, B.: ‘Evolutionary computation for modeling and optimization’, Comput. J., 2008, 51, (6), p. 743.
        . Comput. J. , 6 , 743
    17. 17)
      • A. El-Maleh , S.M. Sait , F. Nawaz Khan .
        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.
        . IEEE Int. Symp. Circuits and Systems, 2006. ISCAS 2006. Proc.
    18. 18)
      • S.M. Sait , F.C. Oughali , A.M. Arafeh .
        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. 845858.
        . J. Appl. Res. Technol. , 6 , 845 - 858
    19. 19)
      • A.H. El-Maleh , A.T. Sheikh , S.M. Sait .
        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. 48324840.
        . Appl. Soft Comput. , 12 , 4832 - 4840
    20. 20)
      • Y. Tao , L. Zhang , Y. Zhang .
        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. 14911498.
        . 2015 IEEE Symp. Series on Computational Intelligence (IEEE SSCI 2015) , 1491 - 1498
    21. 21)
      • N. Nedjah , L.D.M. Mourelle . (2004)
        21. Nedjah, N., Mourelle, L.D.M.: ‘Evolutionary state assignment for synchronous finite state Machines’ (Springer, Berlin, Heidelberg, Germany, 2004).
        .
    22. 22)
      • F.N. Khan . (2005)
        22. Khan, F.N.: ‘FSM state assignment for area, power and testability using iterative algorithms’, 2005, pp. 1175.
        .
    23. 23)
      • Y. Wu , Y. Wang , X. Liu .
        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. 127144.
        . J. Intell. Robot. Syst. , 2 , 127 - 144
    24. 24)
      • C.F. Motta Toledo , M. Da Silva Arantes , R.R. Ribeiro de Oliveira .
        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. 13521364.
        . Appl. Soft Comput. , 3 , 1352 - 1364
    25. 25)
      • M.P.M. Araujo , N. Nedjah , L.D.M. Mourelle .
        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. 25322548.
        . J. Univ. Comput. , 15 , 2532 - 2548
    26. 26)
      • E. Olson , S.M. Kang .
        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. 140143.
        . Proc. IEEE Custom Integrated Circuits Conf., 1994 , 140 - 143
    27. 27)
      • S.J. Wang , M.D. Horng .
        27. Wang, S.J., Horng, M.D.: ‘State assignment of finite state machines for low power applications’, Electron. Lett., 1996, 32, (25), pp. 23232324.
        . Electron. Lett. , 25 , 2323 - 2324
    28. 28)
      • P. Bacchetta , L. Daldoss , D. Sciuto .
        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. 641644.
        . Proc. ISCAS IEEE Int. Symp. Circuits and Systems, 2000 , 641 - 644
    29. 29)
      • K. Kajstura , D. Kania .
        29. Kajstura, K., Kania, D.: ‘Binary tree-based low power state assignment algorithm’. Int. Conf. Computational Methods in Sciences and Engineering, 2016, p. 030007.
        . Int. Conf. Computational Methods in Sciences and Engineering , 030007
    30. 30)
      • A. Jassani , N. Urquhart , A.E.A. Almaini .
        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. 296305.
        . Comput. Digit. Tech. IET , 4 , 296 - 305
    31. 31)
      • S.N. Pradhan , M.T. Kumar , S. Chattopadhyay .
        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. 175184.
        . Integr. VLSI J. , 3 , 175 - 184
    32. 32)
      • P. Choudhury , S.N. Pradhan .
        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. 1929.
        . Int. Conf. Progress in VLSI Design and Test , 19 - 29
    33. 33)
      • S.N. Pradhan , P. Choudhury .
        33. Pradhan, S.N., Choudhury, P.: ‘Low power and high testable finite state machine synthesis’. Int. Conf. Workshop on Computing and Communication, 2015, pp. 15.
        . Int. Conf. Workshop on Computing and Communication , 1 - 5
    34. 34)
      • A. Klimowicz , V. Solov'Ev , T. Grzes .
        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. 259262.
        . Euromicro Conf. Digital System Design , 259 - 262
    35. 35)
      • T.D. Her , K.T. Wei , F. Kurdahi .
        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. 454459.
        . 1994 IEEE Asia-Pacific Conf. Circuits and Systems, 1994. APCCAS ‘94 , 454 - 459
    36. 36)
      • I. Ahmad , F.M. Ali , R. Ul-Mustafa .
        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. 141152.
        . Microproc. Microsyst. , 3 , 141 - 152
    37. 37)
      • K. Mcelvain . (1993)
        37. Mcelvain, K.: ‘Lgsynth93 benchmark set: version 4’, 1993. Available at http://www.cbl.ncsu.edu/pub/Benchmark_dirs/LGSynth93/.
        .
    38. 38)
      • Y. Tao , L. Zhang , Q. Wang .
        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. 123.
        . Nat. Comput. , 1 - 23
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
This is a required field
Please enter a valid email address