Moment-driven coupling-aware routing methodology

ABSTRACT

An underdamped signal response with a number of overshoots and undershoots may lead to false switching and increased settling time delay. This 'ringing' effect adversely affects the signal quality at the output and becomes a source of major concern at multi-GHz frequencies, as the self and mutual inductance of interconnects start playing a crucial role in the performance of a circuit. Reduction in wire length or minimization of coupling capacitance, the stronghold in many earlier routing techniques, may produce a routing solution suitable only at sub-GHz frequencies. In this paper, we propose a routing methodology that accounts for inductive and capacitive parasitics (self and mutual) of the interconnects in its cost function through a combination of second and third order central moments. A trade-off between signal delay and amount of ringing, quantified by second and third order central moments respectively, has been made, which generates a routing solution with the best compromise between ringing and delay for each net under a monotone signal response.

REFERENCES

• 1: R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh. Coupling Aware Routing. In International ASIC/SOC Conference, pages 392--396, 2000.
• 2: Ryon M. Smey , Bill Swartz , Patrick H. Madden, Crosstalk Reduction in Area Routing, Proceedings of the conference on Design, Automation and Test in Europe, p.10862, March 03-07, 2003
• 3: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 4: Raia T. Hadsell , Patrick H. Madden, Improved global routing through congestion estimation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775842]
• 5: Jason Cong , Patrick H. Madden, Performance driven multi-layer general area routing for PCB/MCM designs, Proceedings of the 35th annual conference on Design automation, p.356-361, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277144]
• 6: 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]
• 7: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 8: S. Hur, A. Jagannathan and J. Lillis. Timing-Driven Maze Routing. In Tran. on Computer-Aided Design of Integrated Circuits and Systems, pages 234--241, 2000.
• 9: J. Hu and S. Sapatnekar. A Timing-Constrained Simultaneous Global Routing Algorithm. In Tran. on Computer-Aided Design of Integrated Circuits and Systems, pages 1025--1036, 2002.
• 10: J. Cong, C. Koh and P. Maddden. Interconnect Layout Optimization Under Higher Order RLC Model for MCM Designs. In Tran. on Computer-Aided Design of Integrated Circuits and Systems, pages 1455--1463, 2001.
• 11: R. Gupta, B. Krauter, L. T. Pileggi. Transmission Line Synthesis via Constrained Multivariable Optimization. In Tran. on Computer-Aided Design of Integrated Circuits and Systems, pages 6--19, 1997.
• 12: C. K. Cheng, J. Lillis, S. Lin and N. Chang. Interconnect Analysis and Synthesis. John Wiley & Sons, Inc, 2000.
• 13: H. B. Bakoglu. Circuits, Interconnections, and Packaging for VLSI. Addison-Wesley, 1990.
• 14: Stephen H. Hall , Garrett W. Hall , James A. McCall, High-Speed Digital System Design: A Handbook of Interconnect Theory and Design Practices, Wiley-IEEE Press, 2000
• 15: X. Qi et al. On-Chip Inductance Modeling and RLC Extraction of VLSI Interconnects for Circuit Simulation. In Custom Integrated Circuits Conference, pages 487--490, 2000.
• 16: Min Xu , Lei He, An efficient model for frequency-dependent on-chip inductance, Proceedings of the 11th Great Lakes symposium on VLSI, p.115-120, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368887]
• 17: M. Borah et al. An edge-based heuristic for Steiner routing. In Tran. on Computer-Aided Design of Integrated Circuits and Systems, pages 1563--1568, 1994.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms

Keywords:
coupling-aware, moments, routing