Lettre du LAAS

Publication trimestrielle du Laboratoire
d'analyse et d'architecture des systèmes du CNRS

Dans le domaine avionique, les architectures embarquées connaissent depuis une dizaine d'années une mutation profonde avec l'apparition des architectures modulaires intégrées (IMA). En offrant aux applications embarquées un support d'exécution et de communication standard et mutualisé, ces architectures ont permis une réduction du poids et de la complexité de l'architecture physique. Cette réduction de la complexité au niveau bas s'est cependant traduite par une difficulté accrue de conception et d'intégration des applications car il faut gérer le partage des ressources au moyen de nombreux paramètres de configuration. Cette thèse est consacrée à deux problèmes d'allocation de ressources qui se posent dans le processus de conception d'une architecture IMA.Nous étudions tout d'abord le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques, c'est-à-dire des tâches qui s'exécutent à intervalles de temps constants sur un horizon de temps infini. Nous supposons que l'objectif est de maximiser la durée minimale d'inactivité entre deux exécutions de tâches tout en garantissant que les intervalles pendant lesquels elles s'exécutent ne se chevauchent pas. Ceci permet de garantir une marge d'évolution minimale des budgets de temps alloués aux tâches. Nous proposons tout d'abord une formulation sous la forme d'un programme linéaire en nombres entiers intégrant de nombreuses contraintes temporelles et de ressource de ce problème NP difficile. Pour permettre le passage à l'échelle, nous proposons également une heuristique inspirée de la théorie des jeux dans laquelle chaque tâche adapte à son tour son ordonnancement pour maximiser sa propre fonction d'utilité (qui est liée aux marges d'évolution des tâches). Nous montrons la convergence de cet algorithme vers un point d'équilibre dans lequel aucune tâche n'a intérêt à modifier unilatéralement sa stratégie et établissons qu'il existe au moins un équilibre qui est globalement optimal. Les résultats numériques obtenus montrent que cet algorithme est beaucoup plus rapide que la méthode exacte et fournit une bonne approximation. Pour améliorer encore la qualité des solutions obtenues, nous utilisons cette heuristique dans un algorithme multi-start qui permet d'obtenir des garanties probabilistes sur l'optimalité des équilibres atteints.Dans une seconde partie, nous considérons le problème du routage  dans un réseau AFDX des messages échangés entre les fonctions avioniques. Ce réseau permet la transmission de trames Ethernet dans des liens virtuels (VL) qui se partagent les ressources du réseau de transmission.  Chaque VL peut être vu comme un arbre multicast permettant la transmission de données depuis un point du réseau vers un ou plusieurs autres. Nous proposons tout d'abord une formulation exacte du problème de routage des VL sous la forme d'un programme linéaire en nombres entiers de type noeuds-liens. Nous étudions ensuite une heuristique en deux phases qui permet de faire un compromis entre une distribution équitable de la charge dans le réseau et la minimisation du délai de communication. Les résultats obtenus avec cette heuristique montrent qu'elle permet d'avoir des résultats très proches de la méthode exacte tout en améliorant significativement les délais de communication.