Net-based force-directed macrocell placement for wirelength optimization

摘要

We propose a net-based hierarchical macrocell placement such that "net placement" dictates the cell placement. The proposed approach has four phases. 1) Net clustering and net-level floorplanning phase: a weighted net dependency graph is built from the input register-transfer-level netlist. Clusters of nets are then formed by clique partitioning and a net-cluster level floorplan is obtained by simulated annealing. The floorplan defines the regions where the nets in each cluster must be routed. 2) Force-directed net placement phase: a force-directed net placement is performed which yields a coarse net-level placement without consideration for the cell placement. 3) Iterative net terminal and cell placement phase: a force-directed net and cell placement is performed iteratively. The terminals of a net are free to move under the influence of forces in the quest for optimal wire length. The cells with high net length cost may "jump" out of local minima by ignoring the rejection forces. The overlaps are reduced by employing electrostatic rejection forces. 4) Overlap removal and input/output (I/O) pin assignment phase: Overlap removal is performed by a grid-based heuristic. I/O pin assignment is performed by minimum-weight bipartite matching. Placements generated by the proposed approach are compared with those generated by Cadence Silicon Ensemble and the O-tree floorplanning algorithm. On average, the proposed approach improves both the total wire length and longest wire length by 18.9% and 28.3%, respectively, with an average penalty of 5.6% area overhead.