On convergence of switching windows computation in presence of crosstalk noise

ABSTRACT

Detecting overlapping of switching windows between coupling nets is a major static technique to accurately locate crosstalk noise. However, due to the mutual dependency between switching windows, the computation requires iterations to converge. In this paper, we discuss the issues and provide answers to the important questions involved in convergence and numerical properties, including the effect of coupling models, multiple convergence points, convergence rate, computational complexity, non-monotonicity, continuity and the effectiveness of bounds. Numerical fixed point computation results are used to explain these properties. Our contribution here builds a theoretical foundation for static crosstalk noise analysis.

REFERENCES

• 1: Rafi Levy , David Blaauw , Gabi Braca , Aurobindo Dasgupta , Amir Grinshpon , Chanlee Oh , Boaz Orshav , Supamas Sirichotiyakul , Vladimir Zolotov, ClariNet: a noise analysis tool for deep submicron design, Proceedings of the 37th conference on Design automation, p.233-238, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337400]
• 2: R. Kumar. "Interconnect and Noise Immunity Design for Pentium 4 Processor". In Intel Reports downloaded from http://developer.intel.com.
• 3: S. S. Sapatnekar. "On the Chicken-and-Egg Problem of Determining the Effect of Crosstalk on Delay in Integrated Circuits". In Proc. IEEE of 8th Topical Meeting on Electrical Performance of Eletronic Package, pp. 245--248, 1999.
• 4: B. Franzini , C. Forzan , D. Pandini , P. Scandolara , A. Dal Fabbro, Crosstalk Aware Static Timing Analysis: A Two Step Approach, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.499, March 20-22, 2000
• 5: Peivand F. Tehrani , Shang Woo Chyou , Uma Ekambaram, Deep Sub-Micron Static Timing Analysis in Presence of Crosstalk, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.505, March 20-22, 2000
• 6: Ravishankar Arunachalam , Karthik Rajagopal , Lawrence T. Pileggi, TACO: timing analysis with coupling, Proceedings of the 37th conference on Design automation, p.266-269, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337415]
• 7: Pinhong Chen , Desmond A. Kirkpatrick , Kurt Keutzer, Switching window computation for static timing analysis in presence of crosstalk noise, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 8: T. Xiao, et al. "Efficient static timing analysis in presence of crosstalk". In Proc. of IEEE International ASIC/SOC Conference, pp. 335--339, 2000.
• 9: Hai Zhou , Narendra Shenoy , William Nicholls, Timing analysis with crosstalk as fixpoints on complete lattice, Proceedings of the 38th conference on Design automation, p.714-719, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379053]
• 10: Gisela Engeln-Müllges , Frank Uhlig, Numerical algorithms with C, Springer-Verlag New York, Inc., New York, NY, 1996
• 11: Paul D. Gross , Ravishankar Arunachalam , Karthik Rajagopal , Lawrence T. Pileggi, Determination of worst-case aggressor alignment for delay calculation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.212-219, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288616]
• 12: S. S. Sapatnekar. "A timing model incorporating the effect of crosstalk on delay and its application to optimal channel routing". IEEE Trans. on Computer-Aided Design, Vol.19:pp.550--559, May 2000.
• 13: Andrew B. Kahng , Sudhakar Muddu , Egino Sarto, On switch factor based analysis of coupled RC interconnects, Proceedings of the 37th conference on Design automation, p.79-84, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337318]
• 14: 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
• 15: K. L. Shepard , V. Narayanan , P. C. Elmendorf , Gutuan Zheng, Global harmony: coupled noise analysis for full-chip RC interconnect networks, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.139-146, November 09-13, 1997, San Jose, California, United States
• 16: Worst Delay Estimation in Crosstalk Aware Static Timing Analysis, Proceedings of the 2000 IEEE International Conference on Computer Design: VLSI in Computers & Processors, p.115, September 17-20, 2000
• 17: L. H. Chen and M. Marek-Sadowska. "Aggressor Alignment for Worst-Case Crosstalk Noise". IEEE Trans. on Computer-Aided Design, Vol.20:pp.612--621, May 2001.
• 18: S. Devadas, et al. "Computation of floating mode delay in combinational networks: Theory and algorithms". IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol.12:pp.1913--1923, Dec. 1993.

INDEX TERMS

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

General Terms:
Algorithms, Theory, Verification