We study the use of Multiform Logical Time, as embodied in Esterel/SyncCharts and Clock Constraint Specification Language (CCSL), for the specification of assume-guarantee constraints providing safe driving rules related to time and space, in the context of Automated Driving Assistance Systems (ADAS). The main novelty lies in the use of logical clocks to represent the epochs of specific area encounters (when particular area trajectories just start overlapping for instance), thereby combining time and space constraints by CCSL to build safe driving rules specification. We propose the safe specification pattern at high-level that provide the required expressiveness for safe driving rules specification. In the pattern, multiform logical time provides the power of parameterization to express safe driving rules, before instantiation in further simulation contexts. We present an efficient way to irregularly update the constraints in the specification due to the context changes, where elements (other cars, road sections, traffic signs) may dynamically enter and exit the scene. In this way, we add constraints for the new elements and remove the constraints related to the disappearing elements rather than rebuild everything. The multi-lane highway scenario is used to illustrate how to irregularly and efficiently update the constraints in the specification while receiving a fresh scene.

Due to the mobility of autonomous vehicles and changing context through time, the constraints in safe driving rules specification need to be irregularly updated for monitoring the trajectory plan. This is not assumed in the Spatial-Temporal Logic. This paper proposes a novel approach to build the specification of assume-guarantee constraints providing safe driving rules related to time and space, in the context of Automated Driving Assistance Systems (ADAS). The novelty lies in that the specification adopts Multiform Logical Time to express the time constraints and provides spatial events generated by interactions on area trajectory for expressing space constraints. We propose the safe specification patterns at a high-level that provide the required expressiveness for safe driving rules. In these patterns, logical time provides the power of parameterization to express rules, before instantiation in low-level simulation contexts. The specification finally could be used to generate monitors that are executed on lower-level simulation engines with physical and topological features.

Synchronous languages, such as the recently proposed SCCharts language, have been designed for the rigorous specification of real-time systems. Their sound semantics, which builds on an abstraction from physical execution time, make these languages appealing, in particular for safety-critical systems. However, they traditionally lack built-in support for physical time. This makes it rather cumbersome to express things like time-outs or periodic executions within the language. We here propose several mechanisms to reconcile the synchronous paradigm with physical time. Specifically, we propose extensions to the SCCharts language to express clocks and execution periods within the model. We draw on several sources, in particular timed automata, the Clock Constraint Specification Language, and the recently proposed concept of dynamic ticks. We illustrate how these extensions can be mapped to the SCChart language core, with minimal requirements on the run-time system, and we argue that the same concepts could be applied to other synchronous languages such as Esterel, Lustre or SCADE.

International audience

The development of Cyber Physical Systems (CPS) requires to model both the cyber (i.e., digital) parts, the physical parts and the interaction between them. The state of the practice in such domain usually involves different stakeholders, which use dedicated modeling languages tailored syntactically and semantically to their domain. Functional Mock-up Interface (FMI) is a recent standard, which provides technical facilities to enable the co-simulation among the different dedicated modeling languages. In this context, this paper investigates how discrete-event models of the cyber part are supported by FMI standard for co-simulation. Two main results are presented: 1) how SystemC models can be integrated into the FMI environment and 2) FMI limitations for the efficient use of discrete-event models in co-simulation. Both results are illustrated by using a simple but illustrative use case mixing models in SystemC (for the cyber part) and Modelica (for the physical part).

The search for optimal mapping of application (tasks) onto processor architecture (resources) is always an acute issue, as new types of heterogeneous multicore architectures are being proposed constantly. The physical allocation and temporal scheduling can be attempted at a number of levels, from abstract mathematical models and operational research solvers, to practical simulation and run-time emulation. This work belongs to the first category. As often in the embedded domain we take as optimality metrics a combination of power consumption (to be minimized) and performance (to be maintained). One specificity is that we consider a dedicated architecture, namely the big.LITTLE ARM-based platform style that is found in recent Android smartphones. So now tasks can be executed either on fast, energy-costly cores, or slower energy-sober ones. The problem is even more complex since each processor may switch its running frequency, which is a natural trade-off between performance and power consumption. We consider also energy bonus when a full block (big or LITTLE) can be powered down. This dictates in the end a specific set of requirements and constraints, expressed with equations and inequations of a certain size, which must be fed to an appropriate solver (SMT solver in our case). Our original aim was (and still is) to consider whether these techniques would scale up in this case. We conducted experiments on several examples, and we describe more thoroughly a task graph application based on the tiled Cholesky decomposition algorithm, for its relevant size complexity. We comment on our findings and the modeling issues involved.

