Garnet: A graph-based octilinear mixed-signal Steiner tree routing system

Persistent Link:
http://hdl.handle.net/10150/298732
Title:
Garnet: A graph-based octilinear mixed-signal Steiner tree routing system
Author:
Newbould, Rexford D.
Issue Date:
2004
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
A compatibility graph-based, general area router for integrated circuit (IC) designs is presented. The highly flexible constraint system allows a number of modern and mixed-signal routing requirements to be handled, even for a large number of nets. The IC router can efficiently construct near-minimal Steiner trees for multi-terminal nets in both classical rectilinear, or Manhattan, geometry as well as octilinear geometries. These Steiner trees can be constructed around blockages, and in the presence of obstacles such as other nets. A method for routing trees through weighted areas is also introduced. The routing system can predict congested routing areas before routing is performed, and appropriately weight congested areas in order to reduce net congestion. Finally, a fast crosstalk violation checker can run alongside the routing engine. Each portion of the router is bounded by O(n log(n)) runtime, or less, making the entire routing process bounded by the same runtime. The system thus scales well to handle a very large number of exact routes in a fully mixed-signal aware engine, in either rectilinear or newly-introduced octilinear geometries.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Engineering, Electronics and Electrical.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Electrical and Computer Engineering
Degree Grantor:
University of Arizona
Advisor:
Carothers, Jo Dale

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleGarnet: A graph-based octilinear mixed-signal Steiner tree routing systemen_US
dc.creatorNewbould, Rexford D.en_US
dc.contributor.authorNewbould, Rexford D.en_US
dc.date.issued2004en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractA compatibility graph-based, general area router for integrated circuit (IC) designs is presented. The highly flexible constraint system allows a number of modern and mixed-signal routing requirements to be handled, even for a large number of nets. The IC router can efficiently construct near-minimal Steiner trees for multi-terminal nets in both classical rectilinear, or Manhattan, geometry as well as octilinear geometries. These Steiner trees can be constructed around blockages, and in the presence of obstacles such as other nets. A method for routing trees through weighted areas is also introduced. The routing system can predict congested routing areas before routing is performed, and appropriately weight congested areas in order to reduce net congestion. Finally, a fast crosstalk violation checker can run alongside the routing engine. Each portion of the router is bounded by O(n log(n)) runtime, or less, making the entire routing process bounded by the same runtime. The system thus scales well to handle a very large number of exact routes in a fully mixed-signal aware engine, in either rectilinear or newly-introduced octilinear geometries.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectEngineering, Electronics and Electrical.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorCarothers, Jo Daleen_US
dc.identifier.proquest3145112en_US
dc.identifier.bibrecord.b47210199en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.