A parallel implementation of computer code for generation of uniform and non-uniform unstructured grids in two- or three-dimensional domains based on the molecular dynamics method is presented. The calculation of particle trajectories during molecular dynamics simulation demands significant computational resources. Thus, high-performance computing systems must be used for large size adaptive grids and complex computational domains. Thereby, the effective load balancing methods for molecular dynamics simulation are implemented and investigated. Algorithms are based on geometric and graph representations. Geometric techniques (such as recursive coordinate bisection, recursive inertial bisection and space-filling curve methods) and multilevel schemes are applied. Some test cases are considered to examine of the quantitative and qualitative characteristics of the dynamic load balancing methods.
the molecular dynamics method, unstructured mesh, multiprocessor simulation, graph decomposition, data decomposition
Балансировка нагрузки процессоров при решении задач молекулярной динамики
Представлена параллельная реализация компьютерного кода, предназначенного для создания двумерных и трехмерных, однородных и адаптивных неструктурированных расчетных сеток для различных задач механики сплошной среды с использованием классических методов молекулярной динамики. Расчет траекторий в процессе молекулярно-динамического моделирования требует существенных затрат компьютерных ресурсов. Таким образом, для сеток большой размерности со значительным сгущением узлов в зонах больших градиентов и сложных расчетных областей необходимо использовать высокопроизводительные вычислительные системы. В связи с этим реализуются и исследуются различные эффективные методы балансировки нагрузки процессоров при проведении молекулярно-динамического моделирования на многопроцессорных вычислительных системах в ходе оптимального распределения узлов будущей расчетной сетки. Алгоритмы строятся на основе геометрических и графовых моделей и используют принципы координатной или моментной рекурсивной бисекции, либо применяют заполняющие пространство кривые; также рассматриваются многоуровневые технологии. В ходе работы проведена качественная и количественная оценка эффективности исследованных технологий динамической декомпозиции данных на ряде двумерных и трехмерных тестовых задач.
метод молекулярной динамики, неструктурированная сетка, многопроцессорное моделирование, декомпозиция графов, декомпозиция данных
1. Железнякова А.Л. Унифицированный подход к созданию сложных виртуальных поверхностей и расчетных сеток для комплексного имитационного 3D моделирования современных изделий аэрокосмической техники // Физико-химическая кинетика в газовой динамике. 2016. Том 17, вып. 2. 24 с. http://chemphys.edu.ru/issues/2016-17-2/articles/634/ 2. Zheleznyakova A.L., Surzhikov S.T. Molecular dynamic-based unstructured grid generation method for aerodynamic application // Computer Physics Communication, v.184, (2013) 2711-2727. 3. Zheleznyakova A.L. Molecular dynamics-based triangulation algorithm of free-form parametric surfaces for computer-aided engineering // Computer Physics Communications v.190 (2015) 1-14. 4. Железнякова А.Л. Молекулярно-динамический метод построения неструктурированных сеток в сложных пространственных областях и на криволинейных поверхностях // Физико-химическая кинетика в газовой динамике. 2012. Том 13, вып. 4. http://chemphys.edu.ru/issues/2012-13-4/articles/368/ 5. Железнякова А. Л., Суржиков С. Т. Построение пространственных неструктурированных сеток на NURBS-поверхностях сложных изделий авиационной и ракетно-космической техники методом молекулярной динамики //Физико-химическая кинетика в газовой динамике. 2014. Т.15, вып. 1. http://chemphys.edu.ru/issues/2014-15-1/articles/108/ 6. Rogers D.F. An Introduction to NURBS with Historical Perspective. Morgan Kaufman Publishers, San Fransisco, 2001. 324 p. 7. Piegl L.A., Tiller W. The NURBS Book. Springer, 1997. 646 p. 8. Lee K. Principles of CAD/CAM/CAE Systems. Addison-Wesley, California, 1999. 582 p. 9. Скворцов А.В. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование. №3, 2002. С. 82–92. 10. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. №3, 2002, С. 14–39. 11. FLUENT, Inc., GAMBIT 2.2, User's Guide, Lebanon, NH, USA, 2004. 630 c. 12. Cox M.G. The Numerical Evaluation of B-Splines // J. Inst. Maths. Applies. Vol. 15, 1972. P.95–108. 13. de Boor C. On calculating with B-Splines // J. of Approx. Theory. Vol. 6, 1972. P. 52–60. 14. Verlet L. Computer experiments on classical fluids. I. Thermodynamic properties of Lennard-Jones molecules // Phys. Rev, 1967, v. 159, p. 98-103. 15. Verlet L. Computer experiments on classical fluids. II. Equilibrium correlation functions // Phys. Rev, 1968, v. 165, p. 201-214. 16. Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. 400 с. 17. Гергель В.П. Теория и практика параллельных вычислений. Интернет – университет информационных технологий. – М: Бином, 2007. 424 с. 18. Berger M.J., Bokhari S. A partitioning strategy for nonuniform problems on multiprocessors // IEEE Trans. Comp. Vol. 36. 1987. P. 570–580. 19. Nour-Omid B., Raefsky A., Lyzenga G. Solving finite element equations on concurrent computers. / In A.K. Noor, editor, Parallel Computations and Their Impact on Mechanics, ASME, 1986. P. 209–227. 20. Patra A., Kim D.W. Efficient mesh partitioning for adaptive hp finite element methods / In International Conference on Domain Decomposition Methods, 1998. 21. Pilkington J.R., Baden S.B. Partitioning with spacefilling curves / Technical Report CS94-349, Dept. of Computer Science and Engineering, Univ. of California, 1994. 22. Mandelbrot B.B. The Fractal Geometry of Nature / New York: W. H. Freeman and Co., 1982. 23. Alauzet F., Loseille A. On the use of space filling curves for parallel anisotropic mesh adaptation // Proc. in 18th International Meshing Roundtable, Springer-Verlag, 2009. P. 337–357. 24. Schamberger S., Wierum J.M. A locality preserving graph ordering approach for implicit partitioning: Graph-filling curves // Proc. 17th Intl. Conf. on Parallel and Distributed Computing Systems, PDCS 2004, ISCA, 2004. P. 51–57. 25. Hendrickson B., Leland R. A multilevel algorithm for partitioning graphs / Technical Report SAND 93-1301, Sandia National Laboratories, 1993. 26. Karypis G., Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs // SIAM Journal on Scientific Computing. Vol. 20, №1, 1998. P. 359–392. 27. Karypis G., Kumar V. Multilevel k-way partitioning scheme for irregular graphs // Journal of Parallel and Distributed Computing. Vol. 48, № 1, 1998. P. 96–129. 28. Fiduccia C.M., Mattheyses R.M. A linear time heuristic for improving network partitions // Proc. 19th IEEE Design Automation Conference, 1982. P. 175–181. 29. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs // The Bell System Technical Journal. Vol. 49, №2, 1970. P. 291–307. 30. MATLAB. http://www.mathworks.com/products/matlab/