http://www.dagstuhl.de/11011

January 3 – 7 , 2011, Dagstuhl Seminar 11011

Multi-Core Memory Models and Concurrency Theory

Organizers

Hans-J. Boehm (HP Labs – Palo Alto, US)
Ursula Goltz (TU Braunschweig, DE)
Holger Hermanns (Universitšt des Saarlandes, DE)
Peter Sewell (University of Cambridge, GB)


1 / 2 >

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 1, Issue 1 Dagstuhl Report
List of Participants
Shared Documents

Summary

The current and future trend to multi-core and many-core computing systems suggests that within the next decade, concurrent multi-threaded programming will replace sequential programming as the standard programming paradigm. However, concurrency and modern computer architecture do not go together easily:

  • Current programming language memory models are still incomplete. Mainstream languages such as Java increasingly promise sequential consistency for data-race-free programs. However,how data races can be handled in a way that supports reasonable performance, security, and debugability, is currently completely unknown.
  • Hardware specifications are so informal that it is very hard to know whether we have a correct implementation of the language specs (if we knew how to specify those fully). It is not clear that existing ISAs, which have a long history, are a good match for the language semantics we are developing. There is an argument that this misalignment continues to encourage languages to support complex low-level constructs.
  • The concurrent algorithms that are now being developed, and which are key to exploiting multiprocessors (via high-performance operating systems, hypervisor kernels, and concurrency libraries), are very subtle, so informal reasoning cannot give high confidence in their correctness.
  • While there is a rich literature on concurrency theory, and extensive prior work on software verification for concurrency software (including process calculi, model-checking, temporal logics, rely-guarantee reasoning, and separation logic), almost all of it assumes a global notion of time, unrealistic though that is for these systems and algorithms.

Concurrency theory has a long tradition in investigating the foundational principles of concurrent computation, devoted to parallelism and causality of operations. It has created a wealth of models and notions readily applicable in this semantic challenge. Recent developments in the research communities of programming languages and concurrency theory, respectively, indeed show a growing trend towards cross-fertilization.

This seminar has fostered cross-fertilization of different expertises that will help to develop novel practical and, at the same time, theoretically sound paradigms for multi-core programming. It brought together concurrency theorists, memory model experts, computer systems architects, compiler experts, and formal verification researchers. The aim of the seminar was to adress in particular:

  1. Survey of problem domain: state of the practice in multi-core-programming and state of the art in memory consistency models.
  2. Application of concurrency theory approaches to reveal underlying concepts of parallelism, reordering, causality, and consistency.
  3. Cross-fertilization across formal approaches to memory consistency models and semantics of multithreaded programming.
  4. Attack points for formal analysis and computer aided programmer support.

Many of the questions that stood at the outset of this seminar have not been conclusively answered, thus yielding many potentials for further investigation. However, what makes this seminar uniquely successful is that it initiated a vivid exchange between a multitude of different scientific and industrial communities. During the seminar, it became clear that the current and future challenges of multi-core programming and memory models design in software and hardware can only be solved if the communities continue to exchange ideas and will learn from each other.

Classification

  • Concurrent Computation
  • Programming Languages / Compiler
  • Formal Methods / Semantics

Keywords

  • Concurrency
  • Formal Methods
  • Memory Models
  • Multi-Core
  • Multithreading
  • Program Semantics
  • Shared Memory

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.