Abstract:

In this talk we study the global routing problem in VLSI (very large scale integration) design, where the channels on a chip form the edge set of a grid graph, and their crosses consist of the vertex set. A net is a subset of vertices to be connected by wires along the channels. Given a set of nets, the goal of the global routing problem is to find a routing strategy with respect to edge capacities and certain objective function is optimized. We consider three related models as follows: 1) to minimize the maximum edge congestion while all nets are routed; 2) to maximize the number of successfully routed nets without violating the capacity constraints; 3) to minimize the overall cost while routing all nets without exceeding the edge capacities. For all three models, we present approximation algorithms with improved performance ratios. Furthermore, we show implementation results for the third model, and address some heuristics to improve the computational performance of our approximation algorithm. These results can also been extended to some combinatorial optimization problems in communication networks.

This is joint work with Antoine Deza, Chris Dickson, Mohamed Saad, Tamas Terlaky and Anthony Vannelli.