Fast algorithm for performance-oriented Steiner routing

	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 M. Borah Articles by R.M. Owens Articles by M.J. Irwin

Fifth Great Lakes Symposium on VLSI (GLSVLSI'95)

The State University of New York at Buffalo

March 16-March 18

ISBN: 0-8186-7035-5

	ASCII Text	x
	M. Borah, R.M. Owens, M.J. Irwin, "Fast algorithm for performance-oriented Steiner routing," Great Lakes Symposium on VLSI, pp. 198, Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), 1995.

	BibTex	x
	@article{ 10.1109/GLSV.1995.516052, author = {M. Borah and R.M. Owens and M.J. Irwin}, title = {Fast algorithm for performance-oriented Steiner routing}, journal ={Great Lakes Symposium on VLSI}, volume = {0}, year = {1995}, issn = {1066-1395}, pages = {198}, doi = {http://doi.ieeecomputersociety.org/10.1109/GLSV.1995.516052}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Great Lakes Symposium on VLSI TI - Fast algorithm for performance-oriented Steiner routing SN - 1066-1395 SP EP A1 - M. Borah, A1 - R.M. Owens, A1 - M.J. Irwin, PY - 1995 KW - network routing; integrated circuit layout; VLSI; circuit layout CAD; iterative methods; data structures; computational complexity; delays; performance-oriented Steiner routing; fast routing algorithm; Elmore delay minimisation; layout generators; iterative techniques; data structures VL - 0 JA - Great Lakes Symposium on VLSI ER -

M. Borah, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA

R.M. Owens, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA

M.J. Irwin, Dept. of Comput. Sci. & Eng., Pennsylvania State Univ., University Park, PA, USA

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/GLSV.1995.516052

We present a routing algorithm which minimizes the Elmore delay to the identified critical sinks while producing routes comparable to the best previously existing Steiner router. Since performance oriented layout generators employ iterative techniques that require a large number of calls to the routing algorithm for layout evaluation, a fast algorithm for routing is desirable. Our algorithm has a fast (O(n/sup 2/), where n is the number of points) and practical implementation using simple data structures and techniques. Comparisons with other existing algorithms are presented along with results from a performance driven layout generator using our routing algorithm.

Index Terms:

network routing; integrated circuit layout; VLSI; circuit layout CAD; iterative methods; data structures; computational complexity; delays; performance-oriented Steiner routing; fast routing algorithm; Elmore delay minimisation; layout generators; iterative techniques; data structures

Citation:

M. Borah, R.M. Owens, M.J. Irwin, "Fast algorithm for performance-oriented Steiner routing," glsvlsi, pp.198, Fifth Great Lakes Symposium on VLSI (GLSVLSI'95), 1995

Peer Review Notice | Give Us Feedback

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