БАЛАНСИРОВКА НАГРУЗКИ С ИСПОЛЬЗОВАНИЕМ ВЗВЕШЕННЫХ ДИАГРАММ ВОРОНОГО

Решение задачи балансировки нагрузки актуально при проведении высокопроизводительных вычислений. Одним из оригинальных методов решения задачи балансировки является использование диаграмм Вороного для декомпозиции области. Сильной стороной данного подхода является возможность применения такой декомпозиции на различных типах данных. Балансировка может использоваться на эйлеровых сетках, лагранжевых сетках, совместно с методикой сглаженных частиц (SPH). Метод также может использоваться для балансировки адаптивных сеток, но в этом случае проявляется его недостаток: из-за сильной неоднородности нагрузки на адаптивных сетках метод динамической балансировки может быть неустойчивым или обладать плохой сходимостью. В работе предлагается усовершенствование алгоритма балансировки за счет перехода от использования обычных диаграмм Вороного к взвешенным диаграммам. Предложенный алгоритм реализован в виде программного комплекса. Тестирование предложенного алгоритма строится на базе ряда модельных задач и задач из области механики сплошной среды. Оценка эффективности балансировки строится на базе исследования поведения величины дисбаланса с учетом балансировки и без. Показано, что предложенный алгоритм успешно справляется со своей задачей, и величина дисбаланса в случае использования взвешенной диаграммы Вороного в 10–100 раз меньше, чем при использовании обычных диаграмм Вороного.

1. Cybenko G. Dynamic load balancing for distributed memory multiprocessors // Journal of Parallel and Distributed Computing, 1989. V. 7. P. 279–301.

2. Dobrev V.A., Kolev T.V., Rieben R.N. High-order curvilinear finite element methods for lagrangian hydrodynamics // SIAM Journal on Scientific Computing, 2012. V. 34. P. B606–B641.

3. Egorova M.S., Dyachkov S.A., Parshikov A.N., Zhakhovsky V. Parallel sph modeling using dynamic domain decomposition and load balancing displacement of voronoi subdomains // Computer Physics Communications, 2019. V. 234. P. 112–125.

4. Fryxell B., Olson K., Ricker P., Timmes F., Zingale M., Lamb D., MacNeice P., Rosner R., Truran J., Tufo H. Flash: An adaptive mesh hydrodynamics code for modeling astrophysical thermonuclear flashes // The Astrophysical Journal Supplement Series, 2000. V. 131. P. 273.

5. Galera S., Maire P.-H., Breil J. A two-dimensional unstructured cell-centered multi-material ale scheme using vof interface reconstruction // Journal of Computational Physics, 2010. V. 229. P. 5755–5787.

6. Karypis G., Schloegel K., Kumar V. Parmetis: Parallel graph partitioning and sparse matrix ordering library, 1997.

7. Koradi R., Billeter M., Gu¨ntert P. Point-centered domain decomposition for parallel molecular dynamics simulation // Computer Physics Communications, 2000. V. 124. P. 139–147.

8. Kudryashov N., Muratov R., Ryabov P. The collective behavior of shear strain localizations in dipolar materials // Applied Mathematics and Computation, 2018. V. 338. P. 164–174.

9. Kudryashov N.A., Ryabov P.N., Zakharchenko A.S. Self-organization of adiabatic shear bands in ofhc copper and hy-100 steel // Journal of the Mechanics and Physics of Solids, 201576. P. 180–192.

10. Lohner R. An adaptive finite element scheme for transient problems in cfd // Computer Methods in Applied Mechanics and Engineering, 1987. V. 61. P. 323–338.

11. Menshov I. Zakharov P. On the composite riemann problem for multi-material fluid flows // International Journal for Numerical Methods in Fluids, 2014. V.76. P. 109–127.

12. Muratov R., Kudryashov N., Ryabov P. A finite volume method for numerical simulations of adiabatic shear bands formation // Communications in Nonlinear Science and Numerical Simulation, 2021. V. 101. P. 105858.

13. Muratov R.V., Kudryashov N.A., Ryabov P.N. Application of the adaptive mesh refinement technique to study the plastic flow localization process // Bulletin of the National Research Nuclear University MEPhI, 2019. V .8. P. 361–369.

14. Nourgaliev R.R., Dinh T.-N., Theofanous T.G. Adaptive characteristics-based matching for compressible multifluid dynamics // Journal of Computational Physics, 2006. V. 213. P. 500–529.

15. Pan S., Han L., Hu X., Adams N.A.A conservative interface-interaction method for compressible multi-material flows // Journal of Computational Physics, 2018. V. 371. P. 870–895.

16. Smirnov N., Kiselev A., Zakharov P., Muratov R., Bukharinskaya D. The usage of adaptive mesh refinement in simulation of high-velocity collision between impactor and thin-walled containment // Acta Astronautica, 2022. V. 194. P. 401–410.

17. Zhakhovskii V., Nishihara K., Fukuda Y., Shimojo S., Akiyama T., Miyanaga S., Sone H., Kobayashi H., Ito E., Seo Y., Tamura M., Ueshima Y. A new dynamical domain decomposition method for parallel molecular dynamics simulation, in CCGrid 2005 // IEEE International Symposium on Cluster Computing and the Grid, 2005. V. 2, 2005. P. 848–854.