Floorplanning for 3-D VLSI design

ABSTRACT

In this paper we present a floorplanning algorithm for 3-D ICs. The problem can be formulated as that of packing a given set of 3-D rectangular blocks while minimizing a suitable cost function. Our algorithm is based on a generalization of the classical 2-D slicing floorplans to 3-D slicing floorplans. A new encoding scheme of slicing floorplans (2-D/3-D) and its associated set of moves form the basis of the new simulated annealing based algorithm. The bestknown algorithm for packing 3-D rectangular blocks is based on simulated annealing using sequence-triple floorplan representation. Experimental results show that our algorithm produces packing results on average 3% better than the sequence-triple-based algorithm under the same annealing parameters, and our algorithm runs much faster (17 times for problems containing 100 blocks) than the sequence-triple. Moreover, our algorithm can be extended to consider various types of placement constraints and thermal distribution while the existing sequence-triple-based algorithm does not have such capabilities. Finally, when specializing to 2-D problems, our algorithm is a new 2-D slicing floorplanning algorithm. We are excited to report the surprising results that our new 2-D floorplanner has produced slicing floorplans for the two largest MCNC benchmarks ami33 and ami49 which have the smallest areas (among all slicing/nonslicing floorplanning algorithms) ever reported in the literature.

REFERENCES

• 1: K. Banerjee, S. J. Souri, P. Kapur, and K. C. Saraswat. 3-D ICs: a novel chip design for improving deep submicrometer interconnect performance and systems-on-chip integration. Proc. of the IEEE, 89(5):602--633, May 2001.
• 2: A. Fan, A. Rahman, and R. Reif. Copper wafer bonding. Electrochem. Solid State Lett., 2:534C536, 1999.
• 3: M. Chan and P. K. Ko. Development of a viable 3d integrated circuit technology. Science in China, 44(4):241--248, August 2001.
• 4: Ralph H.J.M. Otten, Automatic floorplan design, Proceedings of the 19th conference on Design automation, p.261-267, January 1982
• 5: 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
• 6: 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
• 7: Xianlong Hong , Gang Huang , Yici Cai , Jiangchun Gu , Sheqin Dong , Chung Kuan Cheng , Jun Gu, Corner block list: an effective and efficient topological representation of non-slicing floorplan, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: Evangeline F. Y. Yong, Chris C. N. Chu, and Zion C. S. Twin binary sequences: A nonredundant representation for general nonslicing floorplan. IEEE TCAD of Integrated Circuits and Systems, 22(4):457--469, April 2003.
• 9: Yingxin Pang , Chung-Kuan Cheng , Takeshi Yoshimura, An enhanced perturbing algorithm for floorplan design using the O-tree representation, Proceedings of the 2000 international symposium on Physical design, p.168-173, May 2000, San Diego, California, United States [doi>10.1145/332357.332395]
• 10: Hiroyuki Yamazaki et al. The 3d-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals, E83-A(4):639--645, April 2000.
• 11: Evangeline F. Y. Yong, D. F. Wong, and H. H. Yang. Slicing floorplans with boundary constraints. IEEE TCAD of Integrated Circuits and Systems, 18(9):1385--1389, September 1999.
• 12: Evangeline F. Y. Yong, D. F. Wong, and H. H. Yang. Slicing Floorplans with Range Constraint. IEEE TCAD of Integrated Circuits and Systems, 19(2):272--278, February 2000.
• 13: Kaustav Banerjee , Amit Mehrotra , Alberto Sangiovanni-Vincentelli , Chenming Hu, On thermal effects in deep sub-micron VLSI interconnects, Proceedings of the 36th ACM/IEEE conference on Design automation, p.885-891, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310093]
• 14: Wei Huang , Mircea R. Stan , Kevin Skadron , Karthik Sankaranarayanan , Shougata Ghosh , Sivakumar Velusam, Compact thermal modeling for temperature-aware design, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996800]
• 15: D. Chen, E. Li, E. Rosenbaum, and S. M. Kang. Interconnect thermal modeling for accurate simulation of circuit timing and reliability. IEEE TCAD of Integrated Circuits and Systems, 19(2):197--205, February 2000.
• 16: Xiaoping Tang , D. F. Wong, FAST-SP: a fast algorithm for block placement based on sequence pair, Proceedings of the 2001 conference on Asia South Pacific design automation, p.521-526, January 2001, Yokohama, Japan [doi>10.1145/370155.370523]
• 17: Shuo Zhou , Sheqin Dong , Chung-Kuan Cheng , Jun Gu, ECBL: an extended corner block list with solution space including optimum placement, Proceedings of the 2001 international symposium on Physical design, p.150-155, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369756]
• 18: C. Zhuang , Y. Kajitani , K. Sakanushi , L. Jin, An Enhanced Q-Sequence Augmented with Empty-Room-Insertion and Parenthesis Trees, Proceedings of the conference on Design, automation and test in Europe, p.61, March 04-08, 2002