betaFeedback

WorksPhysics and Astronomy

Cache Blocking for Flux Reconstruction: Extension to Navier-Stokes Equations and Anti-aliasing

Abstract

In this article, cache blocking is implemented for the Navier Stokes equations with anti-aliasing support on mixed grids in PyFR for CPUs. In particular, cache blocking is used as an alternative to kernel fusion to eliminate unnecessary data movements between kernels at the main memory level. Specifically, kernels that exchange data are grouped together, and these groups are then executed on small sub-regions of the domain that fit in per-core private data cache. Additionally, cache blocking is also used to efficiently implement a tensor product factorisation of the interpolation operators associated with anti-aliasing. By using cache blocking, the intermediate results between application of the sparse factors are stored in per-core private data cache, and a significant amount of data movement from main memory is avoided. In order to assess the performance gains a theoretical model is developed, and the implementation is benchmarked using a compressible 3D Taylor-Green vortex test case on both hexahedral and prismatic grids, with third- and forth-order solution polynomials. The expected performance gains based on the theoretical model range from 1.99 to 2.62, and the speedups obtained in practice range from 1.67 to 3.67 compared to PyFR v1.11.0.

Introduction

Achieving a target accuracy level with as little computational cost as possible has always been an important goal in Computational Fluid Dynamics (CFD). To this end, various numerical discretizations have been developed and improved over the years. For example, compact high-order discretizations for unstructured grids, such as Discontinuous Galerkin (DG), Spectral Difference (SD), and Flux Reconstruction (FR) schemes have been developed to enable accurate scale-resolving simulations of turbulent flow in a tractable cost envelope. However, scale resolving simulations of various industry-relevant high Reynolds number flows are still beyond the reach of high-order methods even when using national laboratory scale supercomputers. This has led researchers to investigate ways to utilize available computational power more efficiently. Changing the arithmetic intensity of kernels can be a way to achieve this. For example, an alternative mathematical form of a given operation may require fewer FLOPs and this may lead to a better arithmetic intensity for a particular hardware. Another example is kernel fusion, which reduces the data movements between processor and memory, and therefore increases the arithmetic intensity. Depending on the arithmetic intensity profile of the kernels and the target hardware, these methods can be used to achieve better performance.

In recent work, the authors implemented a cache blocking strategy as an alternative to kernel fusion to reduce bandwidth requirement for an FR code for Euler equations without anti-aliasing on hexahedral meshes [1]. Cache blocking reduces main memory accesses by using L2L2 cache as a buffer storage for intermediate and temporary data in a set of kernels that exchange data, which we will refer as a kernel group in the remainder of this article. As long as the L2L2 cache is big enough for storing the temporary data, cache blocking has all the benefits of kernel fusion in terms of bandwidth reduction without any downsides [1]. Furthermore, the cache blocking approach is easy to implement, and changing the configuration of kernel groups or adding new kernels into the existing kernel groups is simple and straightforward. Here, we extend this previous work to support Navier-Stokes equations with anti-aliasing on mixed element meshes.

Extension to Navier-Stokes solver enables real-world viscous simulations and it is necessary to use anti-aliasing in order to remain numerically stable for certain physical simulations such as turbulent flows that are marginally resolved [2].

Additionally, supporting mixed element meshes provides flexibility for complex geometries.

There are three important aspects to consider for the aforementioned extensions. First, compared to an Euler solver, a Navier-Stokes solver has more kernels and this introduces more constraints on how they can be grouped together. Next, a direct implementation of anti-aliasing results in additional dense operators as well as changing many of the existing sparse operators in the Navier-Stokes solver into dense operators. This results in FLOP limited kernels due to the sufficiently high arithmetic intensity associated with the dense operators. However, an alternative method for implementing anti-aliasing is using sum factorisation, which was initially proposed by Orszag [3] for spectral methods and later adapted and used for spectral/hphp element methods by Sherwin and Karniadakis [4]. A detailed analysis of sum factorisation carried out by Cantwell [5] shows that sum factorisation can be effective only at p=7p = 7 and beyond. Further studies also confirmed a similar trend [6, 7]. Świry dowicz et al. [8] employed a slightly different strategy which factors the tensor product operators into sparse components by doing 1D interpolations in every dimension one-by-one. Employing such a tensor product factorisation strategy naively for these dense operators where each factor is applied sequentially to the entire data set without cache blocking results in significant increase in the bandwidth requirement, and makes the operations bandwidth bound rather than FLOP bound. Kernel fusion is a solution to this, but it requires not only a complex implementation, but also makes the code architecture specific. Therefore, we propose using the cache blocking strategy in conjunction with the tensor product factorisation in order to eliminate the excess bandwidth requirement. In short, the methodology we propose for anti-aliasing effectively trades of FLOP requirements with bandwidth requirements by using a tensor product factorisation strategy, and then eliminates the excess bandwidth requirement by employing a cache blocking strategy. As a result, anti-aliasing kernels require significantly less FLOPs while requiring similar or even reduced access to main memory. Finally, we enable mixed element support including hexahedra, prisms, tetrahedra and pyramids where tensor product factorisation is only used for hexahedral and prism elements.

The paper is structured as follows. The FR formulation for the Navier-Stokes equations including anti-aliasing is given in § 2 alongside with the kernels that implement these mathematical operations. Next, current kernel execution order and the data movement requirements are presented in § 3 Anti-aliasing and its effects in terms of computational cost is discussed in § 4. Then, an efficient implementation of anti-aliasing in FR within the context of cache blocking is described in § 5. A kernel grouping strategy for the Navier-Stokes equations including anti-aliasing support is given alongside the speedups obtained in practice in § 6. Finally, conclusions are discussed in § 7.

Navier-Stokes Formulation and Kernels

Flux Reconstruction (FR) was first developed by Huynh in 2005 [9]. An overview of the FR approach for solving the Navier-Stokes equations including anti-aliasing is presented in this section.

Formulation

The Navier-Stokes equations can be written in conservative form as,

∂uα∂t+∇⋅fα=0,(1)\frac{\partial u_{\alpha}}{\partial t} + \nabla\cdot\mathbf{f}_{\alpha} = 0, \tag*{(1)}

where α\alpha is the field variable index, uα=uα(x,t)u_{\alpha}=u_{\alpha}(x,t) are the conservative field variables thus,

u=[ρρuxρvyρvzE](2)\mathbf{u}= \begin{bmatrix} \rho\\ \rho u_x\\ \rho v_y\\ \rho v_z\\ E \end{bmatrix} \tag*{(2)}

and f=f(u,∇u)\mathbf{f}=\mathbf{f}(u,\nabla u) is the flux term that incorporates inviscid and viscous fluxes thus f=fe−fv\mathbf{f}=\mathbf{f}^{\mathrm{e}}-\mathbf{f}^{\mathrm{v}}. First, the inviscid flux, fe\mathbf{f}^{\mathrm{e}}, is defined as

fe(u)=[ρvxρvx2+pρvxvyρvxvzvx(E+p)]i+[ρvyρvyvxρvy2+pρvyvzvy(E+p)]j+[ρvzρvzvxρvzvyρvz2+pvz(E+p)]k,(3)\mathbf{f}^{\mathrm{e}}(u)= \begin{bmatrix} \rho v_x\\ \rho v_x^2+p\\ \rho v_xv_y\\ \rho v_xv_z\\ v_x(E+p) \end{bmatrix}\mathbf{i}+ \begin{bmatrix} \rho v_y\\ \rho v_yv_x\\ \rho v_y^2+p\\ \rho v_yv_z\\ v_y(E+p) \end{bmatrix}\mathbf{j}+ \begin{bmatrix} \rho v_z\\ \rho v_zv_x\\ \rho v_zv_y\\ \rho v_z^2+p\\ v_z(E+p) \end{bmatrix}\mathbf{k}, \tag*{(3)}

where ρ\rho is density, vx,vy,vzv_x,v_y,v_z are velocity, pp is pressure, EE is total energy per unit volume, and i,j,k\mathbf{i},\mathbf{j},\mathbf{k} are orthogonal unit vectors. The relation between the pressure and the total energy for a perfect gas is,

E=pγ−1+12ρ(vx2+vy2+vz2),(4)E=\frac{p}{\gamma-1}+\frac{1}{2}\rho(v_x^2+v_y^2+v_z^2), \tag*{(4)}

where γ\gamma is the specific heat ratio, cp/cvc_p/c_v, cpc_p is the specific heat at constant pressure, and cvc_v is the specific heat at constant volume.

Next, the viscous flux, fv\mathbf{f}^{\mathrm{v}} is given as

fv(u,Δu)=[0τxxτxyτxzviτix+ϕx]i+[0τyxτyyτyzviτiy+ϕy]j+[0τzxτzyτzzviτiz+ϕz]k,(5)\mathbf{f}^{\mathrm{v}}(u,\Delta u)= \begin{bmatrix} 0\\ \tau_{xx}\\ \tau_{xy}\\ \tau_{xz}\\ v_i\tau_{ix}+\phi_x \end{bmatrix}\mathbf{i}+ \begin{bmatrix} 0\\ \tau_{yx}\\ \tau_{yy}\\ \tau_{yz}\\ v_i\tau_{iy}+\phi_y \end{bmatrix}\mathbf{j}+ \begin{bmatrix} 0\\ \tau_{zx}\\ \tau_{zy}\\ \tau_{zz}\\ v_i\tau_{iz}+\phi_z \end{bmatrix}\mathbf{k}, \tag*{(5)}

where T\mathcal{T} is the stress tensor and defined as,

T=μ(∂ivj+∂jvi)−23μδij∇⋅v,(6)\mathcal{T}=\mu(\partial_i v_j+\partial_j v_i)-\frac{2}{3}\mu\delta_{ij}\nabla\cdot\mathbf{v}, \tag*{(6)}

and ϕ\phi is the heat flux defined as,

ϕ=μcpPr∇T.(7)\phi= \mu\frac{c_p}{P_r}\nabla T. \tag*{(7)}

The ideal gas law relates the temperature TT with pressure and density as

T=1cv11−γpρ.(8)T = \frac{1}{c_v}\frac{1}{1-\gamma}\frac{p}{\rho}. \tag*{(8)}

With the flux term defined, ∇u\nabla\mathbf{u} can be substituted by q\mathbf{q} so that Equation (1) can be rewritten as a first order system thus,

∂u∂t+∇⋅fα(u,q)=0,qα−∇uα=0.(9)\begin{aligned} \frac{\partial\mathbf{u}}{\partial t}+\nabla\cdot\mathbf{f}_{\alpha}(\mathbf{u},\mathbf{q}) &= 0,\\ \mathbf{q}_{\alpha}-\nabla\mathbf{u}_{\alpha} &= 0. \tag*{(9)} \end{aligned}

When applying FR to solve the Navier-Stokes equations in a domain Ω\Omega, the first step is to tessellate the domain with non-overlapping, conforming elements thus

Ω=⋃e∈EΩe,Ωe=⋃n=1∣Ωe∣Ωen,⋂e∈E⋂n=1∣Ωe∣Ωen=∅.(10)\Omega=\bigcup_{e\in\mathcal{E}}\Omega_e,\qquad \Omega_e=\bigcup_{n=1}^{|\Omega_e|}\Omega_{en},\qquad \bigcap_{e\in\mathcal{E}}\bigcap_{n=1}^{|\Omega_e|}\Omega_{en}=\varnothing. \tag*{(10)}

