A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/155529