High-performance defunctionalisation in futhark

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Anders Kiel Hovgaard, Troels Henriksen, Martin Elsman

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 languageEnglish
Title of host publicationTrends in Functional Programming : 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers
EditorsMichał Pałka, Magnus Myreen
Number of pages21
Publication date2019
ISBN (Print)9783030185053
Publication statusPublished - 2019
Event19th International Symposium on Trends in Functional Programming, TFP 2018 - Gothenburg, Sweden
Duration: 11 Jun 201813 Jun 2018


Conference19th International Symposium on Trends in Functional Programming, TFP 2018
SponsorChalmers ICT Area of Advance, Erlang Solutions
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11457 LNCS

    Research areas

  • Compilers, Defunctionalisation, GPGPU

ID: 223681767