L’informatique utilitaire a évolué au fil des années pour aboutir à ce que nous appelons aujourd’hui le Cloud Computing. Pourtant, ces infrastructures ne sont pas adaptées pour répondre aux besoins de l’Internet des Objets ayant des besoins de calculs à faible latence malgré des ressources limitées. C’est pourquoi, en 2012, Cisco a proposé le paradigme de Fog Computing, consistant à répartir des serveurs sur de nombreux sites placés près des utilisateurs. Dans cette thèse, nous cherchons à créer une solution de stockage unifiée entre les différents sites de Fog. Notre première contribution consiste à évaluer si les solutions de stockage existantes peuvent être utilisées dans un tel environnement. Nous montrons que la solution de stockage InterPlanetary FileSystem (IPFS) reposant sur un protocole similaire à BitTorrent et une table de hachage distribuée (DHT) pour localiser les données est la plus prometteuse. Toutefois, le trafic réseau inter-sites généré impacte négativement les temps de lecture. Notre seconde contribution consiste à coupler IPFS au système de fichiers distribué RozoFS pour limiter ces échanges inter-sites dans le cas d’accès à des données stockées sur le site local. Enfin, notre dernier axe de recherche vise à localiser les données grâce à un protocole reposant sur un arbre des plus courts chemins, de façon à confiner le trafic réseau et à privilégier les nœuds atteignables avec une faible latence. Grâce à de nombreuses expérimentations sur la plateforme Grid’5000, nous montrons que le couplage à un système de fichiers réduit en moyenne de 34% les temps d’accès et que notre protocole de localisation permet un gain de 20% du temps de localisation des données. / Utility Computing has evolved for many years leading to the infrastructure we know today as Cloud Computing. Nevertheless, these infrastructures are unable to satisfy the needs of the Internet of Things which requires low latency computing despite limited resources. In 2012, Cisco proposed a paradigm called Fog Computing, consisting of deploying a huge number of small servers, spread on many sites located at the edge of the network, close to the end devices. In this thesis, we try to create a seamless storage solution between the different Fog sites. Our first contribution consists in comparing existing storage solution and check if they can be used in a such environment. We show that InterPlanetary FileSystem (IPFS), an object store relying on a BitTorrent like protocol and a Distributed Hash Table is a promising solution. Nevertheless, the amount of network traffic exchanged between the sites to locate the data is important and has a non-negligible impact on the overall performance. Our second contribution consists in coupling IPFS with RozoFS, a distributed filesystem deployed on each site to limit the use of the DHT when accessed data are stored on the local site. Finally, we proposed to replace the distributed hash table by a location mechanism relying on a shortest path tree built on the physical topology, in order to contain the network traffic and to first request nodes at a close location, reachable with a low latency. By performing many experiments on the Grid’5000 testbed, we show that the coupling of IPFS with a Scale-Out NAS reduces by 34 % in average the access times and that our protocol to locate the objects reduces by 20 % the time to locate the data.

Cette thèse s'inscrit dans le cadre des grappes dans le projet Grid'5000 (Projet Français pour les grilles). Grid'5000 est une plate-forme expérimentale qui offre la possibilité aux chercheurs de soumettre aux gestionnaires de ressource des programmes (travaux) et d'associer pour chaque requête un environnement. Une grappe est un ensemble de noeuds de calcul, connectés entre eux via un réseau dédié. Le processus de déploiement d'environnement sur les noeuds de calcul n'est pas sans conséquence. Un des problèmes que l'on rencontre est la défaillance des machines. Le démarrage excessif lors de de la phase déploiement peut causer un endomagement de celles-ci. Nous avons ainsi modélisé ce problème sous forme d'un problème d'ordonnancement bicritère. Le premier critère à minimiser comptabilise pour chaque machine (processeur) le nombre de déploiements effectués. Il permet ainsi permet de définir le nombre total de déploiements sur toutes les machines. Nous avons également considéré un second critère à minimiser, le makespan. Nous avons défini un algorithme Groups List Scheduling, basé sur une approche budget, avec un relâchement des contraintes d'optimalité. Cette approche nous a permis de définir une solution (alpha, beta)-budget-relaxée-approchée pour un problème d'optimisation bicritère. Dans le cadre du problème d'ordonnancement bicritère avec déploiement, l'algorithme GLS donne ainsi une solution (4,2)-budget-approchée-relaxée. Nous avons ensuite abordé ce problème d'ordonnancement bicritère avec déploiement en utilisant l'approche «courbe de Pareto». Nous avons défini un algorithme polynômial, qui permet de construire une courbe de Pareto (4+epsilon, 2)-approchée, à partir des solutions fournies par l'algorithme GLS. Une analyse expérimentale nous a permis d'évaluer les performances de l'algorithme GLS et de valider ainsi les rapports

