Non-Slicing Floorplanning-Based Crosstalk Reduction on Gridless Track Assignment for a Gridless Routing System with Fast Pseudo-Tile Extraction

Abstract

Track assignment, which is an intermediate stage between global routing and detailed routing, provides a good platform for promoting performance, and for imposing additional constraints during routing, such as crosstalk. Gridless track assignment (GTA) has not been addressed in public literature. This work develops a gridless routing system integrating a congestion-driven global router, crosstalk-driven GTA and an enhanced implicit connection-graph-based router. Initial assignment is produced rapidly with a left-edge like algorithm. Crosstalk reduction on the assignment is then transformed to a restricted non-slicing floorplanning problem, and a deterministic O-tree based algorithm is employed to re-assign each net segment. Finally, each panel is partitioned into several sub-panels, and the sub-panels are re-ordered using branch and bound algorithm to decrease the crosstalk further. Before detailed routing, routing tree construction is undertook for placed IRoutes and other pins; many original point-to-point routings are set to connect to IRoutes, and can be accomplished simply with pattern routing. For detailed routing, this work proposes a rapid extraction method for pseudo-maximum stripped tiles to boost path propagation. Experimental results demonstrate that the proposed gridless routing system has over 2.66 times the runtime speedup for fixed- and variable-rule routings of an implicit connection-graph-based router, NEMO. As compared with a commercial routing tool, this work yields an average reduction rate of 15% in coupling capacitance calculated using its built-in coupling capacitance estimator.