Accelerating Sum Types

Abstract

Parallel array languages are programming languages that make it possible to write highly parallel programs without knowing the intricacies of parallel programming and hardware. In this thesis, we present an optimization for the memory usage of parallel array languages, specifically geared towards sum types. Sum types are algebraic data types with more than one constructor, which are used to denote a choice between multiple different variants. Examples of applications of sum types in parallel programs are material choices in a ray tracer and parameters to a fluid simulation. We introduce a new representation of sum types that aligns with the struct-of-arrays memory layout that parallel array languages commonly use. We show that this representation is close to optimal with respect to memory usage, and that it is an improvement over existing representations that are suited for a struct-of-arrays memory layout. This representation is implemented in the POSable library, which generically converts non-recursive Haskell 98 data types to this representation. Accelerate is a functional parallel array language embedded in Haskell that supports sum types. The POSable library has been integrated in Accelerate, which shows the viability of the approach.