Solving Grid Equations Using the Alternating-triangular Method on a Graphics Accelerator

Alexander I. Sukhinov, Vladimir N. Litvinov, Alexander E. Chistyakov, Alla V. Nikitina, Nataliya N. Gracheva, Nelli B. Rudenko


The paper describes a parallel-pipeline implementation of solving grid equations using the modified alternating-triangular iterative method (MATM), obtained by numerically solving the equations of mathematical physics. The greatest computational costs at using this method are on the stages of solving a system of linear algebraic equations (SLAE) with lower triangular and upper non-triangular matrices. An algorithm for solving the SLAE with a lower triangular matrix on a graphics accelerator using NVIDIA CUDA technology is presented. To implement the parallel-pipeline method, a three-dimensional decomposition of the computational domain was used. It is divided into blocks along the y coordinate, the number of which corresponds to the number of GPU streaming multiprocessors involved in the calculations. In turn, the blocks are divided into fragments according to two spatial coordinates — x and z. The presented graph model describes the relationship between adjacent fragments of the computational grid and the pipeline calculation process. Based on the results of computational experiments, a regression model was obtained that describes the dependence of the time for calculation one MATM step on the GPU, the acceleration and efficiency for SLAE solution with a lower triangular matrix by the parallel-pipeline method on the GPU were calculated using the different number of streaming multiprocessors.

Ключевые слова

mathematical modeling; parallel algorithm; graphics accelerator

Полный текст:

PDF (English)


Sukhinov A.I., Atayan A.M., Belova Y.V., et al. Data processing of field measurements of expedition research for mathematical modeling of hydrodynamic processes in the Azov Sea. Computational Continuum Mechanics. 2020. Vol. 13, no. 2. P. 161–174. DOI: 10.7242/1999-6691/2020.13.2.13.

Sukhinov A.I., Litvinov V.N., Chistyakov A.E., et al. Computational aspects of solving grid equations in heterogeneous computing systems. Parallel Computing Technologies. Vol. 12942 / ed. by V. Malyshkin. Springer, 2021. P. 166–177. Lecture Notes in Computer Science. DOI: 10.1007/978-3-030-86359-3_13.

Lyupa A., Morozov D., Trapeznikova M., et al. Three-phase filtration modeling by explicit methods on hybrid computer systems. Mathematical Models and Computer Simulations. 2014. Vol. 6. P. 551–559. DOI: 10.1134/S2070048214060088.

Mat Ali N.A., Rahman R., Sulaiman J., Ghazali K. Solutions of reaction-diffusion equations using similarity reduction and HSSOR iteration. Indonesian Journal of Electrical Engineering and Computer Science. 2019. Vol. 16, no. 3. P. 1430–1438. DOI: 10.11591/ijeecs.v16.i3.pp1430-1438.

Kittisopaporn A., Chansangiam P. The steepest descent of gradient-based iterative method for solving rectangular linear systems with an application to Poisson’s equation. Advances in Difference Equations. 2020. Vol. 2020. Article number 259. DOI: 10.1186/s13662-020-02715-9.

Yifen K., Ma C. Adaptive parameter based matrix splitting iteration method for the large and sparse linear systems. Computers & Mathematics with Applications. 2022. Vol. 122. P. 19–27. DOI: 10.1016/j.camwa.2022.07.010.

Klimonov I.A., Korneev V.D., Sveshnikov V.M. Parallelization technologies for solving threedimensional boundary value problems on quasi-structured grids using the CPU+GPU hybrid computing environment. Numerical Methods and Programming. 2016. Vol. 17, no. 1. P. 65–71. DOI: 10.26089/NumMet.v17r107.

Ding P., Liu Z. Accelerating phase-field modeling of solidification with a parallel adaptive computational domain approach. International Communications in Heat and Mass Transfer. 2020. Vol. 111. P. 104452. DOI: 10.1016/j.icheatmasstransfer.2019.104452.

Molostov I., Scherbinin V. Application of NVIDIA CUDA Technology for Numerical Simulation of Electromagnetic Pulses Propagation. Izvestiya of Altai State University. 2015. Vol. 1, no. 1/1(85). DOI: 10.14258/izvasu(2015)1.1-06.

Krasnopolsky B., Medvedev A., Chulyunin A. On application of GPUs for modelling of hydrodynamic characteristics of screw marine propellers in OpenFOAM package. Proceedings of the Institute for System Programming of RAS. 2014. Vol. 26, no. 5. P. 155–172. DOI: 10.15514/ISPRAS-2014-26(5)-8.

Egorov M., Egorov S., Egorov D. Using graphics accelerator to improve computing performance in the numerical modeling of complex technical systems functioning. Perm National Research Polytechnic University Aerospace Engineering Bulletin. 2015. No. 40. P. 81– 91. DOI: 10.15593/2224-9982/2015.40.05.

Szenasi S. Solving the inverse heat conduction problem using NVLink capable Power architecture. PeerJ Computer Science. 2017. Vol. 3. P. 138. DOI: 10.7717/peerj-cs.138.

Zheng L., Gerya T., Knepley M., et al. GPU Implementation of Multigrid Solver for Stokes Equation with Strongly Variable Viscosity. GPU Solutions to Multi-scale Problems in Science and Engineering. Springer, 2013. P. 321–333. Lecture Notes in Earth System Sciences. DOI: 10.1007/978-3-642-16405-7_21.

Konovalov A. The steepest descent method with an adaptive alternating-triangular preconditioner. Differential Equations. 2004. Vol. 40. P. 1018–1028.

Sukhinov A.I., Chistyakov A.E., Litvinov V.N., et al. Computational Aspects of Mathematical Modeling of the Shallow Water Hydrobiological Processes. Numerical methods and programming. 2020. Vol. 21, no. 4. P. 452–469. DOI: 10.26089/NumMet.v21r436.

Samarskii A.A., Vabishchevich P.N. Numerical methods for solving convection-diffusion problems. Moscow: URSS, 2009. (in Russian).

Browning J.B., Sutherland B. C++20 Recipes. A Problem-Solution Approach. Berkeley, CA: Apress, 2020. 630 p.