High-performance defunctionalisation in futhark

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 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
PublisherSpringer
Publication date2019
Pages136-156
ISBN (Print)9783030185053
DOIs
Publication statusPublished - 2019
Event19th International Symposium on Trends in Functional Programming, TFP 2018 - Gothenburg, Sweden
Duration: 11 Jun 201813 Jun 2018

Conference

Conference19th International Symposium on Trends in Functional Programming, TFP 2018
LandSweden
ByGothenburg
Periode11/06/201813/06/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
ISSN0302-9743

    Research areas

  • Compilers, Defunctionalisation, GPGPU

ID: 223681767