Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Dans le domaine de l'électronique embarquée, les applications de communications numériques et de traitement d'images imposent des contraintes de temps très fortes tout en admettant une limitation en ressources et performances des unités de traitement. La restriction quant à la mémoire utilisable peut être préjudiciable pour des domaines tels que le codage vidéo. Une solution pour atteindre les objectifs d'implantation temps-réel peut passer par une distribution sur une architecture matérielle parallèle. Cette problématique constitue le cadre de ces travaux. Plus précisément, il s'agit de développer un processus de prototypage rapide dédié aux architectures parallèles à base de plusieurs processeurs de traitement numérique du signal de dernière génération (FPGA, DSP). L'aspect optimisation du point de vue de la mémoire allouée est abordé ici de manière plus précise.<br />La chaîne de prototypage a été élaborée autour de SynDEx, outil développé à l'INRIA basé sur la méthodologie AAA. Cette dernière vise à améliorer l'implantation d'un algorithme sur une architecture multi-processeurs en déterminant une distribution et ordonnancement optimaux. SynDEx réalise la phase d'adéquation proprement dite, et génère un exécutif indépendant de la cible. Nous avons dans un premier temps contribué à l'automatisation du processus sur cible multi-processeurs, en rajoutant d'une couche fonctionnelle, et en développant de nouveaux noyaux spécifiques pour des processeurs de traitement numérique du signal.<br />Dans un contexte embarqué, nos préoccupations se sont ensuite penchées sur la minimisation de la mémoire pour le code généré. C'est un problème encore très ouvert pour des architectures multi-composants. La solution trouvée, grâce aux algorithmes de coloriage de graphe, aboutit à une amélioration significative des résultats d'implantation distribuée. Le portage vers des plates-formes multi-composants est aujourd'hui automatique, notamment en intégrant directement dans l'outil SynDEx l'optimisation mémoire.<br /> Une autre partie importante de ces travaux a concerné le développement et l'intégration, à travers notre processus de prototypage, d'applications conséquentes dans les domaines du traitement des images (MPEG-4, LAR) et celui des télécommunications (MC-CDMA, UMTS). Les résultats obtenus valident l'ensemble du processus proposé, et démontrent son adaptation à des systèmes globalement orientés traitement de l'information. Le mémoire se conclut en ouvrant sur de nouvelles perspectives, en s'intéressant notamment à des systèmes multi-couches réunissant des couches « transport » de télécommunication numériques et des couches « services » de traitement des images.

