Constrained aggressor set selection for maximum coupling noise

ABSTRACT

In this paper, we consider the problem of selecting a set of aggressor nets that maximize crosstalk induced noise or delay pushout on a coupled victim net, under given logical constraints. We formulate the problem mathematically, and propose efficient Lagrangian Relaxation and network flow based approaches that guarantee an optimal solution. We also formulate and solve this problem while considering the noise susceptibility of the victim's receiving gate. Experimental results show that the proposed approaches are run-time efficient by factors of up to 800X in comparison to an exhaustive search approach, and reduce timing pessimism by up to 36%.

REFERENCES

• 1: Kenneth L. Shepard, Design methodologies for noise in digital integrated circuits, Proceedings of the 35th annual conference on Design automation, p.94-99, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277062]
• 2: Pinhong Chen , Kurt Keutzer, Towards true crosstalk noise analysis, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.132-138, November 07-11, 1999, San Jose, California, United States
• 3: Tong Xiao , Malgorzata Marek-Sadowska, Functional correlation analysis in crosstalk induced critical paths identification, Proceedings of the 38th conference on Design automation, p.653-656, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379041]
• 4: Donald Chai , Alex Kondratyev , Yajun Ran , Kenneth H. Tseng , Yosinori Watanabe , Malgorzata Marek-Sadowska, Temporofunctional crosstalk noise analysis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776048]
• 5: A. Glebov , S. Gavrilov , R. Soloviev , V. Zolotov , M. R. Becer , C. Oh , R. Panda, Delay noise pessimism reduction by logic correlations, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.160-167, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382564]
• 6: K. Tseng and M. Horowitz, "False coupling exploration in timing analysis," in IEEE Transactions on Computer-Aided Design, vol. 24, no. 11, 2005, pp. 1795--1805.
• 7: Kunal P. Ganeshpure , Sandip Kundu, Interactive presentation: Automatic test pattern generation for maximal circuit noise in multiple aggressor crosstalk faults, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 8: Pinhong Chen , Desmond A. Kirkpatrick , Kurt Keutzer, Miller factor for gate-level coupling delay calculation, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 9: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 10: C. Chen, C. Chu, and D. F. Wong, "Fast and exact simultaneous gate and wire sizing by Lagrangian Relaxation," in IEEE Transactions on Computer-Aided Design, July 1999, 1999, pp. 1014--1025.
• 11: A. Korshak, "Noise-rejection model based on charge-transfer equation for digital CMOS circuits," in IEEE Transactions on Computer-Aided Design, vol. 23, no. 10, 2004, pp. 1460--1465.
• 12: A. Kasnavi , J. W. Wang , M. Shahram , J. Zejda, Analytical modeling of crosstalk noise waveforms using Weibull function, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.141-146, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382561]
• 13: J. Cong, D. Z. Pang, and P. V. Srinivas, "Improved crosstalk modeling for noise constrained interconnect optimization," in ACM Intl. Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, 2000.