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 af dette arbejde

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.

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	https://doi.org/10.1007/978-3-030-18506-0_7
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/Område	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

Adgang til dokumentet

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

Andre filer og links

Link to publication in Scopus

Citationsformater

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

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. red. / Michał Pałka; Magnus Myreen. Springer, 2019. s. 136-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 11457 LNCS).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Hovgaard, AK, Henriksen, T & Elsman, M 2019, High-performance defunctionalisation in futhark. i M Pałka & M Myreen (red), 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), bind 11457 LNCS, s. 136-156, 19th International Symposium on Trends in Functional Programming, TFP 2018, Gothenburg, Sverige, 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. I Pałka M, Myreen M, red., Trends in Functional Programming: 19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers. Springer. 2019. s. 136-156. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 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. red. / Michał Pałka ; Magnus Myreen. Springer, 2019. s. 136-156 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Bind 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

Konference

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater