Accurate pseudo-constructive wirelength and congestion estimation

ABSTRACT

Accurate estimation of wirelength and congestion is one of the fundamental issues in VLSI physical design. Current probabilistic estimation methods fail to produce accurate results since they ignore congestion-related detouring and effects of the number of vias and bends. In this work, we propose a practical stochastic routing probability distribution model which includes the effects of blockage and the number of bends. The new model is tested by comparing the estimated routing probability distribution with the actual routing results of a commercial detailed router. An iterative congestion map construction algorithm based on the new probabilistic model is proposed for accurate wirelength and congestion map estimation. The results show that our proposed methods can improve the total wirelength estimation accuracy (i.e., reduce estimation error) by 90% on average with respect to the traditional RSMT wirelength estimate. Our methods also produce more accurate congestion maps than the previous congestion estimation method of [5] without significant runtime overhead.

REFERENCES

• 1: M. Wang, X. Yang and M. Sarrafzadeh, "Congestion Minimization During Placement", IEEE Transactions on CAD, 19(10), 2000, pp. 1140--1148.
• 2: 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]
• 3: W. Huang and A. B. Kahng, "A Layout Advisor for Timing-Critical Bus Routing", Proc. Tenth Annual IEEE International ASIC Conf. and Exhibit, 1997, pp. 210--214.
• 4: Chih-Liang Eric Cheng, RISA: accurate and efficient placement routability modeling, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.690-695, November 06-10, 1994, San Jose, California, United States
• 5: 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]
• 6: Andrew E. Caldwell , Andrew B. Kahng , Stefanus Mantik , Igor L. Markov , Alex Zelikovsky, On wirelength estimations for row-based placement, Proceedings of the 1998 international symposium on Physical design, p.4-11, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274536]
• 7: Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing routability estimation methods for FPGAs, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513937]
• 8: http://nexus6.cs.ucla.edu/GSRC/bookshelf/Slots/Placement/Capo/.
• 9: Steven L. Teig, Challenges and principles of physical design, Proceedings of the 2002 international symposium on Physical design, p.3-4, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505389]
• 10: X. Yang, R. Kastner and M. Sarrafzadeh, "Congestion Estimation During Top-down Placement", IEEE Transactions on CAD, 21(1), 2002, pp. 72--80.
• 11: Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505391]
• 12: http://www.ssicentral.com/lisrel/column3.htm.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance