Title :
A provably good multilayer topological planar routing algorithm in IC layout designs
Author :
Cong, Jingsheng ; Hossain, Moazzem ; Sherwani, Naveed A.
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
1/1/1993 12:00:00 AM
Abstract :
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)≈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
Keywords :
approximation theory; circuit layout CAD; integrated circuit technology; iterative methods; multiterminal networks; IC layout designs; approximation algorithm; iterative-peeling algorithm; multiterminal nets; topological planar routing algorithm; Algorithm design and analysis; Application specific integrated circuits; Approximation algorithms; Fabrication; Integrated circuit interconnections; Integrated circuit layout; Macrocell networks; Nonhomogeneous media; Routing; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
