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

Standard

Timing properties and correctness for structured parallel programs on x86-64 multicores. / Hammond, Kevin; Brown, Christopher Mark; Sarkar, Susmit.

Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. ed. / Marko van Eekelen; Ugo Dal Lago. Springer, 2016. p. 101-125 (Lecture Notes in Computer Science; Vol. 9964).

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

Harvard

Hammond, K, Brown, CM & Sarkar, S 2016, Timing properties and correctness for structured parallel programs on x86-64 multicores. in M van Eekelen & U Dal Lago (eds), Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. Lecture Notes in Computer Science, vol. 9964, Springer, pp. 101-125, 4th International Workshop, Foundational and Practical Aspects of Resource Analysis (FOPARA 2015), London, United Kingdom, 11/04/15. https://doi.org/10.1007/978-3-319-46559-3_6

APA

Hammond, K., Brown, C. M., & Sarkar, S. (2016). Timing properties and correctness for structured parallel programs on x86-64 multicores. In M. van Eekelen, & U. Dal Lago (Eds.), Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers (pp. 101-125). (Lecture Notes in Computer Science; Vol. 9964). Springer. https://doi.org/10.1007/978-3-319-46559-3_6

Vancouver

Hammond K, Brown CM, Sarkar S. Timing properties and correctness for structured parallel programs on x86-64 multicores. In van Eekelen M, Dal Lago U, editors, Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. Springer. 2016. p. 101-125. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-46559-3_6

Author

Hammond, Kevin ; Brown, Christopher Mark ; Sarkar, Susmit. / Timing properties and correctness for structured parallel programs on x86-64 multicores. Foundational and Practical Aspects of Resource Analysis: 4th International Workshop, FOPARA 2015, London, UK, April 11, 2015. Revised Selected Papers. editor / Marko van Eekelen ; Ugo Dal Lago. Springer, 2016. pp. 101-125 (Lecture Notes in Computer Science).

Bibtex - Download

@inproceedings{6e70a1deb0e544e1a7885ceb09100b7f,
title = "Timing properties and correctness for structured parallel programs on x86-64 multicores",
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 evencorrectness is not obvious above the relaxed-memory concurrency modelsthat 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 programexecution times on x86-64 multicores.",
keywords = "Multicore, Relaxed-memory concurrency, Functional correctness, Algorithmic skeletons, Operational semantics, Timing models",
author = "Kevin Hammond and Brown, {Christopher Mark} and Susmit Sarkar",
year = "2016",
doi = "10.1007/978-3-319-46559-3_6",
language = "English",
isbn = "9783319465586",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "101--125",
editor = "{van Eekelen}, Marko and {Dal Lago}, Ugo",
booktitle = "Foundational and Practical Aspects of Resource Analysis",
address = "Netherlands",

}

RIS (suitable for import to EndNote) - Download

TY - GEN

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

AU - Hammond, Kevin

AU - Brown, Christopher Mark

AU - Sarkar, Susmit

PY - 2016

Y1 - 2016

N2 - 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 evencorrectness is not obvious above the relaxed-memory concurrency modelsthat 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 programexecution times on x86-64 multicores.

AB - 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 evencorrectness is not obvious above the relaxed-memory concurrency modelsthat 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 programexecution times on x86-64 multicores.

KW - Multicore

KW - Relaxed-memory concurrency

KW - Functional correctness

KW - Algorithmic skeletons

KW - Operational semantics

KW - Timing models

U2 - 10.1007/978-3-319-46559-3_6

DO - 10.1007/978-3-319-46559-3_6

M3 - Conference contribution

SN - 9783319465586

T3 - Lecture Notes in Computer Science

SP - 101

EP - 125

BT - Foundational and Practical Aspects of Resource Analysis

A2 - van Eekelen, Marko

A2 - Dal Lago, Ugo

PB - Springer

ER -

Related by author

  1. Reasoning about non-functional properties using compiler intrinsic function annotations

    Jadhav, S., Roth, M., Falk, H., Brown, C. M. & Barwell, A. D., 6 Nov 2019, Proceedings of the 13th Junior Researcher Workshop on Real-Time Computing. INP ENSEEIHT/IRIT, p. 25-28 4 p.

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

  2. Type-driven verification of non-functional properties

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

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

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

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

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