This work presents a full-chip RLC crosstalk budgeting routing flow to generate a high-quality routing design under stringent crosstalk constraints. Based on the cost function addressing the sensitive nets in visited global cells for each net, global routing can lower routing congestion as well as coupling effect. Crosstalk-driven track routing minimizes capacitive coupling effects and decreases inductive coupling effects by avoiding placing sensitive nets on adjacent tracks. To achieve inductive crosstalk budgeting optimization, the shield insertion problem can be solved with a minimum column covering algorithm which is undertaken following track routing to process nets with an excess of inductive crosstalk. The proposed routing flow method can identify the required number of shields more accurately, and process more complex routing problems than the linear programming (LP) methods. Results of this study demonstrate that the proposed approach can effectively and quickly lower inductive crosstalk by up to one-third.

Timing optimization is an important goal of global routing in deep submicron era. To guarantee the timing performance of the circuit, merely adopting topology optimization becomes inadequate. In this paper, we present an efficient timing-driven global routing algorithm with buffer insertion. Our approach is capable of applying topological-based timing optimization and buffer insertion simultaneously with routablity considerations. Compared with previous works, we efficiently solve the timing issues under a limited buffer usage. The experimental results have demonstrated significant delay improvement within short runtime with very small number of buffers inserted.

In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid) as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has a merit that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width k (i.e., the minimum width of a grid into which the tree can be laid out is k) can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area and width k + α, where α is an arbitrary integer with 0 α , and the area is existentially optimal for any k 1 and α 0. This implies that α = Ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.

It is known that the problem of determining, given a planar graph G and an integer m, whether there exists a congestion-1 embedding of G into an m k-grid is NP-complete for a fixed integer k 3. It is also known that the problem for k = 3 is NP-complete even if G is restricted to an acyclic graph. The complexity of the problem for k = 2 was left open. In this paper, we show that for k = 2, the problem can be solved in polynomial time if G is restricted to a tree, while the problem is NP-complete even if G is restricted to an acyclic graph.

It is known that the problem of determining, given a planar graph G and integers m and n, whether there exists a congestion-1 embedding of G into a two dimensional mn-grid is NP-complete. In this paper, we show that the problem is still NP-complete if G is restricted to an acyclic graph.

Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.

The most crucial factor that degrades a high speed VLSI is the signal propagation delay in a routing tree. It is estimated by the sum of the delay caused by the source-to-sink path length and by the total length. To design a routing tree in which these two are both small and balanced, we propose an algorithm to construct such a spanning tree, based on the idea of constructing a tree combining the minimum-spanning-tree and shortest-path-tree algorithms. This idea is extended to finding a rectilinear Steiner tree. Experiments are presented to illustrate how the source-to-sink path length and total length can be ballanced and small.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

The family Pk of graphs with proper-path-width at most k is minor-closed. It is known that the number of minimal forbidden minors for a minor-closed family of graphs is finite, but we have few such families for which all the minimal forbidden minors are listed. Although the minimal acyclic forbidden minors are characterized for Pk, all the minimal forbidden minors are known only for P1. This paper lists 36 minimal forbidden minors for P2, and shows that there exist no other minimal forbidden minors for P2.