ArtistDesign NoE

40. Important Dates

Ulrike Woern — 2007-01-23T08:59:28Z

Important Dates

Paper submission	Extended to August 8th, 2006
Acceptance/rejection notification	September 1, 2006
Final version	October 1, 2006
Workshop	October 26, 2006

20. Submissions

Ulrike Woern — 2007-01-23T08:59:17Z

Submissions

Interested authors should submit a full paper (not to exceed 8 double column, single space pages) to:

Dr. Jeff Jackson 317 Houser Hall The University of Alabama Tuscaloosa, AL 35487-0286

Phone: (205) 348-2919 Email:jjackson@eng.ua.edu

Please use the ACM SIG template in constructing your submission. The template may be found here.

Electronic submission is required, preferably as a PDF attachment to an email message.

Please use the subject line “WESE2006 submission” in your submission email.

40. Abstracts and Slides

Ulrike Woern — 2006-10-18T07:17:04Z

Be sure to see the school's overview.

Contents - Abstracts and Slides for the following speakers:
Patricia Bouyer
Alberto Ferrari
Susanne Graf
Pierre Alain Muller
Reiko Heckel
Thierry Jeron
Joost-Pieter Katoen
Brian Nielsen
Ileana Ober
Jean François Raskin
Joseph Sifakis
Stavros Tripakis
Reinhard Wilhelm
Ed Brinksma

Patricia Bouyer

Tutorial: Foundation for Timed Systems

Slides in pdf-format available here.

Many critical applications have explicit timing constraints. For example, behaviours of systems interacting with an environment (e.g. embedded systems) depend on quantitative timing constraints like response times, transmission delays, etc... For representing such timed systems, several timed models have been proposed. Since their introduction by Alur and Dill in the 90s, timed automata are one of the most-studied and most-established models for real-time systems. Numerous works have been devoted to the comprehension of timed automata and the major property of timed automata is probably that reachability is decidable, which implies in particular that it can be used for verification purposes. Based on this nice theoretical result, several model-checkers have been developed (for instance CMC, HyTech, Kronos and Uppaal) and a lot of case studies have been treated. In this tutorial, we will present the model of timed automata, and basic but fundamental results on this model.

Bibliography:

R. Alur and D.L. Dill. A theory of timed automata. Theoretical Computer Science 126:183-235, 1994.
See it online!
R. Alur and P. Madhusudan. Decision problems for timed automata: A survey. 4th Intl. School on Formal Methods for Computer, Communication, and Software Systems: Real Time, 2004.
See it online!
E. Asarin. Challenges in timed languages: From applied theory to basic theory. The Bulletin of the European Association for Theoretical Computer Science 83, 2004.
See it online!

Alberto Ferrari

Modeling of Heterogeneous Systems in Metropolis

Establishing formal design methodologies is imperative to effectively manage complex design tasks required in modern-date system designs. It involves defining levels of abstraction to represent formally systems being designed, as well as formulating problems to be addressed at and across the abstraction levels. This approach calls for a design environment in which systems can be unambiguously represented throughout the abstraction levels, the design problems can be mathematically formulated, and tools can be incorporated to solve some of the problems automatically. Developing such an environment is precisely the goal of Metropolis. Metropolis consists of an infrastructure, a tool set, and design methodologies for various application domains. Metropolis is based on the concept of metamodel, as a way of capturing in a semantic rigorous way the interconnection of subsystems described with different models of computation. By the same metamodeling approach, we can integrate and apply tools for formal methods easily. In addition, the Metropolis infrastructure allows decorating functional models of the design with non functional properties such as execution time and power consumed. Because of its flexibility and expressive power, the framework can be used in a variety of industrial domains.

In this talk, I will review the architecture of the environment, its semantics, models of computation supported, and the application of the Platform-based Design methodology via Metropolis to a number of case studies.

Bibliography:

