Research and Integration Activities for the "Real Time Components" cluster

Seeding New Research Directions in Real-Time Components
JPRA-NoE Integration

Abstract
One of the most exciting outcomes from former HRT cluster was the discovery of new challenges in embedded systems diagnosis and its cross-disciplinary nature. The working meetings that were held collected people that would not attend the same conferences and would not otherwise interact. For instance, for diagnosis, we gathered people with the following backgrounds: dependability, TT architectures, model checking and verification, control and signal processing, design methodology and tools, and statistics. The outcomes of the meeting were considered excellent by the participants. Thus, the new RTC cluster decided to devote part of its energy for the organization of the same type of activity in other topics.

Participants

The full list of participants is available here.

Baseline

Here we quote an interesting part of the progress report of the JPRA on Semantic Platform from the former HRT cluster. This quote clearly points to a number of fundamental issues that concern the RTC cluster. Our aim in this JPRA is to draw the novel research directions that will fundamentally contribute to solving the issues mentioned below.

A. Benveniste was invited to participate to the panel session at IEEE-Control and Decision Conference Dec. 2005: How do control system design engineers use models and simulation?
Organized by Pieter J. Mosterman, from The Mathworks. The text of this panel session says (quoted, specific sentences underlined by us):
  • In control system design, we typically model the plant in detail and then make the model amenable to control law synthesis. With this law at its core, the controller model is gradually refined with implementation detail. Physical models are combined with computational models to ensure we can realize the design. At present, computational
    modeling increasingly replaces physical modeling. This requires sophisticated modeling formalisms and tools. For example, in plant modeling, domain specific languages for, e.g., multi-body systems and image processing systems as well as extensive tool infrastructure, are needed. The challenges we face to further this trend are (i) providing
    domain-specific modeling formalisms, (ii) providing tool support, (iii) combining different formalisms, and (iv) automatic model translation. We discuss the role of models in control system design and address questions such as: Is there a set of sufficient semantic notions for our modeling languages or a general ‘computing API’ to combine
    different formalisms
    ? Is simulation a sufficiently powerful technology? What is the best approach to generating modeling formalisms (libraries, meta-modeling, API, other)? Is there an optimal formalism to translate between formalisms? Can we derive denotational or operational models from axiomatic specifications (i.e., generate models from ‘scenarios’)? How about producing target specific code? How can style guidelines
    be enforced and is there a need to configure tools for controller design? How about support for enterprise-wide modeling? Can model reduction techniques handle industrial models for control synthesis? How can you guarantee model composability? How can we obtain explicit models (e.g., hybrid automata) from models in a more practicable representation?

This text expresses very well concerns from industry. Note that these are specifically addressed by the HRT cluster and this JPRA.

Problem Tackled in Year 2

From the above quotation, we extract issues that merit investigation. The underlined text contains issues including:

- A) combining different formalisms,
- B) automatic model translation,
- C) semantic notions for modelling languages,
- D) producing target specific code,
- E) guaranteeing model composability,


which are a basis for the research agenda in this activity. The two issues just before the first underlined items ((i) providing domain-specific modeling formalisms, (ii) providing tool support) are considered in the activities Developmet of UML for Real-Time embedded Systems and
Platform for Component Modeling and Verification.

A noticeable outcome of the merge that was performed between the Hard-Real Time and Component communities was the discovery of the different points of view that were considered in these communities: though both communities heavily build upon model-based development,
the associated methodologies are quite different. Noticing these differences, trying to understand their rationales and trying to make them converge, was therefore a problem that seemed of interest and worth to investigate. Our work, input from industrials (see above), discussions, and findings, have come up with the following list of candidate issues for further investigations:

- Model-based Development in Computer and Control Sciences (item A) and B) above): is a topic spanning many issues, including
  • Metrics to assess “semantic preserving” in a quantitative way, not just as YES/NO; the traditional paradigm of “implementation meeting the specification” does not seem to be applied in practice, neither it seems reasonable or practical. In real life, engineers have rather a sense of what it means to be “reasonably conform to the specification”. Little theory exists in support of such intuition and industrial practice.
    While such theories are available for the design of continuous control systems, nothing exists for more general systems involving both continuous and discrete parts.
  • Components vs block-diagrams: software engineers tend to promote component based design, based on object oriented technologies, UML, MDA, etc. On the other hand, systems engineers in sectors such as automobile or aeronautics, tend to organize their designs around block-diagram formalisms inherited from control engineering. How to reconcile these seemingly incompatible philosophies?

