Post-route gate sizing for crosstalk noise reduction

ABSTRACT

Gate sizing is a practical and a feasible crosstalk noise repair technique in the post route design stage, especially for block level sea-of-gates designs. The difficulty in gate sizing for noise reduction is that by increasing a driver size, noise at the driver output is reduced, but noise injected by that driver on other nets is increased. This can create cyclical dependencies between nets in the circuit with noise violations. In this paper, we propose a fast and effective heuristic post-route gate sizing algorithm that uses a graph representation of the noise dependencies between nodes. Our method utilizes gate sizing in both directions and works in linear time as a function of the number of gates. The effectiveness of the algorithm is shown on several industrial high performance designs.

REFERENCES

• 1: Prashant Saxena , C. L. Liu, Crosstalk minimization using wire perturbations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.100-103, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309887]
• 2: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277145]
• 3: 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
• 4: 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]
• 5: 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]
• 6: Guy Even , Joseph Naor , Baruch Schieber , Madhu Sudan, Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs, Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.14-28, May 29-31, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms

Keywords:
crosstalk noise repair, gate sizing