betaFeedback

WorksPhysics and Astronomy

A semi-Lagrangian discontinuous Galerkin method for drift-kinetic simulations on GPUs

Abstract

In this paper, we demonstrate the efficiency of using semi-Lagrangian discontinuous Galerkin methods to solve the drift-kinetic equation using graphic processing units (GPUs). In this setting we propose a second order splitting scheme and a 2d semi-Lagrangian scheme in the poloidal plane. The resulting method is able to conserve mass up to machine precision, allows us to take large time steps due to the absence of a CFL condition and provides local data dependency which is essential to obtain good performance on state-of-the art high-performance computing systems. We report simulations of a drift-kinetic ion temperature gradient (ITG) instability and show that our implementation achieves a performance of up to 600 GB/s on an A100 GPU.

Introduction

Kinetic equations have proven to be excellent models to understand the behavior of plasma. For plasmas with strong magnetic fields (such as in tokamaks), the full 6 dimensional Vlasov–Poisson or Vlasov–Maxwell simulation can be reduced to the 5d gyrokinetic (3d in space and 2d in velocity), see e.g. [24], or the 4d drift-kinetic equations (3d in space and 1d in velocity), see e.g. [19].

Semi-Lagrangian schemes [28] are in many cases the preferred choice for solving kinetic equations since these methods do not suffer from the same stability limitations as Eulerian methods (finite differences, finite volumes), see e.g. [18]. Moreover, these schemes allow, in general, more accurate results, assuming one is willing to pay the computational cost, than particle in cell methods (PIC), which introduce numerical noise especially in low density regions, see e.g. [29].

Often semi-Lagrangian methods are combined with splitting schemes [6, 8, 16, 17], which allows us to reduce the complexity of the full nonlinear equations to a sequence of usually linear lower dimensional problems. This permits us to design and use highly efficient methods that are tailored to these simpler sub-problems. It should be noted that for a large class of equations, for example the Vlasov–Poisson model, the problem can be reduced to a sequence of one dimensional advective equations. However, this is not the case for the drift-kinetic model, where a 2d splitting substep has to be retained in order to resolve the characteristic in the poloidal (perpendicular to the magnetic field lines) plane accurately without introducing a large splitting error, see e.g. [19, 4].

The main idea of semi-Lagrangian schemes is to follow the characteristics backward or forward in time. Since the foot of the characteristics usually does not coincide with a grid point, an interpolation technique has to be applied, see e.g. [28]. Among the various interpolation techniques, cubic splines are often the favored option because they provide accurate results and introduce very little numerical diffusion [18]. However, since in the high-dimensional setting of kinetic equations often large supercomputers are required, global methods such as spline interpolation impose significant difficulties to achieve good performance [13]. This is an even more serious issue on GPUs which are currently used extensively in high-performance computing (HPC). Consequently, local methods such as the semi-Lagrangian discontinuous Galerkin (SLDG) schemes have proven to be advantageous on GPUs [14, 15]. In fact, we are not aware of a standard spline construction (i.e. by solving tridiagonal linear systems) for semi-Lagrangian methods that has been implemented on GPUs. However, let us mention that local spline methods, as in [22], or high-order finite difference approximations of the required derivatives for constructing splines, as in [27], have been implemented on GPUs. In [25] spline based interpolation is foregone in favor of the more easily parallelizable but more diffusive polynomial interpolation. In [21] a massively parallel implementation (on CPU hardware) also uses polynomial interpolation.

To tackle the 2d advective sub-problem in the splitting scheme, often a so-called backward semi-Lagrangian (BSL) scheme is applied where in the reconstruction step a cubic spline is used [19]. This method does not conserve the mass of the system, which might lead to unphysical long time simulation results. Recently, a 2d semi-Lagrangian discontinuous Galerkin method has been developed in [1, 2, 3]. This method, besides conserving the mass exactly up to machine precision, is also local in contrast to the BSL scheme. Currently, to the best of our knowledge, no GPU implementation of this method exists, and it is not clear in advance if a reasonable performance on GPUs is possible. In this paper, we demonstrate that this goal can be achieved. Note that in [11] a conservative scheme for the 2d problem has already been introduced. However, although better conservation properties than with the BSL method are achieved, mass is still not conserved up to machine precision. Hence, our implementation is the first splitting based scheme that achieves mass conservation up to machine precision. Moreover, a first order splitting scheme is used in [11], which we will extend to second order in this paper.

In most applications, the only metric of interest in HPC for high-dimensional kinetic equations in plasma physics is weak scaling. That is, problem size and computing resources are increased simultaneously and the execution time should not rise drastically. This is crucial since small-scale structures appear in plasma (this phenomenon is called filamentation) which can not be captured with low resolutions. Therefore, the size of the problem typically scales with the number of available resources. The goal of this paper is to demonstrate efficient single-node performance, which is the first step in developing an efficient and scalable code. Hence, the code used in this work, which is available at https://bitbucket.org/leinkemmer/sldg, can run both on multi-core shared memory CPU-based systems, and on single GPUs. We mainly use an A100 GPU and a dual-socket Intel Xeon Gold 6226R CPU, where we exploit all computational and memory resources of the underlying systems. We use OpenMP for the parallelization on the two CPUs and CUDA to parallelize on the GPU. This allows us to run simulations with a moderate resolution of approximately 200 grid points in each dimension on both platforms. For higher resolutions or an extension of the code to the 5d gyrokinetic equations [24], a (cuda-aware) MPI implementation has to be considered in order to deal with the increasing memory requirements. This will be considered as future work.

This article is organized as follows. At first, we introduce the drift-kinetic model, then we describe the time splitting method and the numerical methods used in the splitting steps. Finally, we report the results of the simulation and analyze the performance of our code.

Problem description

We are interested in solving the 4d drift-kinetic equation in cylindrical coordinates [19],

∂tf−∂θϕr∂rf+∂rϕr∂θf+v∂zf−∂zϕ∂vf=0(1)\partial_t f-\frac{\partial_\theta\phi}{r}\partial_r f+\frac{\partial_r\phi}{r}\partial_\theta f+v\partial_z f-\partial_z\phi\partial_v f=0 \tag*{(1)}

on the domain (r,θ,z,v)∈Ω×[0,L]×[−vmax⁡,vmax⁡](r,\theta,z,v)\in\Omega\times[0,L]\times[-v_{\max},v_{\max}], with Ω=[rmin⁡,rmax⁡]×[0,2π]\Omega=[r_{\min},r_{\max}]\times[0,2\pi], and where ϕ=ϕ(r,θ,z)\phi=\phi(r,\theta,z) solves the quasi neutrality equation,

−[∂r2ϕ+(1r+∂rn0(r)n0(r))∂rϕ+1r2∂θ2ϕ]+1Te(r)(ϕ−⟨ϕ⟩)=1n0(r)∫Rf dv−1.(2)-\left[\partial_r^2\phi+\left(\frac{1}{r}+\frac{\partial_r n_0(r)}{n_0(r)}\right)\partial_r\phi+\frac{1}{r^2}\partial_\theta^2\phi\right]+\frac{1}{T_e(r)}\left(\phi-\langle\phi\rangle\right)=\frac{1}{n_0(r)}\int_{\mathbb{R}}f\,\mathrm{d}v-1. \tag*{(2)}

For the quasi neutrality equation, periodic boundary conditions in (θ,z)(\theta,z), homogeneous Dirichlet boundary conditions in rmax⁡r_{\max} and homogeneous Neumann boundary conditions at rmin⁡r_{\min} are considered, i.e., we enforce no poloidal rotation of the plasma at rmin⁡r_{\min}.

In order to solve (1), we first rewrite it in its conservative form by multiplying the solution with the Jacobian of the transformation from the Cartesian to the polar coordinate system in the poloidal plane. Thus we consider g(t,r,θ,z,v)=rf(t,r,θ,z,v)g(t,r,\theta,z,v)=rf(t,r,\theta,z,v) and gg satisfies

∂tg−∂r(∂θϕrg)+∂θ(∂rϕrg)+∂z(vg)−∂v(∂zϕg)=0.\partial_tg-\partial_r\left(\frac{\partial_\theta\phi}{r}g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}g\right)+\partial_z(vg)-\partial_v(\partial_z\phi g)=0.

Additionally, since gg can be written as g(t)=geq+δg(t)g(t)=g_{\mathrm{eq}}+\delta g(t), i.e., as a sum of a steady state solution of the system and a perturbation, where geq=rfeqg_{\mathrm{eq}}=rf_{\mathrm{eq}}, it is possible to work with δg\delta g instead of gg. This is done to avoid problems with boundary conditions in the radial direction, similar difficulties are observed in [10, 11, 19]. Thus, we are interested to solve

