Incorporating logic exclusivity (LE) constraints in noise analysis using gain guided backtracking method

ABSTRACT

Crosstalk noise becomes one of the critical issues gating design closure for nano-meter designs. Pessimism in noise analysis can lead to significant additional time spent addressing false violations. Taking logic correlation into consideration, noise analysis can reduce pessimism significantly by eliminating false noise signals [1]-[3][5]-[7][10]-[13]. Eliminating the aggressors from the aggressor candidate set that can not switch simultaneously restricted by the logic exclusivity (LE) relationship among them can save simulation time as well. The LE problem, being proved as NP-complete, is basically to determine the subset (possibly multiple equivalent subsets) of a given aggressor candidate set which has the largest combined weight out of all possible subsets governed by logic exclusivity constraints. This paper presents a new approach in resolving the LE problem, which employs a gain guided backtrack search technique that does not require exhaustive search of all the binary paths to reach an optimal solution. We first prove that under certain conditions, if the gain at each level is non-negative, then the result will be optimal. Based on this theorem, a new algorithm is developed. The experimental results demonstrate the efficiency and accuracy of this approach. The algorithm can quickly find the optimal solutions for most cases from industry designs and outperforms other methods.

REFERENCES

• 1: M. Becer , V. Zolotov , R. Panda , A. Grinshpon , I. Algol , R. Levy , C. Oh, Pessimism reduction in crosstalk noise aware STA, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.954-961, November 06-10, 2005, San Jose, CA
• 2: 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]
• 3: 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
• 4: CPLEX. http://www.ilog.com/products/cplex. ILOG.
• 5: Alexey Glebov , Sergey Gavrilov , David Blaauw , Supamas Sirichotiyakul , Chanhee Oh , Vladimir Zolotov, False-noise analysis using logic implications, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 6: False-Noise Analysis using Resolution Method, Proceedings of the 3rd International Symposium on Quality Electronic Design, p.437, March 18-21, 2002
• 7: 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]
• 8: E. Lawler and D. Wood. Branch-and-bound methods: A survey. Operations Research, 14:699--719, 1966.
• 9: R. E. Moore. Global optimization to prescribed accuracy. Computers and Mathematics with Applications, 21(6/7):25--39, 1991.
• 10: M. Palla, J. Bargfrede, K. Koch, W. Anheier, and R. Drechsler. False noise analysis using branch & bound and sat. In TAU Proceedings, pages 32--37, 2008.
• 11: M. Palla, K. Koch, J. Bargfrede, M. Glesner, and W. Anheier. Reduction of crosstalk pessimism using tendency graph approach. In ICCD Conference Proceedings, pages 50--55, 2006.
• 12: D. Sinha, S. Abbaspour, G, and Schaeffer. Constrained aggressor set selection for maximum coupling noise. In TAU Proceedings, pages 38--43, 2008.
• 13: K. Tseng and M. Horowitz. False coupling exploration in timing analysis. Tran. CAD, 24(11):1795--1805, November 2005.
• 14: Lintao Zhang , Conor F. Madigan , Matthew H. Moskewicz , Sharad Malik, Efficient conflict driven learning in a boolean satisfiability solver, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California