Provably good global routing of integrated circuits

This paper investigates the global routing problem for integrated circuits. We introduce a formulation on the basis of integer programming which minim izes the routing area among a limited set of Steiner trees for each net. In deed, the involved cost function depends on the channel density of the rout ing which has a direct influence on the routing area. Our methods for solving the global routing problem employ local search heur istics, sequential routing, genetic routing, and randomized procedures. Our methods for computing lower bounds are based on linear and Lagrange relaxa tion. An analysis on the tightness of the bounds indicates that the differe nce between the cost of the optimal integer solutions and the cost of the o ptimal fractional solutions is only a small number of tracks in practice. M oreover, the analysis leads to the concept of linear preprocessing by which we exclude a large number of high-cost solutions. We introduce several versions of preprocessing, one of which preserves the opportunity of obtaining a globally optimal solution in general; all of the m do so in practice. Linear preprocessing enables us to solve problem insta nces with several thousand nets provably optimal or at least provably close to optimal. All methods have been implemented in the software package ERIDANUS. We pres ent computational results. The global routing problem assumes the placement of the chip components to be fixed. An extension of the problem, which we call global layout of integ rated circuits, allows the placement to be variable and searches for a plac ement that minimizes the routing area among a limited set of alternatives. We show that the results concerning the global routing problem can be easil y extended to global layout.