∂tδg−∂r(∂θϕrδg)+∂θ(∂rϕrδg)+∂z(vδg)−∂v(∂zϕδg)−∂θϕ∂r(geqr)−∂zϕ∂vgeq=0,(3)\partial_t\delta g-\partial_r\left(\frac{\partial_\theta\phi}{r}\delta g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}\delta g\right)+\partial_z(v\delta g)-\partial_v(\partial_z\phi\delta g)-\partial_\theta\phi\partial_r\left(\frac{g_{\mathrm{eq}}}{r}\right)-\partial_z\phi\partial_vg_{\mathrm{eq}}=0, \tag*{(3)}

where two additional source terms regarding the equilibrium function appear. To ensure mass conservation up to machine precision, we set the velocity field component in the radial direction at rmin⁡r_{\min} to zero. Numerical experiments have shown that this slight modification has no significant impact on the obtained results since the velocity field is anyhow close to zero at this boundary. Due to the homogeneous Dirichlet boundary conditions imposed for the quasi neutrality equation at rmax⁡r_{\max}, the velocity field in the radial direction is automatically zero at rmax⁡r_{\max}. Since both δg\delta g and the electric potential decay fast enough towards the radial endpoints and the velocity field is forced to be zero there, no boundary conditions for δg\delta g in this direction have to be imposed. In the θ\theta, zz, and vv dimension periodic boundary conditions are considered. Note that, when working with δg\delta g, the right-hand side of the quasi neutrality equation (2) can be computed as

1n0(r)∫(feq+δf) dv−1=1n0(r)∫δf dv=1r⋅n0(r)∫δg dv.\frac{1}{n_0(r)} \int(f_{\mathrm{eq}}+\delta f)\,\mathrm{d}v - 1 = \frac{1}{n_0(r)} \int\delta f\,\mathrm{d}v = \frac{1}{r\cdot n_0(r)} \int\delta g\,\mathrm{d}v.

Numerical methods and implementation

Time splitting

To solve the drift-kinetic equation numerically, splitting methods are often used, see [11, 19] for example, to overcome the complexity of the whole problem. This allows us to treat the different parts of the equation separately. The advantage of such a procedure is that highly efficient numerical algorithms which are tailored to the simpler subproblems can be used. The drawback of such splitting methods is that, in general, an error in time is introduced. A significant amount of work can be found in the literature that is concerned with the improvement and analysis of splitting methods, see e.g. [8, 16, 17].

The main parts (subflows) of the splitting algorithm in the drift-kinetic setting considered in this work are as follows

  • Solve the quasi neutrality equation and compute the derivatives of the potential ϕ\phi to obtain the electric field.

  • Perform the 1d advection in the zz direction with a semi-Lagrangian method, i.e., solve

∂tδg+∂z(v δg)=0.(4)\partial_t\delta g+\partial_z(v\,\delta g)=0. \tag*{(4)}
  • Perform the 1d advection in the vv direction with a semi-Lagrangian method, i.e., solve

∂tδg−∂v(∂zϕ δg)=0.(5)\partial_t\delta g-\partial_v(\partial_z\phi\,\delta g)=0. \tag*{(5)}
  • Perform the 2d advection in the rr and θ\theta direction with a semi-Lagrangian method, i.e., solve

∂tδg−∂r(∂θϕrδg)+∂θ(∂rϕrδg)=0.(6)\partial_t\delta g-\partial_r\left(\frac{\partial_\theta\phi}{r}\delta g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}\delta g\right)=0. \tag*{(6)}
  • Treat the source terms, i.e., solve

∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0.\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_v g_{\mathrm{eq}}=0.

Those five steps can be combined to obtain splitting schemes of various order. The initial condition of those five steps is the solution obtained in the previous step of the splitting procedure. The step size of each step varies according to the splitting method.

Before proceeding let us emphasize that we treat the advection in the poloidal plane, i.e. in (r,θ)(r,\theta), as a 2d problem. It is possible, in principle, to split (6) into two 1d problems, where again a conservative SLDG scheme can be applied. This is commonly done for the Vlasov–Poisson equations, see e.g. [28]. However, since the advection speed in (6) is not constant with respect to its direction, a less efficient method than will be described for (4) and (5) has to be implemented. In the case of a varying advection speed, space-dependent matrices have to be constructed, while in the constant case, just one matrix is required. Moreover, drift-kinetic problems commonly show turbulent structures in the poloidal plane, and thus the direction of advection changes appreciably from one point to another. Performing a further splitting then introduces a splitting error that often mandates a relatively small time step size. This is not an issue in the toroidal direction as the solution largely follows the generally well-behaved magnetic field lines. It should also be noted that, as is observed in [4], order reduction can appear in splitting advections with variable advection speed.

In this work, we will use two methods. A first order scheme, see algorithm 1, that was already considered in [11]. This scheme fails to be second order because the electric field that is used to trace the characteristics is not a sufficiently accurate approximation at half the time step. This can be easily checked by a local truncation error analysis.

We propose the second order scheme in algorithm 2 that is based on a corrector-predictor strategy. In the Strang splitting scheme of the corrector step, the full time step is taken for the advection in the poloidal plane, which is expected to be the most costly part of the algorithm.

Algorithm 1 First order splitting scheme

  1. solve the quasi neutrality equation to obtain ϕn\phi^n from δgn\delta g^n. Then, compute the velocity field and the invariants of the system,

  2. treat the source term ∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_vg_{\mathrm{eq}}=0 with step size Δt/2\Delta t/2,

  3. solve the 1d advection ∂tδg+∂z(v δg)=0\partial_t\delta g+\partial_z(v\,\delta g)=0 with step size Δt/2\Delta t/2,

  4. solve the 1d advection ∂tδg−∂v(∂zϕ δg)=0\partial_t\delta g-\partial_v(\partial_z\phi\,\delta g)=0 with step size Δt/2\Delta t/2 to get δg∗\delta g^*,

  5. solve the quasi neutrality with right-hand side 1n0(r)∫δg∗ dv\frac{1}{n_0(r)}\int\delta g^*\,dv in order to compute the potential ϕ∗\phi^* to obtain the velocity field, which is used in the remaining steps,

  6. solve the 2d advection ∂tδg−∂r(∂θϕrδg)+∂θ(∂rϕrδg)=0\partial_t\delta g-\partial_r\left(\frac{\partial_\theta\phi}{r}\delta g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}\delta g\right)=0 with step size Δt\Delta t,

  7. solve the 1d advection ∂tδg−∂v(∂zϕ δg)=0\partial_t\delta g-\partial_v(\partial_z\phi\,\delta g)=0 with step size Δt/2\Delta t/2,

  8. solve the 1d advection ∂tδg+∂z(v δg)=0\partial_t\delta g+\partial_z(v\,\delta g)=0 with step size Δt/2\Delta t/2,

  9. treat the source term ∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_vg_{\mathrm{eq}}=0 with step size Δt/2\Delta t/2.

Algorithm 2 Second order splitting scheme

  1. solve the quasi neutrality equation to obtain ϕn\phi^n from δgn\delta g^n. Then, compute the velocity field and the invariants of the system,

Predictor step, using ϕn\phi^n

  1. treat the source term ∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_v g_{\mathrm{eq}}=0 with step size Δt/2\Delta t/2 and initial condition δgn\delta g^n,

  2. solve the 1d advection ∂tδg+∂z(vδg)=0\partial_t\delta g+\partial_z(v\delta g)=0 with step size Δt/2\Delta t/2,

  3. solve the 1d advection ∂tδg−∂v(∂zϕδg)=0\partial_t\delta g-\partial_v(\partial_z\phi\delta g)=0 with step size Δt/2\Delta t/2,

  4. solve the 2d advection ∂tδg−∂r(∂θϕrδg)+∂θ(∂rϕrδg)=0\partial_t\delta g-\partial_r\left(\frac{\partial_\theta\phi}{r}\delta g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}\delta g\right)=0 with step size Δt/2\Delta t/2 by using a first order characteristic tracing method to obtain δgn+1/2\delta g^{n+1/2},

  5. solve the quasi neutrality equation to obtain ϕn+1/2\phi^{n+1/2} from δgn+1/2\delta g^{n+1/2}. Then, compute the velocity field,

