8th International Conference on VLSI Design
Optimal algorithms for planar over-the-cell routing in the presence of obstacles
New Delhi, India
January 04-January 07
ISBN: 0-8186-6905-5
S.R. Danda, Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
S. Madhwapathy, Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
N.A. Sherwani, Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
In two layer standard cell design methodology, if both M1 and M2 layers are used for intra-cell routing, then the entire M2 layer will not be available for over-the-cell routing. In this case, the intra-cell routing segments in the M2 layer can be considered as obstacles, and the over-the-cell routing in the M2 layer has to be completed around these obstacles. In this paper, we present an optimal algorithm to solve the problem of planar over-the-cell routing in the presence of arbitrary shaped obstacles (PROBES), in O(Kn/sup 2/) time, where K is the number of tracks on the over-the-cell area of a cell-row, and n is the number of nets. Our algorithm can be further extended, to solve PROBES optimally, when at most d doglegs are allowed for routing, in O(K/sup d+1/n/sup d+2/) time, where d/spl ges/0 is a constant.
Index Terms:
network routing; integrated circuit layout; circuit layout CAD; VLSI; circuit optimisation; optimal algorithms; planar over-the-cell routing; arbitrary shaped obstacles; two layer standard cell design methodology; ALGO-PROBES algorithm
Citation:
S.R. Danda, S. Madhwapathy, N.A. Sherwani, "Optimal algorithms for planar over-the-cell routing in the presence of obstacles," vlsid, pp.3, 8th International Conference on VLSI Design, 1995
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb