{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T07:14:21Z","timestamp":1773126861745,"version":"3.50.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007514","name":"Universit\u00e0 di Pisa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007514","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper discusses the impact of structured parallel programming methodologies in state-of-the-art industrial and research parallel programming frameworks. We first recap the main ideas underpinning structured parallel programming models and then present the concepts of algorithmic skeletons and parallel design patterns. We then discuss how such concepts have permeated the wider parallel programming community. Finally, we give our personal overview\u2014as researchers active for more than two decades in the parallel programming models and frameworks area\u2014of the process that led to the adoption of these concepts in state-of-the-art industrial and research parallel programming frameworks, and the perspectives they open in relation to the exploitation of forthcoming massively-parallel (both general and special-purpose) architectures.<\/jats:p>","DOI":"10.1007\/s10766-020-00684-w","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T18:04:52Z","timestamp":1604945092000},"page":"177-198","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Algorithmic Skeletons and Parallel Design Patterns in Mainstream Parallel Programming"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7433-376X","authenticated-orcid":false,"given":"Marco","family":"Danelutto","sequence":"first","affiliation":[]},{"given":"Gabriele","family":"Mencagli","sequence":"additional","affiliation":[]},{"given":"Massimo","family":"Torquati","sequence":"additional","affiliation":[]},{"given":"Horacio","family":"Gonz\u00e1lez\u2013V\u00e9lez","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Kilpatrick","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,9]]},"reference":[{"issue":"6","key":"684_CR1","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1007\/s10766-013-0273-6","volume":"42","author":"M Aldinucci","year":"2014","unstructured":"Aldinucci, M., Campa, S., Danelutto, M., Kilpatrick, P., Torquati, M.: Design patterns percolating to parallel programming framework implementation. Int. J. Parallel Program. 42(6), 1012\u20131031 (2014)","journal-title":"Int. J. Parallel Program."},{"key":"684_CR2","doi-asserted-by":"publisher","first-page":"102584","DOI":"10.1016\/j.parco.2019.102584","volume":"91","author":"V Amaral","year":"2020","unstructured":"Amaral, V., et al.: Programming languages for data-Intensive HPC applications: a systematic mapping study. Parallel Comput. 91, 102584 (2020)","journal-title":"Parallel Comput."},{"issue":"10","key":"684_CR3","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/1562764.1562783","volume":"52","author":"K Asanovic","year":"2009","unstructured":"Asanovic, K., et al.: A view of the parallel computing landscape. Commun. ACM 52(10), 56\u201367 (2009)","journal-title":"Commun. ACM"},{"issue":"5","key":"684_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/MM.2011.67","volume":"31","author":"S Benkner","year":"2011","unstructured":"Benkner, S., et al.: PEPPHER: Efficient and productive usage of hybrid computing systems. IEEE Micro 31(5), 28\u201341 (2011)","journal-title":"IEEE Micro"},{"key":"684_CR5","volume-title":"Constructive Methods in Computing Science, volume\u00a055 of NATO ASI Series. F: Computer and Systems Sciences","author":"RS Bird","year":"1989","unstructured":"Bird, R.S.: Lectures on constructive functional programming. In: Broy, M. (ed.) Constructive Methods in Computing Science, volume\u00a055 of NATO ASI Series. F: Computer and Systems Sciences. Springer, Berlin (1989)"},{"issue":"1","key":"684_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0304-3975(97)00196-5","volume":"196","author":"GH Botorog","year":"1998","unstructured":"Botorog, G.H., Kuchen, H.: Efficient high-level parallel programming. Theor. Comput. Sci. 196(1), 71\u2013107 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"684_CR7","unstructured":"Bromling, S., MacDonald, S., Anvik, J., Schaeffer, J., Szafron, D., Tan, K.: Pattern-Based Parallel Programming. In: ICPP \u201902. IEEE Computer Society, Washington, pp. 257\u2013 (2002)"},{"key":"684_CR8","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.future.2013.12.038","volume":"37","author":"S Campa","year":"2014","unstructured":"Campa, S., Danelutto, M., Goli, M., Gonz\u00e1lez-V\u00e9lez, H., Popescu, A.M., Torquati, M.: Parallel patterns for heterogeneous CPU\/GPU architectures: structured parallelism from cluster to cloud. Future Gener. Comput. Syst. 37, 354\u2013366 (2014)","journal-title":"Future Gener. Comput. Syst."},{"key":"684_CR9","volume-title":"Parallel Programming with Microsoft .NET: Design Patterns for Decomposition and Coordination on Multicore Architectures","author":"C Campbell","year":"2010","unstructured":"Campbell, C., Johnson, R., Miller, A., Toub, S.: Parallel Programming with Microsoft.NET: Design Patterns for Decomposition and Coordination on Multicore Architectures, 1st edn. Microsoft Press, Redmond (2010)","edition":"1"},{"key":"684_CR10","volume-title":"A Parallel Programming with Microsoft Visual C++: Design Patterns for Decomposition and Coordination on Multicore Architectures","author":"C Campbell","year":"2011","unstructured":"Campbell, C., Miller, A.: A Parallel Programming with Microsoft Visual C++: Design Patterns for Decomposition and Coordination on Multicore Architectures, 1st edn. Microsoft Press, Redmond (2011)","edition":"1"},{"issue":"6","key":"684_CR11","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/1809028.1806638","volume":"45","author":"C Chambers","year":"2010","unstructured":"Chambers, C., et al.: FlumeJava: easy, efficient data-parallel pipelines. SIGPLAN Not. 45(6), 363\u2013375 (2010)","journal-title":"SIGPLAN Not."},{"key":"684_CR12","doi-asserted-by":"crossref","unstructured":"Chis, A.E., Gonz\u00e1lez-V\u00e9lez, H.: Design patterns and algorithmic skeletons: a brief concordance. In: Ko\u0142odziej, J., Pop, F., Dobre, C. (eds.) Modeling and Simulation in HPC and Cloud Systems, Number 36 in Studies in Big Data, pp. 45\u201356. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-73767-6_3"},{"key":"684_CR13","volume-title":"Algorithmic Skeletons: Structured Management of Parallel Computation. Research Monographs in Parallel and Distributed Computing","author":"M Cole","year":"1991","unstructured":"Cole, M.: Algorithmic Skeletons: Structured Management of Parallel Computation. Research Monographs in Parallel and Distributed Computing. MIT Press, Cambridge (1991)"},{"issue":"3","key":"684_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.parco.2003.12.002","volume":"30","author":"M Cole","year":"2004","unstructured":"Cole, M.: Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming. Parallel Comput. 30(3), 389\u2013406 (2004)","journal-title":"Parallel Comput."},{"key":"684_CR15","unstructured":"Danelutto, M.: QoS in parallel programming through application managers. In: PDP 2005, pp. 282\u2013289. IEEE Computer Society, Lugano (2005)"},{"issue":"1\u20133","key":"684_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0167-739X(92)90040-I","volume":"8","author":"M Danelutto","year":"1992","unstructured":"Danelutto, M., Di Meglio, R., Orlando, S., Pelagatti, S., Vanneschi, M.: A methodology for the development and the support of massively parallel programs. Future Gener. Comput. Syst. 8(1\u20133), 205\u2013220 (1992)","journal-title":"Future Gener. Comput. Syst."},{"key":"684_CR17","doi-asserted-by":"crossref","unstructured":"Danelutto, M., Teti, P.: Lithium: A structured parallel programming environment in Java. In: ICCS \u201902, pp. 844\u2013853. Springer, London (2002)","DOI":"10.1007\/3-540-46080-2_89"},{"key":"684_CR18","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-3-319-15940-9_2","volume-title":"Central European Functional Programming School, volume 8606 of LNCS","author":"M Danelutto","year":"2015","unstructured":"Danelutto, M.: Structured parallel programming with \u201ccore\u201d FastFlow. In: Zs\u00f3k, V., Horv\u00e1th, Z., Csat\u00f3, L. (eds.) Central European Functional Programming School, volume 8606 of LNCS, pp. 29\u201375. Springer, Berlin (2015)"},{"key":"684_CR19","doi-asserted-by":"crossref","unstructured":"Darlington, J., Guo, Y., To, H.W., Yang, J.: Parallel skeletons for structured composition. In: PPoPP\u201995, pp. 19\u201328. ACM, Santa Barbara (1995)","DOI":"10.1145\/209936.209940"},{"issue":"4","key":"684_CR20","first-page":"33:1","volume":"14","author":"D De\u00a0Sensi","year":"2017","unstructured":"De\u00a0Sensi, D., De\u00a0Matteis, T., Torquati, M., Mencagli, G., Danelutto, M.: Bringing parallel patterns out of the corner: the P$$^{3}$$ARSEC benchmark suite. ACM Trans. Archit. Code Optim. 14(4), 33:1\u201333:26 (2017)","journal-title":"ACM Trans. Archit. Code Optim."},{"issue":"1","key":"684_CR21","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1145\/1629175.1629198","volume":"53","author":"J Dean","year":"2010","unstructured":"Dean, J., Ghemawat, S.: MapReduce: A flexible data processing tool. Commun. ACM 53(1), 72\u201377 (2010)","journal-title":"Commun. ACM"},{"issue":"24","key":"684_CR22","doi-asserted-by":"publisher","first-page":"e4175","DOI":"10.1002\/cpe.4175","volume":"29","author":"D del Rio Astorga","year":"2017","unstructured":"del Rio Astorga, D., Dolz, M.F., Fern\u00e1ndez, J., Garc\u00eda, J.D.: A generic parallel pattern interface for stream and data processing. Concurr. Comput. Pract. Exp. 29(24), e4175 (2017)","journal-title":"Concurr. Comput. Pract. Exp."},{"issue":"8","key":"684_CR23","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1109\/TPDS.2011.308","volume":"23","author":"J Diaz","year":"2012","unstructured":"Diaz, J., Munoz-Caro, C., Nino, A.: A survey of parallel programming models and tools in the multi and many-core era. IEEE Trans. Parallel Distrib. Syst. 23(8), 1369\u20131386 (2012)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"4","key":"684_CR24","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/s10766-013-0263-8","volume":"42","author":"K Emoto","year":"2014","unstructured":"Emoto, K., Matsuzaki, K.: An automatic fusion mechanism for variable-length list skeletons in SkeTo. Int. J. Parallel Program. 42(4), 546\u2013563 (2014)","journal-title":"Int. J. Parallel Program."},{"key":"684_CR25","doi-asserted-by":"crossref","unstructured":"Enmyren, J., Kessler, C.W.: SkePU: A multi-backend skeleton programming library for multi-GPU systems. In: HLPP \u201910, pp. 5\u201314. ACM, Baltimore (2010)","DOI":"10.1145\/1863482.1863487"},{"issue":"2","key":"684_CR26","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1504\/IJHPCN.2012.046370","volume":"7","author":"S Ernsting","year":"2012","unstructured":"Ernsting, S., Kuchen, H.: Algorithmic skeletons for multi-core, multi-GPU systems and clusters. Int. J. High Perform. Comput. Netw 7(2), 129\u2013138 (2012)","journal-title":"Int. J. High Perform. Comput. Netw"},{"issue":"1","key":"684_CR27","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/s10766-017-0490-5","volume":"46","author":"A Ernstsson","year":"2018","unstructured":"Ernstsson, A., Li, L., Kessler, C.: SkePU 2: Flexible and type-safe skeleton programming for heterogeneous parallel systems. Int. J. Parallel Program. 46(1), 62\u201380 (2018)","journal-title":"Int. J. Parallel Program."},{"key":"684_CR28","doi-asserted-by":"crossref","unstructured":"Faraj, A., Yuan, X.: Automatic generation and tuning of MPI collective communication routines. In: ICS \u201905, pp. 393\u2013402. ACM, Cambridge (2005)","DOI":"10.1145\/1088149.1088202"},{"key":"684_CR29","unstructured":"FastFlow home page. http:\/\/calvados.di.unipi.it\/fastflow (2018). Accessed Apr 2020"},{"key":"684_CR30","volume-title":"Design Patterns: Elements of Reusable Object-Oriented Software","author":"E Gamma","year":"1995","unstructured":"Gamma, E., Helm, R., Johnson, R., Vlissides, J.: Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Longman Publishing Co., Inc, Boston (1995)"},{"key":"684_CR31","unstructured":"Gazzarri, L., Danelutto, M.: A tool to support FastFlow program design. In: ParCo 2017, pp. 687\u2013697. Bologna (2017)"},{"issue":"8","key":"684_CR32","doi-asserted-by":"publisher","first-page":"4026","DOI":"10.1007\/s11227-018-2448-9","volume":"75","author":"L Gazzarri","year":"2019","unstructured":"Gazzarri, L., Danelutto, M.: Supporting structured parallel program design, development and tuning in FastFlow. J. Supercomput. 75(8), 4026\u20134041 (2019)","journal-title":"J. Supercomput."},{"issue":"2","key":"684_CR33","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s10766-016-0419-4","volume":"45","author":"M Goli","year":"2017","unstructured":"Goli, M., Gonz\u00e1lez-V\u00e9lez, H.: Autonomic coordination of skeleton-based applications over CPU\/GPU multi-core architectures. Int. J. Parallel Programm. 45(2), 203\u2013224 (2017)","journal-title":"Int. J. Parallel Programm."},{"issue":"1","key":"684_CR34","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10766-017-0511-4","volume":"46","author":"M Goli","year":"2018","unstructured":"Goli, M., Gonz\u00e1lez-V\u00e9lez, H.: Formalised composition and interaction for heterogeneous structured parallelism. Int. J. Parallel Program. 46(1), 120\u2013151 (2018)","journal-title":"Int. J. Parallel Program."},{"issue":"12","key":"684_CR35","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1002\/spe.1026","volume":"40","author":"H Gonz\u00e1lez-V\u00e9lez","year":"2010","unstructured":"Gonz\u00e1lez-V\u00e9lez, H., Leyton, M.: A survey of algorithmic skeleton frameworks: high-level structured parallel programming enablers. Softw. Pract. Exp. 40(12), 1135\u20131160 (2010)","journal-title":"Softw. Pract. Exp."},{"key":"684_CR36","doi-asserted-by":"crossref","unstructured":"Gorlatch, S.: Systematic efficient parallelization of scan and other list homomorphisms. In: Euro-Par, Vol. II, volume 1124 of Lecture Notes in Computer Science, pp. 401\u2013408. Springer (1996)","DOI":"10.1007\/BFb0024729"},{"key":"684_CR37","doi-asserted-by":"crossref","unstructured":"Hammond, K et al.: The paraphrase project: parallel patterns for adaptive heterogeneous multicore systems. In: FMCO 2011 (Revised Selected Papers), volume 7542 of Lecture Notes in Computer Science, pp. 218\u2013236. Springer, Turin (2011)","DOI":"10.1007\/978-3-642-35887-6_12"},{"key":"684_CR38","doi-asserted-by":"crossref","unstructured":"Javed N, Loulergue, F.: A formal programming model of Orl\u00e9ans skeleton library. In: PaCT\u201911, pp. 40\u201352. Springer, Kazan (2011)","DOI":"10.1007\/978-3-642-23178-0_4"},{"issue":"9","key":"684_CR39","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/3154484","volume":"61","author":"NP Jouppi","year":"2018","unstructured":"Jouppi, N.P., Young, C., Patil, N., Patterson, D.: A domain-specific architecture for deep neural networks. Commun. ACM 61(9), 50\u201359 (2018)","journal-title":"Commun. ACM"},{"key":"684_CR40","doi-asserted-by":"crossref","unstructured":"Korinth, J., de\u00a0la Chevallerie, D., Koch, A.: An open-source tool flow for the composition of reconfigurable hardware thread pool architectures. In: FCCM 2015, pp. 195\u2013198. IEEE Computer Society, Vancouver (2015)","DOI":"10.1109\/FCCM.2015.22"},{"key":"684_CR41","unstructured":"Lee, J., Samadi, M., Park, Y., Mahlke, S.: Transparent CPU-GPU collaboration for data-parallel kernels on heterogeneous systems. In: PACT \u201913, pp. 245\u2013256. IEEE Press, Edinburgh (2013)"},{"key":"684_CR42","volume-title":"Patterns for Parallel Programming","author":"T Mattson","year":"2004","unstructured":"Mattson, T., Sanders, B., Massingill, B.: Patterns for Parallel Programming, 1st edn. Addison-Wesley Professional, Boston (2004)","edition":"1"},{"key":"684_CR43","volume-title":"Structured Parallel Programming: Patterns for Efficient Computation","author":"M McCool","year":"2012","unstructured":"McCool, M., Reinders, J., Robison, A.: Structured Parallel Programming: Patterns for Efficient Computation, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (2012)","edition":"1"},{"key":"684_CR44","unstructured":"Paraformance home page. https:\/\/www.paraformance.com\/ (2018). Accessed Jan 2019"},{"key":"684_CR45","volume-title":"Structured Development of Parallel Programs","author":"S Pelagatti","year":"1998","unstructured":"Pelagatti, S.: Structured Development of Parallel Programs. Taylor & Francis, Inc., Bristol (1998)"},{"key":"684_CR46","doi-asserted-by":"crossref","unstructured":"Prabhakar, R et al.: Generating configurable hardware from parallel patterns. In: ASPLOS \u201916, pp. 651\u2013665. ACM, Atlanta (2016)","DOI":"10.1145\/2980024.2872415"},{"key":"684_CR47","volume-title":"Intel Threading Building Blocks","author":"J Reinders","year":"2007","unstructured":"Reinders, J.: Intel Threading Building Blocks, 1st edn. O\u2019Reilly & Associates, Inc., Sebastopol (2007)","edition":"1"},{"key":"684_CR48","doi-asserted-by":"crossref","unstructured":"Serban, T., Danelutto, M., Kilpatrick, P.: Autonomic scheduling of tasks from data parallel patterns to CPU\/GPU core mixes. In: HPCS 2013, pp. 72\u201379. Helsinki (2013)","DOI":"10.1109\/HPCSim.2013.6641395"},{"issue":"12","key":"684_CR49","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1016\/S0167-8191(02)00189-8","volume":"28","author":"J S\u00e9rot","year":"2002","unstructured":"S\u00e9rot, J., Ginhac, D.: Skeletons for parallel image processing: an overview of the SKIPPER project. Parallel Comput. 28(12), 1685\u20131708 (2002)","journal-title":"Parallel Comput."},{"key":"684_CR50","unstructured":"Spark Streaming home page. https:\/\/spark.apache.org\/streaming\/ (2019). Accessed Jan 2020"},{"key":"684_CR51","unstructured":"Streamit home page. http:\/\/groups.csail.mit.edu\/cag\/streamit\/ (2016). Accessed Jan 2019"},{"key":"684_CR52","doi-asserted-by":"crossref","unstructured":"Wienke, S., Springer, P.L.: Christian terboven, and dieter an\u00a0Mey. OpenACC\u2014first experiences with real-world applications. In: Euro-Par 2012, volume 7484 of LNCS, pp. 859\u2013870. Rhodes Island. Springer (2012)","DOI":"10.1007\/978-3-642-32820-6_85"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-020-00684-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10766-020-00684-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-020-00684-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T22:12:45Z","timestamp":1697062365000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10766-020-00684-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,9]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["684"],"URL":"https:\/\/doi.org\/10.1007\/s10766-020-00684-w","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,9]]},"assertion":[{"value":"13 August 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}