A novel ultra-fast heuristic for VLSI CAD Steiner trees

Bharat Krishna; C. Y. Roger Chen; Naresh K. Sehgal

doi:10.1145/764856.764858

A novel ultra-fast heuristic for VLSI CAD Steiner trees

Bharat Krishna, C. Y. Roger Chen, Naresh K. Sehgal

Department of Electrical Engineering & Computer Science

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

Abstract

In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.

Original language	English (US)
Pages (from-to)	192-197
Number of pages	6
Journal	Proceedings of the IEEE Great Lakes Symposium on VLSI
DOIs	https://doi.org/10.1145/764856.764858
State	Published - 2003
Event	Proceedings of the 2003 ACM Great Lakes Symposium on VLSI - Washington, DC, United States Duration: Apr 28 2003 → Apr 29 2003

Keywords

Interconnect estimation
Routing
Steiner trees

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1145/764856.764858

Cite this

@article{44074d1b71834f93bc104a1bb309e76a,

title = "A novel ultra-fast heuristic for VLSI CAD Steiner trees",

abstract = "In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.",

keywords = "Interconnect estimation, Routing, Steiner trees",

author = "Bharat Krishna and {Roger Chen}, {C. Y.} and Sehgal, {Naresh K.}",

year = "2003",

doi = "10.1145/764856.764858",

language = "English (US)",

pages = "192--197",

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

issn = "1066-1395",

publisher = "IEEE Computer Society",

note = "Proceedings of the 2003 ACM Great Lakes Symposium on VLSI ; Conference date: 28-04-2003 Through 29-04-2003",

}

TY - JOUR

T1 - A novel ultra-fast heuristic for VLSI CAD Steiner trees

AU - Krishna, Bharat

AU - Roger Chen, C. Y.

AU - Sehgal, Naresh K.

PY - 2003

Y1 - 2003

N2 - In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.

AB - In all stages of VLSI chip design, routing estimation is required to account for the effect of interconnects. We propose a fast Steiner tree construction algorithm, which is 3-180 times faster for 10-300 point Steiner trees, and within 2.5% of the length of the Batched-1-Steiner tree. The proposed method can be used as a fast net length estimation tool in VLSI CAD applications, e.g. in the inner cycle of a floorplanning/placement engine.

KW - Interconnect estimation

KW - Routing

KW - Steiner trees

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

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

U2 - 10.1145/764856.764858

DO - 10.1145/764856.764858

M3 - Conference Article

AN - SCOPUS:0037699712

SN - 1066-1395

SP - 192

EP - 197

JO - Proceedings of the IEEE Great Lakes Symposium on VLSI

JF - Proceedings of the IEEE Great Lakes Symposium on VLSI

T2 - Proceedings of the 2003 ACM Great Lakes Symposium on VLSI

Y2 - 28 April 2003 through 29 April 2003

ER -

A novel ultra-fast heuristic for VLSI CAD Steiner trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this