Optimal gate sizing for coupling-noise reduction

ABSTRACT

Coupling-noise reduction has emerged as a critical design problem with VLSI feature sizes shrinking rapidly and with the use of more aggressive and less noise-immune circuits. Since coupling-noise on a net depends on driving gate-sizes of the net itself and all nets coupled to it, gate-sizing emerges as an effective approach to coupling-noise reduction. It is an attractive approach since re-routing is not required. In this paper, we propose an iterative gate-sizing algorithm to determine optimal gate-sizes for coupling-noise reduction. We consider gate-sizing as a fixpoint computation on a complete lattice and the beauty of the iterative gate-sizing algorithm lies in its ability to guarantee the optimal solution, provided it exists. The effectiveness of the algorithm is validated experimentally by simulations on multiple large circuits.

REFERENCES

• 1: Semiconductor~Industry Association. National technology roadmap for semiconductors, 1997.
• 2: Murat R. Becer , David Blaauw , Ilan Algor , Rajendran Panda , Chanhee Oh , Vladimir Zolotov , Ibrahim N. Hajj, Post-route gate sizing for crosstalk noise reduction, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776071]
• 3: 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.
• 4: 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]
• 5: B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge, 1990.
• 6: David Gries , Fred B. Schneider, A logical approach to discrete math, Springer-Verlag New York, Inc., New York, NY, 1993
• 7: Masanori Hashimoto , Masao Takahashi , Hidetoshi Onodera, Crosstalk noise optimization by post-layout transistor sizing, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505420]
• 8: I. Lemke and G. Sander. Visualization of Compiler Graphs. In Design report, USAAR-1025-visual, ESPRIT Project 5399 Compare, Universität Saarlandes, FB 14 Informatik, pages D 3.12.1--1, 1993.
• 9: Gate Sizing to Eliminate Crosstalk Induced Timing Violation, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.186, September 23-26, 2001
• 10: H. Zhou. Timing analysis with crosstalk is a fixpoint on a complete lattice. In IEEE Transactions on Computer-Aided Design, September 2003, pages 1261--1269.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Algorithms

Keywords:
coupling-noise, fixpoint, gate-sizing, lattice theory