Dispersion analysis, time parallelization, and GPU autotuning for finite element methods

Christensen, Nicholas J

Permalink

https://hdl.handle.net/2142/124325 Copy

Description

Title

Dispersion analysis, time parallelization, and GPU autotuning for finite element methods

Author(s)

Christensen, Nicholas J

Issue Date

2024-04-23

Director of Research (if dissertation) or Advisor (if thesis)

Fischer, Paul F

Doctoral Committee Chair(s)

Fischer, Paul F

Committee Member(s)

• Klöckner, Andreas
• Olson, Luke N
• Parish, Eric J

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Finite Element
• Spectral Element
• Dispersion
• Pde
• Autotuning
• Parallel-in-time
• Euler-lagrange
• Least-squares
• Gpu
• Eigenvalue Avoidance
• Einstein Summation

Language

eng

Abstract

This dissertation explores strategies to enhance the accuracy and computational performance of finite element methods. Specifically, we analyze the dispersive error of the spectral element method, investigate a novel least-squares parallel-in-time formulation, and propose an autotuning approach for a discontinuous Galerkin finite element solver. We investigate the dispersion properties of the spectral element method (SEM) when applied to advection and advection-diffusion problems on a 1D periodic domain. Our analysis spans both the well-resolved (asymptotic) limit and the marginally resolved (pre-asymptotic) limit. To achieve this, we systematically explore a wide range of parameters, including wave numbers, element counts, and local polynomial orders. We observe that high-order methods demand fewer points-per-wavelength (PPW) than low-order methods to meet engineering tolerances during long time-integration. Remarkably, Gottlieb’s observation that polynomial-based spectral methods require approximately PPW > 5 for engineering tolerances holds true across various polynomial orders and element counts. Comparing use of exact quadrature on the Gauss-Legendre points and inexact quadrature (employing a diagonal mass matrix) on the Gauss-Lobotto-Legendre points, we find inexact quadrature does not significantly compromise solution accuracies at high polynomial orders. At high polynomial orders (N > 4), we observe error spikes near specific values of PPW disrupt the convergence behavior, regardless of the quadrature method used. These spikes arise from previously identified gaps in the eigenvalue spectrum of the discrete operators, leading to unrepresentable phase velocities. We demonstrate that diffusive mechanisms – whether introduced numerically (via time-relaxation or an upwind discontinuous Galerkin formulation) or arising naturally from the physics of the problem – can largely mitigate these error spikes. A two-dimensional model problem further illustrates the effectiveness of the mitigation strategy. We propose MG-HLS-PinT, a novel parallel-in-time method based on multigrid principles. Derived from a normal-equations formulation of a semi-discrete partial differential equation (PDE), this approach shows potential in accelerating the solution of hyperbolic PDEs. However, it currently demands high processor counts and problems with stringent accuracy demands. We explore several methods of speeding up the approach and identify promising avenues for future exploration. In the context of the MIRGE-Com DGFEM simulation library, we introduce sub-batching as a method to enhance the computation of large fused batched Einstein summation (einsum) GPU kernels. By limiting the number of concurrent einsum computations and minimizing contention for local memory and cache, sub-batching significantly improves performance compared to the baseline.

Graduation Semester

2024-05

Type of Resource

Text

Handle URL

https://hdl.handle.net/2142/124325

Copyright and License Information

Copyright 2024 Nicholas Christensen. CC0: This work has been marked as dedicated to the public domain.

Owning Collections