A provably good multilayer topological planar routing algorithm in IC layout designs

摘要

A provably good approximation algorithm for the multilayer topological planar routing problem is presented. The algorithm, called the iterative-peeling algorithm, finds a solution whose weight is guaranteed to be at least 1-(1/e) approximately=63.2% of the weight of an optimal solution. The algorithm works for multiterminal nets and arbitrary number of routing layers. For a fixed number of routing layers, even tighter performance bounds are used. In particular, the performance ratio of the iterative-peeling algorithm is at least 75% for two-layer routing and is at least 70.4% for three-layer routing. Experimental results confirm that the algorithm can always route a majority of the nets without using vias, even when the number of routing layers is fairly small.