- Models of Computation and Communication (MoCC) (item C) above): there is a need for a better understanding of these; there is a need for better high-level mathematical modelling of MoCCs; and there is a need for studies on some MoCCs corresponding to special architectures used (e.g., communication by sampling, a nonstandard mechanism – from the viewpoint of computer engineers – often used in distributed control systems).
- Techniqes for the software implementation of embedded systems (item D) above.
- Components and interfaces for non-functional aspects (item E) above: these are very hot topics in the academic community at the moment. Corresponding theories aim to be the basis for incremental design with correct-by-construction integration. In contrast, object oriented concepts such as inheritance have not found their counterpart yet regarding behaviours and non-functional aspects: what does it mean, in terms of
behaviours and non-functional aspects, to inherit from another component? The topic of component interfaces was a central issues for the former Modeling and Components cluster, and is continuously considered in the RTC cluster. Details on technical progress is reported in the RTC Cluster deliverable.

Previous Work

Since this is a new activity, we only summarize here the original plans, for reference.

This activity aims at reproducing more systematically the type of meeting and discussion forum the former HRT cluster held in Vienna and Grenoble, for the topic of Diagnosis. The minutes collected from this meeting were quite rich and useful for us in guiding our research activities in this particular topic (whether or not this will actually happen depends on available resources and is not related to the actual interest of these research suggestions). The work done in the JPRA on Diagnosis involved skills originating from communities not meeting at existing conferences (dependability, control and signal processing, statistics, verification). We think that this type of “trans-skills” prospective activity must be sustained by the academic community, and we believe that ARTIST2 is the adequate place to handle it.

The scope of this activity will comprise all research topics of the former clusters HRT and Components (diagnosis, semantic platform, heterogeneity, interfaces, ET&TT, and, more generally, what is relevant to the concept of Real-Time component).

We therefore plan to hold a set of meetings between us (and possibly inviting affiliates, academic and/or industrial), on selected topics within the scope of this activity. The aim of such 2-3 days meetings is to gather, for extensively discussing the following matters:
  • A vision of the issues the area of embedded systems is faced with, in relation with the selected topic.
  • Participants having different backgrounds would present their perspective on the subject of the meeting and what tools and techniques their community may have developed, if any.
  • Possible connections and blending would be explored, by combining presentations and working sessions.
  • Minutes will be carefully recorded and subsequently lifted to the status of an ARTIST2 document and deliverable. These will contain in addition suggestions for further research directions. The aim is to identify long term fundamental research activities aiming at possibly deeply changing the industrial practice.

We plan 1 or 2 such meetings for the next 18 month period.

Current Results

Our current results are, accordingly, of two different types:
  • Ongoing cooperative research between partners on the subjects already described.
  • Meeting preparation: two meeting have been prepared which hopefully will take place in the last quarter of 2006.
  • Finally, usual scientific activity consisting of publication, conference organisation, attendance and animation.

Model-based Development in Computer and Control Sciences
In computer science, model-based development is endowed with a rich abstraction and refinement theory: a large specification is designed first, imprecise (non deterministic) in general, but sufficient for meeting the desired system properties. Then implementation details are brought in progressively, making the specification more and more precise, while keeping the properties, up to a point when it can be implemented.
Clearly, this is an ideal scheme which is seldom fulfilled in practice, but which has a paradigmatic value.

In control science, on the contrary, an exact model is built first, which allows a control system to be designed. Then the various uncertainties that may affect the system behaviour are progressively introduced and it is checked that the designed controller is robust enough to cope with these uncertainties.

Clearly, these two schemes are not, in practice, too far from each other. But, as control systems are mostly implemented by now on computers, some effort is needed if these two schemes have to match more closely. This can be valuable in the perspective of achieving an easier communication between computer and control cultures. A way to reach this goal would be to see the initially precise control model as representing a large class of models, those models which fall within some given "distance" from this model. This distance would then
represent the maximally admissible uncertainty around the model and further refinements would make this uncertainty smaller. This goal requires thus some notion of control system distance and approximation. Attempts toward this goal have already been pursued by Verimag,
Inria and Airbus:
- P. Caspi and A. Benveniste: Toward an approximation theory for computerised control. In A. Sangiovanni-Vincentelli and J. Sifakis, editors, 2nd International Workshop on Embedded Software, EMSOFT02, volume 2491 of Lecture Notes in Computer Science, 2002.
- Ch. Kossentini and P. Caspi: Approximation, Sampling and Voting in Hybrid Computing Systems. In HSCC06, Sta Barbara, March 2006.
- Similar studies are considered in the USA, notably at the University of Pensylvania (Georges Pappas) and at Carnegie-Mellon University (Bruce Krogh).

