Skeleton
From Parawiki
Contents |
Definition
Here is the first definition of a skeleton introduced by Murray Cole in his PhD thesis, you can find this definition at Murray Cole's skeleton page.:
- A skeleton is a useful pattern of parallel computation and interaction which can be packaged up as `framework/second order/template' constructs (i.e. parameterized by other pieces of code), perhaps presented without reference to explicit parallelism, perhaps not. Implementations and analyses can be shared between instances.
Here is another definitions of skeleton:
- Skeletons are reusable, parameterized components with well defined semantics and pre-packaged efficient parallel implementation. (*)
(*)Ref. H. Bischof, S. Gorlatch, E. Kitzelmann. Cost Optimality and Predictability of Parallel Programming with Skeletons. (Euro-Par 2003, LNCS 2790, pp. 682-693) distinguished paper
† The basic idea of having skeletons, design patterns and frameworks is the idea of reuse. It is more suitable for a programmer designing a complex system to use a solution of a similar system already realized instead of designing from the scratch. Design patterns facilitate the reuse, the programmer chooses the appropriate design pattern from the pattern library. Skeletons and design patterns are very similar but different in the end, a skeleton is in the design of high-performance systems, a design patterns require some other handling mechanisms such as fault tolerance, timelines and quality of service. (2)
Skeletal Programming
For detailed overview refer to Rabhi and Gorlatch's book about skeletons (2).
- Skeletal programming is parallel programming with skeletons.
- Most of the work on skeletal programming is associated with functional languages, as skeletons can be modelled as higher order function (HOF)s (=functionals). The difference is that in skeletal programming, the programmer can benefit from the fully parallel properties of the skeletons but in HOF-oriented programming the programmer can just use the parallelism supported by the HOF.
With this property comes another definition of skeletons: For the functional programmer, a skeleton is nothing more than a polymorphic higher order function (HOF) which can be applied with many different types and parameters.
- An example to imperative skeletons is Skeleton Imperative Language (Skil) based on the imperative programming language C.
- An important idea of skeletal programming is to match the parallel topology to the algorithm, rather than the algorithm to the the topology.
- A skeleton can be implemented in several different ways, the implementations depend on the process topology, target architecture, load balancing, granularity etc.
Skeleton Types
For detailed overview refer to (4).
Depending on the kind of parallelism used, skeletons can be classified into 2 categories:
Skeleton Nesting
Nesting of skeletons is an attractive research area. With support for nesting, it is possible to construct complex parallel applications by composing and transforming skeletons using given transformation rules and compositional cost models for performance prediction.
