Multilevel floorplanning/placement for large-scale modules using B*-trees

ABSTRACT

We present in this paper a multilevel floorplanning/placement framework based on the B*-tree representation, called MB*-tree, to handle the floorplanning and packing for large-scale building modules. The MB*-tree adopts a two-stage technique, clustering followed by declustering. The clustering stage iteratively groups a set of modules based on a cost metric guided by area utilization and module connectivity, and at the same time establishes the geometric relations for the newly clustered modules by constructing a corresponding B*-tree for them. The declustering stage iteratively ungroups a set of the previously clustered modules (i.e., perform tree expansion) and then refines the floorplanning/placement solution by using a simulated annealing scheme. In particular, the MB*-tree preserves the geometric relations among modules during declustering, which makes the MB*-tree an ideal data structure for the multilevel floorplanning/placement framework. Experimental results show that the MB*-tree obtains significantly better silicon area and wirelength than previous works. Further, unlike previous works, MB*-tree scales very well as the circuit size increases.

REFERENCES

• 1: Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th conference on Design automation, p.189-194, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378461]
• 2: C. J. Alpert, J.-H. Huang, and A. B. Kahng, "Multilevel circuit partitioning," IEEE Trans. CAD, vol. 17, no. 8, pp. 655--667, August 1998.
• 3: M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear Programming Theory and Algorithms, 1993.
• 4: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 5: Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
• 6: Jason Cong , Jie Fang , Yan Zhang, Multilevel approach to full-chip gridless routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 7: Jason Cong , Tianming Kong , David Zhigang Pan, Buffer block planning for interconnect-driven floorplanning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.358-363, November 07-11, 1999, San Jose, California, United States
• 8: Jason Cong , Min Xie , Yan Zhang, An enhanced multilevel routing system, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.51-58, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774580]
• 9: Pei-Ning Guo , Chung-Kuan Cheng , Takeshi Yoshimura, An O-tree representation of non-slicing floorplan and its applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.268-273, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309928]
• 10: Bruce Hendrickson , Robert Leland, A multilevel algorithm for partitioning graphs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.28-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224228]
• 11: Iris Hui-Ru Jiang , Yao-Wen Chang , Jing-Yang Jou , Kai-Yuan Chao, Simultaneous floorplanning and buffer block planning, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119858]
• 12: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 13: Shu-Min Li , Yih-Huai Cherng , Yao-Wen Chang, Noise-aware buffer planning for interconnect-driven floorplanning, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119856]
• 14: Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379062]
• 15: Jai-Ming Lin , Yao-Wen Chang, TCG-S: orthogonal coupling of P*-admissible representations for general floorplans, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514127]
• 16: Jai-Ming Lin , Yao-Wen Chang , Shih-Ping Lin, Corner sequence: a P-admissible floorplan representation with a worst case linear-time packing scheme, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.4, p.679-686, August 2003 [doi>10.1109/TVLSI.2003.816137]
• 17: Shih-Ping Lin , Yao-Wen Chang, A novel framework for multilevel routing considering routability and performance, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.44-50, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774579]
• 18: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 19: Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
• 20: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 21: Probir Sarkar , Vivek Sundararaman , Cheng-Kok Koh, Routability-driven repeater block planning for interconnect-centric floorplanning, Proceedings of the 2000 international symposium on Physical design, p.186-191, May 2000, San Diego, California, United States [doi>10.1145/332357.332398]
• 22: D. F. Wong , C. L. Liu, A new algorithm for floorplan design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.101-107, July 1986, Las Vegas, Nevada, United States
• 23: F. Y. Young , Chris C. N. Chu , W. S. Luk , Y. C. Wong, Floorplan area minimization using Lagrangian relaxation, Proceedings of the 2000 international symposium on Physical design, p.174-179, May 2000, San Diego, California, United States [doi>10.1145/332357.332396]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
floorplanning, lagrangian relaxation, multilevel framework