NEMO: A new implicit connection graph-based gridless router with multi-layer planes and pseudo-tile propagation

Hsin Yu Chen*, Yih-Lang Li, Zhi Da Lin

*Corresponding author for this work

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

1 Scopus citations

Abstract

This study presents a new multilayer implicit connection graph-based gridless router called NEMO. Unlike the first implicit connection graph-based router that embeds all routing layers onto a routing plane, NEMO constructs a routing plane for each routing layer. Furthermore, each routing plane is composed of tiles, not an array of grid points as well as their connecting edges, and, consequently, the complexity of routing problem decreases. Each grid then exactly represents one tile (its left bottom corner), and grid maze becomes tile propagation; moreover, to further speedup in path searching, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile. Experimental results indicate that NEMO conducts point-to-point path searching on about 10 times faster than the implicit connection graph-based router. Full-chip routing by NEMO also outperforms all multi-level gridless routers with about 1.45X to 2.42X runtime speedups.

Original languageEnglish
Title of host publicationProceedings of ISPD'06 - 2006 International Symposium on Physical Design
Pages64-71
Number of pages8
DOIs
StatePublished - 20 Jul 2006
EventISPD'06 - 2006 International Symposium on Physical Design - San Jose, CA, United States
Duration: 9 Apr 200612 Apr 2006

Publication series

NameProceedings of the International Symposium on Physical Design
Volume2006

Conference

ConferenceISPD'06 - 2006 International Symposium on Physical Design
CountryUnited States
CitySan Jose, CA
Period9/04/0612/04/06

Keywords

  • Detailed routing
  • Full-chip routing
  • Gridless router
  • Implicit connection graph-based router
  • Point-to-point routing
  • Tile-based router

Fingerprint Dive into the research topics of 'NEMO: A new implicit connection graph-based gridless router with multi-layer planes and pseudo-tile propagation'. Together they form a unique fingerprint.

Cite this