Open AccessOptimization of state assignment in a finite state machine
Author(s) -
Reinaldo Da Silva Ribeiro,
Rafael Lima de Carvalho,
Tiago da Silva Almeida
Publication year - 2021
Publication title -
academic journal on computing, engineering and applied mathematics
Language(s) - English
Resource type - Journals
ISSN - 2675-3588
DOI - 10.20873/uft.2675-3588.2022.v3n1.p9-16
Subject(s) - simulated annealing , benchmark (surveying) , mathematical optimization , computer science , population , annealing (glass) , adaptive simulated annealing , algorithm , mathematics , materials science , demography , geodesy , sociology , composite material , geography
In this research, the application of the Simulated Annealing algorithm to solve the state assignment problem in finite state machines is investigated. The state assignment is a classic NP-Complete problem in digital systems design and impacts directly on both area and power costs as well as on the design time. The solutions found in the literature uses population-based methods that consume additional computer resources. The Simulated Annealing algorithm has been chosen because it does not use populations while seeking a solution. Therefore, the objective of this research is to evaluate the impact on the quality of the solution when using the Simulated Annealing approach. The proposed solution is evaluated using the LGSynth89 benchmark and compared with other approaches in the state-of-the-art. The experimental simulations point out an average loss in solution quality of 11%, while an average processing performance of 86%. The results indicate that it is possible to have few quality losses with a significant increase in processing performance.