Structured Parallelism by Composition - Design and implementation of a framework supporting skeleton compositionality

Diese Arbeit widmet sich der effizienten Komponierbarkeit von algorithmischen Skeletten, einer Abstraktion von gängigen parallelen Programmierschemen, die sich in der funktionalen parallelen Programmiersprache Eden in einfacher Weise als Funktionen höherer Ordnung darstellen lassen. Durch algorithmi...

Ausführliche Beschreibung

Gespeichert in:
1. Verfasser: Dieterle, Mischa
Beteiligte: Loogen, Rita (Prof. Dr.) (BetreuerIn (Doktorarbeit))
Format: Dissertation
Veröffentlicht: Philipps-Universität Marburg 2015
Parallele Syst., Deklarative Prog.
Online Zugang:PDF-Volltext
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!



3. Stephan Ewen, Kostas Tzoumas, Moritz Kaufmann, and Volker Markl. Spinning fast iterative data flows. Proc. VLDB Endowment, 5(11):1268–1279, jul 2012.

4. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.

5. [ELZ + 10] Jaliya Ekanayake, Hui Li, Bingjing Zhang, Thilina Gunarathne, Seung-Hee Bae, Judy Qiu, and Geoffrey Fox. Twister: a runtime for iterative mapreduce. In Proceedings of Bibliography the 19th ACM International Symposium on High Performance Distributed Computing, pages 810–818. ACM, 2010.

6. Jost Berthold and Rita Loogen. Parallel Coordination Made Explicit in a Functional Setting. In Zoltán Horváth and Viktória Zsók, editors, 18th Intl. Symposium on the Implementation of Functional Languages (IFL 2006), LNCS 4449, Budapest, Hungary, 2007. Springer.

7. Simon Marlow, Ryan Newton, and Simon Peyton Jones. A Monad for Deterministic Parallelism. In Haskell '11: 4th ACM Symposium on Haskell. ACM, 2011.

8. Yingyi Bu, Bill Howe, Magdalena Balazinska, and Michael D. Ernst. The HaLoop approach to large-scale iterative data analysis. The VLDB Journal, 21(2):169–190, 2012.

9. Tim Sheard and Simon Peyton Jones. Template meta-programming for Haskell. In Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, pages 1–16. ACM, 2002.

10. Mischa Dieterle, Thomas Horstmeyer, and Rita Loogen. Skeleton composition using remote data. In Manuel Carro and Ricardo Peña, editors, Practical Aspects of Declarative Languages, PADL'10, volume 5937 of Lecture Notes in Computer Science, pages 73–87. Springer, 2010. (awarded most practical paper of PADL'10).

11. Mischa Dieterle, Jost Berthold, and Rita Loogen. A skeleton for distributed work pools in Eden. In Matthias Blume, Naoki Kobayashi, and Germán Vidal, editors, FLOPS, volume 6009 of Lecture Notes in Computer Science, pages 337–353. Springer, 2010.

12. Oleg Lobachev, Jost Berthold, Mischa Dieterle, and Rita Loogen. Parallel fft us- ing Eden skeletons. In 10th Intl. Conference on Parallel Computing Technologies (PaCT)'09, volume 5698 of Lecture Notes in Computer Science. Springer-Verlag, 2009.

13. [THM + 96] P.W. Trinder, K. Hammond, J.S. Mattson Jr., A.S. Partridge, and S.L. Peyton Jones. GUM: a Portable Parallel Implementation of Haskell. In PLDI'96. ACM, 1996.

14. [GHSJ94] S. K. S. Gupta, C.-H. Huang, P. Sadayappan, and R. W. Johnson. Implementing fast Fourier transforms on distributed-memory multiprocessors using data redistributions. Parallel Processing Letters, 4(4):477–488, 1994.

15. [LLS + 93] Xiaobo Li, Paul Lu, Jonathan Schaeffer, John Shillington, Pok Sze Wong, and Hanmao Shi. On the versatility of parallel sorting by regular sampling. Parallel Computing, 19(10):1079–1103, Oct 1993.

16. Anne Benoit and Murray Cole. Two fundamental concepts in skeletal parallel pro- gramming. In Computational Science–ICCS 2005, pages 764–771. Springer, 2005.

