# On the Representation of Partially Specified Implementations and its Application to the Optimization of Linear Algebra Kernels on GPU

arXiv: https://arxiv.org/abs/1904.03383 · HTML: https://mlsanity.com/paper/1904.03383/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [ytopt: Autotuning Scientific Applications for Energy Efficiency at Large Scales](https://mlsanity.com/paper/2303.16245/) (2023)
- [Customized Monte Carlo Tree Search for LLVM/Polly's Composable Loop Optimization Transformations](https://mlsanity.com/paper/2105.04555/) (2021)
- [Autotuning PolyBench Benchmarks with LLVM Clang/Polly Loop Optimization Pragmas Using Bayesian Optimization (extended version)](https://mlsanity.com/paper/2104.13242/) (2021)

## Abstract (arXiv)

Traditional optimizing compilers rely on rewrite rules to iteratively apply program transformations. This iterative approach hides optimization opportunities behind intermediate transformation steps. For instance, vectorization can only be applied to the innermost loop in a nest: one must first perform a loop interchange before even considering vectorization of an outer loop. In contrast, we propose an implementation framework representing programs as sets of possible implementation decisions. Specifying one decision can have an impact on others in a bidirectional manner: specifying that a loop must be vectorized prevents other loops from being nested inside it; conversely, specifying a loop as an outer loop will prevent it from being vectorized. These optimization decisions commute, obviating the pass ordering problem. We present a constraint programming system to formally define, represent and explore such implementation spaces. We also propose an exploration strategy combining tree search and branch-and-bound; the strength and novelty of this strategy reside in an analytical model of the lower bound on the execution time of a set of possible implementations. We showcase our approach on the construction and exploration of an implementation space for linear algebra kernels running on GPUs. We show this search space is expressive enough to represent complex decisions that fundamentally change the structure of the generated code. We also present preliminary results competitive with the performance of native GPU libraries.