A multilevel algorithm for partitioning graphs

ABSTRACT

The graph partitioning problem is that of dividing the vertices of a graph into sets of specified sizes such that few edges cross between sets. This NP-complete problem arises in many important scientific and engineering problems. Prominent examples include the decomposition of data structures for parallel computation, the placement of circuit elements and the ordering of sparse matrix computations. We present a multilevel algorithm for graph partitioning in which the graph is approximated by a sequence of increasingly smaller graphs. The smallest graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs. A variant of the Kernighan-Lin algorithm is applied periodically to refine the partition. The entire algorithm can be implemented to execute in time proportional to the size of the original graph. Experiments indicate that, relative to other advanced methods, the multilevel algorithm produces high quality partitions at low cost.

REFERENCES

• 1: S. T. BARNARD AND H. D. SIMON, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1993, pp. 711-718.
• 2: T. BUI AND C. JONES, A heuristic for reducing fill in sparse matrix factorization, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1993, pp. 445-452.
• 3: P. DINIZ, S. PLIMPTON, B. HENDRICKSON, AND R. LELAND, Parallel algorithms for dynamically partitioning unstructured grids, in Proc. 7th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, 1995, pp. 615-620.
• 4: A. E. DUNLOP AND B. W. KERNIGHAN, A procedure for placement of standard-cell VLSI circuits, IEEE Trans. CAD, CAD-4 (1985), pp. 92-98.
• 5: 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
• 6: M. GAREY, D. JOHNSON, AND L. STOCKMEYER, Some simplified NP-complete graph problems, Theoretical Computer Science, 1 (1976), pp. 237-267.
• 7: John R. Gilbert , Earl Zmijewski, A parallel graph partitioning algorithm for a message-passing multiprocessor, International Journal of Parallel Programming, v.16 n.6, p.427-449, December 1987 [doi>10.1007/BF01388998]
• 8: S. HAMMOND. Personal Communication, November 1992. Available through anonymous ftp at riacs.edu, file /pub/grids/3elt.grid.
• 9: Steven Warren Hammond, Mapping unstructured grid computations to massively parallel computers, Rensselaer Polytechnic Institute, Troy, NY, 1992
• 10: B. HENDRICKSON AND R. LELAND, An improved spectral load balancing method, in Proc. 6th SIAM Conf. Parallel Processing for Scientific Computing, SIAM, March 1993, pp. 953-961.
• 11: B. HENDRICKSON AND R. LELAND, Multidimensional spectral load balancing, Tech. Rep. SAND93-0074, Sandia National Laboratories, Albuquerque, NM, January 1993.
• 12: B. HENDRICKSON AND R. LELAND, The Chaco user's guide, version 2.0, Tech. Rep. SAND94-2692, Sandia National Laboratories, Albuquerque, NM, October 1994.
• 13: Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
• 14: Bruce Hendrickson , Robert Leland , Rafael Van Driessche, Enhancing Data Locality by Using Terminal Propagation, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.565, January 03-06, 1996
• 15: Curt Allen Jones, Vertex and edge partitions of graphs, Pennsylvania State University, University Park, PA, 1992
• 16: G. KARYPIS AND V. KUMAR, A fast and high quality multilevel scheme for partitioning irregular graphs, Tech. Rep. CORR 95-035, University of Minnesota, Dept. Computer Science, Minneapolis, MN, June 1995.
• 17: B. KERNIGHAN AND S. LIN, An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, 29 (1970), pp. 291-307.
• 18: N. Mansour , R. Ponnusamy , A. Choudhary , G. C. Fox, Graph contraction for physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers, Proceedings of the 7th international conference on Supercomputing, p.1-10, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165942]
• 19: Alex Pothen , Horst D. Simon , Kan-Pu Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal on Matrix Analysis and Applications, v.11 n.3, p.430-452, Jul. 1990 [doi>10.1137/0611030]
• 20: J. E. SAVAGE AND M. G. WLOKA, Parallelism in graph-partitioning, J. Par. Dist. Comput., 13 (1991), pp. 257-272.
• 21: H. D. SIMON, Partitioning of unstructured problems for parallel processing, in Proc. Conference on Parallel Methods on Large Scale Structural Analysis and Physics Applications, Pergammon Press, 1991.
• 22: P. SUARIS AND G. KEDEM, An algorithm for quadrisection and its application to standard cell placement, IEEE Trans. Circuits and Systems, 35 (1988), pp. 294-303.
• 23: J. SWISSHELM. Personal Communication, February 1992.
• 24: D. VANDERSTRAETEN, C. FARHAT, P. S. CHEN, R. KEUNINGS, AND O. ZONE, A retrofit based methodology for the fast generation and optimization of mesh partitions: beyond the minimum interface size criteria, Comput. Meths. Appl. Mech. Eng., (1995). To appear.
• 25: D. VANDERSTRAETEN, R. KEUNINGS, AND C. FARHAT, Optimization of mesh partitions and impact on parallel CFD, in Parallel Computational Fluid Dynamics, New Trends and Advances, A. Ecer, J. Hauser, P. Leca, and J. Periaux, eds., Elsevier, 1995, pp. 233-239. (Also in Proc. Parallel CFD '93).
• 26: C. WALSHAW, M. CROSS, AND M. EVERETT, A parallelisable algorithm for optimising unstructured mesh partitions, Tech. Rep. 95/IM/03, University of Greenwich, London SE18 6PF, UK, 1995. (submitted for publication).
• 27: Roy D. Williams, Performance of dynamic load balancing algorithms for unstructured mesh calculations, Concurrency: Practice and Experience, v.3 n.5, p.457-481, Oct. 1991 [doi>10.1002/cpe.4330030502]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms, Economics, Experimentation, Theory

Keywords:
graph partitioning, parallel computation, load balancing, circuit placement