Provably good routing in graphs: regular arrays

ABSTRACT

We examine the problem of routing wires on a VLSI chip where the nodes to be connected are arranged in a two-dimensional array. We develop provably good algorithms that find a solution close to the optimal one with high probability. Our approximation algorithms solve the relevant 0-1 integer optimization problems by solving their relaxed versions and then rounding by an interesting probabilistic technique. One of our algorithms, using multicommodity flow, has applications to routing in circuit switching networks.

REFERENCES

• 1: Michul Burstein ted Rkhard Pelnvin, "Hierarchical Wire Routins," IE~E 7~anead ions on Computer.Aided Design, vol. GAD-2, no. 4, pp. 223-234, October 1983.
• 2: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• 3: S. Even, A. It&i, and A. Sbamir, "On the complexity of timetable and multicommodity flow problems," SIAM Journal on Computing, vol. 5, no. 4, pp. (}91-703, Dec. 1976.
• 4: Micba~l Feuer, "Connectivity of Random Loiic," IEEE 7~~nsoctione on Computers, vol. C-31, no. 1, pp. 29-33, Jaoua:r 1082.
• 5: Abbas El Gamal, "Two-d~e~ion~ stochastic model for intereonnections in muter*slice integrated circuits," {EEE TrGna. Circ~itt Grid $11stema, vol. CAS-28, pp. 127-137, Feb 81. '
• 6: RM. Karp, "Reducibility smonf; combinatorial problems," in ~ompl~it~ of Computer Computatione, ed. R.N. Miller, J.W. Thatcher, pp. 85-104, Plenum Press, New York, 1072.
• 7: R.M. K&rp, F. T. Leishton, 'R. L. Rivest, C. D. Thompson, U. Vuirsmi, sad V. Vuirui, "Global Wire Routing ia Two-gimensionsd Arrays,"/~oc. P.~A AnnloJ $~np. on Fosndations of Computer $dence, pp. 4L3-459, October 1983.
• 8: Frank Thomson Leishton and Arnold L. Rosenberlt, "Three-Dimensional Circuit Layouts," Tecbnksd Report TR84-08, M~roelectronic, Center of North Cnrolins, March 1984.
• 9: C~. Lebenon und F.M. Maley, '~toutins and Teeth; Routsbility in Planar VLSI Layouts," Proc. Seventeenth Annual ACM Sjmposium on TAcky of Computing, May 1985.
• 10: K. Mehlhorn and F=P. Preparats, "Routins Tbrousb A Rectangle," TR A 83/12, Uuiversitat des Ssmrlandes, West Germany, July 1983.
• 11: A. Rtnyi, "Probability Theory," Norfh-HoUand Seri~ in Applied MGthcmGticJ and Mechanict, vol. 10, North-Holland Publisbinlt Company, Amsterdsdn, 1070.
• 12: Prabh,~ur Rtqthavsm and Clark D. Thompson, 'Ttandomized Routinft in Gate. Arrays," CSD/84/202, Computer Science Division, UC Berkeley, Sep. 1084.
• 13: Clark David Thompson, A complexity theory for vlsi, 1980
• 14: M. Tompa, "An optimal solution to a wir~routins probkm," Journal of Computtr and $1etem $dmce, a, vol. 23, pp. 127-150, 1081.

INDEX TERMS

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

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Circuit-switching networks

General Terms:
Algorithms, Theory, Verification