There is now a consistent corpus of models and methods for software/hardware codesign (scope of MeMoCoDe). Still, while success is quite established at both ends of the spectrum (High-Level hardware Synthesis, and System Engineering), the adoption of such Software modeling approach inside mainstream Software Engineering communities could easily be improved. This is certainly so because some of the principles of application modeling do not exactly match, or elsewhere do not focus upon the same concerns, as traditional coding style. Putting forth the relevant important concepts for application modeling, while investigating their relevance to traditional engineering experience, is certainly a way to counter confusion. We view the notion of Multiform Logical Time as such a fundamental concept. In a first part of the talk we consider the premises of Multiform Logical Time in Embedded Design (its origin, its relevance at places of design flows); in a second part we introduce a small declarative language to express logical time properties, study its expressiveness and its associated analysis techniques.

The advent of chip-level parallel architectures prompted a renewal of interest into dataflow process networks. The trend is to model an application independently from the architecture, then the model is morphed to best fit the target architecture. One downplayed aspect is the mapping of communications through the on-chip topology. The cost of such communications is often prevalent with regard to computations. This article establishes a dataflow process network called K-periodically Routed Graph (KRG), which serves the role of representing the various routing decisions during the transformation of a genuine application into a architecture-aware version for this application.

To deal with the high complexity of embedded systems, engineers rely on high-level heterogeneous models that combine functional and non-functional aspects, hardware/software artifacts, structural and behavioral descriptions. PRISMSYS is a system-level multi-view modeling framework, which provides a means to specify functional and non-functional aspects in interrelated views. Each concern/view is addressed separately with a dedicated set of models and correspondence rules, maintaining the semantic consistency between those different views. The behavioral specification mixes UML state machines with equational models defined as SYSML parametric diagrams. To supply a complete non-functional property-aware simulation environment, it is mandatory to formalize 1) the execution semantics of the UML state machines, 2) the SYSML parametric diagrams and 3) the coordination between them. This is achieved by using CCSL, the Clock Constraint Specification Language, to provide an event-based semantics for each model and their coordination. The proposed co-simulation framework combines TIMESQUARE, a discrete event simulator for CCSL, and Scilab, a tool for numerical computation. The framework is illustrated on a CPU thermal manager case study with a joint simulation of both its functional and non-functional models.

The Clock Constraint Specification Language (CCSL) is a formal polychronous language based on the notion of logical clock. It defines a set of kernel constraints that can represent both asynchronous and synchronous relations. It was originally developed as part of the UML Profile for MARTE to express causal and temporal constraints of Real-time and Embedded Systems. In this paper, we explore the use of CCSL for modeling scheduling requirements and to conduct schedulability analysis. For this purpose, a dedicated scheduling library of CCSL has been built. This library is endowed with a state-based operational semantics, and is applied to solve issues related to schedulability analysis and latency-insensitive design. We establish schedulability categories and latency-insensitiveness property in the context of the semantics, and solve those issues by using model checking techniques.

We propose a general method to characterize and synthesize correctness-preserving asynchronous wrappers for synchronous processes on a globally asynchronous locally synchronous (GALS) architecture. While a synchronous process may rely on the absence

An important step in model-based embedded system design consists in mapping functional specifications and their tasks/operations onto execution architectures and their resources. This mapping comprises both temporal scheduling and spatial allocation aspects. Therefore, we promote an approach which starts from loosely-timed/asynchronous models and proceeds by refining them to fully synchronized ones, using so-called clock calculus techniques under the architecture constraints. In this paper we provide a modeling framework based on an intermediate representation format, called clocked graphs, for polychronous endochronous specifications, which are the ones that can be safely considered for deterministic distributed real-time implementation using static scheduling techniques. Our formalism allows the specification of both "intrinsic" correctness properties of the specification, such as causality and clock consistency, and "external" correctness properties, such as endochrony, which ensure compatibility with the desired implementation architecture, including both hardware and software aspects. Using this formalism, we define a new method for distributed real-time implementation of synchronous specification. The move from (endochronous) synchronous specification to realtime scheduled implementation is a seamless sequence of model decorations.

