Load balancing of processors when solving the problems of fluid and gas mechanics by mesh methods

Authors

  • K.N. Volkov

Keywords:

parallel algorithm
load balancing
decomposition
mesh
grid
fluid and gas mechanics

Abstract

Numerical solution of problems of fluid and gas mechanics on multiprocessor computing systems involves a geometric decomposition of the computational domain, handling the corresponding subdomain by each processor, and communications between processors for a complete solution. Load balancing of processors is specified by the uniformity of the mesh distribution between processors and the cost of data transfer between processors. The cost of data transfer between processors depends on the number of connections between the subdomains distributed over the processors. Approaches to the static and dynamic load balancing of processors are considered to solve the problems of fluid and gas mechanics on multiprocessor computing systems. Various stages and methods of static (methods of bisection, combinatorial methods, combined approaches) and dynamic (diffusive algorithm, method of potential, multilevel approaches) load balancing are discussed, and their performance indices are compared. The diffusive method and the method of potential are compared for a domain of simple geometric configuration to solve the problem on an adaptive grid.

New computational technologies

Downloads

Published

2012-01-31

Issue

Vol. 13 (2012): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

K.N. Volkov

D.F. Ustinov Baltic State Technical University «Voenmekh»
• Associate Professor

References

  1. Беликов Д.А., Говязов И.В., Данилкин Е.А., Лаева В.И., Проханов С.А., Старченко А.В. Высокопроизводительные вычисления на кластерах. Томск: Изд-во ТГУ, 2008.
  2. Le Tallec P. Domain decomposition methods in computational mechanics // Advances in Computational Mechanics. 1993. 1, N 2. 121-220.
  3. Волков К.Н. Применение средств параллельного программирования для решения задач механики жидкости и газа на многопроцессорных вычислительных системах // Вычислительные методы и программирование. 2006. 7, № 1. 73-88.
  4. Walshaw C., Cross M., Everett M. Parallel dynamic load balancing for adaptive unstructured meshes // J. of Parallel and Distributed Computing. 1997. 47, N 2. 102-108.
  5. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. University of Minnesota. Department of Computer Science. Technical Report TR 95-035. Minneapolis, 1995.
  6. Simon H.D. Partitioning of unstructured problems for parallel processing // Computing Systems in Engineering. 1991. 2, N 2, 3. 135-148.
  7. Hendrickson B., Devine K. Dynamic load balancing in computational mechanics // Computer Methods in Applied Mechanics and Engineering. 2000. 184, N 2-4. 485-500.
  8. Копысов С.П., Новиков А.К. Параллельные алгоритмы адаптивного перестроения и разделения неструктурированных сеток // Математическое моделирование. 2002. 14, № 9. 91-96.
  9. Круглякова Л.В., Неледова А.В., Тишкин В.Ф., Филатов А.Ю. Неструктурированные адаптивные сетки для задач математической физики (обзор) // Математическое моделирование. 1998. 10, № 3. 93-116.
  10. Diniz P., Plimpton S.J., Hendrickson B., Leland R. Parallel algorithms for dynamically partitioning unstructured grids // Proc. of the 7th SIAM Conference on Parallel Processing for Scientific Computing. 15-17 February 1995. San Francisco, 1995. 615-621.
  11. Schloegel K., Karypis G., Kumar V. Graph partitioning for high performance scientific simulations // CRPC Parallel Computing Handbook. San Francisco: Morgan Kauffman, 2000. 491-541.
  12. Bui T.N., Chaudhuri S., Leighton F.T., Sipser M. Graph bisection algorithms with good average case behavior // Combinatorica. 1987. 7, N 2. 171-191.
  13. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graph // Bell System Technical J. 1970. 49. 291-308.
  14. Hu Y.F., Blake R.J. Numerical experiences with partitioning of unstructured meshes // Parallel Computing. 1994. 20, N 5. 815-829.
  15. Miller G.L., Teng S.-H., Vavasis S.A. A unified geometric approach to graph separators // Proc. of the 32nd Symposium on Foundations of Computer Science. 1-4 October 1991. San Juan, Puerto Rico. 1991. 538-547.
  16. Gilbert G.L., Teng S. Geometric mesh partitioning: implementation and experiments // Proc. of the 9th International Parallel Processing Symposium. 25-28 April 1995. Santa Barbara: Computer Society Press, 1995. 418-427.
  17. Williams R.D. Performance of dynamic load balancing algorithms for unstructured mesh applications // Concurrency - Practice and Experience. 1991. 3, N 5. 457-481.
  18. Berger M.J., Bokhari S.H. A partitioning strategy for nonuniform problems on multiprocessors // IEEE Trans. on Computers. 1987. 36, N 5. 570-580.
  19. Jones M.T., Plassmann P.E. Scalable iterative solution of sparse linear systems // Parallel Computing. 1994. 20, N 5. 753-773.
  20. Keyser J.D., Roose D. Grid partitioning by inertial recursive bisection. University of Leuven, Department of Computer Science. Technical Report TW-174. Leuven, 1992.
  21. Nour-Omid B., Raefsky A., Lyzenga G. Solving finite element equations on concurrent computers // Proc. of the Symposium on Parallel Computations and Their Impact on Mechanics. 13-18 December 1986. Boston, 1986. 209-227.
  22. Shephard M.S., Flaherty J.E., de Cougny H.L., Özturan C., Bottaso C.L., Beall M.W. Parallel automated adaptive procedures for unstructured meshes // Special Course on Parallel Computing in CFD (AGARD-R-807). 1995. 6. 1-6.49.
  23. Farhat A. A simple and efficient automatic FEM domain decomposer // Computer and Structures. 1988. 28, N 5. 579-602.
  24. Pothen A., Simon D.H., Liou K. Partitioning sparse matrices with eigenvectors of graphs // SIAM J. of Matrix Analysis and Applications. 1990. 11, N 3. 430-452.
  25. Kruyt N. A conjugate gradient method for the spectral partitioning of graphs // Parallel Computing. 1997. 22, N 11. 1493-1502.
  26. Sadayappan P., Ercal F., Ramanujam J. Cluster partitioning approach to mapping parallel programs onto a hypercube // Parallel Computing. 1990. 13, N 1. 1-16.
  27. Fiduccia C.M., Mattheyses R.M. A linear-time heuristic for improving network partitions // Proc. of the 19th IEEE Design Automation Conference. 14-16 June 1982. Las Vegas, 1982. 175-181.
  28. Bui T.N., Moon B.R. Genetic algorithm and graph partitioning // IEEE Trans. on Computers. 1996. 45, N 7. 841-855.
  29. Mansour N. Allocating data the multicomputer nodes by physical optimization algorithms for loosely synchronous computations // Concurrency - Practice and Experience. 1992. 4, N 7. 557-574.
  30. Martin O.C., Otto S.W. Partitioning of unstructured meshes for load balancing // Concurrency - Practice and Experience. 1995. 7, N 4. 303-314.
  31. Malone J.G. Automated mesh decomposition and concurrent finite element analysis for hypercube multiprocessor computers // Computer Methods in Applied Mechanics and Engineering. 1988. 70, N 1. 27-58.
  32. Ou C., Ranka S., Fox G. Fast and parallel mapping algorithms for irregular problems // J. of Supercomputing. 1996. 10, N 1/2. 119-140.
  33. Sagan H. Space filling curves. New York: Springer, 1994.
  34. Liu X., Schrack G. Encoding and decoding the Hilbert order // Software - Practice and Experience. 1996. 26, N 12. 1335-1346.
  35. Flaherty J., Loy R., Shephard M., Szymanski B., Teresco J., Ziantz L. Adaptive local refinement with octree load-balancing for the parallel solution of three-dimensional conservation laws // J. of Parallel and Distributed Computers. 1997. 47, N 2. 139-152.
  36. Aftosmis M.J., Berger M.J., Murman S.M. Applications of space-filling curves to Cartesian methods for CFD // AIAA Paper. N 2004-1232.
  37. Griebel M., Tilman N., Regler H. Algebraic multigrid methods for the solution of the Navier-Stokes equations in complicated geometries // Int. J. for Numerical Methods in Fluids. 1998. 26, N 3. 281-301.
  38. Vanderstraeten D., Keunings R. Optimized partitioning on unstructured finite-element meshes // Int. J. for Numerical Methods in Engineering. 1995. 38, N 3. 433-450.
  39. Karypis G., Kumar V. A parallel algorithm for multilevel graph partitioning and sparse matrix ordering // J. of Parallel and Distributed Computing. 1998. 48, N 1. 71-95.
  40. Barnard S.T., Simon H.D. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems // Concurrency - Practice and Experience. 1994. 6, N 2. 101-117.
  41. Головченко Е.Н. Комплекс программ параллельной декомпозиции сеток // Вычислительные методы и программирование. 2010. 11. 366-372.
  42. Flaherty J.E., Loy R.M., Özturan C., Shepard M.S., Szymanski B.K., Teresco J.D., Ziantz L.H. Parallel structures and dynamic load balancing for adaptive finite element computation // Applied Numerical Mathematics. 1998. 26, N 1, 2. 241-263.
  43. Biswas R., Oliker L. Experiments with repartitioning and load balancing adaptive meshes // NASA Ames Research Center. Technical Report NAS-97-021. Moffett Field, 1997.
  44. Biswas R., Das S.K., Harvey D.J., Oliker L. Parallel dynamic load balancing strategies for adaptive irregular applications // Applied Mathematical Modelling. 2000. 25, N 2. 109-122.
  45. Walshaw C., Berzins M. Dynamic load-balancing for PDE solvers on adaptive unstructured meshes // Concurrency - Practice and Experience. 1995. 7, N 1. 17-28.
  46. Schloegel K., Karypis, Kumar V., Biswas R., Oliker L. A performance study of diffusive vs re-mapped load-balancing schemes. University of Minnesota, Department of Computer Science. Technical Report TR 98-018. Minneapolis, 1998.
  47. Cybenko G. Dynamic load balancing for distributed memory multi-processors // J. of Parallel and Distributed Computing. 1989. 7, N 2. 279-301.
  48. Hu Y.F., Blake R.J., Emerson D.R. An optimal dynamic load balancing algorithm // Concurrency - Practice and Experience. 1998. 10, N 6. 467-483.
  49. Xu C.Z., Lau F.C. M. Analysis of the generalized dimension exchange method for dynamic load balancing // J. of Parallel and Distributed Computing. 1992. 16, N 4. 385-393.
  50. Horton G. A multi-level diffusion method for dynamic load balancing // Parallel Computing. 1993. 19, N 2. 209-218.
  51. Song J. A partially asynchronous and iterative algorithm for distributed load balancing // Parallel Computing. 1994. 20, N 6. 853-868.
  52. Boillat J.E., Bruge F. A dynamic load-balancing algorithm for molecular dynamics simulation on multi-processor systems // J. of Computational Physics. 1991. 96, N 1. 1-14.
  53. Kohring G.A. Dynamic load balancing for parallel particular simulation on MIMD computers // Parallel Computing. 1995. 21, N 4. 683-693.
  54. Heririch A., Taylor S. A parabolic load balancing method // Proc. of the 24th Int. Conference on Parallel Processing. 14-18 August 1995. Oconomowoc, Wisconsin. 3. New York: CRC Press, 1995. 192-202.
  55. Hu Y.F. An improved diffusion algorithm for dynamic load balancing // Parallel Computing. 1999. 23, N 4. 417-444.
  56. de Cougny H.L., Devine K.D., Flaherty J.E., Loy R.M., Özturan C., Shephard M.S. Load balancing for the parallel adaptive solution of partial differential equations // Applied Numerical Mathematics. 1994. 16, N 1, 2. 157-182.