PMRSB: parallel multilevel recursive spectral bisection

ABSTRACT

The design of a parallel implementation of multilevel recursive spectral bisection on the Cray T3D is described. The code is intended to be fast enough to enable dynamic repartitioning of adaptive meshes and to partition meshes that are too large for workstations. Two innovations in the implementation are recursive asynchronous task teams and a parallel version of the multilevel accelerator. A performance improvement of a factor of 140 over the best available serial implementation is demonstrated.

REFERENCES

• 1: S. T. Barnard and H. D. Simon, 'Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems', Concurrency: Practice and Experience, Vol. 6, No. 2, 101-117 (1994).
• 2: S. T. Barnard , A. Pothen , H. D. Simon, A spectral algorithm for envelope reduction of sparse matrices, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.493-502, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169790]
• 3: E. D. Brooks III, B. C. Gorda, and Karen H. Warren, 'The Parallel C Preprocessor', Scientific Programming, Vol. 1, No. 1, 79-89 (1992).
• 4: CMSSL For CM Fortran, Vol. II, version 3.2, Thinking Machines Corp., (1994).
• 5: P. Diniz, S. Plimpton, B. Hendrickson, and R. Leland, 'Parallel algorithms for dynamically partitioning unstructured grids', Proceeding of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, 615-620 (1995).
• 6: M. Garey, D. Johnson, and L. Stockmeyer, 'Some simplified NP- complete graph problems', Theoretical Computer Science,1, 237-267 (1976).
• 7: C. Lanczos, 'An iteration method for the solution of the eigenvalue problem of linear differential and integral operators', J. Res. Nat. Bur. Stand., 45, 255-282 (1950).
• 8: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 9: C. C. Paige and M. A. Saunders, 'Solution of sparse indefinite systems of linear equations', SIAM J. Numer. Anal., Vol. 12, 617-629 (1974).
• 10: B. N. Parlett, 'The Rayleigh quotient iteration and some generalizations for nonnormal matrices', Math Comp., 28(127), 679- 693 (1974).
• 11: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 12: H. Gazit, 'Randomized parallel connectivity', in Synthesis of Parallel Applications, ed. by J. H. Reif, 197-214, Morgan Kaufmann Publishers, Inc., 1993.
• 13: H. Simon, 'Partitioning unstructured problems for parallel processing', Comput. Syst. Eng., 2(2/3), 135-148 (1991).
• 14: Numerical Recipes in C, Second Edition, W. H. Press, S. A. Teukolosky, W. T. Vetterling, and B. P. Flannery, Cambridge University Press, 1994.

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.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers
      C.5.3 Microcomputers
          Subjects: Microprocessors

General Terms:
Algorithms, Design, Performance