Avec Kopernic, les statistiques s’invitent dans les systèmes embarqués temps réel

Date :
Mis à jour le 13/03/2020
Dans un avion ou une voiture, les programmes qui gèrent des fonctions vitales (pilotage automatique, freinage, ABS…) doivent respecter des délais maximum d’exécution et des délais de réponse. Mais comment garantir ces délais quand ces programmes se complexifient et sont portés sur des processeurs dits « multicœurs », soit à plusieurs unités physiques de calcul ? Les outils d’analyse utilisés jusqu’ici atteignent leurs limites. L’action exploratoire Kopernic, lancée en 2018 par Inria, propose une voie pionnière : évaluer les temps d’exécution par des approches statistiques.
Kopernic - Statinf
© Inria / Photo Raphaël de Bengy

 

Un ordinateur domestique qui prend son temps ou qui plante, c’est courant et sans gravité. Mais sur un avion ou dans une voiture, un programme qui tarde à s’exécuter peut provoquer une catastrophe. Des exemples ? Les régulateurs de vitesse automobiles bloqués, à l’origine de plusieurs accidents mortels ces dernières années. 

L’intérêt croissant des industriels des systèmes embarqués

« L’arrivée des programmes complexes change l’attitude des industriels de l’embarqué temps réel*, constate Liliana Cucu, responsable de l’action exploratoire Kopernic. L’intérêt pour nos travaux augmente, alors que leur caractère novateur pouvait surprendre, voire dérouter il y a 10 ans. »

À ce jour en effet, l’usage est d’évaluer les temps d’exécution à partir d’une analyse statique d’un modèle exact du programme et de son processeur, c’est-à-dire sans l’exécuter. On obtient ainsi une valeur unique dite « pire cas », par exemple 30 millisecondes (ms). Autrement dit, dans le cas le moins favorable, le programme s’exécutera au maximum en 30 ms, de même que chacune de ses fonctions prise isolément.

Associer approches probabilistes et non-probabilistes

L’approche statistique de Kopernic rompt avec cette culture de la valeur unique. Elle propose en effet une distribution de valeurs assortie de probabilités. Exemple : le programme s’exécutera en 20 ms avec une probabilité de 10-3 par heure de fonctionnement, en 25 ms avec une probabilité de 10-5, en 30 ms avec une probabilité de 10-7 (soit une occurrence en 11 siècles), etc. Il est alors possible de vérifier si ces couples temps d’exécution/probabilités sont acceptables, pour chaque fonction du programme : un travail fin qui offre de solides garanties.

Et les analyses statiques ? Elles ne sont pas écartées. Les chercheurs continuent à les utiliser au cas par cas, pour des fonctions ou des programmes simples. À l’échelle du système complet, Kopernic propose donc de combiner des approches probabilistes et non-probabilistes.

Kopernic
© Inria / Photo Raphaël de Bengy

 

« Une démarche pionnière et une recherche à risque »

« C’est une démarche pionnière et une recherche à risque, sourit Liliana Cucu, car on change de culture scientifique, voire de philosophie, ce qui peut susciter des résistances. Mais nos partenaires industriels suivent. » Ils sont plusieurs, des PME et des grands groupes comme Airbus, Thales, EDF ou Enedis.

Pourquoi suivent-ils ? Parce que les analyses statiques butent sur la complexité croissante des systèmes embarqués temps réel. Ces derniers comptent des dizaines de fonctions dans l’aéronautique, des centaines dans l’automobile, et on en crée régulièrement de nouvelles : ajout d’un capteur, d’un traitement, d’une antenne wifi... « L’évaluation par analyse statique du comportement temporel des programmes devient très difficile. »  

Avec les multicœurs, tout se complique

De plus, cette analyse pêche parfois par excès de pessimisme. On ajoute alors un ou plusieurs processeurs afin d’isoler les fonctions les plus critiques et de sécuriser leur temps d’exécution. Mais plus de processeurs, cela signifie plus de consommation d’énergie. Or, les systèmes embarqués cherchent à l’économiser, notamment pour limiter le poids des batteries. De plus, ces processeurs supplémentaires rendent les systèmes plus complexes, d’où un risque accru de retards d’exécution. Un véritable cercle vicieux.

Il arrive aussi que ces processeurs multicœurs s’imposent à l’industriel, même s’il n’en a pas besoin. Car avec la croissance exponentielle des ventes de smartphones, tous équipés de multicœurs, ce marché s’est envolé et celui des monocœurs a plongé. Les fournisseurs deviennent rares... Or, chaque processeur a un impact spécifique sur la « variabilité » des programmes, autrement dit sur les fluctuations de leur temps d’exécution !

Les applications : aéronautique, automobile, ferroviaire…

« Nos partenaires industriels mesurent ces difficultés et se mobilisent, reprend Liliana Cucu. Ils nous font découvrir la culture métier et les processus de développement de l’aéronautique, de l’automobile, du ferroviaire… De plus, ils nous alimentent en données collectées sur le terrain, par exemple lors du décollage ou de l’atterrissage d’avions. Nous travaillons sur des bases réalistes et nos recherches n’en ont que plus de sens.»

Nous travaillons sur des bases réalistes et nos recherches n’en ont que plus de sens.

De son côté, l’équipe Kopernic rassemble des compétences en mathématiques, informatique temps réel, statistiques et automatique. Selon les phases du projet, son effectif varie entre 10 et 15 chercheurs Inria. Il lui arrive de solliciter des experts extérieurs, par exemple en modélisation fonctionnelle et en théorie des probabilités pour les réseaux. De plus, elle travaille avec des partenaires académiques français et étrangers : Belgique, Grande-Bretagne, Suède, Canada, Singapour…

Deux brevets et un projet de start-up

Moins d’un an après son lancement, le projet a déjà atteint un jalon important avec le dépôt de deux brevets sur une méthode de validation de ses approches statistiques. Cette méthode s’appuie sur la théorie des valeurs extrêmes, qu’elle décline de deux manières (distribution généralisée ou distribution de Pareto). Si les résultats convergent, c’est que les probabilités attribuées aux différents temps d’exécution sont justes. 

« Cette démonstration était indispensable, à la fois pour convaincre ceux qui manquent de background scientifique sur les statistiques et pour fournir aux industriels des moyens de preuve de la fiabilité de leurs systèmes, en vue de leur certification », rappelle Liliana Cucu. De plus, cette méthode est assez prometteuse pour avoir donné naissance à un projet de start-up porté par des membres de l’équipe.

Réseaux sans fil : les statistiques s’imposent

Cette première étape en annonce beaucoup d’autres. Kopernic se penche par exemple sur les incertitudes induites par les systèmes de communication sans fil, pour des voitures autonomes et des drones. Ces systèmes sont bien moins fiables que le filaire, alors qu’ils véhiculent des messages qui interagissent en permanence avec les programmes : le niveau de complexité monte d’un cran. « Dans un tel cas, l’évaluation des temps d’exécution repose nécessairement sur une approche statistique. » 

Autre sujet important de la feuille de route, l’ordonnancement des programmes, c’est-à-dire l’ordre d’exécution de leurs différentes tâches. C’est un facteur-clé du temps d’exécution. Un ordonnancement efficace synchronise ces tâches et les distribue entre les processeurs en exploitant au mieux leur puissance de calcul. À l’inverse, un ordonnancement mal pensé crée des goulets d’étranglement, des files d’attente, des interférences avec d’autres programmes.

Première évaluation du projet en 2020

Les chercheurs développent des algorithmes d’ordonnancement qui prennent en compte les interactions entre les facteurs de variabilité, afin de les minimiser. Grâce à ces algorithmes, ils mèneront des analyses d’ordonnançabilité de programmes. Puis des analyses d’ordonnançabilité d’ensembles de programmes, communicant à travers des réseaux prédictibles (filaires) et non prédictibles (sans fil). Un scénario pas si futuriste : demain, par exemple, un drone pourrait escorter un avion dont les outils de bord sont défaillants, tout en échangeant avec l’équipage, la tour de contrôle et d’autres avions. 

La responsable de l’équipe Kopernic a deux échéances à l’esprit. En mars 2020, son projet fera l’objet d’une première évaluation. Si elle obtient un feu vert, elle compte produire d’ici 2023 une classification des facteurs de variabilité des programmes. Le monde des systèmes embarqués, bousculé par les défis technologiques qui l’assaillent, devrait lui faire bon accueil.

Liliana Cucu-Grosjean
© Inria / Photo Raphaël de Bengy

Bio express de Liliana Cucu

Liliana Cucu a fait ses débuts à Inria entre 2001 et 2004, en tant que thésarde dans une équipe de recherche sur l’optimisation des systèmes temps réel embarqués. Elle collabore ensuite avec plusieurs équipes au Portugal, en Belgique et en France. Elle démontre alors que des résultats fondateurs de la prédictibilité des systèmes temps réel sont erronés, et propose des méthodes de preuves valides. Elle rejoint Inria en tant que chercheuse en 2008 et impose un concept à la base de la création de l’équipe Kopernic : les « approches statistiques pire cas ».  Forte de la reconnaissance internationale de ses travaux, elle soutient et porte des actions en faveur de la parité et de l’égalité des chances, à Inria et dans la communauté scientifique à travers l’Institut des ingénieurs électriciens et électroniciens (IEEE). 

 

 


* système informatique autonome, dédié à une tâche précise et tenu à un délai d’exécution maximum