University of Illinois Urbana-Champaign

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

Christensen, Nicholas J

Content Files
CHRISTENSEN-DISSERTATION-2024.pdf

Permalink

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

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
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
Thesis
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois