Overlap resolution problem for block placement in VLSI layout
- 1 January 1990
- journal article
- research article
- Published by Wiley in Electronics and Communications in Japan (Part III: Fundamental Electronic Science)
- Vol. 73 (6) , 68-77
- https://doi.org/10.1002/ecjc.4430730608
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 preserves 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.Keywords
This publication has 2 references indexed in Scilit:
- A new floorplanning method with global routing based on functional partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Simultaneous Floor Planning and Global Routing for Hierarchical Building-Block LayoutIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987