Nous nous intéressons à l'architecture de robots marins et sous-marins autonomes dans le cadre de missions nécessitant leur coopération. Cette coopération s'avère difficile du fait que la communication (acoustique) est très contrainte en termes de débit et de portée.  Notre travail se place dans le contexte de missions d'exploration pour détecter des éléments particuliers sur les fonds marins, et en particulier des sources d'eau chaude. Pour cela, le véhicule sous-marin parcours des segments de droite pré-planifiés et rejoint des points de rendez-vous (points de communication). Ces derniers permettent d'assurer le suivi de bon déroulement de la mission, mais surtout de mettre en oeuvre des schémas de coopération entre les véhicules sous-marins. Au fur et à mesure de l'exploration, les sous-marins construisent et mettent à jour une représentation de l'environnement qui décrit les probabilités de localisation de sources. Une approche adaptative exploite ces informations et permet de dévier les sous-marins de leurs plan initial pour augmenter la quantité d'information, tout en respectant les contraintes du plan initial, et en particulier les rendez-vous de communication. Lors des rendez-vous, chaque véhicule échange ses données avec les autres, en ne transmettant que les informations nécessaires à la mise en place de schémas de coopération. L'ensemble de ces fonctions sont intégrées au sein de l'architecture existante T-REX, pour laquelle nous proposons des composants supplémentaires qui permettent la cartographie des fonds et la définition de schémas de coopération. Différentes simulations permettent d'évaluer les travaux proposés. / There is a growing research interest in Autonomous Underwater Vehicles (AUV), due to the need for increasing our knowledge about the deep sea and understanding the effects the human way of life has on it. This need has pushed the development of new technologies to design more efficient and more autonomous underwater vehicles. Autonomy refers, in the context of this thesis, to the “decisional autonomy”, i.e. the capability of taking decisions, in uncertain, varying and unknown environments. A more recent concern in AUV area is to consider a fleet of vehicles (AUV, ASV, etc). Indeed, multiple vehicles with heterogeneous capabilities have several advantages over a single vehicle system, and in particular the potential to accomplish tasks faster and better than a single vehicle. Underwater target localization using several AUVs (Autonomous Underwater Vehicles) is a challenging issue. A systematic and exhaustive coverage strategy is not efficient in term of exploration time: it can be improved by making the AUVs share their information and cooperate to optimize their motions. The contribution of this thesis is the definition of an architecture that integrates such a strategy that adapts each vehicle motions according to its and others’ sensory information. Communication points are required to make underwater vehicles exchange information : for that purpose the system involves one ASV (Autonomous Surface Vehicle), that helps the AUVs re-localize and exchange data, and two AUVs that adapt their strategy according to gathered information, while satisfying the associated communication constraints. Each AUV is endowed with a sensor that estimates its distance with respect to targets, and cooperates with others to explore an area with the help of an ASV. To provide the required autonomy to these vehicles, we build upon an existing system (T-REX) with additional components, which provides an embedded planning and execution control framework. Simulation results are carried out to evaluate the proposed architecture and adaptive exploration strategy

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Les performances des algorithmes d'ordonnancement ont un impact direct sur les performances du système complet. Les algorithmes d'ordonnancement temps réel possèdent des bornes théoriques d'ordonnançabilité optimales mais cette optimalité est souvent atteinte au prix d'un nombre élevé d'événements d'ordonnancement à considérer (préemptions et migrations de tâches) et d'une complexité algorithmique importante. Notre opinion est qu'en exploitant plus efficacement les paramètres des tâches il est possible de rendre ces algorithmes plus efficaces et à coût maitrisé, et ce dans le but d'améliorer la Qualité de Service (QoS) des applications. Nous proposons dans un premier temps des algorithmes d'ordonnancement monoprocesseur qui augmentent la qualité de service d'applications hybrides c'est-à-dire qu'en situation de surcharge, les tâches à contraintes souples ont leur exécution maximisée et les échéances des tâches à contraintes strictes sont garanties. Le coût d'ordonnancement de ces algorithmes est aussi réduit (nombre de préemptions) par une meilleure exploitation des paramètres implicites et explicites des tâches. Cette réduction est bénéfique non seulement pour les performances du système mais elle agit aussi positivement sur la consommation d'énergie. Aussi nous proposons une technique associée à celle de DVFS (dynamic voltage and frequency scaling) afin de minimiser le nombre de changements de points de fonctionnement du fait qu'un changement de fréquence implique un temps d'inactivité du processeur et une consommation d'énergie. Les algorithmes d'ordonnancement multiprocesseur basés sur le modèle d'ordonnancement fluide (notion d'équité) atteignent des bornes d'ordonnançabilité optimales. Cependant cette équité n'est garantie qu'au prix d'hypothèses irréalistes en pratique du fait des nombres très élevés de préemptions et de migrations de tâches qu'ils induisent. Dans cette thèse un algorithme est proposé (ASEDZL) qui n'est pas basé sur le modèle d'ordonnancement fluide. Il permet non seulement de réduire les préemptions et les migrations de tâches mais aussi de relâcher les hypothèses imposées par ce modèle d'ordonnancement. Enfin, nous proposons d'utiliser ASEDZL dans une approche d'ordonnancement hiérarchique ce qui permet d'obtenir de meilleurs résultats que les techniques classiques.

Dans un système temps réel, les tâches doivent se terminer avant une date échéance. Pour les ordonnancer, il est nécessaire de connaître leur pire temps d'exécution. Ces systèmes gagnant en complexité, ils demandent une puissance de calcul de plus en plus grande. Pour faire face à cette demande, on peut utiliser des processeurs qui exploitent, en plus du parallélisme d'instructions, le parallélisme de tâches. C'est-à-dire qu'ils sont capables d'exécuter plusieurs tâches en parallèle. Mais la complexité de ces processeurs nuit à la prévisibilité du pire temps d'exécution des tâches. CarCore est un processeur conçu par l'équipe du professeur Ungerer de l'Université d'Augsbourg (Allemagne). Il permet l'exécution simultanée de plusieurs tâches au sein d'un même coeur. Il a été conçu pour isoler temporellement une tâche de l'influence des autres tâches qu'il exécute. Nous proposons une modélisation de ce processeur qui permet l'évaluation du pire temps d'exécution de la tâche temps réel avec des méthodes statiques. Nous mettons en évidence les deux sources de surestimation liées à notre modèle qui peuvent entraîner ponctuellement des surestimations de respectivement 1 et 3 cycles. En analysant ces sources de surestimation, nous montrons que des méthodes d'analyse statique ne semblent pas être suffisantes pour les supprimer. Nous proposons aussi une analyse de l'impact de quelques modifications du processeur sur le pire temps d'exécution estimé. Ces paramètres sont en particulier la taille de la fenêtre d'instructions et la longueur du pipeline. Pour cette dernière, nous envisageons l'ajout d'étages en 4 endroits significatifs du pipeline. Notre travail ouvre sur des perspectives comme des propositions de modification du pipeline qui permettront l'exécution de plusieurs tâches temps réel ou encore l'augmentation des performances du processeur sans que la précision de l'évaluation du pire temps d'exécution n'en souffre.

Pour répondre à des besoins toujours croissants en puissance de calcul, on a vu se multiplier depuis quelques années les études concernant les architectures parallèles. Malgré la variété des solutions proposées il existe encore une classe d'applications difficiles a exécuter en parallèle. Nous proposons dans cette thèse une architecture massivement parallèle basée sur un réseau régulier de cellules, qui ont la particularité d'être totalement asynchrones et de pouvoir communiquer entre elles grâce a un mécanisme d'acheminement de messages. Chaque cellule comprend une partie de traitement composée d'un petit microprocesseur 8 bits et sa mémoire (donnée plus programme), et une partie routage permettant d'acheminer les messages. Notre second objectif consistait a imaginer puis développer une methode de programmation adaptée a la fois a notre nouvelle architecture et a la classe d'algorithmes visée. La solution étudiée consiste a placer un graphe data flow obtenu a partir du langage lustre sur notre réseau cellulaire. Un premier prototype de ce compilateur a été réalisé, il a permis d'étudier l'importance de paramètres comme la répartition de la charge de calcul entre les cellules ou l'enchainement de l'exécution de plusieurs nœuds du graphe places sur la même cellule

Ce travail propose une approche originale pour l'ordonnancement de tâches sous contraintes de temps et de ressources. Les méthodes et techniques développées s'inscrivent dans la problématique de l'"Analyse Sous Contraintes" (A.S.C.) des problèmes d'ordonnancement. Cette A.S.C. vise à caractériser les ordonnancements admissibles de manière à proposer au décideur un choix d'actions cohérentes vis-à-vis des contraintes, tout en lui offrant une certaine flexibilité face à des aléas éventuels. L'A.S.C. est décrite comme un processus d'inférence mettant en interaction une base de règles et une base de faits temporels et séquentiels représentant les caractéristiques des ordonnancements admissibles. Un logiciel (MASCOT) écrit en Prolog-II a été réalisé selon ce principe. Une nouvelle approche pour l'A.S.C. et plus particulièrement pour le raisonnement temporel sous contraintes de ressources a été développée. L'originalité de cette approche réside essentiellement dans la prise en compte du couplage temps/ressource à l'aide du concept d'intervalle temps-ressource qui conduit à utiliser un raisonnement énergétique. L'intervalle temps-ressource permet de représenter à la fois les tâches ou intervalles consommateurs et les intervalles de temps alloués sur lesquels des ressources sont disponibles, appelés intervalles fournisseurs. Le problème de l'ordonnancement de tâches amène à étudier l'interaction entre intervalles consommateurs et fournisseurs sur la base de considérations énergétiques. Le logiciel MASCOT met en jeu un processus de déduction symbolique. Ce type de déduction a été amélioré par la prise en compte de l'énergie obligatoirement consommée ou consommation obligatoire d'intervalles consommateurs sur un intervalle fournisseur. De nouvelles règles de déduction ont été écrites et intégrées dans MASCOT. D'autre part, un processus de déduction basé sur un raisonnement purement énergétique a été élaboré et implémenté (logiciel REPORT) en Prolog-II. Il utilise un autre type de déduction, la déduction numérique, qui permet d'affiner les bornes temporelles d'un intervalle fournisseur en considérant la consommation obligatoire des autres intervalles consommateurs. En d'autres termes, ces résultats consistent à actualiser des dates limites et correspondent à des conditions nécessaires d'admissibilité ; ils permettent ainsi de détecter des infaisabilités éventuelles. L'outil de modélisation utilisé est le graphe potentiels-bornes qui permet de représenter des contraintes numériques (sur la durée des tâches par exemple) et des contraintes symboliques entre intervalles. Il sert de support à un processus d'inférence par propagation numérique des contraintes.

L'objet des recherches en planification de tâches est d'élaborer des algorithmes et des représentations qui participent à l'autonomie des robots en les dotant de capacités décisionnelles. Classiquement, un plan symbolique synthétisé par un planificateur permet au robot de décider des prochaines actions qu'il doit accomplir pour satisfaire sa mission. Dans cette thèse, nous développons l'idée que les planificateurs actuels, basés sur une représentation logique du monde, ne sont pas suffisants pour traiter des missions où les contraintes de mouvements des robots et celles liées à la manipulation d'objet ne peuvent pas être ignorées à cette étape. Souvent, en robotique, la faisabilité des mouvements et des manipulations est un pré-requis à la bonne exécution d'un plan. Dans cette thèse, nous introduisons un formalisme permettant de prendre en considération ces contraintes dans le modèle utilisé par un planificateur. En nous appuyant sur des résultats issus de la planification de mouvements et de manipulations autant que sur ceux de la planification de tâches, nous proposons un nouveau planificateur capable de raisonner sur ce formalisme. Nous produisons alors des plans définissant non seulement un ordre d'actions mais également les mouvements sans collision nécessaires à son exécution. L'implémentation de ce planificateur est présentée et évaluée.

Le domaine des technologies de l'électronique et de l'informatique a subi d'importantes évolutions dans les dernières années, aussi bien du point de vue matériel que du point de vue applicatif. L'évolution matérielle est en grande partie ''tirée'' par l'augmentation de la densité d'intégration des technologies de fabrication des circuits qui peuvent maintenant mettre en \oe uvre des milliards de transistors. Cette évolution a conduit à la définition de Systems-on-Chip (SoCs) qui intègrent l'ensemble des ''composants'' matériels et logiciels nécessaires à l'exécution des applications. L'un des points importants de l'évolution applicative concerne le besoin de dynamicité afin de permettre une adaptation de l'application à son environnement d'exécution. La seule présence d'un processeur n'est pas toujours satisfaisante et des zones reconfigurables ont alors été proposées pour supporter cette dynamicité. On parle alors de RSoC (Reconfigurable System-on-Chip), ou encore de systèmes reconfigurables sur puce. La gestion efficace d'un RSoC s'est naturellement reportée à l'interface entre logiciel et matériel. Il s'agit donc de proposer aux tâches de l'application les moyens de solliciter les ressources du RSoC (de calcul, de mémorisation, de communication, etc) de façon indépendante de leur implémentation matérielle. L'embarquement d'un système d'exploitation dans ce type de systèmes s'est finalement imposé puisqu'il répond à ce besoin. Si la présence d'un OS permet de gérer des ressources relativement classiques, l'intégration de zones reconfigurables au sein d'un SoC impose de faire évoluer certains services de cet OS. Les travaux de recherche présentés sont liés à cette problématique. Trois axes seront développés : ils concernent la définition d'organisation mémoire reconfigurable et faible consommation ; l'ordonnancement et le placement de tâches au sein d'une zone reconfigurable intégrée dans un SoC et enfin les aspects modélisation qui sont de plus en plus importants dans ce domaine où l'accroissement de la complexité rend la maîtrise de la conception des systèmes de plus en plus délicate.