Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/37545| Título: | Otimização da alocação de registradores com heurísticas e metaheurísticas: um estudo comparativo |
| Título(s) alternativo(s): | Optimization of register allocation using heuristics and metaheuristics: a comparative study |
| Autor(es): | Santos, Aline Cardoso dos |
| Orientador(es): | Barbosa, Marco Antonio de Castro |
| Palavras-chave: | Programação heurística Heurística Arquitetura de software Heuristic programming Heuristic Software architecture |
| Data do documento: | 24-Jun-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Pato Branco |
| Citação: | SANTOS, Aline Cardoso dos. Otimização da alocação de registradores com heurísticas e metaheurísticas: um estudo comparativo. 2025. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Computação) - Universidade Tecnológica Federal do Paraná, Pato Branco, 2025. |
| Resumo: | A alocação de registradores é uma etapa crítica no processo de compilação, influenciando diretamente o desempenho do código executável. Devido à limitação na quantidade de registradores disponíveis em arquiteturas de computadores, é essencial adotar estratégias eficazes que reduzam a necessidade de acessos à memória. Este trabalho investiga o problema da alocação de registradores modelado como um caso de coloração de grafos, um problema conhecido por sua complexidade computacional, da classe NP-Completo. O objetivo central foi comparar diferentes técnicas heurísticas e metaheurísticas aplicadas à coloração de grafos, com foco na redução de conflitos, situações em que dois vértices adjacentes recebem a mesma cor. Foram implementados algoritmos heurísticos como o método guloso e a busca local, além de metaheurísticas como GRASP, Simulated Annealing e Busca Tabu. O algoritmo de Chaitin também foi implementado como uma base comparativa, por sua relevância histórica. A metodologia utilizou instâncias do conjunto DIMACS, amplamente adotado na literatura para avaliação de algoritmos de coloração, representando diferentes tipos e densidades de grafos. Os experimentos consideraram a execução dos métodos sob diferentes restrições de cores, simulando a quantidade limitada de registradores, e avaliaram os resultados com base no número de conflitos e no tempo de execução. As heurísticas apresentaram desempenho satisfatório em tempo, porém com maior número de conflitos. As metaheurísticas, embora mais custosas computacionalmente, obtiveram soluções de melhor qualidade, destacando-se especialmente a Busca Tabu. O algoritmo de Chaitin, embora relevante do ponto de vista teórico, mostrou desempenho inferior em relação às demais abordagens modernas. A análise estatística dos resultados confirmou diferenças significativas entre os métodos, reforçando a superioridade das metaheurísticas em cenários onde a minimização de conflitos é prioritária. Conclui-se que o uso de técnicas mais sofisticadas pode representar um ganho substancial na qualidade da alocação, especialmente em contextos com recursos limitados, e que abordagens como a Busca Tabu oferecem um equilíbrio promissor entre robustez e eficácia. |
| Abstract: | Register allocation is a critical phase in the compilation process, directly influencing the performance of the executable code. Due to the limited number of registers available in computer architectures, it is essential to adopt effective strategies that minimize memory access. This work investigates the register allocation problem modeled as a graph coloring problem, a computationally complex NP-complete class problem. The main objective was to compare different heuristic and metaheuristic techniques applied to graph coloring, focusing on reducing conflicts, which occur when adjacent vertices are assigned the same color. Heuristic algorithms such as the greedy method and local search were implemented, along with metaheuristics such as GRASP, Simulated Annealing, and Tabu Search. Chaitin’s algorithm was also implemented as a comparative baseline due to its historical relevance. The methodology used instances from the DIMACS benchmark set, widely adopted in the literature for evaluating coloring algorithms, representing graphs of varying types and densities. Experiments considered the execution of the methods under different color constraints, simulating the limited number of registers, and evaluated the results based on the number of conflicts and execution time. The heuristics showed satisfactory performance in terms of time but resulted in a higher number of conflicts. The metaheuristics, although more computationally expensive, produced higher-quality solutions, with Tabu Search standing out in particular. Chaitin’s algorithm, while theoretically important, showed inferior performance compared to more modern approaches. Statistical analysis of the results confirmed significant differences among the methods, reinforcing the superiority of metaheuristics in scenarios where conflict minimization is a priority. It is concluded that the use of more sophisticated techniques can lead to substantial improvements in allocation quality, especially in contexts with limited resources, and that approaches such as Tabu Search offer a promising balance between robustness and effectiveness. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/37545 |
| Aparece nas coleções: | PB - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| otimizacaoalocacaoregistradores.pdf | 3,92 MB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
