Browsing by Author "Chang, Yu-Ning"

Now showing 1 - 2 of 2

A Gridless Routing System with Nonslicing Floorplanning-Based Crosstalk Reduction on Gridless Track Assignment
(2011-03-01)
Li, Yih-Lang
;
Chang, Yu-Ning
;
Cheng, Wen-Nai
;
資訊工程學系
;
Department of Computer Science
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 nonslicing floorplanning problem, and a deterministic O-Tree based algorithm is employed to reassign each net segment. Finally, each panel is partitioned into several subpanels, and the subpanels are reordered using branch and bound algorithm to decrease the crosstalk further. Before detailed routing, routing tree construction is undertaken 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 pseudomaximum stripped tiles to boost path propagation. Experimental results demonstrate that the proposed gridless routing system has over 2.02 times the runtime speedup in average 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 13.8% in coupling capacitance calculated using its built-in coupling capacitance estimator.
Non-Slicing Floorplanning-Based Crosstalk Reduction on Gridless Track Assignment for a Gridless Routing System with Fast Pseudo-Tile Extraction
(2008)
Chang, Yu-Ning
;
Li, Yih-Lang
;
Lin, Wei-Tin
;
Cheng, Wen-Nai
;
資訊工程學系
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.