| Yves Sorel's Work |
Yves 
Sorel 
Research Director at INRIA in the Rocquencourt Research Unit, scientific co-leader of the AOSTE team.
Member of the OCDS (Tools for Design and Simulation of complex Systems) working group management committee of the System@tic Paris-Region Cluster.
My main topics of interest are in the field of Distributed Real-Time Embedded Systems.
I have been collaborating 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) (you can find here a french version) , allowing 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 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 the algorithms, the multicomponents, the implementations, and the executable codes. 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 operating on two kinds of graph, the algorithm graph and the architecture graph, and producing an algorithm graph as result. Thus, 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 optimized. A typical problem consists in finding the implementation which minimizes on the one hand the execution time of the algorithm while taking into account the cost of the inter-component communications, and on the other hand the number of components and communication media. This amounts to take into account a unique real-time constraint, namely the input-output latency equal to the input rate (cadence or period). We must use heuristics because this kind of optimization problem is NP-hard. Distribution and scheduling heuristics are derived from exact scheduling algorithms, only usable in the monoprocessor case. Indeed, as soon as the number of processor is greater than one the problem becomes NP-hard. The heuristics is based on a cost function taking into account the critical path and the schedule flexibility of the algorithm graph labeled by computation and communication durations. These durations are estimated or measured on the architecture target during a preliminary characterization step. Because optimized 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 for minimizing the number of components.
It is also possible to directly transform an algorithm graph into an architecture graph when an implementation onto a specific integrated circuit is intended, instead of an implementation of the algorithm onto a multicomponent. In this case the resulting architecture graph is a network of logical functions composing the data and the control paths. 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, then we also use greedy heuristics. This optimized integrated circuit may be used in turn as a non-programmable component in a multicomponent architecture.
Finally, an ultimate graph transformation allows us to automatically generate code: on the one hand a dead-lock free distributed real-time executives for each processors 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 in the multiprocessor case.
Research topics: graphs and partial order theories applied to parallelism and real-time, hardware architecture modeling (multicomponent), monoprocessor scheduling optimization for systems of tasks with multiple real-time contraints, multiprocessor distribution and scheduling optimization for systems through heuristics, automatic generation of distributed real-time executives for multiprocessor, automatic generation of data and control paths for application specific integrated circuit.
In 1990 a first version of a System Level CAD software based on the AAA methodology, was released. It was called SynDExV0 and written in SmallTalk until version V4. Version V5 was written in C++. Since the V6 version 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 "For i=1 to N Do ..." and "If cond=true Then ... Else ..." of the imperative languages.
SynDEx is a graphical interactive software, which offers the following services:
SynDEx is distributed free of charge download it !!!
As a tool for implementing algorithms under real-time and embedding constraints specified with specific high level languages, SynDEx is presently interfaced with:
We participated from 1997 to 1999 to an European Esprit project MODISTARC, intending to certify implementations of OSEK/VDX (Open systems and the corresponding interfaces for automotive, electronics) offering an operating system, communication and network management services.
We participated from 1998 to 2000 to an ARC (Action de Recherche Coopérative) of INRIA called TOLERE intending to propose 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 to a RNRT (Réseau National de Recherche en Télécommunication) project called PROMPT intending 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 to a RNTL (Réseau National des Technologies Logicielles) project called ACOTRIS (Analyse et Conception à Objets Temps Réel pour Implantation asynchrone/Synchrone), intending 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 are: CS-SI, MBDA, CEA-Leti, SITIA and INRIA.
I am the INRIA correspondent for national cooperations in the field of real-time embedded electronics, for the automobile industry. More informations about embedded electronics may be found in this press release.
We participated from 1999 to 2001 to a national project called AEE (Architecture Electronique Embarquée i.e. Embedded Electronics Architecture), intending to propose 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 to 2004 to 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.
I was the leader of the AEE Research and Development Action corresponding to these two preceding projects.
We participated from 2002 to 2004 to an ITEA european EUREKA project, called PROMPT2IMPLEMENTATION or P2I (it is issued from the PROMPT project), intending 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 to 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), intending to propose a seamless design-flow combining Scicos: a dynamic systems modeler and simulator with SynDEx for optimized distributed real-time implementation. Partners of this project are: CS-SI, PSA, CRIL and INRIA.
We are participating to a RNTL (Réseau National des Technologies Logicielles) project called MEMVATEX (Méthode de Modélisation pour la VAlidation et la Traçabilité des EXigences), intending to propose a modelling method based on UML2 for the validation of traceability of requirements for real-time embedded systems. Partners of this project are: SIEMENS-VDO, CEA, UTC, and INRIA.
We are participating to a RNTL (Réseau National des Technologies Logicielles) project called OpenEmbeDD, intending to propose an open-source plateform for Model Driven Engineering. Partners of this project are: Airbus, Anyware, CS, France Telecom, Thales, CEA, INRIA, LAAS, Verimag, and INRIA.
Within the SYSTEM@TIC PARIS-REGION Cluster, we are participating to the OpenDevFactory sub-project of the Usine Logicielle project, intending to propose model oriented engineering components in particular for distributed real-time embedded systems. Partners of this project are: Dassault, CS, EADS, EDF, Esterel Technologies, Hispano Suiza, IFP, MBDA, Softeam, Thales, Trialog, CEA, LIP6, University Paris Sud, Ecole Polytechnique, Supelec, and INRIA.
We are participating to an IST european project (FP5 call), called ARTIST (Advanced Real Time Systems) more precisely we are involved in the Action 1: "Hard Real-Time Systems" which intends to consolidate and further improve a strong European competence and know-how that is strategic for safety or mission critical applications (Synchronous languages-TTA- Fixed priority scheduling).
We are participating to an OMG working group intending to standardize a new UML2 profile called ProMARTE dedicated to real-time embedded systems.
Besides this, since 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.
I supervise PhD thesis related to the previous topics:
I give lectures in the Paris XI University (Orsay) DEA, the ENSTA (Paris) and ESIEE (Marne La Vallée) Engineer Schools.
We propose some trainee subjects, please contact me if you are interested.
Last update 2009 March 20 by yves.sorel@inria.fr :o) Bon'humeur