ONE METHOD OF LOAD BALANCING USING WEIGHTED VORONOI DIAGRAM
https://doi.org/10.26583/vestnik.2023.252
Abstract
The solution of load balancing problem in parallel programming is very actual problem. One of the original methods for solving the balancing problem is the use of Voronoi diagrams. The main advantage of the following method that it can be used on the data of different types. For example, this method can be used for balancing the Eulerian and Lagrangian computational grids with the smooth-particles hydrodynamic method. Also, this approach can be used for adaptive grids. However, in that case, due to the strong inhomogeneity of the load on adaptive grids, the such load balancing method can be unstable or have poor convergence. In the present work we give an improvement of the load balancing method in terms of weighted Voronoi diagrams. The proposed algorithm is implemented as a software package. Testing of the proposed algorithm is based on a number of model problems and problems from the field of continuum mechanics. Evaluation of the balancing efficiency is based on the study of the behavior of the imbalance value with and without balancing. It is shown that the proposed algorithm successfully copes with its task and the magnitude of the imbalance in the case of using a weighted Voronoi diagram is 10–100 times less than when using classical Voronoi diagrams.
About the Authors
R. V. Muratov
National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)
Russian Federation
Russian Federation
P. N. Ryabov
National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)
Russian Federation
Russian Federation
S. A. Dyachkov
NL Dukhov All-Russian Research Institute of Automation
Russian Federation
Russian Federation
References
1. Cybenko G. Dynamic load balancing for distributed memory multiprocessors. Journal of Parallel and Distributed Computing. 1989. Vol. 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. Vol. 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. Vol. 234. P. 112–125.
4. Fryxell B., Olson K., Ricker P., Timmes F., Zinga-le 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. Vol. 131. P. 273.
5. Galera S., Maire P.-H., and Breil J. A two-dimensional unstructured cell-centered multi-material ale scheme using vof interface reconstruction. Journal of Computational Physics. 2010. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 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. Vol. 2. P. 848–854.
Review
For citations:
Muratov R.V., Ryabov P.N., Dyachkov S.A. ONE METHOD OF LOAD BALANCING USING WEIGHTED VORONOI DIAGRAM. Vestnik natsional'nogo issledovatel'skogo yadernogo universiteta "MIFI". 2023;12(1):52-74. (In Russ.) https://doi.org/10.26583/vestnik.2023.252
Views:
192
Email this article 