Search

Linear algebra applications are commonly used nowadays to solve large scale problems whose size requires the use of distributed and parallel execution on dedicated computation platforms. Many modern linear algebra libraries rely on runtime systems that implement task-based model for their parallel execution. Such tools allow to achieve high performance by performing dynamic scheduling and automatic handling of communications on a set of distributed resources. At the same time, they simplify the implementation of linear algebra operations by decoupling the data distribution from the computations and relieve the programmer from explicit management of communications. Although runtime systems enable the use of virtually any data distribution, most linear algebra applications still rely on the traditional 2D Block Cyclic distribution inherited from the early years of High Performance Computing, when parallel applications were essentially described using basic MPI primitives. In this work we explore the possibilities offered by runtime systems and we design data distributions adapted to the parallel distributed execution of specific linear algebra operations, namely matrix multiplication, symmetric rank-k update, LU and Cholesky factorization. We show that it is possible to design original data distribution schemes that are best fitted to the characteristics of each operation. By taking into account communications reduction and load balancing, the newly developed solutions manage to outperform classic distributions in many configurations, including dense homogeneous cases, both in terms of theoretical and actual parallel performance. This work illustrates that significant improvements over state-of-the-art solutions are achievable by a more careful design of sophisticated data distributions which can in turn be easily implemented using modern task-based linear algebra libraries.; De nos jours, les applications d'algèbre linéraire sont couramment utilisées pour traiter des problèmes dont la grande taille requiert une exécution parallèle distribuée par des plate-formes de calcul dédiées. De nombreuses librairies d'algèbre linéaire reposent sur l'utilisation de systèmes dynamiques utilisant un modèle d'exécution à base de tâches. De tels outils permettent d'atteindre de hauts niveaux de performance en appliquant un ordonnancement dynamique des tâches et une gestion automatique des communications pour un ensemble de ressources de calcul distribuées. Dans le même temps, ils simplifient la mise en oeuvre des opérations d'algèbre linéaire en découplant la distribution de données et les calculs et exemptent le programmeur de la gestion explicite des communications. Bien que les systèmes dynamiques à base de tâches permettent l'utilisation de virtuellement n'importe quelle distribution de données, une grande partie des librairies d'algèbre liéaire reposent toujours sur la distribution classique 2D Bloc Cyclique héritée des premiers temps du domaine du Calcul Haute Performances durant lequel la description des applications parallèles reposait essentiellement sur des primitives MPI rigides. Dans cette thèse, nous explorons les possibilités qu'offrent les systèmes dynamiques à base de tâches et cherchons à concevoir des distributions de données adaptées à l'exécution parallèle distribuée d'opérations d'algèbre linéaire particulières, plus précisément la multiplication de matrices, l'opération "symmetric rank-k update", la factorisation LU et la factorisation de Cholesky. Nous montrons qu'il est possible de concevoir des distributions de données originales mieux adaptées aux caractéristiques de chaque opération. Prenant en compte la réduction des communications et l'équilibrage de la charge de travail, les solutions développées parviennent à surpasser les distributions classiques dans de nombreuses configurations, en particulier dans les cas denses et homogènes, tant sur les performances théoriques qu'expérimentales. Ce travail illustre que d'importants gains par rapport aux solutions de l'état de l'art actuel sont atteignables grâce à une conception plus fine des distributions de données qui peuvent être facilement mises en oeuvre dans des librairies d'algèbre linéaire modernes utilisant un modèle d'exécution à base de tâches.

During the last years, network infrastructure has moved from dedicated-hardware solutions implementing fixed functions to more flexible software based ones. On one hand, SDN (Software Defined Network) can flexibly control forwarding operations, while on the other, NFV (Network Function Virtualization) creates elastic functions that can scale with the user demands. So far, these solutions have been used to simplify network management and operations, but they let envision a network that can automatically react to network events. In this thesis, we explore to what extent these new software networks can be used to react and adapt finely to the network dynamics.Our first contribution focuses on service chaining: the ability to steer flows through a set of waypoints hosting functions before they reach their destinations. We show that a distributed control plane that relies on existing routing protocols and is constituted by autonomous nodes can dynamically steer traffic through chains of services. Our solution finely adapts its decision to the network traffic and automatically balances the induced load on the functions present in the network. Moreover, our proposal, contrary to existing solutions, can be incrementally deployed in today's network.In our second contribution, we compare two types of chaining decisions: a centralized one with an end-to-end view of the chain and a distributed approach that solely routes flow from a function to another. We show that the two decisions are close in realistic topologies. Thus, hop-by-hop chaining could be used without affecting chaining performance. Finally, we explore how software networks can react to network dynamics in datacenters. So far, load balancers use static policies to spread incoming traffic on servers, which leads to imbalance and overprovisioning. We propose to close the loop and dynamically adapt the policy to the server load variation. Our MPC (Model Predictive Control) approach proved to be efficient to reduce load imbalance at a slow pace, thus improving the number of requests a cluster can process.; Au cours de ces dernières années, les réseaux se sont transformés passant d'une infrastructure à base de matériel dédié implémentant des fonctions statiques à des solutions logicielles plus flexibles. D'un côté, le SDN (Software Defined Networks) permet de contrôler les opérations de transmission, alors que de l'autre le NFV (Network Function Virtualization) crée des fonctions élastiques qui peuvent s'adapter à la demande. Jusqu'à présent, ces solutions ont été utilisées pour simplifier la gestion et l'exploitation des réseaux mais elles laissent également envisager un réseau qui peut automatiquement réagir à des événements réseaux. Dans cette thèse, nous explorons dans quelle mesure ces nouveaux réseaux logiciels peuvent être utilisés pour s'adapter à la dynamique inhérentes aux réseaux. Notre première contribution s'intéresse au chaînage de service, c'est à dire la capacité de diriger des flux de données à travers un ensemble de points intermédiaires, qui hébergent des fonctions, avant d'atteindre leur destination. Nous montrons qu'un plan de contrôle distribué, qui s'appuie sur les protocoles de routage existants et qui est constitué par des noeuds autonomes, peut dynamiquement diriger le trafic à travers des chaines de services. Notre solution adapte sa décision au trafic sur le réseau et équilibre automatiquement la charge induite sur les fonctions présentes sur le réseau. De plus, notre proposition, au contraire des solutions existantes, peut être déployée progressivement dans les réseaux actuels. Dans notre seconde contribution, nous comparons deux types de décision de chaînage : une approche centralisée avec une vue de bout en bout de la chaîne et une approche distribuée qui dirige uniquement les flux d'une fonction à l'autre. Nous montrons que ces deux décisions sont proches dans des topologies réalistes. Ainsi, un chaînage saut par saut pourrait être utilisé sans affecter les performances du réseau.Finalement, nous explorons comment les réseaux logiciels peuvent réagir à la dynamique des réseaux dans les centres de données. Jusqu'à présent, des équilibreurs de charges utilisaient des politiques statiques afin de répartir le trafic sur les serveurs, ce qui amenait du déséquilibre et gâchait des ressources. Nous proposons d'asservir le système et d'adapter dynamiquement la politique à la variation de charge des serveurs. Notre approche MPC (Model Predictive Control) est efficace afin de réduire le déséquilibre de charge à une basse fréquence de contrôle améliorant ainsi le nombre de requêtes qu'un ensemble de serveur peut traiter.

In the high-performance computing field (HPC), storage systems are an important performance factor. Using object storage systems coupled to distributed metadata services enable to overcome limitations induced by the POSIX norm, and to improve the data access concurrency. But this solution comes with its own drawbacks : it requires to deal with metadata distributions and load-balancing for metadata servers (MDS). This work aims to design a new metadata distribution method enabling toefficiently load balance requests between MDS for exascale HPC request flows. In this way, we develop a method named Load-Adaptive Distribution (or LAD), which rebalances the workload only when it is required, and its extension named Load-Adaptive Distribution with Temporal Window (or LAD-TW), which provides a betterworkload evaluation. In order to evaluate our methods and compare them with some state-of-the-art methods, we have developed MeDiE, for Metadata Distribution Evaluator, an evaluation tool dedicated to metadata distribution methods. It enables load-balancing analysis on different and representative request flows and allows us to prove the benefit of using the LAD and LAD-TW methods., Dans le domaine du calcul haute performance (HPC), le stockage de plus en plus de données devient un facteur de performance à prendre en compte. Pour cela, l’utilisation des systèmes de stockage objet et des services de métadonnées distribués permet de pallier les limitations induites par la norme POSIX et d’améliorer la concurrence des accès. Toutefois, cela engendre de nouvelles problématiques telles que la distribution des métadonnées et l’équilibrage de charge des serveurs de métadonnées (MDS). Cette thèse a pour objectif de concevoir une nouvelle méthode de distribution des métadonnées permettant un équilibrage de lacharge des serveurs sur un flux de requêtes HPC EXASCALE. Dans cette optique, nous avons développé la méthode Distribution adaptative à la charge (ou LAD) effectuant des redistributions de charge seulement quand cela est nécessaire, ainsi que sa variante avec fenêtre temporelle LAD-TW permettant une meilleure évaluation de la charge des serveurs. Afin d’évaluer nos méthodes et de les comparer à celles de l’état de l’art, nous avons conçu et développé MeDiE (pour Metadata Distribution Evaluator), un outil d’évaluation pour les méthodes de distribution des métadonnées. Il permet une étude de la répartition de la charge des différents serveurs, selon plusieurs flux de requêtes caractéristiques. Nous avons ainsi pu observer l’apport des méthodes LAD et LAD-TW par rapport aux méthodes de l’état de l’art testées.

This thesis focuses on multi-objective optimization problems arising when running scientific applications on high performance computing platforms and streaming applications on embedded systems. These optimization problems are all proven to be NP-complete, hence our efforts are mainly on designing efficient heuristics for general cases, and proposing optimal solutions for special cases.Some scientific applications are commonly modeled as rooted trees. Due to the size of temporary data, processing such a tree may exceed the local memory capacity. A practical solution on a multiprocessor system is to partition the tree into many subtrees, and run each on a processor, which is equipped with a local memory. We studied how to partition the tree into several subtrees such that each subtree fits in local memory and the makespan is minimized, when communication costs between processors are accounted for.Then, a practical work of tree scheduling arising in parallel sparse matrix solver is examined. The objective is to minimize the factorization time by exhibiting good data locality and load balancing. The proportional mapping technique is a widely used approach to solve this resource-allocation problem. It achieves good data locality by assigning the same processors to large parts of the task tree. However, it may limit load balancing in some cases. Based on proportional mapping, a dynamic scheduling algorithm is proposed. It relaxes the data locality criterion to improve load balancing. The performance of our approach has been validated by extensive experiments with the parallel sparse matrix direct solver PaStiX.Streaming applications often appear in video and audio domains. They are characterized by a series of operations on streaming data, and a high throughput. Multi-Processor System on Chip (MPSoC) is a multi/many-core embedded system that integrates many specific cores through a high speed interconnect on a single die. Such systems are widely used for multimedia applications. Lots of MPSoCs are batteries-operated. Such a tight energy budget intrinsically calls for an efficient schedule to meet the intensive computation demands. Dynamic Voltage and Frequency Scaling (DVFS) can save energy by decreasing the frequency and voltage at the price of increasing failure rates. Another technique to reduce the energy cost and meet the reliability target consists in running multiple copies of tasks. We first model applications as linear chains and study how to minimize the energy consumption under throughput and reliability constraints, using DVFS and duplication technique on MPSoC platforms.Then, in a following study, with the same optimization goal, we model streaming applications as series-parallel graphs, which are more complex than simple chains and more realistic. The target platform has a hierarchical communication system with two levels, which is common in embedded systems and high performance computing platforms. The reliability is guaranteed through either running tasks at the maximum speed or triplication of tasks. Several efficient heuristics are proposed to tackle this NP-complete optimization problem.; Cette thèse se concentre sur les problèmes d'optimisation multi-objectifs survenant lors de l'exécution d'applications scientifiques sur des plates-formes de calcul haute performance et des applications de streaming sur des systèmes embarqués. Ces problèmes d'optimisation se sont tous avérés NP-complets, c'est pourquoi nos efforts portent principalement sur la conception d'heuristiques efficaces pour des cas généraux et sur la proposition de solutions optimales pour des cas particuliers.Certaines applications scientifiques sont généralement modélisées comme des arbres enracinés. En raison de la taille des données temporaires, le traitement d'une telle arborescence peut dépasser la capacité de la mémoire locale. Une solution pratique sur un système multiprocesseur consiste à partitionner l'arborescence en plusieurs sous-arbres, et à exécuter chacun d'eux sur un processeur, qui est équipé d'une mémoire locale. Nous avons étudié comment partitionner l'arbre en plusieurs sous-arbres de sorte que chaque sous-arbre tienne dans la mémoire locale et que le makespan soit minimisé, lorsque les coûts de communication entre les processeurs sont pris en compte. Ensuite, un travail pratique d'ordonnancement d'arbres apparaissant dans un solveur de matrice clairsemée parallèle est examiné. L'objectif est de minimiser le temps de factorisation en présentant une bonne localisation des données et un équilibrage de charge. La technique de cartographie proportionnelle est une approche largement utilisée pour résoudre ce problème d'allocation des ressources. Il réalise une bonne localisation des données en affectant les mêmes processeurs à de grandes parties de l'arborescence des tâches. Cependant, cela peut limiter l'équilibrage de charge dans certains cas. Basé sur une cartographie proportionnelle, un algorithme d'ordonnancement dynamique est proposé. Il assouplit le critère de localisation des données pour améliorer l'équilibrage de charge. La performance de notre approche a été validée par de nombreuses expériences avec le solveur direct à matrice clairsemée parallèle PaStiX. Les applications de streaming apparaissent souvent dans les domaines vidéo et audio. Ils se caractérisent par une série d'opérations sur le streaming de données et un débit élevé. Le système multiprocesseur sur puce (MPSoC) est un système embarqué multi / plusieurs cœurs qui intègre de nombreux cœurs spécifiques via une interconnexion haute vitesse sur une seule puce. De tels systèmes sont largement utilisés pour les applications multimédias. De nombreux MPSoC fonctionnent sur piles. Un budget énergétique aussi serré nécessite intrinsèquement un calendrier efficace pour répondre aux demandes de calcul intensives. La mise à l'échelle dynamique de la tension et de la fréquence (DVFS) peut économiser de l'énergie en diminuant la fréquence et la tension au prix d'une augmentation des taux de défaillance. Une autre technique pour réduire le coût énergétique et atteindre l'objectif de fiabilité consiste à exécuter plusieurs copies de tâches. Nous modélisons d'abord les applications sous forme de chaînes linéaires et étudions comment minimiser la consommation d'énergie sous des contraintes de débit et de fiabilité, en utilisant DVFS et la technique de duplication sur les plates-formes MPSoC.Ensuite, dans une étude suivante, avec le même objectif d'optimisation, nous modélisons les applications de streaming sous forme de graphes série-parallèle, plus complexes que de simples chaînes et plus réalistes. La plate-forme cible dispose d'un système de communication hiérarchique à deux niveaux, ce qui est courant dans les systèmes embarqués et les plates-formes informatiques hautes performances. La fiabilité est garantie par l'exécution des tâches à la vitesse maximale ou par la triplication des tâches. Plusieurs heuristiques efficaces sont proposées pour résoudre ce problème d'optimisation NP-complet.