Corrector step, using ϕn+1/2\phi^{n+1/2}

  1. treat the source term ∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_v g_{\mathrm{eq}}=0 with step size Δt/2\Delta t/2 with initial condition δgn\delta g^n,

  2. solve the 1d advection ∂tδg+∂z(vδg)=0\partial_t\delta g+\partial_z(v\delta g)=0 with step size Δt/2\Delta t/2,

  3. solve the 1d advection ∂tδg−∂v(∂zϕδg)=0\partial_t\delta g-\partial_v(\partial_z\phi\delta g)=0 with step size Δt/2\Delta t/2,

  4. solve the 2d advection ∂tδg−∂r(∂θϕrδg)+∂θ(∂rϕrδg)=0\partial_t\delta g-\partial_r\left(\frac{\partial_\theta\phi}{r}\delta g\right)+\partial_\theta\left(\frac{\partial_r\phi}{r}\delta g\right)=0 with step size Δt\Delta t by using a second order characteristic tracing method,

  5. solve the 1d advection ∂tδg−∂v(∂zϕδg)=0\partial_t\delta g-\partial_v(\partial_z\phi\delta g)=0 with step size Δt/2\Delta t/2,

  6. solve the 1d advection ∂tδg+∂z(vδg)=0\partial_t\delta g+\partial_z(v\delta g)=0 with step size Δt/2\Delta t/2,

  7. treat the source term ∂tδg−∂θϕ∂r(geq/r)−∂zϕ∂vgeq=0\partial_t\delta g-\partial_\theta\phi\partial_r(g_{\mathrm{eq}}/r)-\partial_z\phi\partial_v g_{\mathrm{eq}}=0 with step size Δt/2\Delta t/2, to obtain δgn+1\delta g^{n+1}, which is a second order solution in time.

Approximation space

To approximate functions u(tn,x)≈un(x)u(t^n,x)\approx u^n(x) in space, a discontinuous Galerkin representation is considered. In 1d, Lagrangian functions that interpolate at Gauss–Legendre points are used as (orthogonal) basis functions. A function uu (in 1d) is then approximated as follows

un(x)≈∑i=1N∑j=1k+1un(xi,j)φi,j(x),u^n(x)\approx\sum_{i=1}^{N}\sum_{j=1}^{k+1}u^n(x_{i,j})\varphi_{i,j}(x),

where kk is the degree of the polynomial approximation, xi,jx_{i,j} is the jjth Gauss–Legendre point scaled to cell ii and where φij\varphi_{ij} is the Lagrange basis function corresponding to the point xi,jx_{i,j}. Note that φij\varphi_{ij} are non-zero only in cell ii. Therefore the degrees of freedom are the values of the function at the Gauss–Legendre points. For higher dimensional problems tensor products of the 1d basis functions are used. Therefore, for example in 2d, the domain is divided into rectangular cells and the basis functions in each cell (i,j)(i,j) are

φij,m(x,y)=φi,p(x)φj,q(y),\varphi_{ij,m}(x,y)=\varphi_{i,p}(x)\varphi_{j,q}(y),

where m=m(p,q)m=m(p,q) is a linearized index of (p,q)(p,q). This can be extended to arbitrary dimensions. Thus, for the problem considered here in the 4d4d setting, the domain is divided into four dimensional cells. In each such cell the density function is approximated by a polynomial.

Semi-Lagrangian discontinuous Galerkin in 1d with constant coefficients

To solve the two 1d1d advection problems (4) and (5), a semi-Lagrangian discontinuous Galerkin method is used. Since the advection speed for the two 1d1d advections in consideration does not depend on the direction where the advection takes place, an extremely efficient algorithm can be derived. For each degree of freedom in the 3d3d subspace where the advection is not performed, the following problem has to be solved,

∂tu+∂x(au)=0.(7)\partial_t u+\partial_x(au)=0. \tag*{(7)}

Note that with an advection velocity that does not depend on (t,x)(t,x) we can pass from the conservative to the advective form of the transport equation without any additional considerations. The exact solution of this problem is known, namely u(t,x)=u0(x−at)u(t,x)=u_0(x-at), which can be derived with the method of characteristics. The numerical scheme uses the same idea, namely following the characteristics backward in time. However, since the endpoint of a characteristic curve does not necessarily coincide with a grid point, an interpolation technique has to be applied. In our case, since the approximation space consists of piecewise polynomial functions which are discontinuous at the cell interface, the shifted function is no longer a continuous polynomial in the cells. Therefore, an L2L^2 projection is applied in order to remain in the approximation space. The idea of this method is shown in Figure 1.

Image not extracted

Figure 1. Illustration of the one dimensional semi-Lagrangian discontinuous Galerkin method. When the advective step is completed (figure in the middle), the solution is projected back to the approximation space (red curve in the right figure).

To derive the variational form, the following theorem can be used,

∂t(∫Ai(t)u(t,x)φ(t,x) dx)=0,(8)\partial_t\left(\int_{A_i(t)}u(t,x)\varphi(t,x)\,\mathrm{d}x\right)=0, \tag*{(8)}

where Ai(t)A_i(t) is the moving Lagrangian cell in time and where φ\varphi solves the adjoint problem,

∂tφ+a∂xφ=0,φ(tn+1) is given.(9)\partial_t\varphi+a\partial_x\varphi=0,\qquad\varphi(t^{n+1})\text{ is given}. \tag*{(9)}

For a proof we refer to [20]. Then evaluating (8) at time tnt^n and tn+1t^{n+1} gives

∫Aiun+1φ(tn+1,x) dx=∫Ai(tn)unφ(tn,x) dx.(10)\int_{A_i} u^{n+1}\varphi(t^{n+1},x)\,\mathrm{d}x = \int_{A_i(t^n)} u^n\varphi(t^n,x)\,\mathrm{d}x. \tag*{(10)}

Since in the one dimensional case the advection speed is constant, Ai(tn)A_i(t^n) and φ(tn,x)\varphi(t^n,x) can be determined exactly and are just shifted versions of their initial conditions. As a consequence, Ai(tn)A_i(t^n) overlaps always with at most two underlying Eulerian cells and in order to find those cells, following the endpoints of the interval AiA_i along the characteristic is sufficient. This results in the following algorithm

ui,:n+1=A(a)ui∗,:n+B(a)ui∗+1,:n,(11)u_{i,:}^{n+1}=A(a)u_{i^*,:}^n+B(a)u_{i^*+1,:}^n, \tag*{(11)}

where A(a)A(a) and B(a)B(a) are small matrices of size (k+1)×(k+1)(k+1)\times(k+1) and kk is the degree of the polynomial used. The index i∗i^* gives the cell where the left endpoint of the interval A(tn)A(t^n) lies after following the characteristics. These matrices do depend only on the advection speed and can thus be precomputed. See [12] for more details about the derivation of the method and the form of the matrix. The method is of order k+1k+1 in space and is mass and momentum conservative by construction. Moreover, since the advection speed is constant and the characteristics can be computed analytically and never cross, this scheme is unconditionally stable. Furthermore, comparable and in some cases even less numerical diffusion is introduced than by cubic splines, see [13].

This method can be implemented extremely efficiently. In each step, all degrees of freedom have to be read and written once, and for each cell just the sum of two small matrix-vector products has to be performed. Moreover, since only two adjacent cells are required to compute the values of a cell at the next time step, this scheme can be efficiently and easily parallelized and is thus interesting from a high performance computing point of view. More details about the efficiency of the implementation on multi-core CPU and GPU based systems can be found in [13, 14, 15].

Semi-Lagrangian discontinuous Galerkin in 2d

To solve the 2d advection (6), again a semi-Lagrangian discontinuous Galerkin method is used. This recently developed method in [2] conserves mass up to machine precision, which is not the case for the standard backward semi-Lagrangian method used in [19]. This is an important property, especially for long time simulations, as it helps to obtain physically relevant results and to improve the quality of the solution. We recall in the following the main ideas of the method developed in [2, 23], which is used to solve (6).

We are interested to solve problems of the following form,

∂tu+∂x(a(t,x,y)u)+∂y(b(t,x,y)u)=0.(12)\partial_t u+\partial_x\left(a(t,x,y)u\right)+\partial_y\left(b(t,x,y)u\right)=0. \tag*{(12)}

Similarly as in 1d, the 2d extensions of equations (8) and (9) are used to derive the variational form

∫Aiju(tn+1,x,y)φ(tn+1,x,y) dxdy=∫Aij(tn)u(tn,x,y)φ(tn,x,y) dxdy.(13)\int_{A_{ij}}u(t^{n+1},x,y)\varphi(t^{n+1},x,y)\,\mathrm{d}x\mathrm{d}y=\int_{A_{ij}(t^n)}u(t^n,x,y)\varphi(t^n,x,y)\,\mathrm{d}x\mathrm{d}y. \tag*{(13)}

