An exact jumper insertion algorithm for antenna effect avoidance/fixing

ABSTRACT

As the process technology enters the nanometer era, reliability has become a major concern in the design and manufacturing of VLSI circuits. In this paper we focus on one reliability issue-jumper insertion in routing trees for avoiding/fixing antenna effect violations at the routing/post-layout stages. We formulate the jumper insertion for antenna avoidance/fixing as a tree-cutting problem. We show that the tree-cutting problem exhibits the properties of optimal substructures and greedy choices. With these properties, we present an O(V lg V)-time exact jumper insertion algorithm that uses the optimum number of jumpers to avoid/fix the antenna violations in a routing tree with V vertices. Experimental results show the superior effectiveness and efficiency of our algorithm.

REFERENCES

• 1: Peter H. Chen , Sunil Malkani , Chun-Mou Peng , James Lin, Fixing Antenna Problem by Dynamic Diode Dropping and Jumper Insertion, Proceedings of the 1st International Symposium on Quality of Electronic Design, p.275, March 20-22, 2000
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: Tsung-Yi Ho , Yao-Wen Chang , Sao-Jie Chen, Multilevel routing with antenna avoidance, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981074]
• 4: H. Shin, C. -C. King, and C. Hu, "Thin Oxide Damage by plasma etching and ashing process", Proc. IRPS, 1992.
• 5: H. Watanabe, et al., "A wafer level monitoring method for plasma-charging damage using antenna PMOSFET test structure," IEEE Trans. Semiconductor manufacturing, vol. 10, no. 2, May. 1997.

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
antenna effect, jumper insertion