In order to express parallelism, parallel sparse direct solvers take advantage of the elimination tree to exhibit tree-shaped task graphs, where nodes represent computational tasks and edges represent data dependencies. One of the pre-processing stages of sparse direct solvers consists of mapping computational resources (processors) to these tasks. The objective is to minimize the factorization time by exhibiting good data locality and load balancing. The proportional mapping technique is a widely used approach to solve this resource-allocation problem. It achieves good data locality by assigning the same processors to large parts of the elimination tree. However, it may limit load balancing in some cases. In this paper, we propose a dynamic mapping algorithm based on proportional mapping. This new approach, named Steal, relaxes the data locality criterion to improve load balancing. In order to validate the newly introduced method, we perform extensive experiments on the PaStiX sparse direct solver. It demonstrates that our algorithm enables better static scheduling of the numerical factorization while keeping good data locality., Les solveurs parallèles directs creux se servent de l’arbre d’ élimination pour obtenir des graphes de tâches sous forme d’arbres, où les nœuds représentent des tâches de calcul, et les arêtes des dépendances de données. Une des premières étapes de ces solveurs consiste à placer les tâches sur les ressources (les processeurs). Le but est de minimiser le temps de factorisation, en ayant un bon équilibrage de charge et une bonne localité des données. La technique de place-ment proportionnel est utilisée afin d’avoir une bonne localité : un même processeur va traiter une branche de l’arbre d’élimination et il y a peu de communications à faire lors de la factorisation. Cependant, dans certains cas, l’équilibrage de charge n’est pas parfait. Nous proposons un nouvel algorithme dynamique de placement, basé sur le placement proportionnel, qui améliore l’équilibrage de charge au prix d’une légère perte en localité. De nombreuses expériences et simulations sur le solveur direct creux PaStiX permettent de démontrer que notre algorithme permet un meilleur ordonnancement pour la factorisation numérique, tout en gardant une bonne localité des données.

MANET networks are mobile networks capable of wireless communications without any pre-existing infrastructure. MANET networks are characterized by their dynamic environments, this feature makes routing problematic in case of instability of the elements that make up non-direct communications. To overcome these difficulties, new types of routing protocols have emerged, including multi-path routing protocols. Multi-path routing seems to be an effective solution in wireless networks by providing solutions to link failure with the distributtion of the traffic on multiple paths, this improves the performance of communications. The main objective of this thesis is to study MC routing techniques in a wireless context in order to obtain better performance., Les réseaux MANET sont des réseaux mobiles capables de fonctionner sans fil ni infrastructure préexistante. Les réseaux MANET sont caractérisés par leurs environnements dynamiques, cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Pour surmonter ces difficultés, de nouveaux types de protocoles de routage sont apparus, dont les protocoles de routage multi chemins. Le routage multi chemin semble être une solution efficace dans les réseaux sans fil en permettant de se prémunir contre le problème de rupture de liens et de distribuer le trafic sur plusieurs chemins, ceci permet d’améliorer les performances des communications. L’objectif principal de cette thèse est d’étudier les techniques de routage multi-chemins dans un contexte sans fil en vue d’obtenir de meilleures performances.

Scientific applications have an increasing need of resources and many grand scientific challenges require exascale compute capabilities to be addressed. One major concern to achieve exascale is programmability. New automatic methods are required to fill the gap between developers of scientific applications and HPC experts. In addition, as scientific applications are becoming more and more complex and are supposed to run at extreme scale, new tools are required to assist developers in the debugging phase of application development. This thesis explores the combination of static and dynamic methods to improve programmability of HPC applications. Two major issues are investigated: the complexity of programming heterogeneous architectures and the prevention of deadlocks in parallel programs.The first part of this thesis investigates the automatic task adaptation for heterogeneous architectures. More precisely, we propose a new method to improve programmability of heterogeneous architectures. The programmer expresses the parallelism of his application through a sequence of OpenCL tasks without considering issues related to the underlying architecture where its code will be executed. Then our method automatically partitions the tasks into sub-tasks executed by each device and handles load balancing between the devices to take full advantage of the machine capabilities.The second part of this thesis investigates the automatic detection and prevention of deadlocks in parallel programs. We propose a novel static analysis to precisely detect execution paths in parallel programs potentially leading to deadlocks. This static analysis is then combined with a dynamic instrumentation of the code to automatically prevent deadlocks at runtime.The solutions proposed in this thesis have been tested and validated on real parallel applications., Les applications de calcul scientifique ont besoin de ressources de calcul de plus en plus importantes et beaucoup de grands challenges scientifiques exigent des capacités de calcul Exascale (10 puissance 18 calculs par seconde) pour être relevés. L’un des principaux obstacles pour atteindre l’Exascale est la difficulté de programmer les architectures parallèles actuelles. De nouvelles méthodes automatiques sont nécessaires pour combler l’écart entre les développeurs d’applications scientifiques et les experts en calcul haute performance. De plus, les applications scientifiques devenant de plus en plus complexes et étant supposées s’exécuter à très large échelle, de nouveaux outils sont nécessaires pour aider les développeurs lors de la phase de débogage des programmes. Cette thèse explore la combinaison de méthodes statiques et dynamiques pour faciliter la programmation des applications de calcul haute performance. Deux enjeux majeurs sont étudiés : faciliter la programmation des architectures hétérogènes et prévenir les interblocages dans les programmes parallèles.La première partie de cette thèse s’intéresse à l’adaptation automatique des tâches de calcul aux architectures hétérogènes. Nous proposons une nouvelle méthode pour faciliter la programmation des architectures hétérogènes composées de plusieurs unités de calcul (CPUs et GPUs). Le programmeur exprime le parallélisme de son application sous forme de tâches OpenCL sans se soucier des problèmatiques liées à l’architecture sur laquelle son code sera exécuté. Ensuite notre méthode partitionne automatiquement chaque tâche en sous-tâches et équilibre la charge de travail entre les unités de calcul afin de tirer pleinement avantage de toutes les ressources de calcul de la machine.La deuxième partie de cette thèse porte sur la détection automatique des interblocages dans les programmes parallèles. Nous proposons une nouvelle analyse statique permettant de détecter précisément les chemins d’exécution menant à des interblocages dans les programmes parallèles. Cette analyse statique est ensuite combinée à une instrumentation dynamique du code afin de prévenir les interblocages à l’exécution.Les solutions proposées dans cette thèse ont été testée et validées sur des cas réels d’applications parallèles.

International audience; Dans les algorithmes de cartographie d'Internet, l'un des problèmes clés à résoudre est celui de la découverte des différentes interfaces de sortie d'un routeur en cas d'équilibrage de charge: combien de sondes doit-on envoyer tester la connexion pour être raisonnablement certain d'avoir découvert toutes les interfaces ? Une des solutions existantes est une variante du problème du collecteur de coupons, qui consiste à associer à chaque nombre d'interfaces découvertes un nombre de sondes au-delà duquel on considère que l'on peut s'arrêter. Dans cet article, nous donnons une formule close pour l'association et prouvons sa quasi-optimalité.ne formule close pour l'association et prouvons sa quasi-optimalité.

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.; 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.; 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.

Monte Carlo particle transport applications consist in studying the behaviour of particles moving about a simulation domain. Particles distribution among simulation domains is not uniform and change dynamically during simulation. The parallelization of this kind of applications on massively parallel architectures leads to solve a complex issue of workloads and data balancing among numerous compute cores.We started by identifying parallelization pitfalls of Monte Carlo particle transport applications using theoretical and experimental analysis of reference parallelization methods. A semi-dynamic based on partitioning techniques has been proposed then. Finally, we defined a dynamic approach able to redistribute workloads and data keeping a low communication volume. The dynamic approach obtains speedups using strong scaling and a memory footprint reduction compared to the perfectly balanced domain replication method.; Les applications de transport de particules Monte-Carlo consistent à étudier le comportement de particules se déplaçant dans un domaine de simulation. La répartition des particules sur le domaine de simulation n'est pas uniforme et évolue dynamiquement au cours de la simulation. La parallélisation de ce type d'applications sur des architectures massivement parallèles amène à résoudre une problématique complexe de répartition de charges de calculs et de données sur un grand nombre de cœurs de calcul.Nous avons d'abord identifié les difficultés de parallélisation des applications de transport de particules Monte-Carlo à l'aide d'analyses théoriques et expérimentales des méthodes de parallélisation de référence. Une approche semi-dynamique reposant sur des techniques de partitionnement a ensuite été proposée. Enfin, nous avons défini une approche dynamique capable de redistribuer les charges de calcul et les données tout en maintenant un faible volume de communication. L'approche dynamique a obtenu des accélérations en extensibilité forte et une forte réduction de la consommation mémoire par rapport à une méthode de réplication de domaine parfaitement équilibrée.

Distributed data store are massively used in the actual context of Big Data. In addition to provide data management features, those systems have to deal with an increasing amount of queries sent by distant users in order to process data mining or data visualization operations. One of the main challenge is to evenly distribute the workload of queries between the nodes which compose these system in order to minimize the treatment time. In this thesis, we tackle the problem of query allocation in a distributed environment. We consider that data are replicated and a query can be handle only by a node storing the concerning data. First, near-optimal algorithmic proposals are given when communications between nodes are asynchronous. We also consider that some nodes can be faulty. Second, we study more deeply the impact of data replication on the query treatement. Particularly, we present an algorithm which manage the data replication based on the demand on these data. Combined with our allocation algorithm, we guaranty a near-optimal allocation. Finally, we focus on the impact of data replication when queries are received as a stream by the system. We make an experimental evaluation using the distributed database Apache Cassandra. The experiments confirm the interest of our algorithmic proposals to improve the query treatement compared to the native allocation scheme in Cassandra., Les systèmes de stockage distribués sont massivement utilisés dans le contexte actuel des grandes masses de données. En plus de gérer le stockage de ces données, ces systèmes doivent répondre à une quantité toujours plus importante de requêtes émises par des clients distants afin d’effectuer de la fouille de données ou encore de la visualisation. Une problématique majeure dans ce contexte consiste à répartir efficacement les requêtes entre les différents noeuds qui composent ces systèmes afin de minimiser le temps de traitement des requêtes ( temps maximum et en moyenne d’une requête, temps total de traitement pour toutes les requêtes...). Dans cette thèse nous nous intéressons au problème d’allocation de requêtes dans un environnement distribué. On considère que les données sont répliquées et que les requêtes sont traitées par les noeuds stockant une copie de la donnée concernée. Dans un premier temps, des solutions algorithmiques quasi-optimales sont proposées lorsque les communications entre les différents noeuds du système se font de manière asynchrone. Le cas où certains noeuds du système peuvent être en panne est également considéré. Dans un deuxième temps, nous nous intéressons à l’impact de la réplication des données sur le traitement des requêtes. En particulier, un algorithme qui adapte la réplication des données en fonction de la demande est proposé. Cet algorithme couplé à nos algorithmes d’allocation permet de garantir une répartition des requêtes proche de l’idéal pour toute distribution de requêtes. Enfin, nous nous intéressons à l’impact de la réplication quand les requêtes arrivent en flux sur le système. Nous procédons à une évaluation expérimentale sur la base de données distribuées Apache Cassandra. Les expériences réalisées confirment l’intérêt de la réplication et de nos algorithmes d’allocation vis-à-vis des solutions présentes par défaut dans ce système.

