Iterating skeletons: structured parallelism by composition

Mischa Dieterle; Thomas Horstmeyer; Jost Berthold; Rita Loogen

doi:10.1007/978-3-642-41582-1_2

Iterating skeletons: structured parallelism by composition

Mischa Dieterle, Thomas Horstmeyer, Jost Berthold, Rita Loogen

Department of Computer Science

4 Citations (Scopus)

Abstract

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.

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	https://doi.org/10.1007/978-3-642-41582-1_2
Publication status	Published - 2013
Event	24th International Symposium on Implementation and Application of Functional Languages - Oxford, United Kingdom Duration: 30 Aug 2012 → 1 Sept 2012 Conference number: 24

Conference

Conference	24th International Symposium on Implementation and Application of Functional Languages
Number	24
Country/Territory	United Kingdom
City	Oxford
Period	30/08/2012 → 01/09/2012

Access to Document

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

Cite this

Dieterle, M., Horstmeyer, T., Berthold, J., & Loogen, R. (2013). Iterating skeletons: structured parallelism by composition. In R. Hinze (Ed.), Implementation and Application of Functional Languages: 24th International Symposium, IFL 2012, Oxford, UK, August 30 - September 1, 2012, Revised Selected Papers (pp. 18-36). Springer. https://doi.org/10.1007/978-3-642-41582-1_2

Iterating skeletons : structured parallelism by composition. / Dieterle, Mischa; Horstmeyer, Thomas; Berthold, Jost et al.

Implementation and Application of Functional Languages: 24th International Symposium, IFL 2012, Oxford, UK, August 30 - September 1, 2012, Revised Selected Papers. ed. / Ralf Hinze. Springer, 2013. p. 18-36.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Dieterle, M, Horstmeyer, T, Berthold, J & Loogen, R 2013, Iterating skeletons: structured parallelism by composition. in R Hinze (ed.), Implementation and Application of Functional Languages: 24th International Symposium, IFL 2012, Oxford, UK, August 30 - September 1, 2012, Revised Selected Papers. Springer, pp. 18-36, 24th International Symposium on Implementation and Application of Functional Languages, Oxford, United Kingdom, 30/08/2012. https://doi.org/10.1007/978-3-642-41582-1_2

@inproceedings{6eae17fdcef045e6aa6cc6a4fa7e38e6,

title = "Iterating skeletons: structured parallelism by composition",

abstract = "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.",

author = "Mischa Dieterle and Thomas Horstmeyer and Jost Berthold and Rita Loogen",

note = "A revised version was published in the peer-reviewed proceedings of IFL 2012.; 24th International Symposium on Implementation and Application of Functional Languages, IFL 2012 ; Conference date: 30-08-2012 Through 01-09-2012",

year = "2013",

doi = "10.1007/978-3-642-41582-1_2",

language = "English",

isbn = "978-3-642-41581-4",

pages = "18--36",

editor = "Ralf Hinze",

booktitle = "Implementation and Application of Functional Languages",

publisher = "Springer",

}

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 -

Iterating skeletons: structured parallelism by composition

Abstract

Conference

Access to Document

Fingerprint

Cite this