Computing area and wire length efficient routes for channels

	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/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by R.K. Pal Articles by S.P. Pal Articles by M.M. Das Articles by A. Pal

8th International Conference on VLSI Design

New Delhi, India

January 04-January 07

ISBN: 0-8186-6905-5

	ASCII Text	x
	R.K. Pal, S.P. Pal, M.M. Das, A. Pal, "Computing area and wire length efficient routes for channels," VLSI Design, International Conference on, pp. 196, 8th International Conference on VLSI Design, 1995.

	BibTex	x
	@article{ 10.1109/ICVD.1995.512108, author = {R.K. Pal and S.P. Pal and M.M. Das and A. Pal}, title = {Computing area and wire length efficient routes for channels}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {1995}, isbn = {0-8186-6905-5}, pages = {196}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512108}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Computing area and wire length efficient routes for channels SN - 0-8186-6905-5 SP EP A1 - R.K. Pal, A1 - S.P. Pal, A1 - M.M. Das, A1 - A. Pal, PY - 1995 KW - network routing; VLSI; integrated circuit layout; computational complexity; minimisation; circuit layout CAD; area efficient routes; wire length efficient routes; channel routing; total wire length reduction; polynomial time algorithms; multilayer routing solutions; NP-hard; VLSI layout VL - 0 JA - VLSI Design, International Conference on ER -

R.K. Pal, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India

S.P. Pal, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India

M.M. Das, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India

A. Pal, Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Kharagpur, India

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

The first stage in channel routing is that of computing a routing solution S, for a given channel with as few tracks as possible. We consider a second stage in which it is desirable to reduce the total wire length without increasing area of routing. In this paper we propose efficient polynomial time algorithms for appreciably reducing the total wire length in two-, three- and multi-layer routing solutions by permuting tracks in the solution S obtained in the first stage. This results in a routing solution that is economical in terms of area as well as total wire length. Our algorithms are particularly important in practical terms since the problem of minimizing the total wire length in a routing solution is NP-hard.

Index Terms:

network routing; VLSI; integrated circuit layout; computational complexity; minimisation; circuit layout CAD; area efficient routes; wire length efficient routes; channel routing; total wire length reduction; polynomial time algorithms; multilayer routing solutions; NP-hard; VLSI layout

Citation:

R.K. Pal, S.P. Pal, M.M. Das, A. Pal, "Computing area and wire length efficient routes for channels," vlsid, pp.196, 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.