Ce document présente nos contributions aux algorithmes d'ordonnancement à criticité mixte pour multi-processeurs. La correction de l'exécution des applications temps réel critiques est assurée par l'utilisation d'un ordonnancement vérifié à la conception. Dans ce contexte, le dimensionnement des plate-formes d'exécution vise à minimiser le nombre de processeurs nécessaires pour assurer un ordonnancement correct. Ce dimensionnement est affecté par les exigences de sûreté de fonctionnement. Ces exigences poussent à surestimer le temps nécessaire garantissant l'exécution correcte des applications. Il en découle un dimensionnement assez coûteux. Les méthodes d'ordonnancement des systèmes à criticité mixte proposent des compromis sur les garanties d'exécution des applications améliorant le dimensionnement. Différents compromis ont été proposés mais tous reposent sur la notion de mode d'exécution. Les modes sont ordonnés, et les tâches voient leur temps d'exécution requis croître avec les modes. Cependant, afin de diminuer le dimensionnement du système, seul l'ordonnancement des tâches les plus critiques est garanti. Ce modèle est appelé "discarding". La majorité des algorithmes proposés se limitent à deux modes d'exécutions par simplicité. De plus, les algorithmes les plus efficaces pour multi-processeurs exhibent un nombre élevé de préemptions, ce qui constitue un frein à leur adoption. Finalement, ces algorithmes sont rarement généralisables. Pourtant, la prise en compte de plus de deux modes, ou de tâches aux périodes élastiques permettrait une adoption plus large par le milieu industriel. L'approche proposée repose sur la séparation des préoccupations entre la prise en compte des modes de fonctionnement, et l'ordonnancement des tâches sur multi-processeurs. Cette méthode permet de concevoir une politique d'ordonnancement efficace et adaptable à différents modèles de systèmes à criticité mixte. Notre approche consiste à transformer un lot de tâches à criticité mixte en un lot de tâches qui n'est plus à criticité mixte. Ceci nous permet d'utiliser un algorithme d'ordonnancement temps réel optimal engendrant peu de préemptions et de migrations, à savoir RUN. Cette approche, appliquée en premier pour le modèle discarding avec deux modes d'exécution, rempli son objectif d'efficacité. Nous illustrons sa généricité en utilisant le même principe pour ordonnancer des systèmes discarding avec plus de deux modes d'exécution. Enfin, une démarche reposant sur la décomposition de tâche permet de généraliser l'approche au cas des tâches élastiques. / This thesis focuses on the scheduling of mixed-criticality scheduling algorithms for multi-processors. The correctness of the execution of the real-time applications is ensured by a scheduler and is checked during the design phase. The execution platform sizing aims at minimising the number of processors required to ensure this correct scheduling. This sizing is impacted by the safety requirements. Indeed, these requirements tend to overestimate the execution times of the applications to ensure their correct executions. Consequently, the resulting sizing is costly. The mixed-criticality scheduling theory aims at proposing compromises on the guarantees of the execution of the applications to reduce this over-sizing. Several models of mixed-criticality systems offering different compromises have been proposed but all are based on the use of execution modes. Modes are ordered and tasks have non decreasing execution times in each mode. Yet, to reduce the sizing of the execution platform, only the execution of the most critical tasks is ensured. This model is called the discarding model. For simplicity reasons, most of the mixed-criticality scheduling algorithms are limited to this model. Besides, the most efficient scheduling policies for multi-processors entail too many preemptions and migrations to be actually used. Finally, they are rarely generalised to handle different models of mixed-criticality systems. However, the handling of more than two execution modes or of tasks with elastic periods would make such solutions more attractive for the industry. The approach proposed in this thesis is based on the separation of concerns between handling the execution modes and the scheduling of the tasks on the multi-processors. With this approach, we achieve to design an efficient scheduling policy that schedules different models of mixed-criticality systems. It consists in performing the transformation of a mixed-criticality task set into a non mixed-criticality one. We then schedule this task set by using an optimal hard real-time scheduling algorithm that entails few preemptions and migrations: RUN. We first apply our approach on the discarding model with two execution modes. The results show the efficiency of our approach for such model. Then, we demonstrate the versatility of our approach by scheduling systems of the discarding model with more than two execution modes. Finally, by using a method based on the decomposition of task execution, our approach can schedule systems based on elastic tasks.

