Steiner network construction for timing critical nets

ABSTRACT

Conventionally, signal net routing is almost always implemented asSteiner trees. However, non-tree topology is often superior on timing performance as well as tolerance to open faults and variations. These advantages are particularly appealing for timing critical net routings in nano-scale VLSI designs where interconnect delay is a performance bottleneck and variation effects are increasingly remarkable. We propose Steiner network construction heuristics which can generate either tree or non-tree with different slack-wirelength tradeoff, and handle both long path and short path constraints. Incremental non-tree delay update techniques are developed to facilitate fast Steiner network evaluations. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches.

REFERENCES

• 1: A. B. Kahng and G. Robins. On optimal interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.
• 2: Andrew B. Kahng , Bao Liu , Ion I. Mǎandoiu, Non-tree routing for reliability and yield improvement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.260-266, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774611]
• 3: B. A. McCoy and G. Robins. Non-tree routing. DATE,pages 430--434, 1994.
• 4: Tianxiong Xue , Ernest S. Kuh, Post routing performance optimization via tapered link insertion and wiresizing, Proceedings of the conference on European design automation, p.74-79, September 18-22, 1995, Brighton, England
• 5: 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]
• 6: W. Chuang, S. S. Sapatnekar, and IN. Hajj. Delay and area optimization for discrete gate sizes under double-sided timing constraints. CICC, pages 9.4.1--9.4.4, 1993.
• 7: P. K. Chan and K. Karplus. Computing signal delay in general RC networks by tree/link partitioning. TCAD, 9(8):898--902, August 1990.
• 8: W.-C. D. Lam , J. Jam , C.-K. Koh , V. Balakrishnan , Y. Chen, Statistical based link insertion for robust clock network design, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.588-591, November 06-10, 2005, San Jose, CA
• 9: R. Chaturvedi and J. Hu. An efficient merging scheme for prescribed skew clock routing. TVLSI, 13(6):750--754, June 2005.
• 10: S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor. The rectilinear Steiner arborescence problem. Algorithmica, 7:277--288, 1992.
• 11: G. H. Golub and C. F. Van Loan. Matrix computations. John Hopkins University Press, 1996.
• 12: Andrew B. Kahng , Bao Liu, Q-Tree: A New Iterative Improvement Approach for Buffered Interconnect Optimization, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.183, February 20-21, 2003

INDEX TERMS

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
Steiner network, interconnect, redundancy, routing