Narrow Results

Beowulf class clusters are gaining more and more interest as low cost parallel architectures. They deliver reasonable performance at a very reasonable cost, compared to classical MPP machines. Parallel applications are usually developed on clusters using MPI/PVM message passing or HPF programming environments. Here we discuss new implementation strategies to support structured parallel programming environments for clusters based on skeletons. The adoption of structured parallel programming models greatly reduces the time spent in developing new parallel applications on clusters. The adoption of our implementation techniques based on macro data flow allows very efficient parallel applications to be developed on clusters. We discuss experiments that demonstrate the full feasibility of the approach.

This paper discusses the use of a tagged-token macro data-flow execution model for implementing skeletons within the SKIPPER parallel programming environment. We show that it provides a suitable implementation model for skeletons involving runtime-bounded iterations and/or recursion such as data and task farms, especially in the presence of nesting. The new version of SKIPPER relies on a custom data-flow interpreter controlling SPMD based parallelism. Input data-flow graphs are obtained from a skeletal program specification written in CAML and making use of user defined sequential functions written in C. Initial evaluation suggests that performance close to handcrafted C with MPI can be achieved and that the support for nesting does not entail a significant performance penalty.

The Skeletal approach to parallel programming conjugates a high-level compositional style and efficiency. A second advantage of Skeletal programming is portability since implementation decisions are usually taken at compile time. The paper claims that an intermediate model embedding the main performance features of the target architecture facilitates performance portability across parallel architectures. This is motivated by describing the Skel-BSP framework which implements a skeleton system on top of a BSP computer. A prototype compiler based on a set of BSP templates is presented together with a set of performance models for each skeleton which allow a local optimization. The paper also introduces a global optimization strategy using a set of transformation rules. This local+global approach seems a viable solution to writing parallel software in machine-independent way (Writing Once and Compiling Everywhere).

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.

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.

We introduce a very simple, yet powerful, distribution calculus aimed at describing different strategies that can be used to distribute (ie, partition and replicate) multidimensional dense arrays over a set of processors, like what is done in the implementation of the P3L Map skeleton. We give a formal semantics, that allows to prove equations between distributions, and we show how to associate a cost to such distributions, allowing to choose between semantically equivalent distribution strategies.

We discuss the lack of expressivity in some skeleton-based parallel programming frameworks. The problem is further exacerbated when approaching irregular problems and dealing with dynamic data structures. Shared memory programming has been argued to have substantial ease of programming advantages for this class of problems. We present the library which represents an attempt to merge the two programming models by introducing skeletons in a shared memory framework.

Skeletons are reusable, parameterized program components with well-defined semantics and pre-packaged efficient parallel implementation. This paper develops a new, provably cost-optimal implementation of the DS (double-scan) skeleton for programming divide-and-conquer algorithms. Our implementation is based on a novel data structure called plist (pointed list); implementation's performance is estimated using an analytical model. We demonstrate the use of the DS skeleton for parallelizing a tridiagonal system solver and report experimental results for its MPI implementation on a Cray T3E and a Linux cluster: they confirm the performance improvement achieved by the cost-optimal implementation and demonstrate its good predictability by our performance model.

In mobile languages programmers control the placement of code or computations in open networks, e.g., a program can migrate between locations. Mobile computations are typically stateful and interact with the state at each location in the network. We propose mobility skeletons, a library of parameterisable functions that encapsulate common patterns of mobile computation. Mobility skeletons are analogous to, but very different from, algorithmic skeletons — parameterisable functions encapsulating common patterns of parallel computation. We have identified three common patterns of mobile computation, and implemented them as a library of higher-order functions in mobile Haskell. Each mobility skeleton is defined and illustrated with an example. We show how mobility skeletons can be composed and nested, and illustrate their use in a non-trivial case study: a distributed meeting planner. Mobility skeletons are extensible: there is a small set of mobility primitives, and medium-level abstractions such as remote evaluation can be defined using them. New mobility skeletons can be defined using the medium and low level abstractions.

This paper demonstrates how parallel programs with message-passing can be generated from abstract specifications embedded in the functional language MetaOCaml. The functional style permits to design parallel programs with a high degree of parameterization, so-called skeletons. Programmers who are unexperienced in parallelism can take such skeletons for a simple and safe generation of parallel applications. Since MetaOCaml also has efficient imperative features and an MPI interface, the entire program can be written in one language, without the need to use a language interface restricting the set of data objects which could be exchanged.

