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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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

Original languageEnglish
Title of host publicationProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
Number of pages16
PublisherAssociation for Computing Machinery
Publication date2017
Pages556-571
ISBN (Electronic)978-1-4503-4988-8
DOIs
Publication statusPublished - 2017
Event38th ACM SIGPLAN Conference on Programming Language Design and Implementation - Barcelona, Spain
Duration: 18 Jun 201723 Jun 2017
Conference number: 38

Conference

Conference38th ACM SIGPLAN Conference on Programming Language Design and Implementation
Nummer38
LandSpain
ByBarcelona
Periode18/06/201723/06/2017

    Research areas

  • Compilers, Functional language, GPGPU, Parallel

ID: 184140914