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.

原文English
主出版物標題GLSVLSI 2017 - Proceedings of the Great Lakes Symposium on VLSI 2017
發行者Association for Computing Machinery
頁面399-402
頁數4
ISBN(電子)9781450349727
DOIs
出版狀態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

Conference

Conference27th Great Lakes Symposium on VLSI, GLSVLSI 2017
國家/地區Canada
城市Banff
期間10/05/1712/05/17

指紋

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

引用此