Parallel Processing Letters

We describe a skeletal parallel programming library which integrates task and data parallel constructs within an API for C++. Traditional skeletal requirements for higher orderness and polymorphism are achieved through exploitation of operator overloading and templates, while the underlying parallelism is provided by MPI. We present a case study describing two algorithms for the travelling salesman problem.

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.

Janus is a conceptual framework and C++ template library that provides a flexible and extensible collection of efficient data structures and algorithms for a broad class of data-parallel applications. In particular, finite difference methods, (adaptive) finite element methods, and data-parallel graph algorithms are supported. An outstanding advantage of providing a generic C++ framework is that it provides application-oriented abstractions that achieve high performance without relying on language extension or non-standard compiler technology. The C++ template mechanism allows to plug user-defined types into the Janus data structures and algorithms. Moreover, Janus components can easily be combined with standard software packages of this field.

Metaprogramming is a paradigm for enhancing a general-purpose programming language with features catering for a special-purpose application domain, without a need for a reimplementation of the language. In a staged compilation, the special-purpose features are translated and optimised by a domain-specific preprocessor, which hands over to the general-purpose compiler for translation of the domain-independent part of the program. The domain we work in is high-performance parallel computing. We use metaprogramming to enhance the functional language Haskell with features for the efficient, parallel implementation of certain computational patterns, called skeletons.

The functional parallel language Eden — suitable for the description of parallel and concurrent algorithms in a distributed setting — is an extension of Haskell with a set of coordination features. In this paper we present a formal operational semantics for the kernel of Eden, or more precisely, for a λ-calculus widened with explicit parallelism and potentially infinite communication channels. Eden overrides the lazy nature of Haskell on behalf of parallelism. This interplay between laziness and eagerness is accurately described by the semantics proposed here, which is based on Launchbury's natural semantics for lazy evaluation, and is expressed through a two-level transition system: a lower level for the local and independent evaluation of each process, and an upper one for the coordination between all the parallel processes in the system. As processes are created either under demand or in a speculative way, different scheduling strategies are possible — ranging from a minimal one that only allows the main thread to evolve, to a maximal one that evolves in parallel every active binding.

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.

We discuss a language-based cost model for array programs built on the notions of work complexity and parallel depth. The programs operate over data structures comprising nested arrays and recursive product-sum types. In a purely functional setting, such programs can be implemented by way of the flattening transformation that converts codes over nested arrays into vectorised code over flat arrays. Flat arrays lend themselves to a particularly efficient implementation on standard hardware, but the overall efficiency of the approach depends on the flattening transformation preserving the asymptotic complexity of the nested array codes. Blelloch has characterised a class of first-order array programs, called contained programs, for which flattening preserves the asymptotic depth complexity. However, his result is restricted to programs processing only arrays and tuples. In the present paper, we extend Blelloch's result to array programs processing data structures containing arrays as well as arbitrary recursive product-sum types. Moreover, we replace the notion of containment by the more general concept of fold programs.

This paper describes the transformation of (almost arbitrary) sequential functions on covers to parallel, collective operations (skeletons). This allows the direct re-use of existing, but sequential, code on parallel machines without the necessity to hand-code the desired parallel operations. A necessary pre-requisite for this skeleton lifting is the availability of a cover which holds the mapping information of the local subobjects, including their topology information. The lifting transformation distinguishes sequential values, which are available on each processor, from parallel values, which are only stored once. Accesses to parallel values are either ignored locally if they will be computed on another processor, or they induce communication messages to transfer the necessary data, depending on the behavior of the original function.