Models of Computation and Communications
In any of the two preceeding methods, at some step, implementation details have to be brought in. This also calls for further investigations: what are these "implementation details" how can we classify them, and introduce them in an orderly manner? How can we choose them (that is
to say how can we choose implementation platforms so as to achieve optimality and correct usage?) These are very important questions which can go as far as choosing between hardware and software for implementing some functions.
This systematic way of considering "implementation details" was founded by the pionnering works of Lee & Sangiovanni at Berkeley in the early 90s. It finds now interseting developments within the specific world of embedded systems by Inria, Parades, Verimag, reported in section 0.

This topic appeared as so important that it was chosen as one of the subjects that deserved being devoted a cluster meeting which will take place on November 16th-17th in Zurich, hosted by EHTZ 0.

Basic Concepts in Mobile Embedded Systems
Recent advantages in mobile and wireless technology have enabled a field of mobile embedded systems in new domains like pervasive computing but also in traditional domains like automation and process control. Thus, the time has come to integrate existing knowledge
in the field of real-time systems, dependable systems, modelling and component design into the paradigm of mobile embedded systems.

For example, this subject requires novel models of naming and addressing of the employed devices. While in static, wire-bound system, the address and route to a particular device implicitly identifies the device’s function, in the mobile computing paradigm a particular device
may appear on different routes in the network and take different roles as it moves in space and therefore interact with another part of the environment. Moreover, when considering faults, a faulty node may also infiltrate multiple clusters. This has to be considered in the fault
hypothesis for mobile embedded systems. Therefore, we need to extend existing models from the domain of real-time and distributed systems for mobile embedded systems that take into account naming, addressing, security, configuration, and dependability.

Techniques for the software implementation of embedded systems
PARADES has considered embedded systems specified using synchronous formal models. Unfortunately, efficient software implementations are based on tasks interacting asynhcronously, introducing a substantial difference between the model of computation and communication (MoCC) of synchronous specifications and the MoCC of software implementations.

To overcome the unavoidable difficulties N. Scaife and P. Caspi (Verimag) proposed (ECRTS`04) to introduce inter-task communication support in the operating system in order to preserve the synchornous semantics in the asynchronous software implementation of the embedded system. This approach has been further refined by S. Tripakis et al. (EMSOFT`05a). PARADES has contributed to this issue (EMSOFT`05b) by taking a platform based approach to the problem. We started from an abstraction of the software platform in terms of a traditional timing model based on periods, deadlines, offsets and response times.
We recognized that the problem presents three aspects: 1) a set of precedence constraits between writers and readers, 2) buffering techniques to decouple computation from communication, and 3) tagging mechanisms to make communication deterministic.

Precedence constraints can be guaranted both by locking (e.g. semaphors) and non-locking (e.g. priority assignment) mechanisms. Moreover, we have shown that buffers may be effectively sized by using the timing model abstraction. This approach allows for effective design space exploration, where both single- and multi-processor architectures and distributed platforms can be considered. For each of these platforms we have proposed efficient tagging mechanisms to ensure communication determinism. The different approaches of PARADES and Verimag provide a powerful set of techniques for the asynchronous implementation of synchronous systems covering a wide spectrum of solutions, differentiating in performance, memory efficiency, flexibility and ease of implementation.

The problem of preserving the synchronous semantics in embedded software implementations shows the importance from the applications viewpoint of the problem of scheduling under precedence constraints. We have analyzed the literature on this topic and recognized the
weaknesses on the corresponding state of the art as regards embedded software. We have noted that the theory was not completely developed and ad hoc solutions were only proposed for common cases. In the framework of Artist2 network of excellence, we have developed a
unified and more general theory for uniprocessor scheduling under precedence constraint for embedded software (RTAS`06), providing solutions for different scheduling policies and distinct application cases.

PARADES has contributed, in the person of Alberto Sangiovanni-Vincentelli, together with INRIA, Verimag, U.C. Berkeley and the Columbia University in the development of a systematic method to formally model heterogeneous reactive systems. This work has resulted
in a series of joint publications listed below.

Preparation of two meetings

