Techniques, Tricks, and Algorithms for Efficient GPU-Based Processing of Higher Order Hyperbolic PDEs

doi:10.1007/s42967-022-00235-9

Abstract

Abstract: GPU computing is expected to play an integral part in all modern Exascale supercomputers. It is also expected that higher order Godunov schemes will make up about a significant fraction of the application mix on such supercomputers. It is, therefore, very important to prepare the community of users of higher order schemes for hyperbolic PDEs for this emerging opportunity.
Not every algorithm that is used in the space-time update of the solution of hyperbolic PDEs will take well to GPUs. However, we identify a small core of algorithms that take exceptionally well to GPU computing. Based on an analysis of available options, we have been able to identify weighted essentially non-oscillatory (WENO) algorithms for spatial reconstruction along with arbitrary derivative (ADER) algorithms for time extension followed by a corrector step as the winning three-part algorithmic combination. Even when a winning subset of algorithms has been identified, it is not clear that they will port seamlessly to GPUs. The low data throughput between CPU and GPU, as well as the very small cache sizes on modern GPUs, implies that we have to think through all aspects of the task of porting an application to GPUs. For that reason, this paper identifies the techniques and tricks needed for making a successful port of this very useful class of higher order algorithms to GPUs.
Application codes face a further challenge-the GPU results need to be practically indistinguishable from the CPU results-in order for the legacy knowledge bases embedded in these applications codes to be preserved during the port of GPUs. This requirement often makes a complete code rewrite impossible. For that reason, it is safest to use an approach based on OpenACC directives, so that most of the code remains intact (as long as it was originally well-written). This paper is intended to be a one-stop shop for anyone seeking to make an OpenACC-based port of a higher order Godunov scheme to GPUs.
We focus on three broad and high-impact areas where higher order Godunov schemes are used. The first area is computational fluid dynamics (CFD). The second is computational magnetohydrodynamics (MHD) which has an involution constraint that has to be mimetically preserved. The third is computational electrodynamics (CED) which has involution constraints and also extremely stiff source terms. Together, these three diverse uses of higher order Godunov methodology, cover many of the most important applications areas. In all three cases, we show that the optimal use of algorithms, techniques, and tricks, along with the use of OpenACC, yields superlative speedups on GPUs. As a bonus, we find a most remarkable and desirable result:some higher order schemes, with their larger operations count per zone, show better speedup than lower order schemes on GPUs. In other words, the GPU is an optimal stratagem for overcoming the higher computational complexities of higher order schemes. Several avenues for future improvement have also been identified. A scalability study is presented for a real-world application using GPUs and comparable numbers of high-end multicore CPUs. It is found that GPUs offer a substantial performance benefit over comparable number of CPUs, especially when all the methods designed in this paper are used.

Key words: PDEs, Numerical schemes, Mimetic, High performance computing

