ColorAnt-RT: Algoritmo de Coloração de Grafo que utiliza Colônia de Formigas aplicado a Alocação de Registradores
Resumo
Este artigo apresenta os algoritmos ColorAnt-RT para o problema da coloração de grafos, os quais foram desenvolvidos para serem utilizados em um alocador de registradores. Os experimentos demonstram que ColorAnt3-RT é uma boa opção dentre os desenvolvidos para encontrar boas aproximações para diversas classes de grafos. Além disto, os experimentos também demonstram que o alocador de registradores implementado possui um desempenho superior aquele obtido pelo alocador de registradores proposto por George e Appel.
Referências
Blöchliger, I. and Zufferey, N. (2008). A graph coloring heuristic using partial solutions and a reactive tabu scheme. Computers & Operations Research, 35(3):960–975.
Briggs, P., Cooper, K. D., and Torczon, L. (1994). Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst., 16:428–455.
Chaitin, G. J. (1982). Register Allocation & Spilling via Graph Coloring. SIGPLAN Notices, 17:98–101.
Costa, D. and Hertz, A. (1997). Ants Can Colour Graphs. The Journal of the Operational Research Society, 48(3):295–305.
Dorigo, M. and Stützle, T. (2004). Ant Colony Optimization. Bradford Books. MIT Press, Cambridge, Massachusetts.
George, L. and Appel, A. W. (1996). Iterated register coalescing. ACM Transactions on Programming Languages and Systems, 18:300–324.
Hertz, A. and Zufferey, N. (2006). A New Ant Algorithm for Graph Coloring. In Workshop on Nature Inspired Cooperative Strategies for Optimization NICSO, pages 51–60, Granada, Espanha.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011a). Algoritmo Heurśtico Baseado em Colônia de Formigas Artificiais ColorAnt2 com Busca Local Aplicado ao Problema de Coloração de Grafo. In X Congresso Brasileiro de Inteligência Computacional, Fortaleza, BRA.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011b). Register Allocation with Graph Coloring by Ant Colony Optimization. In XXX International Conference of the Chilean Computer Science Society, Curico, Chile.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011c). RT-ColorAnt: Um Algoritmo Heurístico Baseado em Colônia de Formigas Artificiais com Busca Local para Colorir Grafos. In XLIII Simposio Brasileiro de Pesquisa Operacional 2011, Ubatuba, SP, BRA.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011d). Toward Better Performance of ColorAnt ACO Algorithm. In XXX International Conference of the Chilean Computer Science Society, Curico, Chile.
Plumettaz, M., Schindl, D., and Zufferey, N. (2010). Ant local search and its efficient adaptation to graph colouring. Journal of the Operational Research Society, 61(5):819–826.
Shawe-Taylor, J. and Zerovnik, J. (2001). Ants and graph coloring. In International Conference on Artificial Neural Nets and Genetic Algorithms, pages 276–279.
Wu, S. and Li, S. (2007). Extending Traditional Graph-Coloring Register Allocation Exploiting Meta-heuristics for Embedded Systems. In Proceedings of the Third International Conference on Natural Computation, pages 324–329.
Briggs, P., Cooper, K. D., and Torczon, L. (1994). Improvements to graph coloring register allocation. ACM Trans. Program. Lang. Syst., 16:428–455.
Chaitin, G. J. (1982). Register Allocation & Spilling via Graph Coloring. SIGPLAN Notices, 17:98–101.
Costa, D. and Hertz, A. (1997). Ants Can Colour Graphs. The Journal of the Operational Research Society, 48(3):295–305.
Dorigo, M. and Stützle, T. (2004). Ant Colony Optimization. Bradford Books. MIT Press, Cambridge, Massachusetts.
George, L. and Appel, A. W. (1996). Iterated register coalescing. ACM Transactions on Programming Languages and Systems, 18:300–324.
Hertz, A. and Zufferey, N. (2006). A New Ant Algorithm for Graph Coloring. In Workshop on Nature Inspired Cooperative Strategies for Optimization NICSO, pages 51–60, Granada, Espanha.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011a). Algoritmo Heurśtico Baseado em Colônia de Formigas Artificiais ColorAnt2 com Busca Local Aplicado ao Problema de Coloração de Grafo. In X Congresso Brasileiro de Inteligência Computacional, Fortaleza, BRA.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011b). Register Allocation with Graph Coloring by Ant Colony Optimization. In XXX International Conference of the Chilean Computer Science Society, Curico, Chile.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011c). RT-ColorAnt: Um Algoritmo Heurístico Baseado em Colônia de Formigas Artificiais com Busca Local para Colorir Grafos. In XLIII Simposio Brasileiro de Pesquisa Operacional 2011, Ubatuba, SP, BRA.
Lintzmayer, C. N., Mulati, M. H., and da Silva, A. F. (2011d). Toward Better Performance of ColorAnt ACO Algorithm. In XXX International Conference of the Chilean Computer Science Society, Curico, Chile.
Plumettaz, M., Schindl, D., and Zufferey, N. (2010). Ant local search and its efficient adaptation to graph colouring. Journal of the Operational Research Society, 61(5):819–826.
Shawe-Taylor, J. and Zerovnik, J. (2001). Ants and graph coloring. In International Conference on Artificial Neural Nets and Genetic Algorithms, pages 276–279.
Wu, S. and Li, S. (2007). Extending Traditional Graph-Coloring Register Allocation Exploiting Meta-heuristics for Embedded Systems. In Proceedings of the Third International Conference on Natural Computation, pages 324–329.
Publicado
16/07/2012
Como Citar
LINTZMAYER, Carla Negri; MULATI, Mauro Henrique; SILVA, Anderson Faustino da.
ColorAnt-RT: Algoritmo de Coloração de Grafo que utiliza Colônia de Formigas aplicado a Alocação de Registradores. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 31. , 2012, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 31-40.