Metropolis Design Guidelines, Alessandro Pinto, University of California at Berkeley, UCB/ERL Memo 04/40, November, 2004.
The Metropolis Meta Model Version 0.4, The Metropolis Project Team, University of California, Berkeley, UCB/ERL M04/38, September, 2004.
Simple Case Study in Metropolis, Abhijit Davare, Douglas Densmore, Vishal Shah, Haibo Zeng, University of California, Berkeley, UCB.ERL 04/37, September, 2004.
Microarchitecture Development via Metropolis Successive Platform Refinement, Douglas Densmore, Sanjay Rekhi, Alberto Sangiovanni-Vincentelli, Design Automation and Test in Europe (DATE), February, 2004.
Separation of Concerns: Overhead in Modeling and Efficient Simulation Techniques, G Yang, Y Watanabe, F Balarin, A Sangiovanni-Vincentelli, Fourth ACM International Conference on Embedded Software (EMSOFT'04), September, 2004.
Metropolis: An Integrated Electronic System Design Environment, Felice Balarin, Yosinori Watanabe, Harry Hsieh, Luciano Lavagno, Claudio Passerone, Alberto Sangiovanni-Vincentelli, IEEE Computer Society, April 2003.
Compositional Modeling in Metropolis, Gregor Goessler and Alberto Sangiovanni-Vincentelli, Proc. EMSOFT'02, A. Sangiovanni-Vincentelli and J. Sifakis, October, 2002.

Susanne Graf

Verification of UML models with timing constraints with IF

Slides in pdf format are available here.

This talk will give an overview on the IF, an open validation platform for asynchronous timed systems such as telecommunication protocols or distributed embedded applications. The IF toolbox is built upon a specification language based on timed automata with urgency extended with discrete data variables, various communication primitives, dynamic process creation and destruction. This language includes most of the concepts allowing the direct representation of modeling and programming languages for distributed systems like SDL, UML or Java, as well as extensions allowing the expressions of timing properties. Here, we will focus on the use of IF for the validation of real-time properties of UML models. A short overview on the considered UML profile and the mapping principles from UML to IF will be presented, as well as the way in which semantic variations of the profile are anticipated. Then the usefulness of the UML profile for modelling of real-time systems and their properties, and the use of the IF toolset for their validation will be demonstrated on hand of one or two case studies. In particular, we will show the use of the considered UML profile for the validation of deployment related propserties such as scheduling and timely access to a shered bus. This talk is related to the talk on Component-based modeling of real-time systems (see the program ). Several of the concepts presented in this talk have been implemented in IF and have shown their usefulness for obtaining faithful and direct mappings of high-level modeling languages.

A list of related documents and links :

The webpage of the IF verification platform containing links to manuals, downloadable code, case studies and contains also a tutorial.
Below a few papers on the IF language and tool and the theory behind: o The paper presented at CAV 2002 explains the difference to the older versions of the language and the tool o The paper presented at SFM summer school 2004 gives a complete overview on the IF language and the tool architecture. o This paper which has been published in Information and Computation introduces timed automata with urgency which are the version of timed automata used in IF o This paper which has been presented at the Symposium FMCO 2003 shows the expressive power of priorities. Indeed, priorities have been very helpful for the mapping of different high level formalisms to IF.
The webpage of the Omega project in which the considered UML profile and the UML interface IFx for IF have been developed.
Below a few papers on the UML profile, in particular the real-time extensions and the work in connection with the IF tool. Overviews on all work done in Omega can be found on the Omega home page. o This paper which is being published in STTT gives an overview on the mapping from UML to IF, the IFx frontend and one of the case studies o This paper which is being published in STTT explains in details the real-time extensions of the UML profile. o This paper presents a case study carried out in the context of the Omega project and is to be presented at the MARTES workshop. Another case study is in this paper, and the Omega web page gives an overview on all case studies

Pierre Alain Muller

Applications of model transformations

Slides in pdf-format available here.

Reiko Heckel

Foundations of Model Transformations

Slides in pdf-format are available here.

At the heart of model-driven engineering are activities like maintaining consistency, evolution, translation, and execution of models. These are examples of model transformations. A (mathematical) foundation is needed for studying issues like the expressiveness and complexity, execution and optimisation, well-definedness and semantic correctness of transformations. This lecture is about graph transformations as one such foundation. After introducing the basic concepts of graph transformation by means of an example, different applications of graph transformations to model transformations will be discussed. A survey of relevant theory and tools concludes the presentation.

Thierry Jeron

Test Generation using Model Checking

In this talk, we will show how verification techniques (model-checking, abstract interpretation) can be used for the automatic generation of test cases for conformance testing of reactive systems. Conformance testing consists in checking, using test cases, whether a black box implementation behaves correctly with respect to a formal specification. In the ioco testing theory [Tretmans96], the operational semantics of a (non-deterministic) system (specification, implementation or test case) is modelled by a transition system with inputs and outputs (IOLTS) and conformance is defined as a relation between visible behaviors of the implementation and the specification. A crucial problem in this context is to select off-line some test cases from the specification, before executing them on the implementation. One possible solution is to use test purposes specified by observers accepting behaviors one wants to observe during testing. Test case selection then mainly reduces to a language intersection problem (computing a subset of the visible behaviors of the specification accepted by a test purpose), which amounts to solving reachability and co-reachability problems in a product model. For finite state systems, these problems can be solved by classical graph algorithms, as implemented in the TGV tool [Jard-Jeron]. For more powerful specification models like extended automata (IOSTS), one wants to select test cases in the form of extended automata, by syntactic operations. But because reachability and co-reachability problems are undecidable in these models, over-approximations (e.g. computed by abstract interpretation) can be used to guide the syntactic transformations [Jeannet et al.05]. These algorithms are implemented in the STG tool.

Bibliography:

[Tretmans96] J. Tretmans. Test Generation with Inputs, Outputs and Repetitive Quiescence. Software - Concepts and Tools, Vol. 17(3), pp. 103 - 120. Springer-Verlag, 1996.
Also: Technical Report No. 96-26, Centre for Telematics and Information Technology, University of Twente, The Netherlands.
[Jard-Jeron 04] C. Jard, T. Jéron. TGV: theory, principles and algorithms, A tool for the automatic synthesis of conformance test cases for non-deterministic reactive systems, Software Tools for Technology Transfer (STTT), Volume 7, No 4, August 2005. See it online!
[Jeannet et al.] B. Jeannet, T. Jéron, V. Rusu, E. Zinovieva. Symbolic Test Selection based on Approximate Analysis, in TACAS'05, Volume 3440 of LNCS, Edinburgh (Scottland), April 2005. See it online!

Joost-Pieter Katoen

Model checking focuses on absolute correctness ("either the system is safe or not"). In practice such rigid notions are hard, or even impossible, to guarantee. Instead, systems are subject to various phenomena of stochastic nature, such as message loss, faults, and delays. Correctness thus has a less absolute nature. Quantitative properties ("safety is guaranteed in 93% of the cases") can be automatically checked using stochastic model checking. This technique originates from the mid 1980s focusing on establishing 0-1 probabilities ("a program terminates with probability one"). During the last decade, these methods have been extended, refined and improved, and - most importantly - are nowadays supported by software tools that have been applied to analyze real-life systems e.g., Bluetooth's device discovery, IPv4 address assignment, and group membership protocols for wireless networks. This tutorial will survey the foundations of model checking of stochastic process of different nature, such as discrete-time, continuous-time, cost- extended models as well as models exhibiting probabilistic and non-deterministic behaviour.

Background material:

Basics on stochastic processes, e.g. lectures 10, 11, 12, 17 and 18.
See it online!

Fundamental papers on this topic

Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen: Model-Checking Algorithms for Continuous-Time Markov Chains. IEEE Trans. Software Eng. 29(6): 524-541 (2003).
See it online!
Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen: On the Logical Characterisation of Performability Properties. ICALP 2000: 780-792.
See it online!
Christel Baier, Marta Z. Kwiatkowska: Model Checking for a Probabilistic Branching Time Logic with Fairness. Distributed Computing 11(3): 125-155 (1998).
See it online!
Hans Hansson, Bengt Jonsson: A Logic for Reasoning about Time and Reliability. Formal Asp. Comput. 6(5): 512-535 (1994).
See it online!

Brian Nielsen

Automated model-based testing of real-time systems poses a new set of challenges: It must be defined when a system is correct with respect to real-time requirements. The test selection problem is worsened because in real-time systems there are an infinite set of time instances to choose from about when to supply inputs expect outputs. The test cases or formal model must be interpreted in real-time requiring new symbolic analysis algorithms. Finally tests must be executed and the implementation monitoring in real-time. In this tutorial we present a framework, an algorithm and a new tool for online testing of embedded real-time systems based on symbolic techniques used in \uppaal model checker engine. Using online testing, tests are generated and immediately executed event per event. We describe a sound and complete randomized online testing algorithm and how to implement it using symbolic state representation and manipulation techniques. We propose the notion of relatvized timed input/output conformance as the formal implementation relation. A novelty of this relation and our testing algorithm is that they explicitly take environment assumptions into account, generate, execute and verify the result online. Finally, we show how the framework and tool can be applied to an industrial embedded controller.

Bibliography

Mikucionis, Marius and Larsen, Kim G. and Nielsen,Brian. T-Uppaal: Online Model-based Testing of Real-time Systems, 19th IEEE International Conference on Automated Software Engineering, 2004, september, 2 pp.
See it online!
Kim Larsen and Marius Mikucionis and Brian Nielsen, Online Testing of Real-time Systems using Uppaal, International workshop on Formal Approaches to Testing of Software, 2004, Co-located with IEEE Conference on Automates Software Engineering 2004, Linz, Austria, September 21.
See it online!
Mikucionis, Marius and Larsen, Kim G. and Nielsen, Brian and Skou, Arne, Testing Real-Time Embedded Software using UppAal-TRON --- an industrial case study, Embedded Software (EMSOFT), September 2005.
See it online!

Ilena Ober

Slides are available here.

UML (Unified Modeling Language) is a standardised (set of) language(s) allowing to specify, design, visualize and document models of software systems. UML does not impose a development process or methodology and it aims at being independent of any programming language. In UML, the user can specify requirements, model the system's logical structure and behaviour (as a whole or by decomposition into subsystems and components), describe physical deployment and platform-specific information, annotate and document the model. By covering various facets of software development at various points of its lifetime, UML provides a concrete support for model driven development. This tutorial presents the major features of UML, with focus on system and components modelling of structure and behaviour.

Resources and links - UML Standard Specifications UML is a subject of frantic writing. There are lots of books describing UML, giving different interpretations for it, suggesting how to use it in various contexts, how to adapt it for fitting various needs… Therefore, to me, The most important references are the (user unfriendly) documents composing the OMG standard. You can always find the most up-to-date standard UML specifications here.

The reference specifications for UML 2.0 (august 2005) are:

Those still interested in UML 1.x can find the specification for UML 1.4.2 (the UML specification also standardised by ISO) here.

A little known, yet quite interesting OMG working document containing an assessment on the use of UML 1.x performed before starting the work on UML 2.0.

UML biographies

Other ressources An overview of (some) UML-based tools can be found here.

"Classical" UML critiques:

Death by UML fever, by Alex E. Bell, on the occasional misuse of UML
Bertrand Meyer's 1997 satire on UML published in a special issue of Ed Yourdon's American Programmer UML: The Positive Spin

Jean François Raskin

Timed Controller Synthesis and Implementability Issues

Slides in pdf-format available here.

In this talk, I will show how to formalize the controller synthesis problem using two-player games. First, I will consider reachability and safety games on finite game structures. Second, I will consider those games on (infinite) timed game structures and show how to synthesize strategies that have desirable properties like non-zenoness. Third, I will show that some non-zeno strategies are not implementable and I will introduce the notion of Almost ASAP semantics which allow to solve the implementability problem for timed automata.

Two papers to read :

Luca de Alfaro, Marco Faella, Thomas A. Henzinger, Rupak Majumdar, Mariëlle Stoelinga. The element of surprise in timed games. In the Proc. of CONCUR'03, LNCS , Springer-Verlag, p. 142-156, 2003.
Martin De Wulf, Laurent Doyen, Jean-François Raskin. Almost ASAP Semantics: From Timed Models to Timed Implementations. In the Proc. of HSCC'04, LNCS 2993, Springer-Verlag, p. 296-310, 2004.
More pointers to relevant papers will be given during the talk.

Joseph Sifakis

Please see this pdf document.

Stavros Tripakis

A more recent abstract is available in this pdf document.

We study the problem of fault-diagnosis in the context of dense-time automata. The problem is, given the model of a plant as a timed automaton with a set of observable events and a set of unobservable events, including a special event modeling faults, to construct a deterministic machine, the diagnoser, which reacts to observable events and time delays, and announces a fault within a delay of at most Delta time units after the fault occurred. We define what it means for a timed automaton to be diagnosable, and provide algorithms to check diagnosability. The algorithms are based on standard reachability analyses in search of accepting states or non-zeno runs. We also show how to construct a diagnoser for a diagnosable timed automaton, and how the diagnoser can be implemented using data structures and algorithms similar to those used in most timed-automata verification tools.

Main reference:

S. Tripakis. Fault Diagnosis for Timed Automata. In FTRTFT'02. LNCS 2469, Springer.
See it online!
Other references available here.

Reinhard Wilhelm

Timing Analysis for Real-Time Systems

Hard real-time systems are subject to stringent timing constraints which are dictated by the surrounding physical environment. A schedulability analysis has to be performed in order to guarantee that all timing constraints will be met ("timing validation"). Existing techniques for schedulability analysis require upper bounds for the execution times of all the system's tasks to be known. These upper bounds are commonly called worst-case execution times (WCETs). The WCET-determination problem has become non-trivial due to the advent of processor features such as caches, pipelines, and all kinds of speculation, which make the execution time of an individual instruction locally unpredictable. Such execution times may vary between a few cycles and several hundred cycles.

A combination of Abstract Interpretation (AI) with Integer Linear Programming (ILP) has been successfully used to determine precise upper bounds on the execution times of real-time programs. The task solved by abstract interpretation is to compute invariants about the processor's execution states at all program points. These invariants describe the contents of caches, of the pipeline, of prediction units etc. They allow to verify local safety properties, safety properties who correspond to the absence of "timing accidents". Timing accidents, e.g. cache misses, pipeline stalls are reasons for the increase of the execution time of an individual instruction in an execution state.

Ed Brinksma

Foundations of Testing

Slides in pdf format available here.
StatCounter - Free Web Tracker and Counter

Communication-centric Systems

Ulrike Woern — 2006-10-13T15:14:26Z

Activity Leaders: Rolf Ernst (IDA, TU Braunschweig)

Artist2 Clusters:
Execution Platforms

Contents
Baseline
Previous Work
Problem Tackled in Year2
Current Results
Keynotes, Workshops, Tutorials
Related Publications
Participants

Abstract
The activity assesses the state-of-the-art in models that take into consideration the particularities of various quasi-standard communication protocols during system analysis and scheduling. The communication infrastructure can be optimised in order to be adapted to the particularities of the implemented application. That meets a growing need in industry to consider formal techniques in embedded system design as a complement to traditional prototyping and simulation based approaches.

Baseline

Formal communication modelling has been investigated by Zebo Peng and Petru Eles at Linköping University, Lothar Thiele at ETH Zurich (ETHZ) and Rolf Ernst at Braunschweig. The ETH Zurich and Linköping University have outstanding expertise in modelling and analysing packet flow communication and network processors (ETH) and conditional task graphs combined with statistical modelling. UoB is one of the most widely recognized centres of expertise in NoC design, analysis and road mapping. DTU has a long experience in asynchronous circuits design and in NoC design based on this technology. Embedded architectures and heterogeneous distributed embedded systems have grown to extremely complex computation and communication patterns. New performance models and a corresponding theory are urgently needed Europe needs to develop skills to safely design such systems.

Previous Work

Mixed Performance Analysis in Communication Centric Systems In a first step, the SymTA/S tool framework that was initially designed to support only the evaluation methods designed at TU Braunschweig was extended with a dynamic library concept, such that different analytical libraries can be loaded into the tool to perform the system-level analysis of embedded systems. In a next step, at ETH Zürich, the formal analysis method Real-Time Calculus was implemented as a Java library that can be used from within the SymTA/S tool. This library was then integrated into the tool and can now be used for performance evaluation.

Hybrid Approach for Performance Analysis of Communication Centric Embedded Systems After an initial meeting (3 days in Bologna) in March 2004 to discuss the possibilities for a joint effort towards this new approach and exchange the knowledge of the existing performance evaluation methods used, Simon Künzli spent 3 weeks in May 2005 in Bologna for the actual implementation of a case study using such a hybrid approach.

The existing simulation framework was extended by the interfaces needed for the proposed hybrid approach. Further, an example application was analyzed using the new approach. The hybrid analysis can be performed automated and exposes the expected speed-up for the simulation of embedded systems, with only a small deterioration of the accuracy of the results.

Performance Analysis in the System Design Process In February 2004, Ernesto Wandeler spent 10 days at the ESI. During this time, an appropriate case-study system was identified and analyzed using a formal performance analysis method developed at TIK, ETH Zürich (Real-Time Calculus). Further, Ernesto Wandeler held 3 talks at ESI, to introduce people at ESI to the performance analysis research at TIK. In April 2005, Marcel Verhoef spent 5 days at ETH. During this time, a journal paper was written, based on a former conference paper. Further, new potential case-study systems, as well as plans for a performance analysis tool were discussed.

As a first case study, an existing distributed in-car radio navigation system was chosen and was specified in UML. For this case study, Real-Time Calculus was used to evaluate and compare 5 different potential system architectures. Sensitivity analysis was applied to all architectures to identify their robustness and potential bottlenecks. For the architecture that is actually used in the commercial implementation of the case study system, the robustness and the bottlenecks could be identified correctly using formal performance analysis methods.

Optimization and analysis of distributed embedded systems Prof. Eles and his research group, University Linköping, have continued their work in the context of optimization and analysis of distributed embedded systems. They have concentrated on the following issues:
Analysis of hierarchically scheduled systems
Timing analysis of distributed task sets communicating through the FlexRay protocol
Analysis and optimization of distributed embedded systems with fault tolerance requirements

Power analysis and optimization To initiate the joint activity, Bren Mochocki, University of Notre Dame, spent 2 month at TU Braunschweig. During this time, interfaces between the power analysis tool developed at University of Notre Dame and SymTA/S were created. Based on these interfaces SymTA/S could be extended with an analysis technique to determine the power consumption of a given embedded system. Since then the power models and the interfaces were regularly extended and refined.

On-chip interconnections for single-chip execution platforms The work on communication-centric systems by the group of Prof. Madsen, Technical University of Denmark (DTU), has focused on on-chip interconnections for single-chip execution platforms. The starting point for this work has been the development of a clock less NoC architecture (MANGO) and a system-level NoC model based on the multiprocessor simulation environment (ARTS) developed at DTU. The MANGO NoC architecture is based on asynchronous message-passing and provides guaranteed services. Its interface is based on the standard OCP interface protocol which makes the architecture very suited for a modular SoC design flow. The use of a clockless circuit technique has a number of advantages, among which are; inherent global timing closure, low forward latency in pipelines, and zero dynamic idle power consumption. The ARTS modelling framework, which is developed as part of the System Modelling Infrastructure activity of ARTIST2, was extended with capabilities to model interconnect structures. At the system-level, the details of the processing elements and the NoC need to be abstracted in a way that allows for an accurate modelling of the global performance of the system, including the interrelationships among the diverse processors, software processes and physical interfaces and interconnections. To support the designer of single-chip based embedded systems, which includes multi-processor platforms running dedicated RTOS's, with the ability to analyse effects of on-chip interconnect network, the ARTS framework was required to support the analysis of network performance under different traffic and load conditions. This was achieved by extending the model with capabilities for NoC modelling.

Highly scalable communication architectures The design objective was to develop a NoC targeting heterogeneous systems and featuring support for customizable, domain-specific NoC realizations. This implies designing Xpipes network building blocks as soft cores and to arbitrarily instantiate these blocks so to obtain custom-tailored irregular topologies. All Xpipes components were modelled in SystemC at the cycle accurate level, and integrated in an overall system simulation environment. Network interface was designed with the objective to allow frequency decoupling and efficient protocol conversion between system cores domain and network domain. Moreover, a standard OCP interface protocol with the cores was implemented to increase portability across different platforms. Links design was characterized by the concern to avoid limiting effects of signal propagation time on overall system clock period. This was achieved by providing support for link pipelining and latency-insensitive design. Finally, switch modules design followed the following guidelines: latency minimization, minimum impact of routing logic, output buffering to avoid head-of-line blocking, initial support for best-effort traffic only. Parameters that can be set at design time include number of switch input/output ports, buffer sizing, flit width, over clocking factor, etc.

High level modelling of system interconnects High level models for system interconnects were at first derived for state-of-the-art busses, validated on a virtual platform and potentials for their deployment were explored. In particular, a cooperation with Linköping University paved the way for exploring different high level models for shared communication resources and for exploiting them within theoretical frameworks for efficient allocation, mapping and scheduling of tasks onto MPSoC hardware platforms. Specifically, we identified two modelling approaches to on-chip communication (additive models and coarse-grain modelling of communication tasks) and addressed the issue of modelling implicit communication in a predictive way (cache misses, semaphore polling). Then, we developed the theoretical framework taking the Benders Decomposition approach: an Integer Programming model to assign tasks to computation and storage resources and a Constraint Programming model to schedule tasks onto processors. Non-feasible schedules generate a no-good for the IP problem, which is then re-iterated. The procedure is proved to converge to the optimum.

Hybrid system-level performance analysis approach High level bus models can also be used for performance estimation. However, it is well known that formal models by themselves may turn out to be inaccurate for exploring the performance of complex multi-processor systems, because abstractions might fail to capture the system behaviour. Similarly, accurate simulation of the entire system might turn out to be infeasible due to the long simulation times. Therefore, we set up a cooperation with ETH Zürich with the objective to assess the efficiency of a hybrid approach: combining simulation and formal methods for system-level performance analysis. This approach enables a faster validation of the whole system in that we can decide to model a subcomponent of which the behaviour is well known through a formal analysis, whereas we can have a detailed low level and time-consuming simulation component modelling for other components. We described how the simulation models can be coupled with the formal analysis framework and showed the applicability of the approach using case studies.

Problem Tackled in Year2

The industry increasingly applies hierarchical communication protocols, such as the automotive FlexRay Standard. Timing analysis has to follow that trend. Since system dependability and flexibility are growing demands in embedded systems, fault tolerance and robustness have to be included in communication modelling and optimization. Further case studies are needed to demonstrate the feasibility and practicability of the research results. Power optimization is a new and urgent requirement in mobile and streaming applications.

Current Results

Timing Analysis of the Flexray Protocol (University Linköping) In the second year the Linköping group has continued the work regarding analysis and optimization of distributed embedded real-time systems, with application in automotive electronics. The main goal is to develop models and tools for the analysis and optimization of such communication-intensive systems. Emphasis is placed on the analysis of timing properties, considering the heterogeneous nature of such systems and the particularities of the various communication protocols. In the most recent research the analysis of mixed static/dynamic protocols, such as FlexRay, has been performed [PPE+06]. FlexRay is likely to become a standard for certain automotive applications and the elaboration of the first timing analysis approach for distributed systems built on FlexRay is of importance for our industrial partners. On top of these timing analysis approaches, various system-level optimization tools have been built, performing application mapping, communication synthesis, priority assignment, etc. The Linköping group has closely collaborated with our industrial partners at Volvo as well as with the Braunschweig group. The developed analysis approaches are under integration in the Symta/S environment developed at Braunschweig.

Fault Tolerance (University Linköping) One other issue that has been explored by the Linköping group, in the same context of distributed communication-intensive real-time systems, is that of fault tolerance and, in particular, the issue of transient faults. There are two main aspects of interest here:

Analysis of timing properties in the presence of faults and possible guarantees regarding worst case behaviour
System optimization, such that timing and fault tolerance requirements are satisfied given a certain, limited amount of resources. An approach for scheduling and worst case analysis with fault tolerance has been developed [IPE+06]. On top of this analysis approach, an optimization technique for task mapping and fault tolerance policy assignment has been elaborated and implemented.

Combination of performance analysis methods: SymTA/S and MPA (ETH Zürich) Collaboration with Arne Hamann, University of Braunschweig.

This new collaboration is based on collaborations between the two institutions from previous years, where we tried to identify the similarities and differences of the performance evaluation methods developed (a) at TU Braunschweig integrated in the SymTA/S tool, and (b) at ETH Zurich implemented as toolbox for modular performance analysis (MPA). With this analysis of the weaknesses and strengths of the various methods in mind, we believe that a combination of the methods leads to a significant improvement of analysis results. Especially for systems in which not all parts of the system can be analysed using a single technique due to limitations of the methods, we see the possibility to apply a combined approach which leads to good analysis results. After the analysis of the individual techniques, we are now looking at a common basic for such a combination, and analyse the implementation effort needed for a tool that supports both analysis techniques. The plan for the next months is to implement the changes needed for a combination and analyse an example application to show the strength of the new approach. These steps should also result into a joint publication of the results.

To achieve this, we intend to:

apply the changes in the tools at each of the partner's sites
organise an integration week where the two parts should be combined to form a single tool
perform the analysis of an example system.

Performance Analysis of an In-Car Radio Navigation System (ETH Zürich) Collaboration with Marcel Verhoef at Chess Information Technology, Embedded Systems Institute Eindhoven and Radboud University Nijmegen, and with Paul Lieverse at Siemens VDO In this activity, we investigated an in-car radio navigation system that was specified in UML. Modular Performance Analysis with Real-Time Calculus was used to evaluate and compare 5 different potential system architectures, and sensitivity analysis was applied to all architectures to identify their robustness and potential bottlenecks. For the architecture that is actually used in the commercial implementation of the case study system, the robustness and the bottlenecks could be identified correctly using the above methods. First results on this research were published at the First International Symposium on Leveraging Applications of Formal Methods [WTVL06]. After this symposium, we refined the analysis of the case study system. Based on the case study system, we also compared a number of different performance analysis and simulation methods. Currently, a hardware test bed is implemented to compare the analysis results with measured results in different system architectures. The results of the refined analysis, together with a thorough description of the applied analysis methods were published this year in a journal article [WTVL06]. The results of the analysis methods comparison and of the comparison to the measurements will be published in a future joint publication.

Sureal-Project: Hierarchical Event Models (TU Braunschweig) The main goal of the Sureal Project is to define an integrated development process for distributed embedded real-time Systems, especially regarding real-time aspect in all phases of the development. This includes the integration of different techniques for describing, analysing and modelling real-time aspects. To be able to use different tools specialized in handling real-time aspects in different phases of the system development interfaces must be defined for them to efficiently work together. Also the early prediction of the timing behaviour, the sensitivity and optimizing possibilities of the architecture play a very important role in such an integrated development process. The tool SymTA/S is capable of analysing such aspects but the underlying methods still have some limitations regarding specific system setups. Up to date, only task sets, which consist of tasks that are activated according to a standard event model can be analysed appropriately. To lift this limitation, first steps towards exploring hierarchical event models are taken. Future Results will be integrated into SymTA/S to further enhance its applicability.

Power Optimization under Timing Constraints (TU Braunschweig) Cooperation with Sharon Hu and Bren Mochocki from University of Notre Dame.

Based on the power analysis extension to SymTA/S which was realized in cooperation with Bren Mochocki during the first project year, TU Braunschweig and University of Notre Dame implemented heuristic and stochastic power optimization algorithms using DVS and SVS (Dynamic/Static Voltage Scaling). The presented algorithms are applicable to complex distributed systems with complex timing constraints (maximum jitter, end-to-end deadlines, etc.), and are capable of determining Pareto-optimal design trade-offs between system power consumption and timing properties.

The heuristic power optimization approach is based on research of TU Braunschweig related to sensitivity analysis [RHE06], whereas the stochastic algorithms utilize the compositional SymTA/S design space exploration framework [HRJ+06].

The results of this activity lead to a joint publication at the International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (CASES) [RHE+06].

Robustness Optimization for Distributed Embedded Systems (TU Braunschweig) Based on the results achieved in the domain of sensitivity analysis [RHE06], TU Braunschweig developed techniques for optimizing the robustness of embedded real-time systems with respect to variations of system properties like worst-case execution/communication times, bus bandwidth, CPU clock rate, input data rate, etc. Reasons for such variation during the design process or in the field include updates, bug fixes, late feature requests, and product variants.

The developed algorithms consider hard-real time constraints and are capable of optimizing a given system for static and dynamic design robustness. Thereby, the static design robustness optimization approach is applicable to the design scenario where system parameters are fixed early in the design process, whereas dynamic design robustness optimization approach includes possible counteractions to unforeseen system property changes, and is thus applicable to reconfigurable systems.

The results of this research will be published at the International Conference on Hardware - Software Codesign and System Synthesis 2006 (CODES) [HRE06].

Flex Film: High-resolution Real-time Digital Film Applications (TU Braunschweig) In the context of the FlexFilm project, TU Braunschweig developed a multi-board, multi-FPGA hardware/software architecture, for computation intensive, high resolution (2048x2048 pixels), real-time (24 frames per second) digital film processing. The architecture reaches record performance running a complex noise reduction algorithm (used both as example and proof of concept) including a 2.5 dimensions DWT and a full 16x16 motion estimation at 24 fps requiring a total of 203 Gops/s net computing performance and a total of 28 Gbit/s DDR-SDRAM frame memory bandwidth. This design was awarded with the "DATE2006 Design Record" distinction [LHR+06].

Simulation-based analysis of SoC interconnection architectures (University of Bologna) Industrial MPSoC platforms exhibit increasing communication needs while not yet reverting to revolutionary solutions such as networks-on-chip. The limited scalability of shared busses is being overcome by means of multi-layer communication architectures. However, the complex interaction among system components and the dependency of macroscopic performance metrics on fine-grain protocol features stress the importance of highly accurate modelling and analysis tools. The work in this area has focused on developing accurate functional model of multi-node on-chip interconnects, as they are currently deployed in high-complexity SoCs today.

Network-on-chip architectures (Technical University of Denmark) In the second year the group at the Technical University of Denmark has further developed the NoC architecture called MANGO (Message-passing Asynchronous Network-on-Chip providing Guaranteed services over OCP interfaces). In particular the network core, i.e. the routers and links. MANGO is based on clockless circuit techniques, and thus inherently supports a GALS (Globally Asynchronous Locally Synchronous) type design flow. This is an advantage in large scale SoC design, since the distribution of a global clock is becomming increasingly difficult. MANGO employs virtual channels to provide connection-less best-effort routing as well as connection-oriented virtual circuits, for which service guarantees can be given. The predictability of guaranteed services is a way to promote system-level integrity. The MANGO architecture has been demonstrated through a circuit-level design of a 5x5 router using a 0.13 m CMOS standard cell library from STMicroelectronics. Netlist simulations showed a performance of 650 Mflits/s under typical timing conditions [BS06]. Three patents [BS05] on the MANGO technology have been filed and a startup company, called Teklatech, was formed as a spin-off from this research. Teklatech is developing a one-step EDA solution to achieving timing closure in large scale, globally synchronous, deep submicron ASIC designs.

Distributed wireless sensor networks (Technical University of Denmark) Besides the further development for extending the capabilities of the ARTS system-level modelling framework towards the modelling of wireless sensor networks (reported under the System Modelling Infrastructure action), a sensor node development platform [VLMB05] has been developed, implemented and build. The aim of the platform is to explore hardware/software tradeoffs when designing the node behavior and to calibrate the developed system-level models with real design implementations. In order to efficiently utilize the limited resources available on a sensor node, key design parameters needs to be optimized which is only possible by making system-level design decisions about its hardware and software (operating system and applications) architecture.

Simulation-based analysis of SoC interconnection traffic (Technical University of Denmark and University of Bologna) In Multi-Processor System-on-Chip (MPSoC) design stages, accurate modeling of IP behaviour is crucial to analyze interconnect effectiveness. However, parallel development of components may cause IP core models to be still unavailable when tuning communication performance. Traditionally, synthetic traffic generators have been used to overcome such an issue. However, target applications increasingly present non-trivial execution flows and synchronization patterns, especially in presence of underlying operating systems and when exploiting interrupt facilities. This property makes it very difficult to generate realistic test traffic. Technical University of Denmark and University of Bologna have jointly developed a reactive traffic generator device [MAMBS05] capable of correctly replicating complex software behaviours in the MPSoC design phase. The approach has been validated by showing cycle-accurate reproduction of a previously traced application flow. Even when tested under complex synchronization scenarios, including asynchronous interrupts involving OS interaction in a multiprocessor environment, the proposed traffic generator is able to reproduce IP traffic with full capability to express the application flow.

Keynotes, Workshops, Tutorials

Workshop: Workshop on Distributed Embedded Systems Leiden, Netherlands, November 2005 Collaboration with various research groups in the area of performance analysis of embedded systems. There exist almost no results on comparisons of system level performance estimation and analysis methods for embedded systems in literature. One of the main problems that prevents such results is that there exists no consensus on how these methods should be compared. To overcome this problem, we co-organized an international workshop on distributed embedded systems. The workshop aimed to achieve three goals: first to identify issues and trends of system level performance estimation and analysis of distributed embedded systems, secondly to learn about existing system level performance estimation and analysis methods for embedded systems, and thirdly to establish a set of benchmark applications that can serve as basis for future methods comparisons. To achieve these three goals, the workshop was split into three modules. During the first two days, a set of presentations from various researches served as basis for discussions on issues and trends of system level performance estimation and analysis of distributed embedded systems. On the third day, a number of existing analysis and estimation methods were discussed. Also on the third day, all attendees were invited to propose benchmark applications for method comparisons. Discussions on these applications led to a set of benchmark applications that were then published on a webpage. The fourth day was dedicated to experimenting with the various methods, and to obtaining first results on the set of benchmark applications.

After the workshop, we compared five existing performance estimation and analysis methods and tools, based on a part of the benchmark application set. These methods and tools were: Modular Performance Analysis with Real-Time Calculus, SymTA/S, MAST, Timed Automata with UppAal, and SystemC simulation. The results of this comparison were published in a Masters Thesis [Pera06]. In future, we plan to publish an article on the methods comparison, together with Rolf Ernst from TU Braunschweig. See it online!

Workshop: Design Issues in Distributed, Communication-Centric Systems DATE Conference, Munich, Germany, 10.3.2006 Organisers: Bruno Bouyssounouse, Rolf Ernst, Lothar Thiele 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. View it online!

Workshop: New approaches to WCET analysis York, England 30.7.-5.8.2006 Organisers: Jan Staschulat, Technical University of Braunschweig, Guillem Bernat Rapita Systems. The workshop was set up to discuss new approaches to WCET analysis. In particular synergy effects between the SymTA/P and the RapiTime approach were examined.

Workshop: Robustness Optimization and Scheduling Anomalies Linköping, Sweden, August 2006 Organisers: Petru Eles, Arne Hamann, Razvan Racu During the workshop recent results of TU Braunschweig concerning system robustness optimization and the detection of scheduling anomalies were presented and discussed. Additionally, a cooperation in the field of simulation pattern generation based on the scheduling anomalies detection algorithms was discussed.

Tutorial: Introduction to Sensor Networks ARTIST2 PhD Course, University of Linkoping, Sweden, May 2006 Speaker: Jan Madsen and Srdjan Capkun from DTU. Phd course on wireless sensor networks. Organized in cooperation between DTU and Linkoping. Participant were from both academia and industry, mainly from Sweeden. Sensor networks have become more and more popular as a solution to various large scale networked applications in very diverse areas. This course is an introduction to the problematic of sensor networks. The course addresses issues such as deployment and localization, routing protocols and operating systems for wireless sensor networks, design methodologies and security issues. View it online!

Tutorial: Supporting Predictable Design Using Formal Analysis Techniques ARTES Summer School, Nässlingen, Sweden – August, 2006 ARTES is a Swedish network for real-time research and graduate education, which annually organizes a summer school for leading researchers and graduate students in real-time systems. The tutorial presented the state of the art in formal performance verification (task and system level), and explained how these techniques can be used to design predictable systems using sensitivity analysis and robustness optimization algorithms. View it online!

Tutorial: Frameworks for System-Level Analysis of Real-Time Systems - Symta/S and MPA Real-Time and Embedded Technology and Applications Symposium (RTAS), San Jose, USA – April, 2006 RTAS is the leading international conference in real-time applications and is co-located with the Embedded Systems Conference. System-level timing, performance, and power become increasingly intractable as the interactions between system parts introduce complex dynamic behaviour that can not be fully overseen by anyone in a design team. It is agreed that appropriate analysis tools are urgently needed. However, today's dynamic design processes require flexible and extensible tool suites that can cope with and be adapted to changed objectives and new requirements. Furthermore, the trend towards IP reuse and black-box integration introduces another type of complexity as it requires clear interfaces and must cope with only partially available information. The tutorial addressed recent research on composable and extensible analysis methods, and tools that demonstrate the application in practice. The tutorial was targeted to embedded system architects, component designers, and integrators as well as researchers in these fields. View it online!

Mini-Keynote: Modular Communication-Centric MPSoC Architectures MpSoC Summer school, Estes Park, Colorado, August 2006 Speaker: Rolf Ernst The keynote presented distributed memory access analysis techniques for MPSoC modelling and analysis to leading researchers and industrial managers in System-on-Chip design. View it online!

Publications Resulting from these Achievements

[1] [PPE+06] Timing Analysis of the FlexRay Communication Protocol, Traian Pop, Paul Pop, Petru Eles, Zebo Peng, Alexandru Andrei. 18th Euromicro Conference on Real-Time Systems (ECRTS 06), Dresden, Germany, July 5-7, 2006, pp. 203-213
[2] [IPE+06] Synthesis of Fault-Tolerant Schedules with Transparency/Performance Trade-offs for Distributed Embedded Systems, Viacheslav Izosimov, Paul Pop, Petru Eles, Zebo Peng. Design Automation and Test in Europe Conference (DATE 2006), Munich, Germany, March 6-10, 2006, pp. 706-711
[3] [MBT+06] Clemens Moser, Davide Brunelli, Lothar Thiele, Luca Benini, Real-Time Scheduling with Regenerative Energy, 8th Euromicro Conference on Real-Time Systems (ECRTS 06), Dresden, Germany, July, 2006.
[4] [WTVL06] Ernesto Wandeler, Lothar Thiele, Marcel Verhoef and Paul Lieverse: System Architecture Evaluation Using Modular Performance Analysis — A Case Study. Software Tools for Technology Transfer (STTT), Springer, pages to appear, 2006.
[5] [WTVL06] Ernesto Wandeler, Lothar Thiele, Marcel Verhoef and Paul Lieverse: System Architecture Evaluation Using Modular Performance Analysis — A Case Study, 1st International Symposium on Leveraging Applications of Formal Methods (ISoLA), Paphos, Cyprus, October, 2004
[6] [Pera06] Simon Perathoner, Evaluation and Comparison of Performance Analysis Methods for Distributed Embedded Systems, Masters Thesis, Computer Engineering and Networks Laboratory, ETH Zurich
[7] [RHE06] Razvan Racu, Arne Hamann, Rolf Ernst, A Formal Approach to Multi-Dimensional Sensitivity Analysis of Embedded Real-Time Systems. In Proc. of the 18th Euromicro Conference on Real-Time Systems (ECRTS), Dresden, Germany, July 2006
[8] [RHE+06] Razvan Racu, Arne Hamann, Rolf Ernst, Bren Mochocki, Sharon Hu, Methods for Power Optimization in Distributed Embedded Systems with Real-Time Requirements, In Proc. International Conference on Compilers, Architectures, and Synthesis for Embedded Systems (CASES), Seoul, Korea, October 2006
[9] [HJR+06] Arne Hamann, Marek Jersak, Kai Richter, Rolf Ernst, A framework for modular analysis and exploration of heterogeneous embedded systems, Real-Time Systems, volume 33, pages 101-137, July 2006
[10] [HRE06] Arne Hamann, Razvan Racu, Rolf Ernst, A formal approach to robustness maximization of complex heterogeneous embedded systems, In Proc. International Conference on Hardware/Software Codesign and System Synthesis (CODES), Seoul, Korea, October 2006
[11] [LHR+06] Amilcar do Carmo Lucas, Sven Heithecker, Peter Rüffer, Rolf Ernst, Holger Rückert, Gerhard Wischermann, Karin Gebel, Reinhard Fach, Wolfgang Huther, Stefan Eichner, Gunter Scheller, A reconfigurable HW/SW platform for computation intensive high-resolution real-time digital film applications, In Proc. Design Automation and Test in Europe Conference (DATE), Munich, Germany, March 2006
[12] [VLMB05] Virk, K., Leopold, M., Madsen, J., Bonnet, P., Hansen, M., Design of A Development Platform for HW/SW Codesign of Wireless Integrated Sensor Nodes, EUROMICRO Symposium on DIGITAL SYSTEM DESIGN, 2005.
[13] [MAMBS05] Mahadevan, S., Angiolini, F., Madsen, J., Benini, L., Sparsø, J., Realistically Rendering SoC Traffic Patterns with Interrupt Awareness, in the proceedings of the IFIP International Conference on Very Large Scale Integration (VLSI-SoC), 2005.
[14] [BS06] T. Bjerregaard and J. Sparsø. Implementation of Guaranteed Services in the MANGO Clockless Network-on-Chip. IEE Proceedings: Computing and Digital Techniques, Vol. 153 no. 4, July, 2006, pp 217 - 229.
[15] [BS05] T. Bjerregaard and J. Sparsø. A network, a system and a node for use in the network or system, 2005. DK and US patents submitted, DK serial no. PA 2005 00306 and US no. 60/656,375.

ARTIST2 Participants: Expertise and Roles

Prof. Lothar Thiele – TIK, ETH Zürich (Switzerland)
developing a calculus to describe the performance of communication-centric systems, unifying the models for computation and communication.
Prof. Petru Eles – ESLAB, Linköping University (Sweden)
schedulability analysis for heterogeneous distributed systems, communication synthesis.
Prof. Rolf Ernst – IDA, TU Braunschweig (Germany)
formal performance models for networks-on-chip. Prof. Luca Benini – Micrel Lab, University of Bologna (Italy)
analytic and simulation based models for performance, power and area of NoCs.
Prof. Jan Madsen – Technical University of Denmark (Denmark)
power issues in network on chip architectures.

Affiliated Participants: Expertise and Roles

Dr. Fabian Wolf – Volkswagen AG (Germany)
Software integration under real-time constraints.
Dr. Magnus Hellring – Volvo (Sweden)
Requirements analysis
Dr. Kai Richter – Symtavision (Germany)
Performance analysis of complex distributed systems.
Prof. Sharon Hu – University of Notre Dame (USA)
Power analysis and optimization.

Resource-aware Design

Ulrike Woern — 2006-10-13T14:48:04Z

Activity Leaders: Peter Marwedel (University of Dortmund) Luca Benini (University of Bologna)

Artist2 Clusters:
Execution Platforms
Compilers and Timing Analysis

Contents
Baseline
Previous Work
Problem Tackled in Year2
Current Results
Keynotes, Workshops, Tutorials
Related Publications
Participants

Abstract
Provide, through the integration of research activities of many participants, a viable path for resource-aware software and hardware development. The final objective is to achieve integration of research activities in concrete deliverables:
A set of tools that can interact and work together and demonstrate the achievable optimizations on a particular hardware platform.
A methodology that enables the design of predictable embedded systems with a special focus on issues that cut several layers of abstraction, such as hardware and compiler design.

Baseline

The importance of resource awareness in embedded systems is growing rapidly. The limited availability of computing resources is preventing the introduction of new products and applications, especially is areas where high-performance embedded systems are required (e.g. in telecom and consumer markets). Resources include energy, computational power and hardware components.

Minimization of the energy consumption plays a major role in the design of embedded systems. Limited availability of energy is the dominating constraint for many advanced embedded systems, in particular those involving multimedia or sensor technologies. At the start of the project, only a very limited number of energy models were available. Optimizing systems for minimized energy consumption at the software level was more an exception. Exploitation of memory hierarchies for minimizing the energy consumption was at an infant state.

Also, maximizing the computational power of embedded systems is becoming of increasing importance due to the wide-spread deployment of high-performance multimedia-enabled devices in the market. The increasing trend towards encrypted communication also increases the performance requirements. As a result the efficient use of available hardware components, most importantly of processors and memories, is mandatory. When the project was started, customized processors were in use, but the generation of tools chains for processors was a mainly manual process. Support for multiprocessor systems was almost completely lacking.

With the growing software content in embedded systems and the diffusion of highly programmable and re-configurable platforms, software is given an unprecedented degree of control on resource utilization. This relation between hardware and software layers can be used to perform aggressive optimizations that can be achieved only by a synergistic approach that combines the advantages of static and dynamic techniques.

Previous Work

Work achieved in the first 6 months Cooperation was established between the Universities of Bologna and Dortmund. The objective was to integrate the memory-aware compiler developed in Dortmund with the multi-processor platform simulator developed in Bologna. The first results were the definition of a standard format for the executable output of the compiler, as well as for the memory allocation information. This output format is supported by the platform simulator.

Cooperation was furthermore established between the Universities of Bologna and Aachen. The objective is to extend the modelling capabilities of the platform simulator developed in Bologna toward heterogeneous multi-core architectures, exploiting the Application-specific Processor development framework based on the LISA architecture description language developed in Aachen. The first result of this work was the definition of a standardized wrapping protocol which allows any SystemC core description generated by Aachen tools to be instantiated (multiple times) as a core in the platform simulator by Bologna.

Work achieved in months 6-12 The cooperations established in the first six months were continued and were significantly strengthened, as a significant amount of technical work was performed to sustain them. More specifically:
The cooperation between Bologna and Dortmund required the development of a new souce-level transformation tool for performing memory optimizations by Dortmund, and the development of compatible memory organization models by Bologna (including I and D caches as well as scratchpad memories).
The cooperation between Aachen and Bologna required extensive re-design of Bologna's core interfacing protocol within the platform simulator. On the other hand, Aachen has provided extensive technical support on Lisatek core wrapping architectures and toolsets. An additional cooperation between Bologna and Saarland University was established. The objective of this cooperation is the exploitation of the platform simulator developed at Bologna, more specifically of the timing accurate core models incorporated in the simulator, as targets for the worst case execution analysis framework developed in Saarland University.

Milestones
Established a working path between the memory-optimizing compiler developed at Dortmund and the platform simulator developed at Bologna. This tool interoperability path was validated during a visit of Dortmund's research staff to University of Bologna in July 2005
Development and extensive benchmarking of the LISATek-MPARM bridge: Several heterogeneous platforms were instantiated and tested. Performance analysis was performed.

Problem Tackled in Year2

In general, a tight integration between the software and hardware layers is a key approach for coping with resource constrains. Research in year 2 addressed all embedded system resources which are available only in tightly limited amounts:

Coping with energy constraints has been a research goal in several groups involved in this activity and it has also been the goal of co-operations.
The particular problem addressed by the Linköping group during this period has been that of on-line approaches for voltage scaling and dynamic body biasing. The goal was to address both dynamic and leakage power and, as opposed to static approaches, to also make use of the dynamic slack resulting from the fact that tasks execute for less than their worst case execution times (WCET). Shut-down of processors, very important for leakage power reduction, has also been considered. One of the main challenges was that such an on-line approach has to be of very low complexity.
Dortmund improved the software support for memory hierarchies. Possible solutions include architectures containing small, fast memories called scratch pads and compilers that map memory objects to these memories at compile-time, rather than at run-time. Such compilers must be aware of the resource “memory hierarchy”. In year 2, improvements for the existing optimization tools were the target. These improvements concerned the support for multiple processes, the integration of various models and their simulation and the generation of run-time support for scratch pad management.
Limited computational power is a second constraint.
Highly optimized processors can be designed with tools that support the creation of tool chains for application-specific instruction set processors. This particular problem is tackled by the Aachen group by providing a method for generating tool chains for application-specific processors. In year 2, the problem tackled was to tighten the interface between the LISATek tools designed at Aachen and tools designed at other partners, in particular at Bologna. The goal included the accurate prediction of the performance of a complex multiprocessor system, enabled by the MPARM virtual platform from Bologna. This required the generation of models for hardware components typically found in systems on a chip. Towards this end, compatible models of interrupt and peripheral components had to be generated. Compatibility between the LISATek and MPARM environments had to be provided. Furthermore, efficient use of memories is becoming more and more important as the speed gap between processors and memories widens. The DTU group has focused on resource aware multiprocessor design space exploration, taking into account memory, buffer and power constraints.
A third goal of the resource aware design activity is to provide timing predictable designs. Current computer architectures are optimized towards excellent average performance. For hard real-time systems, the worst case behaviour is what counts. As a consequence, for example, memory hierarchies improving the worst case behaviour and not just the average case behaviour are necessary. Timing predictability was tackled by six groups. The Linköping group focussed on WCET calculations for multiprocessors, while the two groups at Saarbrücken worked on generating tighter bounds for access times to caches. Support for scratch pads, as studied by Dortmund, also establishes tight bounds on the WCET. Analysing of these bounds has been a target in the second year. Improved knowledge about the real-time behaviour of components was the target of the work at ETH Zurich and EPFL. The six groups discussed ideas for designing predictable systems. A joint research proposal was filed by five of the six groups.

Current Results

Energy efficient time constrained systems Power models as well as a simulation environment for validation have resulted from cooperation of the University of Linköping with the Bologna group. As the first step, an approach for mono-processor systems has been elaborated, implemented and published [And05].

During the last six months the efforts have concentrated on an extension of this approach to multiprocessor systems. This work is currently performed as part of the ARTIST mobility action in cooperation with the Dortmund group and will be continued into the following period.

Predictability in Multiprocessor SoC architectures Besides being energy efficient and having a high performance, for many applications it is required that multiprocessor SoC implementations are highly predictable with respect to their timing behaviour. This problem has been addressed by the Linköping group during this period. While this issue has been previously investigated in the context of mono-processor systems, available results are inapplicable to modern multiprocessor architectures in which, for example, due to the shared memory access and shared buses, the individual WCETs of tasks depend on the global system schedule. Providing WCET guarantees and reliable schedules in this context is extremely challenging. It involves issues related to bus protocols and control, WCET analysis, system level scheduling and optimizations. With regard to the "classical" aspect of WCET analysis the group is building on the Symta/P tool from the Braunschweig group (a member of the (“execution platform” cluster). The Linköping group is also interacting with the Bologna group with regard to the issues of bus control.

This work is an effort started at the beginning of 2006. The overall concept has been elaborated, solutions have been developed and tools are under implementation. Publications and further results are expected in the following period. View it online!

Integration of LISATek ISS models in SystemC and the MPARM virtual platform The issues arising from the integration of LISATek ISS models in SystemC and the MPARM virtual platform have been investigated in more detail [Ang05], especially concerning the interaction with level one (L1) memories. A new MPARM functional model was developed to handle the L1 memory. It was also useful to cluster other functionality within the same block. The end result is called a “processor tile”, comprising LISATek-generated SystemC model of the processor and the most tightly coupled components (see fig. 1). The following component models were developed:
a timer device,
an emulated serial port,
a simple interrupt controller. The first component is vital if attempting to port an operating system. The second is very useful for debugging purposes; placing it next to IP cores, instead of in a shared location accessible to all system processors, has the advantage of allowing for independent input/output, and prevents debug traffic from spilling onto the system interconnect where it could pollute performance statistics. Finally, the interrupt controller is both a requirement of the other two devices and a crucial component to develop efficient synchronization mechanisms in multiprocessor systems. The controller is externally attached to a set of system-level wires which convey inter-core interrupts. On the IP core side, a simple interrupt handshaking protocol was implemented at Bologna. In this protocol, the value of interrupt registers is copied on some LISATek core pins which are polled every cycle by the core to take proper action. The interrupt controller is memory mapped to let the core reset the pending interrupt flags and configure the masking status.

Figure 1: Processor Tile.

Figure 2: Memory Aware Compilation and Simulation Tool-Chain.

Memory Aware Compilation and Simulation Tool-Chain for Energy Optimizations During the last reporting period, the need for a coherent tool chain for energy optimizations and for exploration of memory hierarchies across different system architectures was recognized. Therefore, a memory aware tool-chain supporting uni-processor ARM, multiprocessor ARM and M5 DSP based systems was developed (see fig. 2). Both the simulation and compilation subsystems are configured from a single memory hierarchy description. In addition, a common energy database is used by the memory optimizers in the compilation subsystem as well as by the memory and multi-processor SoC simulators in the simulation subsystem. The developed tool-chain optimizes input application code for a given memory hierarchy [Ver06d, Weh06] and also evaluates the optimization by simulating the optimized executable on the same memory hierarchy. The tool-chain is developed due to the cooperation between University of Dortmund and University of Bologna, as the simulation subsystem includes the multi-processor SoC simulation from Bologna while the compilation subsystem is developed at Dortmund. Moreover, both partners have agreed on a common memory hierarchy description format, which will be used for developing future optimizations [Ver06c]. View it online!

Design-Time Memory Allocation Techniques for Multi-Process Applications with Aperiodic Processes Previous work at Dortmund proposed compile-time or design-time memory allocation approaches to share the scratchpad memory among the periodic processes of a multi-process application. The current work extends the previous work and proposes memory allocation approaches for applications consisting of aperiodic tasks. This significantly increases the complexity of the memory allocator as the arrival times of the processes are completely unknown at design time. Therefore, the memory allocator is divided into an intelligent design-time component and a simple run-time component.

The design-time component of the memory allocator works in the following stepwise manner. First, it identifies memory objects, i.e. code segments and data variables, which on scratchpad allocation lead to reduction in the energy consumption of the system. Second, it processes the application code to enable the movement of memory objects at runtime. Finally, it inserts blocking statements in the application code to prevent unsafe movement of memory objects. The runtime component, depending upon the current set of active processes and the current state of the scheduled process, allocates (de-allocates) memory objects to (from) the scratchpad memory. Experiments report that a two-phased memory allocator minimizes the energy consumption due to applications with aperiodic tasks [Ver06a, Ver06b]. View it online!

Operating System Support for Online Allocation of Scratchpad Memories The goal of this work at Dortmund is to develop a runtime memory allocator which keeps track of the execution behaviour of the application and allocates scratchpad memory with memory objects (code segments and data variables) at runtime. The runtime allocator of this approach is more complex than the design-time memory allocator described above. At compile time, attributes such as access counts and the size are computed for each memory object. These attributes are then supplied as input to the memory allocator. The allocator based upon the input attributes, the scratchpad memory utilization and the current execution pattern swaps memory objects in and out of the scratchpad memory. Several heuristics as well as analytical approaches have been proposed for the online allocation of the scratchpad memory. The proposed approaches have been integrated into the RTEMS operating system. Experiments demonstrate that for highly dynamic applications, significant energy savings can be achieved. View it online!

Analysis of cache predictability First quantitative results have been obtained on the predictability of different cache architectures. A paper is in preparation. Improvement of timing analysis by integration with code synthesis The University of Saarbrücken and AbsInt (an industrial member of the compiler cluster) have cooperated with ETAS (an external company) on the integration of the ASCET-SD model-based design tool with the AbsInt timing analyzer aiT. This work is continuing. A paper was published by Ferdinand et al. [Fer06]. View it online!

Resource aware design space exploration The Technical University of Denmark (DTU) has developed a multi-objective design space exploration environment based on the PISA environment for multi-objective optimization from the group of Lothar Thiele, ETH Zurich. The exploration is based on a genetic algorithm to solve the problem of mapping a set of task graphs onto a heterogeneous multiprocessor platform. The objective is to meet all real-time deadlines subject to minimizing system cost and power consumption, while staying within bounds on local memory sizes and interface buffer sizes. The approach allows for mapping onto a fixed platform or onto a flexible platform where architectural changes are explored during the mapping. This work will be continued. A paper has been accepted for publication at DIPES 2006 [Mad06]

FET Open Call project proposal A consortium from within ARTIST2 consisting of the Universities of Saarbrücken, Zürich, Bologna, Pisa and Dortmund as well as AbsInt has applied for a project on “Reconciling Performance with Predictability” in the FET Open Call. Both short and long proposals have passed all thresholds. However, only 5% of the proposed projects can be funded, and this project will probably not be among them.

Interfaces for real-time components Between members of the group of Tom Henzinger (EPFL) and Lothar Thiele (ETHZ) there have been intensive discussions on interface based design of embedded systems. There were common meetings and presentations. The main concept is to extend the common idea of static types towards resource types that talk about the use of various resources by a component, e.g. power, time, computing resources. As a result, the concept of interface-based design (by Tom Henzinger) has been successfully applied to real-time systems and associated publications have been written [Hen06, Thi06, Cha06]. View it online!

Resource awareness in sensor networks The University of Bologna cooperated with ETH Zürich on resource awareness in sensor networks. For a full description please refer to the report on progress within the execution platform cluster.

Difficulty: LISATek Compatibility LISATEK versions distributed by Europratice were frequently not based on recent versions of Linux. The cooperation between the Universities of Aachen and Saarbrücken would benefit from a shorter update cycle.

Keynotes, Workshops, Tutorials

Keynotes: Peter Marwedel: Towards laying common grounds for embedded system design education, Opening, Embedded Systems Week (at Manukau Institute of Technology)
Auckland, New Zeeland, Nov. 16th, 2005. The talk proposed an approach for introducing embedded systems at the college level.

Mini-Keynote: Jan Madsen: Evolving MPSoC Solutions
MPSoC Symposium, Colorado.
A key challenge of implementing an embedded systems application on a heterogeneous multiprocessor SoC platform is to find the right partitioning of the application onto the platform architecture. The right partitioning is dependent on the characteristics of the processors and the network connecting them, as well as the application. The mini-keynote addressed this challenge. View it online!

Workshop: SCOPES: 9th International Workshop on Software and Compilers for Embedded Systems
Dallas, US – Sept. 29th – Oct. 1st, 2005
Software for embedded systems with emphasis on code generation for embedded processors. View it online! View it online!

Tutorial: Peter Marwedel: Code optimizations for efficient embedded systems (at SCOPES 2005)
Dallas, US, Sept 29th, 2005
The tutorial presented various code transformations aiming at improving the efficiency of embedded software, taking the limited resources of embedded systems into account.

Tutorial: Luca Benini: System Level Power Optimization (at course on Advanced Digital Design, organized by EPFL)
Lausanne, Switzerland, Oct. 8th, 2005
The tutorial presented the main issues in power optimization (under various types of resource constraints) at the system level. The tutorial aimed at industrial as well as academic attendees. View it online (for the 2006 edition)!

Tutorial: Rainer Leupers: Retargetable Compilation (at course on Advanced Digital Design, organized by EPFL)
Lausanne, Switzerland, Oct. 6th, 2005 (morning). The tutorial presented techniques for generating compilers from descriptions of the instruction set architecture (ISA). The tutorial aimed at industrial as well as academic attendees. View it online (for the 2006 edition)!

Tutorial: Peter Marwedel: Memory-architecture aware compilation (at course on Advanced Digital Design, organized by EPFL) Lausanne, Switzerland, Oct. 6th, 2005 (afternoon) The tutorial presented the benefits resulting from making compilers aware of the memory architecture. Significant reductions in terms of consumed resources (energy, time) can be achieved. The tutorial aimed at industrial as well as academic attendees. View it online (for the 2006 edition)!

Tutorial: Peter Marwedel: Code optimizations for efficient embedded systems (at Manukau Institute of Technology) Auckland, New Zealand, Nov. 17th, 2005 The tutorial presented various code transformations aiming at improving the efficiency of embedded software, taking the limited resources of embedded systems into account.

Tutorial: Lothar Thiele: Frameworks for System-Level Analysis of Real-Time Systems - Symta/S and MPA RTAS 2006 Tutorial IEEE Real-Time and Embedded Technology and Applications Symposium: System-level timing, performance, and power becomes increasingly intractable as the interactions between system parts introduce complex dynamic behaviour that can not be fully overseen by anyone in a design team. The tutorial addressed recent research on composable and extensible analysis methods, and tools.

Tutorial: Lothar Thiele: Sensor Networks DATE 2006 Symposium This tutorial reviewed basic concepts of wireless sensor networks, including: ad-hoc networking, programming models, power management, in-network processing, development environments and methodologies.

Tutorial: Lothar Thiele and Peter Marwedel: ARTIST2 Spring School in China on Models, Methods and Tools for Embedded Systems Xi'an, China, April 3rd-15th, 2006 The tutorial started with an introduction to embedded systems and resource aware generation of software and performance analysis. It also comprised modelling of real-time systems, validation and verification. View it online!

Publications Resulting from these Achievements

[1] [And05] Alexandru Andrei, Marcus Schmitz, Petru Eles, Zebo Peng, Bahir M. Al-Hashimi: Overhead-Conscious Voltage Selection for Dynamic and Leakage Energy Reduction of Time-Constrained Systems, IEE Proceedings Computers & Digital Techniques, Volume 152, Issue 1, 2005, pp. 28-38.
[2] [Ang06] Federico Angiolini, Jianjiang Ceng, Rainer Leupers, Federico Ferrari, Cesare Ferri, Luca Benini: An Integrated Open Framework for Heterogeneous MPSoC Design Space Exploration, Proceedings of the Design, Automation and Test in Europe Conference and Exhibition 2006, Munich, Germany, Mar 6-10, 2006, pp. 1145-1150.
[3] [Cha06] Samarjit Chakraborty, Lothar Thiele, Ernesto Wandeler, Nikolay Stoimenov: Interface-Based Rate Analysis of Embedded Systems, submitted to RTSS 2006.
[4] [Fer06] Christian Ferdinand, Reinhold Heckmann, Hans-Joerg Wolff, Christian Renz, Oleg Parshin, Reinhard Wilhelm. Towards Model-Driven Development of Hard Real-Time Systems – Integrating ASCET-MD and aiT/StackAnalyzer. In Proceedings of the Automotive Software Workshop in San Diego, 2006, San Diego, USA, March 2006.
[5] [Hen06] Thomas A. Henzinger and Slobodan Matic: An interface algebra for real-time components, Proceedings of the 12th Annual Real-Time and Embedded Technology and Applications Symposium (RTAS), IEEE Computer Society Press, 2006.
[6] [Mad06] Jan Madsen, Thomas K. Stidsen, Peter Kjærulf, Shankar Mahadevan: Multi-Objective Design Space Exploration of Embedded System Platforms. Accepted for publication: DIPES 2006, Portugal, 2006.
[7] [Thi06] Lothar Thiele, Nikolay Stoimenov, Ernesto Wandeler: Real-Time Interfaces for Composing Real-Time Systems. To be published: EMSOFT 2006, Seoul, 2006.
[8] [Ver06a] Manish Verma, Peter Marwedel: Advanced Memory Optimization Techniques for Low-Power Embedded Processors. In Fundamentals and Methods for Low-Power Information Processing (Ed. Baerbel Mertsching), Springer, Dordrecht, The Netherlands, 2006.
[9] [Ver06b] Manish Verma: Advanced Memory Optimization Techniques for Low-Power Embedded Processors, PhD Thesis, University of Dortmund, Germany, 2006.
[10] [Ver06c] Manish Verma, Lars Wehmeyer, Robert Pyka, Peter Marwedel, Luca Benini: Compilation and Simulation Tool Chain for Memory Aware Energy Optimizations, SAMOS 2006, 6th International Workshop, p. 279-288.
[11] [Ver06d] Manish Verma, Peter Marwedel: Overlay Techniques for Scratchpad Memories in Low Power Embedded Processors, IEEE TVLSI, vol. 14, no. 8, August 2006.
[12] [Weh06] Lars Wehmeyer, Peter Marwedel: Fast, Efficient and Predictable Memory Accesses, Springer, 2006.

ARTIST2 Participants: Expertise and Roles

Prof. Dr. Luca Benini - University of Bologna (Italy)
Power modelling and OS integration.
Prof. Dr. Petru Eles - University Linköping (Sweden)
Dynamic and leakage power optimisation for real-time system, accurate system-level power modelling for communication.
Prof. Dr. Tom Henzinger – EPFL (Switzerland)
Virtual machines for hard real-time computing, Embedded Machine; Schedule-Carrying Code
Prof. Dr. Rainer Leupers - RWTH Aachen (Germany)
Processor modelling tools.
Prof. Dr. Jan Madsen, Technical University (TU) of Denmark (Denmark)
Power modelling and resource aware design space exploration.
Prof. Dr. Peter Marwedel - University of Dortmund (Germany)
Memory architecture aware code generation
Prof. Dr. Reinhard Wilhelm - University of Saarbrücken (Germany)
Time as a resource.
Prof. Dr. Lothar Thiele – ETH Zürich (Switzerland)
Cooperating on concepts for real-time components (but not included in budget).

Affiliated Participants: Expertise and Roles

Roberto Zafalon – STM (Italy)
Dynamically controlling power consumption in MPSoC platforms.

Seeding New Research Directions in Real-Time Components

Ulrike Woern — 2006-10-03T11:52:05Z

Artist2 Clusters:
Real-Time Components
Control for Embedded Systems
Execution Platforms

Activity Leaders: Albert Benveniste (INRIA)

Bengt Jonsson (Uppsala)

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.

Development of UML for Real-time Embedded Systems

Ulrike Woern — 2006-10-03T09:12:57Z

Artist2 Cluster:
Real-Time Components

Activity Leader:

François Terrier (CEA/LIST)

Abstract
A framework for handling central aspects of Real time Systems in UML-based notations, and in UML-based system development. This will influence standardization and allow European UMLbased tool providers to have a larger impact.

Participants

The full list of participants is available here.

Baseline

Since the adoption of the UML standard and its new advanced release UML2, this modeling language has been used for development of a large number of time-critical and resourcecritical systems. Based on this experience, a consensus has emerged that, while a useful tool, UML is lacking in some key areas that are of particular concern to real-time and embedded system designers and developers. In particular, it was noticed that first the lack of quantifiable notions of time and resources was an impediment to its broader use in the real-time and embedded domain. Second, the need for rigorous semantics definition is also a mandatory requirement for a widespread usage of the UML for RT/E systems development. And third, specific constructs were required to build models using artifacts related the real-time operating system level such as task and semaphore.

Fortunately, and contrary to an often expressed opinion, it was discovered that UML had all the requisite mechanisms for addressing these issues, in particular through its extensibility facilities. This made the job much easier, since it was unnecessary to add new fundamental modeling concepts to UML – so-called “heavyweight” extensions. Consequently, the job consisted in defining a standard way of using these capabilities to represent concepts and practices from the real-time and embedded domain.

Hence, this specification of a UML™ profile adds capabilities in one hand for modeling Real Time and Embedded Systems (RTES), and in other hand for analyzing schedulability and performance properties of UML specifications. This new profile is intended to replace the existing UML Profile for Schedulability, Performance and Time [UML profile for Schedulability, Performance, and Time, version 1.1., formal/05-01-02, 2005]. This extension, called the Marte profile, should address specification, design, and verification stages of the development cycle of RTES. It wants to address the two branches of the V cycle, i.e. modeling and validation& verification. Modeling capabilities have to ensure both hardware and software aspects of RTES in order to improve communication/exchange between developers. It has also to foster the construction of models that may be used to make quantitative analysis regarding hardware and software characteristics. Finally, it should enable interoperability between developments tools used all along the development process.

Problem Tackled in Year 2

Continue the year1 work in order to develop a UML-based proposal defining model constructs for modelling and analysising of real-time and embedded systems. Special focus is put on representing resources, timing, RT/E qualities of service, communication modes, execution modes, component model.

Within this year 2, we also continued to review and suggest changes to the Open Management Group (OMG - responsible for defining the UML standard) by providing inputs on standardization of UML profiles specific to real-time systems: the UML profile for MARTE.

The second year of this activity has been also time to start experiments of the Marte standard through realizations of case studie and connections with analysis tools such as schedulablity analysis tools.

Previous Work

The first year of this activity has been dedicated to firstly influence on the writing of the request for proposal (RFP) of the new UML profile for real-time and embedded systems. This RFP expresses all the requirements the new standard will have to satisfy. The RFP, document referenced at omg web server as realtime/05-02-06 (UML Profile for Modeling and Analysis of Real-Time and Embedded systems (MARTE) RFP)) has been voted in the context of the Realtime, Embedded, and Specialized Systems (RTESS) Platform Task Force in February 2005: UML Profile for Modeling and Analysis of Real-Time and Embedded systems (MARTE) RFP, realtime/05-02-06.

Within the second half year period, the job consisted in both following action (main part of this work has been performed within the French CARROLL-Protes project):

To setup an OMG submitter team in order to answer to the RFP. The team that has been organized is called the ProMARTE team: www.promarte.org. This team consists of the main companies (end users and toolprovider) involved in this aaspect at the OMG. It is composed of: Artisan, Carlton university, CEA, IBM, I-Logix, INRIA, Looked-Martin, Thales, Tri-Pacific.
To write the intial submission of the ProMARTE team that has been delivered in Novembre 2005: Joint UML Profile for MARTE Initial Submission, realtime/05-11-01.

Within this first year, in the context of the Omega project, Verimag aimed at the definition of an UML profile appropriate for real-time embedded systems based on the existing SPT profile. The extension done in Omega introduces a notion of "observer" and emphasizes the importance of capturing the relevant events which make reference to the system at execution and is used to capture its dynamic properties.

Current Results

A consolidated architecture for the Marte profile

The Marte profile architecture model consists of three main packages:

The Time and Concurrent Resource Modeling package (TCRM); it defines basic model constructs for time and resource, especially concurrent resources. This foundational concepts are then refined in both following package in order to fit with both modeling and analyzing concerns.
The RealTime and Embedded application Modeling package (RTEAM); it enables modeling of RT/E application. It concerns mainly defining in one hand high-level model constructs to depict real-time and embedded features of application, and in other hand to enable the description of execution platforms, software as well as hardware.
The RealTime and Embedded application Analysis; it provides a generic support for analyzing annotated models. This generic framework is also refined in order to cope with schedulability and performance analysis. It is also expected that the generic framework for analysis will be specialized/extended to support other kind of quantitative analysis, such as power consumption, memory use or reliability.

Figure 1. Current architecture of the Marte profile

Keynotes, Workshops, Tutorials

Workshop: MARTES 2005 - Modelling and Analysis of Real Time and Embedded Systems, MoDELS/UML 2005, Int. Conf. on Model Driven Engineering Languages and Systems, Montego Bay, Jamaica, Oct. 4, 2005. Verimag and CEA have been the initiators of this workshop on model-driven development and real-time and embedded systems as a follow-up event on the successful workshop series on Real time embedded systems SIVOES and SVERTS. MARTES has been hold in October 2005 as a satellite event of the MODELS conference. The workshop attracted a number of interesting submissions and participants. The results of the workshop, as well as 2 best papers have been published in an LNCS volume.

Presently, we are actively preparing the second edition, to be held on October 2 or 3, 2006 in Genova, Italy in conjunction with the 9th International Conference on Model Driven Engineering Languages and Systems, MoDELS/UML 2006. View it online!

Summer school: MDD for Distributed Real Time Embedded Systems, Brest, France – September 4-8, 2006 This summer school was co-organized by CEA. It is the third edition of a series of summer school which focuses on model-driven related issues in the context of real-time and embedded systems development. The main goal of this summer school series is to provide participants with the most up-to-date information needed to understand and apply MDE approaches to the development of distributed, real-time and embedded systems. For that purpose, we have gathered experts from a variety of research labs and industries to give seminars that provide insights into the ongoing research works and practical applications related to MDE for DRES View it online!

Tutorial: Status and perspectives of the UML profile for Marte MDD for Distributed Real Time Embedded Systems Summer School, Brest, France – September 4-8, 2006. Sébastien Gérard gave this tutorial on Marte. The current architecture of th new OMG standard for real-time and embedded systems has been presented and some specific technical focuses has been done: the non-functional property framework, the sub-profile for modelling software execution resources and the subprofile for model-based schedulability analysis. View it online!

Tutorial: UML for Real Time Systems Artist Summerschool on Component & Modelling, Testing & Verification, and Statical Analysis of Embedded Systems, Nässlingen, Sweden, September 29 to October 2, 2005 Sébastien Gérard gave this tutorial on UML for real-time systems. The talk has been focused on native concepts of UYML2 for real-time and on its extenssions (profiles) specically dedicated to real-time modelling and analysis. View it online!

ARTIST2 Participants: Expertise and Roles

Dr. Susanne Graf – VERIMAG (Fr)
Areas of his team's expertise: modelling of real-time components.
Pr. Jean-Marc Jezequel – INRIA (Fr)
Areas of his team's expertise: UML Meta-model.
Dr. Julio Medina - Cantabria University (Sp)
Areas of his team's expertise: model-based schedulability analysis.
Dr. Sébastien Gérard – CEA (Fr)
Areas of his team's expertise: standard modelling and RT/E domains.

Affiliated Participants: Expertise and Roles

Pr. Ivica Crnkovic – MdH
Areas of his team's expertise: component models.
Dr. Leader: Stefan van Baelen - K.U. Leuven (Be)
Areas of his team's expertise: QoS specification.
Dr. Bernhard Josko – OFFIS (Ge)
Areas of his team's expertise: real-time UML.
Dominique Potier – Thalès Research and Technology (Fr)
Areas of his team's expertise: standardization and case study from the aerospace or telecommunication domain.
Dr. Matthias Grochtmann – DaimlerChrysler (Ge)
Areas of his team's expertise: specification, design and implementation of automotive systems.

JTRES 2006

Ulrike Woern — 2006-09-24T19:43:29Z

50. Organisation

Ulrike Woern — 2006-09-21T12:16:20Z

The Course Organizers:

The Course is organized by the ARTIST2 Network of Excellence, and the Department of Control Engineering of the CTU in Prague.

Program Hanzalek Zdenek Czech Technical University in Prague Karlovo námestí 13, Prague http://dce.felk.cvut.cz/hanzalek/

Editor Krakora Jan Czech Technical University in Prague Karlovo námestí 13, Prague krakorj (at) control.felk.cvut.cz http://dce.felk.cvut.cz/krakora/

Administration Kurkova Linda Czech Technical University in Prague Karlovo námestí 13, Prague > kurkova (at) control.felk.cvut.cz

40. Programme & Course Materials

Ulrike Woern — 2006-09-21T12:02:31Z

Course Materials

Full version of the Course Materials (29 MB)

Program of Graduate Course on Embedded Control Systems

Monday 3rd of April 8:00 Registration 8:30 M1 Motivation and examples, Bengt Eriksson and Martin Torngren, 1.5 hour (KTH) 10:00 Coffee 10:15 M2 Control issues, Pedro Albertos, 2 hours (UPVLC) 12:15 Lunch 13:45 M3 RT issues, Alfons Crespo, 2 hours (UPVLC)

Tuesday 4th of April 9:00 T1 Kernels and safe (back-up) operation, Pedro Albertos and Alfons Crespo, 1 hour (UPVLC) 10:00 Coffee 10:15 T2a Control design practical issues – principles, Bengt Eriksson, 1 hour (KTH) 11:15 T2b Control design practical issues – models, Jindrich Fuka, Jiri Roubal, 1 hour (laboratories K23 and K26 – CTU) 12:15 Lunch 13:45 T3 Integrated control design and implementation, Karl-Erik Arzen and Anton Cervin, 2 hours (LTH)

Wednesday 5th of April 8:00 W1 Control of Computing Systems, Karl-Erik Arzen and Anton Cervin (LTH) , 2 hours 10:00 Coffee 10:15 W2 Jitterbug and Truetime, Karl-Erik Arzen and Anton Cervin, 2 hours (laboratory K2 – LTH) 12:15 Lunch 13:45 W3 ECS Deployment, Bengt Eriksson and Martin Torngren, 2 hours (KTH )

Thursday 6th of April 8:00 Th1 Off-line scheduling, Zdenek Hanzalek, 2 hours (CTU) 10:00 Coffee 10:15 Th2 Platform for Advanced Process Control and Real Time Optimization, Vladimir Havlena and Jiri Findejs, 2 hours (Honeywell Laboratory Prague) 12:15 Lunch 13:45 Th3, RT practical issues, Michal Sojka and Ondrej Spinka, 2 hours (laboratory K09 – CTU)

Friday 7th of April 8:00 F1 TORSCHE Scheduling Toolbox for Matlab, Premysl Sucha and Michal Kutil, 2 hours (laboratory K2 – CTU) 10:00 Coffee 10:15 F2 Implementing Floating-Point DSP and Control with PicoBlaze Processors, Jiri Kadlec, 2 hours (CTU) 12:15 Closing remarks and discussion

Abstracts

M1 Motivation and examples, Bengt Eriksson and Martin Torngren, 1.5 hour (KTH) In this introductory session, the general problem of the course will be presented and motivated. What Embedded systems (ES) are? What Embedded control systems (ECS) are? Why? Motivating examples: inverted pendulum, mobile robot, car safety control. Main issues in the design of ECS: typical requirements, conflicting requirements, design trade-offs, typical architectures, design parameters.

M2 Control issues, Pedro Albertos, 2 hours (UPVLC) Real-time implementation of control algorithms in a multitasking environment involves a number of issues that should be taken into account. The unavoidable delays, both in computation and in data handling, the lost of data, the change of operation mode, the changes in sampling periods and the performance degrading are among the main issues to be considered. In this session, a review of these concepts for a general audience will be presented. The goal of this session would be to emphasize the relevance of these control design issues, to be strongly connected to the actual implementation of the control, to be discussed in the next sessions.

M3 RT issues, Alfons Crespo, 2 hours (UPVLC) The aim of this session is to introduce the most important concepts of ECS from the real-time (RT) systems perspective. The different types of RT tasks are introduced, and the importance of RT constraints is emphasized, especially in the context of control systems design. The central role of processor scheduling for guaranteeing RT constraints is motivated, and the main paradigms of RT scheduling are introduced. Fixed and dynamic priority scheduling methods are described, including temporal analysis methods. Resource usage and jitter control are also introduced. Finally, implementation approaches in view of the existing RT operating systems and programming languages technologies are discussed. The level of presentation of the topics is introductory, but a basic knowledge of operating systems, computer architecture, and programming in a high-level language is assumed.

T1 Kernels and safe (back-up) operation, Pedro Albertos and Alfons Crespo, 1 hour (UPVLC) ECS require to work in a variety of (unexpected) circumstances. The operating system (OS) should provide a number of basic options to guarantee the safe behaviour of ECS. In this session, a new set of operating services to provide the applications a higher control of faults and temporal constraints will be described. Some examples of this functionalities are: Execution timers, application defined scheduling, fault tolerant monitors, etc. From the control viewpoint, a hierarchical sorting of activities should be scheduled in agreement with the OS kernel to get the best, among the possible, control options. Safe (back-up) operation, basic control actions, optional and supervision are among the main issues to be discussed.

T2 Control design practical issues – principles and models, Bengt Eriksson (KTH), Jindrich Fuka, Jiri Roubal (CTU), 2 hours Introductory and simple exercises about control design using CACD (computer aided control design) packages will allow a better insight into the RT control design algorithms. Moreover, using some simple rigs, the participants will get some hands-on control design approaches. Some principles will be demonstrated on laboratory models.

T3 Integrated control design and implementation, Karl-Erik Arzen and Anton Cervin, 2 hours (LTH) This session will focus on the interaction between the control design and control implementation. In embedded systems, floating point arithmetic is sometimes too costly. The problems associated with fixed point arithmetic are discussed. The implementation platform normally introduces input-output latencies due to computation and communication delays. The effects of this on control performance and how it can be compensated for will be discussed. Special emphasis will be given to the recent jitter margin concept. The implementation platform also introduces jitter in sampling intervals. This will also be discussed. The control server is a computational model for controller tasks that combines the benefits of static scheduling and dynamic event-based scheduling. Changing controller task parameters such as sampling periods on-line could sometimes be useful in order to adapt to changing conditions. The problems associated with this and the risk of switching induced instabilities will be discussed.

W1 Control of Computing Systems, Karl-Erik Arzen and Anton Cervin, 2 hours (LTH) Using control-based approaches for modeling, analysis, and design of embedded computer and communications systems is currently receiving increased attention from the real-time systems community, as a promising foundation for controlling the uncertainty in large and complex real-time systems. The control-based approach has the potential to increase flexibility, while preserving dependability and efficiency. In this session we will give an overview of the work that is being done within the area with a special emphasis on two areas: Control of Web-servers and feedback scheduling of controller tasks. An inverted pendulum control example will illustrate some of the issues.

W2 Jitterbug and Truetime, Karl-Erik Arzen and Anton Cervin, 2 hours (laboratory K2 – LTH) A hands-on session/exercise where the users will become familiar with the two co-design tools Jitterbug and TrueTime. Jitterbug is a MATLAB-based toolbox that computes a quadratic performance criterion for a linear control system under various timing conditions. Using the toolbox, one can easily and quickly assert how sensitive a control system is to delay, jitter, lost samples, etc., without resorting to simulation. The tool is quite general and can also be used to investigate jitter-compensating controllers, aperiodic controllers, and multi-rate controllers. TrueTime is a MATLAB/Simulink-based tool that facilitates simulation of the temporal behavior of a multitasking real-time kernel executing controller tasks. The tasks are controlling processes that are modeled as ordinary continuous-time Simulink blocks. TrueTime also makes it possible to simulate simple models of communication networks and their influence on networked control loops.

W3 ECS Deployment, Bengt Eriksson and Martin Torngren, 2 hours (KTH ) The practical issues of ECS deployment will be discussed in this session, including: ECS implementation and platform selection (e.g. which type of OS?, which hardware?); OS configuration, components selection and loading (static vs dynamic OS types); Cross- compiling; Code generation; Verification and validation. A case study will illustrate the approach.

Th1 Off-line scheduling, Zdenek Hanzalek, 2 hours (CTU) The objective of this course is to provide an overview of different off-line scheduling problems found in embedded systems. In order to classify the scheduling problems, we show alpha|beta|gamma notation first. Then we develop several algorithms for real-time monoprocessor applications. Namely we show Bratley's branch&bound algorithm for Cmax optimization with release dates and deadlines and we underline main ideas of 0/1 programming solution for weighted completion time optimization with precedence constraints. The class of monoprocessor problems is concluded by minimization of maximum latency, i.e. Earliest Due-Date First algorithm and Earliest Deadline First algorithm. Finally we give an insight into the scheduling on dedicated processors and we provide examples on code synthesis for FPGA.

Th2 Platform for Advanced Process Control and Real Time Optimization, Vladimir Havlena, 2 hours (Honeywell Prague) The talk will demonstrate componentised architecture for Advanced Process Control and Real Time Optimization. The concept will be illustrated by the Unified Energy Solutions (UES) package developed by the Honeywell Laboratory in Prague, a portfolio of advanced control and optimization components for utilities and industrial energy, with the objective to operate the plant with maximum achievable profit (maximum efficiency) under the constraints imposed by technology and environmental impacts.

Th3, RT practical issues, Michal Sojka and Ondrej Spinka, 2 hours (laboratory K09 – CTU) In this laboratory exercise the students will learn, how to use the Linux for low level control of a laboratory model. The main goal of this session will be to control the velocity of a DC motor. The motor is actuated by a PWM signal realized via two bit outputs as one periodic thread. The measured velocity is derived from two phase-shifted signals while implementing IRC (Incremental Radial Counter) sensor as an aperiodic thread. The motor is connected to a PC using printer port through a simple electronics consisting of a motor driver and basic logic circuits. The organization of the session will be as follows (it is assumed the students know to write a simple RT Linux program, Session T3): First, the students will be provided with information on how to control parallel port circuits through the configuration registers. Second, the students will try to generate the PWM signal for motor control. Third, they will write the code to measure the rotation velocity and they will program a simple PID controller for velocity control. Finally the use of RT Linux will be discussed.

F1 TORSCHE Scheduling Toolbox for Matlab, Premysl Sucha and Michal Kutil, 2 hours (laboratory K2 – CTU) The aim of the seminar is to present a Matlab based Scheduling toolbox TORSCHE (Time Optimization of Resources, SCHEduling). The toolbox is intended mainly as a research tool to handle control and scheduling co-design problems. It offers a collection of data structures that allow the user to formalize various off-line and on-line scheduling problems. Potential of the toolbox will be shown on a high level synthesis of parallel algorithms.

F2 Implementing Floating-Point DSP and Control with PicoBlaze Processors, Jiri Kadlec, 2 hours (CTU) For developers using reconfigurable HW for the implementation of floating-point DSP and Control algorithms, one key challenge is how to decompose the computation algorithm into sequences of parallel hardware processes while efficiently managing data flow through the parallel pipelines of these processes. Lecture, will summarize our current experiences with architecture based on network of Xilinx PicoBlaze controllers on a single chip. Complete design path from model-based (Simulink) and C-based designs (Handel-C) to the concrete reconfigurable HW will be demonstrated.

Hanzalek Zdenek Czech Technical University in Prague Karlovo náměstí 13, Prague http://dce.felk.cvut.cz/hanzalek/