next up previous
Next: Genotype Representation Up: An Adaptive Parallel Genetic Previous: The Design of

Genetic Layout Optimization

The classical work on layout generation with GAs is done by Cohoon et al.[3,4]. They encode a placement by a polish notation of a binary slicing tree, thus having a chromosome represented by a string. They use different recombination operators, which work either directly on this string, or take the tree structure into consideration by decoding the chromosome. Chan et al. [2] represent a placement in a bit-matrix. The layout area is divided into discrete regions and each row in the matrix describes the orientation and the position for a single cell. Recombination is done by mixing two matrices. During the optimization incorrect placements with overlapping cells are allowed and are handled by adding a penalty term when computing the fitness. Esbensen [6] describes a GA for macro cell placement where the genotype representation is a binary tree. In contrast to the approach of Cohoon et al., this tree does not directly characterize a placement, but it can be generated by decoding the tree in a traversal due to a given order. His operators directly work on the tree structure.

The major drawback of the previously mentioned approaches is the fact, that they only optimize the placement without considering the routes to be chosen for the interconnection wirings. The approach described in this paper also uses a genotype representation as a binary tree and non-standard genetic operators, but here the global routes for the signal nets are computed before fixing the positions of the cells. Due to this, routing is not restricted by any limited capacities arising from wrong estimates for the need of routing space.

Mon Jun 10 11:25:16 MET DST 1996