Automatic load balanced paritioning strategies for PDE computations

ABSTRACT

In this paper we study the partitioning and allocation of computations associated with the numerical solution of partial differential equations (PDEs). Strategies for the mapping of such computations to parallel MIMD architectures can be applied to different levels of the solution process. We introduce and study heuristic approaches defined on the associated geometric data structures (meshes). Specifically, we study methods for decomposing finite element and finite difference meshes into balanced, nonoverlapping subdomains which guarantee minimum communication and synchronization among the underlying associated subcomputations. Two types of algorithms are considered: clustering techniques based on sequential orderings of the discrete geometric data and optimization based techniques involving geometric or graphical metric criteria. These algorithms support the automatic mode of a geometry decomposition tool developed in the parallel ELLPACK environment which is implemented under X11-window systems. A brief description of this tool is presented.

REFERENCES

• Barne 82: E.R. Barnes, "An algorithm for partitioning the nodes of a graph", S/AM Journal Algebraic and Discrete Methods, Vol. 3, pp. 541-550, Dec. (1982).
• Berg 85: M.J. Bergcr and S. Bokhari, "A partitioning strategy for non-uniform problems as multiprocessors", ICASE Report No. 85-55, Nov. 0985).
• Chris 76: N. Christofides and P. Brooker, "The Optimal partitioning of graphs", SIAM Journal of Applied Mathematics, Vol. 30, pp. 55-69 (1976).
• Donat 73: W.E. Donath and A.J. Hoffmann, "Lower bounds for the partitioning of graphs", iBM Journal of Research and Development, Vol. 17, pp. 420425, Sept. (1973).
• Farh 88: C. Farhat, "A simple and efficient automatic FEM domain decomposer'', Computers and Structures, Vol. 28, pp. 579--602 (1988).
• Fox 86a: G.C. Fox, "A graphical approach to load balancing and sparse matrix vector multiplication on the hypercube", in Numerical Algorithms for Modern Parallel Computer Architectures, IMA Vol. Math. App., 13 (M. Schultz, ed.), Springer-Verlag, pp. 37-61 (1987).
• Fox 86b: G.C. Fox, "A review of automatic load balancing and decomposition methods for the hypercube", in Numerical Algorithms for Modern Parallel Computer Architectures, IMA Vol. Math. App., 13 (M. Schultz, ed.), Springer-Verlag, pp. 63-76 (1987).
• Garey 79: M.R. Garey and D.S. johnson, "Computers and Intractability' ', W.H. Freeman and Company, (1979).
• Goldb 84: M.K. Goldberg and R. Gardner, "On the minimal cut problem", Progress in Graph Theory, (1984).
• Hous 88: C.E. Houstis, E.N. Houstis, J.R. Rice, S.M. Samartzis and D.L. Alexandrakis, "The algorithm mapper: A System for modeling and evaluating parallel applications/architectures pairs", in Fourth Generation Mathematical Software Systems (Houstis, Rice and Vichnevetsky, eds.), North-Holland (1989), to appear.
• Hous 89a: E.N. Houstis, T.S. Papa theodorou and J.R. Rice, "Parallel ELLPACK: An expert system for the parallel processing of partial differential equations", Math. Comp. Simul., Vol. 31 (1989), to appear.
• Hous 89b: E.N. Houstis, P.N. Papachiou, J.R. Rice and M.S. Samartzis, "Domain decomposer: A software tool for partitioning PDE computations based on geometry decomposition strategies", Purdue University Technical report, in preparation.
• Kern 70: B.W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs", The Bell System Technical Journal, Feb. (1970), pp. 291-307.
• Pirkt 83: Lenna~, Pirktl, "On the use of cluster analysis for partitioning and allocation computational objects in distributed computing systems", Computer Science and Statistics: The Interface, James E. Gentle (ed.), North-Holland, pp. 361-364, (1983).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory