A Maze Routing-Based Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction
Simple item page Statistics| Field | Value | Language |
|---|---|---|
dc.citation.volume |
23 | en_US |
dc.citation.woscount |
0 | 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 |
2019-04-02T06:00:44Z | |
dc.date.available |
2019-04-02T06:00:44Z | |
dc.date.issued |
2018-07-01 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.doi |
10.1145/3177878 | en_US |
dc.identifier.issn |
1084-4309 | en_US |
dc.identifier.journal |
ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1145/3177878 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/148726 | |
dc.identifier.wosnumber |
WOS:000455950300005 | 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 Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction | en_US |
dc.type |
Article | en_US |
Files
No files are attached to this item.
Collections: Articles
Cite this item
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
Citation generated in APA 7th edition style; please check it before use.
Share
Permanent link: https://ir.lib.nycu.edu.tw/handle/11536/148726