17. Carl Hewitt, Peter Bishop, and Richard Steiger. A Universal Modular ACTOR Formalism for Artificial Intelligence. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence, IJCAI'73. Morgan Kaufmann, 1973.

18. Jost Berthold and Rita Loogen. Visualizing Parallel Functional Program Runs – Case Studies with the Eden Trace Viewer. In Proceedings of the International Conference ParCo 2007, September 2007, Central Institute for Applied Mathematics, Jülich, Germany, 2007.

19. Anne Benoit and Murray Cole. eSkel – The Edinburgh Skeleton Library, University of Edinburgh 2002.

20. Martin Alt and Sergei Gorlatch. Adapting Java RMI for grid computing. Future Generation Computer Systems, 21(5):699–707, 2004.

21. Joe Armstrong. A History of Erlang. In Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III. ACM, 2007.

22. Murray Cole. Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press, 1989.

23. Marshall C. Pease. An adaptation of the fast Fourier transform for parallel processing. JACM, 15(2):252–264, April 1962.

24. Herbert Kuchen. A skeleton library. In Burkhard Monien and Rainer Feldmann, editors, Euro-Par 2002 Parallel Processing, volume 2400 of Lecture Notes in Computer Science, pages 620–629. Springer Berlin Heidelberg, 2002.

25. Kevin Hammond, Jost Berthold, and Rita Loogen. Automatic skeletons in template haskell. Parallel processing letters, 13(03):413–424, 2003.

26. Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. Concurrent haskell. In 23rd ACM Symposium on Principles of Programming Languages (POPL 96), volume 96, pages 295–308, 1996.

27. Ian Foster. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1995.

28. Jost Berthold, Mischa Dieterle, Oleg Lobachev, and Rita Loogen. Distributed memory Bibliography programming on many-cores -a case study using Eden divide-&-conquer skeletons.

29. Steffen Priebe. Dynamic task generation and transformation within a nestable workpool skeleton. In Wolfgang E. Nagel, Wolfgang V. Walter, and Wolfgang Lehner, editors, European Conference on Parallel Computing (Euro-Par) 2006, LNCS 4128, Dresden, Germany, 2006.

30. Denis Caromel and Mario Leyton. Fine tuning algorithmic skeletons. In Euro-Par 2007 Parallel Processing, pages 72–81. Springer, 2007.

31. Benoit B Mandelbrot. Fractal aspects of the iteration of z → λz (1-z) for complex λ and z. Annals of the New York Academy of Sciences, 357(1):249–259, 1980.

32. John Darlington, Yi-ke Guo, Hing Wing To, and Jin Yang. Functional skeletons for parallel coordination. In EURO-PAR'95 Parallel Processing, pages 55–66. Springer, 1995.

33. Martin Alt and Sergei Gorlatch. Future-Based RMI: Optimizing compositions of remote method calls on the Grid. In Harald Kosch, László Böszörményi, and Hermann Hellwagner, editors, Euro-Par 2003, volume 2790 of Lecture Notes in Computer Science, pages 682–693. Springer-Verlag, August 2003.

34. Jost Berthold, Mischa Dieterle, Rita Loogen, and Steffen Priebe. Hierarchical master- worker skeletons. In Paul Hudak and David S. Warren, editors, Practical Aspects of Declarative Languages: 10th International Symposium, PADL 2008, San Fran- cisco, CA, USA, January 2008. Proceedings, pages 248–264, Berlin, Heidelberg, 2008.

35. David B Loveman. High performance fortran. Parallel & Distributed Technology: Systems & Applications, IEEE, 1(1):25–42, 1993.

36. Jost Berthold, Mischa Dieterle, and Rita Loogen. Implementing parallel google map-reduce in Eden. In H. Sips, D. Epema, and H.X. Lin, editors, Euro-Par 2009, volume 5704 of Lecture Notes in Computer Science, pages 990–1002. Springer-Verlag, 2009.

37. Rishiyur S Nikhil. Implicit parallel programming in pH. Oxford University Press, 2001.

38. David MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. Chapter 20. An Example Inference Task: Clustering PDF, pages 284–292.