Software-Defined Networking (SDN) has emerged as a new intelligent architecture for network programmability. The primary idea behind SDN is to move the control-plane outside the switches and enable external control of data-plane through a logical software entity called controller. Such approach benefits mobile network management by brining complete intelligence to the logically centralized controller. Network Function Virtualization (NFV) is the process of relocating or migrating network functions from dedicated hardware to generic servers. SDN and NFV are two closely related technologies that are often used together. The traditional mobile network architecture due to its strongest coupling between control and data planes along with limitations in scalability and flexibility requires the usage of cloud computing along with the recent revolutionary approaches in networking such as SDN and NFV to have an architecture that deploys on demand "Network-as-a-Service" for users. The global research focus of this thesis falls in to two main use cases of next generation mobile networks such as Telco and Vertical. In the telco use cases, we exploit the advantages of SDN to have flexible control framework for both Self-Organizing Networks (SON) and dynamic user processing split. In vertical use case, we apply various advantages of SDN and OpenFlow protocol to efficiently utilize the scare radio resources of wireless backhaul network in the train-to-ground communication system. Our SDN framework in general can be an efficient and alternative solution for RAN management i.e. Radio Optimization, Network Optimization, Mobility Management and Load Balancing can be achieved with such framework. Through analysis and experimentation of SDN frameworks for RAN, we shows that the proposed solutions can bring set of advantages to wireless networks such as flexibility, programmability, unified management, and enables new services, Le SDN (Software-Defined Networking) émerge comme une nouvelle architecture pour la programmation des réseaux. A l'origine, l'idée du SDN est de déplacer le plan de contrôle à l'extérieur des équipements, et de permettre ainsi un contrôle déporté de l'ensemble depuis une entité logicielle logique nommée "contrôleur". Le principal avantage d'une telle approche est de centraliser donc toute l'intelligence de gestion du réseau dans le contrôleur, qui s'appuie pour cela sur des protocoles standard et assure par ce biais la reprogrammation de la totalité de la partie du réseau sous son contrôle. L'évolution technologique vers le SDN est toujours en cours dans des scénarios de déploiement programmable et flexible des réseaux mobiles. Le NFV (Network Function Virtualization) est le processus de déplacement ou de migration des fonctions réseau d'un équipement dédié de réseau vers des serveurs génériques dans le Cloud. Les SDN et NFV sont deux technologies étroitement liées qui sont souvent utilisées ensemble. Le couplage fort entre les plans de contrôle et de données, ainsi que les limitations en matière de passage à l'échelle et de flexibilité, font que la virtualisation des réseaux mobiles actuels nécessite non seulement l'utilisation du Cloud Computing mais aussi les récentes innovations telles que SDN et NFV pour pouvoir permettre un déploiement à la demande des services réseaux (Network-as-a-Service) aux utilisateurs. Les lignes de recherche globales de cette thèse s'inscrivent dans deux principaux cas d'utilisation. Ces cas d'utilisation, bien qu'appelés de la "prochaine génération de réseaux mobiles", sont le "Telco" et le "Vertical", qui apparaissent ici couplés, les deux étant traditionnellement complètement séparés. Dans les cas d'utilisation de "télécommunications", nous exploitons les avantages de SDN pour avoir un cadre de contrôle flexible pour les réseaux d'auto-organisation (SON) et la division de traitement dynamique des utilisateurs. Dans le cas d'utilisation de "verticale", nous appliquons divers avantages du protocole SDN et OpenFlow pour utiliser efficacement les ressources radio du réseau de backhaul dans le système de communication train-sol. Notre cadre d'étude du SDN, en général, peut être une solution efficace et alternative pour la gestion RAN (Radio Access Network), c'est-à-dire pour des objectives comme l'optimisation des ressources radio, l'optimisation du réseau, la gestion de la mobilité et l'équilibrage de la charge, peuvent être atteint avec ce cadre. Grâce à l'analyse et l'expérimentation concrète des SDN et NFV pour le RAN, nous montrons que les solutions proposées dans ce travail peuvent apporter un faisceau d'avantages évidents aux réseaux mobiles tels que la flexibilité, la programmabilité, la gestion unifiée et la mise en œuvre de nouveaux services

Load balancing is an important step conditioning the performance of parallel applications. The goal is to distribute roughly equal amounts of computational load across a number of processors, while minimising interprocessor communication. A common approach to model the problem is based on graph structures and graph partitioning algorithms. Moreover, new challenges involve the simulation of more complex physical phenomena, where different parts of the computational domain exhibit different physical behavior. Such simulations follow the paradigm of multi-physics or multi-scale modeling approaches. Combining such different models in massively parallel computations is still a challenge to reach high performance. Additionally, traditional load balancing algorithms are often inadequate, and more sophisticated solutions should be explored. In this thesis, we propose new graph partitioning algorithms that balance the load of such simulations, refered to as co-partitioning. We formulate this problem with the use of graph partitioning with initially fixed vertices which we believe represents efficiently the additional constraints of coupled simulations. We have therefore developed a direct algorithm for graph partitioning that manages successfully problems with fixed vertices. The algorithm is implemented inside Scotch partitioner and a series of experiments were carried out on the DIMACS graph collection. Moreover we proposed three copartitioning algorithms that respect the constraints of the respective coupled codes. We finally validated our algorithms by an experimental study comparing our methods with current strategies on artificial cases and on real-life coupled simulations.; Dans le contexte du calcul scientique, l'équilibrage de la charge est un problème crucial qui conditionne la performance des simulations numériques parallèles. L'objectif est de répartir la charge de travail entre un nombre de processeurs donné, afin de minimiser le temps global d'exécution. Une stratégie populaire pour résoudre ce problème consiste à modéliser la simulation à l'aide d'un graphe et à appliquer des algorithmes de partitionnement. En outre, les simulations numériques tendent à se complexifier, notamment en mixant plusieurs codes représentant des physiques différentes ou des échelles différentes. On parle alors de couplage de codes multi-physiques ou multi-échelles. Dans ce contexte, le problème de l'équilibrage de charge devient également plus difficile, car il ne s'agit plus d'équilibrer chacun des codes séparément, mais l'ensemble de ces codes pris dans leur globalité. Dans ce travail, on propose de resoudre ce problème en utilisant le modèle de partitionnement à sommets fixes qui pourrait représenter efficacement les contraintes supplémentaires imposées par les codes couplés (co-partitionnement). Nous avons donc développé un algorithme direct de partitionnement de graphe qui gère des sommets fixes. L'algorithme a été implémenté dans le partitionneur Scotch et une série d'expériences ont été menées sur la collection des graphes DIMACS. Ensuite nous avons proposé trois algorithmes de co-partitionnement qui respectent les contraintes issues des codes couplés respectifs. Nous avons egalement validé nos algorithmes par une étude expérimentale en comparant nos méthodes aux strategies actuelles sur des cas artificiels ainsi que sur des codes réels couplés.

Nowadays stream analysis is used in many context where the amount of data and/or the rate at which it is generated rules out other approaches (e.g., batch processing). The data streaming model provides randomized and/or approximated solutions to compute specific functions over (distributed) stream(s) of data-items in worst case scenarios, while striving for small resources usage. In particular, we look into two classical and related data streaming problems: frequency estimation and (distributed) heavy hitters. A less common field of application is stream processing which is somehow complementary and more practical, providing efficient and highly scalable frameworks to perform soft real-time generic computation on streams, relying on cloud computing. This duality allows us to apply data streaming solutions to optimize stream processing systems. In this thesis, we provide a novel algorithm to track heavy hitters in distributed streams and two extensions of a well-known algorithm to estimate the frequencies of data items. We also tackle two related problems and their solution: provide even partitioning of the item universe based on their weights and provide an estimation of the values carried by the items of the stream. We then apply these results to both network monitoring and stream processing. In particular, we leverage these solutions to perform load shedding as well as to load balance parallelized operators in stream processing systems.; L’analyse de flux de données est utilisée dans beaucoup de contexte où la masse des données et/ou le débit auquel elles sont générées, excluent d’autres approches (par exemple le traitement par lots). Le modèle flux fourni des solutions aléatoires et/ou fondées sur des approximations pour calculer des fonctions d’intérêt sur des flux (repartis) de n-uplets,en considérant le pire cas, et en essayant de minimiser l’utilisation des ressources. En particulier, nous nous intéressons à deux problèmes classiques : l’estimation de fréquence et les poids lourds. Un champ d’application moins courant est le traitement de flux qui est d’une certaine façon un champ complémentaire aux modèle flux. Celui-ci fournis des systèmes pour effectuer des calculs génériques sur les flux en temps réel souple, qui passent à l’échelle. Cette dualité nous permetd’appliquer des solutions du modèle flux pour optimiser des systèmes de traitement de flux. Dans cette thèse, nous proposons un nouvel algorithme pour la détection d’éléments surabondants dans des flux repartis, ainsi que deux extensions d’un algorithme classique pour l’estimation des fréquences des items. Nous nous intéressons également à deux problèmes : construire un partitionnement équitable de l’univers des n-uplets par rapport à leurs poids et l’estimation des valeurs de ces n-uplets. Nous utilisons ces algorithmes pour équilibrer et/ou délester la charge dans les systèmes de traitement de flux.

International audience; Les simulations numériques de grande taille nécessitent d'être effectuées en parallèle. L'équilibre de la charge entre les nœuds de calcul est alors primordial. Dans le cas de simulations multi-physiques, on modélise le problème d'équilibrage de charge par celui du partitionnement multi-critères de graphes, problème NP-Difficile pour lequel les outils existants reposent sur des heuristiques largement améliorables. Nous présentons ici une méthode de partitionnement multi-critères de graphe utilisant un schéma multi-niveaux adapté. Notamment, nous proposons un nouvel algorithme de partitionnement initial et nous démarquons de l'existant concernant la phase de raffinement, conçue pour respecter strictement les tolérances d'équilibre. En mono-critère, notre méthode est compétitive par rapport à des logiciels de référence comme Scotch et MeTiS. En multi-critères, contrairement à MeTiS, notre méthode retourne dans tous les cas des solutions valides par rapport aux tolérances prescrites.

International audience; Key grouping is a technique used by stream processing frame- works to simplify the development of parallel stateful opera- tors. Through key grouping a stream of tuples is partitioned in several disjoint sub-streams depending on the values con- tained in the tuples themselves. Each operator instance tar- get of one sub-stream is guaranteed to receive all the tuples containing a specific key value. A common solution to imple- ment key grouping is through hash functions that, however, are known to cause load imbalances on the target operator instances when the input data stream is characterized by a skewed value distribution. In this paper we present DKG, a novel approach to key grouping that provides near-optimal load distribution for input streams with skewed value distri- bution. DKG starts from the simple observation that with such inputs the load balance is strongly driven by the most frequent values; it identifies such values and explicitly maps them to sub-streams together with groups of less frequent items to achieve a near-optimal load balance. We provide theoretical approximation bounds for the quality of the map- ping derived by DKG and show, through both simulations and a running prototype, its impact on stream processing applications.; Le groupement de clés est une technique utilisée dans les plateformes de traitement de flux pour simplifier le dé-ploiement parallèle d'opérateurs à états. Cette méthode consiste à subdiviser le flux de tuples en plusieurs sous-flux disjoints, au regard d'une clef définie pour chaque tuple. Chaque opérateur recevant l'un de ces sous-flux est donc as-suré de recevoir tous les tuples contenant une clé spécifique. Une solution classique est de grouper les clés en utilisant des fonctions de hachage, induisant potentiellement un déséquilibre de charge des opérateurs en cas de distribution bi-aisée des clefs du flux d'entrée. Nous présentons une solution permettant d'obtenir une répartition de la charge proche de l'optimal, quelque soit la distribution. Cette solution repose sur le fait que l'équilibre est majoritairement influencé par les clés les plus fréquentes. En identifiant ces valeurs dominantes et en les groupant judicieusement avec des clés plus rares, les sous-flux ainsi obtenus permettent d'atteindre un équilibrage de charge quasi-optimal. Nous présentons une analyse théorique des bornes de qualité obtenu avec notre algorithme et illustrons son impact sur des applications de traitement de flux, via des simulations intensives et un prototype opérationnel.

