Skip to content

Research at St Andrews

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

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

Abstract

This paper determines correctness and timing properties for structured parallel programs on x86-64 multicores. Multicore architectures are increasingly common, but real architectures have unpredictable timing properties, and even
correctness is not obvious above the relaxed-memory concurrency models
that are enforced by commonly-used hardware. This paper takes a rigorous approach to correctness and timing properties, examining common locking protocols from first principles, and extending this through queues to structured parallel constructs. We prove functional correctness and derive simple timing models, and both extend for the first time from low-level primitives to high-level parallel patterns. Our derived high-level timing models for structured parallel programs allow us to accurately predict upper bounds on program
execution times on x86-64 multicores.

Close

Details

Original languageEnglish
Title of host publicationFoundational and Practical Aspects of Resource Analysis
Subtitle of host publication4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers
EditorsMarko van Eekelen, Ugo Dal Lago
PublisherSpringer
Pages101-125
Number of pages26
ISBN (Electronic)9783319465593
ISBN (Print)9783319465586
DOIs
StatePublished - 2016
Event4th International Workshop, Foundational and Practical Aspects of Resource Analysis (FOPARA 2015) - London, United Kingdom
Duration: 11 Apr 201511 Apr 2015
Conference number: 4
http://resourceanalysis.cs.ru.nl/fopara/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9964
ISSN (Print)0302-9743

Workshop

Workshop4th International Workshop, Foundational and Practical Aspects of Resource Analysis (FOPARA 2015)
Abbreviated titleFOPARA
CountryUnited Kingdom
CityLondon
Period11/04/1511/04/15
Internet address

    Research areas

  • Multicore, Relaxed-memory concurrency, Functional correctness, Algorithmic skeletons, Operational semantics, Timing models

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

  3. Towards semi-automatic data-type translation for parallelism in Erlang

    Barwell, A. D., Brown, C. M., Castro, D. & Hammond, K. 23 Sep 2016 Proceedings of the 15th International Workshop on Erlang. New York: ACM, p. 60-61

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

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

ID: 248130167