Simultaneous antenna avoidance and via optimization in layer assignment of multi-layer global routing

Antenna effect is an important issue that needs to be considered in the routing stage for modern design. In this paper, we study a layer assignment problem that arises during multi-layer global routing and takes antenna avoidance into account. The problem asks to transform a given 2-dimensional global routing result into a 3-dimensional one (i.e., a multi-layer one) and to minimize the amount of antenna violations and the via count subject to given wire congestion constraints. We present an algorithm that tackles the addressed layer assignment problem in a net-by-net manner. An existing dynamic-programming-based single-net layer assignment method that can only consider the via count is judiciously modified and adopted by our algorithm to handle both antenna avoidance and via count minimization for each net. To further reduce the via count but without increasing the amount of antenna violations, a refinement procedure based on min-cost max-flow is developed and added to our algorithm. The experiment results show that when compared with the layer assignment approach adopted by a state-of-the-art academic global router, our algorithm not only can improve the via count slightly but also can significantly reduce the amount of antenna violations.