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

access icon free Majority-based evolution state assignment algorithm for area and power optimisation of sequential circuits

© The Institution of Engineering and Technology
Received 03/03/2015, Accepted 08/07/2015, Revised 15/06/2015, Published 01/01/2016

State assignment (SA) for finite state machines (FSMs) is one of the crucial synthesis steps in the design and optimisation of sequential circuits. In this study, we propose a majority-based evolution (MBE) SA algorithm that can be considered a variant of the well known differential evolution algorithm. Each individual is evolved based on selecting three random individuals, one of which is selected to be the best individual with a 50% probability. Then, for each state in the individual a selection is made with a 50% probability between keeping the current state or replacing it with a newly computed state. The bit values of the new state are determined based on the majority values of the state of the three selected individuals under a randomly generated probability within a predetermined range. The proposed algorithm is used for FSM state encoding targeting the optimisation of both area and power. Experimental results demonstrate the effectiveness of the proposed MBE SA algorithm in comparison with other evolutionary algorithms including genetic algorithm, binary particle swarm optimisation, Tabu search and simulated evolution.

Inspec keywords: finite state machines; microprocessor chips; polynomials

Other keywords: genetic algorithm; Tabu search; evolutionary algorithms; simulated evolution; evolution state assignment algorithm; area optimisation; majority based evolution; generated probability; FSM; differential evolution algorithm; finite state machines; power optimisation; SA; sequential circuits; binary particle swarm optimisation

Subjects: Logic design methods; Algebra; Microprocessors and microcomputers; Microprocessor chips; Algebra

References

    1. 1)
      • 9. Sagahyroon, A., Aloul, F.A., Sudnitson, A.: ‘Low power state assignment using ILP techniques’. 15th IEEE Mediterranean Electrotechnical Conf., 2010, pp. 850–855.
    2. 2)
      • 21. Oughali, F.C., Sait, S.M., 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.
    3. 3)
      • 26. Sait, S.M., Youssef, H.: ‘Iterative computer algorithms with applications in engineering: solving combinatorial optimization problems’ (IEEE Computer Society Press, CA, 1999).
    4. 4)
    5. 5)
    6. 6)
      • 24. Nedjah, N., de Macedo Mourelle, L.: ‘Evolutionary synthesis of synchronous finite state machines’. Int. Conf. on Computer Engineering and Systems, 2006, pp. 19–24.
    7. 7)
      • 20. Khan, F.N.: ‘FSM state assignment for area, power and testability using non-deterministic evolutionary heuristics’. Master's thesis, KFUPM, Saudi Arabia, 2005.
    8. 8)
    9. 9)
    10. 10)
    11. 11)
      • 12. El-Maleh, A., Sait, S.M., Khan, F.N.: ‘Finite state machine state assignment for area and power minimization’. IEEE Int. Symp. on Circuits and Systems, 2006, pp. 5303–5306.
    12. 12)
      • 19. Yang, M.: ‘State assignment for finite state machine synthesis’, J. Comput., 2013, 8, (6), pp. 1406–1410.
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • 6. Lin, B., Newton, A.R.: ‘Synthesis of multiple-level logic from symbolic high-level description languages’. IFIP Int. Conf. on Very Large Scale Integration, 1989, pp. 187–196.
    17. 17)
      • 8. Salauyou, V., Grzes, T.: ‘FSM state assignment methods for low-power design’. Sixth Int. Conf. on Computer Information Systems and Industrial Management Applications, 2007, pp. 345–350.
    18. 18)
    19. 19)
      • 15. Pradhan, S.N., Kumar, M.T., Chattopadhyay, S.: ‘Integrated power-gating and state assignment for low power FSM synthesis’. IEEE Computer Society Annual Symp. on VLSI, April 2008, pp. 269–274.
    20. 20)
      • 4. Villa, T., Sangiovanni-Vincentelli, A.: ‘Nova: state assignment of finite state machines for optimal two-level logic implementations’. 26th ACM/IEEE Conf. on Design Automation Conf., 1989, pp. 327–332.
    21. 21)
      • 27. Available at http://www.cbl.ncsu.edu:16080/benchmarks/LGSynth89/fsmexamples.
    22. 22)
      • 14. Chattopadhyay, S., Chetry, A., Biswas, S.: ‘State assignment and selection of types and polarities of flip-flops, for finite state machine synthesis’. IEEE INDICON, Kharagpur, India, December 2004, pp. 27–30.
    23. 23)
    24. 24)
    25. 25)
    26. 26)
    27. 27)
      • 28. Sentovich, E.M., Singh, K.J., Lavagno, L., et al: ‘SIS: a system for sequential circuit synthesis’. EECS Department, University of California, Berkeley. Available at http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/2010.html.
    28. 28)
      • 23. Chyzy, M., Kosinski, W.: ‘Evolutionary algorithm for state assignment of finite machines’. Euromicro Symp. on Digital System Design, 2002, pp. 359–362.
    29. 29)
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2015.0038
Loading

Related content

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