where the velocity field in our case depends on tt, xx, and yy. This implies that additional difficulties arise since we can not compute, in general, exactly the upstream cell Aij(tn)A_{ij}(t^n), see the left picture in Figure 2, and the analytical solution of the adjoint problem, φ(tn,x,y)\varphi(t^n,x,y), is not known in general.

Image not extracted

Figure 2. Illustration of the SLDG 2d algorithm. Left picture: Tracing the characteristics of the corner points of AijA_{ij} (gray arrow), then, Aij∗A^*_{ij} is created by connecting the corner points with straight lines (red dashed lines), which is a second order approximation of Aij(t)A_{ij}(t) (red lines). Right picture: The intersection points with the Eulerian grid cells have to be found (black crosses), and finally, the coefficients (18) are computed by integrating over Aij,rs∗A^*_{ij,rs} and using Green’s theorem (cyan arrows).

To find the upstream cell by following the corner points of an Eulerian grid cell along the characteristics back in time and connecting them with straight lines introduces an error of order two in space. There exist several strategies to obtain a higher order approximation of the upstream cell, for example, using higher order polynomial approximations of the faces, see [2], or using so called Eulerian-Lagrangian schemes, which introduce additional terms to correct the error which is coming from the boundary, see [5]. Let us note that the error in space for semi-Lagrangian schemes is related to the error in time when tracing the characteristics. Since we are working with an at most second order in time splitting method, we expect to get at most an error of order two in space. Therefore, we use quadrilaterals in this article to approximate the upstream cells and polynomial approximations of order two. We denote the approximated upstream cell by Aij∗A^*_{ij}. Let us mention that if the characteristics can be traced exactly, in general large time steps can be taken. However, if this is not the case, which happens for example in problems where the velocity field is not analytically available, approximations of the characteristics have to be computed. This leads to time step restrictions due to a loss of accuracy and even stability problems might appear if the approximated characteristics cross each other. By using higher order methods to trace the characteristics, as is done in [1], large time steps can be used.

To solve the adjoint problem, some points of the cell are chosen and the characteristics are then followed backward in time starting from those points. Since the solution stays constant on these points, φ(tn,x,y)\varphi(t^n,x,y) is then approximated by a polynomial φ∗(x,y)\varphi^*(x,y) with an appropriate strategy.

Lagrange vs Legendre basis functions

For discontinuous Galerkin approximations in 2d, if the domain is divided into quadrilaterals, polynomials in Pk\mathbb{P}^k are enough to get a method of order k+1k+1 (in contrast to finite element approximations, see [26]). Therefore, as basis often Legendre polynomials are used due to their favorable orthogonality properties. Also in [2], the algorithm is implemented in this way.

In this work, we use tensor products of Lagrange functions, as explained previously, as a basis for the two dimensional subspace. This is done to have a consistent representation along all four dimensions. In the literature, this polynomial space is often referred as Qk\mathbb{Q}^k, which is larger than Pk\mathbb{P}^k, since it has in two dimensions (k+1)2(k+1)^2 degrees of freedom in each cell in contrast to (k+1)(k+2)/2(k+1)(k+2)/2. This implies that more memory is required and this is consequently an issue for high dimensional problems. However, since more degrees of freedom are used, in general the resulting error is also lower, as has been observed in [4]. In this article, we use k=1k=1.

For different basis functions in the 2d SLDG method, different strategies to find approximations of the adjoint problem φ(tn,x,y)\varphi(t^n,x,y) have to be applied. For Legendre basis functions (as considered in [2]), the four corner points of the cell are traced along the characteristics backward in time. Since the solution of the adjoint problem (2d extension of (9)) stays constant at the characteristics, an approximating polynomial of the solution can be constructed. As explained above, a second order method results in three degrees of freedom in each cell. Therefore, more backward traced points (four) than degrees of freedom (three) are given and consequently a least square strategy is applied to minimize the error for the constructed approximating polynomial.

By applying a similar strategy that uses the corner points when Lagrange polynomials are used, we observe numerical instabilities when the upstream cell is no longer a rectangle, i.e., we observe wrong and fast increasing slopes of the polynomial in each cell. Thus, instead of using the corner points of the upstream cell, we use the four points (ξmn,ηmn)m=1,…,4(\xi_m^n,\eta_m^n)_{m=1,\ldots,4} that are obtained by tracing the characteristics back in time starting from the Gauss–Legendre nodes (ξmn+1,ηmn+1)m=1,…,4(\xi_m^{n+1},\eta_m^{n+1})_{m=1,\ldots,4} of a cell. Then, we solve a small 4×44\times4 Vandermonde system, i.e., φ∗(ξmn,ηmn)=φ(tn+1,ξmn+1,ηmn+1)\varphi^*(\xi_m^n,\eta_m^n)=\varphi(t^{n+1},\xi_m^{n+1},\eta_m^{n+1}) for m=1,…,4m=1,\ldots,4, to obtain the second order polynomial approximation φ∗(x,y)=∑i,j=0kcijxiyj\varphi^*(x,y)=\sum_{i,j=0}^{k}c_{ij}x^iy^j of φ(tn,x,y)\varphi(t^n,x,y). This strategy is more natural as the Lagrange basis functions are defined on the Gauss–Legendre nodes and we observe numerically robust simulations.

Characteristics tracing

In order to trace the characteristics of (12) backward in time, we consider the following first order method

xn=xn+1−Δt⋅a(xn+1,yn+1,tn)yn=yn+1−Δt⋅b(xn+1,yn+1,tn)(14)\begin{aligned} x^n &= x^{n+1}-\Delta t\cdot a(x^{n+1},y^{n+1},t^n)\\ y^n &= y^{n+1}-\Delta t\cdot b(x^{n+1},y^{n+1},t^n) \tag*{(14)} \end{aligned}

and a second order method,

xn=xn+1−Δt⋅a(xn+1/2,yn+1/2,tn+1/2)yn=yn+1−Δt⋅b(xn+1/2,yn+1/2,tn+1/2)(15)\begin{aligned} x^n &= x^{n+1} - \Delta t \cdot a\left(x^{n+1/2},y^{n+1/2},t^{n+1/2}\right) \\ y^n &= y^{n+1} - \Delta t \cdot b\left(x^{n+1/2},y^{n+1/2},t^{n+1/2}\right) \tag*{(15)} \end{aligned}

respectively, where the starting points xn+1x^{n+1} and yn+1y^{n+1} are either the cell corners or the Gauss–Legendre points inside the cells. The first order scheme (14) can be easily implemented since the velocity field at time tnt^n is known. For the second order method (15) additional considerations have to be taken. First, half a step size has to be computed in advance in order to get the velocity field at time tn+1/2t^{n+1/2} by solving the quasi neutrality equation. This is done in the predictor step of the time splitting method and thus no additional cost is incurred. Then we can use the first order scheme (14) to compute xn+1/2x^{n+1/2} and yn+1/2y^{n+1/2}. Finally, to obtain the velocity field at these points, we have to perform an interpolation since the velocity field is only known at the grid points. The resulting order can be checked with a local truncation error analysis. Although there exist higher order methods in the literature to trace the characteristics, see [1, 3] for example, we restrict ourselves to the second order scheme since the time splitting introduces an error of order two in any case.

Description of the algorithm

In order to implement (13), the following steps have to be taken.

  • Trace the corner points of the Eulerian grid cells AijA_{ij} along the characteristics back in time to find a second order approximation Aij∗A^*_{ij} of the upstream cell Aij(tn)A_{ij}(t^n), see the left picture of Figure 2.

  • Determine a polynomial approximation φij,m∗\varphi^*_{ij,m} of the solution of the adjoint problem, where the initial condition are the basis functions, by tracing the Gauss-Legendre points along the characteristics back in time and solve the corresponding small Vandermonde system.

  • Approximate (13) by

∫Aijun+1(x,y)φij,m(tn+1,x,y) dxdy≈∫Aij∗un(x,y)φij,m∗(x,y) dxdy=∑rs∫Aij,rs∗un(x,y)φij,m∗(x,y) dxdy.(16)\int_{A_{ij}} u^{n+1}(x,y)\varphi_{ij,m}(t^{n+1},x,y)\,dxdy \approx\int_{A^*_{ij}} u^n(x,y)\varphi^*_{ij,m}(x,y)\,dxdy = \sum_{rs}\int_{A^*_{ij,rs}} u^n(x,y)\varphi^*_{ij,m}(x,y)\,dxdy. \tag*{(16)}

where Aij,rs∗A^*_{ij,rs} is the intersection of the upstream cell with the underlying Eulerian grid cells ArsA_{rs}. In order to determine them, the intersection points between Aij∗A^*_{ij} and the Eulerian cells have to be found, see the black crosses in Figure 2.

  • Finalize by writing (16) as

