A genetic approach to standard cell placement using meta-genetic parameter optimization

The genetic algorithm applies transformations on the chromosonal representation of the physical layout. The algorithm works on a set of configurations constituting a constant-size population. The transformations are performed through crossover operators that generate a new configuration assimilating the characteristics of a pair of configurations existing in the current population. Mutation and inversion operators are also used to increase the diversity of the population, and to avoid premature convergence at local optima. Due to the simultaneous optimization of a large population of configurations, there is a logical concurrency in the search of the solution space which makes the genetic algorithm an extremely efficient optimizer. Three efficient crossover techniques are compared, and the algorithm parameters are optimized for the cell-placement problem by using a meta-genetic process. The resulting algorithm was tested against TimberWolf 3.3 on five industrial circuits consisting of 100-800 cells. The results indicate that a placement comparable in quality can be obtained in about the same execution time as TimberWolf, but the genetic algorithm needs to explore 20-50 times fewer configurations than does TimberWolf