Where ee is a particular element type in the list of available elements E\mathcal{E}, therefore Ωe\Omega_e refers to all elements of type ee, and ∣Ωe∣|\Omega_e| is the number of elements of type ee. Each element Ωen\Omega_{en} is then mapped to a reference element Ω^e\widehat{\Omega}_e via a mapping function Men\mathcal{M}_{en} defined as

x=Men(x~),x~=Men−1(x),\mathbf{x}=\mathcal{M}_{en}(\widetilde{\mathbf{x}}),\qquad \widetilde{\mathbf{x}}=\mathcal{M}_{en}^{-1}(\mathbf{x}),

and this is illustrated for a quadrilateral element in Figure 1.

Image not extracted

Figure 1. Mapping function from physical space to reference space for a quadrilateral element.

Geometric Jacobian matrices can be defined from the mapping functions thus

Jen=[Jenij]=∂Meni∂x~j,Jen=det⁡Jen,\mathbf{J}_{en}=\left[J_{enij}\right]=\frac{\partial\mathcal{M}_{eni}}{\partial\widetilde{x}_j},\qquad J_{en}=\det\mathbf{J}_{en},
Jen−1=[Jenij−1]=∂Meni−1∂x~j,Jen−1=det⁡Jen−1=1Jen.\mathbf{J}_{en}^{-1}=\left[J_{enij}^{-1}\right]=\frac{\partial\mathcal{M}_{eni}^{-1}}{\partial\widetilde{x}_j},\qquad J_{en}^{-1}=\det\mathbf{J}_{en}^{-1}=\frac{1}{J_{en}}.

The definitions above will be used to transform quantities to and from reference element space. In order to transform Equation (9) into reference space, transformed solution u~enα\tilde{u}_{en\alpha}, transformed flux f~nα\tilde{\mathbf{f}}_{n\alpha}, and transformed gradient q~enα\tilde{\mathbf{q}}_{en\alpha} are defined thus

u~enα=u~enα(x~,t)=Jen(x~)uenα(Men(x~),t),(11)\tilde{u}_{en\alpha}=\tilde{u}_{en\alpha}(\tilde{\mathbf{x}},t)=J_{en}(\tilde{\mathbf{x}})u_{en\alpha}(\mathcal{M}_{en}(\tilde{\mathbf{x}}),t), \tag*{(11)}
f~enα=f~enα(x~,t)=Jen(x~)Jen−1(Men(x~))fenα(Men(x~),t),(12)\tilde{\mathbf{f}}_{en\alpha}=\tilde{\mathbf{f}}_{en\alpha}(\tilde{\mathbf{x}},t)=J_{en}(\tilde{\mathbf{x}})J_{en}^{-1}(\mathcal{M}_{en}(\tilde{\mathbf{x}}))\mathbf{f}_{en\alpha}(\mathcal{M}_{en}(\tilde{\mathbf{x}}),t), \tag*{(12)}
q~enα=q~enα(x~,t)=JenT(x~)qenα(Men(x~),t),(13)\tilde{\mathbf{q}}_{en\alpha}=\tilde{\mathbf{q}}_{en\alpha}(\tilde{\mathbf{x}},t)=J_{en}^{T}(\tilde{\mathbf{x}})\mathbf{q}_{en\alpha}(\mathcal{M}_{en}(\tilde{\mathbf{x}}),t), \tag*{(13)}

and for a more compact definition let ∇~=∂/∂x~i\tilde{\nabla}=\partial/\partial\tilde{x}_{i}. Then Equation (9) can be written as,

∂uenα∂t+Jen−1∇~⋅f~enα=0,q~enα−∇~uenα=0.(14)\begin{aligned} \frac{\partial u_{en\alpha}}{\partial t}+J_{en}^{-1}\tilde{\nabla}\cdot\tilde{\mathbf{f}}_{en\alpha}&=0,\\ \tilde{\mathbf{q}}_{en\alpha}-\tilde{\nabla}u_{en\alpha}&=0. \tag*{(14)} \end{aligned}

Now that the equation in the discretized domain is defined, the next step is to define set of solution points inside the elements and flux points at element interfaces. FR method represents the solution inside the elements by using a polynomial of order pp. The solution across the element interfaces is allowed to be discontinuous. Selection of the solution and flux point sets affects the properties of the numerical scheme as indicated in various publications such as [10, 11, 12]. The formulation given in this section is valid for any solution and flux point set.

First, let x~eζ(u)\tilde{\mathbf{x}}_{e\zeta}^{(u)} be the set of solution points for each reference element e∈Ee\in\mathcal{E}. ζ\zeta is the solution point index in an element and satisfies 0≤ζ<Ne(u)0\leq\zeta<N_{e}^{(u)}, where Ne(u)N_{e}^{(u)} is the number of solution points in element type ee. Now a nodal basis set ℓeζ(u)(x~)\ell_{e\zeta}^{(u)}(\tilde{\mathbf{x}}) can be defined where the nodal basis polynomial ℓeζ(u)\ell_{e\zeta}^{(u)} satisfies ℓeζ(u)(x~eσ(u))=δζσ\ell_{e\zeta}^{(u)}(\tilde{\mathbf{x}}_{e\sigma}^{(u)})=\delta_{\zeta\sigma}. Next, a set of flux points x~eζ(f)\tilde{\mathbf{x}}_{e\zeta}^{(f)} on ∂Ω^e\partial\hat{\Omega}_{e} is also defined, where 0≤ζ<Ne(f)0\leq\zeta<N_{e}^{(f)} and Ne(f)N_{e}^{(f)} is the number of flux points at the interfaces of the element type ee. These flux points are constrained such that all paired flux points across interfaces match in terms of global coordinates, Men(x~eζ(f))=Me′n′(x~e′ζ′(f))\mathcal{M}_{en}(\tilde{\mathbf{x}}_{e\zeta}^{(f)})=\mathcal{M}_{e'n'}(\tilde{\mathbf{x}}_{e'\zeta'}^{(f)}), where ′' denotes the corresponding interface from the neighbouring element. Furthermore, there is an associated outward-pointing normal vector for each flux point given by n^~eζ(f)\tilde{\hat{\mathbf{n}}}_{e_{\zeta}^{(f)}}. The solution points, flux points, and an interface between a quadrilateral element and triangular element are all demonstrated in Figure 2.

Image not extracted

Figure 2. Solution points and flux points for a quadrilateral and a triangular elements.

The first step in the FR method is obtaining the discontinuous solution at the flux points ueσnα(f)u_{e_{\sigma n_{\alpha}}^{(f)}} from the solution state at the solution points ueζnα(u)u_{e_{\zeta n_{\alpha}}^{(u)}} as

ueσnα(f)=ueζnα(u)ℓeζ(u)(x~eσ(f))(15)u_{e_{\sigma n_{\alpha}}^{(f)}} = u_{e_{\zeta n_{\alpha}}^{(u)}}\ell_{e_{\zeta}}^{(u)}\left(\tilde{x}_{e_{\sigma}}^{(f)}\right) \tag*{(15)}

Then, the discontinuous solution at the interfaces can be used to obtain a common solution via the LDG method [13, 14] which is defined as

C(uL,uR)=(12−β)uL+(12+β)uR.(16)\mathcal{C}(u_L,u_R) = \left(\frac{1}{2}-\beta\right)u_L + \left(\frac{1}{2}+\beta\right)u_R. \tag*{(16)}

It is important to note that C(uL,uR)\mathcal{C}(u_L,u_R) is not in general equal to C(uR,uL)\mathcal{C}(u_R,u_L). Therefore it is important to visit all the flux point pairs in the domain only once and assign the common value to both points. Consequently, the following equalities hold

Cα(ueσnα(f),ueσˉnα(f))=Cαueσnα(f)=Cαueσˉnα(f).(17)\mathcal{C}_{\alpha}\left(u_{e_{\sigma n_{\alpha}}}^{(f)},u_{e_{\bar{\sigma}n_{\alpha}}}^{(f)}\right) = \mathcal{C}_{\alpha}u_{e_{\sigma n_{\alpha}}}^{(f)} = \mathcal{C}_{\alpha}u_{e_{\bar{\sigma}n_{\alpha}}}^{(f)}. \tag*{(17)}

A correction procedure is then used to obtain a C0C^{0} continuous solution across elements. For this purpose, there is a correction function associated with each flux point in the reference element. geζ(f)\mathbf{g}_{e_{\zeta}}^{(f)} is the vector correction function which satisfies n^~eσ(f)⋅geζ(f)(x~eσ(f))=δζσ\tilde{\hat{\mathbf{n}}}_{e_{\sigma}}^{(f)} \cdot\mathbf{g}_{e_{\zeta}}^{(f)}\left(\tilde{x}_{e_{\sigma}}^{(f)}\right) = \delta_{\zeta\sigma}. The form of geζ(f)\mathbf{g}_{e_{\zeta}}^{(f)} determines a particular FR scheme. Further details on the correction function can be found in [15].

Combining the above, Equation 11c can be expressed as

q~eζnα(u)=[n~eσ(f)⋅∇~eσ(f)(x~){Eαueσnα(f)−ueσnα(f)}+u~eνnα(u)⋅∇~ℓeν(u)(x~)]x~=x~eζ(u).(18)\widetilde{\mathbf{q}}^{(u)}_{e\zeta n\alpha}=\left[\widetilde{\mathbf{n}}^{(f)}_{e\sigma}\cdot\widetilde{\nabla}^{(f)}_{e\sigma}(\widetilde{\mathbf{x}})\left\{\mathcal{E}_{\alpha}u^{(f)}_{e\sigma n\alpha}-u^{(f)}_{e\sigma n\alpha}\right\}+\widetilde{\mathbf{u}}^{(u)}_{e\nu n\alpha}\cdot\widetilde{\nabla}\ell^{(u)}_{e\nu}(\widetilde{\mathbf{x}})\right]_{\widetilde{\mathbf{x}}=\widetilde{\mathbf{x}}^{(u)}_{e\zeta}}. \tag*{(18)}

This equation simply computes the transformed gradient by using the analytic derivation of the basis polynomial ℓe\ell_e together with the solution at solution points, and adds the contribution of the jump between the discontinuous solution at the flux points and the common solution at flux points.

The physical gradients at solution points and at flux points can be computed using approaches of Kopriva [16] and Sun et al. [17] as

qeζnα(u)=Jen−T(x~eσ(u))q~eζnα(u),(19)\mathbf{q}^{(u)}_{e\zeta n\alpha}=\mathbf{J}^{-T}_{en}\left(\widetilde{\mathbf{x}}^{(u)}_{e\sigma}\right)\widetilde{\mathbf{q}}^{(u)}_{e\zeta n\alpha}, \tag*{(19)}
qeζnα(f)=ℓeζ(u)(x~eσ(f))q~eζnα(u).(20)\mathbf{q}^{(f)}_{e\zeta n\alpha}=\ell^{(u)}_{e\zeta}\left(\widetilde{\mathbf{x}}^{(f)}_{e\sigma}\right)\widetilde{\mathbf{q}}^{(u)}_{e\zeta n\alpha}. \tag*{(20)}

The auxiliary equation is now solved and transformed flux can be obtained as

f~eσnα(u)=Jeσn(u)Jeσn−1fα(ueσn(u),qeσn(u)),(21)\widetilde{\mathbf{f}}^{(u)}_{e\sigma n\alpha}=\mathbf{J}^{(u)}_{e\sigma n}\mathbf{J}^{-1}_{e\sigma n}\mathbf{f}_{\alpha}\left(\mathbf{u}^{(u)}_{e\sigma n},\mathbf{q}^{(u)}_{e\sigma n}\right), \tag*{(21)}

