Особенности реализации алгоритма Treecode для решения задачи N-тел с использованием графических ускорителей
Аннотация
Иерархические методы вычисления гравитационных сил для систем N-тел позволяют существенно увеличить качество численного моделирования при решении различных астрофизических задач за счет увеличения числа элементов N, поскольку вместо вычислительной сложности ∼O(N2) для прямого метода, мы имеем N log(N) при использовании приближенного метода TreeCode, что позволяет существенно увеличить число частиц в численных моделях. Разработано новое программное обеспечение для решения динамической задачи с большим числом частиц для моделирования галактических бесстолкновительных компонент, в частности, звездной подсистемы и темной массы. В работе представлены результаты тестирования алгоритма TreeCode для параллельной реализациии на графических ускорителях NVidia Tesla. Для построения иерархической системы сеток нами реализован быстрый алгоритм построения октодеревьев, основанный на пространственной кривой Мортона. Для оценок качества построенной численной модели используем для сравнения результаты моделирования на основе прямого вычисления сил взаимодействия между всеми N частицами системы. Проведен анализ быстродействия различных реализаций алгоритмов решения задачи N-тел и выполнения интегральных законов сохранения физических характеристик для гравитирующих систем. В частности, проанализированы законы сохранения энергии и момента импульса для вращающегося самогравитирующего диска. Рассмотрены модели с различными критериями оценки удаленности частицы и значениями угла раскрытия θ.
Ключевые слова
Полный текст:
PDFЛитература
Aarseth S.J. The Cambridge N-body lectures. Lecture Notes in Physics. 2008. Vol. 760. 402 p. DOI: 10.1007/978-1-4020-8431-7.
Greenspan D. N-body problems and models. World Scientific, 2004. 193 p.
Ostriker J.P., Peebles P.J.E. A Numerical Study of the Stability of Flattened Galaxies: or, can Cold Galaxies Survive? Astrophysical Journal. 1973. Vol. 186. P. 467–480. DOI: 10.1086/152513.
Klypin A., Holtzman J., Primack J., Regos E. Structure Formation with Cold plus Hot Dark Matter. Astrophysical Journal. 1993. Vol. 416. P. 1–16. DOI: 10.1086/173210.
Schaye J., Crain R.A., Bower R.G. et al. The EAGLE project: simulating the evolution and assembly of galaxies and their environments. Monthly Notices of the Royal Astronomical Society. 2014. Vol. 446, no. 1. P. 521–554. DOI: 10.1093/mnras/stu2058.
Pillepich A., Springel V., Nelson D. et al. Simulating galaxy formation with the IllustrisTNG model. Monthly Notices of the Royal Astronomical Society. 2018. Vol. 473, no. 3. P. 4077–4106. DOI: 10.1093/mnras/stx2656.
Kim J., Abel T., Agertz O. et al. The AGORA High-resolution Galaxy Simulations Comparison Project. The Astrophysical Journal Supplement. 2014. Vol. 210, id. 14. 20 p. DOI: 10.1088/0067-0049/210/1/14.
Boylan-Kolchin M., Springel V., White S.D.M., Jenkins A., Lemson G. Resolving cosmic structure formation with the Millennium-II Simulation. Monthly Notices of the Royal Astronomical Society. 2009. Vol. 398. P. 1150–1164. DOI: 10.1111/j.1365-2966.2009.15191.x.
Zhao D., Du M., Ho L.C., Debattista V.P., Shi J. Barred Galaxies in the IllustrisTNG Simulation. The Astrophysical Journal. 2020. Vol. 904, id. 170. 12 p. DOI: 10.1111/10.3847/1538-4357/abbe1b.
Khoperskov S., Zinchenko I., Avramov B. et al. Extreme kinematic misalignment in IllustrisTNG galaxies: the origin, structure, and internal dynamics of galaxies with a large-scale counterrotation. Monthly Notices of the Royal Astronomical Society. 2021. Vol. 500, no. 3. P. 3870–3888. DOI: 10.1093/mnras/staa3330.
Ubler H., Genel S., Sternberg A., Genzel R. et al. The kinematics and dark matter fractions of TNG50 galaxies at z = 2 from an observational perspective. Monthly Notices of the Royal Astronomical Society. 2021. Vol. 500, no. 4. P. 4597–4619. DOI: 10.1093/mnras/staa3464.
Hockney R.W., Eastwood J.W. Computer simulation using particles. Adam Hilger, Bristol, NY: IOP Publishing Ltd, 1988. 540 p.
Nemukhin A.V., Grigorenko B.L., Savitsky A.P. Computer Modeling of the Structure and Spectra of Fluorescent Proteins. Acta Naturae. 2009. Vol. 1, no. 2. P. 33–43. DOI: 10.32607/20758251-2009-1-2-33-43.
Kholmurodov K.T., Altaisky M.V., Puzynin I.V., Darden T., Filatov F.P. Molecular Dynamics Methods for Simulation of Physical and Biological Processes. Physics of Elementary Particles and Atomic Nuclei. 2003. Vol. 34, no. 2. P. 474–515. (in Russian)
Suplatov D.A., Sharapova Y.A., Popova N.N., Kopylov K.E., Voevodin Vl.V., Svedas V.K. Molecular Dynamics in the Force Field FF14SB in Water TIP4P-Ew, and in the Force Field FF15IPQ in Water SPC/Eb: a Comparative Analysis on GPU and CPU. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2019. Vol. 8, no. 1. P. 71–88. (in Russian) DOI: 10.14529/cmse190105.
Barnes J., Hut P. A hierarchical O(N log N) force-calculation algorithm. Nature. 1986. Vol. 324. P. 446–449. DOI: 10.1038/324446a0.
Hamada T., Nitadori K., Benkrid K. et al. A novel multiple-walk parallel algorithm for the Barnes–Hut treecode on GPUs – towards cost effective, high performance N-body simulation. Computer Science – Research and Development volume. 2009. Vol. 24. P. 21–31. DOI: 10.1007/s00450-009-0089-1.
Gulenok A.A., Dordopulo A.I., Levin I.I., Gudkov V.A. Hybrid computer system programming technology with adaptation and scaling of calculations. Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2017. Vol. 6, no. 1. P. 73–86. DOI: 10.14529/cmse170105.
Glinskiy B., Kulikov I., Chernykh I., Snytnikov A., Sapetina A., Weins D. The integrated approach to solving large-size physical problems on supercomputers. Communications in Computer and Information Science. 2017. Vol. 793. P. 278–289. DOI: 10.1007/978-3-319-71255-0_22.
Kuksheva E.A., Malyshkin V.E., Nikitin S.A., Snytnikov A.V., Snytnikov V.N., Vshivkov V.A. Supercomputer simulation of self-gravitating media. Future Generation Computer Systems. 2005. Vol. 21, no. 5. P. 749–757. DOI: 10.1016/j.future.2004.05.019.
Glinskiy B.M., Kulikov I.M., Snytnikov A.V., Romanenko A.A., Chernykh I.G., Vshivkov V.A. Co-design of parallel numerical methods for plasma physics and astrophysics. Supercomputing Frontiers and Innovations. 2014. Vol. 1, no. 3. P. 88–98. DOI: 10.14529/jsfi140305.
Fridman A.M., Khoperskov A.V. Physics of Galactic Disks. Cambridge International Science Publishing Ltd, 2013. 754 p.
Smirnov A.A., Sotnikova N.Ya., Koshkin A.A. Simulations of slow bars in anisotropic disk systems. Astronomy Letters. 2017. Vol. 43 P. 61–74. DOI: 10.1134/S1063773717020062.
Lukat G., Banerjee R. A GPU accelerated Barnes–Hut tree code for FLASH4. New Astronomy. 2016. Vol. 45. P. 14–28. DOI: 10.1016/j.newast.2015.10.007.
Karras T. Maximizing Parallelism in the Construction of BVHs, Octrees, and K-d Trees. Proceedings of the 4th Symposium on High-Performance Graphics. 2012. P. 33–37. DOI: 10.2312/EGGH/HPG12/033-037.
Khoperskov A.V., Bizyaev D., Tiurina N., Butenko M. Numerical modelling of the vertical structure and dark halo parameters in disc galaxies. Astronomische Nachrichten. 2010. Vol. 331, no. 7. P. 731–745. DOI: 10.1002/asna.200911402.
Khoperskov A.V., Tyurina N.V. A Dynamical Model of the Galaxy. Astronomy Reports. 2003. Vol. 47. P. 443–457. DOI: 10.1134/1.1583771.
Khrapov S.S., Khoperskov S.A., Khoperskov A.V. New features of parallel implementation of N-body problems on GPU. Bulletin of the South Ural State University, Series: Mathematical Modelling, Programming and Computer Software. 2018. Vol. 11, no. 1. P. 124–136. DOI: 10.14529/mmp180111.
Treecode guide. URL: https://www.ifa.hawaii.edu/barnes/treecode/treeguide.html (accessed: 30.11.2020).
Aarseth S.J. Gravitational N-Body Simulations Tools and Algorithms. Cambridge University Press, 2003. 431 p.
Kireyeu V., Aichelin J., Bratkovskaya E., Le Fevre A., Lenivenko V., Kolesnikov V., Leifels Y., Voronyuk V. PHQMD Model for the Formation of Nuclear Clusters and Hypernuclei in Heavy Ion. Bulletin of the Russian Academy of Sciences: Physics. 2020. Vol. 84. P. 957–961. DOI: 10.3103/S1062873820080171.
Zasov A.V., Moiseev A.V., Khoperskov A.V., Sidorova E.A. Early-type disk galaxies: structure and kinematics. Astronomy Reports. 2008. Vol. 52. P. 79–93. DOI: 10.1134/S1063772908020017.
Zasov A.V., Saburova A.S., Khoperskov A.V., Khoperskov S.A. Dark matter in galaxies. Advances in Physical Sciences. 2017. Vol. 60, no. 1. P. 3–39. DOI: 10.3367/UFNe.2016.03.037751.
Korolev V.V., Eremin M.A., Kovalenko I.G., Zankovich A.M. Numerical simulations of instability in the shell of a supernova remnant expanding in a weakly inhomogeneous interstellar medium. Mathematical Physics and Computer Simulation. 2020. Vol. 23, no. 3. P. 23—35. DOI: 10.15688/mpcm.jvolsu.2020.3.3.
DOI: http://dx.doi.org/10.14529/cmse210204