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

研究成果: Conference contribution同行評審

6 引文 斯高帕斯(Scopus)


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.

主出版物標題GLSVLSI 2017 - Proceedings of the Great Lakes Symposium on VLSI 2017
發行者Association for Computing Machinery
出版狀態Published - 10 5月 2017
事件27th Great Lakes Symposium on VLSI, GLSVLSI 2017 - Banff, Canada
持續時間: 10 5月 201712 5月 2017


名字Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI
Part F127756


Conference27th Great Lakes Symposium on VLSI, GLSVLSI 2017


深入研究「A maze routing-based algorithm for ML-OARST with pre-selecting and re-building steiner points」主題。共同形成了獨特的指紋。