A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points
檔案
本條目沒有附加檔案。
日期
2017-01-01
類型
系所
期刊名稱
PROCEEDINGS OF THE GREAT LAKES SYMPOSIUM ON VLSI 2017 (GLSVLSI' 17)
卷期與頁次
頁 399–402
ISBN
978-1-4503-4972-7
語言
英文
摘要
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 45x runtime speed-up averagely; moreover, our algorithm outperforms the state-of-the-art ML-OARST 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.
所屬典藏
會議論文引用此條目
Lin, K.-W., Lin, Y.-S., Li, Y.-L., & Lin, R.-B. (2017). A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points. PROCEEDINGS OF THE GREAT LAKES SYMPOSIUM ON VLSI 2017 (GLSVLSI' 17), 399–402. https://doi.org/10.1145/3060403.3060448
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/155529