A genetic algorithm for register allocation
Khaled M. Elleithy, E.G. Abd-El-Fattah · 2003
In this paper we introduce a new genetic algorithm for register allocation. A merge operator is used to generate new individual solutions. The number of steps required to examine all pairs in the population matrix to generate n/sup 2/ (n is the population matrix size). Generating an offspring from the parents needs m steps (m number of nodes). The total number of steps required by the algorithm is n/sup 2/m, that is the genetic algorithm has a linear time complexity in terms of number of nodes. The experimental results show optimal solutions in many of the graphs used for testing.