Fast floorplanning by look-ahead enabled recursive bipartitioning

ABSTRACT

A new paradigm is introduced for floorplanning any combination of fixed-shape and variable-shape blocks under tight fixed-outline area constraints and a wirelength objective. Dramatic improvement over traditional floorplanning methods is achieved by explicit construction of strictly legal layouts for every partition block at every level of a cutsize-driven, top-down hierarchy. By scalably incorporating legalization into the hierarchical flow, post-hoc legalization is successfully eliminated. For large floorplanning benchmarks, an implementation, called PATOMA, generates solutions with half the wirelength of state-of-the-art floorplanners in orders of magnitude less run time.

REFERENCES

• 1: Fixed-Outline Floorplanning through Better Local Search, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.328, September 23-26, 2001
• 2: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 3: 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]
• 4: Jason Cong , Gabriele Nataneli , Michail Romesis , Joseph R. Shinnerl, An area-optimality study of floorplanning, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981083]
• 5: J. Cong, M. Romesis, and J. Shinnerl. Fast floorplanning by look-ahead enabled recursive bipartitioning. Technical Report TR040043, Computer Science Dept., University of California, Los Angeles, 2004.
• 6: 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]
• 7: http://cadlab.cs.ucla.edu/cpmo/HBsuite.html/.
• 8: X. Hong, S. Dong, G. Huang, Y. Ma, Y. Cai, C. Cheng, and J. Gu. A Non-slicing Floorplanning Algorithm Using Corner Block List Topological Representation. In Proc. Design Automation Conf., pages 268--273, 1999.
• 9: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 10: 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]
• 11: 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
• 12: S. Nakatake, K. Fujiyoshi, H. Mirata, and Y. Kajitani. Module Packing Based on the BSG-structure and IC Layout Applications. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, volume 17, pages 519--530, 1998.
• 13: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 14: Abhishek Ranjan , Kiarash Bazargan , Seda Ogrenci , Majid Sarrafzadeh, Fast floorplanning for effective prediction and construction, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.341-352, April 2001 [doi>10.1109/92.924056]
• 15: Peter G. Sassone , Sung K. Lim, A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.74, November 09-13, 2003 [doi>10.1109/ICCAD.2003.15]
• 16: 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