http://www.dagstuhl.de/13471

November 17 – 22 , 2013, Dagstuhl Seminar 13471

Synchronous Programming

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)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 3, Issue 11 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule [pdf]

(Use seminar number and access code to log in)

Summary

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. \/p>

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.

License
  Creative Commons BY 3.0 Unported license
  Stephen A. Edwards and Alain Girault and Klaus Schneider

Dagstuhl Seminar Series

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground 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.

NSF young researcher support