The aim of the first meeting proposed is the study of research toward a conceptual model and a description of the associated concepts and terms, an ontology, covering the field of distributed real-time embedded computer system. At present, there seems to be no general
agreement concerning the precise meaning of many commonly used terms. For example, the important concept of a component is viewed differently by different authors, depending whether they come from the software or the hardware arena. The same is true for other fundamental concepts, such as time, state, and determinism. We feel that ARTIST2 can make a substantial contribution to establish a commonly accepted ontology for distributed embedded systems.

We propose to build on the results of the DSoS (Dependable Systems of Systems) Conceptual Model (IST Project-1999-11585). It was a key objective of the DSoS Conceptual Model to analyze and unify the concepts in the field Dependable Systems-of-Systems and to establish a
common ontology that brings together the differing viewpoints and terms of a number of the involved communities. The final version of the DSoS conceptual model makes a significant contribution towards this objective. However, a number of important terms, such as interface,
software module, middleware, need further deliberations and more detailed descriptions.

Having participated in a number of community wide initiatives that had the objective to establish and clarify fundamental concepts (e.g. in the field of fault-tolerance), we know about the difficulties and the effort required to achieve a community wide agreement on fundamental concepts and terms. However, we feel such an effort is needed to further advance the field of distributed embedded systems.

The aim of the second meeting is to thoroughly address the question of models of computation and communication: heterogeneity, both conceptual (due to the differences in cultural backgrounds that takes place in the domain: software, hardware, control) and material
(the different possible implementation technologies) make it mandatory to better understanding this issue; there is a need for better high-level mathematical modelling of MoCCs; and there is a need for studies on some MoCCs corresponding to special architectures used e.g., communication by sampling, a non-standard mechanism – from the viewpoint of computer engineers – often used in distributed control systems).

Keynotes, Workshops, Tutorials

ARTIST2 Workshop: Design Issues in Distributed, Communication-Centric Systems
DATE Conference, Munich, Germany, 10.3.2006
Organiser: Bruno Bouyssounouse, Rolf Ernst, Lothar Thiele
Objective: The workshop presented relevant, innovative, and holistic topics in communication-centric systems, sensor networks, dynamic real-time architecture, distributed computing, minimal operating systems, and self-organisation.
See it online!

ARTIST2 Workshop: Distributed Embedded Systems
Leiden, Netherlands, 21.11. - 24.11.2005
Organiser: Lothar Thiele
Objective: Benchmarking and comparison of different formal analysis approaches
See it online!

Keynote address by Tom Henzinger and Joseph Sifakis: The embedded systems design challenge
14th International Symposium on Formal Methods (FM)
August 2006
We summarize some current trends in embedded systems design and point out some of their characteristics, such as the chasm between analytical and computational models, and the gap between safety-critical and best-effort engineering practices. We call for a coherent scientific foundation for embedded systems design, and we discuss a few key demands on such a foundation: the need for encompassing several manifestations of heterogeneity, and the need for constructivity in design. We believe that the development of a satisfactory Embedded Systems Design Science provides a timely challenge and opportunity for reinvigorating computer science.

Tutorial: Supporting predictable design using formal analysis techniques
ARTES Summer School, Stockholm Schweden, August 21-25 2006.
Speaker: Arne Hamann and Razvan Racu, Technical University of Braunschweig.
See it online!

Talk (in german): Zuverlässige und effiziente Integration eingebetteter Systeme - ein Widerspruch?
Annual Meeting IEEE Computer Society, Wolfsburg Germany, July 2006.
Speaker: Rolf Ernst, Technical University of Braunschweig

Invited Lecture by Martin Törngren at Mecel (a Swedish subsidiary of Delphi): "Costefficient and systematic verification of embedded control systems", June 14, 2006. Performed at the occasion of starting a new national project between Mecel and KTH.

Invited lecture by Paul Caspi, Verimag (France): Some Issues in Model-based Development for Embedded Control Systems, DIPES 2006, Braga, Portugal, IFIP Working Conference on Distributed and Parallel Embedded Systems.
See it online!

 

 

