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
Publication statusPublished - 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. Type-driven verification of non-functional properties

    Brown, C. M., Barwell, A. D., Marquer, Y., Minh, C. & Zendra, O., 7 Oct 2019, 21st International Symposium on Principles and Practice of Declarative Programming (PPDP 2019). New York: ACM, 15 p. 6

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

  2. Refactoring for introducing and tuning parallelism for heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C., Barwell, A. & Hammond, K., 24 Jun 2019, In : Concurrency and Computation : Practice and Experience. Early View, p. 1-25 25 p., e5420.

    Research output: Contribution to journalArticle

  3. High-level programming for heterogeneous and hierarchical parallel systems

    García-Blas, J. & Brown, C., 14 Nov 2018, In : International Journal of High Performance Computing Applications. 32, 6, p. 804-806

    Research output: Contribution to journalSpecial issue

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

ID: 248130167

Top