Show simple item record

dc.contributor.advisorNakajima, K.en_US
dc.contributor.authorNaclerio, N.J.en_US
dc.date.accessioned2007-05-23T09:40:19Z
dc.date.available2007-05-23T09:40:19Z
dc.date.issued1987en_US
dc.identifier.urihttp://hdl.handle.net/1903/4721
dc.description.abstractIn the design of integrated circuits (ICs), it is important to minimize the number of vias between conductors on different layers since excess vias lead to decreased yield and degraded circuit performance. Similarly, in the design of printed circuit boards (PCBs), it is important to minimize the number of contact holes used to connect copper strips on opposite sides of the board. Excess contact holes increase manufacturing cost and decrease the board's reliability. Given a particular design of an IC (or PCB), the Constrained Via Minimization Problem is to find a layer assignment that requires the fewest possible vias (or contact holes). It is shown that this problem is NP-hard for two- layer layouts and remains so when the layout is restricted to be grid-based, vias are restricted to lie at previously existing junctions, and the maximum number of wires which are joined at any particular junction does not exceed six. A new graph- theoretic formulation of the two-layer problem is then presented along with an algorithm which yields optimum results when the maximum junction degree is limited to three. The worst-case time complexity of the algorithm is O (n sup 3) where n is the number of routing segments in the given layout. Unlike previous algorithms, this algorithm does not require the layout to be grid based and places no constraints on the location of vias or the number of wires that may be joined at a single junction. If there are junctions with degree exceeding three, then our solution may be slightly less then optimum. If vias are limited to a subset of all possible via sites such as those allowable by a particular set of geometric design rules, then a further speedup is possible. This algorithm has been fully implemented. When tested on examples from the literature, it was found to be faster than the existing heuristic algorithms. A new heuristic is also suggested that is based on properties of the optimum solutions which were generated by this algorithm.en_US
dc.format.extent2824433 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; PhD 1987-2en_US
dc.subjectSystems Integrationen_US
dc.titleVia Minimization for IC and PCB Layoutsen_US
dc.typeDissertationen_US
dc.contributor.departmentISRen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record