The current parallel architectures integrate processors with many cores to shared memory growing and responding to specific usage constraints, particularly in the cache management. To take advantage of this power, a unique distributed memory parallelism, to manage the inter-node communications is not directly adapted to the characteristics of multi-core architectures. In addition, the shared memory computing environments offer techniques for balancing the load among available cores more appropriate than those in a distributed memory context.Thus, programming models like OpenMP and KAAPI is a tailored response to the specific characteristics of these architectures.Given these issues, we are interested in developing a hardware-aware approach taking into consideration the hierarchical organization of parallel architectures with shared memory. Our approach provides an optimization model for the use of storage space in this context of parallelism.To prove the pertinence of this approach, we have implemented it in the fast dynamic simulation software EUROPLEXUS of fluids and structures, focusing on the shared memory parallelism complementary to the distributed memory approach developed elsewhere. Because of its wide range of applications, EUROPLEXUS is characterized by a very rich data structure and very complex dependencies among its routines. We focused on accelerating the main loop iterating over the mesh elements. The heterogeneity of the formulations and the materials of the elements that can co-exist in the same simulated model generates a large variability between the costs of the iterations of this loop. A first parallelization of the loop with the XKAAPI library based on a dynamic workstealing scheduling has been implemented. However, despite the acceleration achieved by the parallel implementation, performance has been restrained by frequent and dispersed access costs to a complex data structure. This makes the implementation of the code difficult to optimize. Because of this structure, much of the execution time has elapsed in cache misses. The work is based on the implementation of a model approximating the data structure that ensures a better access locality. It mainly consists in moving from the global data structure in which the physical fields are stored in separate tables to a structure based on the storage of data in independent structures called groups. These groups contain the data relating to a number of elements in the local tables. This number is an adjustable parameter depending on the size of the cache levels. Specifically, this method returns to the nest of the elementary loop in a loop iterating on groups. The iterations among the groups are distributed over the cores of the architecture.The execution of the inner loop is sequentially by core. The best results are obtained for groups of the L2 cache size. For this particular size, the use of a dynamic load balancing in XKAAPI allowed us to double the acceleration of the elementary loop compared to the reference version of the code. The second part of this thesis is based on the parallelization of elementary loop inside the already parallelized loop. We demonstrated that this second level of parallelism is less efficient than the single. However, this nested parallelism might be interesting on Intel Xeon Phi architectures incorporating hyper-threaded cores at their calculation units., Les architectures parallèles actuelles intègrent des processeurs avec un nombre de cœurs à mémoire partagée de plus en plus important et répondant à des contraintes d'utilisation spécifiques, notamment en matière de gestion de la mémoire cache. Pour tirer parti de cette puissance, un parallélisme unique à mémoire distribuée, nécessaire pour gérer les communications inter-nœuds, présente le désavantage de ne pas s'adapter directement aux particularités des architectures multi-cœurs. De plus, les environnements de calcul à mémoire partagée proposent des techniques pour l'équilibrage de la charge entre les cœurs disponibles, qui se présentent de manière plus délicate dans un contexte de mémoire distribuée. Ainsi, des modèles de programmation tels qu’OpenMP et XKAAPI sont une réponse bien adaptée aux spécificités de ces architectures.Au regard de ces problématiques, nous nous sommes intéressés, à développer une approche Hardware-aware prenant en considération l'organisation hiérarchique des architectures parallèles à mémoire partagée. Notre approche offre un modèle d'optimisation de l'utilisation des espaces de stockage dans ce contexte de parallélisme. Pour démontrer la pertinence de cette approche, nous l'avons implémentée dans le logiciel de simulation en dynamique rapide des fluides et des structures EUROPLEXUS, en se concentrant sur le parallélisme à mémoire partagée, complémentaire d'une approche à mémoire distribuée développée par ailleurs. De par son large panel d'applications, EUR0PLEXUS est caractérisé par une structure de données très riche et des dépendances très complexes entre ses routines. Nous nous sommes concentrés sur l'accélération de la boucle principale itérant sur les éléments du maillage. L'hétérogénéité des formulations et des matériaux des éléments pouvant co-exister dans un même modèle simulé engendre une grande variabilité entre les coûts des itérations de cette boucle. Une première parallélisation de cette boucle avec la bibliothèque XKAAPI basée sur un ordonnancement dynamique par vol de tâches a été implémentée. Cependant, malgré l'accélération atteinte par cette implémentation parallèle, les performances ont été freinées par les coûts des accès fréquents et dispersés à une structure de données complexe rendant l'exécution du code délicate à optimiser. A cause de cette structuration, une grande partie du temps d'exécution est écoulée dans des défauts de cache.Ces travaux reposent sur l’implémentation d'un modèle de structure de données assurant une meilleure localité des accès. Il consiste majoritairement à passer de la structure de données globale dans laquelle les champs physiques sont stockés dans des tableaux séparés à une structure basée sur le stockage des données dans des structures indépendantes appelées groupes. Ces groupes contiennent les données relatives à un certain nombre d'éléments dans des tableaux locaux. Ce nombre est un paramètre réglable selon la taille des niveaux du cache. Concrètement, cette méthode revient à imbriquer la boucle élémentaire dans une boucle itérant sur les groupes. Les itérations sur les groupes sont distribuées sur les cœurs de l'architecture. L'exécution de la boucle interne est séquentielle par cœur. Les meilleurs résultats sont obtenus pour des groupes de la taille du cache L2 privé par cœur. Pour cette taille particulière, l'utilisation d'un équilibrage dynamique de charge sous XKAAPI nous a permis de doubler l'accélération de la boucle élémentaire par rapport à une parallélisation avec XKAAPI de la version de référence du code.La deuxième partie de cette thèse repose sur la parallélisation de la boucle élémentaire à l'intérieur de la boucle déjà parallélisée. Nous avons démontré que ce second niveau de parallélisme est moins performant que celui à un seul niveau. Cependant, ce parallélisme imbriqué pourrait être intéressant sur les architectures Xeon Phi de Intel intégrant des cœurs hyper-threadés au niveau de leurs unités de calcul.

Les simulations numériques de grande taille nécessitent d'être effectuées en parallèle. L'équilibre de la charge entre les nœuds de calcul est alors primordial. Dans le cas de simulations multi-physiques, on modélise le problème d'équilibrage de charge par celui du partitionnement multi-critères de graphes, problème NP-Difficile pour lequel les outils existants reposent sur des heuristiques largement améliorables. Nous présentons ici une méthode de partitionnement multi-critères de graphe utilisant un schéma multi-niveaux adapté. Notamment, nous proposons un nouvel algorithme de partitionnement initial et nous démarquons de l'existant concernant la phase de raffinement, conçue pour respecter strictement les tolérances d'équilibre. En mono-critère, notre méthode est compétitive par rapport à des logiciels de référence comme Scotch et MeTiS. En multi-critères, contrairement à MeTiS, notre méthode retourne dans tous les cas des solutions valides par rapport aux tolérances prescrites.

Heterogeneous architectures have been widely used in the domain of high performance computing. However developing applications on heterogeneous architectures is time consuming and error-prone because going from a single accelerator to multiple ones indeed requires to deal with potentially non-uniform domain decomposition, inter-accelerator data movements, and dynamic load balancing. The aim of this thesis is to propose a solution of parallel programming for novice developers, to ease the complex coding process and guarantee the quality of code. We lighted and analysed the shortcomings of existing solutions and proposed a new programming tool called STEPOCL along with a new domain specific language designed to simplify the development of an application for heterogeneous architectures. We evaluated both the performance and the usefulness of STEPOCL. The result show that: (i) the performance of an application written with STEPOCL scales linearly with the number of accelerators, (ii) the performance of an application written using STEPOCL competes with an handwritten version, (iii) larger workloads run on multiple devices that do not fit in the memory of a single device, (iv) thanks to STEPOCL, the number of lines of code required to write an application for multiple accelerators is roughly divided by ten.; Architectures hétérogènes sont largement utilisées dans le domaine de calcul haute performance. Cependant, le développement d'applications sur des architectures hétérogènes est indéniablement fastidieuse et sujette à erreur pour un programmeur même expérimenté. Pour passer une application aux architectures multi-cœurs hétérogènes, les développeurs doivent décomposer les données de l'entrée, gérer les échanges de valeur intermédiaire au moment d’exécution et garantir l'équilibre de charge de système. L'objectif de cette thèse est de proposer une solution de programmation parallèle pour les programmeurs novices, qui permet de faciliter le processus de codage et garantir la qualité de code. Nous avons comparé et analysé les défauts de solutions existantes, puis nous proposons un nouvel outil de programmation STEPOCL avec un nouveau langage de domaine spécifique qui est conçu pour simplifier la programmation sur les architectures hétérogènes. Nous avons évalué la performance de STEPOCL sur trois cas d'application classiques : un stencil 2D, une multiplication de matrices et un problème à N corps. Le résultat montre que : (i) avec l'aide de STEPOCL, la performance d'application varie linéairement selon le nombre d'accélérateurs, (ii) la performance de code généré par STEPOCL est comparable à celle de la version manuscrite. (iii) les charges de travail, qui sont trop grandes pour la mémoire d'un seul accélérateur, peuvent être exécutées en utilisant plusieurs accélérateurs. (iv) grâce à STEPOCL, le nombre de lignes de code manuscrite est considérablement réduit.

Grids and clouds are types of currently widely known distributed computing systems or DCSs. DCSs are complex systems in the sense that their emergent global behavior results from decentralized interaction of its parts and is not guided directly from a central point. In our study, we present a complex system model that efficiently manages the ressources of a DCS. The entities of the DCS react to system instability and adjust their environmental condtions for optimizing system performance. The structure of the interaction networks that allow fast and reliable access to available resources is studied and improvements ar proposed., Les grilles et les clouds sont deux types aujourd'hui largement répandus de systèmes informatiques distribués (en anglais DCS). Ces DCS sont des systèmes complexes au sens où leur comportement global émergent résulte de l'interaction décentralisée de ses composants, et n'est pas guidée directement de manière centralisée. Dans notre étude, nous présentons un modèle de système complexe qui gère de manière la plus efficace possible les ressources d'un DCS. Les entités d'un DCS réagissent à l'instabilité du système et s'ajustent aux conditions environnementales pour optimiser la performance du système. La structure des réseaux d'interaction qui permettent un accès rapide et sécurisé aux ressources disponibles est étudiée, et des améliorations proposées.

Grids and clouds are types of currently widely known distributed computing systems or DCSs. DCSs are complex systems in the sense that their emergent global behavior results from decentralized interaction of its parts and is not guided directly from a central point. In our study, we present a complex system model that efficiently manages the ressources of a DCS. The entities of the DCS react to system instability and adjust their environmental condtions for optimizing system performance. The structure of the interaction networks that allow fast and reliable access to available resources is studied and improvements ar proposed.; Les grilles et les clouds sont deux types aujourd'hui largement répandus de systèmes informatiques distribués (en anglais DCS). Ces DCS sont des systèmes complexes au sens où leur comportement global émergent résulte de l'interaction décentralisée de ses composants, et n'est pas guidée directement de manière centralisée. Dans notre étude, nous présentons un modèle de système complexe qui gère de manière la plus efficace possible les ressources d'un DCS. Les entités d'un DCS réagissent à l'instabilité du système et s'ajustent aux conditions environnementales pour optimiser la performance du système. La structure des réseaux d'interaction qui permettent un accès rapide et sécurisé aux ressources disponibles est étudiée, et des améliorations proposées.

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.; 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.; 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.

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 constantly growing. Thus, how do we scale these applications? Parallelization and massively parallel supercomputers are the only ways to achieve this. Nevertheless, there is a price to pay considering the hardware topologies incessantly complex, both in terms of network and memory hierarchy. The issue of data locality becomes central: how to reduce the distance between a processing entity and data to which it needs to access? Application placement is one of the levers to address this problem. In this thesis, we present the TreeMatch algorithm and its application for static mapping, that is to say at the launchtime of the application, and the dynamic placement. For this second approach, we propose the awareness of data locality within a load balancing algorithm. The different approaches discussed are validated by experiments both on benchmarking codes and on real applications., La simulation numérique est un des piliers des Sciences et de l’industrie. La simulation météorologique, la cosmologie ou encore la modélisation du cœur humain sont autant de 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 massivement parallèles sont les seuls moyens d’y parvenir. Néanmoins, il y a un prix à payer compte tenu des topologies matérielles de plus en plus complexes, tant en terme de réseau que 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 doit accé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 applications dans le cadre du placement statique, c’est-à-dire au lancement de l’application, et du placement dynamique. Pour cette seconde approche, nous proposons la prise en compte de la localité des données dans le cadre d’un algorithme d’équilibrage de charge. Les différentes approches abordées sont validées par des expériences réalisées tant sur des codes d’é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 constantly growing. Thus, how do we scale these applications? Parallelization and massively parallel supercomputers are the only ways to achieve this. Nevertheless, there is a price to pay considering the hardware topologies incessantly complex, both in terms of network and memory hierarchy. The issue of data locality becomes central: how to reduce the distance between a processing entity and data to which it needs to access? Application placement is one of the levers to address this problem. In this thesis, we present the TreeMatch algorithm and its application for static mapping, that is to say at the launchtime of the application, and the dynamic placement. For this second approach, we propose the awareness of data locality within a load balancing algorithm. The different approaches discussed are validated by experiments both on benchmarking codes and on real applications.; La simulation numérique est un des piliers des Sciences et de l’industrie. La simulation météorologique, la cosmologie ou encore la modélisation du cœur humain sont autant de 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 massivement parallèles sont les seuls moyens d’y parvenir. Néanmoins, il y a un prix à payer compte tenu des topologies matérielles de plus en plus complexes, tant en terme de réseau que 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 doit accé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 applications dans le cadre du placement statique, c’est-à-dire au lancement de l’application, et du placement dynamique. Pour cette seconde approche, nous proposons la prise en compte de la localité des données dans le cadre d’un algorithme d’équilibrage de charge. Les différentes approches abordées sont validées par des expériences réalisées tant sur des codes d’évaluation de performances que sur des applications réelles.

