De nombreux systèmes distribués sont confrontés au problème du déséquilibre de charge entre machines. Avec l'émergence du Big Data, de larges volumes de données aux valeurs souvent biaisées sont produits par des sources hétérogènes pour être souvent traités en temps réel. Il faut donc être capable de s'adapter aux variations de volume/contenu/provenance de ces données. Nous nous intéressons ici aux données RDF, un format du Web Sémantique. Nous proposons une nouvelle approche pour améliorer la répartition des données, basée sur l'utilisation de plusieurs fonctions de hachage préservant l'ordre naturel des données dans le réseau. Cela permet à chaque pair de pouvoir indépendamment modifier la fonction de hachage qu'il applique sur les données afin de réduire l'intervalle de valeurs dont il est responsable. Plus généralement, pour résoudre le problème du déséquilibre de charge, il existe presque autant de stratégies qu'il y a de systèmes différents. Nous montrons que de nombreux dispositifs d'équilibrage de charge sont constitués des mêmes éléments de base, et que seules la mise en œuvre et l'interconnexion de ces éléments varient. Partant de ce constat, nous décrivons les concepts derrière la construction d'une API générique pour appliquer une stratégie d'équilibrage de charge qui est indépendante du reste du code. Mise en place sur notre système, l'API a un impact minimal sur le code métier et permet de changer une partie d'une stratégie sans modifier d'autres composants. Nous montrons aussi que la variation de certains paramètres peut influer sur les résultats obtenus. / Many distributed systems face the problem of load imbalance between machines. With the advent of Big Data, large datasets whose values are often highly skewed are produced by heterogeneous sources to be often processed in real time. Thus, it is necessary to be able to adapt to the variations of size/content/source of the incoming data. In this thesis, we focus on RDF data, a format of the Semantic Web. We propose a novel approach to improve data distribution, based on the use of several order-preserving hash functions. This allows an overloaded peer to independently modify its hash function in order to reduce the interval of values it is responsible for. More generally, to address the load imbalance issue, there exist almost as many load balancing strategies as there are different systems. We show that many load balancing schemes are comprised of the same basic elements, and only the implementation and interconnection of these elements vary. Based on this observation, we describe the concepts behind the building of a common API to implement any load balancing strategy independently from the rest of the code. Implemented on our distributed storage system, the API has a minimal impact on the business code and allows the developer to change only a part of a strategy without modifying the other components. We also show how modifying some parameters can lead to significant improvements in terms of results.

La simulation numérique est un des piliers des Sciences et de l’industrie. La simulationmétéorologique, la cosmologie ou encore la modélisation du coeur humain sont autantde domaines dont les besoins en puissance de calcul sont sans cesse croissants. Dès lors,comment passer ces applications à l’échelle ? La parallélisation et les supercalculateurs massivementparallèles sont les seuls moyens d’y parvenir. Néanmoins, il y a un prix à payercompte tenu des topologies matérielles de plus en plus complexes, tant en terme de réseauque de hiérarchie mémoire. La question de la localité des données devient ainsi centrale :comment réduire la distance entre une entité logicielle et les données auxquelles elle doitaccéder ? Le placement d’applications est un des leviers permettant de traiter ce problème.Dans cette thèse, nous présentons l’algorithme de placement TreeMatch et ses applicationsdans le cadre du placement statique, c’est-à-dire au lancement de l’application, et duplacement dynamique. Pour cette seconde approche, nous proposons la prise en comptede la localité des données dans le cadre d’un algorithme d’équilibrage de charge. Les différentesapproches abordées sont validées par des expériences réalisées tant sur des codesd’évaluation de performances que sur des applications réelles. / Computer simulation is one of the pillars of Sciences and industry. Climate simulation,cosmology, or heart modeling are all areas in which computing power needs are constantlygrowing. Thus, how to scale these applications ? Parallelization and massively parallel supercomputersare the only ways to do achieve. Nevertheless, there is a price to pay consideringthe hardware topologies incessantly complex, both in terms of network and memoryhierarchy. The issue of data locality becomes central : how to reduce the distance betweena processing entity and data to which it needs to access ? Application placement is one ofthe levers to address this problem. In this thesis, we present the TreeMatch algorithmand its application for static mapping, that is to say at the lauchtime of the application,and the dynamic placement. For this second approach, we propose the awareness of datalocality within a load balancing algorithm. The different approaches discussed are validatedby experiments both on benchmarking codes and on real applications.

