Optimal algorithms for planar over-the-cell routing in the presence of obstacles

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by S.R. Danda Articles by S. Madhwapathy Articles by N.A. Sherwani

8th International Conference on VLSI Design

New Delhi, India

January 04-January 07

ISBN: 0-8186-6905-5

	ASCII Text	x
	S.R. Danda, S. Madhwapathy, N.A. Sherwani, "Optimal algorithms for planar over-the-cell routing in the presence of obstacles," VLSI Design, International Conference on, pp. 3, 8th International Conference on VLSI Design, 1995.

	BibTex	x
	@article{ 10.1109/ICVD.1995.512068, author = {S.R. Danda and S. Madhwapathy and N.A. Sherwani}, title = {Optimal algorithms for planar over-the-cell routing in the presence of obstacles}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {1995}, isbn = {0-8186-6905-5}, pages = {3}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512068}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Optimal algorithms for planar over-the-cell routing in the presence of obstacles SN - 0-8186-6905-5 SP EP A1 - S.R. Danda, A1 - S. Madhwapathy, A1 - N.A. Sherwani, PY - 1995 KW - 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 VL - 0 JA - VLSI Design, International Conference on ER -

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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512068

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.