where Jeσn(u)=det⁡(Jen−T(x~eσ(u)))\mathbf{J}^{(u)}_{e\sigma n}=\det\left(\mathbf{J}^{-T}_{en}\left(\widetilde{\mathbf{x}}^{(u)}_{e\sigma}\right)\right). Now a similar procedure used in Equation (15) can be applied here to obtain the normal transformed flux at flux points as

feσnα(f⊥)=ℓeζ(u)(x~eσ(f))n~eσ(f)⋅f~eσnα(u).(22)\mathbf{f}^{(f\perp)}_{e\sigma n\alpha}=\ell^{(u)}_{e\zeta}\left(\widetilde{\mathbf{x}}^{(f)}_{e\sigma}\right)\widetilde{\mathbf{n}}^{(f)}_{e\sigma}\cdot\widetilde{\mathbf{f}}^{(u)}_{e\sigma n\alpha}. \tag*{(22)}

With the discontinuous solution and the physical gradient at the flux points, the next step is to obtain the common normal flux for each flux point pair in the domain. The inviscid component of the flux is computed using a Riemann solver [18, 19]. The viscous component of the flux is obtained by using the Local Discontinuous Galerkin (LDG) method as described in [13] and it is defined as

F~v(fLv,fRv,n^L)=n^L⋅((12+β)fLv+(12−β)fRv)+τ(uL−uR),(23)\widetilde{\mathcal{F}}^{v}\left(\mathbf{f}^{v}_{L},\mathbf{f}^{v}_{R},\widehat{\mathbf{n}}_{L}\right)=\widehat{\mathbf{n}}_{L}\cdot\left(\left(\frac{1}{2}+\beta\right)\mathbf{f}^{v}_{L}+\left(\frac{1}{2}-\beta\right)\mathbf{f}^{v}_{R}\right)+\tau(\mathbf{u}_{L}-\mathbf{u}_{R}), \tag*{(23)}

where τ\tau is a penalty parameter, fLv=fv(uL,qL)\mathbf{f}^{v}_{L}=\mathbf{f}^{v}(\mathbf{u}_{L},\mathbf{q}_{L}), fRv=fv(uR,qR)\mathbf{f}^{v}_{R}=\mathbf{f}^{v}(\mathbf{u}_{R},\mathbf{q}_{R}), and β\beta controls the upwinding or downwinding.

F~α\widetilde{\mathcal{F}}_{\alpha} is the operator for the common normal flux at the interface, and f(f⊥)\mathbf{f}^{(f\perp)} denotes the normal flux at a flux point. Note that interfaces between elements conform and we have n^σn(f)=−n^σ′n′(f)\hat{\mathbf n}_{\sigma n}^{(f)}=-\hat{\mathbf n}_{\sigma' n'}^{(f)}. Due to the conservation property of the numerical scheme, we always have F~σnα(f⊥)=−F~σ′n′α(f⊥)\widetilde{\mathcal F}_{\sigma n\alpha}^{(f_\perp)}=-\widetilde{\mathcal F}_{\sigma' n'\alpha}^{(f_\perp)}, and the full form of the common normal flux operator can be given as,

F~σnα(f⊥)=−F~σ′n′α(f⊥)=F~(uσn(f),uσ′n′(f),qσn(f),qσ′n′(f),n^σn(f)).(24)\widetilde{\mathcal F}_{\sigma n\alpha}^{(f_\perp)}=-\widetilde{\mathcal F}_{\sigma' n'\alpha}^{(f_\perp)}=\widetilde{\mathcal F}\left(\mathbf u_{\sigma n}^{(f)},\mathbf u_{\sigma' n'}^{(f)},\mathbf q_{\sigma n}^{(f)},\mathbf q_{\sigma' n'}^{(f)},\hat{\mathbf n}_{\sigma n}^{(f)}\right). \tag*{(24)}

Next, we need to obtain the flux at solution points f~εσnα(u)\widetilde{\mathbf f}_{\varepsilon\sigma n\alpha}^{(u)} from the solution state at solution points uεσnα(u)\mathbf u_{\varepsilon\sigma n\alpha}^{(u)} using (3) and 5. The flux at solution points will then be used to obtain the normal flux at flux points fεσnα(f⊥)\mathbf f_{\varepsilon\sigma n\alpha}^{(f_\perp)}. The difference between the flux and the common normal flux at flux points is used in the correction procedure analogous to the (18). Finally, assembling all of the steps defined above, we can define an expression for the divergence of the continuous flux as,

(∇~⋅f~)εσnα(u)=[∇~⋅g~(f)(x~){F~σnα(f⊥)−fσnα(f⊥)}+f~ενnα(u)⋅∇~φεν(u)(x~)]x~=x~εσ(u).(25)\left(\widetilde{\nabla}\cdot\widetilde{\mathbf f}\right)_{\varepsilon\sigma n\alpha}^{(u)} = \left[ \widetilde{\nabla}\cdot\widetilde{\mathbf g}^{(f)}(\widetilde{\mathbf x}) \left\{ \widetilde{\mathcal F}_{\sigma n\alpha}^{(f_\perp)} -\mathbf f_{\sigma n\alpha}^{(f_\perp)} \right\} +\widetilde{\mathbf f}_{\varepsilon\nu n\alpha}^{(u)} \cdot\widetilde{\nabla}\varphi_{\varepsilon\nu}^{(u)}(\widetilde{\mathbf x}) \right]_{\widetilde{\mathbf x}=\widetilde{\mathbf x}_{\varepsilon\sigma}^{(u)}}. \tag*{(25)}

which results in a semi-discretised form of the governing system.

Anti-aliasing formulation

FR uses collocation based projections to obtain the transformed flux at the solution points. This approach is efficient but may result in aliasing errors where the energy from unresolved modes gets erroneously transferred into resolved modes and consequently this results in stability problems as well as accuracy issues. One way to overcome aliasing errors is using L2L^2 based projections with suitable quadrature rules [2].

Two types of anti-aliasing are considered here, flux anti-aliasing and surface-flux anti-aliasing. Flux anti-aliasing uses fluxes at quadrature points to perform an L2 projection of flux and then samples this projection at the original solution points. Surface-flux anti-aliasing applies the flux correction operation in a similar way. First, fluxes at flux points are used to obtain the fluxes at the quadrature points at the interfaces. Then, common flux and common solution are evaluated at the quadrature points at the interfaces, and finally common flux and solution are sampled at the original flux points. These procedures require extra operators and changes in some of the existing operators. First, flux anti-aliasing requires two new matrix multiplication operations. One of them operates on the solution and the other operates on the gradients at the solution points. Next, surface-flux anti-aliasing requires changes in many of the existing operators in the FR algorithm.

First, for flux anti-aliasing, interpolation from solution points to quadrature points can be expressed as

ueσnα(q)=ueξnα(u)ℓeξ(u)(x~eσ(q))(26)u_{e\sigma n\alpha}^{(q)}=u_{e\xi n\alpha}^{(u)}\ell_{e\xi}^{(u)}\left(\widetilde{x}_{e\sigma}^{(q)}\right) \tag*{(26)}
qeσnα(q)=qeξnα(u)ℓeξ(u)(x~eσ(q))(27)\mathbf{q}_{e\sigma n\alpha}^{(q)}=\mathbf{q}_{e\xi n\alpha}^{(u)}\ell_{e\xi}^{(u)}\left(\widetilde{x}_{e\sigma}^{(q)}\right) \tag*{(27)}

Then the solution and gradients at the quadrature points are used to evaluate the flux at quadrature points, replacing (21) thus

f~eσnα(q)=Jeσn(u)Jeσn−1(q)fα(ueσn(q),qeσn(q)).(28)\widetilde{\mathbf{f}}_{e\sigma n\alpha}^{(q)}=J_{e\sigma n}^{(u)}J_{e\sigma n}^{-1(q)}\mathbf{f}_{\alpha}\left(u_{e\sigma n}^{(q)},\mathbf{q}_{e\sigma n}^{(q)}\right). \tag*{(28)}

Then, in order to sample the fluxes at the original solution points the following operation can be used

f~eξnα(u)=ψeν(x~eξ(u))ωeσ(q)ψeν(x~eσ(q))f~eσnα(q).(29)\widetilde{\mathbf{f}}_{e\xi n\alpha}^{(u)}=\psi_{e\nu}\left(\widetilde{x}_{e\xi}^{(u)}\right)\omega_{e\sigma}^{(q)}\psi_{e\nu}\left(\widetilde{x}_{e\sigma}^{(q)}\right)\widetilde{\mathbf{f}}_{e\sigma n\alpha}^{(q)}. \tag*{(29)}

Next, a similar strategy can be used for the surface-flux anti-aliasing. Surface-flux anti-aliasing evaluates the solution and flux at the quadrature points, obtains the common flux and common solution, and samples these back at the original flux points. However, instead of bringing up more operations to carry out the interpolations, surface-flux anti-aliasing can be implemented simply by replacing flux points by quadrature points at the interfaces. This will result in changes in all the operations that include data at the flux points yet the formulation will be the same as presented in the previous section.

Formulation in Terms of Kernels

The operations required to implement the FR algorithm described in Section 2 can be cast in terms of individual kernels. These can be grouped into two main types, matrix-matrix multiplication and point-wise kernels. In PyFR, various third party libraries such as LIBXSMM [20] and GiMMiK [?] are made available for the matrix-matrix multiplication kernels. Point-wise kernels are implemented through PyFR-Mako, a bespoke templating language derived from Mako, which is then rendered into low-level platform-specific code.

In order to formulate the FR algorithm in terms of kernels, we define the various constant operator matrices and point-wise kernels, alongside various storage matrices for state variables and some intermediate data.

First, we define the disudisu kernel, which corresponds to Equation (15). This kernel evaluates the solution at flux points using the solution at solution points, and can be formulated as a matrix multiplication. The constant operator matrix of element type ee for the disudisu kernel, Me0\mathbf{M}_e^0, is defined as

(Me0)σζ=ℓeζ(f)(x~σ(f)),dim⁡Me0=Ne(f)×Ne(u),(30)\left(\mathbf{M}_e^0\right)_{\sigma\zeta} = \ell_{e\zeta}^{(f)}\left(\widetilde{\mathbf{x}}_\sigma^{(f)}\right), \qquad\dim\mathbf{M}_e^0 = N_e^{(f)} \times N_e^{(u)}, \tag*{(30)}

the array Ue(u)\mathbf{U}_e^{(u)} for storing the solution state at solution points is defined as

(Ue(u))ζ(nα)=ueζnα(u),dim⁡Ue(u)=Ne(u)×NV∣Ωe∣.(31)\left(\mathbf{U}_e^{(u)}\right)_{\zeta(n\alpha)} = u_{e\zeta n\alpha}^{(u)}, \qquad\dim\mathbf{U}_e^{(u)} = N_e^{(u)} \times N_V \lvert\Omega_e\rvert. \tag*{(31)}

Therefore, the disudisu kernel can be cast as a matrix multiplication as,

Ue(f)=Me0Ue(u),(32)\mathbf{U}_e^{(f)} = \mathbf{M}_e^0\mathbf{U}_e^{(u)}, \tag*{(32)}