In the first part, we take a binding restriction, called qualification, present in semiconductor manufacturing as a lever for increasing flexibility and optimizing capacity utilization. A qualification determines the processing authorization of a product on a machine (like an eligibility constraint). In order to define the best qualification, the production volume should be allocated to parallel non-identical machines which are partially reconfigurable. Capacitated flexibility measures are introduced to define the best qualification which increases machine capacity utilization at most. Batching is another industrial constraint encountered in semiconductor industry. It influences workload balancing and qualification management. Several workload balancing algorithms are proposed to find the optimal workload balance of a workcenter. Variability measures are also proposed to evaluate the workload variability of a workcenter. The second part deals with closed-loop production planning. Soitec uses Smart-Cut Technology to fabricate SOI wafers. Using this technology, one of the two raw materials used to fabricate SOI wafers can be reused several times to make other SOI wafers. However, before coming back to the SOI fabrication line, the used raw material (by-product) must be reworked in another production line. An original closed-loop production planning model adapted to the supply chain specificities of Soitec is proposed, and is validated using industrial data. Based on this industrial model, a single-item uncapacitated closed-loop lot-sizing model is defined, analyzed, and a dynamic programming algorithm is proposed for a simplified version of the problem., La thèse est composée de deux parties. La première partie traite de la gestion des qualifications dans l'industrie des semi-conducteurs. La contrainte de qualification définit l'éligibilité d'une machine à processer un produit. La gestion des qualifications nécessite de résoudre un problème d'allocation et d'équilibrage des charges sur des machines parallèles non-identiques et partiellement reconfigurables. Nous avons défini et introduit des indicateurs pour la gestion des qualifications en tenant compte de la capacité des équipements ainsi que la contrainte de regroupements de lots (batching). Plusieurs algorithmes d'équilibrage de charge sont proposés et validés pour le calcul de la charge optimale sur un parc d'équipements. Ce concept est industrialisé au sein de l'entreprise Soitec et fait partie du processus de prise de décision.La deuxième partie de la thèse porte sur la planification de production en boucle fermée. Le processus de fabrication des plaques SOI à Soitec s'appuie sur la Technologie Smart-Cut. En utilisant cette technologie, une des deux matières premières peut être réutilisée à plusieurs reprises pour la fabrication des produits finis. Le couplage de deux lignes de production crée un système manufacturier en boucle fermée. Nous avons proposé un modèle de dimensionnement de lots original pour la planification de production de ce système manufacturier, que nous avons validé avec des données industrielles. En se basant sur le problème industriel, un problème mono-produit et sans contrainte de capacité est défini, analysé et résolu pour une version simplifiée du problème.

In this thesis, we are interested in the task of diffusion in networks of dynamic wireless sensors RCSF. This is an essential and primordial task, since it is necessary for neighbor discovery, routing, information distribution throughout the network, node location and time synchronization.[...], Dans cette thèse, on s’intéresse à la tâche de diffusion dans les réseaux de capteurs sans fils dynamiques RCSF. C'est une tache essentielle et primordiale puisqu'elle est nécessaire pour réaliser la découverte de voisinage, le routage, la distribution d’informations dans tout le réseau, la localisation des nœuds et la synchronisation du temps.[...]

In the exascale race, supercomputer architectures are evolving towards massively multicore nodes with hierarchical memory structures and equipped with larger vectorization registers. These trends tend to make MPI-only applications less effective, and now require programmers to explicitly manage low-level elements to get decent performance.In the context of Molecular Dynamics (MD) applied to condensed matter physics, the need for a better understanding of materials behaviour under extreme conditions involves simulations of ever larger systems, on tens of thousands of cores. This will put molecular dynamics codes among software that are very likely to meet serious difficulties when it comes to fully exploit the performance of next generation processors.This thesis proposes the design and implementation of a high-performance, flexible and scalable framework dedicated to the simulation of large scale MD systems on future supercomputers. We managed to separate numerical modules from different expressions of parallelism, allowing developers not to care about optimizations and still obtain high levels of performance. Our architecture is organized in three levels of parallelism: domain decomposition using MPI, thread parallelization within each domain, and explicit vectorization. We also included a dynamic load balancing capability in order to equally share the workload among domains.Results on simple tests show excellent sequential performance and a quasi linear speedup on several thousands of cores on various architectures. When applied to production simulations, we report an acceleration up to a factor 30 compared to the code previously used by CEA’s researchers., Dans la course vers l’exascale, les architectures des supercalculateurs évoluent vers des nœuds massivement multicœurs, sur lesquels les accès mémoire sont non-uniformes et les registres de vectorisation toujours plus grands. Ces évolutions entraînent une baisse de l’efficacité des applications homogènes (MPI simple), et imposent aux développeurs l’utilisation de fonctionnalités de bas-niveau afin d’obtenir de bonnes performances.Dans le contexte de la dynamique moléculaire (DM) appliqué à la physique de la matière condensée, les études du comportement des matériaux dans des conditions extrêmes requièrent la simulation de systèmes toujours plus grands avec une physique de plus en plus complexe. L’adaptation des codes de DM aux architectures exaflopiques est donc un enjeu essentiel.Cette thèse propose la conception et l’implémentation d’une plateforme dédiée à la simulation de très grands systèmes de DM sur les futurs supercalculateurs. Notre architecture s’organise autour de trois niveaux de parallélisme: décomposition de domaine avec MPI, du multithreading massif sur chaque domaine et un système de vectorisation explicite. Nous avons également inclus une capacité d’équilibrage dynamique de charge de calcul. La conception orienté objet a été particulièrement étudiée afin de préserver un niveau de programmation utilisable par des physiciens sans altérer les performances.Les premiers résultats montrent d’excellentes performances séquentielles, ainsi qu’une accélération quasi-linéaire sur plusieurs dizaines de milliers de cœurs. En production, nous constatons une accélération jusqu’à un facteur 30 par rapport au code utilisé actuellement par les chercheurs du CEA.

The mobile network of Orange in France comprises more than 100 000 2G, 3G and 4G antennas with severalfrequency bands, not to mention many femto-cells for deep-indoor coverage. These numbers will continue toincrease in order to address the customers’ exponentially increasing need for mobile data. This is an illustrationof the challenge faced by the mobile operators for operating such a complex network with low OperationalExpenditures (OPEX) in order to stay competitive. This thesis is about leveraging the Self-Organizing Network(SON) concept to reduce this complexity by automating repetitive or complex tasks. We specifically proposeautomatic optimization algorithms for scenarios related to network densification using either small cells orActive Antenna Systems (AASs) used for Vertical Sectorization (VeSn), Virtual Sectorization (ViSn) and multilevelbeamforming. Problems such as load balancing with limited-capacity backhaul and interference coordination eitherin time-domain (eICIC) or in frequency-domain are tackled. We also propose optimal activation algorithms forVeSn and ViSn when their activation is not always beneficial. We make use of results from stochastic approximationand convex optimization for the mathematical formulation of the problems and their solutions. We also proposea generic methodology for the coordination of multiple SON algorithms running in parallel using results fromconcave game theory and Linear Matrix Inequality (LMI)-constrained optimization., Le réseau mobile d’Orange France comprend plus de 100 000 antennes 2G, 3G et 4G sur plusieurs bandes de fréquences sans compter les nombreuses femto-cells fournies aux clients pour résoudre les problèmes de couverture. Ces chiffres ne feront que s’accroître pour répondre à la demande sans cesse croissante des clients pour les données mobiles. Cela illustre le défi énorme que rencontrent les opérateurs de téléphonie mobile en général à savoir gérer un réseau aussi complexe tout en limitant les coûts d’opération pour rester compétitifs. Cette thèse s’attache à utiliser le concept SON (réseaux auto-organisants) pour réduire cette complexité en automatisant les tâches répétitives ou complexes. Plus spécifiquement, nous proposons des algorithmes d’optimisation automatique pour des scénarios liés à la densification par les small cells ou les antennes actives. Nous abordons les problèmes classiques d’équilibrage de charge mais avec un lien backhaul à capacité limitée et de coordination d’interférence que ce soit dans le domaine temporel (notamment avec le eICIC) ou le domaine fréquentiel. Nous proposons aussi des algorithmes d’activation optimale de certaines fonctionnalités lorsque cette activation n’est pas toujours bénéfique. Pour la formulation mathématique et la résolution de tous ces algorithmes, nous nous appuyons sur les résultats de l’approximation stochastique et de l’optimisation convexe. Nous proposons aussi une méthodologie systématique pour la coordination de multiples fonctionnalités SON qui seraient exécutées en parallèle. Cette méthodologie est basée sur les jeux concaves et l’optimisation convexe avec comme contraintes des inégalités matricielles linéaires.

The mobile network of Orange in France comprises more than 100 000 2G, 3G and 4G antennas with severalfrequency bands, not to mention many femto-cells for deep-indoor coverage. These numbers will continue toincrease in order to address the customers’ exponentially increasing need for mobile data. This is an illustrationof the challenge faced by the mobile operators for operating such a complex network with low OperationalExpenditures (OPEX) in order to stay competitive. This thesis is about leveraging the Self-Organizing Network(SON) concept to reduce this complexity by automating repetitive or complex tasks. We specifically proposeautomatic optimization algorithms for scenarios related to network densification using either small cells orActive Antenna Systems (AASs) used for Vertical Sectorization (VeSn), Virtual Sectorization (ViSn) and multilevelbeamforming. Problems such as load balancing with limited-capacity backhaul and interference coordination eitherin time-domain (eICIC) or in frequency-domain are tackled. We also propose optimal activation algorithms forVeSn and ViSn when their activation is not always beneficial. We make use of results from stochastic approximationand convex optimization for the mathematical formulation of the problems and their solutions. We also proposea generic methodology for the coordination of multiple SON algorithms running in parallel using results fromconcave game theory and Linear Matrix Inequality (LMI)-constrained optimization., Le réseau mobile d’Orange France comprend plus de 100 000 antennes 2G, 3G et 4G sur plusieurs bandes de fréquences sans compter les nombreuses femto-cells fournies aux clients pour résoudre les problèmes de couverture. Ces chiffres ne feront que s’accroître pour répondre à la demande sans cesse croissante des clients pour les données mobiles. Cela illustre le défi énorme que rencontrent les opérateurs de téléphonie mobile en général à savoir gérer un réseau aussi complexe tout en limitant les coûts d’opération pour rester compétitifs. Cette thèse s’attache à utiliser le concept SON (réseaux auto-organisants) pour réduire cette complexité en automatisant les tâches répétitives ou complexes. Plus spécifiquement, nous proposons des algorithmes d’optimisation automatique pour des scénarios liés à la densification par les small cells ou les antennes actives. Nous abordons les problèmes classiques d’équilibrage de charge mais avec un lien backhaul à capacité limitée et de coordination d’interférence que ce soit dans le domaine temporel (notamment avec le eICIC) ou le domaine fréquentiel. Nous proposons aussi des algorithmes d’activation optimale de certaines fonctionnalités lorsque cette activation n’est pas toujours bénéfique. Pour la formulation mathématique et la résolution de tous ces algorithmes, nous nous appuyons sur les résultats de l’approximation stochastique et de l’optimisation convexe. Nous proposons aussi une méthodologie systématique pour la coordination de multiples fonctionnalités SON qui seraient exécutées en parallèle. Cette méthodologie est basée sur les jeux concaves et l’optimisation convexe avec comme contraintes des inégalités matricielles linéaires.

The amount of smartphone sales recently surpassed the desktop computer ones. This is mainly due to the smart integration of many functionalities in the same architecture. This is also due to the wide variety of supported applications like augmented reality, video conferencing and video games. The support of these applications is made by heterogeneous computing resources specialized to support each application type thus allowing to meet required performance and power consumption. For example, multimedia applications are accelerated by hardware modules that help video encoding and decoding and video game 3D rendering is accelerated by specialized processors (GPU). However, applications become more and more complicated. As an example, augmented reality requires image processing, 3D rendering and computing the information to display. This complexity often comes with a variation of the computing load, which dynamically changes application performance requirements. When this application is implemented in parallel, the way parallelism is chosen for a specific workload, becomes inefficient for a different one. This leads to a waste in computing resources and our objective is to optimize the usage of all available computing resources at runtime. The selected use case is a graphic rendering pipeline application because it is a dynamic application, which is also widely used in mobile devices. This application has been implemented and parallelized on a multicore architecture simulator. The profiling shows that the dynamicity of the application, the time and the amount of data needed to compute vary. The profiling also shows that the best balance of the parallelism depends on the rendered scene; a dynamic load balancing is therefore required for this application. These studies brought us about defining a system allowing to dynamically adapt the application parallelism depending on a prediction of its computing requirements, which can be performed by monitoring the data exchanges between the application tasks. Then the new parallelism is calculated for each stage by a central controller that manages the whole application. This system has been implemented in a Timed-TLM simulator in order to estimate performance improvements allowed by the dynamic adaptation. An architecture allowing to accelerate mobile applications, such as general-purpose and 3D applications, has been defined and compared to other multicore architectures. The hardware complexity and the performance of the architecture have also been estimated. For an increased complexity lower that 1,5%, we demonstrate performance improvements up to 20% compared with static parallelisms. We also demonstrated the ability to support a variable amount of resources.; Le nombre de smartphones vendus a récemment dépassé celui des ordinateurs. Ces appareils tendent à regrouper de plus en plus de fonctions, ceci grâce à des applications de plus en plus variées telles que la vidéo conférence, la réalité augmentée, ou encore les jeux vidéo. Le support de ces applications est assuré par des ressources de calculs hétérogènes qui sont spécifiques aux différents types de traitements et qui respectent les performances requises et les contraintes de consommation du système. Les applications graphiques, telles que les jeux vidéo, sont par exemple accélérées par un processeur graphique. Cependant les applications deviennent de plus en plus complexes. Une application de réalité augmentée va par exemple nécessiter du traitement d'image, du rendu graphique et un traitement des informations à afficher. Cette complexité induit souvent une variation de la charge de travail qui impacte les performances et donc les besoins en puissance de calcul de l'application. Ainsi, la parallélisation de l'application, généralement prévue pour une certaine charge, devient inappropriée. Ceci induit un gaspillage des ressources de calcul qui pourraient être exploitées par d'autres applications ou par d'autres étages de l'application. Un pipeline de rendu graphique a été choisi comme cas d'utilisation car c'est une application dynamique et qui est de plus en plus répandu dans les appareils mobiles. Cette application a été implémentée et parallélisée sur un simulateur d'architecture multi-cœurs. Un profilage a confirmé l'aspect dynamique, le temps de calcul de chaque donnée ainsi que le nombre d'objets à calculer variant de manière significative dans le temps et que la meilleure répartition du parallélisme évolue en fonction de la scène rendue. Ceci nous a amenés à définir un système permettant d'adapter, au fil de l'exécution, le parallélisme d'une application en fonction d'une prédiction faite de ses besoins. Le choix d'un nouveau parallélisme nécessite de connaître les besoins en puissance de calcul des différents étages, en surveillant les transferts de données entre les étages de l'application. Enfin, l'adaptation du parallélisme implique une nouvelle répartition des tâches en fonction des besoins des différents étages qui est effectuée grâce à un contrôleur central. Le système a été implémenté dans un simulateur précis au niveau TTLM afin d'estimer les gains de performances permis par l'adaptation dynamique. Une architecture permettant l'accélération de différents types d'applications que ce soit généralistes ou graphiques a été définie et comparée à d'autres architectures multi-cœurs. Le coût matériel de cette architecture a de plus été quantifié. Ainsi, pour un support matériel dont la complexité est inférieure à 1,5 % du design complet, on démontre des gains de performance allant jusqu'à 20 % par rapport à certains déploiements statiques, ainsi que la capacité à gérer dynamiquement un nombre de ressources de calcul variable.