uij,mn+1wm=∑rs∑kurs,knCrs,kij,m,(17)u^{n+1}_{ij,m}w_m = \sum_{rs}\sum_k u^n_{rs,k}C^{ij,m}_{rs,k}, \tag*{(17)}

where

Crs,kij,m=∫Aij,rs∗φrs,k(x,y)φij,m∗(x,y) dx dy.(18)C_{rs,k}^{ij,m}=\int_{A_{ij,rs}^{*}}\varphi_{rs,k}(x,y)\varphi_{ij,m}^{*}(x,y)\,dx\,dy. \tag*{(18)}

These coefficients are then computed by using Green’s theorem,

∫Aij,rs∗φrs,k(x,y)φij,m∗(x,y) dx dy=∮∂Aij,rs∗[P(x,y) dx+Q(x,y) dy],\int_{A_{ij,rs}^{*}}\varphi_{rs,k}(x,y)\varphi_{ij,m}^{*}(x,y)\,dx\,dy=\oint_{\partial A_{ij,rs}^{*}}\left[P(x,y)\,dx+Q(x,y)\,dy\right],

where

−∂yP(x,y)+∂xQ(x,y)=φrs,k(x,y)φij,m∗(x,y)=∑p,q=02kc(p,q)xpyq-\partial_yP(x,y)+\partial_xQ(x,y)=\varphi_{rs,k}(x,y)\varphi_{ij,m}^{*}(x,y)=\sum_{p,q=0}^{2k}c_{(p,q)}x^py^q

In order to do so, the surrounding faces of Aij,rs∗A_{ij,rs}^{*} have to be determined, see the cyan arrows in Figure 2. More precisely,

∫Aij,rs∗φrs,k(x,y)φij,m∗(x,y) dx dy=∑p,q=02kc(p,q)∫Aij,rs∗xpyq dx dy=∑p,q=02kc(p,q)∑l∫∂Aij,rs,l∗[P(p,q)(x,y) dx+Q(p,q)(x,y) dy]\begin{aligned} \int_{A_{ij,rs}^{*}}\varphi_{rs,k}(x,y)\varphi_{ij,m}^{*}(x,y)\,dx\,dy=\sum_{p,q=0}^{2k}c_{(p,q)}\int_{A_{ij,rs}^{*}}x^py^q\,dx\,dy \\ &=\sum_{p,q=0}^{2k}c_{(p,q)}\sum_l\int_{\partial A_{ij,rs,l}^{*}}\left[P^{(p,q)}(x,y)\,dx+Q^{(p,q)}(x,y)\,dy\right] \end{aligned}

where ⋃l∂Aij,rs,l∗=∂Aij,rs∗\bigcup_l\partial A_{ij,rs,l}^{*}=\partial A_{ij,rs}^{*} and the functions P(p,q)P^{(p,q)} and Q(p,q)Q^{(p,q)} are chosen for p+q≤2p+q\leq2 as in [23] and the higher degree polynomials are chosen as follows

P(2,1)=0,Q(2,1)=x3y3,P(1,2)=−xy33,Q(1,2)=0,P(2,2)=0,Q(2,2)=x3y23.P^{(2,1)}=0,\quad Q^{(2,1)}=\frac{x^3y}{3},\quad P^{(1,2)}=-\frac{xy^3}{3},\quad Q^{(1,2)}=0,\quad P^{(2,2)}=0,\quad Q^{(2,2)}=\frac{x^3y^2}{3}.

Let us mention that the choice of P(p,q)P^{(p,q)} and Q(p,q)Q^{(p,q)} is not unique, but its integral is.

Although the numerical implementation in (17) looks similar to (11) in the one dimensional case, i.e., as a sum of matrix vector products, it is much more challenging to get good performance from an implementation on GPUs. In contrast to the 1d case, several differences appear. First, the velocity field varies in space, which implies that for each cell different matrices have to be computed. Additionally, since the computation of these quantities does depend on the geometry determined by following the characteristics, a lot of control flow is required, which is a scarce resource on GPUs. Second, since the advection speed is not constant, it is not clear a priori how many grid cells are intersected by the upstream cell. This is especially a problem on GPUs with their small caches since the loaded data can often not be reused. Moreover, as explained previously, the amount of data to read varies from cell to cell and the memory access pattern can not be predicted. Third, since this problem is two dimensional, we have to deal with a strided memory access.

However, for realistic time step sizes the area of the upstream cell does not vary too much. Then, a reasonably small range of rsrs in (17) can be chosen. Thus, as in the 1d case, it follows that just a few cells are required to compute the values at the next time step for a given cell. Therefore, this method is local which is advantageous in a high performance computing setting (especially if one wishes to scale such methods to large systems).

Source term

As explained previously, the advective splitting substeps are mass conservative. In order to obtain a global mass conservative method, also the way how the source term is treated has to be mass conservative. If we integrate the term ∂zϕ∂vgeq\partial_z\phi\partial_vg_{\mathrm{eq}} over the full domain, we obtain

mass=∫rmin⁡rmax⁡∫02π∫0L∫−vmax⁡vmax⁡∂zϕ(t,r,θ,z)∂vgeq(r,v) dr dθ dz dv=∫rmin⁡rmax⁡∫02π∫−vmax⁡vmax⁡∂vgeq(r,v)(∫0L∂zϕ(t,r,θ,z) dz) dr dθ dv=∫rmin⁡rmax⁡∫02π∫−vmax⁡vmax⁡∂vgeq(r,v)(ϕ(t,r,θ,L)−ϕ(t,r,θ,0)) dr dθ dv=0\begin{aligned} \mathrm{mass} &= \int_{r_{\min}}^{r_{\max}}\int_{0}^{2\pi}\int_{0}^{L}\int_{-v_{\max}}^{v_{\max}} \partial_z\phi(t,r,\theta,z)\partial_vg_{\mathrm{eq}}(r,v)\,dr\,d\theta\,dz\,dv \\ &= \int_{r_{\min}}^{r_{\max}}\int_{0}^{2\pi}\int_{-v_{\max}}^{v_{\max}} \partial_vg_{\mathrm{eq}}(r,v)\left(\int_{0}^{L}\partial_z\phi(t,r,\theta,z)\,dz\right)\,dr\,d\theta\,dv \\ &= \int_{r_{\min}}^{r_{\max}}\int_{0}^{2\pi}\int_{-v_{\max}}^{v_{\max}} \partial_vg_{\mathrm{eq}}(r,v)\left(\phi(t,r,\theta,L)-\phi(t,r,\theta,0)\right)\,dr\,d\theta\,dv=0 \end{aligned}

due to the periodicity of ϕ\phi in the zz direction. A similar computation holds for the other term, ∂θϕ∂r(geqr)\partial_\theta\phi\partial_r\left(\frac{g_{\mathrm{eq}}}{r}\right). Therefore, if the derivative is discretized in such a way as to preserve this property, we obtain a mass conservative scheme. This is, e.g., the case if we use centered finite differences to compute the derivatives. Then, the source term can be simply treated as

δg⋆,n+1=δg⋆,n+Δt(∂zϕ∂vgeq+∂θϕ∂r(geqr))\delta g^{\star,n+1}=\delta g^{\star,n}+\Delta t\left(\partial_z\phi\partial_vg_{\mathrm{eq}}+\partial_\theta\phi\partial_r\left(\frac{g_{\mathrm{eq}}}{r}\right)\right)

in the splitting step and does not introduce an error in mass.

Quasi neutrality equation

For the quasi neutrality equation, periodic boundary conditions are considered in the θ\theta and zz direction, homogeneous Dirichlet boundary conditions in the radial direction at rmax⁡r_{\max} and homogeneous Neumann boundary conditions at rmin⁡r_{\min} are considered. Therefore, we can use FFT in the (θ,z)(\theta,z) plane. In addition, we use finite differences in the rr direction. Thus, for each degree of freedom in the θ\theta and zz direction, a tridiagonal linear system has to be solved. See [19] for more details. Since we are working with a non equidistant nodal basis, in order to use the FFT, we have to evaluate first the right-hand side of the equation, i.e., 1rn0(r)∫δgm dv\frac{1}{r n_0(r)}\int\delta g^m\,dv, at an equidistant grid. In the zz direction, this is done inside the cell, while in the rr-θ\theta plane it is done at the cell corners, where the average is taken since the function is discontinuous here. To compute the velocity field, we use again second order finite differences. In order to obtain the values of the transport field inside the cells, bilinear interpolation is applied.

Implementation details

