Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-12T10:14:52.121Z Has data issue: false hasContentIssue false
  • English
  • Français

Skeleton composition versus stable process systems in Eden

Part of: JFP Research Articles

Published online by Cambridge University Press:  15 July 2016

M. DIETERLE ,
T. HORSTMEYER ,
R. LOOGEN  and
J. BERTHOLD
M. DIETERLE
Affiliation:
Fachbereich Mathematik und Informatik, Philipps-Universität, Marburg, Germany (e-mail: [email protected], [email protected], [email protected])
T. HORSTMEYER
Affiliation:
Fachbereich Mathematik und Informatik, Philipps-Universität, Marburg, Germany (e-mail: [email protected], [email protected], [email protected])
R. LOOGEN
Affiliation:
Fachbereich Mathematik und Informatik, Philipps-Universität, Marburg, Germany (e-mail: [email protected], [email protected], [email protected])
J. BERTHOLD
Affiliation:
Commonwealth Bank of Australia, Sydney, Australia (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We compare two inherently different approaches to implement complex process systems in Eden: stable process systems and a compositional approach. A stable process system is characterised by handling several computation stages in each of the participating processes. Often, processes communicate using streams of data, change behaviour with the different computation phases, and more often than not, exactly one process is allocated to each processor element. In contrast, a complex process system can also be achieved by skeleton composition of a number of elementary skeletons, such as parallel transformation, reduction, or special communication patterns. In a compositional implementation, each computation phase leads to a new set of interacting processes. When implementing complex parallel algorithms, skeleton composition is usually easier and more flexible, but has a larger overhead from additional process creation and communication. We present case studies of different parallel application kernels implemented as stable systems and using composition in Eden, including a comprehensive description of Eden's features. Our results show that the compositional performance loss can be alleviated by co-locating processes which directly communicate, and by using Eden's remote data concept to enable such direct communication. Moreover, Eden's parallel runtime system handles communication between co-located processes in an optimised way. EdenTV visualisations of execution traces are invaluable to analyse program characteristics and for targeted optimisations towards better process placement and communication avoidance.

Type
Articles
Information
Journal of Functional Programming , Volume 26 , 2016 , e11
Copyright
Copyright © Cambridge University Press 2016 

References

Aditya, Sh., Arvind, , Augustsson, L., Maessen, J.-W. & Nikhil, R. S. (1995) Semantics of pH: A parallel dialect of Haskell. In Proceedings of the Haskell Workshop, Hudak, P. (ed), YALE Research Report DCS/RR-1075, Yale University. Available at https://www.haskell.org/haskell-workshop/1995/HW1995-Proceedings.pdf [Accessed 27 Apr. 2016] pp. 35–49.Google Scholar
Armstrong, J. (2007) A history of Erlang. In Proceedings of the 3rd ACM SIGPLAN Conference on History of Programming Languages. HOPL III. ACM, New York, NY, USA, pp. 6-1–6-26.Google Scholar
Bacci, B., Danelutto, M., Orlando, S., Pelagatti, S. & Vanneschi, M. (1995) P3L: A structured high level programming language and its structured support. Concurrency — Pract. Exp. 7 (3), pp. 225–255.CrossRefGoogle Scholar
Benoit, A. & Cole, M. (2002) eSkel — The Edinburgh Skeleton Library. Available at: http://homepages.inf.ed.ac.uk/mic/eSkel/ [Accessed 27 Apr. 2016].Google Scholar
Berthold, J., Dieterle, M. & Loogen, R. (2009a) Implementing parallel google map-reduce in Eden. In Euro-Par 2009 Parallel Processing, 15th International Euro-Par Conference, Proceedings, Sips, H., Epema, D. & Lin, H. X. (eds), Lecture Notes in Computer Science, vol. 5704. Springer, pp. 990–1002.CrossRefGoogle Scholar
Berthold, J., Dieterle, M., Lobachev, O. & Loogen, R. (2009b) Parallel FFT using Eden Skeletons. In Parallel Computing Technologies, 10th International Conference, PaCT 2009, Malyshkin, V. (ed), Lecture Notes in Computer Science, vol. 5698. Springer, pp. 73–83.Google Scholar
Berthold, J. & Loogen, R. (2007) Parallel coordination made explicit in a functional setting. In IFL 2006, 18th Intl. Symposium on the Implementation of Functional Languages, Horváth, Z. & Zsók, V. (eds), Lecture Notes in Computer Science, vol. 4449, Springer. (awarded best paper of IFL'06), pp. 73–90.Google Scholar
Berthold, J. & Loogen, R. (2008) Visualizing parallel functional program Executions: Case studies with the Eden trace viewer. In Parallel Computing: Architectures, Algorithms and Applications. Proceedings of the International Conference Parco 2007, Bischof, C. H., Bücker, H. M., Gibbon, P., Joubert, G. R., Lippert, Th., Mohr, B. & Peters, F. J. (eds), Advances in Parallel Computing, vol. 15. IOS Press, pp. 121–128.Google Scholar
Blelloch, G. E. (1996) Programming parallel algorithms. Commun. ACM 39 (3), 85–97.CrossRefGoogle Scholar
Breitinger, S. (1998) Design and Implementation of the Parallel Functional Language Eden. Ph.D. thesis, Philipps-University of Marburg, Germany. Available at http://archiv.ub.uni-marburg.de/diss/z1999/0142/ [Accessed 27 Apr. 2016].Google Scholar
Chakravarty, M. M. T., Keller, G., Peyton Jones, S. & Marlow, S. (2005) Associated types with class. In POPL 2005, Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Palsberg, J. & Abadi, M. (eds), ACM, pp. 1–13.Google Scholar
Chakravarty, M. M. T., Keller, G., Lee, S., McDonell, T. L. & Grover, V. (2011) Accelerating Haskell array codes with multicore GPUs. In DAMP 2011, Proceedings of the 6th Workshop on Declarative Aspects of Multicore Programming, Carro, M. & Reppy, J. H. (eds), ACM, pp. 3–14.Google Scholar
Chakravarty, M. M. T., Leshchinskiy, R., Peyton Jones, S., Keller, G. & Marlow, S. (2007) Data parallel Haskell: A status report. In DAMP 2007, Proceedings of the POPL 2007 Workshop on Declarative Aspects of Multicore Programming, Glew, N. & Blelloch, G. E. (eds), ACM, pp. 10–18.CrossRefGoogle Scholar
Cole, M. I. (1989) Algorithmic Skeletons: Structured Management of Parallel Computation. Research Monographs in Parallel and Distributed Computing. MIT Press.Google Scholar
Dieterle, M., Horstmeyer, Th., Berthold, J. & Loogen, R. (2013) Iterating Skeletons – structured parallelism by composition. In IFL 2012, Implementation and Application of Functional Languages, Revised selected papers, Hinze, R. & Gill, A. (eds), Lecture Notes in Computer Science, vol. 8241. Springer, pp. 18–36.Google Scholar
Dieterle, M., Horstmeyer, Th. & Loogen, R. (2010) Skeleton composition using remote data. In Practical Aspects of Declarative Languages, 12th International Symposium, PADL 2010, Carro, M. & Peña, R. (eds), Lecture Notes in Computer Science, vol. 5937. Springer, pp. 73–87.Google Scholar
Epstein, J., Black, A. P. & Peyton-Jones, S. (2011) Towards Haskell in the Cloud. In Haskell 2011: Proceedings of the 4th ACM Symposium on Haskell, Claessen, K. (ed), ACM, pp. 118–129.Google Scholar
Ferreira, J. F., Sobral, J. L. & Proença, A. J. (2006) JaSkel: A Java skeleton-based framework for structured cluster and grid computing. CCGrid 2006, 6th IEEE International Symposium on Cluster Computing and the Grid. IEEE Computer Society, pp. 301–304.CrossRefGoogle Scholar
GHC. (1991–2015) The Glasgow Haskell Compiler. Available at: http://www.haskell.org/ghc [Accessed 27 Apr. 2016].Google Scholar
González-Vélez, H. & Leyton, M. (2010) A survey of algorithmic Skeleton frameworks: High-level structured parallel programming enablers. Softw. Pract. Exper. 40 (12), 1135–1160.CrossRefGoogle Scholar
Haskell. (2010) Haskell 2010 Language Report. edited by Marlow, S.. Available at: http://www.haskell.org/ [Accessed 27 Apr. 2016].Google Scholar
Hewitt, C., Bishop, P. & Steiger, R. (1973) A universal modular ACTOR formalism for artificial intelligence. In Proceedings of the 3rd International Joint Conference on Artificial Intelligence. IJCAI'73. Morgan Kaufmann, pp. 235–245.Google Scholar
Jones, D. Jr., Marlow, S. & Singh, S. (2009) Parallel performance tuning for Haskell. In Haskell 2009, Proceedings of the 2nd ACM SIGPLAN Symposium on Haskell. ACM, pp. 81–92.Google Scholar
Kuchen, H. (2007) The Münster Skeleton Library Muesli. Universität Münster, Available at: http://www.wi1.uni-muenster.de/pi/forschung/Skeletons/ [Accessed 27 Apr. 2016].Google Scholar
Leshchinskiy, R. (2008) Vector library. Available at: http://hackage.haskell.org/package/vector [Accessed 27 Apr. 2016].Google Scholar
Li, X., Lu, P., Schaeffer, J., Shillington, J., Wong, P. S. & Shi, H. (1993) On the versatility of parallel sorting by regular sampling. Parallel Comput. 19 (10), 1079–1103.CrossRefGoogle Scholar
Lippmeier, B., Chakravarty, M., Keller, G. & Peyton Jones, S. (2012) Guiding parallel array fusion with indexed types. In Haskell 2012, Proceedings of the 2012 Haskell Symposium. ACM, pp. 25–36.CrossRefGoogle Scholar
Loogen, R., Ortega-Mallén, Y., Peña, R., Priebe, St. & Rubio, F. (2003) Parallelism Abstractions in Eden. In Rabhi, F. A. & Gorlatch, S. (eds), Patterns and Skeletons for Parallel and Distributed Computing. Springer, pp. 95–128.CrossRefGoogle Scholar
Loogen, R., Ortega-Mallén, Y. & Peña-Marí, R. (2005) Parallel functional programming in Eden. J. Funct. Program. 15 (3), 431–475.CrossRefGoogle Scholar
Maier, P., Stewart, R. & Trinder, P. (2014) The HdpH DSLs for scalable reliable computation. In Haskell 2014: Proceedings of the 2014 ACM SIGPLAN Symposium on Haskell. ACM, pp. 65–76.CrossRefGoogle Scholar
Mainland, G. & Morrisett, G. (2010) Nikola: Embedding compiled GPU functions in Haskell. In Haskell 2010, Proceedings of the 3rd ACM SIGPLAN Symposium on Haskell. ACM, pp. 67–78.Google Scholar
Marlow, S., Maier, P., Loidl, H.-W., Aswad, M. K. & Trinder, P. (2010) Seq no more: Better strategies for parallel Haskell. In Haskell 2010, Proceedings of the 3rd ACM SIGPLAN Symposium on Haskell. ACM, pp. 91–102.Google Scholar
Marlow, S., Newton, R. & Peyton Jones, S. (2011) A monad for deterministic parallelism. In Haskell 2011, Proceedings of the 4th ACM Symposium on Haskell. ACM, pp. 71–82.Google Scholar
Peyton Jones, S. L., Clack, C. D., Salkild, J. & Hardie, M. (1987) GRIP - a high-performance architecture for parallel graph reduction. In FPCA 1987, Intl. Conf. on Functional Programming Languages and Computer Architecture. Lecture Notes in Computer Science, vol. 274. Springer, pp. 98–112.Google Scholar
Saad, Y. (1996) Iterative Methods for Sparse Linear Systems. PWS Publishing Company.Google Scholar
Trinder, P. W., Hammond, K. Jr., Mattson, J. S., Partridge, A. S. & Peyton Jones, S. L. (1996) GUM: A portable parallel implementation of Haskell. In PLDI 1996, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Fischer, Ch. N. (ed), ACM, pp. 78–88.Google Scholar
Trinder, P. W., Hammond, K., Loidl, H.-W. & Peyton Jones, S. L. (1998) Algorithm + Strategy = Parallelism. J. Funct. Program. 8 (1), 23–60.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.