L'ablation des tissus par hyperthermie locale guidée par IRM est une technique prometteuse pour le traitement du cancer et des arythmies cardiaques. L'IRM permet d'extraire en temps réel des informations anatomiques et thermiques des tissus. Cette thèse a pour objectif d'améliorer et d'étendre la méthodologie existante pour des interventions sur des organes mobiles comme le rein, le foie et le coeur. La première partie a été consacrée à l'introduction de l'imagerie rapide (jusqu'à 10-15 Hz) pour le guidage de l'intervention par IRM en temps réel. L'utilisation de cartes graphiques (GPGPU) a permis une accélération des calculs afin de satisfaire la contrainte de temps réel. Une précision, de l'ordre de 1°C dans les organes abdominaux et de 2-3°C dans le coeur, a été obtenue. Basé sur ces avancées, de nouveaux développements méthodologiques ont été proposés dans une seconde partie de cette thèse. L'estimation du mouvement basée sur une approche variationnelle a été améliorée pour gérer la présence de structures non persistantes et de fortes variations d'intensité dans les images. Un critère pour évaluer la qualité du mouvement estimé a été proposé et utilisé pour auto-calibrer notre algorithme d'estimation du mouvement. La méthode de correction des artefacts de thermométrie liés au mouvement, jusqu'ici restreinte aux mouvements périodiques, a été étendue à la gestion de mouvements spontanés. Enfin, un nouveau filtre temporel a été développé pour la réduction du bruit sur les cartographies de température. La procédure interventionnelle apparaît maintenant suffisamment mature pour le traitement des organes abdominaux et pour le transfert vers la clinique. Concernant le traitement des arythmies cardiaques, les méthodes ont été évaluées sur des sujets sains et dans le ventricule gauche. Par conséquent, la faisabilité de l'intervention dans les oreillettes mais aussi en présence d'arythmie devra être abordée. / MR-guided thermal ablation is a promising technique for the treatment of cancer and atrial fibrillation. MRI provides both anatomical and temperature information. The objective of this thesis is to extend and improve existing techniques for such interventions in mobile organs such as the kidney, the liver and the heart. A first part of this work focuses on the use of fast MRI (up to 10-15 Hz) for guiding the intervention in real time. This study demonstrated the potential of GPGPU programming as a solution to guarantee the real time condition for both MR-reconstruction and MR-thermometry. A precision in the range of 1°C and 2-3°C was obtained in abdominal organs and in the heart, respectively. Based on these advances, new methodological developments have been carried out in a second part of this thesis. New variational approaches have proposed to address the problem of motion estimation in presence of structures appearing transient and high intensity variations in images. A novel quality criterion to assess the motion estimation is proposed and used to autocalibrate our motion estimation algorithm. The correction of motion related magnetic susceptibility variation was extended to treat the special case of spontaneous motion. Finally, a novel temporal filter is proposed to reduce the noise of MR-thermometry measurements while controlling the bias introduced by the filtering process. As a conclusion, all main obstacles for MR-guided HIFU-ablation of abdominal organs have been addressed in in-vivo and ex-vivo studies, therefore clinical studies will now be realized. However, although promising results have been obtained for MR-guided RF-ablation in the heart, its feasibility in the atrium and in presence of arrhythmia still remains to be investigated.

Ce travail présente un modèle de noyau de communication pour les systèmes répartis. Son architecture, basée sur le modèle de CSP proposé par HOARE, a été définie pour un type particulier de système, les systèmes «temps réel» répartis sur un réseau local. Il s'agit donc d'un modèle adapté à une classe précise d'application, à l'opposé de la plupart des études qui traitent des noyaux de systèmes répartis généraux. Ce noyau est basé sur deux classes d'objets: les processus «normaux» pour exprimer les traitements séquentiels et de processus appelés canaux pour implémenter à la fois la communication et la synchronisation. Une implémentation de ce noyau a été réalisée sur UNIX

Étude d'un modèle mathématique pour formaliser le comportement des systèmes parallèles et temps réel, à des fins de spécification de problèmes, de description, d'analyse et de preuve de réalisations. Construction, à partir des mêmes notions, d'un calcul formel conduisant à des méthodes systématiques d'analyse de systèmes logiques temporisés, au niveau algorithmique

