Timing and crosstalk driven area routing

ABSTRACT

We present a timing and crosstalk driven router for the chip assembly task that is applied between global and detailed routing. Our new approach aims to process the crosstalk and timing constraints by ordering nets and tuning wire spacing in a quantitative way. Our graph-based optimizer preroutes wires on the global routing grids incrementally in two stages - net order assignment and space relaxation. The timing delay of each critical path is calculated taking into account interconnect coupling capacitance. The objective is to reduce the delays of critical nets with negative timing slack values, by tuning net ordering and adding extra wire spacing. It shows a remarkable 8.4-25% delay reduction for MCNC benchmarks for wire geometric ratio=2.0, against a 33% delay reduction if interconnect interference disappear.

REFERENCES

• 1: Hai Zhou , D. F. Wong, An optimal algorithm for river routing with crosstalk constraints, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.310-315, November 10-14, 1996, San Jose, California, United States
• 2: K, Jhang, S. Ha, and C. S. Jhon, "COP: A Crosstalk Optimizer for Gridded Channel Routing," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 424-9, Vol. 15, N.5, April 1996.
• 3: Tong Gao , C. L. Liu, Minimum crosstalk switchbox routing, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.610-615, November 06-10, 1994, San Jose, California, United States
• 4: Tianxiong Xue , Ernest S. Kuh , Dongsheng Wang, Post global routing crosstalk risk estimation and reduction, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.302-309, November 10-14, 1996, San Jose, California, United States
• 5: Kamal Chaudhary , Akira Onozawa , Ernest S. Kuh, A spacing algorithm for performance enhancement and cross-talk reduction, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.697-702, November 07-11, 1993, Santa Clara, California, United States
• 6: W.C. Kao and T.M. Parng, "Cross Point Assignment with Global Rerouting for General-Architecture Designs,"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 337-348, Vol. 14, No. 3, March 1995.
• 7: Desmond A. Kirkpatrick , Alberto L. Sangiovanni-Vincentelli, Digital sensitivity: predicting signal interaction using functional analysis, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.536-541, November 10-14, 1996, San Jose, California, United States
• 8: W. Swartz and C. Sechen, "New Alogrithms for the Placement and Routing of Macro Cells," Digest of Technical Papers of 1990 IEEE/ACM International Conference on Computer-Aided Design, pp. 336-9,1990
• 9: Le-Chin Eugene Liu , C. Sechen, Multi-layer chip-level global routing using an efficient graph-based Steiner tree heuristic, Proceedings of the 1997 European conference on Design and Test, p.311, March 17-20, 1997
• 10: Hsiao-Ping Tseng , Carl M. Sechen, Detailed routing algorithms for vlsi circuits, 1997

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
fanout optimization, gate-sizing, logic synthesis