In the real-time and embedded domain, systems tend to combine periodic and aperiodic computations. This leads to mixing event-triggered with time-triggered communications with their pros and cons. Then, modeling standards of the domain must provide mechanisms to support both kinds whereas historically they pertain to different communities: asynchronous and synchronous designers. In this paper, we compare the expressiveness of two standards of the domain (AADL and MARTE) to model these two kinds of communications. Specifically we focus on the time facilities of MARTE and on AADL models amenable to end-to-end flow latency analyses.

AADL and MARTE are both modeling formalisms supporting the analysis of real-time embedded systems. We investigate how MARTE, with its Time Model facilities, can be made to represent faithfully AADL periodic/aperiodic tasks communicating through event or data ports, in an approach to end-to-end flow latency analysis.

Synchronous reactive formalisms associate concurrent behaviors to precise schedules on global clock(s). This allows a non-ambiguous notion of "absent" signal, which can be reacted upon. But in desynchronized (distributed) implementations, absent values must be explicitely exchanged, unless behaviors were already provably independent and asynchronous (a property formerly introduced as endochrony). We provide further criteria restricting "reaction to absence" for correct desynchronization.

Marte (A UML Profile for Modeling and Analysis of Real-Time and Embedded systems) is a new UML profile extension for real-time and embedded systems, which is going to be standardized by mid 2007 at OMG (Object Management Group). This standard has been proposed by the "ProMarte" consortium, which consists of OMG end-users, tool providers and academics. Marte defines concepts in terms of UML extensions needed to model and analyze real-time and embedded systems (RT/ES). The Marte specification provides an annex which handles its relation to AADL-based models, and the way it may represent them.. Our purpose in this paper is to describe this relation. Our constructions will be presented and illustrated through some examples.

The theory of latency-insensitive design (LID) was recently invented to cope with the time closure problem in otherwise synchronous circuits and programs. The idea is to allow the inception of arbitrarily fixed (integer) latencies for data/signals traveling along wires or communication media. Then mechanisms such as shell wrappers and relay-stations are introduced to "implement" the necessary backpressure congestion control, so that data with shorter travel duration can safely await others with which they are to be consumed simultaneously by the same computing element. These mechanisms can themselves be efficiently represented as synchronous components in this global, asynchronously-spirited environment. Despite their efficient form, relay-stations and backpressure mechanisms add complexity to a system whose behaviour is ultimately very repetitive. Indeed, the "slowest" data loops regulate the traffic and organize the traffic to their pace. This specific repetitive scheduling has been extensively studied in the past under the name of "central repetitive problem", and results were established proving that so-called k-periodic optimal solutions could be achieved. But the "implementation" using typical synchronous circuit elements in the LID context was never worked out. We deal with these issues here, using explicit representation of schedules as periodic words on {0,1}* borrowed from the recently theory of N-synchronous systems.

This paper presents a new global MDA design methodology capable to bridge the gap between an abstract specification level and a heterogeneous architecture level while assisting real-time implementation. The P2I contribution is the result of a joint study on abstraction refinement methods and optimized mapping on architecture within a UML based design tools suite including SCADE/spl trade/ Suite for formal verifications and SynDEx for optimized distributed realtime implementation. The original points of this work are: i) a specification methodology that handles the control flow and the data flow representation, including efficient verifications, ii) a method for parallelism exploration based on abstract resources/performance estimation, iii) a HW/SW mapping approach that refines the specification into explicit HW configurations and the associated SW until executable distributed real-time code. The P2I framework shows how a cooperation of complementary methodologies and CAD tools associated with a relevant architecture can significantly improve the designer productivity, especially in the context of co-modelling for embedded design.