Les travaux présentés dans cette thèse portent sur la conception de systèmes de fabrication en contexte incertain. La conception d’un tel système peut être vue comme un problème d’optimisation qui consiste à trouver une configuration qui permet d’optimiser certains objectifs tout en respectant des contraintes technologiques et économiques connues. Les systèmes de fabrication étudiés dans ce mémoire sont des lignes d’assemblage et d’usinage. La première est une ligne qui se présente comme une chaîne de postes de travail où, dans chaque poste, les opérations d’assemblage s’exécutent de manière séquentielle. La deuxième, quant à elle, est une ligne particulière qui se compose de machines de transfert comportant plusieurs boîtiers multibroches où les opérations s’exécutent simultanément. Dans un premier temps, nous décrivons de différentes approches permettant de modéliser l’incertitude des données en optimisation. Une attention particulière est portée sur les deux approches suivantes : l’approche robuste et l’analyse de sensibilité. Puis, nous présentons trois applications : la conception d’une ligne d’assemblage et d’une ligne d’usinage soumises aux variations de temps opératoires et la conception d’une ligne d’assemblage avec les temps opératoires connus sous la forme d’intervalles des valeurs possibles. Pour chaque application, nous identifions les performances attendues ainsi que la complexité de la prise en compte de l’incertitude. Ensuite, nous proposons de nouveaux critères d’optimisation en adéquation avec la problématique introduite. Enfin des méthodes de résolution sont développées pour appréhender les différents problèmes mis en évidence par ces critères. / The presented work deals with the design of production systems in uncertain context. The design of such systems can be interpreted as an optimization problem that consists to find a configuration optimizing certain objectives and respecting technological and economical constraints. The production systems studied in this thesis are the assembly and transfer lines. The first one is the line that can be represented as a flow-oriented chain of workstations where, at each workstation, the tasks are executed in a sequential manner. The second is a particular line that is composed of transfer machines including several multi-spindle heads where the tasks are executed simultaneously. At first, we describe different approaches that permit to model the uncertainty of data in optimization. A particular attention is attracted to two following approaches: robust approach and sensitivity analysis. Then, we present three applications: the design of assembly and transfer lines under variations of task processing times and the design of an assembly line with interval task processing times. For each application, we identify the expected performances as well as the complexity of taking into account the uncertainty. Thereafter, we propose some new optimization criteria in adequacy with the introduced problematic. Finally, resolution methods are developed to solve different problems engendered by these criteria.

De nombreuses applications industrielles mettent en jeu des écoulements gaz-particules, comme les turbines aéronautiques et les réacteurs à lit fluidifié de l'industrie chimique. La prédiction des propriétés de la phase dispersée, est essentielle à l'amélioration et la conception des dispositifs conformément aux nouvelles normes européennes des émissions polluantes. L'objectif de cette thèse est de développer le formalisme Euler-Lagrange dans un solveur parallèle et non-structure pour la simulation aux grandes échelles pour ce type d'écoulements. Ce travail est motivé par l'augmentation rapide de la puissance de calcul des machines massivement parallèles qui ouvre une nouvelle voie pour des simulations qui étaient prohibitives il y a une décennie. Une attention particulière a été portée aux structures de données afin de conserver une certaine simplicité et la portabilité du code sur des différentes architectures. Les développements sont valides pour deux configurations : un cas académique de turbulence homogène isotrope décroissante et un calcul polydisperse d'un jet recirculant charge en particules. L'équilibrage de charges de particules est mis en évidence comme une solution prometteuse pour les simulations diphasiques Lagrangiennes afin d'améliorer les performances des calculs lorsque le deséquilibrage est trop important.

