High-performance defunctionalisation in futhark
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
General-purpose massively parallel processors, such as GPUs, have become common, but are difficult to program. Pure functional programming can be a solution, as it guarantees referential transparency, and provides useful combinators for expressing data-parallel computations. Unfortunately, higher-order functions cannot be efficiently implemented on GPUs by the usual means. In this paper, we present a defunctionalisation transformation that relies on type-based restrictions on the use of expressions of functional type, such that we can completely eliminate higher-order functions in all cases, without introducing any branching. We prove the correctness of the transformation and discuss its implementation in Futhark, a data-parallel functional language that generates GPU code. The use of these restricted higher-order functions has no impact on run-time performance, and we argue that we gain many of the benefits of general higher-order functions, without in most practical cases being hindered by the restrictions.
Originalsprog | Engelsk |
---|---|
Titel | Trends in Functional Programming : 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers |
Redaktører | Michał Pałka, Magnus Myreen |
Antal sider | 21 |
Forlag | Springer |
Publikationsdato | 2019 |
Sider | 136-156 |
ISBN (Trykt) | 9783030185053 |
DOI | |
Status | Udgivet - 2019 |
Begivenhed | 19th International Symposium on Trends in Functional Programming, TFP 2018 - Gothenburg, Sverige Varighed: 11 jun. 2018 → 13 jun. 2018 |
Konference
Konference | 19th International Symposium on Trends in Functional Programming, TFP 2018 |
---|---|
Land | Sverige |
By | Gothenburg |
Periode | 11/06/2018 → 13/06/2018 |
Sponsor | Chalmers ICT Area of Advance, Erlang Solutions |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 11457 LNCS |
ISSN | 0302-9743 |
ID: 223681767