Title :
A genetic algorithm for register allocation
Author :
Elleithy, K.M. ; Abd-El-Fattah, E.G.
Author_Institution :
Dept. of Comput. Eng., King Fahd Univ. of Pet. & Miner., Dhahran, Saudi Arabia
Abstract :
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 n2 (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 n2m, 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
Keywords :
circuit optimisation; computational complexity; genetic algorithms; logic CAD; genetic algorithm; linear time complexity; logic CAD; merge operator; offspring; parents; population matrix; register allocation; Biological cells; Genetic algorithms; Genetic engineering; Hamming distance; Machine learning; Minerals; Pattern classification; Petroleum; Registers; Testing;
Conference_Titel :
VLSI, 1999. Proceedings. Ninth Great Lakes Symposium on
Conference_Location :
Ypsilanti, MI
Print_ISBN :
0-7695-0104-4
DOI :
10.1109/GLSV.1999.757416
