"The Transformational Derivation of Parallel Programs using Data Distribution Algebras and Skeletons"

Abstract

The transformational derivation of parallel programs for distributed-memory architectures using skeleton-based approaches is one of the most promising methods for parallel program development. These approaches support the derivation of provably correct, efficient and portable parallel programs using a predefined set of encapsulated efficiently implemented parallel base algorithms. Encapsulation requires that compositions of skeletons are explicitly defined by means of transformations. More flexible approaches which enable the compositional development of parallel programs - that is, without reliance on ad hoc transformations - are, however, often advantageous.

The research presented in this dissertation tackles this problem by introducing overlapping data structures, called covers, as a concept for the explicit but still high-level specification of the spatial aspects of parallel programs. Covers consist of overlapping substructures that explicitly represent the data distribution of data elements and domains of elements which can be communicated. Their semantics is defined algebraically on the basis of an abstract notion of data structures, and concrete covers can be defined using the concept of views providing multiple concrete representations of a data type. Together with a set of high-level operators, which can be used to define compositionally complex covers, they form data-distribution algebras.

Parallel algorithms are expressed using skeletons parameterized with covers. Thus, communication can be made explicit through the accesses of skeletons to the overlapping parts of covers. In this dissertation, three semantic models for the treatment of such accesses are discussed. The skeleton definitions commonly used in a functional setting can be adapted to skeletons parameterized with covers. Generalizing this purely functional skeletons, a model interpreting accesses to the overlapping parts as implicit specifications of data dependencies is defined. Their semantics can be defined by elimination transformations into purely functional skeletons. The most general model allows arbitrary accesses to the overlapping parts, provided that data consistency is ensured. A sheaf-theoretic semantics allows properties about skeletons to be derived in this case.

Another focus of the research work reported here, is the integration of views, covers and skeletons into a transformational development method for parallel programs. The use of views for program development is promoted by so-called neighbourhood relations, a notion of adequacy of views w.r.t. the constructive data-driven formulation of algorithms. Cover operators have an intuitive interpretation with regard to their effect on the parallel behaviour of skeletons defined on constructed covers. Implicit dependencies are shown to be an important tool for the derivation of parallel programs. They enable a natural representation of frequently used optimization techniques for parallel programs. Finally, the method is applied to different non-trivial examples presenting, among others, a first step towards the structural treatment of the parallelization of multigrid algorithms for the solution of partial differential equations using domain decomposition.