Due to the inherent genericity of graph-based representations, and thanks to the improvement of computer capacities, structural representations have become more and more popular in the field of Pattern Recognition (PR). In a graph-based representation, vertices and their attributes describe objects (or part of them) while edges represent interrelationships between the objects. Representing objects by graphs turns the problem of object comparison into graph matching (GM) where correspondences between vertices and edges of two graphs have to be found., En raison de la capacité et de l'amélioration des performances informatiques, les représentations structurelles sont devenues de plus en plus populaires dans le domaine de la reconnaissance de formes (RF). Quand les objets sont structurés à base de graphes, le problme de la comparaison d'objets revient à un problme d'appariement de graphes (Graph Matching). Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition entre graphes (GED), notamment pour sa capacité à traiter différent types de graphes. GED a été ainsi appliquée sur des problématiques spécifiques qui varient de la reconnaissance de molécules à la classi fication d'images.

Computer science is deeply changing methodological aspects of the discovery process in different areas of knowledge. Researchers have at their disposal new capabilities that can create novel research opportunities. Parallel and distributed platforms composed of resources shared between different participants can make these new capabilities accessible to every researcher at every level, delivering computational power that was restricted before to bigger (and wealthy) scientific projects. This work explores four different facets of the rules that govern how organizations engage in collaboration on modern parallel and distributed platforms. Using classical combinatorial tools, multi-objective scheduling and game-theory, we showed how to compute schedules with good trade-offs between the results got by the participants and the global performance of the platform. By ensuring fair results and guaranteeing performance improvements for the participants, we can create an efficient platform where everyone always feels encouraged to collaborate and to share its resources. First, we study the collaboration between selfish organizations. We show how the selfish behavior between the participants imposes a lower bound on the global makespan. We present algorithms that cope with the selfishness of the organizations and that achieve good fairness in practice. The second study is about collaboration between organizations that can tolerate a limited degradation on their performance if this can help ameliorate the global makespan. We improve the existing inapproximation bounds for this problem and present new algorithms whose guarantees are close to the Pareto set. The third form of collaboration studied is between rational participants that can independently choose the best strategy for their jobs. We present a non-cooperative game-theoretic model for the problem and show how coordination mechanisms allow the creation of approximate pure equilibria with bounded price of anarchy. Finally, we study collaboration between users sharing a set of common resources. We present a method that enumerates the frontier of best compromise solutions for the users and selects the solution that brings the best value for the global performance function.; L'informatique a changé profondément les aspects méthodologiques du processus de découverte dans les différents domaines du savoir. Les chercheurs ont à leur disposition aujourd'hui de nouvelles capacités qui permettent d'envisager la résolution de nouveaux problèmes. Les plates-formes parallèles et distribués composées de ressources partagés entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offre une puissance de calcul qui a été limitée jusqu'à présent, aux projets scientifiques les plus grands (et les plus riches). Dans ce document qui regroupe les résultats obtenus pendant mon doctorat, nous explorons quatre facettes différentes de la façon dont les organisations s'engagent dans une collaboration sur de plates-formes parallèles et distribuées. En utilisant des outils classiques de l'analyse combinatoire, de l'ordonnancement multi-objectif et de la théorie des jeux, nous avons montré comment calculer des ordonnancements avec un bon compromis entre les résultats obtenu par les participants et la performance globale de la plate-forme. En assurant des résultats justes et en garantissant des améliorations de performance pour les différents participants, nous pouvons créer une plate-forme efficace où chacun se sent toujours encourager à collaborer et à partager ses ressources. Tout d'abord, nous étudions la collaboration entre organisations égoïstes. Nous montrons que le comportement égoïste entre les participants impose une borne inférieure sur le makespan global. Nous présentons des algorithmes qui font face à l'égoïsme des organisations et qui présentent des résultats équitables. La seconde étude porte sur la collaboration entre les organisations qui peuvent tolérer une dégradation limitée de leur performance si cela peut aider à améliorer le makespan global. Nous améliorons les bornes d'inapproximabilité connues sur ce problème et nous présentons de nouveaux algorithmes dont les garanties sont proches de l'ensemble de Pareto (qui regroupe les meilleures solutions possibles). La troisième forme de collaboration étudiée est celle entre des participants rationnels qui peuvent choisir la meilleure stratégie pour leur tâches. Nous présentons un modèle de jeu non coopératif pour le problème et nous montrons comment l'utilisation de "coordination mechanisms" permet la création d'équilibres approchés avec un prix de l'anarchie borné. Finalement, nous étudions la collaboration entre utilisateurs partageant un ensemble de ressources communes. Nous présentons une méthode qui énumère la frontière des solutions avec des meilleurs compromis pour les utilisateurs et sélectionne la solution qui apporte la meilleure performance globale.

Computer science is deeply changing methodological aspects of the discovery process in different areas of knowledge. Researchers have at their disposal new capabilities that can create novel research opportunities. Parallel and distributed platforms composed of resources shared between different participants can make these new capabilities accessible to every researcher at every level, delivering computational power that was restricted before to bigger (and wealthy) scientific projects. This work explores four different facets of the rules that govern how organizations engage in collaboration on modern parallel and distributed platforms. Using classical combinatorial tools, multi-objective scheduling and game-theory, we showed how to compute schedules with good trade-offs between the results got by the participants and the global performance of the platform. By ensuring fair results and guaranteeing performance improvements for the participants, we can create an efficient platform where everyone always feels encouraged to collaborate and to share its resources. First, we study the collaboration between selfish organizations. We show how the selfish behavior between the participants imposes a lower bound on the global makespan. We present algorithms that cope with the selfishness of the organizations and that achieve good fairness in practice. The second study is about collaboration between organizations that can tolerate a limited degradation on their performance if this can help ameliorate the global makespan. We improve the existing inapproximation bounds for this problem and present new algorithms whose guarantees are close to the Pareto set. The third form of collaboration studied is between rational participants that can independently choose the best strategy for their jobs. We present a non-cooperative game-theoretic model for the problem and show how coordination mechanisms allow the creation of approximate pure equilibria with bounded price of anarchy. Finally, we study collaboration between users sharing a set of common resources. We present a method that enumerates the frontier of best compromise solutions for the users and selects the solution that brings the best value for the global performance function.; L'informatique a changé profondément les aspects méthodologiques du processus de découverte dans les différents domaines du savoir. Les chercheurs ont à leur disposition aujourd'hui de nouvelles capacités qui permettent d'envisager la résolution de nouveaux problèmes. Les plates-formes parallèles et distribuées composées de ressources partagées entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offrent une puissance de calcul qui a été limitée jusqu'à présent aux projets scientifiques les plus grands (et les plus riches). Dans ce document qui regroupe les résultats obtenus pendant cette thèse, nous explorons quatre facettes différentes de la façon dont les organisations s'engagent dans une collaboration sur de plates-formes parallèles et distribuées. En utilisant des outils classiques de l'analyse combinatoire, de l'ordonnancement multi-objectif et de la théorie des jeux, nous avons montré comment calculer des ordonnancements avec un bon compromis entre les résultats obtenus par les participants et la performance globale de la plate-forme. En assurant des résultats justes et en garantissant des améliorations de performance pour les différents participants, nous pouvons créer une plate-forme efficace où chacun se sent toujours encouragé à collaborer et à partager ses ressources. Tout d'abord, nous étudions la collaboration entre organisations égoïstes. Nous montrons que le comportement égoïste entre les participants impose une borne inférieure sur le makespan global. Nous présentons des algorithmes qui font face à l'égoïsme des organisations et qui présentent des résultats équitables. La seconde étude porte sur la collaboration entre les organisations qui peuvent tolérer une dégradation limitée de leur performance si cela peut aider à améliorer le makespan global. Nous améliorons les bornes d'inapproximabilité connues sur ce problème et nous présentons de nouveaux algorithmes dont les garanties sont proches de l'ensemble de Pareto (qui regroupe les meilleures solutions possibles). La troisième forme de collaboration étudiée est celle entre des participants rationnels qui peuvent choisir la meilleure stratégie pour leur tâches. Nous présentons un modèle de jeu non coopératif pour le problème et nous montrons comment l'utilisation de "coordination mechanisms" permet la création d'équilibres approchés avec un prix de l'anarchie borné. Finalement, nous étudions la collaboration entre utilisateurs partageant un ensemble de ressources communes. Nous présentons une méthode qui énumère la frontière des solutions avec des meilleurs compromis pour les utilisateurs et sélectionne la solution qui apporte la meilleure performance globale.

L’adresse IP est devenue une fonctionnalité clé dans l'architecture actuelle d'Internet. Cependant, la conception de base de la pile d'Internet Protocol est basée sur une architecture formée il y a des années, quand l'Internet était un réseau statique. Les adresses IP fixes n'ont posé aucun problème jusqu'à ce que les appareils de communication sont devenus mobiles. Quand un noeud mobile (MN) communique avec un autre noeud via une association active, il peut avoir accès à plusieurs point d'attachement de différentes technologies, son adresse IP actuel change et par conséquent sa session active se termine. Différentes techniques sont mises en application pour soutenir la mobilité utilisant la pile d'Internet Protocol. L'IP mobile soutient la mobilité à la couche réseau, le SCTP soutient la mobilité à la couche transport. Quelle couche convient à la mobilité est toujours une question ouverte. Le protocole SCTP présente une caractéristique multihoming avec la reconfiguration dynamique d'adresse (DAR), pour fournir une solution plus sécurisée avec des pertes presque négligeables de paquet. Et d’un autre côté, il permet d’activer plusieurs sessions pour n’utiliser qu’une seule. Dans ce projet, après avoir présenté les caractéristiques du protocole SCTP, nous avons proposé une approche d’équilibrage de charge dont le but est de réduire les délais de transmission et d’optimiser l’utilisation des ressources disponibles (Débit) en exploitant les différentes sessions ouvertes en même temps. Nous avons ensuite présenté les étapes de modélisation et l’environnement de simulation. Enfin, nous avons évalué les performances du protocole SCTP vis à vis de l’équilibrage de charge.

