Балансировка нагрузки процессоров при решении краевых задач механики жидкости и газа сеточными методами

Авторы

  • К.Н. Волков

Ключевые слова:

параллельный алгоритм
балансировка нагрузки
декомпозиция
сетка
механика жидкости и газа

Аннотация

Численное решение задач механики жидкости и газа на многопроцессорных вычислительных системах состоит в геометрической декомпозиции расчетной области, обработке каждым процессором своей подобласти и коммуникациях между процессорами для получения полного решения. Сбалансированность нагрузки процессоров определяется равномерностью распределения сетки по процессорам и затратами на передачу данных между ними. Объем передачи данных между процессорами зависит от числа связей между подобластями, распределенными по процессорам. Обсуждаются подходы к обеспечению статической и динамической балансировки нагрузки процессоров при решении задач механики жидкости и газа на многопроцессорных вычислительных системах. Приводится описание различных этапов и методов статической (методы половинного деления, комбинаторные методы, комбинированные подходы) и динамической (диффузный алгоритм, метод потенциала, многоуровневые подходы) балансировки, а также сравниваются показатели их эффективности. Проводится сравнение диффузного метода и метода потенциала для области простой геометрической конфигурации при решении задачи на адаптивной сетке.

Новые вычислительные технологии

Загрузки

Опубликован

2012-01-31

Выпуск

Том 13 (2012): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

К.Н. Волков

Балтийский государственный технический университет «Военмех» имени Д.Ф. Устинова,
физико-механический факультет
1-я Красноармейская ул., 1, 190005, Санкт-Петербург
• доцент

Библиографические ссылки

  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.