ColorAnt-RT: Ant Colony Graph Coloring Algorithm Applied to Register Allocation

• Carla Negri Lintzmayer UNICAMP
• Mauro Henrique Mulati UEM
• Anderson Faustino da Silva UNICENTRO

Abstract

This paper presents the ColorAnt-RT algorithms for graph coloring problems, that was developed to be used in a register allocator. The experiments demonstrate that ColorAnt₃-RT is a promising option among the developed ones in finding good approximations for several graphs. Besides, the experiments also demonstrate that our register allocator outperforms the George-Appel register allocator.

References

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.