where Ue(f)\mathbf{U}_e^{(f)} is the storage for the solution state at flux points which has dimension dim⁡Ue(f)=Ne(f)×NV∣Ωe∣\dim\mathbf{U}_e^{(f)} = N_e^{(f)} \times N_V\lvert\Omega_e\rvert.

The next five kernels are dedicated to obtaining the gradients of the solution which is a requirement for calculating the flux and common flux. The first operation related to the gradients is obtaining the common solution at the flux points which is defined in Equation (17). The con_ucon\_u kernel is defined to obtain the common solution as

Ce(f)=con_u(Ue(f),ne(f)),(33)\mathbf{C}_e^{(f)} = con\_u\left(\mathbf{U}_e^{(f)}, \mathbf{n}_e^{(f)}\right), \tag*{(33)}

which is a point-wise kernel with considerable indirect memory access to main memory. The con_ucon\_u kernel uses up-winding or down-winding to determine the common solution at the element interfaces, and writes the solution into a sub-region of the Fe(f)\mathbf{F}_{e}^{(f)} array in order to save memory usage. For clarity we will refer to this sub-region of the Fe(f)\mathbf{F}_{e}^{(f)} matrix as Ce(f)\mathbf{C}_{e}^{(f)} after its data is replaced by the con_u kernel. ne(f)\mathbf{n}_{e}^{(f)} refers to the outward pointing normal vector at the flux points.

Afterwards, the corrections have to be applied in order to obtain the gradients. The procedure to apply corrections is described in Equation (18). Therefore the following two constant matrices are defined thus

(Me4)cσ=[∇ℓe(u)~(x~)]x~=x~eσ(u)T,dim⁡Me4=Ne(u)×NDNe(u),(34)\left(\mathbf{M}_{e}^{4}\right)_{c\sigma}=\left[\widetilde{\nabla\ell_{e}^{(u)}}\left(\widetilde{\mathbf{x}}\right)\right]_{\widetilde{\mathbf{x}}=\widetilde{\mathbf{x}}_{e\sigma}^{(u)}}^{\mathsf{T}}, \qquad\dim\mathbf{M}_{e}^{4}=N_{e}^{(u)}\times N_{D}N_{e}^{(u)}, \tag*{(34)}
(Me6)cσ=[n~e(f)⋅∇~⋅g~eσ(f)(x~)]x~=x~eσ(u),dim⁡Me6=Ne(u)×Ne(f).(35)\left(\mathbf{M}_{e}^{6}\right)_{c\sigma}=\left[\widetilde{\mathbf{n}}_{e}^{(f)}\cdot\widetilde{\nabla}\cdot\widetilde{\mathbf{g}}_{e\sigma}^{(f)}\left(\widetilde{\mathbf{x}}\right)\right]_{\widetilde{\mathbf{x}}=\widetilde{\mathbf{x}}_{e\sigma}^{(u)}}, \qquad\dim\mathbf{M}_{e}^{6}=N_{e}^{(u)}\times N_{e}^{(f)}. \tag*{(35)}

Using the matrices defined above, (18) can be written in matrix multiplication form as

Q~e(u)=Me6{C~e(f)−U~e(f)}+Me4U~e(u)=Me6{C~e(f)−Me0U~e(u)}+Me4U~e(u)=Me6C~e(f)−{Me4−Me6Me0}U~e(u),(36)\begin{aligned} \widetilde{\mathbf{Q}}_{e}^{(u)}&=\mathbf{M}_{e}^{6}\{\widetilde{\mathbf{C}}_{e}^{(f)}-\widetilde{\mathbf{U}}_{e}^{(f)}\}+\mathbf{M}_{e}^{4}\widetilde{\mathbf{U}}_{e}^{(u)}\\ &=\mathbf{M}_{e}^{6}\{\widetilde{\mathbf{C}}_{e}^{(f)}-\mathbf{M}_{e}^{0}\widetilde{\mathbf{U}}_{e}^{(u)}\}+\mathbf{M}_{e}^{4}\widetilde{\mathbf{U}}_{e}^{(u)}\\ &=\mathbf{M}_{e}^{6}\widetilde{\mathbf{C}}_{e}^{(f)}-\{\mathbf{M}_{e}^{4}-\mathbf{M}_{e}^{6}\mathbf{M}_{e}^{0}\}\widetilde{\mathbf{U}}_{e}^{(u)}, \tag*{(36)} \end{aligned}

where the Q~e(u)\widetilde{\mathbf{Q}}_{e}^{(u)} array is the storage for the gradients at solution points and has a size dim⁡Q~e(u)=NDNe(u)×NV∣Ωe∣\dim\widetilde{\mathbf{Q}}_{e}^{(u)}=N_{D}N_{e}^{(u)}\times N_{V}|\Omega_{e}|. The size of Q~e(u)\widetilde{\mathbf{Q}}_{e}^{(u)} is NDN_{D} times bigger compared to that of U~e(u)\widetilde{\mathbf{U}}_{e}^{(u)} as there are NDN_{D} many components of gradient for each state variable. As there are two arrays and two constant matrix multiplications involved in this operation, it can be cast as two consecutive matrix multiplication kernels. Corresponding to the first and second terms in the equation, tgradcoru and tgradpcoru kernels are defined respectively. The tgradpcoru is called first and the output is stored at Q~e(u)\widetilde{\mathbf{Q}}_{e}^{(u)} thus

Q~e(u)={Me4−Me6Me0}U~e(u).(37)\widetilde{\mathbf{Q}}_{e}^{(u)}=\{\mathbf{M}_{e}^{4}-\mathbf{M}_{e}^{6}\mathbf{M}_{e}^{0}\}\widetilde{\mathbf{U}}_{e}^{(u)}. \tag*{(37)}

Next, the tgradcoru kernel is called and the result is added to Q~e(u)\widetilde{\mathbf{Q}}_{e}^{(u)} as

Q~e(u)=Q~e(u)+Me6C~e(f).(38)\widetilde{\mathbf{Q}}_{e}^{(u)}=\widetilde{\mathbf{Q}}_{e}^{(u)}+\mathbf{M}_{e}^{6}\widetilde{\mathbf{C}}_{e}^{(f)}. \tag*{(38)}

Then, a point-wise kernel, gradcoru is defined in order to obtain the gradients of the solution at solution points in physical space as formulated in Equation (19) thus

Qe(u)=gradcoru(Je(u),Q~e(u)).(39)\mathbf{Q}_{e}^{(u)} = gradcoru\left(\mathbf{J}_{e}^{(u)}, \widetilde{\mathbf{Q}}_{e}^{(u)}\right). \tag*{(39)}

Afterwards, the gradcoru_fpts kernel is defined in order to evaluate the physical gradients at the flux points corresponding to Equation (20). This is also a matrix multiplication kernel and the associated constant operator matrix is Me5\mathbf{M}_{e}^{5}, which is defined as

(Me5)σζ=diag⁡(Me0,…,Me0),dim⁡Me5=NDNe(f)×NDNe(u).(40)\left(\mathbf{M}_{e}^{5}\right)_{\sigma\zeta} = \operatorname{diag}\left(\mathbf{M}_{e}^{0}, \ldots, \mathbf{M}_{e}^{0}\right), \qquad\dim\mathbf{M}_{e}^{5} = N_{D}N_{e}^{(f)} \times N_{D}N_{e}^{(u)}. \tag*{(40)}

Therefore, gradcoru_fpts kernel can be defined as

Qe(f)=Me5Qe(u),(41)\mathbf{Q}_{e}^{(f)} = \mathbf{M}_{e}^{5}\mathbf{Q}_{e}^{(u)}, \tag*{(41)}

where Qe(f)\mathbf{Q}_{e}^{(f)} is the storage array for the gradients at flux points with the dimension dim⁡Qe(f)=NDNe(f)×NV∣Ωe∣\dim\mathbf{Q}_{e}^{(f)} = N_{D}N_{e}^{(f)} \times N_{V}|\Omega_{e}|.

Next, with the solution and its gradient available at the element interfaces, it is now possible to obtain the common interface flux at the element interfaces as in Equation (24). For this purpose, the comm_flux kernel is defined thus

De(f)=comm_flux(Ue(f),Qe(f),ne(f)),(42)\mathbf{D}_{e}^{(f)} = comm\_flux\left(\mathbf{U}_{e}^{(f)}, \mathbf{Q}_{e}^{(f)}, \mathbf{n}_{e}^{(f)}\right), \tag*{(42)}

which is a point-wise kernel with a significant indirect memory access requirement. The comm_flux kernel calls a Riemann flux function on pairs of flux points reading Ue(f)\mathbf{U}_{e}^{(f)} and Fe(f)\mathbf{F}_{e}^{(f)}, then returning De(f)\mathbf{D}_{e}^{(f)}. In practice it overwrites the data over Ue(f)\mathbf{U}_{e}^{(f)}. However for clarity, we will refer to the Ue(f)\mathbf{U}_{e}^{(f)} matrix as De(f)\mathbf{D}_{e}^{(f)} after its data is replaced by the comm_flux kernel.

Then, the next step is obtaining the transformed flux at the solution points as in Equation (21). A point-wise kernel, tdisf, is defined to evaluate the flux at solution points thus

F~e(u)=tdisf(Ue(u),Qe(u),xe(u)).(43)\widetilde{\mathbf{F}}_{e}^{(u)} = tdisf\left(\mathbf{U}_{e}^{(u)}, \mathbf{Q}_{e}^{(u)}, \mathbf{x}_{e}^{(u)}\right). \tag*{(43)}

This kernel takes the solution Ue(u)\mathbf{U}_{e}^{(u)}, gradient at the solution points Qe(u)\mathbf{Q}_{e}^{(u)}, and the element coordinates xe(u)\mathbf{x}_{e}^{(u)}, and returns the transformed flux F~e(u)\widetilde{\mathbf{F}}_{e}^{(u)}, where $\widetilde{\mathbf{F}}_{e}^{(u)} 天天中彩票买 has a size dim⁡F~e(u)=NDNe(u)×NV∣Ωe∣\dim\widetilde{\mathbf{F}}_{e}^{(u)} = N_{D}N_{e}^{(u)} \times N_{V}|\Omega_{e}|. Because the gradients at the solution points are not needed any more, the Qe(u)\mathbf{Q}_{e}^{(u)} array is overwritten by Fe(u)\mathbf{F}_{e}^{(u)} and the array is referred as Fe(u)\mathbf{F}_{e}^{(u)} from this point onwards.

In order to rewrite the final semi-discrete form in (25) in matrix multiplication format, the following constant operator matrices are defined,

(Me1)ζσ=[∇~ℓe(u)(x~)]x~=x~e(u),dim⁡Me1=Ne(u)×NDNe(u)(44)(\mathbf{M}_{e}^{1})_{\zeta\sigma} = \left[\widetilde{\nabla}\ell_{e}^{(u)}(\widetilde{\mathbf{x}})\right]_{\widetilde{\mathbf{x}}=\widetilde{\mathbf{x}}_{e}^{(u)}}, \qquad\dim\mathbf{M}_{e}^{1} = N_{e}^{(u)} \times N_{D}N_{e}^{(u)} \tag*{(44)}
(Me2)ζσ=[ℓe(u)(x~e(f))n~^eσ(f)]T,dim⁡Me2=Ne(f)×NDNe(u)(45)(\mathbf{M}_{e}^{2})_{\zeta\sigma} = \left[\ell_{e}^{(u)}(\widetilde{\mathbf{x}}_{e}^{(f)})\widehat{\widetilde{\mathbf{n}}}_{e\sigma}^{(f)}\right]^{T}, \qquad\dim\mathbf{M}_{e}^{2} = N_{e}^{(f)} \times N_{D}N_{e}^{(u)} \tag*{(45)}
(Me3)ζσ=[∇~⋅g~eζ(f)(x~)]x~=x~e(u),dim⁡Me3=Ne(u)×Ne(f).(46)(\mathbf{M}_{e}^{3})_{\zeta\sigma} = \left[\widetilde{\nabla}\cdot\widetilde{\mathbf{g}}_{e\zeta}^{(f)}(\widetilde{\mathbf{x}})\right]_{\widetilde{\mathbf{x}}=\widetilde{\mathbf{x}}_{e}^{(u)}}, \qquad\dim\mathbf{M}_{e}^{3} = N_{e}^{(u)} \times N_{e}^{(f)}. \tag*{(46)}

