| Floorplanning is a crucial phase in VLSI Physical
Design, as subsequent placement and routing of the
modules are coupled very closely with the quality of the
floorplan. A widely used technique for floorplanning is
Simulated Annealing, which generates very good results
but has major limitations in terms of running time. For
more than tens of modules, Simulated Annealing is not
practical. Top-down partitioning-based floorplanning is an alternative to Simulated Annealing. This method is much faster, but generates inferior solutions to Simulated Annealing. The main weakness of partitioning-based methods is that, they do not try to match the shape of the modules when grouping the modules into partitions: only cut cost is considered. This is in contrast to Simulated Annealing which performs sizing and wire-length minimization simultaneously. The figure below shows a partitioning which does not consider the shape of the modules. The green and the blue modules are flexible, i.e., have more than one shape in the library of modules. As you can see, a lot of space is wasted in the resulting floorplan, because all the rigid modules (the yellow, red and pink) are grouped together. Their shapes cannot be matched nicely.
We propose a top-down partitioning-based floorplanning that tries to balance flexibility of the modules, as well as area, across partitions, while minimizing the cut cost. A flexible module is one that can take many shapes. We define some heuristic functions to quantify the flexibility of the modules. Distributing flexibility across partitions makes the sizing problem almost trivial. The figure below shows an example of partitioning while balancing the flexibility on both sides. The resulting floorplan is more compact compared to the previous figure.
The quality of our method is comparable to the annealing method (5% worse on the average), but about 1000 times faster.
Related Published Papers
Back to Research
Page. |
