A GENETIC ALGORITHM FOR HARD MODULE AND NON-SLICING VLSI FLOORPLANNING

摘要

Floorplanning is one of the most important problems in VLSI (Very Large Scale Integrated-circuits) physical design automation. Given a set of rectangular modules of arbitrary sizes, VLSI floorplanning is to place them on a plane within a minimum rectangular area such that no module overlaps. VLSI floorplan problems can be classified into soft module floorplan problems and hard module floorplan problems in terms of the flexibility of modules, and can also be classified into slicing floorplan problems and non-slicing floorplan problems in terms of representation. In order to find a global optimal solution, many genetic algorithms for VLSI floorplanning have been proposed. However, all the genetic algorithm are for slicing floorplan problems and no genetic algorithm for hard module and non-slicing floorplan problems has been published. This paper presents a genetic algorithm for hard module and non-slicing floorplan problems. This genetic algorithm has been implemented and tested using popular VLSI floor-plan benchmark problems. Experimental results show that this GA can find better solutions to the benchmarks problems than the best heuristic approach.