High-performance defunctionalisation in futhark

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

Standard

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

Harvard

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

APA

Hovgaard, A. K., 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 (pp. 136-156). Springer. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 11457 LNCS https://doi.org/10.1007/978-3-030-18506-0_7

Vancouver

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

Author

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

Bibtex

@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",
address = "Switzerland",
note = "19th International Symposium on Trends in Functional Programming, TFP 2018 ; Conference date: 11-06-2018 Through 13-06-2018",

}

RIS

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 -

ID: 223681767