Then (25) can be rewritten using the matrices defined above as

R~e(u)=Me3{D~e(f)−Me2F~e(u)}+Me1F~e(u)=Me3D~e(f)+{Me1−Me3Me2}F~e(u),(47)\begin{aligned} \widetilde{\mathbf{R}}_{e}^{(u)} = \mathbf{M}_{e}^{3}\left\{\widetilde{\mathbf{D}}_{e}^{(f)}-\mathbf{M}_{e}^{2}\widetilde{\mathbf{F}}_{e}^{(u)}\right\}+\mathbf{M}_{e}^{1}\widetilde{\mathbf{F}}_{e}^{(u)} \\ &= \mathbf{M}_{e}^{3}\widetilde{\mathbf{D}}_{e}^{(f)}+\left\{\mathbf{M}_{e}^{1}-\mathbf{M}_{e}^{3}\mathbf{M}_{e}^{2}\right\}\widetilde{\mathbf{F}}_{e}^{(u)}, \tag*{(47)} \end{aligned}

where the R~e(u)\widetilde{\mathbf{R}}_{e}^{(u)} array has a size dim⁡R~e(u)=Ne(u)×NV∣Ωe∣\dim\widetilde{\mathbf{R}}_{e}^{(u)} = N_{e}^{(u)} \times N_{V}|\Omega_{e}|, equivalent to the size of the solution array Ue(u)\mathbf{U}_{e}^{(u)}. The kernel implementation of (25) consists of two matrix multiplication kernels that correspond to the two terms in the right hand side of the equation, tdivtconf and tdivpcorf respectively. The tdivpcorf kernel is called first and the data in the R~e(u)\widetilde{\mathbf{R}}_{e}^{(u)} array is overwritten by the result as

R~e(u)={Me1−Me3Me2}F~e(u).(48)\widetilde{\mathbf{R}}_{e}^{(u)}=\left\{\mathbf{M}_{e}^{1}-\mathbf{M}_{e}^{3}\mathbf{M}_{e}^{2}\right\}\widetilde{\mathbf{F}}_{e}^{(u)}. \tag*{(48)}

Next, the tdivtconf kernel is executed and the result is added to R~e(u)\widetilde{\mathbf{R}}_{e}^{(u)} thus

R~e(u)=R~e(u)+Me3D~e(f).(49)\widetilde{\mathbf{R}}_{e}^{(u)}=\widetilde{\mathbf{R}}_{e}^{(u)}+\mathbf{M}_{e}^{3}\widetilde{\mathbf{D}}_{e}^{(f)}. \tag*{(49)}

Finally, the negdivconf kernel is defined in order to obtain the divergence of flux in the physical space thus

Re(u)=negdivconf⁡(det⁡Je(u),R~e(u)).(50)\mathbf{R}_{e}^{(u)}=\operatorname{negdivconf}\left(\det\mathbf{J}_{e}^{(u)},\widetilde{\mathbf{R}}_{e}^{(u)}\right). \tag*{(50)}

Anti-aliasing Kernels

Flux anti-aliasing. Flux anti-aliasing requires two additional kernels which evaluate the solution state and gradients at quadrature points within each element, such that the tdisftdisf kernel can then evaluate these fluxes at these same quadrature points. For this purpose uqptsuqpts and gradcoru_qptsgradcoru\_qpts kernels are defined which interpolate the solution and gradients at solution points to quadrature points. They are both matrix multiplication kernels corresponding to Equations 24 and 25 respectively. The associated operator matrix Me7\mathbf{M}_{e}^{7} for the uqptsuqpts kernel is defined as

(Me7)σζ=ℓeζ(u)(x~eσ(q)),dim⁡Me7=Ne(u)×Ne(q),(51)\left(\mathbf{M}_{e}^{7}\right)_{\sigma\zeta}=\ell_{e\zeta}^{(u)}\left(\widetilde{x}_{e\sigma}^{(q)}\right),\qquad\dim\mathbf{M}_{e}^{7}=N_{e}^{(u)}\times N_{e}^{(q)}, \tag*{(51)}

and the uqptsuqpts kernel is defined as

Ue(q)=Me7Ue(u).(52)\mathbf{U}_{e}^{(q)}=\mathbf{M}_{e}^{7}\mathbf{U}_{e}^{(u)}. \tag*{(52)}

The operator matrix Me10\mathbf{M}_{e}^{10} for gradcoru_qptsgradcoru\_qpts is given as

(Me10)σζ=diag⁡(Me7,…,Me7),dim⁡Me10=NDNe(u)×NDNe(q),(53)\left(\mathbf{M}_{e}^{10}\right)_{\sigma\zeta}=\operatorname{diag}\left(\mathbf{M}_{e}^{7},\ldots,\mathbf{M}_{e}^{7}\right),\qquad\dim\mathbf{M}_{e}^{10}=N_{D}N_{e}^{(u)}\times N_{D}N_{e}^{(q)}, \tag*{(53)}

and the gradcoru_qptsgradcoru\_qpts kernel can be expressed as

Qe(q)=Me10Qe(u).(54)\mathbf{Q}_{e}^{(q)}=\mathbf{M}_{e}^{10}\mathbf{Q}_{e}^{(u)}. \tag*{(54)}

When flux anti-aliasing is turned on, the tdisftdisf kernel evaluates the flux at quadrature points using the solution and gradients at quadrature points thus it can be redefined as

F~e(q)=tdisf(Ue(q),Qe(q),xe),(55)\widetilde{\mathbf{F}}_{e}^{(q)}=tdisf\left(\mathbf{U}_{e}^{(q)},\mathbf{Q}_{e}^{(q)},\mathbf{x}_{e}\right), \tag*{(55)}

which obtains the modal coefficients in the solution space. Then, the operator matrix Me8\mathbf{M}_{e}^{8} is defined to convert these modal coefficients into nodal values at the solution points.

(Me8)σζ=ψeν(x~eζ(u))ωeν(q)ψeν(x~eσ(q)),dim⁡Me8=Ne(q)×Ne(u).(56)\left(\mathbf{M}_{e}^{8}\right)_{\sigma\zeta}=\psi_{e\nu}\left(\widetilde{x}_{e\zeta}^{(u)}\right)\omega_{e\nu}^{(q)}\psi_{e\nu}\left(\widetilde{x}_{e\sigma}^{(q)}\right),\qquad\dim\mathbf{M}_{e}^{8}=N_{e}^{(q)}\times N_{e}^{(u)}. \tag*{(56)}

Me9\mathbf{M}_{e}^{9} is the block diagonal form of the Me8\mathbf{M}_{e}^{8} matrix and it is defined as

(Me9)σζ=diag⁡(Me8,…,Me8),dim⁡Me9=NDNe(q)×NDNe(u).(57)\left(\mathbf{M}_{e}^{9}\right)_{\sigma\zeta}=\operatorname{diag}\left(\mathbf{M}_{e}^{8},\ldots,\mathbf{M}_{e}^{8}\right),\qquad\dim\mathbf{M}_{e}^{9}=N_{D}N_{e}^{(q)}\times N_{D}N_{e}^{(u)}. \tag*{(57)}

This operation is carried out by the tdivtpcorftdivtpcorf kernel with a small update therefore when flux anti-aliasing is in use tdivtpcorftdivtpcorf kernel becomes

R~e(u)={Me1−Me3Me2}Me9F~e(q).(58)\widetilde{\mathbf{R}}_{e}^{(u)}=\left\{\mathbf{M}_{e}^{1}-\mathbf{M}_{e}^{3}\mathbf{M}_{e}^{2}\right\}\mathbf{M}_{e}^{9}\widetilde{\mathbf{F}}_{e}^{(q)}. \tag*{(58)}

Surface-flux anti-aliasing. Surface-flux anti-aliasing on the other hand changes many of the constant operator matrices that act on flux points. Because the formulation is valid for any flux point set, turning on surface-flux anti-aliasing does not alter any of the kernel or the formulation, however it changes the data movement requirements. A schematic that includes all the Navier-Stokes kernels and the additional flux anti-aliasing kernels is given in Figure 3.

Figure 3. Kernel prerequisites map for Navier-Stokes Solver including optional Flux AA kernels.

Kernel Execution Order and Data Movement Requirements

As a baseline for comparison, data movement and bandwidth requirements are first analysed for PyFR version v1.11.0, which has no cache blocking support. Similar to analysis carried out for the Euler solver in [1], time integration related operations are not included in data movement requirements and speedups therefore will only reflect the performance of evaluating the RHS. In reality, a time integrator such as RK4 will need to be used to move forward in time which requires additional data movement that consumes bandwidth and it will slightly reduce the performance per RHS call.

Kernel execution order for the Navier-Stokes solver in PyFR version v1.11.0 is demonstrated in Figure 4 including the flux anti-aliasing kernels. Without cache blocking support, each kernel is executed for the entire input and output arrays and therefore the data movement requirement is directly related to the size of input and output arrays. Data movement requirements of each kernel are tabulated in Table A.6 for a hexahedral mesh, normalized per element, at polynomial orders p=3p = 3 and p=4p = 4, double precision, and including flux and surface-flux anti-aliasing on/off. Non-temporal stores are used whenever possible for the matrix multiplication kernels through the LIBXSMM library [20] to reduce the data movement requirements for the qualifying kernels. Total data movement requirements for polynomial orders p=3p = 3 and p=4p = 4 for anti-aliasing on and off is summarised in Table 1.

Figure 4. Current kernel execution order. Arrows going over green line indicate main memory access.

Data Movement Req. Per RHS Per Element [KiB/RHS/element]AA offFull AA
HexaPrismHexaPrism
p=3p = 3p=4p = 4p=3p = 3p=4p = 4p=3p = 3p=4p = 4p=3p = 3p=4p = 4
Total Bandwidth143.63276.35102.44163.88224.41381.12144.80238.05

Table 1. Total data movement requirement for PyFR version v1.11.0.

Tensor Product Factorisation of Anti-aliasing Operators

Turning on anti-aliasing in PyFR brings in additional operators and changes in the existing kernels. A straightforward implementation of these new operators and changes in the existing kernels results in dense matrix operators. However, it is well known in the literature that for tensor product elements these operators can be cast as multiple sparse factors as opposed to a single dense matrix multiplication. Converting a single dense operator into a chain of sparse operations reduces the FLOP requirement significantly, but a direct implementation can make the code overly bandwidth bound and the performance gains would be limited. However for tensor product elements such as hexahedra and prisms, it is possible to factor the dense operator into sparse components. In this section, we examine ways to factor the new dense operators associated with flux anti-aliasing and the existing operators that are converted into a dense form due to surface-flux anti-aliasing. A breakdown of all the affected kernels due to flux and surface-flux anti-aliasing is shown in Table 2.

KernelOperatorflux AAsurf-flux AAfull AA
disuM0M^{0}M0M^{0}M0M^{0}
con-uPointwise
tgradpcoruM4−M6M0M^{4}-M^{6}M^{0}M4−M6M0M^{4}-M^{6}M^{0}M4−M6M0M^{4}-M^{6}M^{0}
tgradcoruM6M^{6}M6M^{6}M6M^{6}
gradcoruPointwise
gradcoru_fptsI3⊗M0I_{3}\otimes M^{0}I3⊗M0I_{3}\otimes M^{0}I3⊗M0I_{3}\otimes M^{0}
comm_fluxPointwise
uqptsM7M^{7}M7M^{7}M7M^{7}
gradcoru_qptsI3⊗M7I_{3}\otimes M^{7}I3⊗M7I_{3}\otimes M^{7}I3⊗M7I_{3}\otimes M^{7}
tdisfPointwise
tdivtpcorfM1−M3M2M^{1}-M^{3}M^{2}(M1−M3M2)M9(M^{1}-M^{3}M^{2})M^{9}M1−M3M2M^{1}-M^{3}M^{2}(M1−M3M2)M9(M^{1}-M^{3}M^{2})M^{9}
tdivtconfM3M^{3}M3M^{3}M3M^{3}
negdivconfPointwise

Table 2. Changes in operator matrices due to anti-aliasing. Blue colour indicates a change due to flux anti-aliasing, and red colour indicates a change due to surface-flux anti-aliasing.

First, flux anti-aliasing brings in two new operators, M7\mathrm{M}^{7} and M9\mathrm{M}^{9}. M7\mathrm{M}^{7} operator interpolates data in solution points to quadrature points. If implemented directly, it is a single dense operator. However, for a hexahedral element this process can be factored into three sparse components. The process is explained in detail in [8]. The sparse components obtained after factorisation correspond to interpolations in xx, yy, and zz directions. Sampling the nodal coefficients at solution points using the modal representation at quadrature points can also be factored into three sparse components. M9\mathrm{M}^{9} operator applies the reverse operation for the gradients at solution points, so its a block diagonal matrix that applies the reverse interpolation for three components of the gradient at each solution point.

The interpolations between solution points and quadrature points are the main building blocks for decomposing the rest of the operators that are associated with the surface-flux anti-aliasing. The only extra operation involved with surface-flux anti-aliasing is the interpolation to flux points at the interfaces. The M0M^{0} operator without anti-aliasing that interpolates data from solution points to flux points will be used together with the M7M^{7} or M9M^{9} operator to form the sparse factors of the M0M^{0} operator with surface-flux anti-aliasing.

Extension to Prism Elements

The decomposition into sparse factors is apparent for hexahedral elements, however, there is no generic way of obtaining sparse factors for tetrahedral or pyramid elements. Prisms on the other hand are slightly different. A direct approach for obtaining the modal coefficients at quadrature points by using the nodal coefficients at solution points in a prism would require a dense operator matrix as shown in Figure 5.

Figure 5. Solution points for prism elements with polynomial orders p=2p = 2 and p=3p = 3. Point distribution is based on William-Shun at the triangular cross sections and based on Gauss-Legendre along the zz-direction. A direct interpolation between p=2p = 2 and p=3p = 3 prisms solution points results in a dense operator matrix as any point in p=3p = 3 depend on all the points in p=2p = 2 as indicated with orange points.

However, a prism can be generated by a tensor production of a triangle and a line that is perpendicular to the triangle. Depending on the polynomial order, there are a number of triangular planar regions inside a prism and the solution points are located on these regions. Therefore, obtaining modal coefficients at quadrature points using the nodal coefficients at solution points, which is an operation carried out by the qptsu kernel can be simplified and reformulated in a two part operation. The first operation obtains the solution at the quadrature points within triangular planes in a prism, and then a second operation obtains the solution at a set of triangular planes inside the prism. The procedure is illustrated in Figure 6. The former requires a block structured operator while the latter is a sparse operation. As there is a sparse component in the factored formulation, cache blocking can be used effectively to implement this.

Image not extracted

Figure 6. An intermediate state shown in the middle is introduced to decompose interpolation from p=2p = 2 to p=3p = 3 into one block diagonal and one sparse factor. First, an interpolation is carried out on triangular planes only resulting in a block diagonal operator as indicated with the orange points. The next step is interpolating values along the zz-direction that results in a sparse operator as indicated with the blue points.

Application of Cache Blocking in Tensor Product Factorisation

There are a few different ways to implement the tensor product operations after obtaining the sparse factorisation. The naive implementation would simply call a matrix multiplication library for each sparse factor. This would reduce the FLOP requirement significantly due to reduced number of non-zero entries in the sparse factors provided that a sparse matrix multiplication library is used. However, it would result in increased bandwidth use because the intermediate solutions between each of the separate kernel invocations have to be stored in memory and this results in unnecessary reads and writes. The alternative is using cache blocking strategies. These make it possible to store the intermediate results in CPU cache, and reduce the main memory access and data movement requirements significantly. Using sparse factors rather than a single dense matrix reduces the FLOP requirement, and cache blocking strategy eliminates the excess data movement by utilizing CPU cache as an intermediate storage. Therefore, it is possible to get the best of both worlds by enabling cache blocking for the tensor product operations. Table 3 shows how the FLOP and data movement requirements differ between the regular approach where a single dense matrix is used, the naive approach where a matrix multiplication library is called for each sparse factor, and the ideal approach where cache blocking is enabled together with the sparse factors. Furthermore, a roofline model [21] demonstrating the

Factored
FLOP [GFLOPS]DenseDirectCache Blocked
Data Movement [GiB]1.957.811.95
FLOP/Byte14.480.542.16

Table 3. FLOP and Data movement requirements for the tdivtconf kernel on hexahedral elements for three different implementations

strating the FLOP/Byte ratio for a selection of Navier-Stokes kernels with full anti-aliasing are given in Figure 7 before and after applying tensor product factorisation using the cache blocking strategy. It is clear from Table 3 and Figure 7 that the tensor product factorisation using the cache blocking strategy for the standalone tensor product kernels reduces the FLOP requirement while keeping the data movement requirement from main memory the same. As a result, the profile of these individual kernels shifted towards a smaller FLOP/Byte region where they would normally be bandwidth bound from main memory. However, now that most of the kernels are bandwidth bound, a kernel grouping strategy can be implemented to eliminate the unnecessary data movements between kernels that exchange data. When these approaches are implemented together, there is a reduction in both FLOP and data movement requirements.

Image not extracted

Figure 7. A selection of the Navier-Stokes kernels are shown in the figure for anti-aliasing off and full anti-aliasing on a full hexahedral mesh. The remaining kernels have similar properties if not exactly the same.

In summary, tensor product factorisation with cache blocking reduces the FLOP requirement significantly while keeping the amount of data movement from main memory the same. Then, a kernel grouping strategy can be implemented to reduce the total amount of data movement requirements to improve the performance even further.

Theoretical Predictions and Benchmarking in PyFR

A kernel grouping configuration for the Navier-Stokes solver is examined in this section both for anti-aliasing on. The test case used for the performance comparisons is the compressible Taylor-Green Vortex. It is a typical test case for the validation of high-order software and it is used in [22] for comparing PyFR performance against industry standard codes. Also, it is one of the test cases in the high-order workshops [23]. The configuration and mesh files used here are taken from Vermeire [22], and the numerical results are compared against spectral DNS results from van Rees et al. [24]. Taylor-Green Vortex case is initialized with the following initial conditions

vx=+U0sin⁡(x/L)cos⁡(y/L)cos⁡(z/L),vy=+U0cos⁡(x/L)sin⁡(y/L)cos⁡(z/L),vz=0,p=p0+ρ0U0216(cos⁡(2x/L)+cos⁡(2y/L))(cos⁡(2z/L)+2),ρ=pRT0(59)\begin{aligned} v_x &= +U_0 \sin(x/L)\cos(y/L)\cos(z/L),\\ v_y &= +U_0 \cos(x/L)\sin(y/L)\cos(z/L),\\ v_z &= 0,\\ p &= p_0 + \frac{\rho_0 U_0^2}{16}\left(\cos(2x/L)+\cos(2y/L)\right)\left(\cos(2z/L)+2\right),\\ \rho&= \frac{p}{RT_0} \tag*{(59)} \end{aligned}

in a cube domain with periodic boundary conditions in all the faces with dimensions [−πL,+πL]3[-\pi L,+\pi L]^3. Performance comparisons of the cache blocking approach is executed at two different polynomial orders, p=3p=3 and p=4p=4, with a structured mesh consisting of 64364^3 and 52352^3 hexahedra respectively so that the degree of freedom is approximately equivalent. The Reynolds number Re=1600Re=1600 based on the length LL and velocity U0U_0. The Mach number based on U0U_0 is M=0.1M=0.1 so that the simulation is effectively incompressible. Firstly, a simulation is carried out using the cache blocking approach in order to validate the implementation. The evolution of enstropy is compared with the spectral DNS result [24] and shown in Figure 8. The results from cache blocking show a good agreement with the spectral DNS results. A snapshot at t=10tct=10t_c is shown in Figure 9 with isosurfaces based on Q-criterion [25] and coloured by velocity magnitude.

Image not extracted

Figure 8. Temporal evolution of enstrophy obtained with cache blocking approach implemented in PyFR. Simulation is carried out on a 52352^3 all hexadhedral mesh at p=4p = 4 with anti-aliasing off.

Q-criterion isosurfaces coloured based on velocity magnitude

Figure 9. Q-criterion isosurfaces coloured based on velocity magnitude for a snapshot at t=10tct = 10t_{\mathrm{c}}.

Kernel Grouping Configuration

The main consideration when forming kernel groupings is the amount of bandwidth saving. Bandwidth saving is maximised when a chain of kernels that write and read from the same location in the memory grouped together. The more data kernels in a group exchange by writing and reading the same piece of memory the better the savings and therefore speedups. Therefore the first step is analysing the kernels in the Navier-Stokes solver and determine chain of kernels that exchange data. When compared with the Euler solver, there are more constraints in Navier-Stokes solver and this limits the number of possible kernel grouping configurations. As with the Euler solver, eliminating the intermediate storage array F(u)\mathbf{F}^{(u)} is possible in Navier-Stokes solver as well and it saves a considerable amount of bandwidth. There are 6 kernels in total that operate on F(u)\mathbf{F}^{(u)}, and a kernel group with all of them can save a significant amount of data movement. The kernels are tgradpcoru, tgradcoru, gradcoru, gradcoru_fpts, tdisf, and tdivpcorf. In case of flux anti-aliasing the additional kernels, qptsu and gradcoru_qpts, are also added to this kernel grouping as they also make use of F(u)\mathbf{F}^{(u)} as well as introducing a new temporary storages U(q)\mathbf{U}^{(q)} and F(q)\mathbf{F}^{(q)} that can be stored entirely in the CPU cache for a single block. Afterwards, there is only one other kernel grouping possibility is left which consist of tdivtconf and negdivconf. A schematic of the kernel grouping configuration is given in Figure 10 for full anti-aliasing. Data movement requirements of the present kernel grouping configuration with anti-aliasing on are tabulated in Table A.7.

