Due to its complexity, the physical design is normally divided into various sub-steps: The circuit has to be partitioned to get some (up to 50) macro cells which have to be placed on the chip (floorplanning). In the routing phase pins on the walls of these modules have to be connected. This is usually done in two steps: In the global routing the `loose' routes are determined, while in the detailed routing the exact routes for the wires in each channel between two modules are computed. The last step in the physical design is the compaction of the layout, where it is compressed in all dimensions so that the total area is reduced.
In this project the floorplanning and the routing is done in one step using a genetic algorithm. The input to the floorplanning process are the rectangular building blocks (macro cells) and a number of interconnections between these blocks, described by a netlist. Most nets are two-terminal nets, i.e. they only connect two modules on the chip, but there are also some nets (e.g. power or ground), which connect all blocks. At this stage (after the partitioning of the circuit) there are good estimates for the area of the macro cells, but their exact dimensions can still be varied over a wide range. The different aspect-ratios of these flexible cells are described by shape-functions (lists of feasible width/height-combinations).
Like in nature there is a mutation operator, which randomly changes an individual and so prevents the algorithm from sticking to a local optimum. The crossover operator creates an offspring out of two `parent'-individuals and thereby hereditaring their good qualities to the new individual. At the end of every generation a fixed number of individuals is selected from the grown population due to their fitness to survive to the following generation. This is done by the selection operator which together with mutation and crossover simulates Darwin's `survival of the fittest' and yields a (nearly) optimal solution even in very complex solution spaces.
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. 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.
Further information in postscript (40 kB) and publications about this project....
Back to the homepage of the research group, the homepage of the Institute of Computer Science, and to the homepage of the University.