On the Massively Parallel Execution of Declarative Programs

Manuel M. T. Chakravarty

Accepted as a doctoral dissertation by the
Technische Universität Berlin, Fachbereich Informatik

Functions and relations can be combined into a declarative notation for describing parallel programs, where step-at-a-time computations being expressed purely functionally, whereas parallel behaviour is specified relationally. A recent proposal demonstrated that such an integration can use a type system to guarantee the semantic integrity of purely functional subcomputations -- and it can therefore be regarded as a conservative extension of purely functional programming.

The research documented in this dissertation generalizes results from purely functional programming to this extended setting. In particular, this work extends the typed lambda calculus by co-ordinating relations, but in such a way that it preserves the conventional semantics for purely functional subcomputations. Furthermore, it describes an extension of an abstract machine for compiled graph-reduction, which provides explicit support for optimizations and code generation, targeted at distributed-memory parallel computers.

The extension of the lambda calculus, called D, includes a basic notion of agents, which are represented by relations and may form parallel ensembles. Such agents communicate via equational constraints on unbound variables; and they can exhibit indeterminate behaviour, which is important for some parallel algorithms. Agents are first-class values in the sense that they support full higher-order programming. Computational tasks are realized within these agents as purely functional subcomputations. D is a declarative framework for parallel programming, which has a logic semantics based on an encoding into linear logic as well as a parallel operational semantics derived from the logic semantics.

This work also introduces an extension of the the Spineless Tagless G-machine, one of the most efficient implementations of compiled graph-reduction, that covers all features of D -- which can be seen as a refinement of the operational semantics of D. More importantly, the abstract machine is revised to integrate multi-threading as a mechanism for tolerating communication latencies. Such latencies are inherent in distributed-memory parallel computers and represent one of the major obstacles to an efficient implementation of declarative languages on these computers. The operational semantics of the abstract machine is specified formally and its mapping to concrete parallel hardware is discussed. The effectiveness of the multi-threading extension is demonstrated by results obtained using an emulator, which implements the parallel operational semantics of the abstract machine.

PostScript (351 kB)

This page is part of Manuel Chakravarty's WWW-stuff.