Figure 10. Kernel grouping configuration of the Navier-Stokes solver with flux anti-aliasing. Arrows going over green line indicate main memory access. Dashed gray arrow indicates write orders avoided due to cache blocking, while solid arrow indicate a definite read/write operation. Constant arrays such as xx, which are not changed by the kernels, are omitted for simplicity.

Further, the speedups obtained in three different platforms with an Arm based AWS Graviton3, Intel Xeon Platinum 8488C, and AMD EPYC 7742 are given in Table 4. The highest speedup is 3.67x compared to PyFR v1.11.0 and it is obtained when running at p=4p = 4 on hexahedral elements with full anti-aliasing on Intel Xeon Platinum 8488C CPUs. GDOF/s parameters are also tabulated in Table 5 and compared with PyFR v1.11.0 and ZEFR [26] on NVIDIA V100 GPU. ’GDOF/s’ parameter makes it possible to compare performance of PyFR on different platforms such as GPUs and CPUs. When cache blocking is enabled with anti-aliasing, single socket CPU performance of PyFR exceeds the single device GPU performance.

AA offFull AA
HexaPrismHexaPrism
Speedupsp=3p=3p=4p=4p=3p=3p=4p=4p=3p=3p=4p=4p=3p=3p=4p=4
Prediction2.102.311.992.162.342.622.192.41
AMD2.222.171.871.913.313.421.832.02
Arm2.172.531.761.782.822.031.681.67
Intel2.612.761.831.902.833.671.952.08

Table 4. Theoretical speedup predictions compared with observed speedups on AMD EPYC 7742, Arm based AWS Graviton3, and Intel Xeon Platinum 8488C CPUs.

AA offFull AA
HexaPrismHexaPrism
GDOF/sp=3p=3p=4p=4p=3p=3p=4p=4p=3p=3p=4p=4p=3p=3p=4p=4
PyFR Cache Blocking - AMD0.5200.6290.4270.4860.3180.3680.2490.277
PyFR Cache Blocking - Arm0.9211.1620.6170.7020.5380.3390.3470.359
PyFR Cache Blocking - Intel0.8300.9830.5500.6320.4990.5960.3100.348
PyFR v1.11.0 - NVIDIA V1000.6210.6650.1470.117
ZEFR [26] - NVIDIA V1000.600.65------

Table 5. Comparison of GDOF/s: PyFR with Cache Blocking on AMD EPYC 7742 CPU, Arm based AWS Graviton3 CPU, Intel Xeon Platinum 8488C CPU, PyFR v1.11.0 on NVIDIA V100 GPU, and ZEFR on NVIDIA V100 GPU.

Conclusion

In this article, a methodology for applying cache blocking in FR has been extended and implemented for the Navier-Stokes solver with full anti-aliasing support on mixed grids in PyFR for CPUs. Cache blocking was used to eliminate unnecessary data movements between kernels that exchange data at the main memory level, as an alternative to kernel fusion. In particular, per-core private data cache on CPUs was used as a temporary storage to enable data exchanges between consecutive kernels. As the amount of cache is limited, these kernels are executed on small sub-regions of the domain that fit in the available cache. In addition to eliminating data exchanges between kernels, cache blocking was used to implement dense interpolation kernels associated with anti-aliasing as well. These dense interpolation kernels first decomposed into sparse matrix factors using tensor product factorisation, and cache blocking is used as a temporary storage for the intermediate results when applying these chain of sparse matrix factors consecutively. As a result, cache blocking saved a significant amount of data movement from main memory. The amount of savings in data movements then used to construct a theoretical model to predict the performance gains. Finally, the implementation was benchmarked using a compressible 3D Taylor-Green vortex test case on both hexahedral and prismatic grids, with third- and forth-order solution polynomials. A comparison between the theoretical expectations and speedups obtained in practice compared to PyFR v1.11.0 were given.

Acknowledgements

The first author gratefully acknowledges the President’s PhD Scholarship provided by Imperial College London. The authors would like to thank the Engineering and Physical Sciences Research Council for their support via an Early Career Fellowship (EP/R030340/1).

Data Movement Requirements

A breakdown of data movement requirements for PyFR v1.11.0 and PyFR with kernel grouping are provided in Tables A.6 and A.7.

KernelInputOutputFormulaAA off: Hexa p=3p=3AA off: Hexa p=4p=4AA off: Prism p=3p=3AA off: Prism p=4p=4Full AA: Hexa p=3p=3Full AA: Hexa p=4p=4Full AA: Prism p=3p=3Full AA: Prism p=4p=4
disudisuUe(u)\mathrm{U}_{e}^{(u)}Ue(f)\mathrm{U}_{e}^{(f)}S(Ue(u))+S(Ue(f))\mathcal{S}(\mathrm{U}_{e}^{(u)})+\mathcal{S}(\mathrm{U}_{e}^{(f)})6.2510.744.227.038.3613.325.668.79
con_ucon\_uDe(f),ne(f)\mathbf{D}_{e}^{(f)},\mathbf{n}_{e}^{(f)}De(f)\mathbf{D}_{e}^{(f)}S(ne(u))+2S(De(f))\mathcal{S}(\mathbf{n}_{e}^{(u)})+2\mathcal{S}(\mathbf{D}_{e}^{(f)})10.5016.417.4411.4814.7221.5610.3315.00
tgradpcorutgradpcoruUe(u)\mathbf{U}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(Ue(u))+S(Fe(u))\mathcal{S}(\mathbf{U}_{e}^{(u)})+\mathcal{S}(\mathbf{F}_{e}^{(u)})10.0019.536.2511.7210.0019.536.2511.72
tgradcorutgradcoruUe(f)\mathbf{U}_{e}^{(f)}Fe(u)\mathbf{F}_{e}^{(u)}S(Ue(f))+2S(Fe(u))\mathcal{S}(\mathbf{U}_{e}^{(f)})+2\mathcal{S}(\mathbf{F}_{e}^{(u)})18.7535.1612.0321.6820.8637.7313.4823.44
gradcorugradcoruFe(u),xe(u),Je(u)\mathbf{F}_{e}^{(u)},\mathbf{x}_{e}^{(u)},\mathbf{J}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(Je(u))+S(xe(u))+2S(Fe(u))\mathcal{S}(\mathbf{J}_{e}^{(u)})+\mathcal{S}(\mathbf{x}_{e}^{(u)})+2\mathcal{S}(\mathbf{F}_{e}^{(u)})15.6930.469.8818.3015.6930.469.8318.30
gradcoru_fptsgradcoru\_fptsFe(u)\mathbf{F}_{e}^{(u)}Fe(f)\mathbf{F}_{e}^{(f)}S(Fe(u))+S(Fe(f))\mathcal{S}(\mathbf{F}_{e}^{(u)})+\mathcal{S}(\mathbf{F}_{e}^{(f)})18.7549.8020.6321.0925.0839.9616.9926.37
uqptsuqptsUe(u)\mathbf{U}_{e}^{(u)}Ue(q)\mathbf{U}_{e}^{(q)}S(Ue(u))+S(Ue(q))\mathcal{S}(\mathbf{U}_{e}^{(u)})+\mathcal{S}(\mathbf{U}_{e}^{(q)})----7.3813.324.497.85
gradcoru_qptsgradcoru\_qptsFe(u)\mathbf{F}_{e}^{(u)}Fe(q)\mathbf{F}_{e}^{(q)}S(Fe(u))+S(Fe(q))\mathcal{S}(\mathbf{F}_{e}^{(u)})+\mathcal{S}(\mathbf{F}_{e}^{(q)})----22.1539.9613.4823.55
tdisftdisfUe(u),xe(u),Fe(u)\mathbf{U}_{e}^{(u)},\mathbf{x}_{e}^{(u)},\mathbf{F}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(Ue(u))+S(xe(u))+2S(Fe(u))\mathcal{S}(\mathbf{U}_{e}^{(u)})+\mathcal{S}(\mathbf{x}_{e}^{(u)})+2\mathcal{S}(\mathbf{F}_{e}^{(u)})17.6934.3711.1320.6534.3759.2520.6534.59
tdivpcorftdivpcorfFe(u)\mathbf{F}_{e}^{(u)}Re(u)\mathbf{R}_{e}^{(u)}S(Fe(u))+S(Re(u))\mathcal{S}(\mathbf{F}_{e}^{(u)})+\mathcal{S}(\mathbf{R}_{e}^{(u)})10.0019.536.2511.7217.1530.2010.3517.70
comm_fluxcomm\_fluxDe(f),Fe(f),ne(f)\mathbf{D}_{e}^{(f)},\mathbf{F}_{e}^{(f)},\mathbf{n}_{e}^{(f)}De(f)\mathbf{D}_{e}^{(f)}S(ne(u))+S(Fe(f))+2S(De(f))\mathcal{S}(\mathbf{n}_{e}^{(u)})+\mathcal{S}(\mathbf{F}_{e}^{(f)})+2\mathcal{S}(\mathbf{D}_{e}^{(f)})21.7533.9815.4023.7932.3046.8822.6332.58
tdivtconftdivtconfUe(f)\mathbf{U}_{e}^{(f)}Re(u)\mathbf{R}_{e}^{(u)}S(Ue(f))+2S(Re(u))\mathcal{S}(\mathbf{U}_{e}^{(f)})+2\mathcal{S}(\mathbf{R}_{e}^{(u)})8.7515.635.789.9610.8518.207.2311.72
negdivconfnegdivconfRe(u),Je(u)\mathbf{R}_{e}^{(u)},\mathbf{J}_{e}^{(u)}Re(u)\mathbf{R}_{e}^{(u)}S(Je(u))+2S(Re(u))\mathcal{S}(\mathbf{J}_{e}^{(u)})+2\mathcal{S}(\mathbf{R}_{e}^{(u)})5.5010.743.446.455.5010.743.446.45
Total Bandwidth143.63276.35102.44163.88224.41381.12144.80238.05

Table A.6. Current Navier-Stokes Data Movement Requirements. Data Movement Requirements Per RHS Per Element [KiB/RHS/element]

