1. Overlap Resolution Problem for Block Placement in VLSI Layout.
- Author
-
Ohmura, Michiroh, Miyao, Jun'ichi, Yoshida, Noriyoshi, and Kikuno, Tohru
- Subjects
- *
VERY large scale circuit integration , *COMPUTATIONAL complexity , *HEURISTIC , *ALGORITHMS , *POLYGONS , *INTEGRATED circuits - Abstract
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]
- Published
- 1990
- Full Text
- View/download PDF