Timing analysis with crosstalk as fixpoints on complete lattice

ABSTRACT

Increasing delay variation due to crosstalk has a dramatic impact on deep sub-micron technologies. It is now necessary to include crosstalk in timing analysis. But timing analysis with crosstalk is a chicken-and-egg problem since crosstalk effect in turn depends on timing behavior of a circuit. In this paper, we establish a theoretical foundation for timing analysis with crosstalk. We show that solutions to the problem are fixpoints on a complete lattice. Base on that, we prove in general the convergence of any iterative approach. We also show that, starting from different initial solutions, an iterative approach will reach different fixpoints. The current prevailing practice, which starts from the worst case solution, will always reach the greatest fixpoint (which is the loosest solution). In order to reach the least fixpoint, we need to start from the best case solution. Base on chaotic iteration and heterogeneous structures of coupled circuits, we also design techniques to speed up iterations.

REFERENCES

• 1: 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]
• 2: Semiconductor Industry Association. National technology roadmap for semiconductors, 1997.
• 3: 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
• 4: 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
• 5: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 6: Florentin Dartu , Lawrence T. Pileggi, Calculating worst-case gate delays due to dominant capacitance coupling, Proceedings of the 34th annual conference on Design automation, p.46-51, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266033]
• 7: B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge, 1990.
• 8: M. R. Garey and D. S. Johnson. Computers and Intractability.W. H. Freeman and Co., 1979.
• 9: G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins, 3rd edition, 1996.
• 10: 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]
• 11: E. Lelarasmee, A. E. Ruehli, and A. L. Sangiovanni-Vincentelli. The waveform relaxation method for time-domain analysis of large scale integrated circuites and systems. IEEE Transactions on Computer Aided Design, July 1982.
• 12: S. S. Sapatnekar. A timing model incorporating the effect of crosstalk on delay and its application to optimal channel routing. IEEE Transactions on Computer Aided Design, 2000.
• 13: Y. Sasaki and G. De Micheli. Crosstalk delay analysis using relative window method. In ASIC/SoC Conference, 1999.
• 14: Y. Sasaki and K. Yano. Multi-aggressor relative window method for timing analysis including crosstalk delay degradation. In Custom Integrated Circuit Conference, pages 495-498, 2000.
• 15: 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

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

  J. Computer Applications

General Terms:
Design, Measurement, Performance, Theory