Iterating skeletons: structured parallelism by composition
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
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.
Original language | English |
---|---|
Title of host publication | Implementation and Application of Functional Languages : 24th International Symposium, IFL 2012, Oxford, UK, August 30 - September 1, 2012, Revised Selected Papers |
Editors | Ralf Hinze |
Number of pages | 19 |
Publisher | Springer |
Publication date | 2013 |
Pages | 18-36 |
ISBN (Print) | 978-3-642-41581-4 |
ISBN (Electronic) | 978-3-642-41582-1 |
DOIs | |
Publication status | Published - 2013 |
Event | 24th International Symposium on Implementation and Application of Functional Languages - Oxford, United Kingdom Duration: 30 Aug 2012 → 1 Sep 2012 Conference number: 24 |
Conference
Conference | 24th International Symposium on Implementation and Application of Functional Languages |
---|---|
Nummer | 24 |
Land | United Kingdom |
By | Oxford |
Periode | 30/08/2012 → 01/09/2012 |
Bibliographical note
A revised version was published in the peer-reviewed proceedings of IFL 2012.
ID: 43868769