Efficient multi-layer obstacle-avoiding region-to-region rectilinear steiner tree construction
Journal
Design Automation Conference
Journal Volume
Part F137710
Date Issued
2018
Author(s)
Wang, R.-Y.
Pai, C.-C.
Wang, J.-J.
Wen, H.-T.
Pai, Y.-C.
Li, J.C.M.
Jiang, J.-H.R.
Abstract
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.
Type
conference paper