Dokument

Summary:
This thesis is dedicated to the efficient compositionality of algorithmic skeletons, which are abstractions of common parallel programming patterns. Skeletons can be implemented in the functional parallel language Eden as mere parallel higher order functions. The use of algorithmic skeletons facilitates parallel programming massively. This is because they already implement the tedious details of parallel programming and can be specialised for concrete applications by providing problem specific functions and parameters. Efficient skeleton compositionality is of particular importance because complex, specialised skeletons can be compound of simpler base skeletons. The resulting modularity is especially important for the context of functional programming and should not be missing in a functional language. We subdivide composition into three categories: -Nesting: A skeleton is instantiated from another skeleton instance. Communication is tree shaped, along the call hierarchy. This is directly supported by Eden. -Composition in sequence: The result of a skeleton is the input for a succeeding skeleton. Function composition is expressed in Eden by the ( . ) operator. For performance reasons the processes of both skeletons should be able to exchange results directly instead of using the indirection via the caller process. We therefore introduce the remote data concept. -Iteration: A skeleton is called in sequence a variable number of times. This can be defined using recursion and composition in sequence. We optimise the number of skeleton instances, the communication in between the iteration steps and the control of the loop. To this end, we developed an iteration framework where iteration skeletons are composed from control and body skeletons. Central to our composition concept is remote data. We send a remote data handle instead of ordinary data, the data handle is used at its destination to request the referenced data. Remote data can be used inside arbitrary container types for efficient skeleton composition similar to ordinary distributed data types. The free combinability of remote data with arbitrary container types leads to a high degree of flexibility. The programmer is not restricted by using a predefined set of distributed data types and (re-)distribution functions. Moreover, he can use remote data with arbitrary container types to elegantly create process topologies. For the special case of skeleton iteration we prevent the repeated construction and deconstruction of skeleton instances for each single iteration step, which is common for the recursive use of skeletons. This minimises the parallel overhead for process and channel creation and allows to keep data local on persistent processes. To this end we provide a skeleton framework. This concept is independent of remote data, however the use of remote data in combination with the iteration framework makes the framework more flexible. For our case studies, both approaches perform competitively compared to programs with identical parallel structure but which are implemented using monolithic skeletons - i.e. skeleton not composed from simpler ones. Further, we present extensions of Eden which enhance composition support: generalisation of overloaded communication, generalisation of process instantiation, compositional process placement and extensions of Box types used to adapt communication behaviour.

Bibliographie / References

1. Silvia Breitinger. Design and Implementation of the Parallel Functional Language Eden. PhD thesis, Philipps-University of Marburg, Germany, 1998. Available at http://archiv.ub.uni-marburg.de/diss/z1999/0142/.
2. Jost Berthold. Explicit and implicit parallel functional programming : concepts and implementation. PhD thesis, Philipps-Universität Marburg, July 2008.
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. http://homepages.inf.ed.ac.uk/abenoit1/eSkel/.
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): http://www.well-typed.com/blog/73/, October 2012.
60. Herbert Kuchen. The Münster Skeleton Library Muesli. Universität Münster, URL: http://www.wi.uni-muenster.de/PI/forschung/Skeletons/index.php, 2007.
61. [Aut07] Wiki Authors. Foldable and traversable. Haskell Wiki (https://wiki.haskell.org/Foldable_and_Traversable), 2007.
62. Robert Harper. Practical foundations for programming languages. Cambridge Univer- sity Press, 2015. second edition preview, available at https://www.cs.cmu.edu/ ~rwh/plbook/2nded.pdf.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten