Monografia

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

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,...

ver descrição completa

Autor principal: Ribeiro, Reinaldo da Silva
Grau: Monografia
Idioma: pt_BR
Publicado em: Universidade Federal do Tocantins 2022
Assuntos:
Máquina de Estados Finitos
Simulated Annealing
Sistemas Digitais
Metaheurística
Ciência da computação
Acesso em linha: http://hdl.handle.net/11612/4386
id ir-11612-4386
recordtype dspace
spelling ir-11612-43862022-11-18T06:00:59Z Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing Ribeiro, Reinaldo da Silva Carvalho, Rafael Lima de Almeida, Tiago da Silva Máquina de Estados Finitos Simulated Annealing Sistemas Digitais Metaheurística Ciência da computação 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. Neste projeto de pesquisa, a aplicação do algoritmo Simulated Annealing para resolver o problema de atribuição de estados em uma máquina de estados finitos foi investigada. O problema de atribuição de estado é um problema clássico em projeto de sistemas digitais e impacta diretamente no custo, tanto de área quanto de energia, no tempo de projeto, por se tratar de um problema NP-Completo. O algoritmo Simulated Annealing foi escolhido por não utilizar populações no espaço de busca da solução, e a literatura traz métodos mais complexos e com maior esforço computacional, portanto o objetivo foi avaliar o impacto na qualidade da solução com um método mais simples . Nos experimentos realizados, a qualidade da solução caiu em menor porcentagem, em média houve uma perda de 14,29%. E o percentual de ganho de processamento foi maior que o porcentual de perda, em média 58,67%. Isso mostra que é possível ter poucas perdas de qualidade com um aumento significativo no desempenho. 2022-11-17T12:47:40Z 2022-11-17T12:47:40Z 2022 Monografia RIBEIRO, Reinaldo da Silva. Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing. 2022. 16 f. TCC (Graduação) - Curso de Ciência da Computação, Universidade Federal do Tocantins, Palmas, 2022. http://hdl.handle.net/11612/4386 pt_BR application/pdf Universidade Federal do Tocantins Palmas Ciência da Computação Palmas Graduação
institution Repositório Institucional - Universidade Federal do Tocantins - UFT
collection RepositorioUFT
language pt_BR
topic Máquina de Estados Finitos
Simulated Annealing
Sistemas Digitais
Metaheurística
Ciência da computação
spellingShingle Máquina de Estados Finitos
Simulated Annealing
Sistemas Digitais
Metaheurística
Ciência da computação
Ribeiro, Reinaldo da Silva
Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
topic_facet Máquina de Estados Finitos
Simulated Annealing
Sistemas Digitais
Metaheurística
Ciência da computação
description 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.
author_additional Carvalho, Rafael Lima de
author_additionalStr Carvalho, Rafael Lima de
format Monografia
author Ribeiro, Reinaldo da Silva
title Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
title_short Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
title_full Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
title_fullStr Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
title_full_unstemmed Alocação de estados quase ótima em máquina de estados finitos utilizando Simulated Annealing
title_sort alocação de estados quase ótima em máquina de estados finitos utilizando simulated annealing
publisher Universidade Federal do Tocantins
publishDate 2022
url http://hdl.handle.net/11612/4386
_version_ 1787134226915655680
score 11.755432

Registros relacionados