Dagstuhl Seminar 13471
Synchronous Programming
( Nov 17 – Nov 22, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13471
Organizers
- Albert Benveniste (INRIA Rennes - Bretagne Atlantique, FR)
- Stephen A. Edwards (Columbia University - New York, US)
- Alain Girault (INRIA - Grenoble, FR)
- Klaus Schneider (TU Kaiserslautern, DE)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Synchronous languages have been designed for the unambiguous description of reactive real-time systems. Their key innovation is a clever abstraction from physical time to logical time, which allows programmers to separate the functional behavior from the real-time constraints of their programs. To this end, the execution of a synchronous program is divided into discrete reaction steps that correspond to the interaction of the reactive system with its environment. In every reaction step, new input values are read by the system and new output values are immediately computed as the reaction of the synchronous program. In the programmer's view, the computations of a reaction step are thereby performed in "zero time". This simplifies greatly the temporal reasonings, by providing ideal temporal primitives and deterministic semantics.
The use of synchronous languages in model-driven engineering has many advantages: For example, the parallel composition of synchronous programs that are triggered by the same clock is deterministic. For this reason, it is possible to replay once observed phenomena in simulation, and to avoid so-called Heisenbugs (when added code for testing changes the behavior of the system under test). Moreover, once hardware architectures are determined, the physical execution time of reaction steps can be estimated since, by construction of the languages, it is guaranteed that there are no data dependent loops within a reaction. Finally, due to precisely formulated semantics, all synchronous languages lend themselves well for formal analysis, in particular, formal verification. For all of these reasons, almost all digital hardware circuits are designed as synchronous circuits, and synchronous programming languages transfer these benefits to the software and hardware/software co-design.
However, the continuously growing complexity of applications pose new challenges, such as the de-synchronization of synchronous designs to allow the synthesis of globally asynchronous locally synchronous (GALS) or distributed systems. Moreover, the sound integration of synchronous, polychronous, and asynchronous, event- and time-triggered, or discrete and continuous systems is still a major challenge that requires further research. Also, the optimized code generation for and the design of appropriate multithreaded processor architectures is of growing interest.
This seminar aims to address these challenges, building on a strong and active community and expanding its scope into relevant related fields. It is an edition of the Synchronous Programming (SYNCHRON) workshops that is the yearly meeting place for the researchers in this exciting field. The SYNCHRON workshops started in 1993 at Schloss Dagstuhl, and we are proud to celebrate the 20-th edition of the workshop from November 17-22, 2013 again in Dagstuhl. During its nineteen years of existence, the workshop has evolved significantly: its scope has grown to expand to many languages and techniques that are not classically synchronous, but have been substantially influenced by the synchronous languages' attention to timing, mathematical rigor, and parallelism. Also, while many of the most senior synchronous language researchers are still active, many younger researchers have also entered the fray and have taken the field in new directions.
As typical for Dagstuhl Seminars, SYNCHRON is also an open forum without program selection or review process. It welcomes an international audience of students and researchers to present their latest ongoing work on the large spectrum of topics including for example programming language semantics, models of computation and communication, concurrency and scheduling theory, domain-specific languages, design methodologies like model-driven engineering, modeling and simulation, verification/analysis and validation, hardware/software synthesis, cyber-physical systems, code generation, tools, projects, case studies, and engineering practice of applying synchronous programming.
Model-based Design of Embedded Systems
In general, the development of embedded systems is a challenging task: Concerning the hardware platforms, developers have to cope with tight resource constraints, heterogeneous and application-specific hardware architectures, virtual prototypes, and many other difficulties during the design phases. Concerning the software side, several concurrent tasks are executed on the available hardware, either with or without the help of special operating systems, sometimes statically or dynamically scheduled to the available hardware platforms, and sometimes tightly coupled with the hardware platforms themselves (implementing memory barriers etc). Finally, many non-functional aspects have to be considered as well like the energy consumption, the reliability, and most important the prediction of the worst-case computation times. As many embedded systems are real-time systems, it is not sufficient to perform the right computations; in addition, the results have to be available at the right point of time to achieve the desired functionality. Besides, the direct interaction with other systems that often have a continuous behavior requires to consider cyber-physical systems. Since many embedded systems are used in safety-critical applications, incorrect or delayed behaviors are unacceptable, so that formal verification is often applied. Since, moreover, the development costs have to be minimized, new design flows that allow the development of safe and flexible embedded systems are of high interest.
For these reasons, model-based design flows became popular where one starts with an abstract model of the embedded system. Many languages are discussed for such model-based approaches, but most of them are based on only a few models of computation. A model of computation thereby defines which, when and why an action of the system takes place taking into account the timeliness, the causality, and the concurrency of the computations. Classic models of computation are dataflow process networks, where computations can take place as soon as sufficient input data is available, synchronous systems, which are triggered by clocks, discrete-event based systems, where each process is sensitive to the occurrence of a set of certain events, and cyber-physical systems whose behavior consists of discrete and continuous transitions (the latter are determined by differential equations).
It is not surprising that all models of computation have their advantages and disadvantages. For example, dataflow process networks can be naturally mapped to distributed systems and have a robust form of asynchronous concurrency provided that the nodes implement continuous functions (as required for Kahn networks). Synchronous systems are the perfect choice for implementing deterministic systems with predictable real-time behaviors on platforms having a local control (like clocks in digital hardware circuits). Discrete-event based systems are ideal for efficiently simulating systems, since the events directly trigger the next actions.
Many years of research were necessary to understand the above mentioned models of computation in depth to be able to develop corresponding programming languages, compilers and verification techniques. The synchronous programming community made substantial progress in this area: Today, the synchronous programming languages have precise formal semantics which are supported by efficient compiler techniques. Moreover, synchronous languages provide high-level descriptions of real-time embedded systems so that all relevant requirements for a model-based design flow are fulfilled. There are also graphical versions of these textual languages, notably Safe State Machines (developed from Argos and SyncCharts), and there are commercial versions like SCADE. The SCADE tool provides a code generator certified against DO 178-B, which makes it particularly attractive for the aircraft sector.
Quoting Benveniste et al.: Today, synchronous languages have been established as a technology of choice for modeling, specifying, validating, and implementing real-time embedded applications. The paradigm of synchrony has emerged as an engineer-friendly design method based on mathematically sound tools [Proceedings of the IEEE, January 2003].
Open Problems
Despite the incredible progress made in the past, even the combination of the classic synchronous languages Esterel, Lustre, and Signal is not yet fully understood. All these languages are based on the abstraction of physical time to a logical time, where each logical step of time may consist of finitely many executions of actions that are - at least in the programming model - executed in zero time. Such a logical step of the computation matches naturally with an interaction of a reactive system with its environment. However, looking at the details, one can observe that the semantics differ: for example, Lustre and Signal are not based on a single clock like Esterel, and while Esterel's and Lustre's semantics are operational and can therefore be defined by least fixpoints, Signal is rather declarative and requires a more complicated analysis before code generation.
Since different models of computation have different advantages and disadvantages, their combination becomes more and more important. This does also imply the translation and communication between models of computations. For example, so-called globally asynchronous, locally synchronous (GALS) systems have been developed, mixing both asynchronous and synchronous computations. For model-based designs starting from synchronous languages, special forms of synchronous systems have been defined in terms of the (weakly) endochronous systems. Intuitively, endochronous systems are synchronous systems that can determine from which input ports the values are expected for the next reaction step (and therefore they can derive the absence of other inputs, and they do not need the explicit knowledge of absence). For this reason, one can integrate endochronous systems in an asynchronous environment without destroying their synchronous behaviors.
Similar techniques are used for generating distributed systems from high-level descriptions (like synchronous programs) which lead, e.g., also to first approaches to multithreaded code generation from synchronous languages, which becomes more important due to the advent of multicore processors in embedded system design. More progress is needed and will likely be available in the near future in combining these different forms of discrete models of computations.
The combination of synchronous, endochronous, or asynchronous discrete systems with continuous behaviors to describe cyber-physical systems is still in its infancies. Of course, there are many languages for modeling, simulating, and even formally verifying these systems, but most of these languages lack of a formal semantics, and essentially none of them lends itself for a model-based design like synchronous languages. The generalization of the concepts of synchronous systems to polychronous systems, and even further to cyber-physical systems will be a challenge for future research.
Results of the Seminar
The major goal of the seminar was therefore to allow researchers and practitioners in the field of models of computation and model-based design to discuss their different approaches. Desired results are new combinations of these techniques to form new language concepts and design flows that are able to choose the best suited language for particular components and that allow engineers the sound integration of synchronous and asynchronous, discrete and continuous, or event- and time-triggered systems. Besides this, still more research is required for further developing compilation techniques for future manycore processors, and even to develop special processors like the PRET architectures to obtain better estimated time bounds for the execution of programs.
The seminar proposed here aims ar addressing all of these questions, building on a strong and active community and expanding its scope into relevant related fields, by inviting researchers prominent in model-based design, embedded real-time systems, mixed system modeling, models of computation, and distributed systems. The seminar was held in the tradition of the Synchronous Programming (SYNCHRON) workshops that are used as the yearly meeting place for the community in this exciting field. The SYNCHRON workshops started in 1994 at Schloss Dagstuhl, and we were proud to celebrate the 20th edition of the workshop from November 18-22, 2013 again in Schloss Dagstuhl. Previous editions of the SYNCHRON workshop were organized at the following locations:
- 2012: Le Croisic, France - http://synchron2012.inria.fr
- 2011: Dammarie-les-Lys - http://synchron2011.di.ens.fr
- 2010: Fréjus, France - http://www.artist-embedded.org/artist/Synchron-2010,2206.html
- 2009: Dagstuhl, Germany - http://www.dagstuhl.de/09481
- 2008: Aussois, France - http://synchron2008.lri.fr
- 2007: Bamberg, Germany
- 2006: L'Alpe d'Huez, France - http://www.inrialpes.fr/Synchron06/
- 2005: Qwara, Malta - http://www.cs.um.edu.mt/~synchrone05/
- 2004: Dagstuhl, Germany - http://www.dagstuhl.de/04491
- 2003: Luminy, France - http://www-verimag.imag.fr/PEOPLE/Nicolas.Halbwachs/SYNCHRON03/
- 2002: La Londe les Maures, France - http://www-sop.inria.fr/tick/Synchron2002.html
- 2001: Dagstuhl, Germany - http://www.dagstuhl.de/01491
- 2000: Saint-Nazaire, France
- 1999: Hyères, France - http://www-sop.inria.fr/meije/synchron99/location.htm
- 1998: Gandia, Spain
- 1997: Roscoff, France
- 1996: Dagstuhl, Germany - http://www.dagstuhl.de/9650
- 1995: Luminy, France
- 1994: Dagstuhl, Germany - http://www.dagstuhl.de/9448
During its 20 years of existence, the workshop has significantly evolved: its scope has grown to expand to many languages and techniques that are not classically synchronous, but have been substantially influenced by the synchronous languages' attention to timing, mathematical rigor, and parallelism. Also, while many of the most senior synchronous language researchers are still active, many younger researchers have also entered the fray and have taken the field in new directions. We carefully selected the potential persons to be invited in that senior and junior researchers of the different branches mentioned above will participate the seminar.
This year, we had 44 participants where 23 came from France, 10 from Germany, 5 from the USA, 2 from Sweden, 2 from UK, one from Portugal and one even from Australia. The seminar had 33 presentations of about 45 minutes length with very active discussions (See http://www.dagstuhl.de/schedules/13471.pdf for the schedule.). The presentations can be clustered in typical research areas around synchronous languages like
- synchronous and asynchronous models of computation
- hybrid systems
- causality and other program analyses
- compilation techniques
- predictable software and hardware architectures
It was a pleasure to see that the synchronous programming community is still very active in these research fields and that even after 20 years of research, there are still more and more interesting and fruitful results to be discovered. The following sections contains short abstracts of the presentations of the seminar, and further documents were provided by many participants on the seminar's webpage.
Creative Commons BY 3.0 Unported license
Stephen A. Edwards and Alain Girault and Klaus Schneider
- Joaquin Aguado (Universität Bamberg, DE) [dblp]
- Mihail Asavoae (VERIMAG - Grenoble, FR) [dblp]
- Yu Bai (TU Kaiserslautern, DE) [dblp]
- Fernando Barros (University of Coimbra, PT) [dblp]
- Sanjoy Baruah (University of North Carolina at Chapel Hill, US) [dblp]
- Guillaume Baudart (ENS - Paris, FR) [dblp]
- Vagelis Bebelis (INRIA - Grenoble, FR) [dblp]
- Gérard Berry (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Nicolas Berthier (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Timothy Bourke (ENS - Paris, FR & INRIA - Paris, FR) [dblp]
- David Broman (University of California - Berkeley, US) [dblp]
- Benoit Caillaud (INRIA Rennes - Bretagne Atlantique, FR) [dblp]
- Albert Cohen (ENS - Paris, FR) [dblp]
- Willem-Paul de Roever (Universität Kiel, DE) [dblp]
- Robert de Simone (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Gwenaël Delaval (University of Grenoble - LIG, FR) [dblp]
- Stephen A. Edwards (Columbia University - New York, US) [dblp]
- Peter A. Fritzson (Linköping University, SE) [dblp]
- Manuel Gesell (TU Kaiserslautern, DE) [dblp]
- Dan R. Ghica (University of Birmingham, GB) [dblp]
- Alain Girault (INRIA - Grenoble, FR) [dblp]
- Adrien Guatto (ENS - Paris, FR) [dblp]
- Nicolas Halbwachs (VERIMAG - Grenoble, FR) [dblp]
- Jun Inoue (ENS - Paris, FR) [dblp]
- Xian Li (TU Kaiserslautern, DE) [dblp]
- Gerald Lüttgen (Universität Bamberg, DE) [dblp]
- Antoine Madet (ENS - Paris, FR) [dblp]
- Frédéric Mallet (INRIA Sophia Antipolis - Méditerranée, FR) [dblp]
- Louis Mandel (College de France, Paris, FR) [dblp]
- Florence Maraninchi (VERIMAG - Grenoble, FR) [dblp]
- Eleftherios Matsikoudis (University of California - Berkeley, US) [dblp]
- Michael Mendler (Universität Bamberg, DE) [dblp]
- Christian Motika (Universität Kiel, DE) [dblp]
- Valentin Perrelle (IRT SystemX, FR) [dblp]
- John Plaice (UNSW - Sydney, AU) [dblp]
- Dumitru Potop-Butucaru (INRIA - Le Chesnay, FR) [dblp]
- Marc Pouzet (ENS - Paris, FR) [dblp]
- Pascal Raymond (VERIMAG - Grenoble, FR) [dblp]
- Ingo Sander (KTH Royal Institute of Technology, SE) [dblp]
- Klaus Schneider (TU Kaiserslautern, DE) [dblp]
- Alex Shafarenko (University of Hertfordshire, GB) [dblp]
- Chris Shaver (University of California - Berkeley, US) [dblp]
- Wei-Tsun Sun (INRIA - Grenoble, FR) [dblp]
- Reinhard von Hanxleden (Universität Kiel, DE) [dblp]
Related Seminars
- Dagstuhl Seminar 9448: Synchronous Languages (1994-11-28 - 1994-12-02) (Details)
- Dagstuhl Seminar 9650: Synchronous Languages (1996-12-09 - 1996-12-13) (Details)
- Dagstuhl Seminar 01491: Synchronous Languages (2001-12-02 - 2001-12-07) (Details)
- Dagstuhl Seminar 04491: Synchronous Programming - SYNCHRON'04 (2004-11-28 - 2004-12-03) (Details)
- Dagstuhl Seminar 09481: SYNCHRON 2009 (2009-11-22 - 2009-11-27) (Details)
Classification
- modelling / simulation
- programming languages / compiler
- semantics / formal methods
Keywords
- synchronous and asynchronous languages
- model-based design
- discrete and hybrid systems
- compilation and code synthesis for embedded systems
- execution time analysis
- safety-critical real-time systems
