×

Skeleton-based parallel programming: functional and parallel semantics in a single shot. (English) Zbl 1112.68026

Summary: Semantics of skeleton-based parallel programming languages comes usually as two distinct items: a functional semantics, modeling the function computed by the skeleton program, and a parallel semantics describing the ways used to exploit parallelism during the execution of the skeleton program. The former is usually expressed using some kind of semantic formalism, while the latter is almost always given in an informal way. Such a separation of functional and parallel semantics seriously impairs the possibility of programmers to use the semantic tools to prove properties of programs. In this work, we show how a formal semantic framework can be set up that handles both functional and parallel aspects of skeleton-based parallel programs. The framework is based on a labeled transition system. We show how different properties related to skeleton programs can be proved using such a system. We use Lithium, a skeleton-based full Java parallel programming environment, as the case study.

MSC:

68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68Q55 Semantics in the theory of computing

Software:

SKIPPER; Eden; eSkel; BSMLlib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldinucci M, Danelutto M. An operational semantics for skeletons. In: Joubert GR, Nagel WE, Peters FJ, Walter WV, editors. Parallel computing: software technology, algorithms, architectures and applications, PARCO 2003, Advances in parallel computing, vol. 13. Dresden, Germany: Elsevier; 2004, p. 63-70.; Aldinucci M, Danelutto M. An operational semantics for skeletons. In: Joubert GR, Nagel WE, Peters FJ, Walter WV, editors. Parallel computing: software technology, algorithms, architectures and applications, PARCO 2003, Advances in parallel computing, vol. 13. Dresden, Germany: Elsevier; 2004, p. 63-70.
[2] Cole M. Algorithmic skeletons: structured management of parallel computations, Research monographs in parallel and distributed computing. London: Pitman; 1989.; Cole M. Algorithmic skeletons: structured management of parallel computations, Research monographs in parallel and distributed computing. London: Pitman; 1989.
[3] Au, P.; Darlington, J.; Ghanem, M.; Guo, Y.; To, H.; Yang, J., Co-ordinating heterogeneous parallel computation, (Bouge, L.; Fraigniaud, P.; Mignotte, A.; Robert, Y., Proceedings of Euro-Par 1996 (1996), Springer: Springer Berlin), 601-614
[4] Bacci, B.; Danelutto, M.; Orlando, S.; Pelagatti, S.; Vanneschi, M., \(P^3\) L: a structured high-level programming language and its structured support, Concurrency Practice and Experience, 7, 3, 225-255 (1995)
[5] Bacci, B.; Danelutto, M.; Pelagatti, S.; Vanneschi, M., SkIE: a heterogeneous environment for HPC applications, Parallel Computing, 25, 13-14, 1827-1852 (1999)
[6] Pelagatti, S., Structured development of parallel programs (1998), Taylor & Francis: Taylor & Francis London
[7] Sérot, J.; Ginhac, D., Skeletons for parallel image processing: an overview of the SKIPPER project, Parallel Computing, 28, 12, 1685-1708 (2002) · Zbl 1043.68106
[8] Loulergue, F., Distributed evaluation of functional BSP programs, Parallel Processing Letters, 4, 423-437 (2001)
[9] Klusik U, Loogen R, Priebe S, Rubio F. Implementation skeletons in Eden—low-effort parallel programming. In: IFL’00—International workshop on the implementation of functional languages. Lecture notes in computer science, vol. 2011. Aachen, Germany: Springer; 2000. p. 71-88.; Klusik U, Loogen R, Priebe S, Rubio F. Implementation skeletons in Eden—low-effort parallel programming. In: IFL’00—International workshop on the implementation of functional languages. Lecture notes in computer science, vol. 2011. Aachen, Germany: Springer; 2000. p. 71-88. · Zbl 0977.68676
[10] Kuchen H. A skeleton library. In: Monien B, Feldmann R, editors. Proceedings of Euro-Par 2002. Lecture notes in computer science, vol. 2400. Berlin: Springer; 2002. p. 620-9.; Kuchen H. A skeleton library. In: Monien B, Feldmann R, editors. Proceedings of Euro-Par 2002. Lecture notes in computer science, vol. 2400. Berlin: Springer; 2002. p. 620-9. · Zbl 1068.68646
[11] Cole, M., Bringing skeletons out of the closet: A pragmatic manifesto for skeletal parallel programming, Parallel Computing, 30, 3, 389-406 (2004)
[12] MacDonald, S.; Anvik, J.; Bromling, S.; Schaeffer, J.; Szafron, D.; Taa, K., From patterns to frameworks to parallel programs, Parallel Computing, 28, 12, 1663-1684 (2002) · Zbl 1043.68046
[13] Gava F, Loulergue F. A parallel virtual machine for bulk synchronous parallel ML. In: International conference on computational science (ICCS 2003). Lecture notes in computer science, vol. 2657. Berlin: Springer; 2003. p. 155-64.; Gava F, Loulergue F. A parallel virtual machine for bulk synchronous parallel ML. In: International conference on computational science (ICCS 2003). Lecture notes in computer science, vol. 2657. Berlin: Springer; 2003. p. 155-64. · Zbl 1033.68532
[14] Loulergue F, Hu Z, Kakehi K. An implementation of the diffusion algorithmic skeleton with the BSMLlib library. Technical Report METR-2004-06, Department of Mathematical Informatics, University of Tokyo; 2004.; Loulergue F, Hu Z, Kakehi K. An implementation of the diffusion algorithmic skeleton with the BSMLlib library. Technical Report METR-2004-06, Department of Mathematical Informatics, University of Tokyo; 2004.
[15] Cosmo RD, Pelagatti S, Li Z. A calculus for parallel computations over multidimensional dense arrays. Computer Languages, Systems and Structures, 2006, in press, doi: 10.1016/j.cl2006.07.05; Cosmo RD, Pelagatti S, Li Z. A calculus for parallel computations over multidimensional dense arrays. Computer Languages, Systems and Structures, 2006, in press, doi: 10.1016/j.cl2006.07.05 · Zbl 1112.68058
[16] Hidalgo-Herrero, M.; Ortega-Mallén, Y., An operational semantics for the parallel language Eden, Parallel Processing Letters, 12, 2, 211-228 (2002)
[17] The Ocaml home page, \( \langle;\) http://www.ocaml.org \(\rangle;\); The Ocaml home page, \( \langle;\) http://www.ocaml.org \(\rangle;\)
[18] Aldinucci M, Danelutto M. Stream parallel skeleton optimization. In: Proceedings of the 11th IASTED international conference on parallel and distributed computing and systems (PDCS’99). Cambridge, MA, USA: IASTED/ACTA Press; 1999. p. 955-62.; Aldinucci M, Danelutto M. Stream parallel skeleton optimization. In: Proceedings of the 11th IASTED international conference on parallel and distributed computing and systems (PDCS’99). Cambridge, MA, USA: IASTED/ACTA Press; 1999. p. 955-62.
[19] Aldinucci, M.; Gorlatch, S.; Lengauer, C.; Pelagatti, S., Towards parallel programming by transformation: the fan skeleton framework, Parallel Algorithms and Applications, 16, 2-3, 87-122 (2001) · Zbl 1021.68026
[20] Gorlatch, S.; Lengauer, C.; Wedler, C., Optimization rules for programming with collective operations, (Proceedings of the 13th international parallel processing symposium & 10th symposium on parallel and distributed processing (IPPS/SPDP’99) (1999), IEEE Computer Society Press: IEEE Computer Society Press Silver Spring, MD), 492-499
[21] Aldinucci, M., Automatic program transformation: the meta tool for skeleton-based languages, (Gorlatch, S.; Lengauer, C., Constructive methods for parallel programming, advances in computation: theory and practice (2002), Nova Science Publishers: Nova Science Publishers NY, USA), 59-78, [chapter 5] · Zbl 1089.68528
[22] Cole, M.; Hayashi, Y., Static performance prediction of skeletal programs, Parallel Algorithms and Applications, 17, 1, 59-84 (2002) · Zbl 0999.68040
[23] Skillicorn, D. B.; Cai, W., A cost calculus for parallel functional programming, Journal of Parallel and Distributed Computing, 28, 65-83 (1995) · Zbl 0833.68021
[24] Fradet, P.; Mallet, J., Compilation of a specialized functional language for massively parallel computers, Journal of Functional Programming, 10, 6, 561-605 (2000) · Zbl 0976.68038
[25] Aldinucci, M.; Danelutto, M.; Teti, P., An advanced environment supporting structured parallel programming in Java, Future Generation Computer Systems, 19, 5, 611-626 (2003)
[26] Aldinucci, M.; Danelutto, M.; Dünnweber, J.; Gorlatch, S., Optimization techniques for skeletons on grid, (Grandinetti, L., Grid computing and new frontiers of high performance processing. Advances in parallel computing, vol. 14 (2005), Elsevier: Elsevier Amsterdam)
[27] Backus J. Can programming be liberated from the von Neumann style? A functional programming style and its algebra of programs, Communications of the ACM 1978; 21(8):613-41.; Backus J. Can programming be liberated from the von Neumann style? A functional programming style and its algebra of programs, Communications of the ACM 1978; 21(8):613-41. · Zbl 0383.68013
[28] Vanneschi, M., The programming model of ASSIST, an environment for parallel and distributed portable applications, Parallel Computing, 28, 12, 1709-1732 (2002) · Zbl 1043.68047
[29] Aldinucci M, Coppola M, Danelutto M, Vanneschi M, Zoccolo C. ASSIST as a research framework for high-performance Grid programming environments. In: Cunha JC, Rana OF, editors. Grid computing: software environments and tools. Berlin: Springer; 2007. p. 230-56 [Chapter 10].; Aldinucci M, Coppola M, Danelutto M, Vanneschi M, Zoccolo C. ASSIST as a research framework for high-performance Grid programming environments. In: Cunha JC, Rana OF, editors. Grid computing: software environments and tools. Berlin: Springer; 2007. p. 230-56 [Chapter 10].
[30] Darlington J, To HW. Building parallel applications without programming. In: Leeds workshop on abstract parallel machine models; 1993.; Darlington J, To HW. Building parallel applications without programming. In: Leeds workshop on abstract parallel machine models; 1993.
[31] Darlington J, Field AJ, Harrison PG, Kelly PHJ, Sharp DWN, While RL, et al. Parallel programming using skeleton functions. In: Bode A, Reeve M, Wolf G, editors. Proceedings of the parallel architectures and languages Europe. Lecture notes in computer science, vol. 694. Berlin: Springer; 1993.; Darlington J, Field AJ, Harrison PG, Kelly PHJ, Sharp DWN, While RL, et al. Parallel programming using skeleton functions. In: Bode A, Reeve M, Wolf G, editors. Proceedings of the parallel architectures and languages Europe. Lecture notes in computer science, vol. 694. Berlin: Springer; 1993.
[32] MacDonald S, Szafron D, Schaeffer J, Bromling S. Generating parallel program frameworks from parallel design patterns. In: Bode A, Ludwing T, Karl W, Wismüller R, editors. Proceedings of Euro-Par 2000. Lecture notes in computer science, vol. 1900. Berlin: Springer; 2000, p. 95-105.; MacDonald S, Szafron D, Schaeffer J, Bromling S. Generating parallel program frameworks from parallel design patterns. In: Bode A, Ludwing T, Karl W, Wismüller R, editors. Proceedings of Euro-Par 2000. Lecture notes in computer science, vol. 1900. Berlin: Springer; 2000, p. 95-105.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.