Skeleton-based programming is an area of increasing relevance with upcoming highly parallel hardware, since it substantially facilitates parallel programming and separates concerns. When parallel algorithms expressed by skeletons involve iterations – applying the same algorithm repeatedly to successively improving data, the repeated instantiation of a skeleton incurs a certain overhead that could be saved by reusing existing processes, threads and communication structures. This is especially important when running parallel applications in a distributed environment.
However, customising a particular skeleton ad-hoc for repeated execution turns out to be considerably complicated, and raises general questions about introducing state into a stateless parallel computation. In addition, one would strongly prefer an approach which leaves the original skeleton intact, and only uses it as a building block inside a bigger structure.
In this work, we present a general framework for skeleton iteration and discuss requirements and variations of iteration control and iteration body. Skeleton iteration is expressed by synchronising a parallel iteration body skeleton with a (likewise parallel) state-based iteration control, where both skeletons offer supportive type safety by dedicated types geared towards stream communication for the iteration.
The skeleton iteration framework is implemented in the parallel Haskell dialect Eden. We use example applications to assess performance and overhead.