A Weighted Steiner Tree-Based Global Router with Simultaneous Length and Density Minimization

Abstract

We consider the problem of global routing, aiming to simultaneously minimize wire length and density through the regions. Previous global routers have attempted to achieve this goal; however, they minimized one of the two parameters as the main objective and proposed heuristics for minimizing the other parameter. We accomplish this task by introducing the concept of weighted Steiner trees. We propose an efficient and simple algorithm for obtaining a weighted (rectilinear) Steiner tree in the plane. The proposed global router at each step finds a weighted Steiner tree for a net, where weight of a region represents its “complexity.” Weights of the regions are dynamically changing. Experimental results on master slice chips and on benchmark examples from the Physical Design Workshop are included, and they verify the effectiveness of the proposed global router and its superiority over related global routers. © 1994 IEEE.