back to
Parallel Programming Languages
The idea of skeletons apply to both imperative languages, and functional languages. The basic idea is simple: in designing algorithms, certain basic patterns occur over and over again.
A skeleton can be thought of as describing a class of algorithms. Alternately, it can be thought of as a template for parallel algorithms. In parallel applications, there are several easily identifiable constructs that can be used as algorithmic skeletons such as:
Divide and Conquer
Pipeline
Farm -- given a stream a1, a2 ... we compute f(a1), f(a2) ... in parallel.
Map and Reduce -- map is essentially similar to farm. Reduce however is defined as: given a steam a1, a2 ..., and an opertaion +, the result of reduce will be: a1 + a2 + a3 ....
There are several others but these are provided to give a general idea. For functional languages, these skeletons can be defined as higher order functions, allowing skeletons to be defined is purely functional terms. There are many languages (both imperative and functional) that support this skeletal approach, some of them use skeletons as the only means of employing parallelism in a program.
The two major languages to pioneer this skeletal approach is Imperial College's Structured Coordinating Language (SCL), and the Pisa Parallel Programming Language (P3L) of Pelagatti and Danelutto. SCL is a functional language, while P3L is an imperative language that uses functional forms for the expression of skeletons.
Reference:
Murray Cole, Algorithmic Skeletons, Research Directions in Parallel Functional Programming, Springer-Verlag 1999.
Susanna Pelagatti, Structured Development of Parallel Programns, Taylor and Francis, 1998.