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. A. E. Caldwell, A. B. Kahng, and I. L. Markov. Can recursive bisection produce routable placements? In Proceedings of the 37th ACM/IEEE Design Automation Conference, pages 477--482, 2000.
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. H. M. Chen, H. Zhou, F. Y. Young, D. Wong, H. H. Yang, and N. Sherwani. Integrated floorplanning and interconnect planning. In Proceedings of IEEE Internation Cnference on Computer-Aided Design, pages 354--357, 1999.
6. A. B. Kahng and X. Xu. Accurate pseudo-constructive wirelength and congestion estimation. In Proceedings of International Workshop on System-level Interconnect Prediction, pages 61--68, 2003.
7. Kusnadi and J. D. Carothers. A method of measuring nets routability for MCM's general area routing problems. In Proceedings of Internation Symposium on Physical Design, pages 186--194, 1999.
8. S. T. W. Lai, E. F. Y. Young, and C. C. N. Chu. A new and efficient congestion evaluation model in floorplanning: Wire density control with twin binary trees. In Proceedings of Design, Automation and Test in Europe Conference and Exhibition, 2003.
9. J. Lou, S. Krishnamoorthy, and H. S. Sheng. Estimating routing congestion using probabilistic analysis. In Proceedings of Internation Symposium on Physical Design, pages 112--117, 2001.
10. Y. C. Ma, X. L. Hong, S. Q. Dong, S. Chen, Y. C. Cai, C. K. Cheng, and J. Gu. Dynamic global buffer planning optimization based on detail block locating and congestion analysis. In Proceedings of ACM/IEEE Design Automation Conference, pages 806--811, 2003.
11. P. N. Parakh, R. B. Brown, and K. A. Sakallah. Congestion driven quadratic placement. In Proceedings of the 37th ACM/IEEE Design Automation Conference, pages 275--278, 1998.
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. M. Wang and M. Sarrafzadeh. Modeling and minimization of routing congestion. In Proceedings of the ASP-ACM/IEEE Design Automation Conference, pages 185--190, 2000.
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. J. Westra, C. Bartels, and P. Groeneveld. Probabilistic congestion prediction. In Proceedings of Internation Symposium on Physical Design, pages 204--209, 2004.
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

• Hardware

  • Electronic design automation

    • Physical design (EDA)

  • Hardware validation