Iterating skeletons: structured parallelism by composition

TY - GEN

T1 - Iterating skeletons

T2 - 24th International Symposium on Implementation and Application of Functional Languages

AU - Dieterle, Mischa

AU - Horstmeyer, Thomas

AU - Berthold, Jost

AU - Loogen, Rita

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - Algorithmic skeletons are higher-order functions which provide tools for parallel programming at a higher abstraction level, hiding the technical details of parallel execution inside the skeleton implementation. However, this encapsulation becomes an obstacle when the actual algorithm is one that involves iterative application of the same skeleton to successively improve or approximate the result. Striving for a general and portable solution, we propose a skeleton iteration framework in which arbitrary skeletons can be embedded with only minor modifications. The framework is flexible and allows for various parallel iteration control and parallel iteration body variants. We have implemented it in the parallel Haskell dialect Eden using dedicated stream communication types for the iteration. Two non-trivial case studies show the practicality of our approach. The performance of our compositional iteration framework is competitive with customised iteration skeletons.

AB - Algorithmic skeletons are higher-order functions which provide tools for parallel programming at a higher abstraction level, hiding the technical details of parallel execution inside the skeleton implementation. However, this encapsulation becomes an obstacle when the actual algorithm is one that involves iterative application of the same skeleton to successively improve or approximate the result. Striving for a general and portable solution, we propose a skeleton iteration framework in which arbitrary skeletons can be embedded with only minor modifications. The framework is flexible and allows for various parallel iteration control and parallel iteration body variants. We have implemented it in the parallel Haskell dialect Eden using dedicated stream communication types for the iteration. Two non-trivial case studies show the practicality of our approach. The performance of our compositional iteration framework is competitive with customised iteration skeletons.

U2 - 10.1007/978-3-642-41582-1_2

DO - 10.1007/978-3-642-41582-1_2

M3 - Article in proceedings

SN - 978-3-642-41581-4

SP - 18

EP - 36

BT - Implementation and Application of Functional Languages

A2 - Hinze, Ralf

PB - Springer

Y2 - 30 August 2012 through 1 September 2012

ER -