A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
402 | en_US |
dc.citation.spage |
399 | en_US |
dc.citation.woscount |
2 | en_US |
dc.contributor.author |
Lin, Kuen-Wey | en_US |
dc.contributor.author |
Lin, Yeh-Sheng | en_US |
dc.contributor.author |
Li, Yih-Lang | en_US |
dc.contributor.author |
Lin, Rung-Bin | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2020-10-05T02:02:22Z | |
dc.date.available |
2020-10-05T02:02:22Z | |
dc.date.issued |
2017-01-01 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.doi |
10.1145/3060403.3060448 | en_US |
dc.identifier.isbn |
978-1-4503-4972-7 | en_US |
dc.identifier.journal |
PROCEEDINGS OF THE GREAT LAKES SYMPOSIUM ON VLSI 2017 (GLSVLSI' 17) | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1145/3060403.3060448 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/155529 | |
dc.identifier.wosnumber |
WOS:000568262800071 | en_US |
dc.language.iso |
en_US | en_US |
dc.subject |
Layout | en_US |
dc.subject |
Physical Design | en_US |
dc.subject |
Routing | en_US |
dc.subject |
Steiner Tree | en_US |
dc.title |
A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points | en_US |
dc.type |
Proceedings Paper | en_US |
檔案
本條目沒有附加檔案。
所屬典藏: 會議論文
引用此條目
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