Plusieurs applications scientifiques effectuent des calculs sur des matrices creuses de grandes tailles. Pour des raisons d'efficacité en temps et en espace lors du traitement de ces matrices, elles sont stockées selon des formats compressés adéquats. D'un autre coté, la plupart des calculs scientifiques creux se ramènent aux deux problèmes fondamentaux d'algèbre linéaire i.e. la résolution de systèmes linéaires et le calcul d'éléments (valeurs/vecteurs) propres de matrices. Nous étudions dans ce mémoire la distribution, au sein d'un Système Distribué à Grande Echelle (SDGE), des calculs dans des méthodes itératives de résolution de systèmes linéaires et de calcul d'éléments propres et ce, dans le cas creux. Le produit matricevecteur creux (PMVC) constitue le noyau de base pour la plupart de ces méthodes. Notre problématique se ramène en fait à l'étude de la distribution du PMVC sur un SDGE. Généralement, trois étapes sont nécessaires pour accomplir cette tâche, à savoir, (i) le prétraitement, (ii) le traitement et (iii) le post-traitement. Dans la première étape, nous procédons d'abord à l'optimisation de quatre versions de l'algorithme du PMVC correspondant à quatre formats de compression spécifiques de la matrice, puis étudions leurs performances sur des machines cibles séquentielles. Nous nous focalisons de plus sur l'étude de l'équilibrage des charges pour la distribution des données traitées (se ramenant en fait aux lignes de la matrice creuse) sur un SDGE. Concernant l'étape de traitement, elle a consisté à valider l'étude précédente par une série d'expérimentations réalisées sur une plate-forme gérée par l'intergiciel XtremWeb-CH. L'étape de post-traitement, quant à elle, a consisté à analyser et interpréter les résultats expérimentaux obtenus au niveau de l'étape précédente et ce, afin d'en tirer des conclusions adéquates.

L'émergence des applications de bases de données dans les domaines tels que le data warehousing, le data mining et l'aide à la décision qui font généralement appel à de très grands volumes de données rend la parallélisation des algorithmes des jointures nécessaire pour avoir un temps de réponse acceptable. Une accélération linéaire est l'objectif principal des algorithmes parallèles, cependant dans les applications réelles, elle est difficilement atteignable : ceci est dû généralement d'une part aux coûts de communications inhérents aux systèmes multi-processeur et d'autre part au déséquilibre des charges des différents processeurs. En plus, dans un environnement hétérogène multi-utilisateur, la charge des différents processeurs peut varier de manière dynamique et imprévisible. Dans le cadre de cette thèse, nous nous intéressons au traitement de la jointure et de la multi-jointure sur les architectures distribuées hétérogènes, les grilles de calcul et les systèmes de fichiers distribués. Nous avons proposé une variété d'algorithmes, basés sur l'utilisation des histogrammes distribués, pour traiter de manière efficace le déséquilibre des données, tout en garantissant un équilibrage presque parfait de la charge des différents processeurs même dans un environnement hétérogène et multi-utilisateur. Ces algorithmes sont basés sur une approche dynamique de redistribution des données permettant de réduire les coûts de communication à un minimum tout en traitant de manière très efficace le problème de déséquilibre des valeurs de l'attribut de jointure. L'analyse de complexité de nos algorithmes et les résultats expérimentaux obtenus montrent que ces algorithmes possèdent une accélération presque linéaire.

L'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici. Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème " repartitionnement M × N ". Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une " bonne " matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneurs actuels.