ARTIST2 Participants: Expertise and Roles

  • Team Leader: Alberto Sangiovanni-Vincentelli (PARADES, Italy)
    Areas of his team’s expertise: strong interaction with automotive, design software and semiconductor industry (co-founder of Cadence and Synopsys); expertise in design flows, tools and modelling methodologies with particular attention to Hard Real-Time; Platform-Based Design and Metropolis design framework for integration of design processes from OEMs to suppliers involving functional and non functional aspects.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Albert Benveniste (INRIA, France)
    Areas of his team’s expertise: synchronous languages and heterogeneous systems modelling and deployment.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Bengt Jonsson (Uppsala University)
    Areas: Semantics, modeling, analysis of distributed embedded systems. Development of TIMES and UPPAAL tools.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Hermann Kopetz (TU Vienna, Austria)
    Areas of his team’s expertise: inventor of the TTA concept.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Werner Damm (OFFIS, Germany)
    Areas of his team’s expertise: embedded system modelling and validation, deep involvement in cooperation with the automotive industries.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Paul Caspi (Verimag, France)
    Areas of his team’s expertise: synchronous languages and heterogeneous systems modelling and deployment; tight cooperation with Airbus.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Petru Eles (Linköping University, Sweden)
    Areas of his team’s expertise: schedulability analysis for heterogeneous systems.
    Role in the activity: organization and planning of meetings.
  • Team Leader: Tom Henzinger (EPFL, Switzerland)
    Areas of his team’s expertise: development of abstract programming models for realtime computing [Giotto: time-triggered; xGiotto: both time- and event-triggered].
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Rolf Ernst (University Braunschweig, Germany)
    Areas of his team’s expertise: formal performance models for networks-on-chip.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Francois Terrier (CEA, France)
    Areas of his team’s expertise: Expertise: Modeling and analysis of embedded systems, UML development
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Pierre Combes (FTRD, France)
    Expertise: Component modeling, Service integration and interference, performance analysis.
  • Team leader: Karl-Erik Arzen (Lund University, Sweden)
    Expertise: relations between control and embedded software, effect of architecture on the performance of control, control techniques for architecture studies.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Martin Törngren (KTH, Sweden)
    Expertise: relations between control and embedded software, effect of architecture on
    the performance of control, control techniques for architecture studies, mechatronics.
    Role in the activity: discussion of and participation to meetings.

Affiliated Participants: Expertise and Roles

  • Team Leader: Jan Romberg (TU Munich, Germany)
    Areas of his team’s expertise: synchronous dataflow notations and tools, distributed architectures in automobile.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Luciano Lavagno (Politecnico di Torino, Italy)
    Areas of his team’s expertise: IC design and algorithms for synchronous and asynchronous design.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Francois Pilarski (Airbus France)
    Areas of his team’s expertise: avionics industrial case study.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Heiko Dörr (DaimlerChrysler, Germany)
    Areas of his team’s expertise: automotive industrial case study.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Stephan Kowalewski (RWTH Aachen, Germany)
    Areas of his team’s expertise: automotive industrial case study.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Jakob Axelsson (Volvo, Sweden)
    Areas of his team’s expertise: automotive industrial case study.
    Role in the activity: discussion of and participation to meetings.
  • Team Leader: Christoph Kirsch (University of Salzburg, Austria)
    Areas of this team’s expertise: development of abstract programming models for realtime computing [Giotto: time-triggered; xGiotto: both time- and event-triggered].
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Ivica Crnkovic (MdH, Sweden)
    Areas of his team’s expertise: component models, component-based software engineering.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Marius Minea (Institute e-Austria Timisoara, Romania)
    Areas of his team’s expertise: Formal verification, specification of timed systems.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Bernhard Steffen (Dortmund University, Germany)
    Areas of his team’s expertise: tool integration, modeling and verification, generation of models of communicating systems.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Anders Ravn (Aalborg, Danmark)
    Areas of his team’s expertise: modeling and verification of timed systems.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Peter Eriksson (ABB Automation Technology, Sweden)
    Areas of his team’s expertise: Construction of large complex embedded systems.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Dominique Potier (Thales R&T, France)
    Areas of his team’s expertise: Construction of large complex embedded systems, Model
    driven development.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Alan Moore (ARTiSAN Software)
    Areas of his team’s expertise: technologies for embedded systems engineering, UML tool suites.
    Role in the activity: discussion of and participation to meetings.
  • Team leader: Luca Carloni (Columbia University)
    Areas of his team’s expertise: tool integration, modeling and verification, design methodology, communication-based design, latency insensitive protocols.
    Role in the activity: discussion of and participation to meetings.

(c) Artist Consortium, All Rights Reserved - 2006, 2007, 2008, 2009

Réalisation Axome - Création de sites Internet