Higher-order functions for a high-performance programming language for GPUs

MSc Defence by Anders Kiel Hovgaard


General-purpose massively parallel processors, such as modern GPUs, have become common, but the difficulty of programming these machines is well known. Pure functional programming provides some reassurance that the situation can be improved, by guaranteeing referential transparency and providing useful combinators for expressing data-parallel computations. Unfortunately, one of the main features of functional programming, namely higher-order functions, cannot be efficiently implemented on GPUs by the usual means.

In this thesis, we present a defunctionalization transformation that relies on type-based restrictions on the use of functions to be able to 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 runtime performance and we argue that we gain many of the benefits of general higher-order functions without being hindered by the restrictions in most cases in practice.

Supervisors: Martin Elsman and Troels Henriksen
External examiner: Professor Peter Sestoft, ITU