Search

With the recent development of semiconductor integration technology, the amount of data that must be handled in the layout design of VLSI is increasing rapidly. Even if the improvement of the processing speed of the computer in the future is considered, it is desired to develop a high-speed layout algorithm compared to the conventional method. This paper discusses the k (> 2)-way graph partitioning problem, which is one of the most basic problems concerning the layout design. A parallel algorithm is proposed. The general method to solve this problem has been to apply hierarchically the two-way graph partitioning algorithm. In this method, the algorithm can easily be executed in parallel by operating a number of processors at each hierarchy. A problem then is the efficiency of the processor and the computation time. This paper considers the k-way graph partitioning and proposes a new method called nonhierarchical k-way graph partitioning, aiming at the education of the computation time by parallel processing. In general, it is considered difficult to improve the speed sufficiently by the parallel processing, while maintaining the same accuracy of the solution as that of the sequential algorithm. In this paper, the effectiveness of the proposed algorithm is shown by a simulation experiment on the sequential computer. [ABSTRACT FROM AUTHOR]

In VLSI layout design by the building block approach, a hierarchical floorplanning method is proposed in which the floorplan and global routing are determined simultaneously to realize low-congestion switchboxes. In this method, overlap resolution, which pre- serves relative position and minimizes the obtained chip area, is needed to prevent the increase in the wire length of each net. In this paper, a fundamental study of this overlap resolution Is made, and the following are described. (1) The formulation of the overlap resolution problem RI is given. In the formulation, (a) preservation of relative position among blocks, and (b) the minimization of obtained chip area are considered; (2) the computational complexity of the problem is analyzed, and then NP-completeness of the problem RI is proved; and (3) a polynomial heuristic algorithm R for the problem RI is given. In addition, the result of simulation experiments to verify the efficiency of the heuristic algorithm R is also described. [ABSTRACT FROM AUTHOR]

In the detailed routing for VLSI standard cell layout design, the over-the-cell channel routing, which utilizes the over-the-cell region as the routing region, has been proposed. In this design method, after determining the net assignment to each channel in the global routing step, the track assignment both in channel and on over-the-cell regions is performed by an over-the-cell channel router. However, conventional global routing algorithms do not assume over-the-cell routing but conventional channel routing. Therefore, the minimization of channel density does not always successfully lead to the minimization of the final channel height. This paper presents a new global routing method for standard cell layouts to determine global routes for each net in both channel and over-the-cell regions simultaneously. The standard cell layout design system GLORIA based on the proposed algorithm is developed, and the experimental results compared with the conventional global routing method that performs the over-the-cell channel routing after global-routing with TimberWolf-SC4.2c are reported. Experimental results showed that the proposed routing algorithm can route about 18.4 percent fewer number of tracks than the conventional routing method, and the effectiveness of the proposed method is shown. The experimental results of applying the proposed method to the three-layer routing layout model also are presented. [ABSTRACT FROM AUTHOR]

In a VLSI layout design using the building block approach, design is divide into two phases, placement and routing. On the other hand, a new hierarchical floorplanning method was proposed by Dai et al., in which a global routing for the evaluation of the placement. However, the precise estimation of routability is difficult since the global routes in this method do not correspond to the routing region such as channels and switchboxes. In this paper, a new method is proposed, which simultaneously and hierarchically obtains floorplan, shapes and positions of modules, and global routes which directly correspond to switchboxes and channels. In this method, the routing-based partitioning, the hierarchical detailed global routing, and the hierarchical positioning are repeatedly executed, and a chip which small area and short wire length is obtained. This paper presents these three algorithms, and discusses the experimental results of each algorithm and the whole proposed method in a comparison to the conventional method that separately executes placement and routing. [ABSTRACT FROM AUTHOR]

This paper considers the building block method, which is one of the methods in VLSI layout design, and discusses the improvement of module placement assuming that a one-dimensional placement of the modules is given as the initial placement. Discussions are made of the following: (1) The case where net list given as the input is composed only of two-terminal nets, which connect the external terminals and the modules. The placement improvement problem PMO is formulated, Where the virtual connection length defined only by x coordinate is to be minimized while retaining the placement order of the modules. The algorithm to solve this problems as well as the proof for the optimality, are presented. Then a problem PM1 with a constraint on the range of displacement of the module is considered, and it is shown that the problem can be solved by extending the algorithm for PMO. (2) A problem PM2 is considered, which is am extension of PM1 by introducing in general the multiterminal net connecting modules and external terminals. It is shown that PM2 can be reduced to PM1. (3) A problem PM3 is considered, where river routing is adopted as the connection model, and the connection length is to be minimized considering also g coordinates (separation). It is shown that the optimal solution can be obtained in a polynomial time of the number of modules and the number of nets. [ABSTRACT FROM AUTHOR]

in VLSI layout design, the placement problem of functional blocks with different sizes and shapes include two NP-hard problems, that is, the problem of minimizing the chip size and the problem of minimizing the total virtual wire length. Therefore, in general, it is considered that any efficient placement method is very hard to develop. As a fundamental consideration of the placement problem, this paper discusses a placement problem in which the size of each block to be placed is restricted. First, the placement problem MSL in which the size of each block is restricted to be either 2 × 2, 2 × 1, or 1 × 1 is formulated. Next, a heuristic algorithm for the problem MSL is presented and some theoretical consideration on the proposed algorithm is given. In the theoretical consideration, the following two results are shown: 1) that the algorithm can find an initial placement with minimum chip area within a linear time on the number of blocks; and 2) that a set of placement change operations used to improve the total virtual wire length is a sufficient set of operations in a sense that any placement can always be transformed into another arbitrary placement by using the set of operations. Finally, the results of simulation experiment which was performed to evaluate empirically the proposed algorithm are scribed. [ABSTRACT FROM AUTHOR]

One of the interesting issues in the management of large computer networks is to partition the network into clusters and then to perform the management for each cluster. This paper presents a basic discussion on the initial clustering problem for a given network. The initial clustering problem C is defined as follows. Given a graphic representation G(V,E), V-n of a network and a set of nodes G-(c)1≤ r ≤ m) &epsive; 1, the graph G is to be partitioned into m connected subgraphs Gi = (Vi, Ei) (1≦i≦m) of G satisfying the following conditions: &o1; V, O C= (c), &o2; V, ≦K (a positive integer); and &o3; the distance between v&epsive; V, and Cx&epsive; C is minimum when x = i. The following results were obtained for the time complexity of the problem C: (1) the initial clustering problem C is in general NP-hard; and (2) the sub-problem obtained by deleting the condition &o2; can be solved in O(n⊃). [ABSTRACT FROM AUTHOR]