A new multilevel framework for large-scale interconnect-driven floorplanning

We present in this paper a new interconnect-driven multilevel floorplanner, called interconnect-driven multilevel-floorplanning framework (IMF), to handle large-scale building-module designs. Unlike the traditional multilevel framework that adopts the "Lambda-shaped" framework (inaccurately called the "V-cycle" framework in the literature): bottom-up coarsening followed by top-down uncoarsening, the IMF, in contrast, works in the "V-shaped" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). The top-down partitioning stage iteratively partitions the floorplan region based on min-cut bipartitioning with exact net-weight modeling to reduce the number, of global interconnections and, thus, the total wirelength. Then, the bottom-up merging stage iteratively applies fixed-outline floorplanning using simulated annealing for all regions and merges two. neighboring regions recursively. Experimental results show that the IMF obtains the best published fixed-outline floorplarining results with the smallest average wirelength for the Microelectronics Center of North Carolina/Gigascale Systems Research Center benchmarks. In particular, IMF scales very well as the circuit size increases. The V-shaped multilevel framework outperforms the Lambda-shaped one in the optimization of global circuit effects, such as interconnection and crosstalk optimization, since the V-shaped framework considers the global configuration first and then processes down to local ones level by level, and thus, the global effects can be handled at earlier stages. The V-shaped multilevel framework is general and, thus, can be readily applied to other problems.