A maze routing-based methodology with bounded exploration and path-assessed retracing for constrained multilayer obstacle-avoiding rectilinear steiner tree construction

Kuen Wey Lin*, Yeh Sheng Lin, Yih-Lang Li, Rung Bin Lin

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Owing to existing intellectual properties, prerouted nets, and power/ground wires, the routing of a system on chip design demands to detour around multilayer obstacles. Traditional approaches for the multilayer obstacle-avoiding rectilinear Steiner tree (ML-OARST) problem are thus nonmaze routing-based approaches for runtime issues, yet they cannot be directly applied to deal with additional constraints such as variant edge weights on a routing layer. In this article, we propose the maze routing-based methodology with bounded exploration and path-assessed retracing to reduce runtime and routing cost for the constrained ML-OARST construction problem. The exploration of maze routing is bounded to reduce the runtime; the costs of connecting pins are computed to select Steiner points in the retracing phase. To further reduce the routing cost, we develop a Steiner point-based ripping-up and rebuilding scheme for altering tree topology. Experimental results on industrial and randomly generated benchmarks demonstrate that the proposed methodology can provide a solution with good quality in terms of routing cost and has a significant speedup compared to traditional maze routing. A commercial tool is also used to show the effectiveness of the proposed methodology.

Original languageEnglish
Article numberA45
JournalACM Transactions on Design Automation of Electronic Systems
Volume23
Issue number4
DOIs
StatePublished - 1 Jul 2018

Keywords

  • Layout
  • Physical design
  • Routing
  • Steiner tree

Fingerprint Dive into the research topics of 'A maze routing-based methodology with bounded exploration and path-assessed retracing for constrained multilayer obstacle-avoiding rectilinear steiner tree construction'. Together they form a unique fingerprint.

  • Cite this