La démocratisation des nouvelles plateformes d'exécution parallèles et distribuées, notamment les grilles de calcul, a engendré l'émergence de nouvelles d'architectures constituées en grande partie par des ressources fournies par des personnes/organisations volontaires. Ces machines ne sont pas disponibles tout le temps. Elles sont sujettes à des perturbations liées aux incertitudes sur les dates de début et de fin de disponibilités. Pour générer des ordonnancements adaptés à ces plateformes, nous cherchons à optimiser, en plus des fonctions objectifs classiques, un nouveau critère qui caractérise l'aptitude de l'ordonnancement à absorber l'effet des perturbations (la stabilité). Nous nous sommes intéressés dans le cadre de ce travail au problème de l'ordonnancement avec contraintes d'indisponibilité de ressources et d'incertitudes sur les dates d'occurrence des évènements. Nous commençons par étudier le cas préliminaire de ce problème où une seule indisponibilité est possible par machine et où l'incertitude porte sur la durée de l'indisponibilité. Nous généralisons ensuite cette étude pour le cas où plusieurs indisponibilités peuvent être envisagées sur les machines et où l'incertitude porte sur les dates d'occurrences des évènements. Pour l'ensemble de ces problèmes, nous utilisons une technique de tampon pour fournir une famille d'ordonnancements qui optimisent simultanément la performance et la stabilité des ordonnancements générés. Une vaste campagne de simulation des heuristiques proposées conduit à la sélection de configurations qui aboutissent à des résultats satisfaisants en terme de compromis. Mots clés : Parallélisme, ordonnancement, incertitude, disponibilité, stabilité / New platforms for parallel and distributed computing, such grids, are emergent structure build by collecting resources provided by volunteers individuals or organisations. These resources are not always available. They are in fact subject to disturbances related to uncertainty on start and end availability time. In order to design schedules adapted to these platforms we aim to optimise, in addition to the classic objective function, a new criteria that characterise the ability of the schedule to absorb the effect of the perturbation (stability). In this work, we study the problem of scheduling under availability resource constraints and uncertainty on the events occurrence dates. We initially study the elementary case where only one unavailability is allowed per machine and where the duration of the availability is uncertain. We then generalize to the general case when multiple unavailabilities are allowed by machine and where uncertainties are related on the events occurrence dates. For all these problems, we design schedules based on the slack technique, and that optimise both performance and stability. A wide simulation campaign of the designed heuristics lead to the identification of configurations that produces satisfactory results.

L’autonomicité - la capacité des systèmes à se gérer eux-mêmes - est une qualité nécessaire pour parvenir à contrôler des systèmes complexes, c’est à dire des systèmes ouverts, à grande échelle, dynamiques, composés de sous-systèmes tiers hétérogènes et suivant de multiples objectifs, éventuellement en conflit. Dans cette thèse, nous cherchons à fournir des supports génériques et réutilisables pour la conception de tels systèmes autonomiques complexes. Nous proposons une formalisation des objectifs de gestion, une architecture générique pour la conception de systèmes autonomiques multi-objectifs et adaptables, et des organisations génériques pour l’intégration de tels systèmes autonomiques. Nous appliquons nôtre approche au cas d’utilisation des réseaux électriques intelligents, qui sont un parfait exemple de complexité. Nous présentons une plateforme de simulation que nous avons développée et via laquelle nous illustrons nôtre approche, au travers de plusieurs scénarios de simulation. / Autonomic features, i.e. the capability of systems to manage themselves, are necessary to control complex systems, i.e. systems that are open, large scale, dynamic, comprise heterogeneous third-party sub-systems and follow multiple, sometimes conflicting objectives. In this thesis, we aim to provide generic reusable supports for designing complex autonomic systems. We propose a formalisation of management objectives, a generic architecture for designingadaptable multi-objective autonomic systems, and generic organisations integrating such autonomic systems.We apply our approach to the concrete case of smart micro-grids which is a relevant example of such complexity. We present a simulation platform we developped and illustrate our approach via several simulation scenarios.