Le thème de la « navigation bas-coût », caractérisé par le transfert de performance des capteurs vers les algorithmes de fusion de données et de commande, est un thème central dans de nombreuses applications militaires liées en particulier aux besoins nouveaux des troupes légères. L'utilisation de capteurs inertiels ou magnétométriques type MEMS et de GPS civils (notamment), optimise les critères d'encombrement, de masse et de consommation. Mais elle requiert, en compensation des performances relativement médiocres des capteurs, des algorithmes de guidage-navigation-pilotage spécifiques aux applications considérées. Dans ce mémoire, nous considérons trois scénarios d'utilisation et exposons des techniques innovantes pour la localisation et le contrôle. Nous considérons d'abord le cas d'un robot terrestre équipé de capteurs de proximité, d'un gyroscope, d'odomètres et d'un GPS. Nous implémentons expérimentalement avec succès un algorithme d'évitement d'obstacles dont nous établissons une preuve de convergence, ainsi qu'un algorithme de planification de trajectoires hors ligne dont nous utilisons les résultats en temps réel pour réaliser, via un estimateur non linéaire, un bouclage par retour dynamique. Nous étudions ensuite le cas du vol autonome d'une plate-forme aérienne instable de type hélicoptère. Nous développons et implémentons, à bord sur un système de mesure et de calcul temps-réel de notre conception, un estimateur d'état incluant un modèle de la dynamique du vol de l'engin, recalé par les capteurs inertiels, barométriques, et GPS ainsi qu'un bouclage par retour d'état. En utilisant les résultats de filtrage sur les vols effectués, les paramètres du modèle sont précisément identifiés : la qualité et la robustesse de l'estimation obtenues grâce au modèle permettent de réaliser un vol stationnaire autonome en extérieur. Enfin nous considérons le problème d'un piéton évoluant à l'intérieur de bâtiments. Les erreurs d'estimation du cap lors de l'utilisation des différentes plate-formes (terrestre comme aérienne) nous guident vers une utilisation nouvelle du champ magnétique par l'inspection de ses gradients. Par une technique que nous exposons, nous montrons comment utiliser les perturbations (inconnues) du champ magnétique pour améliorer considérablement l'estimation de position d'une centrale inertielle bas-coût au point qu'elle devienne un instrument de localisation.

Les travaux de recherche présentés dans cette thèse portent sur le problème de la perception de l’environnement en milieu urbain, complexe et dynamique et ce en présence de mesures extéroceptives bruitées et incomplètes obtenues à partir decapteurs embarqués. Le problème est formalisé sous l’angle de la fusion de données capteurs à l’aide d’une représentation spatiale de l’environnement. Ces travaux ont été réalisés pour la navigation autonome de véhicules intelligents dans le cadre du projet national ANR CityVIP. Après avoir considéré les principaux formalismes de modélisation de l’incertitude, un système de fusion de grilles spatio-référencées gérant l’incertitude avec des fonctions de croyances est étudié. Ce système est notamment capable de fusionner les mesures d’un lidar multi-nappes et multi-échos, obtenues à différents instants pour construire une carte locale dynamique sous la forme discrète d’une grille d’occupation évidentielle.Le principal avantage des fonctions de croyance est de représenter de manière explicite l’ignorance et ne nécessite donc pas d’introduire d’information à priori non fondée. De plus, ce formalisme permet d’utiliser facilement l’information conflictuelle pour déterminer la dynamique de la scène comme par exemple les cellules en mouvement. Le formalisme de grilles d’occupation évidentielles est présenté en détails et un modèle de capteur lidar multi-nappes et multi-echos est ensuite proposé. Deux approches de fusion séquentielle multi-grilles sont étudiées selon les paradigmes halocentréet égo-centré. Enfin, l’implémentation et les tests expérimentaux des approches sont décrits et l’injection d’informations géographiques connues a priori est étudiée. La plupart des travaux présentés ont été implémentés en temps réel sur un véhicule du laboratoire et de nombreux tests en conditions réelles ont été réalisés avec une interface d’analyse de résultat utilisant une rétro-projection dans une image grand angle. Les résultats ont été présentés dans 5 conférences internationales [Moras et al., 2010, Moras et al., 2011a, Moras et al., 2011b, Moras et al., 2012, Kurdej et al., 2012] etle système expérimental a servi à la réalisation de démonstrations officielles dans le cadre du projet CityVIP à Paris et lors de la conférence IEEE Intelligent Vehicles Symposium 2011 en Allemagne. / The research presented in this thesis focuses on the problem of the perception of the urban environment which is complex and dynamic in the presence of noisy and incomplete exteroceptive measurements obtained from on-board sensors. The problem is formalized in terms of sensor data fusion with a spatial representation of the environment. This work has been carried out for the autonomous navigation of intelligent vehicles within the national project ANR CityVIP. After having considered various formalisms to represent uncertainty, a fusion of spatio-referenced grids managing uncertainty with belief functions is studied. This system is capable of merging multi-layers and multi-echoes lidar measurements, obtainedat different time indexes to build a dynamic local map as a discrete evidential occupancy grid. The main advantages of belief functions are, firstly, to represent explicitly ignorance, which reduces the assumptions and therefore avoid introducing wrong a priori information and, secondly, to easily use conflicting information to determine the dynamics of the scene such as movements of the cells. The formalism of evidential occupancy grids is then presented in details and two multi-layers and multi-echos lidar sensor models are proposed. The propagation of the information through geometrical transformations is formalized in a similar way of image transformation framework. Then, the implementation of the approach is described and the injection of prior geographic information is finally investigated. Most of the works presented have been implemented in real time on a vehicle and many tests in real conditions have been realized. The results of these researches were presented through five international conferences [Moras et al., 2010, Moras et al., 2011a, Moras et al., 2011b, Moras et al., 2012], [Kurdej et al., 2012] and the experimental vehicle was presented at the official demonstration project CityVIP in Paris and at the IEEE Intelligent Vehicles Symposium 2011, in Germany.

