A maze routing-based algorithm for ML-OARST with pre-selecting and re-building steiner points

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

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

6 Scopus citations


The benefits of applying maze routing algorithm over non-maze routing based methods include the feasibility of imposing various additional constraints on routing graphs. However, the much higher complexity of a multi-layer routing graph than that of a single-layer routing graph significantly increases the required runtime of conducting maze routing to solve the multi-layer obstacle-avoiding rectilinear Steiner tree (ML-OARST) problem, making applying maze routing to this problem infeasible. In this paper, we present a maze routing-based algorithm with the proposed Steiner point pre-selection to guide the construction of a ML-OARST. This can achieve a favorable balance between quality and runtime. The quality of routing is determined by total cost, that is, the summation of wire-length and via cost. To improve the flexibility of routing tree generation, we also propose a rip-up and re-building strategy for altering Steiner points and tree topology. Compared with a multi-layer multi-terminal maze routing algorithm, our algorithm can reduce the total cost by 4.8% on average and achieve 45× runtime speed-up averagely; moreover, our algorithm outperforms the state-of-the-art MLOARST method using computational geometry techniques in terms of wire-length. With additional costs on routing graph, the proposed maze routing-based method can be further enhanced to solve VLSI routing constraints, such as layer-specific costs, scenic control, and layer directive.

Original languageEnglish
Title of host publicationGLSVLSI 2017 - Proceedings of the Great Lakes Symposium on VLSI 2017
PublisherAssociation for Computing Machinery
Number of pages4
ISBN (Electronic)9781450349727
StatePublished - 10 May 2017
Event27th Great Lakes Symposium on VLSI, GLSVLSI 2017 - Banff, Canada
Duration: 10 May 201712 May 2017

Publication series

NameProceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI
VolumePart F127756


Conference27th Great Lakes Symposium on VLSI, GLSVLSI 2017


  • Layout
  • Physical design
  • Routing
  • Steiner Tree


Dive into the research topics of 'A maze routing-based algorithm for ML-OARST with pre-selecting and re-building steiner points'. Together they form a unique fingerprint.

Cite this