Congestion prediction in early stages of physical design

Abstract

Routability optimization has become a major concern in physical design 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 designing stages. Many congestion models have been proposed but there's still a lot of room for improvement. Besides, routers will perform rip-up and reroute operations to prevent overflow, but most models do not consider this case. The outcome is that the existing models will usually underestimate the routability. In this paper, we have a comprehensive study on our proposed congestion models. Results show that the estimation results of our approaches are always more accurate than the previous congestion models.

References

1. Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2000. Can recursive bisection produce routable placements? In Proceedings of the 37th ACM/IEEE Design Automation Conference. 477--482.
2. Chang, C. C., Cong, J., Pan, D. Z., and Yuan, X. 2000. Interconnect-driven floorplanning with fast global wiring planning and optimization. In Proceedings of the SRC Technical Conference.
3. Chen, H. M., Zhou, H., Young, F. Y., Wong, D., Yang, H. H., and Sherwani, N. 1999. Integrated floorplanning and interconnect planning. In Proceedings of the IEEE Internation Cnference on Computer-Aided Design. 354--357.
4. ISPD. 2002. http://vlsicad.eecs.umich.edu/bk/ispd02bench/.
5. ISPD. 2008. http://www.sigda.org/ispd2007/rcontest/.
6. Kahng, A. B. and Xu, X. 2003. Accurate pseudo-constructive wirelength and congestion estimation. In Proceedings of the International Workshop on System-level Interconnect Prediction. 61--68.
7. Kastner, R., Bozorgzadeh, E., and Sarrafzadeh, M. 2002. Pattern routing: Use and theory for increasing predictability and avoiding coupling. In IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst.
8. Kusnadi and Carothers, J. D. 1999. A method of measuring nets routability for MCM's general area routing problems. In Proceedings of the International Symposium on Physical Design. 186--194.
9. Lai, S. T. W., Young, E. F. Y., and Chu, C. C. N. 2003. A new and efficient congestion evaluation model in floorplanning: Wire density control with twin binary trees. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition.
10. Lou, J., Krishnamoorthy, S., and Sheng, H. S. 2001. Estimating routing congestion using probabilistic analysis. In Proceedings of the Internation Symposium on Physical Design. 112--117.
11. Ma, Y. C., Hong, X. L., Dong, S. Q., Chen, S., Cai, Y. C., Cheng, C. K., and Gu, J. 2003. Dynamic global buffer planning optimization based on detail nlock locating and congestion analysis. In Proceedings of the ACM/IEEE Design Automation Conference. 806--811.
12. Moffitt, M. D. 2008. Maizerouter: Engineering an effective global router. In Proceedings of the ASP-ACM/IEEE Design Automation Conference. 226--231.
13. Pan, M. and Chu, C. 2006. Fastroute: a step to integrate global routing into placement. In Proceedings of the IEEE Internation Cnference on Computer-Aided Design. 464--471.
14. Saeedi, M., Zamani, M. S., and Jahanian, A. 2006. Prediction and reduction of routing congestion. In Proceedings of the International Workshop on System Level Interconnect Prediction. 72--77.
15. Sham, C. W. and Young, E. F. Y. 2005a. Congestion prediction in early stages. In Proceedings of the International Workshop on System Level Interconnect Prediction. 91--98.
16. Sham, C. W. and Young, E. F. Y. 2005b. Congestion prediction in floorplanning. In Proceedings of the ASP-ACM/IEEE Design Automation Conference. 1107--1110.
17. Taghavi, T., Dabiri, F., Nahapetian, A., and Sarrafzadeh, M. 2007. Tutorial on congestion prediction. In Proceedings of the International Workshop on System Level Interconnect Prediction. 15--24.
18. Wang, M. and Sarrafzadeh, M. 2000. Modeling and minimization of routing congestion. In Proceedings of the ASP-ACM/IEEE Design Automation Conference. 185--190.
19. Wang, M., Yang, X., and Sarrafzadeh, M. 2000. Congestion minimization during placement. In IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 1140--1148.
20. Westra, J., Bartels, C., and Groeneveld, P. 2004. Probabilistic congestion prediction. In Proceedings of Internation Symposium on Physical Design. 204--209.
21. Xiao, L., Li, L., and Qian, Z. 2008. International Society for Physical Design Routing Contest (ISPD'08).
22. Yang, X. J., Kastner, R., and Sarrafzadeh, M. 2002. Congestion estimation during top-down placement. In IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 72--80.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)