Browsing by Author "Naclerio, N.J."
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item A Linear Time Algorithm for Circular Permutation Layout.(1988) Rim, C.S.; Naclerio, N.J.; Masuda, Sumio; Nakajima, K.; ISRSuppose that two sets of terminals t_l,t_2,...,t_n and b_1,b_2,...,b_n are located on two concentric circles C_out and C_in, respectively. Given a permutation PI of integers 1,2,...,n, the circular permutation layout problem is the problem of connecting each pair of terminals t_i and b_PI(i) for i = 1,2,. . .,n with zero width wires in such a way that no two wires which correspond to different terminal pairs intersect each other. In this paper, we present a linear time algorithm for the following case: (i) no wire can cross C_out, (ii) at most one wire can pass between any two adjacent terminals on C_in, and (iii) no wire can cross C_in more than once. The previously known algorithm for the same case has time complexity O(n^2).Item Via Minimization for IC and PCB Layouts(1987) Naclerio, N.J.; Nakajima, K.; ISRIn 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.Item The Via Minimization Problem is NP-Complete.(1987) Naclerio, N.J.; Masuda, Sumio; Nakajima, K.; ISRVias between different layers of interconnection on dense integrated circuits tend to reduce yield, degrade performance, and take up a large amount of chip area. Similarly, contact holes on multilayer printed circuit boards add to manufacturing cost, and reduce reliability. Thus, many researchers have examined ways to minimize the number of vias required for a particular circuit layout. In this paper, we analyze the computational complexity of the so-called Constrained Via Minimization problem. Given an already routed circuit, the problem is to find a minimum cardinality set of vias for which a valid layer assignment exists. We first prove that the corresponding decision problem is NP-complete. We then show that it remains NP-complete even if one or more of the following restrictions are imposed.