Fast hypergraph partition

ABSTRACT

We present a new &Ogr;(n2) heuristic for hypergraph min-cut bipartitioning, an important problem in circuit placement. Fastest previous methods for this problem are &Ogr;(n2 log n). Our approach is based on the intersection graph G dual to the input hypergraph. Paths in G are used to construct partial bipartitions which can be completed optimally. The method is provably good and, in particular, obtains optimum results for “difficult” inputs, i.e., hypergraphs with smaller than expected minimum cutsize. Computational results for a wide range of inputs are also discussed.

REFERENCES

• 1: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 2: Boltobas, B., Random Graphs, Academic Press, 1985.
• 3: Bollobas, B. and W. F. de la Vega, "Diameter of Random Regular Graphs", Combinatorica 2(4), 1982, pp. 125-134.
• 4: Breuer, M. A., "Min-Cut Placement", J. Design Automation and Fault Tolerant Computing 1(4), October 1977, pp. 343-36 2.
• 5: Thang Nguyen Bui , F. Thomson Leighton , Soma Chaudhuri , Michael Sipser, Graph bisection algorithms with good average case behavior, Combinatorica, v.7 n.2, p.171-191, June 1, 1987 [doi>10.1007/BF02579448]
• 6: H. W. Carter , M. A. Breuer , Z. A. Syed, Incremental processing applied to Steinberg's placement procedure, Proceedings of the 16th Conference on Design automation, p.26-31, June 25-27, 1979, San Diego, CA, United States
• 7: Chopra, S., "Hypergraph Partitioning and VLSI Circuits", Technical Report, NYU School of Bush~ess Administration, 1987.
• 8: A. E. Dunlop and B. W. Kemighan, "A Procedure for Placement of Standard-Cell VLSI Circuits", IEEE Trans. on CAD ICAS CAD-4(1 ), 1985.
• 9: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 10: Fredman, M., "New Bounds on the Complexity of the Shortest Path Problem", SlAM J. Cor~uting 5, March 1976, pp. 83-89.
• 11: Kunio Fukunaga , Shoichiro Yamada , Harold S. Stone , Tamotsu Kasai, Placement of circuit modules using a graph space approach, Proceedings of the 20th conference on Design automation, p.465-471, June 27-29, 1983, Miami Beach, Florida, United States
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: G. Hachtel, A. R. Newton and A. Sangiovanni- Vincentelli, "An Algorithm for Optima} PLA Folding", IEEE Trans. on CAD ICAS CAD-l(2) (1982), pp. 63-77.
• 14: Maurice Hanan , Peter K. Wolff, Sr. , Barbara J. Agule, Some experimental results on placement techniques, Proceedings of the 13th conference on Design automation, p.214-224, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804817]
• 15: Mark R. Hartoog, Analysis of placement procedures for VLSI standard cell layout, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.314-319, July 1986, Las Vegas, Nevada, United States
• 16: T.C. Hu and K. Moerder, "Multitermmal Flows in a Hypergraph", in VLS1 Circuit Layout.: Theory and Design, T.C. Hu and E.S. Kuh, Eds., IEEE Press, 1985, pp. 87-93.
• 17: Kernighan, B. W. and S. Lin, "An Efficient Procedure for Partitioning Graphs", Bell System Technical Journal 49(2), 1961, pp. 291-307.
• 18: Kirkpatrick, S., C.D. Gelatt, and M.P. Vecchi, "Optimization by Simulated Annealing", Science 220(4598), 13 May 1983, pp. 671-680.
• 19: Lawler, E., Combinatorial Optimization. Networks and Matroids, Holt, Rinehart & Winston, New York, 1976.
• 20: T. Leighton and S. Rao, "An Approxhrmte Max-Flow Min-Cut Theorem for Uniform Multicx)mmodity Flow Problems With Applications to Approximation Algorithms", Proc. IEEE Syrup. on Foundations of Computer Science, May 1988, pp. 422-431.
• 21: J. Schmidt-Pruzan and E. Shamir, "Component Structure in the Evolution of Random Hypergraphs", Combinatorica 5(1), 1985, pp. 81-94.
• 22: D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
• 23: Soukup, J. "Circuit Layout", Proc. of the IEEE 69(10), October 1981, pp. 1281-1304.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Algorithms, Design, Theory