標題: Corner-Stitching-Based Multilayer Obstacle-Avoiding Component-to-Component Rectilinear Minimum Spanning Tree Construction
作者: Su, Yen-Yu
Wang, Shuo-Hui
Wu, Wei-Liang
Lin, Mark Po-Hung
電子工程學系及電子研究所
智慧科學暨綠能學院
Department of Electronics Engineering and Institute of Electronics
College of Artificial Intelligence
關鍵字: Routing;Shape;Data structures;Nonhomogeneous media;Connectors;Integrated circuits;Runtime;Corner stitching;engineering change order (ECO);minimal spanning tree;minimum spanning tree (MST);multilayer;obstacle;physical design;rectilinear;routing
公開日期: 1-Mar-2020
摘要: Engineering change orders (ECOs) are pervasively applied to modern physical design of nanometer integrated circuits for cost-effective design changes. After applying ECO, a net may become open, which results in a large number of disconnected net components. Each net component further consists of a set of connected net shapes and vias on different layers. It is very challenging to efficiently and effectively identify all disconnected net components and find an obstacle-avoiding minimal-cost routing path among those net components. This paper introduces an open-net finder and an open-net connector based on the corner-stitching data structure for open-net routing, and proposes a new method of constructing a multilayer obstacle-avoiding component-to-component rectilinear minimum spanning tree. The preliminary idea and implementation of the proposed method had received the first place award in ICCAD-2017 CAD contest. This paper further details the complete idea of the proposed method. Experimental results show that the proposed open-net finder and connector outperform the top three open-net routers in the ICCAD-2017 CAD contest and two latest published works, with better routing costs and much shorter runtime.
URI: http://dx.doi.org/10.1109/TCAD.2018.2890531
http://hdl.handle.net/11536/154197
ISSN: 0278-0070
DOI: 10.1109/TCAD.2018.2890531
期刊: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Volume: 39
Issue: 3
起始頁: 675
結束頁: 685
Appears in Collections:Articles