Algorithms for routing and testing routability of planar VLSI layouts

ABSTRACT

This paper studies the problem of routing wires in a grid among features on one layer of a VLSI chip, when a sketch of the layer is given. A sketch specifies the positions of features and the topology of the interconnecting wires. We give polynomial-time algorithms that (1) determine the routability of a sketch, and (2) produce a routing of a sketch that optimizes both individual and total wire length. These algorithms subsume most of the polynomial-time algorithms in the literature for planar routing and routability testing in the rectilinear grid model. We also provide an explicit construction of a database, called the rubber-band equivalent, to support computation involving the layout topology.

REFERENCES

• 1: B. $. Baker and R. Y. Pinter, "An algorithm for the optimal placement and routing of a circuit within a ring of pads,," Proceedingz ol the ~4th Annual $~lmpoeium on Foundations of Computer Science (November 1983), pp. 360-370.
• 2: R. Coh: and A. Siegel, "River routing every which way, but loose," Procecding~ of the 25th Annua! Symposium on Foundations of Computer Science (October 1984), pp. 65-73.
• 3: 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]
• 4: M. R. Gaze), and D. S. Johnson, Computers and Intractability, Preeman (1979).
• 5: M. R. Kramer and J. van Leeuwen, "Wire-routing is NP- complete ," Technical Report RUU-CS-82-4, Department of Computer Science, University of Utrecht, the Netherlands (February 1982).
• 6: C.E. Leiserson and R. Y. Pinter, "Optimal placement for river routing," SlAM Journal on Computing, Vol. 12, No. 3 (August 1983), pp. 447-462.
• 7: F. M. Maley, "Compaction with automatic jog introduction," to appear in 1985 Chapel Hill Conference on VLSI (May 1985).
• 8: R.Y. Pinter, The Impact of Layer Assignmer~t Meth. odz on Layout Algorithms/or Ir~tegrated Circuits, Ph.D. Thesis, MIT Department of Electrical Engineering and Computer Science (August 1982).
• 9: D. Richards, "Complexity of single-layer routing," IEEE 7~ansactions on Computers, Vol. C-33, No. 3 (March 1984), pp. 286-288.
• 10: A. Siegel and D. Dolev, "The separation for general single-layer wiring barriers," Proceedings o! the Carnegie-Mellon Conference on VLSI Systems and Oomputations (October 1981), pp. 143-152.
• 11: T. Szymanski, "Dogleg channel routing is NP-comphte," unpublished manuscript (September 1981).
• 12: M. Tompa, "An optimal solution to a wire-routing probhm,' Journal of Computer and Sllstem Sciem:es, Vol. 23, No. 2 (October 1981), pp. 127-150.

INDEX TERMS

Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Theory, Verification