Optimising purely functional GPU programs

Trevor L. McDonell; Manuel M.T. Chakravarty; Gabriele Keller; Ben Lippmeier

doi:10.1145/2500365.2500595

Optimising purely functional GPU programs

Trevor L. McDonell, Manuel M.T. Chakravarty, Gabriele Keller, Ben Lippmeier

University of New South Wales

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Purely functional, embedded array programs are a good match for SIMD hardware, such as GPUs. However, the naive compilation of such programs quickly leads to both code explosion and an excessive use of intermediate data structures. The resulting slowdown is not acceptable on target hardware that is usually chosen to achieve high performance. In this paper, we discuss two optimisation techniques, sharing recovery and array fusion, that tackle code explosion and eliminate superfluous intermediate structures. Both techniques are well known from other contexts, but they present unique challenges for an embedded language compiled for execution on a GPU. We present novel methods for implementing sharing recovery and array fusion, and demonstrate their effectiveness on a set of benchmarks.

Original language	English
Title of host publication	ICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming
Pages	49-60
Number of pages	12
DOIs	https://doi.org/10.1145/2500365.2500595
Publication status	Published - 12 Nov 2013
Externally published	Yes
Event	2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013 - Boston, MA, United States Duration: 25 Sept 2013 → 27 Sept 2013

Conference

Conference	2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013
Country/Territory	United States
City	Boston, MA
Period	25/09/13 → 27/09/13

Keywords

Array fusion
Arrays
Data parallelism
Dynamic compilation
Embedded language
GPGPU
Haskell
Sharing recovery

Access to Document

10.1145/2500365.2500595

Cite this

@inproceedings{9f963e54f2554ecabb3031d7f2c99754,

title = "Optimising purely functional GPU programs",

abstract = "Purely functional, embedded array programs are a good match for SIMD hardware, such as GPUs. However, the naive compilation of such programs quickly leads to both code explosion and an excessive use of intermediate data structures. The resulting slowdown is not acceptable on target hardware that is usually chosen to achieve high performance. In this paper, we discuss two optimisation techniques, sharing recovery and array fusion, that tackle code explosion and eliminate superfluous intermediate structures. Both techniques are well known from other contexts, but they present unique challenges for an embedded language compiled for execution on a GPU. We present novel methods for implementing sharing recovery and array fusion, and demonstrate their effectiveness on a set of benchmarks.",

keywords = "Array fusion, Arrays, Data parallelism, Dynamic compilation, Embedded language, GPGPU, Haskell, Sharing recovery",

author = "McDonell, {Trevor L.} and Chakravarty, {Manuel M.T.} and Gabriele Keller and Ben Lippmeier",

year = "2013",

month = nov,

day = "12",

doi = "10.1145/2500365.2500595",

language = "English",

isbn = "9781450323260",

pages = "49--60",

booktitle = "ICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming",

note = "2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013 ; Conference date: 25-09-2013 Through 27-09-2013",

}

McDonell, TL, Chakravarty, MMT, Keller, G & Lippmeier, B 2013, Optimising purely functional GPU programs. in ICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming. pp. 49-60, 2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013, Boston, MA, United States, 25/09/13. https://doi.org/10.1145/2500365.2500595

TY - GEN

T1 - Optimising purely functional GPU programs

AU - McDonell, Trevor L.

AU - Chakravarty, Manuel M.T.

AU - Keller, Gabriele

AU - Lippmeier, Ben

PY - 2013/11/12

Y1 - 2013/11/12

N2 - Purely functional, embedded array programs are a good match for SIMD hardware, such as GPUs. However, the naive compilation of such programs quickly leads to both code explosion and an excessive use of intermediate data structures. The resulting slowdown is not acceptable on target hardware that is usually chosen to achieve high performance. In this paper, we discuss two optimisation techniques, sharing recovery and array fusion, that tackle code explosion and eliminate superfluous intermediate structures. Both techniques are well known from other contexts, but they present unique challenges for an embedded language compiled for execution on a GPU. We present novel methods for implementing sharing recovery and array fusion, and demonstrate their effectiveness on a set of benchmarks.

AB - Purely functional, embedded array programs are a good match for SIMD hardware, such as GPUs. However, the naive compilation of such programs quickly leads to both code explosion and an excessive use of intermediate data structures. The resulting slowdown is not acceptable on target hardware that is usually chosen to achieve high performance. In this paper, we discuss two optimisation techniques, sharing recovery and array fusion, that tackle code explosion and eliminate superfluous intermediate structures. Both techniques are well known from other contexts, but they present unique challenges for an embedded language compiled for execution on a GPU. We present novel methods for implementing sharing recovery and array fusion, and demonstrate their effectiveness on a set of benchmarks.

KW - Array fusion

KW - Arrays

KW - Data parallelism

KW - Dynamic compilation

KW - Embedded language

KW - GPGPU

KW - Haskell

KW - Sharing recovery

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

U2 - 10.1145/2500365.2500595

DO - 10.1145/2500365.2500595

M3 - Conference contribution

AN - SCOPUS:84887171337

SN - 9781450323260

SP - 49

EP - 60

BT - ICFP 2013 - Proceedings of the 2013 ACM SIGPLAN International Conference on Functional Programming

T2 - 2013 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013

Y2 - 25 September 2013 through 27 September 2013

ER -

Optimising purely functional GPU programs

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this