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

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Kulkarni, Kaushik G.

Contributors dc:contributor

• Olson, Luke
• Kloeckner, Andreas
• Fischer, Paul
• Ham, David

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

Statement dc:rights

• Copyright 2023 Kaushik Kulkarni

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121927