Optimal river routing with crosstalk constraints

ABSTRACT

With the increasing density of VLSI circuits, the interconnection wires are being packed even closer. This has increased the effect of interaction among these wires on circuit performance and hence, the importance of controlling crosstalk. In this article, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of neighboring nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk when it is feasible.

REFERENCES

• 1: ANDERSON, R. AND SETUBAL, J. 1992. MAXFLOW. Available at ftp://dimacs.rutgers.edu in directory/pub/netflow/submit/setubal.
• 2: BAKOGLU, H.B. 1990. Circuits, Interconnections and Packaging for VLSI. Addison-Wesley, Reading, MA.
• 3: 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
• 4: CHEN, H. H. AND WONG, C.K. 1992. Wiring and crosstalk avoidance in multi-chip module design. In Proceedings of the Custom Integrated Circuits Conference (Boston, MA, May), 28.6.1-28.6.4.
• 5: Danny Dolev , Kevin Karplus , Alan Siegel , Alex Strong , Jeffrey D. Ullman, Optimal wiring between rectangles, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.312-317, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802484]
• 6: FORD, J. R. AND FULKERSON, D.R. 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
• 7: Tong Gao , C. L. Liu, Minimum crosstalk channel routing, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.692-696, November 07-11, 1993, Santa Clara, California, United States
• 8: 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
• 9: 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
• 10: Thomas Lengauer, Combinatorial algorithms for integrated circuit layout, John Wiley & Sons, Inc., New York, NY, 1990
• 11: Errol L. Lloyd , S S. Ravi, One-layer routing without component constraints, Journal of Computer and System Sciences, v.28 n.3, p.420-438, June 1984 [doi>10.1016/0022-0000(84)90022-9]
• 12: MIKAMI, K. AND TABUCHI, K. 1968. A computer program for optimal routing of printed circuit connectors. IFIPS Proc. H47, 1475-1478.
• 13: THAKUR, S., CHAO, K.-Y., AND WONG, D.F. 1995. An optimal layer assignment algorithm for minimizing crosstalk for three layer VHV channel routing. In Proceedings of the IEEE International Symposium on Circuits and Systems (Seattle, WA, Apr. 30-May 3), 207-210.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
crosstalk, river routing