A Maze Routing-Based Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction

檔案

本條目沒有附加檔案。

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

日期

2018-07-01

類型

期刊名稱

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS

卷期與頁次

第 23 卷

ISSN

1084-4309

語言

英文

摘要

Owing to existing intellectual properties, prerouted nets, and power/ground wires, the routing of a system on chip design demands to detour around multilayer obstacles. Traditional approaches for the multilayer obstacle-avoiding rectilinear Steiner tree (ML-OARST) problem are thus nonmaze routing-based approaches for runtime issues, yet they cannot be directly applied to deal with additional constraints such as variant edge weights on a routing layer. In this article, we propose the maze routing-based methodology with bounded exploration and path-assessed retracing to reduce runtime and routing cost for the constrained ML-OARST construction problem. The exploration of maze routing is bounded to reduce the runtime; the costs of connecting pins are computed to select Steiner points in the retracing phase. To further reduce the routing cost, we develop a Steiner point-based ripping-up and rebuilding scheme for altering tree topology. Experimental results on industrial and randomly generated benchmarks demonstrate that the proposed methodology can provide a solution with good quality in terms of routing cost and has a significant speedup compared to traditional maze routing. A commercial tool is also used to show the effectiveness of the proposed methodology.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Lin, K.-W., Lin, Y.-S., Li, Y.-L., & Lin, R.-B. (2018). A Maze Routing-Based Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction. ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 23. https://doi.org/10.1145/3177878

BibTeX RIS

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

分享

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