next up previous
Next: Contact address Up: Design of VLSI-Layouts Previous: Genetic Algorithms

Combined floorplanning and routing

The main problem in the development of a genetic algorithm is to find good encodings for the individuals (genotypes) and the genetic operators. Here each individual describes a correct layout for the circuit of the VLSI chip. This layout is encoded by a binary tree (cf. Fig. 1). The leaves of this tree represent the building blocks of the layout and the inner nodes of the tree describe meta-blocks (partial layouts), which have the same representation like the basic blocks. When building such a meta-block out of two blocks or meta-blocks, the total (detailed) routing inside this block can be done.

Building the tree in a bottom-up fashion, the root of this tree represents the layout for the complete chip. The mutation and crossover operators operate on the tree by exchanging leaves or changing the wiring-routes inside a meta-block (mutation) and combining subtrees of two individuals to a new solution (crossover). The convergence-ratio of the fitness (layout-area) is increased by using shape-functions also for the meta-blocks, so that every inner node of the tree -- including the root -- describes more than one layout alternative, provided that the blocks have different aspect ratios.

For real-world VLSI chips there are 10 to 50 building blocks and up to 500 nets (full custom design). The actual implementation includes a visualization of the layout by showing the blocks and the routing space. Future versions will include a visualization of the detailed routing, too, and an efficient parallelization of the genetic algorithm.

This project is part of the BMBF-project `HYBRID--Applications of Parallel Genetic Algorithms in Combinatorial Optimization'. It has started in April 1994 and will end in December 1996.

Fri May 12 15:23:19 MET DST 1995