Efficient multi-layer obstacle-avoiding region-to-region rectilinear steiner tree construction
| Autor: | Chia-Cheng Pai, James Cm Li, Run-Yi Wang, Hsiang-Ting Wen, Yu-Cheng Pai, Jie-Hong R. Jiang, Yao-Wen Chang, Jun-Jie Wang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
010302 applied physics
Mathematical optimization Computer science Rectilinear Steiner tree 02 engineering and technology 01 natural sciences Steiner tree problem Graph 020202 computer hardware & architecture symbols.namesake 0103 physical sciences Path (graph theory) Hardware_INTEGRATEDCIRCUITS 0202 electrical engineering electronic engineering information engineering symbols Graph (abstract data type) Routing (electronic design automation) Time complexity |
| Zdroj: | DAC |
| Popis: | As Engineering Change Order (ECO) has attracted substantial attention in modern VLSI design, the open net problem, which aims at constructing a shortest obstacle-avoiding path to reconnect the net shapes in an open net, becomes more critical in the ECO stage. This paper addresses a multi-layer obstacle-avoiding region-to-region Steiner minimal tree (SMT) construction problem that connects all net shapes by edges on a layer or vias between layers, and avoids running through any obstacle with a minimal total cost. Existing multi-layer obstacle-avoiding SMT algorithms consider pin-to-pin connections instead of region-to-region ones, which would limit the solution quality due to its lacking region information. In this paper, we present an efficient algorithm based on our new multi-layer obstacle-avoiding region-to-region spanning graph to solve the addressed problem, which guarantees to find an optimal solution for a net connecting two regions on a single layer. Experimental results show that our algorithm outperforms all the participating routers of the 2017 CAD Contest at ICCAD in both solution quality and runtime. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|