Dataset Sensitive Autotuning of Multi-versioned Code Based on Monotonic Properties: Autotuning in Futhark

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt


  • Fulltext

    Forlagets udgivne version, 768 KB, PDF-dokument

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’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.

TitelTrends in Functional Programming - 22nd International Symposium, TFP 2021, Revised Selected Papers
RedaktørerViktoria Zsok, John Hughes
ForlagSpringer Science and Business Media Deutschland GmbH
ISBN (Trykt)9783030839772
StatusUdgivet - 2021
Begivenhed22nd International Symposium on Trends in Functional Programming, TFP 2021 - Virtual, Online
Varighed: 17 feb. 202119 feb. 2021


Konference22nd International Symposium on Trends in Functional Programming, TFP 2021
ByVirtual, Online
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind12834 LNCS

Antal downloads er baseret på statistik fra Google Scholar og

Ingen data tilgængelig

ID: 299693781