Persistent Link:
http://hdl.handle.net/10150/187524
Title:
MCG: A multilayer general area MCM routing algorithm.
Author:
Li, Donghui.
Issue Date:
1995
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 new multilayer, general-area, multichip module (MCM) routing algorithm, called MCG, is introduced. The algorithm differs from other MCM routers in the way that the routes interconnecting the nets are constructed. Some routers perform the routing net-by-net and others extend the routes piece by piece during the routing process. The MCG router takes a more global approach by constructing a small number of candidate routes for each net, building a compatibility graph for the candidate routes and reducing the graph to yield a routing solution. Due to this unique way of performing the routing, the MCG router offers several outstanding features. First, it performs the routing of the nets simultaneously. Therefore it is not subject to the net ordering problem. Second, it can give the designer the flexibility of selecting the topology of routes for the nets to be routed, which is almost impossible for other algorithms. Third, it offers a natural way to incorporate the electrical constraints into the routing process, which is absent or hard to handle in other algorithms. The timing constraint can be incorporated easily by constructing the candidate routes of the net according to the requirements of the design; and the compatibility test of the candidate routes can be used to estimate the crosstalk between the routes from different nets, which make the crosstalk estimation more sophisticated than the other techniques. Compared with other MCM routers, the MCG router produces better quality routing solutions in terms of number of layers, number of vias, total wire length and routing density. In addition to the application in the area of MCM routing, the MCG algorithm can also be applied to high density PCB routing problems.
Type:
text; Dissertation-Reproduction (electronic)
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Electrical and Computer Engineering; Graduate College
Degree Grantor:
University of Arizona
Committee Chair:
Carothers, Jo Dale

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleMCG: A multilayer general area MCM routing algorithm.en_US
dc.creatorLi, Donghui.en_US
dc.contributor.authorLi, Donghui.en_US
dc.date.issued1995en_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 new multilayer, general-area, multichip module (MCM) routing algorithm, called MCG, is introduced. The algorithm differs from other MCM routers in the way that the routes interconnecting the nets are constructed. Some routers perform the routing net-by-net and others extend the routes piece by piece during the routing process. The MCG router takes a more global approach by constructing a small number of candidate routes for each net, building a compatibility graph for the candidate routes and reducing the graph to yield a routing solution. Due to this unique way of performing the routing, the MCG router offers several outstanding features. First, it performs the routing of the nets simultaneously. Therefore it is not subject to the net ordering problem. Second, it can give the designer the flexibility of selecting the topology of routes for the nets to be routed, which is almost impossible for other algorithms. Third, it offers a natural way to incorporate the electrical constraints into the routing process, which is absent or hard to handle in other algorithms. The timing constraint can be incorporated easily by constructing the candidate routes of the net according to the requirements of the design; and the compatibility test of the candidate routes can be used to estimate the crosstalk between the routes from different nets, which make the crosstalk estimation more sophisticated than the other techniques. Compared with other MCM routers, the MCG router produces better quality routing solutions in terms of number of layers, number of vias, total wire length and routing density. In addition to the application in the area of MCM routing, the MCG algorithm can also be applied to high density PCB routing problems.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineElectrical and Computer Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.chairCarothers, Jo Daleen_US
dc.contributor.committeememberHill, Fredrick J.en_US
dc.contributor.committeememberTharp, Hal S.en_US
dc.identifier.proquest9706308en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.