Performance Optimized Floor Planning by Graph Planarization

A new procedure for VLSI floor planning that minimizes routing parasitics is presented. The procedure, based on rectangular dualization, maximizes adjacency of modules that are heavily connected or connected by critical nets. Wiring macros are introduced to provide routing area for those modules that cannot be located adjacent to one another; these macros are located by planarizing the system interconnectivity graph using an edge crossing strategy that minimizes the cost of intersection. The rectangular dual is compacted using heuristics to approximate a quadratic area constraint by one or more linear constraints, thereby reducing the complexity of compaction from that of quadratic programming to linear programming.