Probabilistic congestion model considering shielding for crosstalk reduction

ABSTRACT

We extend an existing probabilistic congestion model to consider shielding for crosstalk reduction. We then develop a multilevel router to study the impact of various congestion models on routing congestion by using large industrial design examples. We show that (1) when shielding is applied as a post-routing optimization for crosstalk reduction, the existing probabilistic model, when compared to a deterministic routing-order dependent congestion model, reduces routing congestion by 17.1% on average under the given routing area constraints, or reduces routing area by 9.4% on average under the given routing congestion constraints; (2) our extended probabilistic congestion model considering shielding enables shielding reservation and minimization for routing and achieves routing congestion (or area) reduction by 47.7% (or 31.0%) on average under the given routing area (or congestion) constraints, when compared to the above deterministic congestion model not able to estimate shielding and therefore not able to minimize shielding during routing.

REFERENCES

• 1: Shih-Ping Lin , Yao-Wen Chang, A novel framework for multilevel routing considering routability and performance, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.44-50, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774579]
• 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: 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]
• 4: U. Brenner and A. Rohe, "An effective congestion-driven placement framework," in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, pp. 387--394, April 2003.
• 5: Yi-Lin Hsieh , Tsai-Ming Hsieh, A New Effective Congestion Model in Floorplan Design, Proceedings of the conference on Design, automation and test in Europe, p.21204, February 16-20, 2004
• 6: P. Saxena and S. Gupta, "On integrating power and signal routing for shield count minimization in congested regions," TCAD, April 2003.
• 7: B. Chappell , J. Vendrell, A System-Level Solution to Domino Synthesis with 2 GHz Application, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.164, September 16-18, 2002
• 8: 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]
• 9: Haihua Su , Jiang Hu , Sachin S. Sapatnekar , Sani R. Nassif, Congestion-driven codesign of power and signal networks, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513936]
• 10: M. Aigner, Combinatorial Theory. Springer-Verlag, 1997.
• 11: Jason Cong , Jie Fang , Yan Zhang, Multilevel approach to full-chip gridless routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 12: Jason Cong , Min Xie , Yan Zhang, An enhanced multilevel routing system, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.51-58, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774580]