Notre travail aborde le problème de navigation autonome en milieu dynamique partiellement connu. Ce problème a généré de nombreux travaux durant les dix dernières années. Néanmoins, nous avons observé que certains aspect fondamentaux liés à la nature dynamique de l'environnement ont été oubliés, en commençant par la limite de temps qu'un système placé dans un environnement dynamique a, pour prendre une décision et exécuter son mouvement. Bien que cette contrainte soit d'importance cruciale, il y a paradoxalement peu de travaux dans la littérature la prennent en compte. Cette contrainte temps réel a été placée au cœur de notre travail. Dans ce travail nous présentons une technique de planification qui prend en compte de manière explicite la contrainte temps réel imposée par l'environnement dynamique. La planification de mouvement partiel (PMP) est une technique originale de planification qui réagit à tout moment; dès que le temps imparti pour calculer une trajectoire est écoulé, la meilleure trajectoire calculée disponible est transmise. En fait, de notre point de vue, l'approche PMP est la meilleure approche possible au problème que nous avons observé, à savoir l'incompatibilité intrinsèque entre la planification en environnement dynamique et la contrainte temps réelle. PMP intègre également le problème de sûreté, que nous considérons d'un point de vue des états de collisions inévitables (ICS), concept récent qui englobe toutes les approches existantes et de proposer une technique qui donne de fortes garanties de sûreté pour notre système. Enfin, dans ce travail, nous démontrons l'efficacité de notre approche PMP pour des environnements relativement complexes. Plusieurs expérience ont été mises en œuvre où PMP a ainsi été intégré sur une plate forme réelle, le robot type voiture Cycab, véhicule conçu par l'INRIA.

Les cameras intelligentes, ou Smart Cameras, sont des systèmes embarqués de vision artificielle. Ces systèmes se différencient des caméras "communes" par leur capacité à analyser les images, afin d'en extraire des informations pertinentes sur la scène observée, et ceci de féçon autonome grâce à des dispositifs embarqués de calcul. Les applications pratiques de ce type de système sont nombreuses (vidéo-surveillance, vision industrielle, véhicules autonomes, etc.), mais leur implémentation est assez complexe, et demande un haut degré d'expertise et des temps de développement élevés. Les travaux présentés dans cette thèse s'adressent à cette problématisue, et proposent une méthodologie d'implémentation permettant de simplifier le développement d'applications au sein des plateformes Smart Camera basées sur un dispositif FPGA. Cette méthodologie s'appuie d'une part sur l'instanciation au sein du FPGA d'un processeur "soft-core" taillé sur mesure, et d'autre part sur un flot de design à deux niveaux, permettant ainsi de traiter séparément les aspects matériels liés à la plateforme et les aspects algorithmiques liés à l'application