Les algorithmes Branch and Bound (B&B) sont attractifs pour la résolution exacte de problèmes d'optimisation combinatoire (POC) par exploration d'un espace de recherche arborescent. Néanmoins, ces algorithmes sont très gourmands en temps de calcul pour des instances de problèmes de grande taille (exemple : benchmarks de Taillard pour FSP) même en utilisant le calcul sur grilles informatiques [Mezmaz et al., IEEE IPDPS'2007]. Le calcul massivement parallèle fourni à travers les plates-formes de calcul hétérogènes d'aujourd'hui [TOP500 ] est requis pour traiter effi cacement de telles instances. Le dé fi est alors d'exploiter tous les niveaux de parallélisme sous-jacents et donc de repenser en conséquence les modèles parallèles des algorithmes B&B. Dans cette thèse, nous nous attachons à revisiter la conception et l'implémentation des ces algorithmes pour la résolution de POC de grande taille sur (larges) plates-formes de calcul multi-coeurs et multi-GPUs. Le problème d'ordonnancement Flow-Shop (FSP) est considéré comme étude de cas. Une étude expérimentale préliminaire sur quelques grandes instances du FSP a révélé que l'arbre de recherche est hautement irrégulier (en forme et en taille) et très large (milliards de milliards de noeuds), et que l'opérateur d'évaluation des bornes est exorbitant en temps de calcul (environ 97% du temps de B&B). Par conséquent, notre première contribution est de proposer une approche GPU avec un seul coeur CPU (GB&B) dans laquelle seul l'opérateur d'évaluation est exécuté sur GPU. L'approche traite deux dé fis: la divergence de threads et l'optimisation de la gestion de la mémoire hiérarchique du GPU. Comparée à une version séquentielle, des accélérations allant jusqu'à ( 100) sont obtenues sur Nvidia Tesla C2050. L'analyse des performances de GB&B a montré que le surcoût induit par le transfert des données entre le CPU et le GPU est élevé. Par conséquent, l'objectif de la deuxième contribution est d'étendre l'approche (LL-GB&B) a fin de minimiser la latence de communication CPU-GPU. Cet objectif est réalisé grâce à une parallélisation à grain fin sur GPU des opérateurs de séparation et d'élagage. Le défi majeur relevé ici est la divergence de threads qui est due à la nature fortement irrégulière citée ci-dessus de l'arbre exploré. Comparée à une exécution séquentielle, LL-GB&B permet d'atteindre des accélérations allant jusqu'à ( 160) pour les plus grandes instances. La troisième contribution consiste à étudier l'utilisation combinée des GPUs avec les processeurs multi-coeurs. Deux scénarios ont été explorés conduisant à deux approches: une concurrente (RLL-GB&B) et une coopérative (PLL-GB&B). Dans le premier cas, le processus d'exploration est eff ectué simultanément par le GPU et les coeurs du CPU. Dans l'approche coopérative, les coeurs du CPU préparent et transfèrent les sous-problèmes en utilisant le streaming CUDA tandis que le GPU eff ectue l'exploration. L'utilisation combinée du multi-coeur et du GPU a montré que l'utilisation de RLL-GB&B n'est pas bénéfi que et que PLL-GB&B permet une amélioration allant jusqu'à (36%) par rapport à LL-GB&B. Sachant que récemment des grilles de calcul comme Grid5000 (certains sites) ont été équipées avec des GPU, la quatrième contribution de cette thèse traite de la combinaison du calcul sur GPU et multi-coeur avec le calcul distribué à grande échelle. Pour ce faire, les diff érentes approches proposées ont été réunies dans un méta-algorithme hétérofigène qui sélectionne automatiquement l'algorithme à déployer en fonction de la con figuration matérielle cible. Ce méta-algorithme est couplé avec l'approche B&B@Grid proposée dans [Mezmaz et al., IEEE IPDPS'2007]. B&B@Grid répartit les unités de travail (sous-espaces de recherche codés par des intervalles) entre les noeuds de la grille tandis que le méta-algorithme choisit et déploie localement un algorithme de B&B parallèle sur les intervalles reçus. L'approche combinée nous a permis de résoudre à l'optimalité et e fficacement les instances (20 20) de Taillard.

La résolution exacte de problèmes d'optimisation combinatoire avec les algorithmes Branch and Bound (B&B) nécessite un nombre exorbitant de ressources de calcul. Actuellement, cette puissance est offerte par les environnements large échelle comme les grilles de calcul. Cependant, les grilles présentent de nouveaux challenges : le passage à l'échelle, l'hétérogénéité et la tolérance aux pannes. La majorité des algorithmes B&B revisités pour les grilles de calcul sont basés sur le paradigme Master-Worker, ce qui limite leur passage à l'échelle. De plus, la tolérance aux pannes est rarement adressée dans ces travaux. Dans cette thèse, nous proposons trois principales contributions : P2P-B&B, H-B&B et FTH-B&B. P2P-B&B est un famework basé sur le paradigme Master-Worker traite le passage à l'échelle par la réduction de la fréquence de requêtes de tâches et en permettant les communications directes entre les workers. H-B&B traite aussi le passage à l'échelle. Contrairement aux approches proposées dans la littérature, H-B&B est complètement dynamique et adaptatif i.e. prenant en compte l'acquisition dynamique des ressources de calcul. FTH-B&B est basé sur de nouveaux méchanismes de tolérance aux pannes permettant de construire et maintenir la hiérarchie équilibrée, et de minimiser la redondance de travail quand les tâches sont sauvegardées et restaurées. Les approches proposées ont été implémentées avec la plateforme pour grille ProActive et ont été appliquées au problème d'ordonnancement de type Flow-Shop. Les expérimentations large échelle effectuées sur la grille Grid'5000 ont prouvé l'éfficacité des approches proposées.