Ce document présente SCOOP, un nouveau cadriciel Python pour la distribution automatique de hiérarchies de tâches dynamiques axé sur la simplicité. Une hiérarchie de tâches réfère à des tâches qui peuvent récursivement générer un nombre arbitraire de sous-tâches. L’infrastructure de calcul sous-jacente consiste en une simple liste de ressources de calcul. Le cas d’utilisation typique est l’exécution d’un programme principal sous la tutelle du module SCOOP, qui devient alors la tâche racine pouvant générer des sous-tâches au travers de l’interface standard des « futures » de Python. Ces sous-tâches peuvent elles-mêmes générer d’autres sous-sous-tâches, etc. La hiérarchie de tâches complète est dynamique dans le sens où elle n’est potentiellement pas entièrement connue jusqu’à la fin de l’exécution de la dernière tâche. SCOOP distribue automatiquement les tâches parmi les ressources de calcul disponibles en utilisant un algorithme de répartition de charge dynamique. Une tâche n’est rien de plus qu’un objet Python pouvant être appelé en conjonction avec ses arguments. L’utilisateur n’a pas à s’inquiéter de l’implantation du passage de message ; toutes les communications sont implicites. / This paper presents SCOOP, a new Python framework for automatically distributing dynamic task hierarchies focused on simplicity. A task hierarchy refers to tasks that can recursively spawn an arbitrary number of subtasks. The underlying computing infrastructure consists of a simple list of resources. The typical use case is to run the user’s main program under the umbrella of the SCOOP module, where it becomes a root task that can spawn any number of subtasks through the standard “futures” API of Python, and where these subtasks may themselves spawn other subsubtasks, etc. The full task hierarchy is dynamic in the sense that it is unknown until the end of the last running task. SCOOP automatically distributes tasks amongst available resources using dynamic load balancing. A task is nothing more than a Python callable object in conjunction with its arguments. The user need not worry about message passing implementation details; all communications are implicit.

La plupart des systèmes ferroviaires subissent une demande croissante de capacité. Pour y faire face, il faut construire de nouvelles infrastructures ou exploiter plus efficacement celles existantes, notamment en définissant des grilles horaires optimisées. Dans la littérature, la plupart des approches de construction des grilles sont basées sur des représentations macroscopiques de l'infrastructure, ce qui peut conduireà des solutions infaisables ou inefficaces. En revanche, les approches microscopiques reposent sur une modélisation réaliste du système ferroviaire, ce qui garantit la faisabilité et l'efficacité des résultats. Néanmoins, en raison de leur complexité, l'utilisation de ces approches est généralement limitée à une seule gare. Malgré l'optimisation de la grille horaire, les travaux de maintenance peuvent avoir un fort impact sur les circulations des trains. En présence de maintenances, il peut donc être nécessaire de redéfinir la grille horaire pour assurer une exploitation efficace de la capacité. Nous présentons deux contributions principales sous forme de deux approches microscopiques : une pour la conception de grilles horaires et l'autre pour leur redéfinition en cas de maintenance. La deuxième est la première approche microscopique qui apparaît dans la littérature pour aborder ce problème tout en considérant des aspects comme les limitations temporaires de vitesse. Nous démontrons la validité de nos approches et leur applicabilité dans des scénarios réels. De plus, nous montrons que les approches microscopiques peuvent être utilisées pour traiter des zones de l'infrastructure contenant plusieurs gares. / Most railway systems experience a growing demand of railway capacity. To face this demand, either new infrastructure must be built or a more efficient exploitation of the existing one must be attained. Timetables play a determinant role in the efficient capacity exploitation. Most timetabling approaches in the literature are based on macroscopic representations of the infrastructure. This may lead to inefficient and in some cases, impractical solutions. Instead, microscopic approaches are based on more realistic modelling of the elements of the railway system. This guarantees the feasibility of the timetables while promoting an efficient capacity exploitation. However, due to their complexity, the scope of microscopic approaches is typically restricted to main stations. Despite the optimization of timetables, the performance of infrastructure maintenance may severely impact the trains' circulations in the network. Therefore, the timetable may have to be rearranged to ensure an efficient capacity exploitation. We present two main contributions in this thesis: first, a microscopic approach for timetable design. Second, a microscopic approach for timetable rearrangement to cope with maintenance. This is the first microscopic approach in the literature to tackle this problem while also considering specific aspects as temporary speed limitations. After a thorough experimental analysis, we demonstrate the validity of our approaches and their practical applicability in real life scenarios. In particular, we show that microscopic approaches can be used to tackle large areas of the infrastructure, including several stations.

