Abstract
Today, parallel programming is dominated by message passing libraries such as MPI. Algorithmic skeletons intend to simplify parallel programming by their expressive power. The idea is to offer typical parallel programming patterns as polymorphic higher-order functions which are efficiently implemented in parallel. Skeletons can be understood as a domain-specific language for parallel programming. In this chapter, we describe a set of data parallel skeletons in detail and investigate the potential of optimizing sequences of these skeletons by replacing them by more efficient sequences. Experimental results based on a draft implementation of our skeleton library are shown.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bischof, H., Gorlatch, S.: Double-Scan: Introducing and Implementing a New Data-Parallel Skeleton. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 640–647. Springer, Heidelberg (2002)
Bird, R.: Lectures on Constructive Functional Programming. In: Broy, M. (ed.) Constructive Methods in Computing Science. NATO ASI Series, pp. 151–216. Springer, Heidelberg (1988)
Bird, R.: Algebraic identities for program calculation. The Computer Journal 32(2), 122–126 (1989)
Botorog, G.H., Kuchen, H.: Efficient Parallel Programming with Algorithmic Skeletons. In: Fraigniaud, P., Mignotte, A., Bougé, L., Robert, Y. (eds.) Euro-Par 1996. LNCS, vol. 1123, pp. 718–731. Springer, Heidelberg (1996)
Botorog, G.H., Kuchen, H.: Efficient High-Level Parallel Programming. Theoretical Computer Science 196, 71–107 (1998)
Cole, M.: Algorithmic Skeletons: Structured Management of Parallel Computation. MIT Press, Cambridge (1989)
Darlington, J., Field, A.J., Harrison, T.G., et al.: Parallel Programming Using Skeleton Functions. In: Reeve, M., Bode, A., Wolf, G. (eds.) PARLE 1993. LNCS, vol. 694, pp. 146–160. Springer, Heidelberg (1993)
Darlington, J., Guo, Y., To, H.W., Yang, J.: Functional Skeletons for Parallel Coordination. In: Haridi, S., Ali, K., Magnusson, P. (eds.) Euro-Par 1995. LNCS, vol. 966, pp. 55–66. Springer, Heidelberg (1995)
Danelutto, M., Pasqualetti, F., Pelagatti, S.: Skeletons for Data Parallelism in p3l. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds.) Euro-Par 1997. LNCS, vol. 1300, pp. 619–628. Springer, Heidelberg (1997)
Foster, I., Olson, R., Tuecke, S.: Productive Parallel Programming: The PCN Approach. Scientific Programming 1(1), 51–66 (1992)
Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns. Addison-Wesley, Reading (1995)
Gropp, W., Lusk, E., Skjellum, A.: Using MPI. MIT Press, Cambridge (1999)
Gorlatch, S., Lengauer, C. (De)Composition Rules for Parallel Scan and Reduction. In: 3rd Int. Working Conf. on Massively Parallel Programming Models (MPPM 1997), pp. 23–32. IEEE, Los Alamitos (1997)
Gorlatch, S.: Optimizing Compositions of Components in Parallel and Distributed Programming. LNCS, vol. 3016. Springer, Heidelberg (2004)
Gorlatch, S., Wedler, C., Lengauer, C.: Optimization Rules for Programming with Collective Operations. In: 13th Int. Parallel Processing Symp. & 10th Symp. on Parallel and Distributed Processing, pp. 492–499 (1999)
Karmesin, S., et al.: Array Design and Expression Evaluation in POOMA II. In: Caromel, D., Oldehoeft, R.R., Tholburn, M. (eds.) ISCOPE 1998. LNCS, vol. 1505, pp. 231–238. Springer, Heidelberg (1998)
Kuchen, H., Cole, M.: The Integration of Task and Data Parallel Skeletons. Parallel Processing Letters 12(2), 141–155 (2002)
Koelbl, C.H., et al.: The High Performance Fortran Handbook. Scientific and Engineering Computation. MIT Press, Cambridge (1994)
Kuchen, H., Plasmeijer, R., Stoltze, H.: Efficient Distributed Memory Implementation of a Data Parallel Functional Language. In: Halatsis, C., Philokyprou, G., Maritsas, D., Theodoridis, S. (eds.) PARLE 1994. LNCS, vol. 817, pp. 466–475. Springer, Heidelberg (1994)
Kuchen, H., Striegnitz, J.: Higher-Order Functions and Partial Applications for a C++ Skeleton Library. In: Joint ACM Java Grande & ISCOPE Conference, pp. 122–130. ACM, New York (2002)
Kuchen, H.: A Skeleton Library. In: Monien, B., Feldmann, R.L. (eds.) Euro-Par 2002. LNCS, vol. 2400, pp. 620–629. Springer, Heidelberg (2002)
Kuchen, H.: The Skeleton Library Web Pages, http://danae.uni-muenster.de/lehre/kuchen/Skeletons/
Lengauer, C.: Program Optimization in the Domain of High-Performance Parallelism. In: Lengauer, C., Batory, D., Consel, C., Odersky, M. (eds.) Domain-Specific Program Generation. LNCS, vol. 3016, pp. 73–91. Springer, Heidelberg (2004)
McColl, W.: Scalable Computing. In: van Leeuwen, J. (ed.) Computer Science Today. LNCS, vol. 1000, pp. 46–61. Springer, Heidelberg (1995)
McNamara, B., Smaragdakis, Y.: Functional Programming in C++. In: ICFP 2000, pp. 118–129. ACM, New York (2000)
Skillicorn, D.B., Danelutto, M., Pelagatti, S., Zavanella, A.: Optimising Data-Parallel Programs Using the BSP Cost Model. In: Pritchard, D., Reeve, J.S. (eds.) Euro-Par 1998. LNCS, vol. 1470, pp. 698–703. Springer, Heidelberg (1998)
Skillicorn, D., Hill, J.M.D., McColl, W.: Questions and Answers about BSP. Scientific Programming 6(3), 249–274 (1997)
Skillicorn, D.: Foundations of Parallel Programming. Cambridge U. Press, Cambridge (1994)
Smaragdakis, Y.: A Personal Outlook on Generator Research. In: Lengauer, C., Batory, D., Consel, C., Odersky, M. (eds.) Domain-Specific Program Generation. LNCS, vol. 3016, pp. 92–106. Springer, Heidelberg (2004)
Striegnitz, J.: Making C++ Ready for Algorithmic Skeletons. Tech. Report IB-2000-08, http://www.fz-juelich.de/zam/docs/autoren/striegnitz.html
Zima, H.P., Chapman, B.M.: Supercompilers for Parallel and Vector Computers. ACM Press/Addison-Wesley (1990)
ZIV-Cluster, http://zivcluster.uni-muenster.de/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kuchen, H. (2004). Optimizing Sequences of Skeleton Calls. In: Lengauer, C., Batory, D., Consel, C., Odersky, M. (eds) Domain-Specific Program Generation. Lecture Notes in Computer Science, vol 3016. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25935-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-25935-0_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22119-7
Online ISBN: 978-3-540-25935-0
eBook Packages: Springer Book Archive