Inria representative in the R&D steering committe of the SystemX Institute for Technological Research.
Distributed Real-Time Embedded Systems
My main topics of interest are in the field of Distributed Real-Time Embedded Systems.
I collaborated from 1982 to 1988 with the french research teams involved in the development of the Synchronous Languages: Esterel (Ecole des Mines Sophia Antipolis), Lustre (Imag Grenoble), Signal (INRIA Rennes).
In 1988 I began to work on a methodology called "Algorithm Architecture Adequation" (AAA ), see section 3.3 of this document. This methodology allows us to implement, taking into account real-time constraints, control, signal and image processing application algorithms specified with the Synchronous Languages semantics, on multicomponent architecture, i.e. a network of programmable (RISC, CISC, DSP processors, or microcontrolers) and/or non-programmable components (ASIC, FPGA), all together interconnected through different types of communication media (point-to point, multipoint) using shared memory or message passing as communication protocols.
The AAA methodology is based on graphs. They are used to describe application algorithms, multicomponents, implementations, and automatically generated codes. An application algorithm is specified by a graph, of possibly, dependent functions, whereas a multicomponent is specified by a graph of programmable and non-programmable components, and of communicating media. A possible implementation of a given algorithm onto a given multicomponent is obtained by transforming (distributing and scheduling) the initial algorithm graph, according to the architecture graph, into a new algorithm graph. In this sense, it corresponds to an external compositional law on the one hand operating on two kinds of graph, the algorithm graph and the architecture graph, and on the other hand producing an algorithm graph as result. The resulting algorithm graph has more vertices and edges than the initial algorithm graph. In addition the partial order associated with that resulting graph is smaller (less independent functions than in the initial graph), but consistent with the initial algorithm graph. Therefore, it is possible to describe, in intention, all the possible implementations of a given algorithm onto a given multicomponent.
The Adequation (meaning an efficient matching) consists in choosing, among the set of all the possible implementations of a given algorithm onto a given multicomponent, one implementation called "an optimized implementation". A typical problem consists in finding an implementation that satisfies deadline constraints equal to periods and minimizes on the one hand the total execution time of the algorithm (makespan) taking into account the cost of the inter-component communications, and on the other hand the number of components and communication media. We must use heuristics because that kind of optimization problem is NP-hard since it is equivalent to a "Bin-Packing" problem.
We chose the "partitioned approach" for the real-time scheduling of the algorithm functions onto the distributed architecture (multiprocessor) since the task migrations involved by the "global approach" has a prohibitive cost for the processors currently available on the market. Actually, functions become real-time tasks as soon as some timing characteristics are associated to that functions, i.e. period or minimum period, deadline, computation and communication durations, i.e. WCET (Worst Execution Time) and WCCT (Worst Case Communication Time). These heuristics are derived from uniprocessor real-time scheduling algorithms that are extended to the multiprocessor case. It uses a cost function based on the critical path and the schedule flexibility of the algorithm graph labeled by computation and communication durations. These durations are assessed from the executable code, or measured on the architecture target during a preliminary characterization step. Because rapid prototyping is intended, fast greedy heuristics are first used, and then we use iterative versions of these heuristics with back-tracking, in order to obtain more accurate results but less rapidely. We use meta-heuristics, i.e. heuristics that call other heuristics, for minimizing the number of components.
It is also possible to directly transform an algorithm graph into an architecture graph when an implementation of that algorithm, onto a specific integrated circuit, is intended, instead of an implementation of that algorithm onto a multicomponent. In this case the resulting architecture graph is a network of logical functions composing the data and the control paths of the specific integrated circuit. A transformation is chosen such that a good compromise is obtained, between the surface of the circuit and the execution time of the algorithm. Here again, the optimization problems are NP-hard, thus we also use greedy heuristics. This optimized integrated circuit may be used, in turn, as a non-programmable component in a multicomponent architecture.
Finally, a final graph transformation allows us to automatically generate code: on the one hand a dead-lock free distributed real-time executive for each processor of the architecture, and on the other hand a net-list for each integrated circuit of the architecture.
This global approach based on a common graph framework allows us to clearly state and solve hardware/software co-design problems since the multicomponent graph may be composed of non-programmable components (hardware) and programmable components (software).
Due to new applications, in the domains of avionics and automobile we are involved in, we need to take into account multiple real-time constraints, namely several latencies and periods, leading to more complex scheduling problems, and then to more complex distribution and scheduling problems in the multiprocessor case.
The first research topic we are interested in, concerns monoprocessor real-time scheduling. Beside the classical deadline constraint, often equal to a period, we take into consideration dependences beetween tasks and several, possibly related, latencies. A latency is a generalization of the typical “end-to-end” constraint. Dealing with multiple real-time constraints raises the complexity of that issue. Moreover, because the preemption leads to a waste of resources due to its approximation in the WCET (Worst Execution Time) of every task as proposed by Liu and Leyland, we first studied non-preemtive real-time scheduling with dependences, periodicities, and latencies constraints. Although a bad approximation may have dramatic consequences on critical real-time scheduling, there are only few researches on this topic. We have been investigating preemptive real-time scheduling since some years, but seeking the exact cost of the preemption such that it can be integrated in schedulability conditions and in the corresponding scheduling algorithms, is very complex. More generally, we are interested in integrating in the schedulability analyses the cost of the RTOS (Real-Time Operating System), for which the exact cost of preemption is the most difficult part because it varies according to the instance of each task. Finally, we investigate also the problem of mixing hard real-time and soft real-time constraints that arises in the most complex applications.
The second research topic concerns distributed real-time scheduling with embedding constraints. We use the results obtained in the monoprocessor case in order to derive solutions for the problem of multiprocessor (distributed) real-time scheduling according to the partitioned multiprocessor real-time scheduling approach. In addition to satisfy the multiple real-time constraints mentioned in the monoprocessor case, we minimize the total execution time (makespan) taking into account the cost of inter-processor communication since we deal with automatic control applications involving feedback. Furthermore, the domain of embedded systems leads to solving minimization resources problems. Since these optimization problems are of NP-hard complexity we develop exact algorithms (Branch & Bound, Branch & Cut) which are optimal for simple problems, and heuristics which are sub-optimal for realistic problems corresponding to industrial needs. Long time ago we proposed a very fast “greedy” heuristics whose results were regularly improved, and extended with local neighborhood heuristics, or used as initial solutions for metaheuristics such as variants of “genetic algorithm”. Also, we started to study semi-partitioned multiprocessor real-time scheduling where the number of migrations are minimized compared to global multiprocessor real-time scheduling approach.
Besides the spatial dimension (distributed) of real-time scheduling problems, other important dimensions are the type of communication mechanisms (shared memory vs. message passing), or the source of control and synchronization (event-driven vs. time-triggered). We explore real-time scheduling on architectures corresponding to all combinations of the above dimensions. This is of particular impact in application domains such as automotive and avionics.
Since real-time distributed systems are often safety-critical we address dependability issues, to tolerate faults in processors and communication interconnects. We maily focus on software redondancy, rather than hardware, to ensure real-time behaviour preservation in presence of faulty processors and/or communication media (where possible failures are predictively specified by the designer). We investigate fail silent and intermittent faults.
From 1990 to 2005 I have been the leader of a working group of research laboratories called GT7, involved in the field of Algorithm Architecture Adequation, within the framework of the GDR/PRC ISIS which is a national federation of laboratories working on Information, Signal, Image and Vision Processing. More precisely I am involved in methodologic studies.
SynDEx: System Level CAD software
In 1990 a first version of a System Level CAD software based on the AAA methodology, was released. It was called SynDEx V0 and written in SmallTalk up to version V4. The V5 version was written in C++. Since the version V6 released in 2000 SynDEx has been written in CamlTk. It offers new functionnalities such as hierarchical specification, with graphs repetition and/or graphs conditionning, resp. equivalent to control structures of the imperative languages "For i=1 to N Do ..." and "If cond=true Then ... Else ...". The current V7 version has an improved GUI, and mainly allows the user to specify multi-period algorithms, i.e. a period may be assigned to each algorithm operation with an implicit deadline equal to its period. In that case, each operation with a WCET and a period is equivalent to a real-time task.
As a tool for implementing algorithms under real-time and embedding constraints specified with specific high level languages, SynDEx is presently interfaced with domain specic languages (DSL) such as the synchronous languages (Esterel, SyncCharts, Signal) providing formal verifications, Scicos a Simulink-like language (access to the Scicos-SynDEx gateway), UML2.0 with the MARTE profile.
SynDEx is a graphical interactive software which provides the following features:
Since the executives are automatically generated with SynDEx, low level hand coding and debugging of multiprocessor real-time code are eliminated, consequently the development cycle duration of real-time applications is tremendously reduced.
SynDEx is distributed free of charge for Linux, Mac and Windows platforms, download it!!!
Take a look at a video demo of SynDEx!
I teach graduate courses on topics related to real-time scheduling for distributed embedded systems: University Paris-Sud (Orsay) Master 2, University Paris-Est (Marne-La-Vallée) Master 2, Engineer school ENSTA (Paris), and Engineer school ESIEE (Marne-La-Vallée).
Download the generic course handout (french).
I supervise PhD theses related to the previous topics:
We participated from 1997 to 1999 in an European Esprit project, called MODISTARC, whose purpose was to certify implementations of OSEK/VDX (Open systems and the corresponding interfaces for automotive, electronics) offering an operating system, and services for communication and network management.
We participated from 1998 to 2000 in an ARC (Action de Recherche Coopérative) of INRIA, called TOLERE, whose purpose was to provide a methodology for Fault Tolerant Embedded Real-Time Systems. This settled a strong cooperation on this topic with the POP-ART team of INRIA.
We collaborate with the INRIA project IMARA which aims at developing and experimenting new technologies for road transportation. In this context we use SynDEx in order to program applications for the semi-autonomous electric vehicule CyCab.
We participated from 1999 to 2000 in a RNRT (Réseau National de Recherche en Télécommunication) project, called PROMPT, whose purpose was to develop a CAD software for telecommunication applications implemented on multi-SoC (System on Chip). Partners of this project were: Thomson-CSF-Communications, Thomson-CSF-LCR, Simulog, Armines and INRIA. It is granted by the Research Ministry.
We participated from 2000 to 2003 in a RNTL (Réseau National des Technologies Logicielles) project, called ACOTRIS (Analyse et Conception à Objets Temps Réel pour Implantation asynchrone/Synchrone), whose purpose was to develop a design environment for complex real-time systems, based on the specification languages UML and SIGNAL, and the implementation language SynDEx. Partners of this project were: CS-SI, MBDA, CEA-Leti, SITIA and INRIA.
We participated from 1999 to 2001 in a national project, called AEE (Architecture Electronique Embarquée i.e. Embedded Electronics Architecture), whose purpose was to provide a methodology in order to develop complex real-time embedded applications in the field of transportation, specially for automobiles. The main goals are: independence between hard and soft, standard components and tools, cooperation between actors. Partners of this project were: AEROSPATIALE, PSA, RENAULT, SAGEM, SIEMENS, VALEO, IrCCyn, LORIA and INRIA.
We participated from 2002 in 2004 in an ITEA european EUREKA project, called EAST-EEA, which was an extension of the AEE project. The partners of this project were the same as in the AEE project minus AEROSPATIALE and SAGEM, and plus AUDI, BMW, Daimler-Chrysler, FIAT, OPEL, VOLVO, BOSH, Magneti-Marelli, SIEMENS, ZF, ETAS, VECTOR, Paderborn University, Linkoping University, Malardalen University, Technical University of Darmstadt.
Yves Sorel was the leader of the AEE Research and Development Action of INRIA corresponding to the two previous projects.
We participated from 2002 to 2004 in an ITEA european EUREKA project, called PROMPT2IMPLEMENTATION or P2I (it is issued from the PROMPT project), whose purpose was to develop, for telecommunication applications, a seamless environment from the specification with a new UML RTE (Real-Time Embedded profile) to the optimized implementation with AAA/SynDEx, through verification with Esterel Studio. Partners of this project were: Thales Telecommunication, Nokia, Esterel Technology, Tampere University, Turku University, LIFL, INRIA.
We participated from 2002 to 2005 in a RNTL (Réseau National des Technologies Logicielles) project, called ECLIPSE (Environnement intégré en logiciel libre pour la Conception, simuLation, réalIsation et mise-au-point des Systèmes temps réel Embarqués), whose purpose was to provide a seamless design-flow combining Scicos: a dynamic systems modeler and simulator with SynDEx for optimized distributed real-time implementation. Partners of this project were: CS-SI, PSA, CRIL and INRIA.
We participated from 2006 to 2009 in an ANR (Agence Nationale pour la Recherche) project, called MEMVATEX (Méthode de Modélisation pour la VAlidation et la Traçabilité des EXigences), whose purpose was to provide a modelling method based on UML2 for the validation through traceability of requirements for real-time embedded systems. Partners of this project were: Continental (formerly Siemens-VDO), Sherpa Engineering, CEA, UTC, and INRIA.
We participated from 2006 to 2009 in an ANR (Agence Nationale pour la Recherche) project, called OpenEmbeDD, whose purpose was to provide an open-source plateform for Model Driven Engineering based on generic modelling tools and specific real-time tools such as SynDEx. Partners of this project were: Airbus, Anyware, CS, France Telecom, Thales, CEA, INRIA, LAAS, Verimag, and INRIA.
Within the SYSTEM@TIC PARIS-REGION Cluster, we participated from 2006 to 2009 in the FUI (Fond Unique Interministériel) OpenDevFactory sub-project of the Usine Logicielle project, whose purpose was to provide model oriented engineering components in particular for distributed real-time embedded systems. Partners of this project were: Dassault, CS, EADS, EDF, Esterel Technologies, Hispano Suiza, IFP, MBDA, Softeam, Thales, Trialog, CEA, LIP6, University Paris Sud, Ecole Polytechnique, Supelec, and INRIA.
We participated from 2010 to 2014 in in an ITEA european EUREKA project project, called OPENPROD, whose purpose was to provide an open whole-product model-driven rapid systems development, modelling, and simulation environment integrating the leading open industrial software development platform (Eclipse) with open-source tools (OpenModelica, etc.), and industrial tools and applications. The partners of this project are: Bosh, Siemens, SKF, Nokia, IFP, EDF, PSA, EADS, LMS Imagine, VTT, CEA, Fraunhofer, etc.
We participated from 2010 to 2013 in a FUI (Fond Unique Interministériel) project, called PARSEC, whose purpose was to define a framework for the development of distributed real-time embedded systems that are subject to strict certification standards such as DO-178B (for avionics), IEC 61508 (for transportation systems), or ISO/IEC 15408 (the Common Criteria for information technology security evaluation). Code is generated for partitioned architectures using the APEX API from the ARINC standard. Partners of this project are: Thales, CEA, Elidiss, INRIA, Systerel, OpenWide, Alstom, and TelecomParisTech.
We participated from 2011 to 2015 in a FUI (Fond Unique Interministériel) project, called Project P, whose purpose was to define a "P"ivot format that allows the automatic generation of certified code for safety critical applications, from models specified with tools such as Simulink/Matlab, Scicos, Xcos, SysML, UML/MARTE, AADL, etc. Partners of this project are: Aboard, ACG, Airbus, Adacore, Altair, Astrium, Atos, Continental, ENPC, INRIA, IRIT, LABSTICC, ONERA, RCF, SAGEM, Scilab, STI, Thales-AS, Thales-AV.
We started in 2015 to participate in a FUI (Fond Unique Interministériel) project, called WARUNA, whose purpose is to provide an integrated tool chain for timing modelling, analysis and verification through the complete development cycle of Cyber-Physical Systems. Partners of this project are: Artal, ClearSy, RTaW, Thales, INRIA, LIAS.
We started in 2016 to participate in a ITEA 3 project, called ASSUME, whose general purpose is to provide, for future mobility solutions relying on smart components that continuously monitor the environment and assume more and more responsibility for a convenient safe and reliable operation, a safe multi-core development methodology that allows industry to deliver trustworthy new functions at competitive prices. Partners of this project are: Absint, Airbus, Arcelik, Articus System, BTC, BERNER & MATTNER, DAIMLER, ERICSSON, ESTEREL Technologies, FINDOUT Technologies, FORD OTOSAN, HAVELSAN, Kalray, KocSistem, MES, NXP, OFFIS, RECORE, Robert BOSH, SAGEM, SCANIA, SNECMA/SAFRAN, UNIT, VDL Bus & Coach, verum, Eindhoven University of Technology, ENS, FZI, INRIA, KTH, KIT, Kiel University, Koc University, Malardalen University, TNO, UPMC, TUM, University of Twente.
We participate in a NoE (Network of Excellence) on Embedded Systems called ARTIST initiated in the FP6 Artist2 NoE to become a virtual Center of Excellence in Embedded System Design. More precisely we are involved in both "Modelling & validation" and "Compilation & Timing Analysis" thematic clusters.
Last update November 20th 2016