Fast algorithm for performance-oriented Steiner routing

Manjit Borah; Robert Michael Owens; Mary Jane Irwin

Fast algorithm for performance-oriented Steiner routing

Manjit Borah, Robert Michael Owens, Mary Jane Irwin

Research output: Contribution to journal › Conference article › peer-review

Abstract

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²), 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.

Original language	English (US)
Pages (from-to)	198-203
Number of pages	6
Journal	Proceedings of the IEEE Great Lakes Symposium on VLSI
State	Published - Jan 1 1995
Event	Proceedings of the 5th Great Lakes Symposium on VLSI - Buffalo, NY, USA Duration: Mar 16 1995 → Mar 18 1995

All Science Journal Classification (ASJC) codes

Electrical and Electronic Engineering

Cite this

@article{bea6d9ccf7174dbe9cae686c056d725e,

title = "Fast algorithm for performance-oriented Steiner routing",

abstract = "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(n2), 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.",

author = "Manjit Borah and Owens, {Robert Michael} and Irwin, {Mary Jane}",

year = "1995",

month = jan,

day = "1",

language = "English (US)",

pages = "198--203",

journal = "Proceedings of the IEEE Great Lakes Symposium on VLSI",

issn = "1066-1395",

publisher = "IEEE Computer Society",

note = "Proceedings of the 5th Great Lakes Symposium on VLSI ; Conference date: 16-03-1995 Through 18-03-1995",

}

TY - JOUR

T1 - Fast algorithm for performance-oriented Steiner routing

AU - Borah, Manjit

AU - Owens, Robert Michael

AU - Irwin, Mary Jane

PY - 1995/1/1

Y1 - 1995/1/1

N2 - 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(n2), 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.

AB - 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(n2), 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.

UR - http://www.scopus.com/inward/record.url?scp=0029238204&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029238204&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0029238204

SN - 1066-1395

SP - 198

EP - 203

JO - Proceedings of the IEEE Great Lakes Symposium on VLSI

JF - Proceedings of the IEEE Great Lakes Symposium on VLSI

T2 - Proceedings of the 5th Great Lakes Symposium on VLSI

Y2 - 16 March 1995 through 18 March 1995

ER -

Fast algorithm for performance-oriented Steiner routing

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this