Futhark: purely functional GPU-programming with nested parallelism and in-place array updates

TY - GEN

T1 - Futhark

T2 - 38th ACM SIGPLAN Conference on Programming Language Design and Implementation

AU - Henriksen, Troels

AU - Serup, Niels G. W.

AU - Elsman, Martin

AU - Henglein, Fritz

AU - Oancea, Cosmin Eugen

N1 - Conference code: 38

PY - 2017

Y1 - 2017

N2 - Futhark is a purely functional data-parallel array language that offers a machine-neutral programming model and an optimising compiler that generates OpenCL code for GPUs. This paper presents the design and implementation of three key features of Futhark that seek a suitable middle ground with imperative approaches. First, in order to express efficient code inside the parallel constructs, we introduce a simple type system for in-place updates that ensures referential transparency and supports equational reasoning. Second, we furnish Futhark with parallel operators capable of expressing efficient strength-reduced code, along with their fusion rules. Third, we present a flattening transformation aimed at enhancing the degree of parallelism that (i) builds on loop interchange and distribution but uses higher-order reasoning rather than array-dependence analysis, and (ii) still allows further locality-of-reference optimisations. Finally, an evaluation on 16 benchmarks demonstrates the impact of the language and compiler features and shows application-level performance competitive with hand-written GPU code. Copyright is held by the owner/author(s).

AB - Futhark is a purely functional data-parallel array language that offers a machine-neutral programming model and an optimising compiler that generates OpenCL code for GPUs. This paper presents the design and implementation of three key features of Futhark that seek a suitable middle ground with imperative approaches. First, in order to express efficient code inside the parallel constructs, we introduce a simple type system for in-place updates that ensures referential transparency and supports equational reasoning. Second, we furnish Futhark with parallel operators capable of expressing efficient strength-reduced code, along with their fusion rules. Third, we present a flattening transformation aimed at enhancing the degree of parallelism that (i) builds on loop interchange and distribution but uses higher-order reasoning rather than array-dependence analysis, and (ii) still allows further locality-of-reference optimisations. Finally, an evaluation on 16 benchmarks demonstrates the impact of the language and compiler features and shows application-level performance competitive with hand-written GPU code. Copyright is held by the owner/author(s).

KW - Compilers

KW - Functional language

KW - GPGPU

KW - Parallel

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

U2 - 10.1145/3062341.3062354

DO - 10.1145/3062341.3062354

M3 - Article in proceedings

AN - SCOPUS:85025117216

SP - 556

EP - 571

BT - Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation

PB - Association for Computing Machinery

Y2 - 18 June 2017 through 23 June 2017

ER -