The design of embedded real-time systems requires skills from multiple specific disciplines, including, but not limited to, control, computer science, and electronics. This often involves experts from differing backgrounds, who do not recognize that they address similar, if not identical, issues from complementary angles. Design methodologies are lacking in rigor and discipline so that demonstrating correctness of an embedded design, if at all possible, is a very expensive proposition that may delay significantly the introduction of a critical product. While the economic importance of embedded systems is widely acknowledged, academia has not paid enough attention to the education of a community of high-quality embedded system designers, an obvious difficulty being the need of interdisciplinarity in a period where specialization has been the target of most education systems. This paper presents the reflections that took place in the European Network of Excellence Artist leading us to propose principles and structured contents for building curricula on embedded software and systems.

ESTEREL is a synchronous design language for the specification of reactive systems. Thanks to its compact formal semantics, code generation for ESTEREL is essentially provably correct. In practice, due to the many intricacies of an optimizing compiler, an actual proof would be in order. To begin with, we need a precise description of an efficient translation scheme, into some lower-level formalism. We tackle this issue on a specific part of the compilation process: the translation of loop constructs. First, because of instantaneous loops, programs may generate runtime errors, which cannot be tolerated for embedded systems, and have to be predicted and prevented at compile time. Second, because of schizophrenia , loops must be partly unfolded, making C code generation, as well as logic synthesis, nonlinear in general. Clever expansion strategies are required to minimize the unfolding. We first characterize these two difficulties w.r.t. the formal semantics of ESTEREL. We then derive very efficient, correct-by-construction algorithms to verify and transform loops at compile time, using static analysis and program rewriting techniques. With this aim in view, we extend the language with a new gotopause construct, which we use to encode loops. It behaves as a noninstantaneous jump instruction compatible with concurrency.

Synchronous languages such as Esterel can execute a series of statements in a single "instant" of time. If this series spans a loop iteration then it is possible that a computation local to the loop will have several distinct results during that "instant", which is referred to as schizophrenia. This makes the compilation of synchronous languages into more traditional computation models (such as C code or sequential logic) difficult. In a previous work (2004), we suggested to deal with schizophrenia through preprocessing in the Esterel language extended with a non-instantaneous jump statement. We now advocate for and experimented with such a program transformation, establishing the correctness, the completeness and the efficiency of our approach.

Several efficient compilation techniques have been recently proposed for the generation of sequential (C) code from Esterel programs. Consisting essentially in direct simulation of the reactive features of the language, these techniques need now to be accommodated with traditional issues of Esterel - the definition of formal semantics, the constructive causality, and the design of efficient and correct methods for analysis and optimization. We address some of these problems by defining a new intermediate model for the representation of Esterel programs. The new representation level preserves much of the initial program structure while making the control flow pattern and the hierarchical state structure explicit. It supports the full Esterel semantics, and it is a good support for efficient analysis, optimization, and code generation algorithms based on static analysis.

Twelve years ago, Proceedings of the IEEE devoted a special section to the synchronous languages. This paper discusses the improvements, difficulties, and successes that have occured with the synchronous languages since then. Today, synchronous languages have been established as a technology of choice for modeling, specifying, validating, and implementing real-time embedded applications. The paradigm of synchrony has emerged as an engineer-friendly design method based on mathematically sound tools.

We present SL, a new programming language of the synchronous reactive family in which hypotheses about signal presence/absence are disallowed. One can decide that a signal is absent during an instant only at the end of this instant, and so reaction to this absence is delayed to the next instant. Sources of causal circularities are avoided, while only weak preemption remains. A structural operational semantics is provided through rewrite rules, and an implementation is described. In addition to directly executing programs, this implementation can also be used to produce automata by symbolic evaluation.

The authors present the basics of the ESTEREL reactive model of synchronous parallel systems. The ESTEREL programming style, based on instantaneous communications and decisions, is illustrated through the example of a mouse handler. The ESTEREL formal semantics is described, and it is shown how programs can be compiled into finite state sequential machines for efficient execution. The implementation is described with the ESTEREL environment, including simulation, and verification and validation tools. Some ESTEREL uses in various contexts are reported.>