High-performance defunctionalisation in futhark
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Trends in Functional Programming : 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers |
Editors | Michał Pałka, Magnus Myreen |
Number of pages | 21 |
Publisher | Springer |
Publication date | 2019 |
Pages | 136-156 |
ISBN (Print) | 9783030185053 |
DOIs | |
Publication status | Published - 2019 |
Event | 19th International Symposium on Trends in Functional Programming, TFP 2018 - Gothenburg, Sweden Duration: 11 Jun 2018 → 13 Jun 2018 |
Conference
Conference | 19th International Symposium on Trends in Functional Programming, TFP 2018 |
---|---|
Land | Sweden |
By | Gothenburg |
Periode | 11/06/2018 → 13/06/2018 |
Sponsor | Chalmers ICT Area of Advance, Erlang Solutions |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11457 LNCS |
ISSN | 0302-9743 |
- Compilers, Defunctionalisation, GPGPU
Research areas
ID: 223681767