GENETIC BEAM SEARCH FOR GATE MATRIX LAYOUT

The paper presents a novel implementation of the genetic algorithm in combination with beam search for gate matrix layout. This is a permuta tion problem, for which the traditional genetic crossover operator res ults in repetition of gates, and therefore the GA is not applicable wi thout modification. However, the GA is a very efficient stochastic opt imisation technique, and is easily parallelisable. To adapt it to the gate matrix layout problem, the principles of beam search have been us ed. The gates are ranked according to their connectivity with each oth er, and the ranks of the gates to be placed next to each other are pic ked by the GA. A beam value is used to restrict the ranks of the gates placed next to each other to a low value. This reduces the search spa ce to be explored, and thus results in a more efficient search. The al gorithm produces better results compared to a graph-theoretic approach on published netlists.