Wireless multi-hop networks consist of a collection of mobile and/or fixed nodes which dynamically exchange data with (or without) reliance on a (any) centralized administration. They are by definition self-organized. The frequent topological changes make multi-hop routing a crucial issue for these networks. To overcome these problems, new forms of routing schemes are used as the multipath routing (MP). MP routing uses multiple paths to send data and can be regarded as an effective solution for these networks. The purpose of this PhD thesis is to study the MP routing techniques in a wirelessmulti-hop context for better performance. We choose for our study a MP extension of OLSR, called MP-OLSR. We evaluate its performance under various scenarios in NS-2. These tests have led us to highlight two problems in MP-OLSR : the long recovery delays when facing network failure situations and the allocation strategy of data on multiple paths. We define and seek to evaluate the latency introduced by both protocols OLSR and MP-OLSR to find a new path after a link failure. We propose three new different recovery schemes and accordingly extend these original protocols in order to decrease theexpected latency and reduce the packet loss rate of transmitted flow. We also propose a mechanism which is able to detect the deterioration of the link quality during the transfer of data traffic. The information derived from this mechanism is used to adjust the proportion of traffic to be assigned to each path according to network conditions. This new version of MP-OLSR protocol is evaluated by simulation., Un réseau sans fil multi-saut est un ensemble d’entités mobiles et/ou fixes formant un réseau dynamique temporaire avec ou sans l’aide de toute administration centralisée. Cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Afin de palier ces problèmes, de nouvelles formes de routage sont utilisées comme le routage multi-chemin (MC). Le routage MC permet d’envoyer les données sur des chemins multiples et semble être une solution efficace pour ces réseaux. Le but de cette thèse est d’étudier les techniques de routage MC dans un contexte sans fil multi-saut en vue d’obtenir de meilleures performances. Nous avons choisi pour notre étude une extension MC du protocole OLSR, appelée MP-OLSR. Nous évaluons ses performances sous divers scénarios sous NS-2. Ces tests d’évaluation nous ont amenés à mettre en ´evidence deux problèmes dans MP-OLSR : la réactivité du protocole de routage MC suite à des ruptures de route et la stratégie de répartition des données sur les chemins multiples. Nous avons étudié la réactivité de tels mécanismes dans MP-OLSR. Nous avons proposé trois nouvelles techniques de réparation de pannes qui diminuent les temps de rétablissement d’une route et réduisent le taux de perte des flux transmis. Nous proposons aussi un mécanisme qui détecte la dégradation de la qualité des liens durant le transfert d’un trafic de données. Les informations déduites de ce mécanisme servent à adapter la proportion de trafic à affecter à chaque chemin selon les conditions réseaux. Cette nouvelle variante du protocole MP-OLSR est évaluée par simulation.

The race towards more processing power between all different hardware manufacturers has in recent years faced deep changes. We see nowadays a huge development in the use of parallel machines with more and more cores and increasingly complex architectures. It seems now clear that we will witness in a near future the development of cheap Network On Chip computers. Executing parallel applications on such machines raises several problems. Amongst them we take in this work interest in the problem of scheduling a set of tasks on a set of computing resources. Between all existing methods we can generally distinguish on-line or off-line algorithms. On-line algorithms like work-stealing present the advantage to work without informations on hardware or tasks durations but do not generally achieve an efficient control of communications. In this book we take interest in on-line tasks scheduling on complex platforms where networking can impact (through congestion) performance. More precisely, we propose several new scheduling algorithms based on work-stealing targeting two different configurations. In a first study, we consider applications whose dependency graph is known in advance. By taking advantage of this information we manage to limit the amount of data transfered and thus to achieve high performance and even outperform the best known off-line algorithms. Concurrently to that, we also study possible optimisations in the case where knowledge of platform topology is available. We show again that it is possible to use this information to enhance performance. Our work allows therefore to extend the application field of scheduling algorithms towards more complex architectures and we hope will allow a better use of tomorrow's machine.; La course à l'augmentation de la puissance de calcul qui se déroule depuis de nombreuses années entre les différents producteurs de matériel a depuis quelques années changé de visage: nous assistons en effet désormais à une véritable démocratisation des machines parallèles avec une complexification sans cesse croissante de la structure des processeurs. À terme, il est tout à fait envisageable de voir apparaître pour le grand public des architecture pleinement hétérogènes composées d'un ensemble de cœurs reliés par un réseau sur puce. La parallélisation et l'exécution parallèle d'applications sur les machines à venir soulèvent ainsi de nombreux problèmes. Parmi ceux-ci, nous nous intéressons ici au problème de l'ordonnancement d'un ensemble de tâches sur un ensemble de cœurs, c'est à dire le choix de l'affectation du travail à réaliser sur les ressources disponibles. Parmi les méthodes existantes, on distingue deux types d'algorithmes: en-ligne et hors-ligne. Les algorithmes en-ligne comme le vol de travail présentent l'avantage de fonctionner en l'absence d'informations sur le matériel ou la durée des tâches mais ne permettent généralement pas une gestion efficace des communications. Dans cette thèse, nous nous intéressons à l'ordonnancement de tâches en-ligne sur des plates-formes complexes pour lesquelles le réseau peut, par des problèmes de congestion, limiter les performances. Plus précisément, nous proposons de nouveaux algorithmes d'ordonnancement en-ligne, basés sur le vol de travail, ciblant deux configurations différentes. D'une part, nous considérons des applications pour lesquelles le graphe de dépendance est connu à priori. L'utilisation de cette information nous permet ainsi de limiter les quantités de données transférées et d'obtenir des performances supérieures aux meilleurs algorithmes hors-ligne connus. D'autre part, nous étudions les optimisations possibles lorsque l'algorithme d'ordonnancement connaît la topologie de la plate-forme. Encore une fois, nous montrons qu'il est possible de tirer parti de cette information pour réaliser un gain non-négligeable en performance. Nos travaux permettent ainsi d'étendre le champ d'application des algorithmes d'ordonnancement vers des architectures plus complexes et permettront peut-être une meilleure utilisation des machines de demain.

International audience; Le calcul distribué : un outil pour l'imagerie médicale

Most of the existing load balancing strategies were interested in distributed systems which were supposed to have homogeneous resources interconnected with homogeneous and fast networks. For Grid computing, these assumptions are not realistic because of heterogeneity, scalability and dynamicity characteristics. For these environments the load balancing problem is then a new challenge presently for which many research projects are under way. In this perspective, our contributions through this paper are two folds. First, we propose a distributed load balancing model which can represent any Grid topology into a forest structure. After that, we develop on this model, a load balancing strategy at two levels; its principal objectives : the reduction of average response time of tasks and their transferring cost. The proposed strategy is naturally distributed with a local decision, which allows the possibility of avoiding use of wide area communication network., La plupart des stratégies d’équilibrage de charge existantes se sont intéressées à des systèmes distribués supposés avoir des ressources homogènes interconnectées à l’aide de réseaux homogènes et à hauts débits. Pour les grilles de calcul, ces hypothèses ne sont pas réalistes à cause des caractéristiques d’hétérogénéité, de passage à l’échelle et de dynamicité. Pour ces environnements, le problème d’équilibrage de charge constitue donc, un nouveau défi pour lequel plusieurs recherches sont actuellement investies.Notre contribution dans cette perspective à travers ce papier est double: premièrement, nous proposons un modèle distribué d’équilibrage de charge, permettant de représenter n’importe quelle topologie de grille en une structure de forêt. Nous développons ensuite sur ce modèle, une stratégie d’équilibrage à deux niveaux ayant comme principaux objectifs la réduction du temps de réponse moyen et le coût de transfert de tâches. La stratégie proposée est de nature distribuée avec une prise de décision locale, ce qui permettra d’éviter le recours au réseau de communication à large échelle.

The treatment of sparse numerical problems on large scale systems is often reduced to that of their kernels. For reasons of efficiency in time and space, specific compressing formats are used for storing the matrices of these problems. Most of sparse scientific computations are led to linear algebra problems. Here two fundamental problems are often considered: linear systems resolution and eigenvalue computation. In this thesis, we address the study of distribution of computations performed in iterative methods to solve such problems. The sparse matrix-vector product (SMVP) constitutes a basic kernel in such iterative methods. Thus, our problem reduces to the study of SMVP distribution on large scale distributed systems. Three phases are required for achieving our objectives (i)- pre-processing, (ii)- processing and (iii)- postprocessing. In phase 1, we first process the optimization of four versions of the SMVP algorithm corresponding to four specific matrix compressing formats; we study then their performances on sequential target machines. In addition, we focus on the study of load balancing in the procedure of data distribution (i.e. the sparse matrix rows) on a large scale distributed system. Concerning the processing phase, it consists in validating our study by a series of experimentations achieved on a volunteer distributed system that we installed through using XtremWeb-CH middleware. As to the post-processing phase, it consists in interpreting the experimental results previously obtained in order to deduce adequate conclusions, 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.

Les progrès technologiques réalisés ces dernières années ont permis le développement de nouveaux types de capteurs dotés de moyens de communication sans fil, peu onéreux et pouvant être configurés pour former des réseaux autonomes. Les domaines d'application sont nombreux : domotique, santé, domaine militaire ou bien encore surveillance de phénomènes environnementaux. Les limites imposées sont la limitation des capacités de traitement, de stockage et surtout d'énergie. La liberté laissée à l'implantation est forte et impose de concevoir complètement l'infrastructure, les mécanismes et les protocoles en fonction de l'application visée. Dans cette thèse, nous nous sommes tout d'abord focalisés sur des réseaux de petites tailles. Nous avons conçu une solution protocolaire "Placide" pour le suivi de la chaîne du froid proposée dans le cadre du projet ANR-CAPTEURS. L'originalité première de la solution repose sur l'absence d'infrastructure et de Station de Base. Elle est composée de protocoles performants fondés sur la formation d'un anneau virtuel entre les noeuds, auto-organisants et très économes en énergie. Le second axe est dédié à une étude expérimentale de la qualité du lien.L'objectif est double. Nous souhaitions tout d'abord étayer certaines hypothèses effectuées dans la première partie du travail. Il s'agissait ensuite de proposer des protocoles et des algorithmes fondés sur la qualité du lien. Nous nous sommes focalisés sur la variation de la qualité du lien en fonction de la distance entre les noeuds et de la puissance de transmission. Par la suite, l'impact de la qualité du lien sur la topologie du réseau a été étudiée. Les retours d'expérience sont importants quant à la compréhension des facteurs affectant la durée de vie du réseau. La dernière contribution concerne l'exploitation de ces observations en proposant des stratégies de partage decharge. Notre idée est que des protocoles très réduits et des mécanismes simples peuvent être mis en oeuvre pour le routage. Nous illustrons ces principes au travers d'exemples pour lesquels nous montrons la supériorité de ces solutions par rapport à des routages de type plus court chemin.

Le document présente une synthèse de travaux sur le déploiement, l'utilisation et les techniques de mise en oeuvre d'applications développées selon un modèle de programmation à passage de messages sur des grilles de calcul. La première partie décrit les performances observées sur la période 2002-2006 sur une plateforme à l'échelle de la France, ainsi que les gains obtenus par équilibrage de charge. La deuxième partie décrit un intergiciel nouveau baptisé P2P-MPI qui synthétise un ensemble de propositions pour améliorer la prise en charge de tels programmes à passage de messages.

Numerical resolution of partial differential equations can be made reliable and efficient throught the use of adaptive numerical methods. We present here the work we have done for the design, the implementation and the validation of such a method within an industrial software platform with applications in thermohydraulics. From the geometric point of vue, this method can deal both with mesh refinement and mesh coarsening, while ensuring the quality of the mesh cells. Numerically, we use the mortar elements formalism in order to extend the Finite Volumes-Elements method implemented in the Trio-U platform and to deal with the non-conforming meshes arising from the adaptation procedure. Finally, we present an implementation of this method using concepts from domain decomposition methods for ensuring its efficiency while running in a parallel execution context.; Les méthodes numériques adaptatives constituent un outil de choix pour assurer la pertinence et l'efficacité de la résolution numérique d'équations aux dérivées partielles. Le travail présenté dans ce mémoire porte sur la conception, l'implémentation, et la validation d'une telle méthode au sein d'une plate-forme industrielle de simulation en thermohydraulique. Du point de vue géométrique, la méthode proposée permet de prendre en compte tant le raffinement du maillage que son déraffinement, tout en garantissant la qualité des éléments qui le compose. Du point de vue numérique, nous utilisons le formalisme des éléments joints pour étendre la méthode des Volumes-Éléments Finis proposée par la plate-forme Trio-U et traiter convenablement les maillages non-conformes générés par la procédure d'adaptation. Enfin, l'implémentation proposée repose sur les concepts des méthodes de décomposition de domaine, afin d'en garantir le bon comportement dans un contexte d'exécution parallèle.

Numerical resolution of partial differential equations can be made reliable and efficient throught the use of adaptive numerical methods. We present here the work we have done for the design, the implementation and the validation of such a method within an industrial software platform with applications in thermohydraulics. From the geometric point of vue, this method can deal both with mesh refinement and mesh coarsening, while ensuring the quality of the mesh cells. Numerically, we use the mortar elements formalism in order to extend the Finite Volumes-Elements method implemented in the Trio-U platform and to deal with the non-conforming meshes arising from the adaptation procedure. Finally, we present an implementation of this method using concepts from domain decomposition methods for ensuring its efficiency while running in a parallel execution context., Les méthodes numériques adaptatives constituent un outil de choix pour assurer la pertinence et l'efficacité de la résolution numérique d'équations aux dérivées partielles. Le travail présenté dans ce mémoire porte sur la conception, l'implémentation, et la validation d'une telle méthode au sein d'une plate-forme industrielle de simulation en thermohydraulique. Du point de vue géométrique, la méthode proposée permet de prendre en compte tant le raffinement du maillage que son déraffinement, tout en garantissant la qualité des éléments qui le compose. Du point de vue numérique, nous utilisons le formalisme des éléments joints pour étendre la méthode des Volumes-Éléments Finis proposée par la plate-forme Trio-U et traiter convenablement les maillages non-conformes générés par la procédure d'adaptation. Enfin, l'implémentation proposée repose sur les concepts des méthodes de décomposition de domaine, afin d'en garantir le bon comportement dans un contexte d'exécution parallèle.

