As defined by Cole [Cole, 1988], algorithmic skeletons take the approach that implementing good dynamic behaviour on a machine is hard. A skeleton is intended to be an efficient implementation of a commonly encountered parallel behaviour on some specific machine. In effect a skeleton is a higher-order function that combines (sequential) sub-programs to construct the parallel application. The most commonly encountered skeletons are pipelines and variants of the common list-processing functions map, scan and fold. A general treatment has been provided by Rabhi, who has related algorithmic skeletons to a number of parallel paradigms [Rabhi, 1993].
Since a skeleton is simply a parallel higher-order function, it is straightforward to write skeletons using strategies. Both the parMap function in Section * and the pipeline function in Section * are actually skeletons. A more elaborate divide-and-conquer skeleton, based on a Concurrent Clean function [Nöcker et al., 1991] can be written as follows. All of these strategic skeletons are much higher-level than the skeletons used in practice which have a careful implementation giving good data distribution, communication and synchronisation.
divConq :: (a -> b) -> a -> (a -> Bool) ->
(b -> b -> b) -> (a -> Bool) -> (a -> (a,a)) -> b
divConq f arg threshold conquer divisible divide
| not (divisible arg) = f arg
| otherwise = conquer left right `demanding` strategy
where
(lt,rt) = divide arg
left = divConq f lt threshold conquer divisible divide
right = divConq f rt threshold conquer divisible divide
strategy = if threshold arg
then (seqPair rwhnf rwhnf) $ (left,right)
else (parPair rwhnf rwhnf) $ (left,right)
Many strategic functions take the opposite approach to skeletons: a skeleton parameterises the control function over the algorithm, i.e., it takes sequential sub-programs as arguments. However, a strategic function may instead specify the algorithm and parameterise the control information, i.e. take a strategy as a parameter. Several of the functions we have already described take a strategy as a parameter, including parBuffer.
The algorithmic skeleton approach clearly fits functional languages very well, and indeed much work has been done in a functional context. However, it is also possible to combine skeletons with imperative approaches.
For example, the Skil compiler integrates algorithmic skeletons into a subset of C (C-). Rather than using closures to represent work, as we have done for our purely functional setting, the Skil compiler [Botorog and Kuchen, 1996] translates polymorphic higher-order functions into monomorphic first-order functions. The performance of the resulting program is close to that of a hand-crafted C- application. While the Skil instantiation procedure is not fully general, it may be possible to adopt similar techniques when compiling evaluation strategies, in order to reduce overheads.