How does partitioning matter for 3D floorplanning?

ABSTRACT

The recent hierarchical design framework[8] for 3D floorplan-ning suggests a better performance than previous flat design framework. Under this framework, the layer assignment of the blocks is accomplished by some partitioning algorithms which are assumed to be critical[8]. In this paper, we provide an empirical study on the impact of such partitioning algorithms on the total wire length. By generating various partitions and running our floorplanner based on these partitions, we obtain the statistic of the resultant wire length. We observe that when the design instance has a large number of blocks which are uniformly sized, different partitions with the same cut size lead to roughly the same wire length. By another experiment, we find out that the cut size of the partition has the major influence on the wire length. Therefore, we argue that cut size is a metric good enough for the wire length optimization of 3D floorplanning and suggest that future research focus on other problems such as thermal effect, signal delay, etc.

REFERENCES

• 1: S. N. Adya and I. L. Markov. Fixed-outline floorplanning: Enabling hierarchical design. IEEE Trans. on VLSI Systems, 1(11):1120--1135, Dec. 2003.
• 2: K. Bazargan, R. Kastner, and M. Sarrafzadeh. 3D floorplanning: Simulated annealing and greedy placement methods for reconfigurable computing systems. Journal of Design Automation for Embedded Systems(DAfES), Apr. 2000.
• 3: Lei Cheng , Liang Deng , Martin D. F. Wong, Floorplanning for 3-D VLSI design, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120899]
• 4: J. Cong , Jie Wei , Yan Zhang, A thermal-driven floorplanning algorithm for 3D ICs, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.306-313, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382591]
• 5: Shamik Das , Andy Fan , Kuan-Neng Chen , Chuan Seng Tan , Nisha Checka , Rafael Reif, Technology, performance, and computer-aided design of three-dimensional integrated circuits, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981091]
• 6: Yangdong Deng , Wojciech P. Maly, Interconnect characteristics of 2.5-D system integration scheme, Proceedings of the 2001 international symposium on Physical design, p.171-175, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369763]
• 7: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 8: Z. Li, X. Hong, Q. Zhou, Y. Cai, J. Bian, H. Yang, P. Saxena, and V. Pitchumani. A divide-and-conquer 2.5-D floorplanning algorithm based on statistical wirelength estimation. In Proc. ISCAS'05, pages 6230--6233. IEEE, 2005.
• 9: P. H. Madden. Supersize VLSI, a recipe for disaster. In Electronic Design Process(EDP) 2005 Workshop. IEEE, 2005.
• 10: http://www.cse.ucsc.edu/research/surf/GSRC/progress.html.
• 11: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. on CAD, 15(12):1518--1524, Dec. 1996.
• 12: P. H. Shiu, R. Ravichandran, S. Easwar, and S. K. Lim. Multi-layer floorplanning for reliable system-on-package. In Proc. ISCAS'04, pages V69--V72. IEEE, 2004.
• 13: Xiaoping Tang , Ruiqi Tian , D. F. Wong, Fast evaluation of sequence pair in block placement by longest common subsequence computation, Proceedings of the conference on Design, automation and test in Europe, p.106-111, March 27-30, 2000, Paris, France [doi>10.1145/343647.343713]
• 14: H. Yamazaki, K. Sakanushi, S. Nakatake, and Y. Kajitani. The 3D-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals, E83-A(4):639--645, Apr. 2000.

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:
Experimentation

Keywords:
3D IC, floorplanning, partitioning, wire length