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

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

1 Citation (Scopus)
2 Downloads (Pure)

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.

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
Country/TerritoryUnited Kingdom
CityLondon
Period11/04/1511/04/15
Internet address

Keywords

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

Fingerprint

Dive into the research topics of 'Timing properties and correctness for structured parallel programs on x86-64 multicores'. Together they form a unique fingerprint.

Cite this