Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing

Abstract

In this research project, the application of the Simulated Annealing algorithm to solve the state assignment problem in a finite state machine was investigated. The state assignment problem is a classic problem in digital systems design and directly impacts on the cost, both area and power costs, on design time, as it is an NP-Complete problem. The Simulated Annealing algorithm was chosen because it does not use populations in the search space for the solution, and the literature brings more complex methods with greater computational effort, so the objective was to evaluate the impact on the quality of the solution with a simpler method. In the experiments performed, the dropin solution quality was smaller in percentage, on average there was a loss of 14.29%. And the processing gain percentage higher, on average 58.67%. This shows that it is possible to have few quality losses with a significant increase in performance.