A WEIGHTED STEINER TREE-BASED GLOBAL ROUTER WITH SIMULTANEOUS LENGTH AND DENSITY MINIMIZATION

We consider the problem of global routing, aiming to simultaneously mi nimize wire length and density through the regions. Previous global ro uters have attempted to achieve this goal; however, they minimized one of the two parameters as the main objective and proposed heuristics f or minimizing the other parameter. We accomplish this task by introduc ing 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 ''com plexity.'' Weights of the regions are dynamically changing. Experiment al results on master slice chips and on benchmark examples from the Ph ysical Design Workshop are included, and they verify the effectiveness of the proposed global router and its superiority over related global routers.