Optimal wiring between rectangles

ABSTRACT

We consider the problem of wiring together two parallel rows of points under a variety of conditions. The options include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. In almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. We also compare two fundamentally different wiring approaches, where one and two layers are used. We show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out VLSI circuits there is no substantial advantage to the two-layer approach over the one-layer approach.

REFERENCES

• 1: Dolev, D. and A. Siegel, report in preparation.
• 2: Michael J. Fischer , Michael S. Paterson, Optimal tree layout (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.177-189, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804665]
• 3: Dave Johannsen, Bristle Blocks: A silicon compiler, Proceedings of the 16th Conference on Design automation, p.310-313, June 25-27, 1979, San Diego, CA, United States
• 4: LaPaugh, A. S, "A polynomial time algorithm for optimal routing around a rectangle," Proc. Twenty-first Annual IEEE Symposium on Foundations of Computer Science, pp. 282-293, 1980.
• 5: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 6: Shamos, M. I., "Geometry and statistics: problems at the interface," in Algorithms and Complexity, J. F. Traub, ed., Academic Press, 1976.
• 7: James A. Storer, The node cost measure for embedding graphs on the planar grid (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.201-210, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804667]
• 8: Martin Tompa, An optimal solution to a wire-routing problem (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.161-176, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804664]
• 9: Valiant, L., "Universality considerations in VLSI circuits," CSR-54-80, Dept. of CS, Univ. of Edinburgh, 1980.

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:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Design, Performance