Sethupathy Subramanian, Dinshaw S. Balsara, Deepak Bhoriya, Harish Kumar. Techniques, Tricks, and Algorithms for Efficient GPU-Based Processing of Higher Order Hyperbolic PDEs[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2336-2384.

TrendMD

References

1. Balsara, D.S.: A two-dimensional HLLC Riemann solver with applications to Euler and MHD flows. J. Comp. Phys. 231, 7476-7503 (2012)
2. Balsara, D.S.: Divergence-free adaptive mesh refinement for magnetohydrodynamics. J. Comput. Phys. 174, 614-648 (2001)
3. Balsara, D.S.: Divergence-free reconstruction of magnetic fields and WENO schemes for magnetohydrodynamics. J. Comput. Phys. 228, 5040-5056 (2009)
4. Balsara, D.S.: Higher order accurate space-time schemes for computational astrophysics - Part I: finite volume methods. Liv. Rev. Computat. Astrophy. 3, 2 (2017). https:// doi. org/ 10. 1007/ s41115- 017- 0002-8
5. Balsara, D.S.: Multidimensional extension of the HLLE Riemann solver; application to Euler and magnetohydrodynamical flows. J. Comput. Phys. 229, 1970-1993 (2010)
6. Balsara, D.S.: Multidimensional Riemann problem with self-similar internal structure - Part I-application to hyperbolic conservation laws on structured meshes. J. Comput. Phys. 277, 163-200 (2014)
7. Balsara, D.S.: Second-order-accurate schemes for magnetohydrodynamics with divergence-free reconstruction. Astrophys. J. Suppl. 151, 149-184 (2004)
8. Balsara, D.S., Amano, T., Garain, S., Kim, J.: High order accuracy divergence-free scheme for the electrodynamics of relativistic plasmas with multidimensional Riemann solvers. J. Comput. Phys. 318, 169-200 (2016)
9. Balsara, D.S., Garain, S., Shu, C.-W.: An efficient class of WENO schemes with adaptive order. J. Comput. Phys. 326, 780-804 (2016)
10. Balsara, D.S., Meyer, C., Dumbser, M., Du, H., Xu, Z.: Efficient implementation of ADER schemes for Euler and magnetohydrodynamical flows on structured meshes - comparison with Runge-Kutta methods. J. Comput. Phys. 235, 934-969 (2013)
11. Balsara, D.S., Nkonga, B.: Formulating multidimensional Riemann solvers in similarity variables - Part III - a multidimensional analogue of the HLLI Riemann solver for conservative hyperbolic systems. J. Comput. Phys. 346, 25-48 (2017)
12. Balsara, D.S., Rumpf, T., Dumbser, M., Munz, C.-D., Efficient, high accuracy ADER-WENO schemes for hydrodynamics and divergence-free magnetohydrodynamics. J. Comput. Phys. 228, 2480-2516 (2009)
13. Balsara, D.S., Shu, C.-W.: Monotonicity preserving weighted non-oscillatory schemes with increasingly high order of accuracy. J. Comput. Phys. 160, 405-452 (2000)
14. Balsara, D.S., Spicer, D.S.: A staggered mesh algorithm using high order Godunov fluxes to ensure solenoidal magnetic fields in magnetohydrodynamic simulations. J. Comput. Phys. 149, 270-292 (1999)
15. Balsara, D.S., Taflove, A., Garain, S., Montecinos, G.: Computational electrodynamics in material media with constraint-preservation, multidimensional Riemann solvers and sub-cell resolution - part I, secondorder FVTD schemes. J. Comput. Phys. 349, 604-635 (2017)
16. Balsara, D.S., Taflove, A., Garain, S., Montecinos, G.: Computational electrodynamics in material media with constraint-preservation, multidimensional Riemann solvers and sub-cell resolution - part II, higherorder FVTD schemes. J. Comput. Phys. 354, 613-645 (2018)
17. Chandrasekaran, S., Juckeland, G.: OpenACC for Programmers: Concepts and Strategies. Addison-Wesley, Boston (2018)
18. Chapman, B., Jost, G., van der Pas, R.: Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press, Cambridge, MA (2008)
19. Colella, P.: Multidimensional upwind methods for hyperbolic conservation laws. J. Comput. Phys. 87, 171 (1990)
20. Dai, W., Woodward, P.R.: On the divergence-free condition and conservation laws in numerical simulations for supersonic magnetohydrodynamic flows. Astrophys. J. 494, 317-335 (1998)
21. Dumbser, M., Balsara, D.S.: A new, efficient formulation of the HLLEM riemann solver for general conservative and non-conservative hyperbolic systems. J. Comput. Phys. 304, 275-319 (2016)
22. Dumbser, M., Balsara, D.S., Toro, E.F., Munz, C.-D.: A unified framework for the construction of onestep finite volume and discontinuous Galerkin schemes on unstructured meshes. J. Comput. Phys. 227, 8209-8253 (2008)
23. Dumbser, M., Zanotti, O., Hidalgo, A., Balsara, D.S.: ADER-WENO Finite volume schemes with spacetime adaptive mesh refinement. J. Comput. Phys. 248, 257-286 (2013)
24. Einfeldt, B., Munz, C.-D., Roe, P.L., Sjogreen, B.: On Godunov-type methods near low densities. J. Comput. Phys. 92, 273-295 (1991)
25. Garain, S., Balsara, D.S., Reid, J.: Comparing Coarray Fortran (CAF) with MPI for several structured mesh PDE applications. J. Comput. Phys. 297, 237-253 (2015)
26. Godunov, S.K.: Finite difference methods for the computation of discontinuous solutions of the Equations of Fluid Dynamics. Mathematics of the USSR, Sbornik. 47, 271-306 (1959)
27. Harten, A., Engquist, B., Osher, S., Chakravarthy, S.: Uniformly high order essentially non-oscillatory schemes III. J. Comput. Phys. 71, 231-303 (1987)
28. Harten, A., Lax, P.D., van Leer, B.: On upstream differencing and Godunov-type schemes for hyperbolic conservation laws. SIAM Rev. 25, 289-315 (1983)
29. Jiang, G.-S., Shu, C.-W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202- 228 (1996)
30. Roe, P.L.: Approximate Riemann solver, parameter vectors and difference schemes. J. Comput. Phys. 43, 357-372 (1981)
31. Rusanov, V.V.: Calculation of interaction of non-steady shock waves with obstacles. J. Comput. Math. Phys. USSR 1, 267 (1961)
32. Ryu, D., Miniati, F., Jones, T.W., Frank, A.: A divergence-free upwind code for multidimensional magnetohydrodynamic flows. Astrophys. J. 509, 244-255 (1998)
33. Shu, C.-W.: Total variation-diminishing time discretizations. SIAM J Sci. Stat. Comput. 9, 1073-1084 (1988)
34. Shu, C.-W., Osher, S.J.: Efficient implementation of essentially non-oscillatory shock capturing schemes. J. Comput. Phys. 77, 439-471 (1988)
35. Shu, C.-W., Osher, S.J.: Efficient implementation of essentially non-oscillatory shock capturing schemes II. J. Comput. Phys. 83, 32-78 (1989)
36. Subramanian, S., Balsara, D.S., Gagne, M., A.: ud-Doula, Modeling magnetic massive stars in 3D i: isothermal simulations of a magnetic O star. Month. Note. Royal Astronom. Soc. 515(1), 237-255 (2022)
37. Titarev, V.A., Toro, E.F.: ADER: arbitrary high order Godunov approach. J. Sci. Comput. 17(1/2/3/4), 609-618 (2002)
38. Titarev, V.A., Toro, E.F.: ADER schemes for three-dimensional nonlinear hyperbolic systems. J. Comput. Phys. 204, 715-736 (2005)
39. Toro, E.F., Spruce, M., Speares, W.: Restoration of contact surface in the HLL Riemann solver. Shock Waves 4, 25-34 (1994)
40. Toro, E.F., Titarev, V.A.: Solution of the generalized Riemann problem for advection reaction equations. Proc. R. Soc. Lond. Ser. A 458, 271-281 (2002)
41. Van Leer, B.: Toward the ultimate conservative difference scheme. V. A second-order sequel to Godunov’s method. J. Comput. Phys. 32, 101-136 (1979)
42. Woodward, P., Colella, P.: The numerical simulation of two-dimensional fluid flow with strong shocks. J. Comput. Phys. 54, 115-173 (1984)

[1]	Young Kyu Lee, Shingyu Leung. A Simple Embedding Method for the Laplace-Beltrami Eigenvalue Problem on Implicit Surfaces [J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1189-1216.
[2]	Zhanhong Ye, Xiang Huang, Hongsheng Liu, Bin Dong. Meta-Auto-Decoder: a Meta-Learning-Based Reduced Order Model for Solving Parametric Partial Differential Equations [J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 1096-1130.
[3]	Dinshaw S. Balsara, Deepak Bhoriya, Chi-Wang Shu, Harish Kumar. Efficient Finite Difference WENO Scheme for Hyperbolic Systems with Non-conservative Products [J]. Communications on Applied Mathematics and Computation, 2024, 6(2): 907-962.
[4]	Ernie Tsybulnik, Xiaozhi Zhu, Yong-Tao Zhang. Efficient Sparse-Grid Implementation of a Fifth-Order Multi-resolution WENO Scheme for Hyperbolic Equations [J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1339-1364.
[5]	Dinshaw S. Balsara, Saurav Samantaray, Sethupathy Subramanian. Efficient WENO-Based Prolongation Strategies for Divergence-Preserving Vector Fields [J]. Communications on Applied Mathematics and Computation, 2023, 5(1): 428-484.
[6]	Dinshaw S. Balsara, Roger Käppeli, Walter Boscheri, Michael Dumbser. Curl Constraint-Preserving Reconstruction and the Guidance it Gives for Mimetic Scheme Design [J]. Communications on Applied Mathematics and Computation, 2023, 5(1): 235-294.
[7]	Dinshaw S. Balsara, Roger Käppeli. Von Neumann Stability Analysis of DG-Like and PNPM-Like Schemes for PDEs with Globally Curl-Preserving Evolution of Vector Fields [J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 945-985.
[8]	Hendrik Ranocha, Katharina Ostaszewski, Philip Heinisch. Discrete Vector Calculus and Helmholtz Hodge Decomposition for Classical Finite Diference Summation by Parts Operators [J]. Communications on Applied Mathematics and Computation, 2020, 2(4): 581-611.
[9]	Zhiping Mao, Zhen Li, George Em Karniadakis. Nonlocal Flocking Dynamics: Learning the Fractional Order of PDEs from Particle Simulations [J]. Communications on Applied Mathematics and Computation, 2019, 1(4): 597-619.