Domain-Specific Code Transformations for Computational Science based on the Polyhedral Model

Kulkarni, Kaushik G.

Permalink

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

Description

Title

Domain-Specific Code Transformations for Computational Science based on the Polyhedral Model

Author(s)

Kulkarni, Kaushik G.

Issue Date

2023-08-09

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

Olson, Luke

Doctoral Committee Chair(s)

Kloeckner, Andreas

Committee Member(s)

• Fischer, Paul
• Ham, David

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)

• Loop Transformations
• Polyhedral Model
• Array Programming
• Computational Science

Abstract

Recent advancements in hardware design have shifted the responsibility of optimizing performance from the hardware itself to the programmer. This shift includes decisions related to caching strategies, execution grid sizes, SIMD mapping, and more. These choices significantly impact the overall performance of programs, making it increasingly difficult for general-purpose compilers to achieve roofline performance. In this thesis, we design abstractions that facilitate the integration of domain-specific transformations into the compilation pipeline. We also identify key optimization passes tailored to specific classes of programs, particularly in the field of Scientific Computing. First, this thesis proposes a transformation pipeline for efficient execution of matrix-free Finite Element Method (FEM) operators on GPUs, particularly those lowered from the Unified Form Language (UFL). The assembly kernels corresponding to different variational forms exhibit significant algorithmic variation, posing challenges in achieving roofline performance. To address these challenges, a parametric transform space combined with an auto-tuning scheme is employed. Accompanying performance evaluation using a suite of real-world applications observes that the transformed code delivers at least 50% roofline performance for 70% of the test cases. Furthermore, the portability of the transform strategy is evident across various micro-architectures, function spaces, and different Partial Differential Equations (PDEs). Then, this thesis describes a novel abstraction to record code transformations for the class of Einstein Summation (“einsum”) subprograms. One of the key contributions is a grammar specification that facilitates matching the components of a high-level expression to those in an einsum. This matching can be utilized to transfer the transform knowledge regarding an einsum to a broader class of expressions. This matching is possible through a formulation of a canonical form of an einsum expression. Furthermore, experiments are conducted to compare the proposed approach against the state-of-the-art toolchains utilizing XLA / CUBLAS. The experimental results demonstrate substantial performance improvements, with reported speedups ranging from 1.7–35× for a suite of macro-kernels encountered in Discontinuous Galerkin Finite Element Method (DG-FEM) solvers. Finally, this thesis explores separating concerns in computational science frameworks via a compiler infrastructure based on the n-d array programming paradigm. A sequence of abstractions are proposed that enables the application of domain-specific transformation during the compilation of an array expression graph, both at the loop-level and the computation graph-level. The proposed abstractions are leveraged to implement a DG-FEM solver that realizes primitives as array operations and employs a domain-specific kernel fusion transformation on the array expression graphs during compilation. A comprehensive performance evaluation demonstrates that even in the context of array programming paradigms, domain-specific transformations offer substantial speedups over general-purpose compilers.

Graduation Semester

2023-12

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Kaushik Kulkarni

Owning Collections