Yves Sorel
Research Director External Collaborator
at Inria in
the Paris Research
Center
in the KOPERNIC team.
Inria representative in the steering committe of
the Hub AEC
(Advanced Engineering & Computing) of the System@ticParis-Region Cluster.
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.
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.
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. A latency is a generalization of the typical
"end-to-end" constraint.
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.
Research topics
- Graphs and partial order
theories applied to parallelism and real-time;
- Heterogeneous and hybrid multiprocessor (multicore) hardware modelling (multicomponent);
- Uniprocessor preemptive or/and non preemptive real-time
scheduling with multiple contraints (deadline, generalized latency, data
dependence, strict periodicity, etc.) taking into account preemption and
operating system costs;
- Multiprocessor real-time scheduling with time and resource optimizations;
- Fault tolerance for processors and communication interconnects based on software
redondancy;
- Automatic generation of distributed real-time
executives for multiprocessor;
- Automatic generation of data and control paths
for application specific integrated circuit (ASIC & FPGA).
Generally speaking, the previous researh topics are applied to CPS (Cyber Physical Systems),
mainly critical ones, in domains of avionics, spatial, automotive, railway, drone, etc.
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 the version V4. The version V5 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 version V7 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:
- specification and verification of an application algorithm as a
conditionned data-flow graph or interface with a DSL,
- specification of a multicomponent graph (processors
and specific integrated circuits) or interface with a DSL,
- heuristic for distributing and scheduling the application algorithm onto the
multicomponent, with execution time and components optimization, these
heuristics are based on distributed real-time schedulability analyses,
- simulation of the real-time execution: visualization of predicted
performances for the multicomponent sizing,
- generation of distributed real-time executives, deadlock free and mainly
static, with optional real-time performance measurement. These executives are
built from a processor-dependent executive kernel with minimal
over-head. Presently executives kernels are provided for: TMS320CXX,
PIC18F2680, ADSP21060, i80X86, i80196, MC68332, MPC555, Transputer T800, and
UNIX/LINUX workstations. Executive kernels for other processors can be easily
ported from the existing ones.
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!!!
Teaching activities from 1995 to 2021
I teached graduate courses
on topics related to real-time scheduling for distributed
embedded systems: in the Master 2 of University Paris-Sud Orsay/Saclay, in the
Master 2 of University Paris-Est Marne-La-Vallée, in the Engineer
school ESIEE Marne-La-Vallée and in the Engineer school ENSTA Paris.
Download
the course handout in
french or in english .
PhD Thesis Supervision
I supervised PhD theses related to the previous topics:
- S. E. Saidi: Multicore real-time scheduling of hardware in the loop
co-simulation, in collaboration with team Real-Time IFP Energies
Nouvelles. End April 2018;
- F. Ndoye: Multiprocessor real-time preemptive scheduling accounting for
operating system costs. End April 2014;
- M. Marouf: Fault tolerant multiprocessor non preemptive real-time scheduling. End June 2012;
- P. Meumeu: Uniprocessor real-time scheduling taking into account preemption
costs. End April 2009;
- O. Kermia: Multiprocessor non preemptive real-time scheduling. End March
2009;
- N. Pernet: Mix of control-flow-state-machine and data-flow, mix of off-line
and on-line scheduling. End july 2006;
- M. Raulet: Hardware resource optimization mainly for memory, in
collaboration with team Image IETR/INSA and Mitsubishi ITE. End May 2006;
- H. Kalla: Fault tolerant distribution and real-time scheduling, in
collaboration with team BIP INRIA-Grenoble. End December 2004;
- L. Kaouane: Automatic synthesis of integrated circuit, in collaboration
with team A2SI ESIEE. End December 2004;
- L. Cucu: Uniprocessor non preemptive real-time scheduling for systems with
multiple constraints. End May 2004;
- R. Djenidi: Coupling of Scicos and SynDEx, in collaboration with team
METALAU INRIA-Rocquencourt. End July 2001;
- A. Dias: Automatic synthesis of integrated circuits, in collaboration with
team A2SI ESIEE. End July 2000;
- T. Grandpierre: Formal modeling of heterogeneous parallel architectures for
automatic generation of distributed real-time executive. End November
2000;
- R. Kocik: Modeling of Data-flow/Control-flow specifications satisfying
multiple real-time constraints. End March 2000;
- A. Vicard: Formal modeling of parallel implementations based on graphs. End
July 1999.
Industrial collaborations
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 participated from 2015 to 2018 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 participated from 2016 to 2019 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 participated from 2017 to 2021 in
a FUI (Fond Unique Interministériel) project,
called CEOS, whose purpose is to
deliver a reliable and secure system of inspections of pieces of works using
professional mini-drone. Several software applications will be developed,
adapted and integrated on the drone, in particular a real-time autopilot,
within an innovative multi-criticality
architecture and mixed criticality using multi-core hardware and a hypervisor
certifiable on the shelf. Partners of this project are: Thales Communications &
Security, RTaW, ADCIS, Alerion, DGAC, EDF, ENEDIS, ESIEE, Lorraine University,
Inria.
We started in 2019 to participate in
a PSPC-REGIONS (Projets Structurants Pour la Compétitivité) project called STARTREC,
whose purpose is the verification of critical embedded systems in the field of
autonomous vehicule. It aims at
proposing ISO26262 compliant arguments for the autonomous driving.
Partners of this project are: Easymile, StatInf, Trustinsoft, CEA and Inria.
We participated 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.
We participated in an OMG
working group intending to standardize a UML2 profile dedicated to real-time
embedded systems called MARTE.
Last update July 25th 2024
Contact: yves.sorel@inria.fr
|