Otimização da Alocação de Registradores com GRASP, Busca Tabu e Simulated Annealing: Um estudo comparativo

Este artigo investiga o uso de metaheurísticas na alocação de registradores em compiladores, problema modelado como uma coloração de grafos. Por se tratar de um problema NP-completo, abordagens exatas tornam-se inviáveis em tempo razoável. Diante disso, foram implementadas e comparadas três metaheurísticas — GRASP, Busca Tabu (BT) e Simulated Annealing (SA) — com o objetivo de minimizar conflitos sob diferentes restrições de cores. Os experimentos foram realizados em instâncias do conjunto DIMACS, representando cenários com número limitado de registradores. A BT apresentou melhor desempenho em grafos densos, enquanto o SA obteve resultados superiores em grafos regulares e menos conectados. Já o GRASP mostrou-se competitivo em configurações específicas. Os resultados sugerem que essas técnicas têm potencial para aprimorar a qualidade da alocação de registradores e reduzir o consumo de memória, especialmente em ambientes com restrições severas de recursos.