Implementação de meta-heurísticas para o problema da coloração de vértices e da alocação de registradores

Abstract

The Graph Coloring Problem is one of the major challenges in computing, having its origins in the 19th century, and being one of the great foundations of graph theory. It consists in coloring regions of a graph, such as vertices or edges, so that neighboring areas do not receive the same color. Several other problems can be faced through an approach via Graph Coloring, such as Register Allocation in the compilation process. Here, variables that intersect their life span – time between declaration and last use – cannot be allocated to the same register, and at least one of them must be stored in memory. Here, variables that intersect their live-ranges – time between declaration and last use – cannot be allocated to the same register, and at least one of them must be stored in memory. Both problems mentioned belong to the NP-Complete class, and deal with the management of few resources, colors and registers, being necessary to work intelligently in their utilization. Finding the exact solution of this type of problem demands exponential computation time, being the meta-heuristics extremely suitable alternatives to find solutions of quality in polynomial time. This work proposed the implementation of Tabu Search and Simulated Annealing meta-heuristics for the Graph Coloring Problem, and for the problem derived from it, Register Allocation, with the objective of investigating the behavior of these methods and comparing them with each other. After a series of experiments with DIMACS test cases, it was possible to verify that the implemented Tabu Search is capable of producing better quality solutions for Graph Coloring, while Simulated Annealing had lower execution times. For Register Allocation, Tabu Search proved to be able to achieve better solutions, with less execution time.