×

An optimum placement search algorithm based on extended corner block list. (English) Zbl 1091.68500

Summary: A non-slicing approach, Corner Block List (CBL), has been presented recently. Since CBL only can represent floorplans without empty rooms, the algorithm based on CBL cannot get the optimum placement. An extended corner block list, \(\text{ECBL}_\lambda\), is proposed. It can represent non-slicing floorplan including empty rooms. Based on the optimum solution theorem of BSG (Bounded-Sliceline Grid), it is proved that the solution space of \(\text{ECBL}_n\), where \(n\) is the number of blocks, contains the optimum block placement with the minimum area. A placement algorithm based on \(\text{ECBL}_\lambda\), whose solution space can be controlled by setting \(\lambda\), the extending ratio, is completed. When \(\lambda\) is set as \(n\), the algorithm based on \(\text{ECBL}_n\) is the optimum placement search algorithm. Experiments show that \(\lambda\) has a reasonable constant range for building block layout problem, so the algorithm can translate an \(\text{ECBL}_\lambda\) representation to its corresponding placement in \(O(n)\) time. Experimental results on MCNC benchmarks show promising performance with 7% improvement in wire length and 2% decrease in dead space over algorithms based on CBL. Meanwhile, compared with other algorithms, the proposed algorithm can get better results with less runtime.

MSC:

68M07 Mathematical problems of computer architecture
Full Text: DOI

References:

[1] Ralph H J M Otten. What is a floorplan. InACM International Symposium on Physical Design (ISPD’2000), 2000, pp.174–180.
[2] Wong D F, Liu C L. A new algorithm for floorplan design. InProc. 23rd ACM/IEEE Design Automation Conference, 1 1986, pp.101–107.
[3] Hong Xianlong, Huang Gang, Dong Sheqinet al. Corner block list: An effective and efficient topological representation of non-slicing floorplan. InICCAD’2000, 2000, pp.8–12.
[4] Nakatake S, Murata H, Fujiyoshi K, Kajitani Y. Block placement on BSG-structure and IC layout application. InProc. International Conference on Computer Aided Design (ICCAD), 1996, pp.484–490.
[5] Hiroshi Murata. Kunihiro Fujiyoshi, Nakatake S, Kajitani Y. VLSI block placement based on rectangle-packing by the sequence pair.IEEE Trans. CAD, 1996, 15(15): 1518–1524.
[6] Jin Xu, Pei-Ning Guo, Chung-Kuan Cheng. Cluster refinement for block placement. InACM/IEEE Design Automation Conference, 1997, pp.762–765.
[7] Guo P N, Cheng C K. An O-tree representation of non-slicing floorplan and its applications. InACM/IEEE Design Automation Conference, 1999, pp.268–273.
[8] Pang Y, Cheng C K, Yoshimura T. An enhanced perturbing algorithm for floorplan design using the O-tree representation. InACM International Symposium on Physical Design, 2000, pp.168–173.
[9] Ma Yuchun, Dong Sheqin, Hong Xianlong, Cai Yiciet al. VLSI floorplanning with boundary constraints based on corner block list. InACM/IEEE ASP-DAC’2001, 2001, pp.509–514. · Zbl 0995.68198
[10] Ma Yuchun, Hong Xianlong, Dong Sheqin, Cai Yiciet al. Floorplanning with abutment constraints and L-shaped/T-shaped blocks based on corner block list. InACM/IEEE Design Automation Conference, 2001, pp.770–775. · Zbl 0995.68198
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.