Since the 2d advection is the most expensive part of solving the 4d problem, memory is organized to favor memory access in that step. Thus, the fastest varying indices in memory correspond to rr and θ\theta. In addition, all degrees of freedom in a cell are stored consecutively in memory. The next direction in memory is the vv dimension and finally the zz dimension is considered. This choice is made because the velocity field also depends on zz and thus the coefficients (18) need to be recomputed for each zz. This leads to an implementation as in algorithm 3 which allows us to reuse those coefficients for each vv.

Algorithm 3 2d advection in the drift-kinetic setting

for zz do     compute all Crs,kij,mC_{rs,k}^{ij,m}, see (18)     for vv do         perform the advection in 2d, see (17)

We have implemented this both on the CPU and on the GPU. While for the CPU the implementation is straightforward by parallelizing first the computation of (18) and then the loop over the degrees of freedom in the vv direction using OpenMP, the implementation on the GPU requires more care in order to obtain good performance.

On the GPU algorithm 3 is divided into two steps. The first part consists of computing for each degree of freedom in the zz direction the coefficients Crs,kij,mC_{rs,k}^{ij,m}. The second part consists of one kernel call which implements (17) for the full domain. Here, threads within a block are reading the coefficients (18) of one cell in the rr-θ\theta domain to the shared memory. The number of threads per block is given by the maximum theoretical coefficients that have to be loaded. In our case, since the approximation space with order two has four elements, this implies that for each possible intersection of the upstream cell with the underlying Eulerian grid cell a matrix of 4×44 \times4 has to be read. We assume, that an upstream cell intersects at most a block of 3×33 \times3 grid cells, which implies that a block consists of at most 144 threads. When the coefficients are loaded, each thread is associated to one specific vv-value to perform the advection. In other words, fine-grained thread parallelization is performed in the velocity dimension to optimize the use of the shared memory, while coarse block parallelization is performed at the cells in the rr-θ\theta plane and over the zz dimension. The 2d SLDG code is part of sldg which is available at https://bitbucket.org/leinkemmer/sldg.

Numerical simulation

Validation of the 2d SLDG algorithm with Lagrange polynomials

To demonstrate that the method produces the expected results also in the case of Lagrange basis functions, where we apply a different strategy in approximating the solution of the adjoint problem as described in the previous section, we consider the swirling deformation test case. This test is commonly used to demonstrate the correctness of newly developed algorithms as the advection field depends on space and time and the exact solution at the final time t=Tt = T is the same as at time t=0t = 0. The problem is stated as follows

∂tu−∂x(cos⁡2(x/2)sin⁡(y)g(t)u)+∂y(sin⁡(x)cos⁡2(y/2)g(t)u)=0,\partial_t u - \partial_x\left(\cos^2(x/2)\sin(y)g(t)u\right) + \partial_y\left(\sin(x)\cos^2(y/2)g(t)u\right) = 0,

where g(t)=cos⁡(πtT)πg(t) = \cos\left(\frac{\pi t}{T}\right)\pi. The initial condition is a C5C^5 cosine bell. More details about this problem can be found in [2]. The results are presented in Table 1, where we observe the expected second order convergence rate for k=1.

mesh sizeL2L^2 errorL2L^2 orderL∞L^\infty errorL∞L^\infty order
20 × 205.20e-21.57e-1
40 × 409.94e-32.394.49e-21.80
80 × 801.85e-32.428.66e-32.37
160 × 1603.78e-42.291.57e-32.46

Table 1. Swirling deformation test case using a time step of Δt=0.5Δx\Delta t = 0.5\Delta x and a final time T=1.5T = 1.5. The error in mass in all simulations is close to machine precision.

Drift-kinetic ion temperature gradient instability

In this section we consider the simulation of an ion temperature gradient instability using the full four dimensional drift-kinetic problem specified in equations (1) and (2). The initial condition and parameters are given as follows

f(t=0,r,θ,z,v)=feq(r,v)[1+ϵexp⁡(−(r−rp)2δr)cos⁡(2πnLz+mθ)]f(t = 0, r, \theta, z, v) = f_{\mathrm{eq}}(r,v) \left[1 + \epsilon\exp\left(-\frac{(r-r_p)^2}{\delta_r}\right)\cos\left(\frac{2\pi n}{L}z + m\theta\right)\right]
feq(r,v)=n0(r)exp⁡(−v22Ti(r))(2πTi(r))1/2f_{\mathrm{eq}}(r,v) = \frac{n_0(r)\exp\left(-\frac{v^2}{2T_i(r)}\right)}{(2\pi T_i(r))^{1/2}}
P(r)=CPexp⁡(−κPδrPtanh⁡(r−rpδrP)),P∈{Ti,Te,n0}\mathcal{P}(r) = C_{\mathcal{P}}\exp\left(-\kappa_{\mathcal{P}}\delta r_{\mathcal{P}}\tanh\left(\frac{r-r_p}{\delta r_{\mathcal{P}}}\right)\right),\quad\mathcal{P}\in\{T_i,T_e,n_0\}
CTi=CTe=1,Cn0=rmax⁡−rmin⁡∫rmin⁡rmax⁡exp⁡(−κn0δrn0tanh⁡(r−rpδrn0)) drC_{T_i}=C_{T_e}=1,\quad C_{n_0}=\frac{r_{\max}-r_{\min}}{\int_{r_{\min}}^{r_{\max}}\exp\left(-\kappa_{n_0}\delta r_{n_0}\tanh\left(\frac{r-r_p}{\delta r_{n_0}}\right)\right)\,\mathrm{d}r}
rmin⁡=0.1, rmax⁡=14.5, κn0=0.055, κTi=κTe=0.27586,r_{\min}=0.1,\ r_{\max}=14.5,\ \kappa_{n_0}=0.055,\ \kappa_{T_i}=\kappa_{T_e}=0.27586,
δrTi=δrTe=δrn02=1.45, ϵ=10−6, n=1, m=5,\delta r_{T_i}=\delta r_{T_e}=\frac{\delta r_{n_0}}{2}=1.45,\ \epsilon=10^{-6},\ n=1,\ m=5,
L=1506.759067, rp=rmax⁡+rmin⁡2, δr=4δrn0δrTi.L=1506.759067,\ r_p=\frac{r_{\max}+r_{\min}}{2},\ \delta r=\frac{4\delta r_{n_0}}{\delta r_{T_i}}.

In addition to the distribution function ff and the potential ϕ\phi we also consider the time evolution of the electric energy

∫ϕ2(t,rp,θ,z) dθdz,\sqrt{\int\phi^2(t,r_p,\theta,z)\,\mathrm{d}\theta\mathrm{d}z},

the total mass

∫f(t,r,θ,z,v)r drdθdzdv,\int f(t,r,\theta,z,v)r\,\mathrm{d}r\mathrm{d}\theta\mathrm{d}z\mathrm{d}v,

the L2L^2 norm

∫f2(t,r,θ,z,v)r drdθdzdv,\sqrt{\int f^2(t,r,\theta,z,v)r\,\mathrm{d}r\mathrm{d}\theta\mathrm{d}z\mathrm{d}v},

and the total energy

∫(v2/2+ϕ(t,r,θ,z))f(t,r,θ,z,v)r drdθdzdv.\int\left(v^2/2+\phi(t,r,\theta,z)\right)f(t,r,\theta,z,v)r\,drd\theta dzdv.

The total mass, the L2L^2 norm and the total energy are conserved quantities of the system. Grids of 64×64×64×12864 \times64 \times64 \times128 and 82×82×82×16482 \times82 \times82 \times164 cells and fixed time step sizes of 2, 4 and 8 are used. Let us emphasize that there is no CFL condition; that is, even larger time steps can be taken while maintaining stability. Therefore, the time step size is not restricted by the stability of the scheme, but by the accuracy of the obtained results.

Due to the gradient in temperature given by TiT_i a physical instability develops that results in an exponential increase in the electric energy. This increase is maintained until saturation is caused by a strongly nonlinear dynamics. The initial increase of the electric energy can be obtained analytically by solving the linearized drift-kinetic model, see [7]. In Figure 3a, it can be observed that the simulated growth rate matches the analytical rate very well.

Image not extracted

Figure 3. Time evolution of the electric energy as well as error in mass, L2L^2 norm and total energy is shown. A time step size of 2,4 and 8 a grid of 64×64×64×12864 \times64 \times64 \times128 (dx=64dx=64) and a grid of 82×82×82×16482 \times82 \times82 \times164 (dx=82dx=82) cells with order 2 is used.

