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

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

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

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

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.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 Title Publication 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.

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.

References

    1. 1)
    2. 2)
    3. 3)
    4. 4)
      • 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. 327332.
    5. 5)
    6. 6)
      • 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. 187196.
    7. 7)
    8. 8)
      • 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. 345350.
    9. 9)
      • 9. Sagahyroon, A., Aloul, F.A., Sudnitson, A.: ‘Low power state assignment using ILP techniques’. 15th IEEE Mediterranean Electrotechnical Conf., 2010, pp. 850855.
    10. 10)
    11. 11)
    12. 12)
      • 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. 53035306.
    13. 13)
    14. 14)
      • 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. 2730.
    15. 15)
      • 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. 269274.
    16. 16)
    17. 17)
    18. 18)
    19. 19)
      • 19. Yang, M.: ‘State assignment for finite state machine synthesis’, J. Comput., 2013, 8, (6), pp. 14061410.
    20. 20)
      • 20. Khan, F.N.: ‘FSM state assignment for area, power and testability using non-deterministic evolutionary heuristics’. Master's thesis, KFUPM, Saudi Arabia, 2005.
    21. 21)
      • 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. 845858.
    22. 22)
    23. 23)
      • 23. Chyzy, M., Kosinski, W.: ‘Evolutionary algorithm for state assignment of finite machines’. Euromicro Symp. on Digital System Design, 2002, pp. 359362.
    24. 24)
      • 24. Nedjah, N., de Macedo Mourelle, L.: ‘Evolutionary synthesis of synchronous finite state machines’. Int. Conf. on Computer Engineering and Systems, 2006, pp. 1924.
    25. 25)
    26. 26)
      • 26. Sait, S.M., Youssef, H.: ‘Iterative computer algorithms with applications in engineering: solving combinatorial optimization problems’ (IEEE Computer Society Press, CA, 1999).
    27. 27)
      • 27. Available at http://www.cbl.ncsu.edu:16080/benchmarks/LGSynth89/fsmexamples.
    28. 28)
      • 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.
    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
This is a required field
Please enter a valid email address