In current very large scale integration (VLSI) circuits, there can be hundreds of required I/O pins. Ball grid array (BGA) packaging is commonly used to realize the huge number of connections between VLSI chips and printed circuit boards (PCBs). In this paper, the authors propose a global-routing method by iterative improvements for two-layer BGA packages. In their routing model, the global routing for each net is uniquely determined by a via assignment. The proposed global-routing method begins with an initial feasible via assignment and incrementally improves the via assignment to minimize the maximum wire congestion and the total wire length. In each iteration, a via assignment is improved by exchanging two adjacent vias or by moving vias one by one to their adjacent grids. The algorithm efficiently generates better global routes than initial routes with respect to wire congestion and total wire length.

In current VLSI circuits, there can be hundreds of required I/O pins. BGA(Ball Grid Array) packaging is commonly used to realize the huge number of connections between VLSI and PCB. In this paper, we propose a global routing method for two-layer BGA packages. In our routing model, the global routing for each net is uniquely determined by a via assignment. Our global routing method begins with an initial feasible via assignment and incrementally improves the via assignment to minimize the total wire length and wire congestion. In each iteration, a via assignment is improved by exchanging adjacent two vias, rotating three vias, or by moving vias to their adjacent grids one by one. Our method is a greedy-based heuristic. The algorithm efficiently generates better global routes than initial routes with respect to wire congestion and total wire length.

In VLSI system, a certain set of nets is required to propagate their signals within a tolerable skew of delays. Though the delay of the signal on a wire is determined by a complex environment, it is hard to satisfy this requirement unless all the concerned nets are routed within a certain skew of length. This paper approaches this problem by the concept of l-equidistance routing which aims to route the concerned nets by prescribed length l. After a basic technique to route a 1-sink net with prescribed length, an algorithm is presented for the channel routing where sink terminals are on the upper line and source terminals on the bottom lines. The key idea is in the symmetric slant grid interconnect scheme by which the problem is reduced to the ordinary grid routing problem. An algorithm that attains minimum total wire length is presented. Then a solution is given for the case when terminals are on the perimeters on a rectangle. These algorithms are explained on the Euclidean space. But it is shown that a straightforward transformation of the routes to those on the orthogonal grid is possible keeping the property of equidistance. Proposed algorithms were implemented and applied to random data to demonstrate their ability.

Sequence-pair-based floorplanning has revealed the limit of its usefulness in very large scale integration layout design, the key issue being that it is nonhierarchical and indifferent to the preceding step of partitioning. This paper restructures the sequence pair enhanced to a pair of logic expressions to accept the constraint induced by the previous step - the balanced bipartition. Since the bipartition is hierarchical in nature, the transferred constraint is called the hierarchical superconstraint. Since floorplanning based on this data structure automatically works cooperatively with the partitioning, it is called the consistent floorplanning, which has potential to store all the feasible floorplans under the constraint induced by any balanced binary search. As a typical example, we focus on clock-tree synthesis by H-tree. Experiments are given to show better achievements in length and wire density for module-based circuits and clock trees.

Sequence-Pair based floorplanning has been revealed its limit of usefulness in VLSI physical design. Among reasons, the key issue is in its being non-hierarchical and indifferent to the preceding step of partitioning. This paper restructure the algorithm by the idea that the partition algorithm produces the constraint that is imposed on the sequence-pair data. The partition algorithm is the one based on the balanced-bipartition that works hierarchically. Thus a new floorplan algorithm that is consistent with the hierarchical partition algorithm is constructed. This is enhanced to include other algorithms that are based on the binary search. Here, a clock-tree synthesis by H-tree is shown to be consistent. Experiments are given to show better achievements in length and wire-density.

Abstract | Given a route which connects terminal-s on a one-layer routing area(Steiner tree), \n ip is a procedure that makes a current route change its con-guration within its peripheral domain. A \nip reforms a route by replacing one of its edges with a minimal detour. A route can \nip one nearby obstacle. If the obstacle is another route, a more organized operation, called the dual \nip, is applied to a pair of routes. The idea is enhanced to the 2-layer hv-routing. The per-formance of \nip and dual \nip was experimented in simulated annealing which reforms a route or a set of routes with respect to the evaluation function of mul-tiple objectives. Some unique and satisable results were observed. I.