Skip to content

Research at St Andrews

Automatically deriving cost models for structured parallel processes using hylomorphisms

Research output: Contribution to journalArticle


Structured parallelism using nested algorithmic skeletons can greatly ease the task of writing parallel software, since common, but hard-to-debug, problems such as race conditions are eliminated by design. However, choosing the best combination of algorithmic skeletons to yield good parallel speedups for a specific program on a specific parallel architecture is still a difficult problem. This paper uses the unifying notion of hylomorphisms, a general recursion pattern, to make it possible to reason about both the functional correctness properties and the extra-functional timing properties of structured parallel programs. We have previously used hylomorphisms to provide a denotational semantics for skeletons, and proved that a given parallel structure for a program satisfies functional correctness. This paper expands on this theme, providing a simple operational semantics for algorithmic skeletons and a cost semantics that can be automatically derived from that operational semantics. We prove that both semantics are sound with respect to our previously defined denotational semantics. This means that we can now automatically and statically choose a provably optimal parallel structure for a given program with respect to a cost model for a (class of) parallel architecture. By deriving an automatic amortised analysis from our cost model, we can also accurately predict parallel runtimes and speedups.


Original languageEnglish
Pages (from-to)653-668
JournalFuture Generation Computer Systems
Issue numberPart 2
Early online date9 May 2017
StatePublished - Feb 2018

    Research areas

  • Operational semantics, Algorithmic skeletons, Cost models, Hylomorphisms

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

View graph of relations

Related by author

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

    Castro, D., Hammond, K. & Sarkar, S. 4 Sep 2016 Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming. New York: ACM, p. 4-17

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

  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

Related by journal

  1. High-Performance Computing in Chemistry; NWChem

    Guest, M. F., Apra, E., Bernholdt, D. E., Fruchtl, H. A., Harrison, R. J., Kendall, R. A., Kutteh, R. A., Long, X., Nicholas, J. B., Nichols, J. A., Taylor, H. L., Wong, A. T., Fann, G. I., Littlefield, R. J. & Nieplocha, J. Dec 1996 In : Future Generation Computer Systems. 12, 4, p. 273-289

    Research output: Contribution to journalArticle

ID: 249964983