Search

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]

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]