39. Mischa Dieterle, Thomas Horstmeyer, Jost Berthold, and Rita Loogen. Iterating skeletons. In Ralf Hinze, editor, Implementation and Application of Functional Languages, volume 8241 of Lecture Notes in Computer Science, pages 18–36. Springer Berlin Heidelberg, 2013.

40. Yousef Saad. Iterative Methods for Sparse Linear Systems. PWS Publishing Company, 1996.

41. [BDO + 95] B. Bacci, M. Danelutto, S. Orlando, S. Pelagatti, and M. Vanneschi. P 3 L: A Structured High Level Programming Language and its Structured Support. Concurrency — Practice and Experience, 7(3):225–255, May 1995.

42. Michael J. Quinn. Parallel Computing (2Nd Ed.): Theory and Practice. McGraw-Hill, Inc., New York, NY, USA, 1994.

43. Mischa Dieterle. Parallel functional implementation of master worker skeletons. Diploma Thesis, Philipps-Universität Marburg, October 2007. (in german).

44. [PR01] R. Peña and F. Rubio. Parallel functional programming at two levels of abstraction. In PPDP'01 — Intl. Conf. on Principles and Practice of Declarative Programming, pages 187–198, Firenze, Italy, September 5–7, 2001.

45. [LOMP05] R. Loogen, Y. Ortega-Mallén, and R. Peña-Marí. Parallel functional programming in Eden. Journal of Functional Programming, 15(3):431–475, 2005.

46. [LOP + 03] Rita Loogen, Yolanda Ortega, Ricardo Peña, Steffen Priebe, and Fernando Rubio. Parallelism abstractions in Eden. In Patterns and Skeletons for Parallel and Distributed Computing, pages 95–128. Springer, 2003.

47. John Darlington, Yi-ke Guo, Hing Wing To, and Jin Yang. Parallel skeletons for structured composition. In PPOPP '95: Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 19–28, New York, NY, USA, 1995. ACM.

48. Fernando Rubio. Programación funcional paralele eficiente en Eden. PhD thesis, Universidad Complutense de Madrid, October 2001.

49. Sergei Gorlatch. Programming with divide-and-conquer skeletons: A case study of FFT. J. of Supercomputing, pages 85–97, 1998.

50. M. Leyton and J. M. Piquer. Skandium: Multi-core programming with algorithmic skeletons. In PDP. IEEE Computer Society, 2010.


52. Marco Danelutto, Fabrizio Pasqualetti, and Susanna Pelagatti. Skeletons for data parallelism in p31. In Euro-Par'97 Parallel Processing, pages 619–628. Springer, 1997.

53. W Morven Gentleman. Some complexity results for matrix computations on parallel processors. Journal of the ACM (JACM), 25(1):112–115, 1978.

54. Susanna Pelagatti. Task and data parallelism in P3L. In Patterns and skeletons for parallel and distributed computing, pages 155–186. Springer, 2003.

55. Herbert Kuchen and Murray Cole. The integration of task and data parallel skeletons. Parallel Processing Letters, 12(2):141–155, 2002.

56. Jeff Epstein, Andrew P. Black, and Simon Peyton-Jones. Towards Haskell in the cloud. In Proceedings of the 4th ACM Symposium on Haskell, Haskell '11, New York, USA, 2011. ACM.

57. Martin Alt. Using Algorithmic Skeletons for Efficient Grid Computing with Predictable Performance. PhD thesis, Universität Münster, July 2007.

58. Horacio González-Vélez and Mario Leyton. A survey of algorithmic skeleton frame- works: High-level structured parallel programming enablers. Softw. Pract. Exper., 40(12):1135–1160, November 2010.

59. Edsko de Vries. Communication patterns in Cloud Haskell (part 3): Map reduce. Blog Series (Web):, October 2012.

60. Herbert Kuchen. The Münster Skeleton Library Muesli. Universität Münster, URL:, 2007.

61. [Aut07] Wiki Authors. Foldable and traversable. Haskell Wiki (, 2007.

62. Robert Harper. Practical foundations for programming languages. Cambridge Univer- sity Press, 2015. second edition preview, available at ~rwh/plbook/2nded.pdf.