The numerical methods considered are mass conservative, but do not conserve the L2L^2 norm and the total energy. In Figure 3b we observe that mass is indeed conserved up to machine precision. From Figure 3c and Figure 3d we see that the L2L^2 norm and the total energy are approximately conserved up to an error of 10−410^{-4}.

Finally, in Figure 4 we present slices of the density function δg\delta g at (r,t,v=0,z=0)(r,t,v=0,z=0), the charge density and the electric potential at (r,t,z=0)(r,t,z=0) at time T=3000,4000,5000,6000T=3000, 4000, 5000, 6000. That is, from the late stages of the linear instability to the solution in the fully nonlinear regime. The results match well with what has been reported in literature [19, 9].

Image not extracted

Figure 4. Plots of slices of the density δg\delta g at v=0v = 0, z=0z = 0 (first column), the charge density at z=0z = 0 (second column) and electric potential at z=0z = 0 (third column) at different times using a grid of 64×64×64×12864 \times64 \times64 \times128 cells and a time step of 4.

Convergence order in time

To check the achieved order in time, we integrate the problem up to time T=500T = 500 and use a fixed discretization of 64 cells in the spatial dimensions and 128 cells in the velocity dimension. As reference solution, we take the result of the second order time splitting method using 2000 time steps, which corresponds to a time step size of 0.25. The relative error in maximum norm as a function of the step size is shown in Figure 5. As expected, based on the discussion in § 3.1 the method from [11] is only first order accurate, whereas the method proposed in this work is second order accurate.

Image not extracted

Figure 5. Convergence orders for the method from [11] and the proposed second order splitting scheme. The relative error in the maximum norm at the final time T=500T = 500 is shown.

Multi-core CPU and GPU performance Results

In this section, we will study the performance of the implementation on multi-core CPU and GPU based systems.

Let us first discuss if the problem considered is compute bound or memory bound. While compute bound problems often appear in machine learning, i.e., performance is dictated by how many arithmetic operations can be performed, most of the scientific codes (stencil codes, sparse matrix operations, etc.) are memory bound, i.e., the limiting factor to achieve faster execution times is the time required to read from and write to memory. As is pointed out in [14, 15], performing the 1d advections is a memory bound problem, since comparably few floating point operations have to be performed compared to the amount of memory access.

Regarding the 2d SLDG implementation, the final step requires in each cell at most nine matrix vector products of size 4×44 \times4, which results in 4[9(2⋅4−1)+8]=2844[9(2 \cdot4 - 1) + 8] = 284 floating point operations per cell. Since the entire domain has to be read and written once, an arithmetic intensity, when using double precision, of

dof⋅[9(2⋅4−1)+8]2⋅dof⋅8=4.44\frac{\mathrm{dof}\cdot[9(2\cdot4-1)+8]}{2\cdot\mathrm{dof}\cdot8}=4.44

is obtained in the worst case. Thus also the 2d SLDG algorithm is a memory bound problem on the GPUs considered in this work, see Table 2.

GPUmemorybandwidthflops/byte (double)
Titan V12 GB653 GB/s9.36
V10016 GB900 GB/s8.28
A10040 GB1500 GB/s6.47

Table 2. List of the different GPUs used in this work and their specification.

Thus, to measure the performance of our implementation, we will mostly use the achieved memory bandwidth as a metric. This enables us to compare the achieved performance directly with what the hardware can theoretically support. The achieved bandwidth can be easily translated back into runtime, if desired. For the first order time splitting method, the domain has to be read and written seven times to perform the advections and to treat the source terms. Moreover, two additional reads are required to compute the charge density, which implies that the density function has to be accessed 16 times in total. Consequently, the amount of memory processed per time step is 16⋅dof⋅816\cdot\mathrm{dof}\cdot8 bytes, where dof stands for the degrees of freedom and depends on the number of cells used, i.e.,

dof=∏i=14(number of cells in dimension i)⋅(ki+1),\mathrm{dof}=\prod_{i=1}^{4}(\text{number of cells in dimension }i)\cdot(k_i+1),

where kik_i is the degree of the polynomial used in dimension ii; in our case, ki=1k_i=1. The factor 8 reflects the fact that the computations are performed in double precision; i.e. sizeof(double)=8. Then, the achieved bandwidth of our implementation is obtained by the following formula,

achieved bandwidth=16⋅dof⋅8⋅10−9 GBtime per step in seconds.\text{achieved bandwidth}=\frac{16\cdot\mathrm{dof}\cdot8\cdot10^{-9}\ \mathrm{GB}}{\text{time per step in seconds}}.

Note that the time per step in seconds includes the computation of the electric field, while it is not included in the amount of memory accesses. Solving the quasi neutrality equation and the necessary interpolations and derivatives is a 3d problem, thus its impact on the full 4d drift-kinetic equation is small and not taking it into account does not change the overall bandwidth appreciably. Nevertheless, let us remark that its impact on the overall performance is significantly larger than solving the Poisson problem in the Vlasov–Poisson system in [15].

The implementation of solving the 1d advections and the source term operates relatively close to the theoretical limit of the hardware and has thus a positive impact on the overall performance. For example, on the A100 GPU with a grid size of 64×64×64×12864 \times64 \times64 \times128 cells, the advection in the vv dimension achieves 760 GB/s. Such a performance can not be expected for the 2d advection as the memory access pattern is more complicated and less predictable. Our implementation of the 2d advection achieves a bandwidth of 209 GB/s.

The proposed second order splitting scheme achieves a bandwidth of 560 GB/s, while the first order scheme achieves 590 GB/s. This reduction is mainly due to the additional 2d advection that has to be performed. Overall this results in an increase in the run time of approximately 65% for the second order scheme in contrast to the first order scheme. The second order scheme also requires 1.5 times more memory than the first order scheme since the density function has to be stored three times, compare algorithm 1 to algorithm 2. However, it should be highlighted that the second order scheme (for the time step size chosen here) is more than an order of magnitude more accurate than the first order scheme (see Figure 5).

In Figure 6 the achieved bandwidth of the first order method is plotted as a function of the number of cells. For the A100 we observe a performance of approximately 590 GB/s for the algorithm. The A100 has a theoretical memory bandwidth of 1500 GB/s which corresponds to a parallel efficiency of approximately 40% for our implementation.

Image not extracted

Figure 6. Achieved global bandwidth as a function of the number of cells used in each spatial dimension. In the velocity dimension, twice as many cells are used.

For the V100 we achieve a bandwidth of approximately 360 GB/s and on a Titan V 280 GB/s. Thus, the A100 is around 1.6 times faster than the V100 and 2.1 times faster than the Titan V and the improvement of performance between newer generation GPUs reflects exactly the improvement of bandwidth between them, which once more is a good indication that we are working on a memory bound problem.

Let us finally compare the GPU performance to the performance of a multi-core CPU system. We consider a dual socket system based on two Intel Xeon Gold 6226R CPUs. Our OpenMP implementation achieves a bandwidth of approximately 23 GB/s. It can be observed that all the GPUs outperform the CPU system by a significant margin, for example, the A100 is approximately a factor of 27 times faster than the CPU based system.

In order to better understand the achieved performance displayed in Figure 6, we analyze the different parts of the splitting algorithm. The results are reported in Table 3. Here we compare the performance between the A100 GPU and the CPU system where a fixed grid size of 64×64×64×12864 \times64 \times64 \times128 cells is used. As expected, the GPU outperforms the CPU in each step. Moreover, as expected, the slowest part is the advection in the rr-θ\theta plane. However, while on the GPU this part is approximately a factor of four times slower than the other parts, on the CPU this gap is significantly smaller. Thus, as we might expect, the CPU copes better with the less predictable memory access of the 2d advection, even though overall the GPU in this step is still faster by approximately a factor of 10.

CPUGPUbandwidth GPU
advection rr-θ\theta420.441.06209.2 GB/s
advection vv370.811.30760.0 GB/s
advection zz367.88.98956.3 GB/s
compute ρ\rho387.96.22690.5 GB/s
quasi neutrality83.44.09
source term88.96.661290.1 GB/s

Table 3. Average time per step of the different parts of the splitting algorithm in milliseconds and achieved bandwidth of these parts on the GPU. A grid size of 64×64×64×12864 \times64 \times64 \times128 cells on an A100 GPU and a dual socket Intel Xeon Gold 6226R is used.

