Skip to content

Research at St Andrews

Automatically deriving cost models for structured parallel processes using hylomorphisms

Research output: Contribution to journalArticle


David Castro, Kevin Hammond, Susmit Sarkar, Yasir Alguwaifli

School/Research organisations


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
Publication statusPublished - 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. 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

  2. Simplifying ARM concurrency: multicopy-atomic axiomatic and operational models for ARMv8

    Pulte, C., Flur, S., Deacon, W., French, J., Sarkar, S. & Sewell, P., Jan 2018, Proceedings of the ACM on Programming Languages (POPL '18). New York: ACM, Vol. 2 Issue POPL. 29 p. 19

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

  3. Verification of a lazy cache coherence protocol against a weak memory model

    Banks, C., Elver, M., Hoffmann, R., Sarkar, S., Jackson, P. & Nagarajan, V., 2 Oct 2017, Proceedings of the 17th Conference on Formal Methods in Computer-Aided Design (FMCAD). ACM, p. 60-67

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

  4. Mixed-size concurrency: ARM, POWER, C/C++11, and SC

    Flur, S., Sarkar, S., Pulte, C., Nienhuis, K., Maranget, L., Gray, K., Sezgin, A., Batty, M. & Sewell, P., 1 Jan 2017, Proceedings of the 44th annual ACM-SIGPLAN Symposium on Principles of programming languages. ACM, p. 429-442

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

  5. 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

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