Les Piles à Combustible Microbiennes (PCMs) mettent en oeuvre le métabolisme de micro-organismes et utilisent de la matière organique pour générer de l'énergie électrique. Les applications potentielles incluent le traitement d'eau usée autonome en énergie, les bio-batteries, et le grappillage d'énergie ambiante. Les PCMs sont des équipements basse-tension et basse-puissance dont le comportement est influencé par la vitesse à laquelle l'énergie électrique est récupérée. Dans cette thèse, on étudie des méthodes pour récupérer l'énergie électrique de façon efficace. La tension à laquelle l'énergie est récupérée des PCMs influence leur fonctionnement et leurs performances électriques. La puissance délivrée est maximum pour une tension spécifique (environ 1/3 de la tension en circuit-ouvert). Les PCMs ont été testées à ce point en utilisant une charge contrôlée automatiquement qui inclut un algorithme de recherche de puissance maximale. Un tel outil a été utilisé pour évaluer la puissance maximum, la vitesse de consommation du combustible, le rendement Coulombic et le rendement de conversion de 10 PCMs à chambre unique de 1.3 L, construites de façon similaire. Bien que d'autres choix structurels et opératoires peuvent permettre d'améliorer ces performances, ces résultats ont étudié pour la première fois les performances des PCMs en condition de production d'énergie de point de puissance maximal et les PCMs ont été testées avec des conditions de récupération d'énergie réalistes. Récupérer un maximum d'énergie des PCMs est la ligne directrice de ce rapport. Cela est rendu possible par des circuits dédiés de gestion de l'énergie qui embarquent un contrôle contre-réactif pour réguler la tension des PCMs à une valeur de référence qui est égale à une fraction de leur tension en circuit ouvert. Deux scénarios typiques sont développés dans la suite. Une application critique des PCMs concerne le grappillage autonome de petites énergies, pour alimenter des équipements électroniques basse-puissance (e.g. capteurs sans fil). Dans ce cas, les contraintes basse-puissance et basse-tension imposées par les PCMs nécessitent des fonctionnalités de démarrage autonomes. L'oscillateur d'Armstrong, composé d'inductances couplées à fort rapport d'enroulement et d'un interrupteur normalement-fermé permet d'élever des tensions de façon autonome à partir de sources basse-tension continues comme les PCMs. Ce circuit a été associé à des convertisseurs d'électronique de puissance AC/DC et DC/DC pour réaliser respectivement un élévateur-de-tension et une unité de gestion de l'énergie (UGE) auto-démarrante basée sur une architecture flyback. La première est adaptée pour les puissances inférieures à 1 mW, alors que la seconde peut être dimensionnée pour des niveaux de puissance de quelques mW et permet de mettre en oeuvre une commande qui recherche le point de puissance maximal du générateur. Une seconde application d'intérêt concerne le cas où de l'énergie est récupérée depuis plusieurs PCMs. L'association série peut être utilisée pour élever la tension de sortie mais elle peut avoir des conséquences négatives en terme de performances à cause des non-uniformités entre cellules. Cet aspect peut être résolu avec des circuits d'équilibrage de tension. Trois de ces circuits ont été analysés et évalués. Le circuit " complete disconnection " déconnecte une cellule défectueuse de l'association pour s'assurer qu'elle ne diminue pas le rendement global. Le circuit " switched-capacitor " transfère de l'énergie depuis les MFCs fortes vers les faibles pour équilibrer les tensions de toutes les cellules de l'association. Le circuit " switched-MFCs " connecte les PCMs en parallèle et en série de façon alternée. Chacune des trois méthodes peut être mise en oeuvre à bas prix et à haut rendement, la plus efficace étant la " switched-capacitor " qui permet de récupérer plus de 85 % de la puissance maximum idéale d'une association très largement non uniforme

