A Cost Analysis for a Higher-Order Parallel Programming Model

Abstract

Programming parallel computers remains a difficult task. An ideal programming environment should enablethe user to concentrate on the problem solving activity at a convenient level of abstraction, while managing the intricate low-level details without sacrificing performance. This thesis investigates a model of parallel programming based on the Bird-Meertens Formalism (BMF). This is a set of higher-order functions, many of which are implicitly parallel. Programs are expressed in terms of functions borrowed from BMF. A parallel implementation is defined for each of these functions for a particular topology, and the associated execution costs are derived. The topologies which have been considered include the hypercube, 2-D torus, tree and the linear array. An analyser estimates the costs associated with different implementations of a given program and selects a cost-effective one for a given topology. All the analysis is performed at compile-time which has the advantage of reducing run-time overheads. the cost model's accuracy in choosing a cost-effective implementation and predicting its performance has been studied for three programs. The main contribution of the thesis is the cost model which aims to predict realistic performances and which considers several possible parallel implementations for a given programbefore selecting a cost-effective one.