Skip to content

Research at St Andrews

Farms, pipes, streams and reforestation: reasoning about structured parallel processes using types and hylomorphisms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The increasing importance of parallelism has motivated the creation of better abstractions for writing parallel software, including structured parallelism using nested algorithmic skeletons. Such approaches provide high-level abstractions that avoid common problems, such as race conditions, and often allow strong cost models to be defined. However, choosing a combination of algorithmic skeletons that yields good parallel speedups for a program on some specific parallel architecture remains a difficult task. In order to achieve this, it is necessary to simultaneously reason both about the costs of different parallel structures and about the semantic equivalences between them. This paper presents a new type-based mechanism that enables strong static reasoning about these properties. We exploit well-known properties of a very general recursion pattern, hylomorphisms, and give a denotational semantics for structured parallel processes in terms of these hylomorphisms. Using our approach, it is possible to determine formally whether it is possible to introduce a desired parallel structure into a program without altering its functional behaviour, and also to choose a version of that parallel structure that minimises some given cost model.
Close

Details

Original languageEnglish
Title of host publicationProceedings of the 21st ACM SIGPLAN International Conference on Functional Programming
Place of PublicationNew York
PublisherACM
Pages4-17
ISBN (Print)9781450342193
DOIs
StatePublished - 4 Sep 2016
EventICFP 2016 - 21st ACM SIGPLAN International Conference on Functional Programming - Nara Kasugano International Forum, Nara, Japan
Duration: 18 Sep 201624 Sep 2016
http://conf.researchr.org/home/icfp-2016

Conference

ConferenceICFP 2016 - 21st ACM SIGPLAN International Conference on Functional Programming
CountryJapan
CityNara
Period18/09/1624/09/16
Internet address

    Research areas

  • Parallelism, Type-systems, Hylomorphisms, Term rewriting systems

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y. Feb 2018 In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. Timing properties and correctness for structured parallel programs on x86-64 multicores

    Hammond, K., Brown, C. M. & Sarkar, S. 2016 Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. van Eekelen, M. & Dal Lago, U. (eds.). Springer, p. 101-125 26 p. (Lecture Notes in Computer Science; vol. 9964)

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Memory consistency models using constraints

    Akgün, Ö., Hoffmann, R. & Sarkar, S. 27 Aug 2018 The Seventeenth Workshop on Constraint Modelling and Reformulation (ModRef 2018), Proceedings. 16 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V. Feb 2018 In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

ID: 243004874