Implementation Features of the TreeCode Algorithm for Solving N-body Problems on GPUs
DOI:
https://doi.org/10.14529/cmse210204Keywords:
N-body problem, Treecode, parallel computing, GPUsAbstract
Hierarchical methods for calculating gravitational forces in a N-body system significantly increase the quality of numerical simulations when solving various astrophysical problems by increasing the number of N elements, since we have the computational complexity N log(N) for the TreeCode approximate method instead of ∼O(N2) for the direct method, which allows to greatly increase the number of particles in the models. We developed new software for solving a dynamic problem with a large number of particles for modeling the collisionless components of the galaxies, in particular, stellar subsystem and dark matter. The paper presents the test results for the parallel implementation of the Treecode algorithm for the NVidia Tesla GPUs. To construct a hierarchical grid structure, we implemented a fast parallel octree-construction algorithm based on Morton’s space-filling curve. To assess the quality of the constructed numerical model, we use the simulation results based on the direct calculation of the interaction forces between all N particles of the system. We have compared the performance of the different implementations of algorithms for solving the N-body problem and an analisis of the fulfillment of the integral physical conservation laws of a self-gravitational system. The analysis of the fulfillment of the conservation laws of total energy and angular momentum is carried out for a rotating self-gravitating disk. Models with different criteria for a particle remoteness and value of the opening angle θ are considered.
References
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.