To analyze the performance of the 2d SLDG algorithm in more detail, we report the timings of the required substeps in Table 4. As expected, the GPU is not significantly faster in computing the coefficients (18) (steps 1-5 in the table) as explained above. Nevertheless, the final step (17) (step 6 in the table) on the GPU gives a significant boost in performance compared to the CPUs. As expected, computing the coefficients (18) in steps 1-5 are less expensive than the computation of (17) implemented in step 6. These coefficients only depend on the electric field which is defined in the 3d spatial domain. In contrast, step 6 is responsible for a 2d advection in 4d phase space. Let us also note that we do not observe a significant difference in the performance characteristics using different mesh sizes. Additionally, we do not expect an impact on performance using different time step sizes. The step size influences only the shape of the upstream cell, and since the current implementation allows the upstream cell to be a subset of 3×33 \times3 Eulerian cells, a comparable amount of data has to be processed to perform steps 1-5 in Table 4. The performance of step 6 is dictated by reading and writing the 4d domain, where the impact on the time step size is again rather small.

mesh size64×64×64×12864 \times64 \times64 \times12880×80×80×16080 \times80 \times80 \times160
CPUGPUCPUGPU
1. compute the upstream mesh3.610.436.000.81
2. get outer segments4.871.257.742.47
3. get inner segments3.313.125.965.62
4. solve adjoint problem3.040.435.550.78
5. compute integrals29.0613.7862.7627.76
6. finalize376.2822.05869.2359.66
total420.3641.06957.5597.10

Table 4. Average time per step of the parts of the 2d SLDG algorithm in milliseconds. An A100 GPU and a dual socket Intel Xeon Gold 6226R is used.

Acknowledgements

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 847476. The views and opinions expressed herein do not necessarily reflect those of the European Commission.

References

  1. [1]X. Cai, S. Boscarino, and J.-M. Qiu. High order semi-Lagrangian discontinuous Galerkin method coupled with Runge-Kutta exponential integrators for nonlinear Vlasov dynamics. Journal of Computational Physics, 427:110036, 2021.arxiv.org/abs/1911.12229
  2. [2]X. Cai, W. Guo, and J.-M. Qiu. A high order conservative semi-Lagrangian discontinuous Galerkin method for two-dimensional transport simulations. Journal of Scientific Computing, 73, 2017.arxiv.org/abs/1612.06977
  3. [3]X. Cai, W. Guo, and J.-M. Qiu. A high order semi-Lagrangian discontinuous Galerkin method for the two-dimensional incompressible Euler equations and the guiding center Vlasov model without operator splitting. Journal of Scientific Computing, 79, 2019.arxiv.org/abs/1804.02365
  4. [4]X. Cai, W. Guo, and J.-M. Qiu. Comparison of semi-Lagrangian discontinuous Galerkin schemes for linear and nonlinear transport simulations. Communications on Applied Mathematics and Computation, 4:1–31, 09 2020.arxiv.org/abs/1903.12343
  5. [5]X. Cai, J.-M. Qiu, and Y. Yang. An Eulerian-Lagrangian discontinuous Galerkin method for transport problems and its application to nonlinear dynamics. Journal of Computational Physics, 439:110392, 05 2021.DOI
  6. [6]F. Casas, N. Crouseilles, E. Faou, and M. Mehrenberger. High-order Hamiltonian splitting for the Vlasov–Poisson equations. Numerische Mathematik, 135(3):769–801, 2017.arxiv.org/abs/1510.01841
  7. [7]D. Coulette and N. Besse. Numerical comparisons of gyrokinetic multi-water-bag models. Journal of Computational Physics, 248:1–32, 09 2013.DOI
  8. [8]N. Crouseilles, L. Einkemmer, and E. Faou. Hamiltonian splitting for the Vlasov–Maxwell equations. Journal of Computational Physics, 283:224–240, 2015.DOI
  9. [9]N. Crouseilles, L. Einkemmer, and J. Massot Josselin. Exponential methods for solving hyperbolic problems with application to collisionless kinetic equations. Journal of Computational Physics, 420:109688, 2020.DOI
  10. [10]N. Crouseilles, L. Einkemmer, and M. Prugger. An exponential integrator for the drift-kinetic model. Computer Physics Communications, 224:144–153, 2018.DOI
  11. [11]N. Crouseilles, P. Glanc, S. A. Hirstoaga, E. Madaule, M. Mehrenberger, and J. Pétri. A new fully two-dimensional conservative semi-Lagrangian method: applications on polar grids, from diocotron instability to ITG turbulence. The European Physical Journal D, 68, 2014.DOI
  12. [12]N. Crouseilles, M. Mehrenberger, and F. Vecil. Discontinuous Galerkin semi-Lagrangian method for Vlasov-Poisson. In ESAIM: Proceedings, volume 32, pages 211–230. EDP Sciences, 2011.DOI
  13. [13]L. Einkemmer. A performance comparison of semi-Lagrangian discontinuous Galerkin and spline based Vlasov solvers in four dimensions. Journal of Computational Physics, 376:937–951, 2019.DOI
  14. [14]L. Einkemmer. Semi-Lagrangian Vlasov simulation on GPUs. Computer Physics Communications, 254:107351, 2020.DOI
  15. [15]L. Einkemmer and A. Moriggl. Semi-Lagrangian 4d, 5d, and 6d kinetic plasma simulation on large scale GPU equipped supercomputer. arXiv e-prints, page arXiv:2110.14557, October 2021.arxiv.org/abs/2110.14557
  16. [16]L. Einkemmer and A. Ostermann. Convergence analysis of a discontinuous Galerkin/Strang splitting approximation for the Vlasov–Poisson equations. SIAM Journal on Numerical Analysis, 52(2):757–778, 2014.
  17. [17]L. Einkemmer and A. Ostermann. Convergence analysis of Strang splitting for Vlasov-type equations. SIAM Journal on Numerical Analysis, 52(1):140–155, 2014.DOI
  18. [18]F. Filbet and E. Sonnendrücker. Comparison of Eulerian Vlasov solvers. Comput. Phys. Commun., 150(3):247–266, 2003.DOI
  19. [19]V. Grandgirard, M. Brunetti, P. Bertrand, N. Besse, X. Garbet, P. Ghendrih, G. Manfredi, Y. Sarazin, O. Sauter, E. Sonnendrücker, J. Vaclavik, and L. Villard. A drift-kinetic Semi-Lagrangian 4D code for ion turbulence simulation. Journal of Computational Physics, 217(2):395–423, 2006.DOI
  20. [20]W. Guo, R. Nair, and J.-M. Qiu. A conservative semi-Lagrangian discontinuous Galerkin scheme on the cubed sphere. Monthly Weather Review, 142(1):457 – 475, 2014.DOI
  21. [21]K. Kormann, K. Reuter, and M. Rampp. A massively parallel semi-Lagrangian solver for the six-dimensional Vlasov–Poisson equation. The International Journal of High Performance Computing Applications, 33(5):924–947, 2019.DOI
  22. [22]G. Latu. Fine-Grained Parallelization of a Vlasov-Poisson Application on GPU. In M. R. Guarracino, F. Vivien, J. L. Träff, M. Cannatoro, M. Danelutto, A. Hast, F. Perla, A. Knüpfer, B. Di Martino, and M. Alexander, editors, Euro-Par 2010 Parallel Processing Workshops, pages 127–135. Springer Berlin Heidelberg, 2011.DOI
  23. [23]P. H. Lauritzen, R. D. Nair, and P. A. Ullrich. A conservative semi-Lagrangian multitracer transport scheme (CSLAM) on the cubed-sphere grid. Journal of Computational Physics, 229:1401–1424, 2010.DOI
  24. [24]W. W. Lee. Gyrokinetic approach in particle simulation. The Physics of Fluids, 26(2):556–562, 1983.
  25. [25]M. Mehrenberger, C. Steiner, L. Marradi, N. Crouseilles, E. Sonnendrücker, and B. Afeyan. Vlasov on GPU (VOG project). In ESAIM: Proceedings, volume 43, pages 37–58. EDP Sciences, 2013.arxiv.org/abs/1301.5892
  26. [26]B. Rivière. Discontinuous Galerkin Methods for solving elliptic and parabolic equations: Theory and implementation. Society for Industrial and Applied Mathematics, 2008.
  27. [27]T. M. Rocha Filho. Solving the Vlasov equation for one-dimensional models with long range interactions on a GPU. Computer Physics Communications, 184(1):34–39, 2013.DOI
  28. [28]E. Sonnendrücker, J. Roche, P. Bertrand, and A. Ghizzo. The semi-Lagrangian method for the numerical resolution of the Vlasov equation. Journal of computational physics, 149(2):201–220, 1999.DOI
  29. [29]J. P. Verboncoeur. Particle simulation of plasmas: review and advances. Plasma Phys. Control. Fusion, 47(5A):A231, 2005.DOI

Paper details

vlnc:W_cjsa9k9d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents