Narrow Results

We address the challenging problem of algorithm and program design for the Computational Grid by providing the application user with a set of high-level, parameterised components called skeletons. We descrile a Java-based Grid programming system in which algorithmns are composed of skeletons and the computational resources for executing individual skeletons are chosen using performance prediction. The advantage of our approach is that skeletons are reusable for different applications and that skeletons' implementation can be tuned to particular machines. The focus of this paper is on predicting performance for Grid applications constructed using skeletons.

Dijkstra's famous thesis "goto considered harmful", which paved the way for structured programming, was formally substantiated by the result of Böhm and Jacopini on the Turing universality of the three well-known basic programming constructs. We argue for a similar ideal in parallel programming — "send-receive considered harmful" — i.e. abandoning explicit send-receive statements between processors and expressing programs using a restricted set of parallel constructs. We deal with recursive patterns of parallelism, represented formally as morphisms in a suitable calculus.

The aim of this paper is to study the expressive power of two morphisms – catamorphisms and anamorphisms. For a restricted program calculus based on these morphisms, we constructively prove two formal results, whose pragmatic message is: (1) A programming language based on catamorphisms is computationally equivalent to the class of primitive recursive functions; (2) A programming language based on both catamorphisms and anamorphisms is equivalent to the class of partial recursive functions and is therefore Turing-universal. We present a case study on numerical integration, demonstrating the expressive power of ana- and catamorphisms for parallel programming.