On the use of flexible, rectilinear blocks to obtain minimum-area floorplans in mixed block and cell designs

This paper presents three minimum-area floorplanning algorithms that use fl exible arbitrary rectilinear shapes for the standard cell regions in MBC de signs. The first algorithm (pure HCST) introduces a grid traversal techniqu e which guarantees a minimum-area floorplan. The second algorithm (Hybrid-B F) uses a combination of HCST and Breadth First (BF) traversals to give a p ractical solution that approximately places flexible blocks at specified lo cations called seeds. The third algorithm (Hybrid-MBF) improves on the shap es of the flexible blocks generated by Hybrid-BF by using a combination of HCST and a Modified Breadth First (MBF) traversal. All three algorithms are polynomial in the number of grid squares. optimized implementations of Hyb rid-BF and Hybrid-MBF required less than two seconds on a SUN SPARCstation1 0.