@inproceedings{50506b855c144db1b6df7e1cd5fb86bd,
title = "Dataset Sensitive Autotuning of Multi-versioned Code Based on Monotonic Properties: Autotuning in Futhark",
abstract = "Functional languages allow rewrite-rule systems that aggressively generate a multitude of semantically-equivalent but differently-optimized code versions. In the context of GPGPU execution, this paper addresses the important question of how to compose these code versions into a single program that (near-)optimally discriminates them across different datasets. Rather than aiming at a general autotuning framework reliant on stochastic search, we argue that in some cases, a more effective solution can be obtained by customizing the tuning strategy for the compiler transformation producing the code versions. We present a simple and highly-composable strategy which requires that the (dynamic) program property used to discriminate between code versions conforms with a certain monotonicity assumption. Assuming the monotonicity assumption holds, our strategy guarantees that if an optimal solution exists it will be found. If an optimal solution doesn{\textquoteright}t exist, our strategy produces human tractable and deterministic results that provide insights into what went wrong and how it can be fixed. We apply our tuning strategy to the incremental-flattening transformation supported by the publicly-available Futhark compiler and compare with a previous black-box tuning solution that uses the popular OpenTuner library. We demonstrate the feasibility of our solution on a set of standard datasets of real-world applications and public benchmark suites, such as Rodinia and FinPar. We show that our approach shortens the tuning time by a factor of 6 × on average, and more importantly, in five out of eleven cases, it produces programs that are (as high as 10 × ) faster than the ones produced by the OpenTuner-based technique.",
keywords = "Autotuning, Compilers, Flattening, GPGPU, Nested parallelism, Performance",
author = "Philip Munksgaard and Breddam, {Svend Lund} and Troels Henriksen and Gieseke, {Fabian Cristian} and Cosmin Oancea",
year = "2021",
doi = "10.1007/978-3-030-83978-9_1",
language = "English",
isbn = "9783030839772",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "3--23",
editor = "Viktoria Zsok and John Hughes",
booktitle = "Trends in Functional Programming - 22nd International Symposium, TFP 2021, Revised Selected Papers",
address = "Germany",
note = "22nd International Symposium on Trends in Functional Programming, TFP 2021 ; Conference date: 17-02-2021 Through 19-02-2021",
}