Congestion prediction in early stages

ABSTRACT

Routability optimization has become a major concern in the physical design cycle of VLSI circuits. Due to the recent advances in VLSI technology, interconnect has become a dominant factor of the overall performance of a circuit. In order to optimize interconnect cost, we need a good congestion estimation method to predict routability in the early stages of the design cycle. Many congestion models have been proposed but there's still a lot of room for improvement. Some existing models [6] are dependent on parameters that are related to the actual congestion of the circuits. Besides, routers will perform rip-up and re-route operations to prevent overflow but most models do not consider this case. The outcome is that the existing models will usually under-estimate the routability. In this paper, we propose a new congestion model to solve the above problems. The estimation process is divided into three steps: preliminary estimation, detailed estimation and congestion redistribution. We have compared our new model and some existing models with the actual congestion measures obtained by global routing some placement results with a publicly available maze router [2]. Results show that our model has significant improvement in prediction accuracy over the existing models.

REFERENCES

• 1: http://vlsicad.eecs.umich.edu/bk/ispd02bench/.
• 2: http://www.cs.ucla.edu/~kastner/labyrinth/.
• 3: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 4: C. C. Chang, J. Cong, D. Z. Pan, and X. Yuan. Interconnect-driven floorplanning with fast global wiring planning and optimization. In Proc. SRC Tech. Conference, 2000.
• 5: Hung-Ming Chen , Hai Zhou , F. Y. YOung , D. F. Wong , Hannah H. Yang , Naveed Sherwani, Integrated floorplanning and interconnect planning, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.354-357, November 07-11, 1999, San Jose, California, United States
• 6: Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
• 7: Kusnadi , Jo Dale Carothers, A method of measuring nets routability for MCM's general area routing problems, Proceedings of the 1999 international symposium on Physical design, p.186-192, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300069]
• 8: Steve T. W. Lai , Evangeline F. Y. Young , Chris C. N. Chu, A New and Efficient Congestion Evaluation Model in Floorplanning: Wire Density Control with Twin Binary Trees, Proceedings of the conference on Design, Automation and Test in Europe, p.10856, March 03-07, 2003
• 9: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 10: Yuchun Ma , Xianlong Hong , Sheqin Dong , Song Chen , Yici Cai , C. K. Cheng , Jun Gu, Dynamic global buffer planning optimization based on detail block locating and congestion analysis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776036]
• 11: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 12: C. W. Sham and E. F. Y. Young. Routability-driven floorplanning with buffer planning. In IEEE Transactions on CAD of Integrated Circuit and System, pages 470--480, April 2003.
• 13: Maogang Wang , Majid Sarrafzadeh, Modeling and minimization of routing congestion, Proceedings of the 2000 conference on Asia South Pacific design automation, p.185-190, January 2000, Yokohama, Japan [doi>10.1145/368434.368601]
• 14: M. Wang, X. Yang, and M. Sarrafzadeh. Congestion minimization during placement. In IEEE Transactions on CAD of Integrated Circuit and System, pages 1140--1148, October 2000.
• 15: Jurjen Westra , Chris Bartels , Patrick Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981110]
• 16: X. J. Yang, R. Kastner, and M. Sarrafzadeh. Congestion estimation during top-down placement. In IEEE Transactions on CAD of Integrated Circuit and System, pages 72--80, January 2002.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Performance

Keywords:
floorplanning, interconnect estimation, placement