Coupling aware timing optimization and antenna avoidance in layer assignment

ABSTRACT

The sustained progress of VLSI technology has altered the landscape of routing which is a major physical design stage. For timing driven routings, traditional approaches which consider only wire self capacitance become inadequate since the wire delay is affected more by coupling capacitance in ultra-deep submicron designs. Furthermore, the technology scaling dramatically increases the likelihood of the antenna problem in manufacturing and requests corresponding considerations in the routing stage. In this paper, we propose techniques that can be applied to handle the coupling aware timing and the antenna problem simultaneously during layer assignment which is an important step between global routing and detailed routing. An improved probabilistic coupling capacitance model is suggested for coupling aware timing optimization without performing track assignment. The antenna avoidance problem is modeled as a tree partitioning problem with a linear time optimal algorithm solution. This algorithm is customized to guide antenna avoidance in layer assignment. A linear time optimal jumper insertion algorithm is also derived. Experimental results on benchmark circuits show that the proposed techniques can lead to an average of 270ps timing slack improvement validated by track assignment, 76% antenna violation reduction and 99% via violation reduction.

REFERENCES

• 1: ITRS. Semiconductor Industry Association, 2003.
• 2: Charles Alpert , Andrew B. Kahng , Bao Liu , Ion Măndoiu , Alexander Zelikovsky, Minimum-buffered routing of non-critical nets for slew rate and reliability control, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 3: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 4: Shabbir Batterywala , Narendra Shenoy , William Nicholls , Hai Zhou, Track assignment: a desirable intermediate step between global routing and detailed routing, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.59-66, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774581]
• 5: Murat R Becer , David Blaauw , Ibrahim N. Hajj , Rajendran Panda, Early probabilistic noise estimation for capacitively coupled interconnects, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505365]
• 6: K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins. Near-optimal critical sink routing tree constructions. IEEE Tran. on CAD, 14(12):1417--1436, Dec. 1995.
• 7: C.-C. Chang and J. Cong. An efficient approach to multilayer layer assignment with an application to via minimization. IEEE Tran. on CAD, 18(5):608--620, May. 1999.
• 8: C.-C. Chang and J. Cong. Pseudopin assignment with crosstalk noise control. IEEE Tran. on CAD, 20(5):598--611, May. 2001.
• 9: 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
• 10: Zhan Chen , Israel Koren, Layer Reassignment for Antenna Effect Minimization in 3-Layer Channel Routing, Proceedings of the 1996 Workshop on Defect and Fault-Tolerance in VLSI Systems, p.77, November 06-08, 1996
• 11: J. Cong, L. He, C.-K. Koh, and Z. Pan. Interconnect sizing and spacing with consideration of coupling capacitance. IEEE Tran. on CAD, 20(9):1164--1169, Sep. 2001.
• 12: T. Gao and C. L. Liu. Minimum crosstalk channel routing. IEEE Tran. on CAD, 15(5):465--474, May. 1996.
• 13: 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]
• 14: Tsung-Yi Ho , Yao-Wen Chang , Sao-Jie Chen , D. T. Lee, A Fast Crosstalk- and Performance-Driven Multilevel Routing System, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.382, November 09-13, 2003 [doi>10.1109/ICCAD.2003.3]
• 15: J. Hu and S. S. Sapatnekar. A timing-constrained simultaneous global routing algorithm. IEEE Tran. on CAD, 21(9):1025--1036, Sep. 2002.
• 16: L.-D. Huang, X. Tang, H. Xiang, D. Wong, and I.-M. Liu;. A polynomial time-optimal diode insertion/routing algorithm for fixing antenna problem. IEEE Tran. on CAD, 23(1):141--147, Jan. 2004.
• 17: R. Kay , R. A. Rutenbar, Wire packing: a strong formulation of crosswalk-aware chip-level track/layer assignment with an efficient integer programming solution, Proceedings of the 2000 international conference on Computer-aided design, p.61-68, March 2001, Minnesota, United States
• 18: Desmond A. Kirkpatrick , Alberto L. Sangiovanni-Vincentelli, Techniques for crosstalk avoidance in the physical design of high-performance digital systems, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.616-619, November 06-10, 1994, San Jose, California, United States
• 19: S. Kundu and J. Misra. A linear tree partitioning algorithm. SIAM J. of Computing, 6(1):151--154, Mar. 1977.
• 20: R. Nair. A simple yet effective technique for global wiring. IEEE Tran. on CAD, 6(2):165--172, Mar. 1987.
• 21: P. Saxena and S. Gupta. On integrating power and signal routing for shield count minimization in congested regions. IEEE Tran. on CAD, 22(4):437--445, Apr. 2003.
• 22: H. Shirota, T. Sadakane, M. Terai, and K. Okazaki. A new router for reducing antenna effect in asic design. Proc. of CICC, pages 601--604, 1998.
• 23: S. Thakur, K.-Y. Chao, and D. F. Wong. An optimal layer assignment algorithm for minimizing crosstalk for three layer VHV channel routing. Proc. of ISCAS, 1:207--210, 1995.
• 24: H.-P. Tseng, L. Sheffer, and C. Sechen. Timing- and crosstalk- driven area routing. IEEE Tran. on CAD, 20(4):528--544, Apr. 2001.
• 25: A. Vittal and M. Marek-Sadowska. Crosstalk reduction for VLSI. IEEE Tran. on CAD, 16(3):290--298, Mar. 1997.
• 26: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 27: Di Wu , Jiang Hu , Rabi Mahapatra , Min Zhao, Layer assignment for crosstalk risk minimization, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.159-162, January 27-30, 2004, Yokohama, Japan
• 28: Di Wu , Jiang Hu , Min Zhao , Rabi Mahapatra, Timing driven track routing considering coupling capacitance, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120929]
• 29: Jingyu Xu , Xianlong Hong , Tong Jing , Yici Cai , Jun Gu, A novel timing-driven global routing algorithm considering coupling effects for high performance circuit design, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119958]
• 30: T. Xue, E. S. Kuh, and D. Wang. Post global routing crosstalk synthesis. IEEE Tran. on CAD, 16(12):1418--1430, Dec. 1997.
• 31: H. Zhou and D. F. Wong. Global routing with crosstalk constraints. IEEE Tran. on CAD, 18(11):1683--1688, Nov. 1999.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

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

General Terms:
Algorithms, Design, Performance

Keywords:
VLSI, antenna effect, crosstalk, design for manufacturability (DFM), interconnect, physical design, probabilistic modeling