L'évolution rapide des réseaux, des stations de travail, des gros calculateurs sans oublier les ordinateurs personnels, donne naissance à de nouvelles alternatives architecturales pour les traitements parallèles et distribués. Les Grappes, les grilles de calcul et plus récemment le calcul en nuages (Cloud Computing) répondent aux besoins en calcul sans cesse croissants, grâce à des nouveaux paradigmes et concepts logiciels et systèmes basés sur la programmation distribuée. Les principales caractéristiques des applications développées dans ce cadre sont d'être hétérogènes, irrégulières et imprévisibles. Pour permettre une exécution efficace des applications réparties en Java, nous proposons un environnement de programmation et un environnement d'exécution (ADAJ : Adaptative Distributed Applications in Java) qui optimise le placement dynamique des objets de l'application sur les grappes et les grilles d'ordinateurs. Cette répartition s'appuie sur de nouveaux mécanismes d'observation de l'activité des objets et des relations entre eux. Le gain de cette distribution flexible et adaptative des objets se traduit par une meilleure efficacité de l'exécution et la possibilité d'utiliser au mieux la puissance des différents calculateurs, tout en minimisant les coûts de communication et les surcoûts liés au contrôle de l'application. Munie de ces mécanismes, la plate-forme logicielle ADAJ assure une répartition adaptative et automatique des éléments de l'application sur la plateforme d'exécution, répondant de cette façon, aux évolutions du calcul et aux modifications de la disponibilité des ressources. Ce fonctionnement est basé sur un procédé de vol de cycle et permet de contrôler la granularité du traitement. Le programmeur n'a plus en principe, à s'en préoccuper. Les mécanismes ont été implémentés pour diverses plateformes et technologies. Dans un premier temps, ils ont été conçus pour fonctionner sur des grappes de stations de travail. Nous avons ensuite fait évoluer les solutions adoptées pour fonctionner sur des réseaux plus vastes (passage à l'échelle). En particulier, nous avons introduit un framework basé sur des composants logiciels, qui aide le concepteur à bâtir des applications pour grilles d'ordinateurs. Puis, ces travaux ont été étendus, de sorte que la plateforme ADAJ est aujourd'hui, un intergiciel à part entière. Elle est basée sur des web services et son système d'information, sur des systèmes à agents. Les mécanismes d'ADAJ peuvent maintenant gérer des plateformes d'exécution de type grille composées, à priori de milliers de machines. Nous avons finalement testé cette approche pour des problèmes de fouille de données à l'aide d'algorithmes distribués, spécifiquement développés. De cette façon nous avons répondu à la problématique actuelle concernant la mise en oeuvre et l'exploitation d'architecture de grille par des systèmes de type SOKU (Service Oriented Knowledge Utilities). Pour conclure, nous montrons comment nos travaux pourraient être utilisés dans l'environnement des systèmes-sur-puce de nouvelle génération.

