Systèmes temporis é s et hybrides

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


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


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


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)


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é


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)


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.


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é)


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é


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


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


• 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


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


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


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)


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


Publications

10103Thèses et HDR

61114811Colloques

33303Journaux

1111Livres et collections

20062005200420032002année


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


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


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


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


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


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


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

Documents

Systèmes temporis é s et hybrides