Global load balancing with parallel mesh adaption on distributed-memory systems

ABSTRACT

Dynamic mesh adaption on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load imbalance among processors on a parallel machine. This paper describes the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A huristic remapping algorithm is presented that assigns partitions to processors such that the redistribution cost is minimized. Results indicate that the paralel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors when about 35% of the mesh is randomly adapted. For large-scale scientific computations, our load balancing strategy gives almost a sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remapper yields processor assignments that are less than 3% off the optimal solutions but requries only 1% of the computational time.

REFERENCES

• 1: Rupak Biswas , Roger C. Strawn, A new procedure for dynamic adaption of three-dimensional unstructured grids, Applied Numerical Mathematics, v.13 n.6, p.437-452, Feb. 1994 [doi>10.1016/0168-9274(94)90007-8]
• 2: R. Biswas, S. Thomas, and S. Cliff, An Edge-Based Solution-Adaptive Method Applied to the AIRPLANE Code, 34th AIAA Aerospace Sciences Meeting, Paper 96-0553, 1996.
• 3: G. Cybenko, Dynamic load balancing for distributed memory multiprocessors, Journal of Parallel and Distributed Computing, v.7 n.2, p.279-301, October 1989 [doi>10.1016/0743-7315(89)90021-X]
• 4: Y. Deng, R. McCoy, R. Marr, and R. Peierls, An Unconventional Method for Load Balancing, 7th SIAM Conference on Parallel Processing for Scientific Computing, pp. 605-610, 1995.
• 5: E. Duque, R. Biswas, and R. Strawn, A Solution Adaptive Structured/Unstructured Overset Grid Flow Solver with Applications to Helicopter Rotor Flows, 13th AIAA Applied Aerodynamics Conference, Paper 95-1766, 1995.
• 6: K. D. Devine , J. E. Flaherty , S. R. Wheat , A. B. Maccabe, A massively parallel adaptive finite element method with dynamic load balancing, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.2-11, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169638]
• 7: Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing in parallel and distributed networks by random matchings (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.226-235, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181366]
• 8: B. Hendrickson and R. Leland, The Chaco user's guide --- Version 2.0, Sandia National Laboratories, Technical Report SAND94-2692, 1994.
• 9: G. Horton, A Multilevel Diffusion Method for Dynamic Load Balancing, Parallel Computing, Vol. 19, pp. 209-229, 1993.
• 10: R. Knecht , G. A. Kohring, Dynamic load balancing for the simulation of granular materials, Proceedings of the 9th international conference on Supercomputing, p.164-169, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224556]
• 11: Leonid Oliker , Rupak Biswas , Roger C. Strawn, Parallel Implementation of an Adaptive Scheme for 3D Unstructured Grids on the SP2, Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems, p.35-47, August 19-21, 1996
• 12: T. Purcell, CFD and Transonic Helicopter Sound, 14th European Rotorcraft Forum, Paper 2, 1988.
• 13: Andrew Sohn , Rupak Biswas , Horst D. Simon, Impact of Load Balancing on Unstructured Adaptive Grid Computations for Distributed-Memory Multiprocessors, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.26, October 23-26, 1996
• 14: R. Strawn, R. Biswas, and M. Garceau, Unstructured Adaptive Mesh Computations of Rotorcraft High-Speed Impulsive Noise, Journal of Aircraft, Vol. 32, pp. 754-760, 1995.
• 15: R. Van Driessche and D. Roose, Load Balancing Computational Fluid Dynamics Calculations on Unstructured Grids, AGARD, Report R-807, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

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

Keywords:
Load balancing, mesh adaption, unstructured grids, dual graph, processor reassignment, distributed-memory machines