Via Minimization for IC and PCB Layouts

In 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