KernelInputOutputFormulaAA offFull AA
HexaPrismHexaPrism
p=3p = 3p=4p = 4p=3p = 3p=4p = 4p=3p = 3p=4p = 4p=3p = 3p=4p = 4
disudisuUe(u)\mathbf{U}_{e}^{(u)}Ue(f)\mathbf{U}_{e}^{(f)}S(Ue(u))+S(Ue(f))\mathcal{S}(\mathbf{U}_{e}^{(u)}) + \mathcal{S}(\mathbf{U}_{e}^{(f)})6.2510.744.227.038.3613.325.668.79
con_ucon\_uDe(f),ne(f)\mathbf{D}_{e}^{(f)}, \mathbf{n}_{e}^{(f)}De(f)\mathbf{D}_{e}^{(f)}S(ne(u))+2S(De(f))\mathcal{S}(\mathbf{n}_{e}^{(u)}) + 2\mathcal{S}(\mathbf{D}_{e}^{(f)})10.5016.417.4411.4814.7221.5610.3315.00
tgradpcorutgradpcoruUe(u)\mathbf{U}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(Ue(u))\mathcal{S}(\mathbf{U}_{e}^{(u)})2.504.881.562.932.504.881.562.93
tgradcorutgradcoruUe(f)\mathbf{U}_{e}^{(f)}Fe(u)\mathbf{F}_{e}^{(u)}S(Ue(f))\mathcal{S}(\mathbf{U}_{e}^{(f)})3.755.862.664.105.868.444.105.86
gradcorugradcoruFe(u),xe(c),Je(u)\mathbf{F}_{e}^{(u)}, \mathbf{x}_{e}^{(c)}, \mathbf{J}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(Je(u))+S(xe(u))\mathcal{S}(\mathbf{J}_{e}^{(u)}) + \mathcal{S}(\mathbf{x}_{e}^{(u)})0.691.160.450.730.691.160.450.73
gradcoru_fptsgradcoru\_fptsFe(u)\mathbf{F}_{e}^{(u)}Fe(f)\mathbf{F}_{e}^{(f)}S(Fe(f))\mathcal{S}(\mathbf{F}_{e}^{(f)})11.2517.587.9712.3017.5825.3112.3017.58
uqptsuqptsUe(u)\mathbf{U}_{e}^{(u)}Ue(q)\mathbf{U}_{e}^{(q)}00----0000
gradcoru_qptsgradcoru\_qptsFe(u)\mathbf{F}_{e}^{(u)}Fe(q)\mathbf{F}_{e}^{(q)}00----0000
tdisftdisfUe(u),xe(c),Fe(u)\mathbf{U}_{e}^{(u)}, \mathbf{x}_{e}^{(c)}, \mathbf{F}_{e}^{(u)}Fe(u)\mathbf{F}_{e}^{(u)}S(xe(u))\mathcal{S}(\mathbf{x}_{e}^{(u)})0.190.190.140.140.190.190.140.14
tdivpcorftdivpcorfFe(u)\mathbf{F}_{e}^{(u)}Re(u)\mathbf{R}_{e}^{(u)}S(Re(u))\mathcal{S}(\mathbf{R}_{e}^{(u)})2.504.881.562.932.504.881.562.93
comm_fluxcomm\_fluxDe(f),Fe(f),ne(f)\mathbf{D}_{e}^{(f)}, \mathbf{F}_{e}^{(f)}, \mathbf{n}_{e}^{(f)}De(f)\mathbf{D}_{e}^{(f)}S(ne(u))+S(Fe(f))+2S(De(f))\mathcal{S}(\mathbf{n}_{e}^{(u)}) + \mathcal{S}(\mathbf{F}_{e}^{(f)}) + 2\mathcal{S}(\mathbf{D}_{e}^{(f)})21.7533.9815.4123.7932.3046.8822.6332.58
tdivtconftdivtconfUe(f)\mathbf{U}_{e}^{(f)}Re(u)\mathbf{R}_{e}^{(u)}S(Ue(f))+S(Re(u))\mathcal{S}(\mathbf{U}_{e}^{(f)}) + \mathcal{S}(\mathbf{R}_{e}^{(u)})6.2510.744.227.038.3613.325.668.79
negdivconfnegdivconfRe(u),Je(u)\mathbf{R}_{e}^{(u)}, \mathbf{J}_{e}^{(u)}Re(u)\mathbf{R}_{e}^{(u)}S(Je(u))+S(Re(u))\mathcal{S}(\mathbf{J}_{e}^{(u)}) + \mathcal{S}(\mathbf{R}_{e}^{(u)})3.005.861.883.523.005.861.883.52
Total68.43112.1047.3675.8495.86145.6266.1598.70
Predicted Speedup2.102.311.992.162.342.622.192.41

Table A.7. Navier-Stokes Data Movement Requirements with kernel grouping. Data Movement Requirements Per RHS Per Element [KiB/RHS/element]

References

  1. [1]S. Akkurt, F. Witherden, P. Vincent, Cache blocking strategies applied to flux reconstruction, Computer Physics Communications 271 (2022) 108193. doi:https://doi.org/10.1016/j.cpc.2021.108193.
  2. [2]J. S. Park, F. D. Witherden, P. E. Vincent, High-order implicit large-eddy simulations of flow over a naca0021 aerofoil, AIAA Journal 55 (7) (2017) 2186–2197. arXiv:https://doi.org/10.2514/1.J055304, doi:10.2514/1.J055304. URL https://doi.org/10.2514/1.J055304
  3. [3]S. A. Orszag, Spectral methods for problems in complex geometries, Journal of Computational Physics 37 (1) (1980) 70–92. doi:https://doi.org/10.1016/0021-9991(80)90005-4. URL https://www.sciencedirect.com/science/article/pii/0021999180900054
  4. [4]S. J. Sherwin, G. E. Karniadakis, A new triangular and tetrahedral basis for high-order (hp) finite elements in Engineering, International Journal for Numerical Methods in Engineering 38 (22) (1995) 3775–3802. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/nme.1620382204, doi:https://doi.org/10.1002/nme.1620382204. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/nme.1620382204
  5. [5]C. D. Cantwell, S. J. Sherwin, R. M. Kirby, P. H. J. Kelly, From h to p efficiently: Selecting the optimal spectral/hp discretisation in three dimensions, Mathematical Modelling of Natural Phenomena 6 (3) (2011) 84–96. doi:10.1051/mmnp/20116304.DOI
  6. [6]D. Moxey, C. Cantwell, R. Kirby, S. Sherwin, Optimising the performance of the spectral/hp element method with collective linear algebra operations, Computer Methods in Applied Mechanics and Engineering 310 (2016) 628–645. doi:https://doi.org/10.1016/j.cma.2016.07.001. URL https://www.sciencedirect.com/science/article/pii/S0045782516306739
  7. [7]A. Bolis, C. D. Cantwell, R. M. Kirby, S. J. Sherwin, From h to p efficiently: optimal implementation strategies for explicit time-dependent problems using th International Journal for Numerical Methods in Fluids 75 (8) (2014) 591–607. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/fld.3909, doi:https://doi.org/10.1002/fld.3909. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/fld.3909
  8. [8]K. Świrydowicz, N. Chalmers, A. Karakus, T. Warburton, Acceleration of tensor-product operations for high-order finite element methods, The International Journal of High Performance Computing Applications 33 (4) (2019) 735–757. arXiv:https://doi.org/10.1177/1094342018816368, doi:10.1177/1094342018816368. URL https://doi.org/10.1177/1094342018816368
  9. [9]H. T. Huynh, A flux reconstruction approach to high-order schemes including discontinuous galerkin methods, in: 18th AIAA Computational Fluid Dynamics Conference, 2007. doi:10.2514/6.2007–4079.DOI
  10. [10]F. Witherden, P. Vincent, On nodal point sets for flux reconstruction, Journal of Computational and Applied Mathematics 381 (2021) 113014. doi:https://doi.org/10.1016/j.cam.2020.113014. URL https://www.sciencedirect.com/science/article/pii/S0377042720303058
  11. [11]F. Witherden, P. Vincent, On the identification of symmetric quadrature rules for finite element methods, Computers & Mathematics with Applications 69 (10) (2015) 1232–1241. doi:https://doi.org/10.1016/j.camwa.2015.03.017. URL https://www.sciencedirect.com/science/article/pii/S0898122115001224
  12. [12]F. Witherden, J. Park, P. Vincent, An analysis of solution point coordinates for flux reconstruction schemes on tetrahedral elements, Journal of Scientific Computing 69 (2) (2016) 905–920. doi:https://doi.org/10.1007/s10915-016-0204-y. URL https://link.springer.com/article/10.1007/s10915-016-0204-y
  13. [13]J. S. Hesthaven, T. Warburton, Nodal discontinuous Galerkin methods: algorithms, analysis, and applications, Springer Science & Business Media, 2007.DOI
  14. [14]P. Castonguay, D. Williams, P. Vincent, A. Jameson, Energy stable flux reconstruction schemes for advection–diffusion problems, Computer Methods in Applied Mechanics and Engineering 267 (2013) 400–417. doi:https://doi.org/10.1016/j.cma.2013.08.012. URL https://www.sciencedirect.com/science/article/pii/S0045782513002156
  15. [15]P. Vincent, P. Castonguay, A. Jameson, Insights from von neumann analysis of high-order flux reconstruction schemes, Journal of Computational Physics 230 (22) (2011) 8134–8154. doi:https://doi.org/10.1016/j.jcp.2011.07.013. URL https://www.sciencedirect.com/science/article/pii/S0021999111004323
  16. [16]D. A. Kopriva, A staggered-grid multidomain spectral method for the compressible navier–stokes equations, Journal of computational physics 143 (1) (1998) 125–158.DOI
  17. [17]Y. Sun, Z. Wang, Y. Liu, High-Order Multidomain Spectral Difference Method for the Navier-Stokes Equations on Unstructured Hexahedral Grids, Communications in Computational Physics 2 (2) (2007) 310–333.DOI
  18. [18]E. F. Toro, Riemann solvers and numerical methods for fluid dynamics a practical introduction, 3rd Edition, Springer, Berlin, 2006.
  19. [19]V. Rusanov, The calculation of the interaction of non-stationary shock waves and obstacles, U.S.S.R. computational mathematics and mathematical physics 1 (2) (1962) 304–320.DOI
  20. [20]A. Heinecke, G. Henry, M. Hutchinson, H. Pabst, LIBXSMM: Accelerating small matrix multiplications by runtime code generation, in: SC ’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2016, pp. 981–991. doi:10.1109/SC.2016.83.DOI
  21. [21]S. Williams, A. Waterman, D. Patterson, Roofline: An insightful visual performance model for multicore architectures, Commun. ACM 52 (4) (2009) 65–76. doi:10.1145/1498765.1498785. URL https://doi.org/10.1145/1498765.1498785
  22. [22]B. Vermeire, F. Witherden, P. Vincent, On the utility of gpu accelerated high-order methods for unsteady flow simulations: A comparison with i Journal of Computational Physics 334 (2017) 497–521. doi:https://doi.org/10.1016/j.jcp.2016.12.049. URL https://www.sciencedirect.com/science/article/pii/S0021999116307136
  23. [23]Z. Wang, K. Fidkowski, R. Abgrall, F. Bassi, D. Caraeni, A. Cary, H. Deconinck, R. Hartmann, K. Hillewaert, H. Huynh, N. Kroll, G. May, P.-O. Persson, B. van Leer, M. Visbal, High-order CFD methods: current status and perspective, International Journal for Numerical Methods in Fluids 72 (8) (2013) 811–845. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/fld.3767, doi:https://doi.org/10.1002/fld.3767. URL https://onlinelibrary.wiley.com/doi/abs/10.1002/fld.3767
  24. [24]W. M. van Rees, A. Leonard, D. Pullin, P. Koumoutsakos, A comparison of vortex and pseudo-spectral methods for the simulation of periodic vortical flows at hig Journal of Computational Physics 230 (8) (2011) 2794–2805. doi:https://doi.org/10.1016/j.jcp.2010.11.031. URL https://www.sciencedirect.com/science/article/pii/S0021999110006467
  25. [25]J. Hunt, A. Wray, P. Moin, Eddies, streams, and convergence zones in turbulent flows, in: Proceedings of the Summer Program, Center for Tur-bulence Research, Stanford Univ., 1998, pp. 193–208.
  26. [26]J. Romero, J. Crabill, J. Watkins, F. Witherden, A. Jameson, ZEFR: A GPU-accelerated high-order solver for compressible viscous flows using the flux reconstruction Computer Physics Communications 250 (2020) 107169. doi:https://doi.org/10.1016/j.cpc.2020.107169. URL https://www.sciencedirect.com/science/article/pii/S0010465520300229

Paper details

vlnc:W_6uab7bb6
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