Systèmes temporisés et hybrides
Evaluation laboratoires 2002-2005 - 8 septembre 2006 2
Membres
• Eugene Asarin, Prof. UJF (-2003)• Thao Dang, CR CNRS• Goran Frehse, MdC UJF (2006-)• Oded Maler, DR CNRS• Christophe Rippert, MdC UJF (2005-)• Stavros Tripakis, CR CNRS (-2005)• Sergio Yovine, DR CNRS
Evaluation laboratoires 2002-2005 - 8 septembre 2006 3
Doctorants
• Abdelkarim Kerbaa
• Ismail Assayad• Ramzi Ben Salah• Christos Sofronis*• Alexandre Donze• Scott Cotton• Moez Krichen*• Tarik Nahhal• Dejan Nickovic • Gillaume Salagnac• Colas Le Guernic• Aldric Degorre
Thèses soutenues:
• Yasmina Abdeddaim, 2002• Moez Mahfoudh, 2002• Gerardo Schneider, 2002• Marcelo Zanconi, 2004• Adrian Curic*, 2005
Evaluation laboratoires 2002-2005 - 8 septembre 2006 4
Domaines principaux de recherche
• Vérification, synthèse, test et surveillance pour les systèmes hybrides
• Méthodes efficaces pour l’analyse des systèmes temporisés
• Techniques avancées pour le développement
des systèmes embarqués
Evaluation laboratoires 2002-2005 - 8 septembre 2006 5
Systèmes hybrides : généralités
• Systèmes hybrides: modèles de systèmes à dynamique continue et discrète
• Automates hybrides: combinaison des automates et d’équations différentielles
• Concepts, théories, algorithmes et outils pour aider au développement et analyse de tels systèmes
• Exporter des idées venant de l’informatique vers des disciplines de génie et de sciences plus “physiques” (y compris la biologie)
Evaluation laboratoires 2002-2005 - 8 septembre 2006 6
Hybrid Systems: Reachability Computation
• Le problème majeur pour étendre la verif vers les systèmes continus et hybrides est le calcul d’états atteignables pour les équations différentielles soumises à des perturbations x’=f(x,v)
• Combinaison de techniques d’analyse numérique, géométrie algorithmique et algorithmes sur les graphes et automates
• Un calcul très difficile (dimensions, systèmes non linéaires)• Parmi les outils existants: CheckMate (CMU),d/dt (Verimag), Levelset toolbox
(Stanford), HysDel (ETH), VeriShift (Berkeley).
Systèmes hybrides : calcul d’atteignabilité
Evaluation laboratoires 2002-2005 - 8 septembre 2006 7
Systèmes hybrides: résultats principaux
• Systèmes PCD : Caractérisation complète de la dynamique sur le plan [Asarin, Yovine, Schneider]
• Systèmes linéaires: une amélioration énorme en performance, calcul d’états atteignables pour systèmes en 200 dimensions en utilisant des zonotopes [Le Guernic, Girard, Maler]
• Systèmes non-linéaires– Hybridisation: approximation des systèmes non-linéaires par
systèmes affines par morceaux (Asarin, Dang, Girard) – Équations algébriques: g(x’,x)=0 (Dang)– Techniques spécialisées pour systèmes bilinéaires x’= ax+bux+cu
et multi-affines x1’=x1x2x3+2x1+u (Asarin, Dang)
• Réduction de dimensions– Abstraction par projection: considérer des variables continus
comme des entrées incertaines (Asarin, Dang)
Evaluation laboratoires 2002-2005 - 8 septembre 2006 8
Systèmes hybrides: applications et outils
• Validation des systèmes de commande, par exemple contrôleurs automobiles (Dang)
• Vérification de petits circuits analogiques (Dang, Donze, Maler, Frehse)
• Analyse de réseaux biochimiques (Asarin, Dang)
• Implantation de notre outil d/dt, distribué gratuitement, et ayant des utilisateurs actifs aux USA(5), Allemagne(4), France(3), Pays Bas, Italie, Russie, Chine, Brésil.
Evaluation laboratoires 2002-2005 - 8 septembre 2006 9
Systèmes hybrides: test
• Pour des systèmes trop grands la verif est remplacée par la simulation
• Couverture de la partie atteignable d’espace des états par un nombre fini des trajectoires
• Combinaison de la recherche guidée et aléatoire inspirée par la planification des chemins en robotique (Dang, Nahhal)
• synthèse de contrôleur optimal par exploration intelligente des trajectoires (Donzé)
Evaluation laboratoires 2002-2005 - 8 septembre 2006 10
Systèmes hybrides: “monitoring”
• Formalismes pour la spécification de propriétés temporisées et hybrides (expressions régulières temporisées, logique temporelle des signaux)
• Nouveaux résultats théoriques à propos des logiques temps réel (Maler, Nickovic, Pnueli)
• Génération automatique de testeurs qui observent la sortie des simulateurs numériques et détectent la violation d’une propriété
Evaluation laboratoires 2002-2005 - 8 septembre 2006 11
Vérification légère (monitoring)
• Langage de spécification des propriétés de signaux analogiques et mixtes
• Génération automatique des observateurs de propriétés
• Un outil prototype déjà appliqué au modèle de mémoire FLASH
• Projet PROSYD (Maler, Nickovic)
• La base pour l’extension future (AMS) du standard PSL
Evaluation laboratoires 2002-2005 - 8 septembre 2006 12
Systèmes hybrides: : évaluation
• Parmi les fondateurs et leaders mondiaux dans le domaine
• Participation à la création de la série HSCC des colloques internationaux (100-150 participants), membre du comité du pilotage (chaire 2003-2006).
• Co-chaire du CP pour HSCC’03 (Prague)
• Organisation d’un atelier sur la vérification des circuits analogiques (Edinburgh ’05)
• Organisation d’un colloque sur la commande, le calcul et la biologie (Santa Barbara ’06, ~100 participants)
• Coordination des projets européens VHS (Verification of Hybrid Systems) et CC (Control and Computation) – projets européens principaux dans le domaine
Evaluation laboratoires 2002-2005 - 8 septembre 2006 13
• Un niveau d’abstraction extrêmement important entre le discret et le continu
• Une extension des automates par le temps quantitatif et métrique (horloges)
• Pouvoir de modélisation: temps de réponse de logiciel temps-réel embarqué, retard dans les circuits numériques, ordonnancement et planification dans plusieurs domaines
• Notre axe principal: modélisation des problèmes génériques avec les automates temporisés et lutte contre l’explosion des états et des horloges
Systèmes temporises: généralités
Evaluation laboratoires 2002-2005 - 8 septembre 2006 14
Systèmes temporisés : résultats principaux
• Un cadre pour la modélisation et la résolution des problèmes d’ordonnancement dynamique sous incertitude (Abdeddaim, Asarin, Bozga*, Maler)
• Techniques d’abstraction pour composants temporisés et circuits (BenSalah, Bozga*, Maler).
• Amélioration d’algorithme de vérification pour les automates temporises en exploitant la convexité (BenSalah, Bozga*, Maler)
• Développement d’un solveur SAT performant pour “difference logic” (Cotton)
• Plusieurs résultats théoriques fondamentaux
Evaluation laboratoires 2002-2005 - 8 septembre 2006 15
Systèmes temporises : évaluation
• VERIMAG est parmi les pionniers de la verif temporisée (KRONOS [Sifakis, Yovine, …, Tripakis, …, Bozga])
• Création et comité du pilotage de FORMATS (depuis 2003, 50-70 participants).
• Organisation des colloques TPTS’02 et FORMATS/FTRTFT’04
• Coordination scientifique du projet IST AMETIST
• Compréhension pluri-disciplinaire de l’ordonnancement
• Solveur SAT pour difference logic: parmi les meilleurs au monde
Evaluation laboratoires 2002-2005 - 8 septembre 2006 16
Collaborations internes
• Équipe DCS: Marius Bozga (analyse des systèmes temporisés), Saddek Bensalem (observation et planification)
• Équipe Synchrone: Paul Caspi (contrôle, génération du code pour systèmes embarqués)
Evaluation laboratoires 2002-2005 - 8 septembre 2006 17
Collaborations externes
• Grenoble: LMC, LAG, INRIA, ST
• France: LIAFA, LSV, LIF, ILOG
• Europe: Weizmann, ETHZ, Lund, CWI, Aalborg, Nijmegen, Trento, Graz, MPI, IBM
• Monde: CMU, Penn, NYU, Berkeley, INTEL
Evaluation laboratoires 2002-2005 - 8 septembre 2006 18
Publications
10103Thèses et HDR
61114811Colloques
33303Journaux
1111Livres et collections
20062005200420032002année
Evaluation laboratoires 2002-2005 - 8 septembre 2006 19
Projets
25 K €Dang2005-06ATIPEMTEST
197 K €Maler2006-09RNTLDECIDE
84 K €Maler2002-05IntelFVTA
258 K €Yovine2004-06Crolles II + STAnaconda
2 BDI + 7.5 K €Yovine2000-03RegionSODA
20 K €Yovine2001-03IMAGMash
1 BDI + 22,5 K € Yovine2003-06RegionMadeja
169 K € Yovine2001-03RNTLExpresso
45 K €Yovine2003-06ACIDynamo (avec DCS)
25 K €Tripakis, Dang2003-06ACICORTOS
600 K €Yovine2005-08MEDEA+NEVA
300 K €Maler2004-07ISTPROSYD
271 K € Maler2002-05ISTAMETIST
472 K € Maler2002-05ISTCC
BudgetResponsableDuréeTypeProjet
Evaluation laboratoires 2002-2005 - 8 septembre 2006 20
Sommaire
• Plusieurs domaines d’application en dehors de l’informatique peuvent bénéficier de la modélisation dans une sémantique propre, accompagnée par des algorithmes efficaces
• Deux obstaclesBarrière du langage entre théoriciens et ingénieurs:
investir plus en simplification des présentations et se rapprocher de leur terminologie
Passage à l’échelle: on doit pouvoir résoudre avec nos méthodes propres au moins des problèmes de même taille que ceux que peuvent résoudre les méthodes ad-hoc. C’est là l’essentiel de nos efforts
Evaluation laboratoires 2002-2005 - 8 septembre 2006 21
Plans for the Coming YearsPlans pour l’avenir
• Étendre le calcul d’atteignabilité à des classes importantes de systèmes non-linéaires – applications aux circuits analogiques et en biologie
• Intégration de nos outils (vérification, monitoring, synthèse) dans une chaîne unifiée (besoin d’un ingénieur)
• Appliquer nos techniques d’ordonnancement aux nouvelles architectures multi-processeur (ST, Intel)
• Continuer le développement du solveur SAT étendu (projet avec ILOG) comme un outil majeur de calcul hybride
Evaluation laboratoires 2002-2005 - 8 septembre 2006 22
Implantation guidée par les contraintes logicielles, matérielles et de l’environnement
• Problématique : Complexité croissante au niveau logiciel et matériel– Croissance soutenue du logiciel (e.g., SoC code : 140% / an vs gates : 50% / an)
– Langages haut niveau et RTOS (e.g., Java – VM, mémoire dyn., multithreading)
– Architectures complexes (e.g., Wasabi (Philips, HDTV), IXP2800 (Intel, NP))
– Incertitude (e.g., temps d’exécution variable, environnement non déterministe)
• Etat de l’art : Absence d’approche complète « généraliste »– Dépendantes de la plate-forme
– Modèle d’exécution fixe
– Pas de synthèse de code
– Pas de support pour contraintes quantitatives, architecturales, …
• Approche : Synthèse d’implantations guidée par l’application– Propriétés quantitatives (contraintes, exigences, QoS, …)
– Propriétés du support physique
– Propriétés liées a la logique des applications
Evaluation laboratoires 2002-2005 - 8 septembre 2006 23
Résultats marquants
• Synthèse de code temporisé séquentiel avec ordonnanceur vérifié pour programmes Esterel avec temps d’exécution variable interagissant avec environnements asynchrones temporisés [IEEE Proc’03]
– Outil précompétitif : compilateur Esterel (FTRD) + KRONOS (V.)
– Point fort : Code embarquable exécuté à la vérification
– Applications : Alcatel GSM radio, FTRD mobile phone prototype, PATH AVCS
• Synthèse de code natif (C + noyau d’exécution) temporisé multithread avec ordonnanceur synthétisé pour des programmes Java utilisant le profile Real Time Spécification for Java (RTSJ) [EMSOFT’02-03,ECRTS’03,ASE’04]
– Outil précompétitif : compilateur Java (Silicomp) + noyau TR (Aonix/Thales) + synthèse (V.)
– Points forts :
• Méthodologie de synthèse automatique d’ordonnanceur efficace (90% de réduction)
• Implémentation efficace des ordonnanceurs sur OS : testé sur eCos et FastOS (Thalès)
– Applications : cas d’étude Thalès, bras de robot
Evaluation laboratoires 2002-2005 - 8 septembre 2006 24
Nouvelle équipe / Travaux en cours
• Equipe
– Permanents (2) : S. Yovine (DR CNRS), Ch. Rippert (MdC ENSIMAG)
– Thésards (2) : I. Assayad (BDI CNRS), G. Salagnac (BDI Région Rhône-Alpes)
– Ingénieurs contractuels (4) : F-X. Defaut, Ch. Nakhli, W. Redrovan, M. Zanconi
• Synthèse d’implantations avec gestion de mémoire dynamique prédictible– Quantification polynomiale paramétrée de la mémoire allouée [FTfJP’05,JOT’06]
– Xylophone : Synthèse de gestionnaire mémoire en régions [AIOOL’05,ICOOOLPS’06]
• Passage à l’échelle (testé sur application Thalès Avionics)
• Intégré avec JITS VM (JavaCard, Lille), en cours d’intégration dans Sun HotSpot
• Implantation de logiciels multithread sur architectures multiprocesseurs– Jahuel : Framework de génération de code (langage de spec/outil) [DFMA’05,ICFEM’05]
• Traçabilité des décisions d’implantation, extensible et re-ciblable
• Prototype intégré avec technologie de compilation FlexCC2 (ST)
• Applications : IPv4, PATH AVCS, MPEG-4, AER/NCA
– P-Ware : Framework de modélisation/simulation logiciel/matériel [IES’06]
• Simulation (niveau TLM) rapide (jusqu’à 6 10^5 cycles/sec) et précise (5-20 %)
• Applications : IPv4 s/ Intel IXP2800 NP, MPEG-4 encoder s/ Philips Wasabi/Cake NoC
Evaluation laboratoires 2002-2005 - 8 septembre 2006 25
Bilan et perspectives
• Production scientifique
– Articles : 13 conférences, 2 journaux
– Thèses : 2 soutenues, 2 en cours / Autres : 3 DEA, 1 DESS, 2 CNAM
– Logiciels : 2 prototypes précompétitifs aboutis, 3 prototypes académiques en cours de développement
• Coopérations fluides, dynamiques et productives
– Internationales : Université de Buenos Aires (1 thèse et plusieurs stagiaires en co-tutelle en cours, plusieurs
projets et articles communs, école ARTIST2 de printemps Argentine 2007)
– Nationales : LIFL [Lille, G. Grimaud], ICPS [Strasbourg, Ph. Clauss] (intégration d’outils)
– Laboratoire : groupe de travail sur BIP (DCS)
– Industrielles : ST (forte, projets en cours : MEDEA+ NEVA, Minalogic SCEPTRE), Thalès (naissante)
• Visibilité
– Systèmes temporisés : Reconnue (As.Ed. FMSD, PC conf., jurys, éval. projets, …)
– Gestion de la mémoire dynamique : Naissante (revues d’articles, séminaires invités, …)
– Analyse systèmes multiprocesseurs : En gestation avec forte coopération industrielle (ST)
• Directions de travail
– Framework de modélisation, analyse et synthèse de code intégrant Jahuel / P-Ware / BIP(DCS)
– Méthodologie et outillage orientés au développement d’applications Java embarquées