An exact algorithm for coupling-free routing

ABSTRACT

In this wrok, we develop methods to reduce interconnect delay and noise caused by coupling. First, we explain the Coupling-Free Routing (CFR) problem. CFR takes a set of nets and tries to find a one-bend couple-free routing for a subset of nets. A routed net must not couple with any other routed net. We define coupling as a boolean variable which is true when the coupling of two nets is greater than some threshold. Any pair-wise coupling definition can be used. We argue that this problem is useful in both global and detailed routingWe develop an exact algorithm for the CFR decision problem via a transformation to 2-satisfiability. This algorithm runs in linear time. The decision problem determines whether the given set of nets is coupling-free routable. Next, we present the implication graph which models the dependencies associated with CFR. Also, we look at some of the properties associated with the graph.Finally, we develop a new algorithm for the Maximum Coupling-Free Layout (MAX-CFL) problem. Given a set of nets, the MAX-CFL is defined as finding a subset of nets that are coupling-free routable. The subset should have maximum size and/or critically. The new algorithm, called implication algorithm, uses properties assoicated with the implication graph and experiments show that it consistently finds the best solution in terms of number of nets routed as compared to previous algorithms

REFERENCES

• 1: Andrew B. Kahng , Stefanus Mantik , Dirk Stroobandt, Requirements for models of achievable routing, Proceedings of the 2000 international symposium on Physical design, p.4-11, May 2000, San Diego, California, United States [doi>10.1145/332357.332364]
• 2: 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]
• 3: D. Sylvester et al. "Interconnect Scaling: Signal Integrity and Performance in Future High-speed CMOS Designs". In Proc. of VLSI Symposium on Technology, 1998.
• 4: J. Cong and D.Z. Pan. "Interconnect Delay Estimation Models for Synthesis and Design Planning". In Proc. Asia and South Pacific Design Automation Conference, January 1999.
• 5: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 6: Krzysztof Koźmiński, Benchmarks for layout synthesis—evolution and current status, Proceedings of the 28th conference on ACM/IEEE design automation, p.265-270, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127678]
• 7: K.F. Liao, M. Sarrafzadeh and C.K. Wong. "Single-Layer Global Routing". IEEE Transactions on Computer Aided Design, 1994.
• 8: 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
• 9: 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
• 10: R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh. "Coupling Aware Routing". In Proc. IEEE International ASIC/SOC Conference, September 2000.
• 11: S. Even, A. Itai and A. Shamir. "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal of Comp., 1976.
• 12: V. Vaishnavi and D. Wood. "Rectilinear Line Segment Intersection, Layered Segment Trees and Dynamization". Journal of Algorithms, July 1982.
• 13: Z.-M. Lin and Z.-W. Ro. "A Heuristic Planar Routing Algorithm for High Performance Single-Layer Layout". Manuscript, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance