Persistent Link:
http://hdl.handle.net/10150/284108
Title:
Method of routability measure for general area routing problems
Author:
Kusnadi
Issue Date:
2000
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:
One of the vital phases in the design flow of electronic artifacts is the phase called physical design. In this phase--which traditionally involves partitioning, placement and routing problems--circuit designs are transformed into layouts ready for fabrication. Whether designing PCBs, MCMs or even VLSI chips, a problem that frequently arises is that of knowing if the layout will be routable. This is a classical problem of predicting routability/wireability that has been known since the early days of physical design. Unfortunately, quantifying the 'real' routability is a difficult task and hence the average wirelength based on the number of intramodule connections has become a common measure of routability. At the other end of this overly simplified measure, people do the actual place and route steps to determine the routability. In search of a more realistic way of quantifying the routability, a new method for measuring routability/wireability is proposed for use in general area routing problems. It focuses on MCM and dense PCB designs but can be extended to any general area routing problem. The routability is measured by extending the counting method of Pascal's Triangle where the number of potential routes of each net in the design can be obtained precisely. The method has made it possible to evaluate the number of potential routes in the presence of arbitrary obstacles as well as the possible limitations on the number of vias/bends to use. The theoretical development of the new method has resulted in two main algorithms called the EPTM and FEPT. Testing on several MCM benchmarks confirms what was intuitively believed that routes with 4 or less vias/bends are sufficient for general area routing problems in MCMs. It also uncovered the fact that increasing the number of vias/bends in the routes doesn't always increase the potential of routability unless detours are introduced. Further testing on non-minimum rectilinear paths shows that detours do improve the routability when the number of vias/bends between detour points is 3 or greater.
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.titleMethod of routability measure for general area routing problemsen_US
dc.creatorKusnadien_US
dc.contributor.authorKusnadien_US
dc.date.issued2000en_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.abstractOne of the vital phases in the design flow of electronic artifacts is the phase called physical design. In this phase--which traditionally involves partitioning, placement and routing problems--circuit designs are transformed into layouts ready for fabrication. Whether designing PCBs, MCMs or even VLSI chips, a problem that frequently arises is that of knowing if the layout will be routable. This is a classical problem of predicting routability/wireability that has been known since the early days of physical design. Unfortunately, quantifying the 'real' routability is a difficult task and hence the average wirelength based on the number of intramodule connections has become a common measure of routability. At the other end of this overly simplified measure, people do the actual place and route steps to determine the routability. In search of a more realistic way of quantifying the routability, a new method for measuring routability/wireability is proposed for use in general area routing problems. It focuses on MCM and dense PCB designs but can be extended to any general area routing problem. The routability is measured by extending the counting method of Pascal's Triangle where the number of potential routes of each net in the design can be obtained precisely. The method has made it possible to evaluate the number of potential routes in the presence of arbitrary obstacles as well as the possible limitations on the number of vias/bends to use. The theoretical development of the new method has resulted in two main algorithms called the EPTM and FEPT. Testing on several MCM benchmarks confirms what was intuitively believed that routes with 4 or less vias/bends are sufficient for general area routing problems in MCMs. It also uncovered the fact that increasing the number of vias/bends in the routes doesn't always increase the potential of routability unless detours are introduced. Further testing on non-minimum rectilinear paths shows that detours do improve the routability when the number of vias/bends between detour points is 3 or greater.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.proquest9965895en_US
dc.identifier.bibrecord.b40480847en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.