Design and Implementation of the Parallel Programming Language Petalisp

The goal of this work is to demonstrate that even simple building blocks can be sufficient to solve complex programming problems, that abstraction and efficiency need not be mutually exclusive, and that it is better to consider parallelism from the outset rather than attempting to add it in as an afterthought. To achieve this goal, we have developed the parallel programming language Petalisp. Petalisp has only three elementary operations: applying a function element-wise to one or more arrays, reshaping an array according to certain rules, and combining multiple arrays into one. These simple building blocks are sufficient to describe numerous practical problems such as matrix multiplications, statistical methods, multigrid methods, and sorting algorithms. A special feature of Petalisp is that each of the three elementary operations is inherently parallel. This makes the description of parallel algorithms refreshingly simple, and conversely, the description of serial procedures more difficult. The first part of this work describes Petalisp from the user's perspective and shows how it can be used to write elegant, flexible, and highly efficient programs. A central aspect there is Petalisp's generalized array data structure, which not only allows an arbitrary number of axes, but also arbitrary start indices and step sizes per axis. The elements of such an array are not evaluated immediately, but only on the explicit request of the user. Petalisp offers several interfaces for this, depending on whether one wants to evaluate arrays in a blocking or non-blocking fashion, or repeatedly with different starting values. The elements of an array can either be specified explicitly or are the result of one of the three elementary operations of Petalisp. In addition, Petalisp provides several helper functions for stacking, sorting, reducing, and differentiating arrays. A series of examples shows how this functionality can be applied in practice. The second part of this work describes the implementation of Petalisp, thanks to which Petalisp programs already run almost as fast as established approaches from high-performance computing. The core of this implementation is a specially developed intermediate representation of loop nests and memory blocks. This work describes algorithms for the creation, optimization, and partitioning of this intermediate representation, as well as the subsequent translation to Lisp and C++. Clever caching of intermediate steps allows the translation to be done in only a few microseconds, so that Petalisp can be used interactively.