Les Réseaux de Capteurs Sans Fil (RCSF) sont de plus en plus exploités par des applications diverses grâce à leur facilité de déploiement et d’auto-configuration. Les applications de collecte de données qui utilisent les RCSF ont souvent un profil convergecast : l’ensemble des données récoltées par tous les capteurs du réseau sont acheminées vers un puits de collecte, grâce à une communication multi-saut. Pendant l’acheminement des données des nœuds de collecte vers le puits, des goulots d’étranglement sont fréquemment observés, principalement au voisinage du puits. Cela est du à la congestion et au phénomène d’entonnoir couramment observé sur le trafic de données ayant un profile convergecast. Outre un risque accru de collision, cela entraîne le débordement des files d’attente des nœuds concernés conduisant à des pertes de données. Cette perte réduit le taux de livraison au puits entraînant une baisse du débit du réseau. Afin de réduire ces pertes et de permettre un meilleur taux de livraison au puits, le trafic doit être équitablement réparti au niveau de chaque saut pendant l’acheminement. Dans cette thèse, nous avons d’une part proposé S-CoLBA (Single channel Collaborative Load Balancing Algorithm), un protocole mono-canal de routage dynamique avec équilibrage de la charge. Sa métrique de routage est basée sur le délais moyen d’accès au medium radio par nœud. Chaque nœud choisit comme prochain saut à destination du puits, un de ses voisins ayant le délais d’accès le plus court. S-CoLBA intègre également une surveillance permanente des files d’attente des nœuds afin de prévenir la congestion et d’éviter le débordement de ces files. D’autre part, nous avons adapté S-CoLBA pour le rendre utilisable dans un réseau multicanal. Cette version du protocole s’appelle M-CoLBA (pour Mulitchannel CoLBA). M-CoLBA évite la congestion en équilibrant la charge grâce à une répartition du trafic au niveau de chaque saut du réseau. Dans un réseau multicanal, le problème de support de diffusion se pose. M-CoLBA introduit des périodes de synchronisations où tous les nœuds utilisent le même canal pour échanger les informations de routage. Ces périodes de synchronisation contribuent à allonger les délais de bout en bout des paquets. Nous avons ainsi optimisé M-CoLBA en "surchargeant" les acquittements des trames avec les informations de routage ( piggybacking) et les états des files d’attente. Cela évite de passer par des périodes de synchronisation pour diffuser ces informations. Cette version optimisée s’appelle ABORt ( Acknowledgement-Based opportunistic Routing protocol). Dans un cas de trafic de type convergecast, ABORt induit une diversité des routes prises par les données collectées, ce qui est bénéfique à la quantité de données transportées et à la robustesse de la solution. Les contributions ont été évaluées par simulation et expérimentation dans un réseau monocanal et multicanal. Les résultats montrent que nos contributions améliorent le taux de livraison des données au puits, optimisent le délais de bout en bout et réduisent la quantité de trafic de contrôle comparé à des solutions déjà existantes. / The popularity of wireless sensor networks (WSNs) is increasing due to their ease ofdeployment and auto-configuration capabilities. They are used in different applica-tion domains including data collection with convergecast scenarios. In convergecast,all data collected in the network is destined to one common node usually called thesink. In case of high carried traffic load and depending on the used routing policy,this many-to-one data collection leads to congestion and queue overflow mainly innodes located near the sink. Congestion and queue overflow reduce delivery ratiothat negatively affects the network efficiency.Wireless sensor nodes are resource constrained devices with limited buffers sizeto store and forward data to the sink. Introducing multichannel communication inWSNs helps to increase the carried traffic load thanks to allowing parallel data trans-mission and reduction of contention and interference. With high traffic load, thenumber of data packets travelling from leaf nodes towards the sink becomes higher.In case the routing scheme does not balance the traffic load, it will be unfairly dis-tributed between forwarding nodes. Thus, nodes that are in part of the routing will beoverloaded while others are less used. Overloaded nodes increase the risk of conges-tion and queue overflow leading to data loss that reduces the throughput. Therefore,we need to couple the routing protocols with traffic load balancing scheme in hightraffic load network scenarios.The goal of this thesis is to propose an efficient routing solution to prevent con-gestion and queue overflow in high data rate convergecast WSNs, in such a way, tooptimize data delivery ratio at the sink node.On the one hand, we proposed a single channel traffic load balancing routingprotocol, named S-CoLBA (Single channel Collaborative Load balancing routing).It relies on data queueing delay metric and best score (according to the value of themetric) next hop neighbors to fairly distribute traffic load in per hop basis in the net-work. Since the carried traffic load increases in multichannel communication, onthe other hand, we adapted our contribution to cope with multichannel WSNs andwe named it as Multichannel CoLBA (M-CoLBA). As broadcasting information isnot straightforward in multichannel, we optimize M-CoLBA to use piggybackingscheme for routing information sharing in the network. This enhanced version iscalled ABORt for Acknowledgement-Based opportunistic Routing protocol and re-lies on ACK frames to share routing information. Doing so helps to optimize dataframe end-to-end delay and to reduce the transmitted beacons in the network. ABORtfairly distributes traffic load in the network and avoids congestion and queue over-flow.We evaluated the performance of our contributions in both simulation using Con-tiki OS Cooja simulator and experiment (only for S-CoLBA) on TelosB motes. Ob-tained results in both simulation and experiment confirm the efficiency of our routingprotocols in term of packet delivery ratio and queue overflow compared to some ex-isting routing protocols in the literature.