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 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]