In order to get a better performance in distributed systems, load balancing problem has been extensively studied in recent years. Most of existing works focus on traditional systems where resources are generally homogeneous, like clusters. For grid infrastructures, this assumption is not totally true because resources of a grid are highly heterogeneous. Hence, load balancing problem for grid computing is a new challenge for scientists. In this paper, we propose a tree-based representation model for grid computing, over which we develop a hierarchical load balancing strategy. The main characteristics of this strategy can be summarized as follows:(i) It uses a task-level load balancing; (ii) It privileges local tasks transfer to reduce communication costs; (iii) It is a distributed strategy with local decision making., Afin d’obtenir de meilleures performances dans les systèmes répartis, le problème d’équilibrage de charge a été intensivement étudié ces dernières années. La plupart des travaux existants se sont intéressés à des systèmes qui sont plus ou moins homogènes et trouvent quelques difficultés à s’adapter aux caractéristiques des nouvelles infrastructures telles que les grilles de calcul, qui présentent un degré d’hétérogénéité assez élevé. Pour cela, il faut soit adapter, soit définir de nouvelles stratégies d’équilibrage pour ces infrastructures. Dans cette perspective, nous proposons un modèle arborescent de représentation d’une grille de calcul, sur lequel nous développons une stratégie hiérarchique d’équilibrage de charge. Les caractéristiques principales de la stratégie proposée peuvent être résumées comme suit: (i) C’est une stratégie d’équilibrage au niveau des tâches; (ii) Elle favorise un transfert local de tâches dans le but de réduire les coûts de communication; (iii) C’est une stratégie distribuée avec prise de décision locale

This thesis aims to set the foundations for the development of load-balancing algorithms for theactive objects model defined by ProActive in the context of large-scale networks (Grids).ProActive is an open-source Java middleware which achieves seamless programming for concurrent,parallel, distributed, and mobile computing, implementing the active-object paradigm. InProActive, each active object has its own control thread and can independently decide in whichorder to serve incoming method calls. Incoming method calls are automatically stored in a queueof pending requests (called a service queue). To add efficiency to the active objects paradigm,ProActive provides a migration mechanism, having automatic location and transparency throughthe use of forwarders. The migration operation comes with a communication penalty: an activeobject must migrate with its complete state, consisting of its pending requests (method calls), futures,and passive (mandatory non-shared) objects. Therefore, ProActive applications are sensitiveto latency.When several active objects with identical functionality are deployed, a load-balancing algorithmcan be used to improve the performance of an application using that functionality. We callworkload the total work units required by an application to finish. To use some active object's functionality,an application puts a work unit into the service queue of that active object. The workloadcan be balanced across several active objects either by sending active objects from a highly loadedprocessor to a less loaded one, or by stealing active objects from a highly loaded processor by aless loaded one. The environment where the active objects run is usually composed of multipleclusters of resources, such as sets of machines interconnected by a high-speed local network.In this thesis, a load-balancing algorithm for active objects which belong to a parallel applicationwas developed and studied, setting the foundations for development of load-balancingalgorithms for the middleware ProActive. This first approach is called the Robin-Hood + NottinghamSheriff load-balancing algorithm. This algorithm was validated in the context of a large-scalenetwork (over 1,000 nodes) through simulations. Therefore, we presented our model of Gridsbased on observation and measurement of what we consider key characteristics for active-objectsload-balancing: processing capacity and inter-resource communication latency.Finally, we present coupling contracts for deployment of parallel applications, showing how touse them in the context of load balancing by now choosing between a local scheduler (for clusters)and ProActive's load balancer.; Esta tesis apunta a entregar las bases para el desarrollo de los algoritmos de balance de carga para el modelo de objetos activos definido por ProActive en el contexto de las redes a gran escala (grillas).ProActive es un middleware implementado en lenguaje Java, de código abierto, para la programacióon concurrente, paralela, distribuida, y móvil; basado en el modelo de objeto-activo. EnProActive, cada objeto activo tiene su propio hilo de control y puede decidir independientementeen qué orden servir los métodos invocados, las cuales se almacenan automáticamente en una colade peticiones pendientes. Para agregar eficacia al paradigma de objetos activos, ProActive proporcionaun mecanismo del migración, obteniendo localización automática y transparencia medianteel uso de forwarders. La migración viene con un costo de comunicación: un objeto activo debeemigrar con su estado completo, que consiste en sus peticiones pendientes (llamadas de método),objetos futuros, y sus objetos pasivos. Por lo tanto, las aplicaciones implementadas con ProActiveson sensibles a la latencia.Cuando varios objetos activos con funcionalidad idéntica se despliegan, un algoritmo de balancede carga se utiliza para mejorar el funcionamiento de la aplicación utilizando esa funcionalidad.La carga de trabajo puede ser equilibrada, ya sea enviando objetos activos de un procesadoraltamente cargado a uno menos cargado, o bien robando objetos activos a un procesador altamentecargado. El ambiente donde normalmente se ejecutan las aplicaciones implementadas usando elmodelo de objetos activos se compone generalmente de grupos múltiples de recursos, por ejemplo,un sistema de máquinas interconectadas por una red local de alta velocidad.Dado lo anterior, se ha estudiado y desarrollado un algoritmo de balance de carga para objetosactivos que pertenecen a una aplicación paralela, fijando las bases para el desarrollo de losalgoritmos de balance de carga para el middleware ProActive. Este primer acercamiento se llamaalgoritmo Robin-Hood + Nottingham Sheriff. Este algoritmo fue validado en el contexto de redesde alta escala (sobre 1.000 nodos) mediante simulaciones, utilizando nuestros modelo de grillas decomputadores, los cuales están basados en la observación y la medición de lo que consideramoslas características dominantes para el balance de objetos activos: capacidad de procesamiento ylatencia entre recursos.Finalmente, presentamos los contratos de acoplamiento para el despliegue de aplicaciones paralelas, así como su forma de utilización en el contexto de balance de carga. A modo de ejemplo,mostramos su uso en la elección del balanceador a utilizar (cluster local v/s nuestro algoritmo).

This thesis aims to set the foundations for the development of load-balancing algorithms for theactive objects model defined by ProActive in the context of large-scale networks (Grids).ProActive is an open-source Java middleware which achieves seamless programming for concurrent,parallel, distributed, and mobile computing, implementing the active-object paradigm. InProActive, each active object has its own control thread and can independently decide in whichorder to serve incoming method calls. Incoming method calls are automatically stored in a queueof pending requests (called a service queue). To add efficiency to the active objects paradigm,ProActive provides a migration mechanism, having automatic location and transparency throughthe use of forwarders. The migration operation comes with a communication penalty: an activeobject must migrate with its complete state, consisting of its pending requests (method calls), futures,and passive (mandatory non-shared) objects. Therefore, ProActive applications are sensitiveto latency.When several active objects with identical functionality are deployed, a load-balancing algorithmcan be used to improve the performance of an application using that functionality. We callworkload the total work units required by an application to finish. To use some active object's functionality,an application puts a work unit into the service queue of that active object. The workloadcan be balanced across several active objects either by sending active objects from a highly loadedprocessor to a less loaded one, or by stealing active objects from a highly loaded processor by aless loaded one. The environment where the active objects run is usually composed of multipleclusters of resources, such as sets of machines interconnected by a high-speed local network.In this thesis, a load-balancing algorithm for active objects which belong to a parallel applicationwas developed and studied, setting the foundations for development of load-balancingalgorithms for the middleware ProActive. This first approach is called the Robin-Hood + NottinghamSheriff load-balancing algorithm. This algorithm was validated in the context of a large-scalenetwork (over 1,000 nodes) through simulations. Therefore, we presented our model of Gridsbased on observation and measurement of what we consider key characteristics for active-objectsload-balancing: processing capacity and inter-resource communication latency.Finally, we present coupling contracts for deployment of parallel applications, showing how touse them in the context of load balancing by now choosing between a local scheduler (for clusters)and ProActive's load balancer.; Esta tesis apunta a entregar las bases para el desarrollo de los algoritmos de balance de carga para el modelo de objetos activos definido por ProActive en el contexto de las redes a gran escala (grillas).ProActive es un middleware implementado en lenguaje Java, de código abierto, para la programacióon concurrente, paralela, distribuida, y móvil; basado en el modelo de objeto-activo. EnProActive, cada objeto activo tiene su propio hilo de control y puede decidir independientementeen qué orden servir los métodos invocados, las cuales se almacenan automáticamente en una colade peticiones pendientes. Para agregar eficacia al paradigma de objetos activos, ProActive proporcionaun mecanismo del migración, obteniendo localización automática y transparencia medianteel uso de forwarders. La migración viene con un costo de comunicación: un objeto activo debeemigrar con su estado completo, que consiste en sus peticiones pendientes (llamadas de método),objetos futuros, y sus objetos pasivos. Por lo tanto, las aplicaciones implementadas con ProActiveson sensibles a la latencia.Cuando varios objetos activos con funcionalidad idéntica se despliegan, un algoritmo de balancede carga se utiliza para mejorar el funcionamiento de la aplicación utilizando esa funcionalidad.La carga de trabajo puede ser equilibrada, ya sea enviando objetos activos de un procesadoraltamente cargado a uno menos cargado, o bien robando objetos activos a un procesador altamentecargado. El ambiente donde normalmente se ejecutan las aplicaciones implementadas usando elmodelo de objetos activos se compone generalmente de grupos múltiples de recursos, por ejemplo,un sistema de máquinas interconectadas por una red local de alta velocidad.Dado lo anterior, se ha estudiado y desarrollado un algoritmo de balance de carga para objetosactivos que pertenecen a una aplicación paralela, fijando las bases para el desarrollo de losalgoritmos de balance de carga para el middleware ProActive. Este primer acercamiento se llamaalgoritmo Robin-Hood + Nottingham Sheriff. Este algoritmo fue validado en el contexto de redesde alta escala (sobre 1.000 nodos) mediante simulaciones, utilizando nuestros modelo de grillas decomputadores, los cuales están basados en la observación y la medición de lo que consideramoslas características dominantes para el balance de objetos activos: capacidad de procesamiento ylatencia entre recursos.Finalmente, presentamos los contratos de acoplamiento para el despliegue de aplicaciones paralelas, así como su forma de utilización en el contexto de balance de carga. A modo de ejemplo,mostramos su uso en la elección del balanceador a utilizar (cluster local v/s nuestro algoritmo).

The wireless networks are an even more emergent technology allowing the users access to informationand electronic services regardless of their locations. The success of this type of networks is due to agreat interest of the users, as well as the business and industrial world. Moreover, the rates currentlyreached with wireless networks make it possible to transfer multimedia flows subjected to importantconstraints. Thus, it has become paramount to respect certain constraints such as bandwidth, delayor packet loss. However, the solutions which were introduced into hard-wired networks have becomeunsuitable for networks using a shared radio medium without a centralized administration.In this respect, several works concerning the study of the quality of service (QoS) in wireless networksand in particular ad hoc networks were carried out in order to define QoS models, medium accessprotocols, QoS routing protocols and signalling protocols. Therefore, our prime objective was thestudy of the various mechanisms of QoS. Thus, this work is placed in the framework of the QoSconcept and the proposal of mechanisms making it possible to offer optimal solutions to applicationssensitive to certain factors of QoS. The other contribution of this work lies in the integration of theconcept of traffic engineering in the ad hoc networks. Indeed, this concept has enabled us to proposesome mechanisms offering differentiated services in order to ensure QoS in these networks. In thesame way, we have proposed new scheduling mechanisms in order to manage the various types offlows travelling on the MAC layer of the standard IEEE 802.11. Finally, the last contribution wasthe proposal of solutions for load balancing and traffic engineering as well as the validation of thevarious results through simulations and mathematical evidences.; Les réseaux sans fil constituent de plus en plus une technologie émergente permettant à ses utilisateursun accès à l'information et aux services électroniques indépendamment de leurs positionsgéographiques. Le succès de ce type de réseaux est suscité par un grand intérêt de la part des particuliers,des entreprises et du milieu industriel. Les débits atteints actuellement avec les réseauxsans fil rendent possible le transfert de flux multimédia soumis à de fortes contraintes. Ainsi, lerespect de certaines contraintes telles que la bande passante, le délai ou encore le taux de pertesde paquets devient primordial. Cependant, les solutions qui ont été introduites dans le monde desréseaux filaires deviennent inadaptées pour des réseaux utilisant un médium radio partagé sans aucuneadministration centralisée.Dans ce cadre, plusieurs travaux concernant l'étude de la qualité de service (QoS) dans les réseauxsans fil et notamment les réseaux ad hoc ont été réalisés afin de définir des modèle de QoS, des protocolesd'accès au médium, des protocoles de routage avec QoS et des protocoles de signalisation. Pourcela, notre premier objectif a été l'étude des différents mécanismes de QoS. Ce travail se place donc,dans le cadre de la QoS et la proposition de mécanismes permettant d'offrir des solutions optimalesà des applications sensibles à certains facteurs de QoS. L'autre contribution de ce travail se situedans l'intégration du concept de l'ingénierie du trafic dans les réseaux ad hoc. En effet, ce conceptnous a permis de proposer des mécanismes offrant des services différenciés afin d'assurer la QoS dansces réseaux. De même, nous avons proposé de nouveaux mécanismes d'ordonnancement dans le butde gérer les différents types de flux passant par la couche MAC du standard IEEE 802.11. Enfin, ladernière contribution a été la proposition de solutions d'équilibrage de charge, d'ingénierie de traficet la validation des différents résultats par le biais de simulations et de preuves mathématiques.