Non-slicing floorplanning-based crosstalk reduction on gridless track assignment for a gridless routing system with fast pseudo-tile extraction

Yu Ning Chang*, Yih-Lang Li, Wei Tin Lin, Wen Nai Cheng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

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, crosstalkdriven 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 subpanels, 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.

Original languageEnglish
Title of host publicationISPD'08 - Proceedings of the 2008 ACM International Symposium on Physical Design
Pages134-141
Number of pages8
DOIs
StatePublished - 2008
Event2008 ACM International Symposium on Physical Design, ISPD 2008 - Portland, OR, United States
Duration: 13 Apr 200816 Apr 2008

Publication series

NameProceedings of the International Symposium on Physical Design

Conference

Conference2008 ACM International Symposium on Physical Design, ISPD 2008
Country/TerritoryUnited States
CityPortland, OR
Period13/04/0816/04/08

Keywords

  • Crosstalk reduction
  • Detailed routing
  • Full-chip routing
  • Gridless routing
  • Implicit connection graph-based router
  • Non-slicing floorplanning

Fingerprint

Dive into the research topics of 'Non-slicing floorplanning-based crosstalk reduction on gridless track assignment for a gridless routing system with fast pseudo-tile extraction'. Together they form a unique fingerprint.

Cite this