High-performance defunctionalisation in futhark

Anders Kiel Hovgaard; Troels Henriksen; Martin Elsman

doi:10.1007/978-3-030-18506-0_7

High-performance defunctionalisation in futhark

Anders Kiel Hovgaard, Troels Henriksen, Martin Elsman^*

^*Corresponding author for this work

Abstract

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	https://doi.org/10.1007/978-3-030-18506-0_7
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
Country/Territory	Sweden
City	Gothenburg
Period	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

Keywords

Compilers
Defunctionalisation
GPGPU

Access to Document

10.1007/978-3-030-18506-0_7

Cite this

High-performance defunctionalisation in futhark. / Hovgaard, Anders Kiel; Henriksen, Troels ; Elsman, Martin.
Trends in Functional Programming: 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers. ed. / Michał Pałka; Magnus Myreen. Springer, 2019. p. 136-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11457 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Hovgaard, AK, Henriksen, T & Elsman, M 2019, High-performance defunctionalisation in futhark. in M Pałka & M Myreen (eds), Trends in Functional Programming: 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers. Springer, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11457 LNCS, pp. 136-156, 19th International Symposium on Trends in Functional Programming, TFP 2018, Gothenburg, Sweden, 11/06/2018. https://doi.org/10.1007/978-3-030-18506-0_7

Hovgaard AK, Henriksen T , Elsman M. High-performance defunctionalisation in futhark. In Pałka M, Myreen M, editors, Trends in Functional Programming: 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers. Springer. 2019. p. 136-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11457 LNCS). doi: 10.1007/978-3-030-18506-0_7

Hovgaard, Anders Kiel ; Henriksen, Troels ; Elsman, Martin. / High-performance defunctionalisation in futhark. Trends in Functional Programming: 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers. editor / Michał Pałka ; Magnus Myreen. Springer, 2019. pp. 136-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 11457 LNCS).

@inproceedings{586d4ebfc7a84a9daf12c7096c2cbfb4,

title = "High-performance defunctionalisation in futhark",

abstract = "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.",

keywords = "Compilers, Defunctionalisation, GPGPU",

author = "Hovgaard, {Anders Kiel} and Troels Henriksen and Martin Elsman",

year = "2019",

doi = "10.1007/978-3-030-18506-0_7",

language = "English",

isbn = "9783030185053",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "136--156",

editor = "Micha{\l} Pa{\l}ka and Magnus Myreen",

booktitle = "Trends in Functional Programming",

note = "19th International Symposium on Trends in Functional Programming, TFP 2018 ; Conference date: 11-06-2018 Through 13-06-2018",

}

TY - GEN

T1 - High-performance defunctionalisation in futhark

AU - Hovgaard, Anders Kiel

AU - Henriksen, Troels

AU - Elsman, Martin

PY - 2019

Y1 - 2019

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

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

KW - Compilers

KW - Defunctionalisation

KW - GPGPU

UR - http://www.scopus.com/inward/record.url?scp=85065470408&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-18506-0_7

DO - 10.1007/978-3-030-18506-0_7

M3 - Article in proceedings

AN - SCOPUS:85065470408

SN - 9783030185053

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 136

EP - 156

BT - Trends in Functional Programming

A2 - Pałka, Michał

A2 - Myreen, Magnus

PB - Springer

T2 - 19th International Symposium on Trends in Functional Programming, TFP 2018

Y2 - 11 June 2018 through 13 June 2018

ER -

High-performance defunctionalisation in futhark

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this