Contrairement aux modèles déterministes, le déroulement d'un modèle stochastique est conditionné par la réalisation de variables aléatoires. L'utilisation de hasard permet d'approcher un résultat le plus souvent incalculable de manière déterministe. En contrepartie, il est nécessaire d'estimer les paramètres des distributions associées aux quantités aléatoires en sortie du modèle stochastique. Ce calcul requiert l'exécution de multiples réplications indépendantes de la même expérience et de ce fait, d'une importante quantité de calcul. Toutes les simulations stochastiques comportent par conception un aspect naturellement parallèle. Elles représentent ainsi une des applications phares pour l'utilisation d'environnements de calculs distribués permettant de partager de la puissance de calcul à l'échelle mondiale, appelée grille de calcul. Bien que 50% des cycles des plus gros supercalculateurs de la planète soient consommés par des calculs stochastiques, les techniques de génération parallèle de nombres pseudoaléatoires sont méconnues. Il existe de ce fait un risque bien réel de produire et de publier des résultats de simulations stochastiques erronés. Cette thèse présente l'état de l'art des méthodes pour la distribution des réplications de simulations stochastiques et contribue à leur développement. Elle propose ainsi des méthodes novatrices permettant d'assurer une traçabilité dans le processus complexe de distribution de simulations stochastiques. Elle expose enfin des applications dans les domaines de l'imagerie médicale nucléaire et des simulations environnementales totalisant plus de 70 années de calcul sur un ordinateur séquentiel.

Une des questions majeures de la physique moderne est la détermination de la nature de la matière noire non-baryonique. Les expériences de détection directe de WIMPs (acronyme signifiant particules massives interagissant faiblement) comme EDELWEISS testent l'hypothèse que celle-ci est composée de particules (neutralino) prédites par la supersymétrie et ayant une section efficace d'interaction avec les nucléons d'environ 10-8 picobarn. Pour ceci, EDELWEISS utilise des détecteurs cryogéniques en germanium ultra-pur à double composante ionisation/chaleur, ce qui permet la discrimination des reculs nucléaires attendus pour les WIMPs des reculs électroniques induits par les particules du bruit de fond radioactif. La principale limitation de cette méthode provient des évènements proches de la surface des détecteurs (dus notamment aux betas) qui peuvent être confondus avec des reculs nucléaires. La solution présentée dans cette thèse est l'utilisation de détecteurs à grilles coplanaires pour le rejet des évènements de surface sur la base des signaux d'ionisation. Nous décrivons le principe de ces détecteurs, la réalisation d'un prototype et son étude : tests pratiqués avec différentes sources radioactives en laboratoire de surface puis sur le site-même de l'expérience au Laboratoire Souterrain de Modane. Les résultats expérimentaux sont analysés en détail et comparés à une modélisation approfondie des signaux attendus pour les diverses populations d'évènements. Le pouvoir de rejet des évènements gamma et des évènements de surface betas obtenu démontre la possibilité d'atteindre au moins 10-8 picobarn dans le cadre de l'expérience EDELWEISS II qui a retenu ce type de détecteur pour l'avenir.

Nous étudions des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Notre problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs. Notre étude comporte trois parties généralisant progressivement le problème. Nous nous limitons dans un premier temps au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est introduit dans la deuxième partie, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Dans la dernière partie nous généralisons le modèle de plate-forme à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque. La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage, sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.

Le but de cette these est d'etudier les schemas de communications les plus utilises, et plus particulierement la diffusion, pour en proposer des implementations efficaces sur des machines paralleles. Dans une premiere partie nous presentons les principales machines paralleles et les differents modes de communication mis en oeuvre dans ces machines. Cette partie illustre le probleme du choix du reseau d'interconnexion pour assembler les processeurs des ordinateurs massivement paralleles. La deuxieme partie est consacree a l'etude des schemas de communications globales dans les grilles toriques en mode store and forward. Dans un premier temps, on presente une nouvelle famille d'arbres de recouvrement disjoints de profondeur minimale, permettant de realiser la diffusion pipeline en temps optimal. Dans un deuxieme temps, on presente l'utilisation d'autres outils tels que les chemins hamiltoniens pour realiser l'echange total. Sur ce dernier type de communication, une etude en mode wormhole est presentee. L'algorithme est inspire du decoupage recursif de la grille torique. Il permet d'obtenir un nombre d'etapes plus faible qu'avec les algorithmes traditionnels en store and forward. Des resultats experimentaux sur machine MegaNode a 128 Transputers, permettent de valider notre etude theorique en mode store and forward. La troisieme partie est consacree a l'etude du recouvrement des communications par des calculs. L'idee consiste a anticiper les communications, en pipelinant l'envoi de petits messages. Mais la taille des messages a envoyer n'est pas facile a calculer. Nous illustrons ce probleme sur l'exemple du produit matrice-vecteur.

