Optimal jumper insertion for antenna avoidance under ratio upper-bound

ABSTRACT

Antenna effect may damage gate oxides during plasma-based fabrication process. The antenna ratio of total exposed antenna area to total gate oxide area is directly related to the amount of damage. Jumper insertion is a common technique applied at routing and post-layout stages to avoid and to fix the problems caused by the antenna effect. This paper presents an optimal algorithm for jumper insertion under the ratio upper-bound. It handles Steiner trees with obstacles. The algorithm is based on dynamic programming while works on free trees. The time complexity is O(α|V|²) and the space complexity is O(|V|²), where |V| is the number of nodes in the routing tree and α is a factor depending on how to find a non-blocked position on a wire for a jumper.

REFERENCES

• 1: Design Automation for Deepsubmicron: Present and Future, Proceedings of the conference on Design, automation and test in Europe, p.650, March 04-08, 2002
• 2: Hardy Kwok-Shing Leung, Advanced routing in changing technology landscape, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640027]
• 3: H C Shin and C. Hu. Thin Gate Oxide Damage Due to Plasma Processing. Semicond. Sci. Technol., vol. 11, pages 463--473, 1996.
• 4: R. Rakkhit, F. P. Heiler, P. Fang, and C. Sander. Process Induced Oxide Damage and Its Implications to Device Reliability of Submicron Transistors. In IEEE 38th Annu. Int. Reliability Phys. Symp., pages 293--296, 1993.
• 5: H. Watanabe, J. Komori, K. Higashitani, M. Sekine, and H. Koyama. A Wafer Level Monitoring Method for Plasma-Charging Damage Using Antenna PMOSFET Test Structure. IEEE Trans. Semiconductor Manufacturing, vol. 10, no. 2, pages 228--232, May 1997.
• 6: Process-Induced Damage Rules (otherwise known as "Antenna Rules") - General Requirements. http://www.mosis.org/Technical/Designrules/guidelines.html#antenna
• 7: H. Shirota, T. Sadakane, M. Terai, and K. Okazaki. A New Router for Reducing "Antenna Effect" in ASIC Design. In IEEE Custom Integrated Circuits Conf., pages 601--604, 1998.
• 8: 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
• 9: L. Huang, X. Tang, H. Xiang, D. Wong, and I. Liu. A Polynomial Time Optimal Diode Insertion/Routing Algorithm for Fixing Antenna Problem. IEEE Trans. Computer-Aided Design, vol. 23, no. 1, pages 141--147, Jan 2004.
• 10: 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]
• 11: Di Wu , Jiang Hu , Rabi Mahapatra, Coupling aware timing optimization and antenna avoidance in layer assignment, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055144]
• 12: Bor-Yiing Su , Yao-Wen Chang, An exact jumper insertion algorithm for antenna effect avoidance/fixing, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065664]
• 13: Bor-Yiing Su , Yao-Wen Chang , Jiang Hu, An optimal jumper insertion algorithm for antenna avoidance/fixing on general routing trees with obstacles, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123021]
• 14: H. Zhou. Efficient Steiner Tree Construction Based on Spanning Graphs. IEEE Trans. Computer-Aided Design, vol. 23, no. 5, pages 704--710, May 2004.
• 15: Larry Stockmeyer, Optimal orientations of cells in slicing floorplan designs, Information and Control, v.57 n.2-3, p.91-101, May/June 1983 [doi>10.1016/S0019-9958(83)80038-2]
• 16: L. P.P.P. van Ginneken. Buffer Placement in Distributed RC-tree Network for Minimal Elmore Delay. In Proc. IEEE Int. Symp. Circuits Syst., pages 865--868, 1990.
• 17: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001

INDEX TERMS

General Terms:
Algorithms

Keywords:
antenna effect, jumper insertion