Data-Parallel Programming without Arrays

Conal Elliott

Draft of October 10, 2018 (comments please!)


Despite its overwhelming popularity, the array type has serious drawbacks for parallel programming. In brief, array algorithms are unsafe (subject to out-of-bounds errors), weakly compositional, and brittle to change. A generic functor approach solves these problems, resulting in a programming style that is safe and strongly compositional (for code reuse), while robustly describing infinite families of guaranteed-correct algorithmic variations. For CPU-based and (especially) hardware implementations, the generic functor style of programming can perform fairly well. GPUs and their supporting programming models, however, have a very strong bias toward array programming. In particular, they efficiently support only “flat” data parallelism, corresponding to computing over arrays of scalar values. This note describes a design for a programming interface isomorphic to the generic functor composition style and an implementation that maps to efficient GPU-style array computations. The generated computations are guaranteed safe from out-of-bound errors despite using unsafe array operations internally, and the programming model remains elegantly compositional and generic-friendly.