A new and efficient congestion evaluation model in floorplanning: wire density control with twin binary trees

As technology moves into the deep-submicron era, the complexity of VLSI circuit design grows rapidly, especially in the interconnections between modules. Therefore, interconnect optimization has become an important concern in floorplanning today. Most routability-driven floorplanners use a grid-based approach that divides a floorplan into grids as in global routing. Congestion is estimated as the expected number of nets passing through each grid. Although this approach is direct and accurate, it is not efficient when dealing with complex circuits containing thousands of nets. In this paper, an efficient and innovative routability-driven floorplanner, using a twin binary trees (TBT) representation is proposed. The congestion model we used is the wire density on the half-perimeter boundary of different regions in a floorplan. These regions are defined naturally by the TBT representation. In order to increase the efficiency of our floorplanner, a fast algorithm for the least common ancestor (LCA) problem is used to compute the wire density. From the experimental results, the number of unroutable wires can be reduced in a short time.