The semantics of abstract specifications is expressed by an interpreter written in MetaOCaml. A cost model is defined by abstract interpretation of the specification. Partial evaluation of the interpreter with a specification, a feature which MetaOCaml provides, yields a parallel program. The partial evaluation process takes time on each MPI process directly before the execution of the application program, exploiting knowledge of the number of processes, the current process identifier and the communication structure. Our example is the specification of a divide-and-conquer skeleton which is used to compute the multiplication of multi-digit numbers using Karatsuba's algorithm.

The implementation of stencil computations on modern, massively parallel systems with GPUs and other accelerators currently relies on manually-tuned coding using low-level approaches like OpenCL and CUDA. This makes development of stencil applications a complex, time-consuming, and error-prone task. We describe how stencil computations can be programmed in our SkelCL approach that combines high-level programming abstractions with competitive performance on multi-GPU systems. SkelCL extends the OpenCL standard by three high-level features: 1) pre-implemented parallel patterns (a.k.a. skeletons); 2) container data types for vectors and matrices; 3) automatic data (re)distribution mechanism. We introduce two new SkelCL skeletons which specifically target stencil computations – MapOverlap and Stencil – and we describe their use for particular application examples, discuss their efficient parallel implementation, and report experimental results on systems with multiple GPUs. Our evaluation of three real-world applications shows that stencil code written with SkelCL is considerably shorter and offers competitive performance to hand-tuned OpenCL code.

In the world of Big Data analytics, there is a series of tools aiming at simplifying programming applications to be executed on clusters. Although each tool claims to provide better programming, data and execution models–for which only informal (and often confusing) semantics is generally provided–all share a common underlying model, namely, the Dataflow model. The model we propose shows how various tools share the same expressiveness at different levels of abstraction. The contribution of this work is twofold: first, we show that the proposed model is (at least) as general as existing batch and streaming frameworks (e.g., Spark, Flink, Storm), thus making it easier to understand high-level data-processing applications written in such frameworks. Second, we provide a layered model that can represent tools and applications following the Dataflow paradigm and we show how the analyzed tools fit in each level.

A methodology for the identification of homomorphisms in high level functional language specifications is presented and their role illustrated with a series of examples. These include the synthesis of a fractal-based algorithm for image decompression and a logarithmic parallel simulation of a single server, first-come-first-served queue.

We derive a provably correct, architecture-independent family of parallel implementations for a class of data-parallel algorithms, called DH (distributable homomorphisms). The implementations are well-structured SPMD programs with group-wise personalized all-to-all exchange, directly realizable in MPI. As a case study, we systematically adjust the mathematical specification of the Fast Fourier Transform (FFT) to the DH format and, thereby, obtain a generic SPMD implementation for FFT. The target program includes FFT solutions used in practice – the binary-exchange and the 2D- and SD-transpose – as special cases.

Most of the traditional methods for shape classification are based on contour. They often encounter difficulties when dealing with classes that have large nonlinear variability, especially when the variability is structural or due to articulation. It is well-known that shape representation based on skeletons is superior to contour based representation in such situations. However, approaches to shape similarity based on skeletons suffer from the instability of skeletons, and matching of skeleton graphs is still an open problem.

Using a new skeleton pruning method, we are able to obtain stable pruned skeletons even in the presence of significant contour distortions. We also propose a new method for matching of skeleton graphs. In contrast to most existing methods, it does not require converting of skeleton graphs to trees and it does not require any graph editing. Shape classification is done with Bayesian classifier. We present excellent classification results for complete shapes.

This paper deals with analyzing and comparing several key thinning algorithms in terms of various different methodologies. From these analyses and comparisons, a new sequential model thinning algorithm using heuristic, hybrid methods is presented. It intends to produce, based on past experience, thinned skeletons of thickness one from input patterns, keep connectivity, and eliminate unnecessary pixels. Several illustrative examples on various patterns were tested and the results compared. The parallel model thinning algorithm is still open.

In this paper, a generic approach for the analysis and design of parallel thinning algorithms is presented. The procedures for designing 4-subcycle/iteration, 2-subcycle/iteration, and 1-subcycle/iteration thinning algorithms are developed. The experimental results show that these thinning algorithms designed by proposed approach preserve image connectivity, produce thinner results, and obtain faster speed than many existing key thinning algorithms. As an example, a 1-subcycle/iteration algorithm and its experimental results were illustrated, which is in general about two times faster than others in the literature.

We propose a new approach for recognition, description and extraction of ridges and ravines based on singularity theory; the approach may be used for shape coding and animation.

A new concept of ridges, ravines and related structures (skeletons) associated with a surface in three-dimensional space is introduced. The concept is based on the investigation of relationships between the singularities of the distance function from the surface and singularities of caustic of the normals to the surface. It involves both local and global geometric surface properties and leads to the effective procedure for ridges and ravines recognition.