Avec la démocratisation des environnements du type grappe et grille de calcul, la performance des opérations de communication collective devient un aspect critique dans le coût total des applications parallèles. Fortement influencées par l'hétérogénéité des ressources, ces opérations dépendent à la fois des paramètres de communication des réseaux et des stratégies de communication employées. Cette thèse a pour objet d'étude l'optimisation des communications collectives selon l'approche préconisée par Karonis, où les différentes grappes de calcul sont organisées en plusieurs couches de communication de manière à minimiser le temps total de communication. Pour cela, nous proposons des modèles de communications qui permettent l'optimisation des communications collectives à travers l'ordonnancement hiérarchique des communications et la prédiction des performances. Dans un premier temps, nous démontrons que l'utilisation du modèle de coût pLogP permet la modélisation des performances de communications collectives dans des environnements homogènes. Ces modèles de performance ont été validés expérimentalement sur différentes plates-formes réseaux (Fast Ethernet, Giga Ethernet et Myrinet). Parallèlement, nous étudions la découverte automatique de la topologie du réseau. En effet, la décomposition de l'environnement de grille en îlots d'homogénéité permettrait la réduction de la complexité des optimisations, notamment dans ce qui concerne la modélisation des performances et l'obtention des caractéristiques du réseau. Notre principale contribution a été de proposer certaines heuristiques d'ordonnancement des communications qui tiennent compte de l'organisation hiérarchique de la grille. Ces heuristiques, adaptées aux différents patrons de communication collective, utilisent les techniques étudiées précédemment (dont la découverte des îlots d'homogénéité et la modélisation des performances) afin de réduire la complexité de l'optimisation des communications et de minimiser le temps total de communication.

En permettant le partage à grande échelle de données et d'algorithmes et en fournissant une quantité importante de puissance de calcul et de stockage, les grilles de calcul sont des plates-formes intéressantes pour les applications d'analyse d'images médicales. Dans cette thèse, nous étudions un problème d'analyse d'images médicales qui s'avère être une application dimensionnante pour les grilles, conduisant au développement de nouvelles méthodes et outils pour la description, l'implémentation et l'optimisation de flots de traitements. Le problème applicatif étudié est l'évaluation de la précision d'algorithmes de recalage d'images médicales en l'absence de vérité terrain. Nous faisons passer à l'échelle une méthode statistique d'évaluation de ces algorithmes et nous montrons des résultats de précision sur une base de données liée au suivi de la radiothérapie du cerveau. Ces résultats permettent notamment de détecter des défauts très légers au sein des données. Nous étendons ce schéma pour quantifier l'impact de la compression des images sur la qualité du recalage. Cette application étant représentative de problèmes typiques survenant sur les grilles, nous nous attachons à son déploiement et à son exécution sur ce type d'infrastructures. Pour faciliter une parallélisation transparente, nous adoptons un modèle générique de flots de traitements, dont nous proposons une nouvelle taxonomie. Pour répondre aux limitations de performance des moteurs d'exécution de flots existants, nous présentons MOTEUR, qui permet d'exploiter les différents types de parallélisme inhérents à ces applications. La définition d'un nouvel opérateur de composition de données facilite la description des applications d'analyse d'images médicales sur les grilles. Par une comparaison entre la grille de production EGEE et des grappes dédiées de Grid'5000, nous mettons en évidence l'importance de la variabilité de la latence sur une grille de production. En conséquence, nous proposons un modèle probabiliste du temps d'exécution d'un flot de traitement sur une grille. Ce modèle est centré sur l'utilisateur : il considère la grille toute entière comme une boîte noire introduisant une latence aléatoire sur le temps d'exécution d'une tâche. A partir de ce modèle, nous proposons trois stratégies d'optimisation visant à réduire l'impact de la latence et de sa variabilité : dans un flot de traitement, grouper les tâches séquentiellement liées permet de réduire la latence moyenne rencontrée, optimiser la valeur du délai d'expiration des tâches prémunit contre les valeurs extrêmes de la latence et optimiser la granularité des tâches permet de réduire le risque de rencontrer de fortes latences. Des accélérations significatives sont ainsi obtenues.