L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs. / Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.

De nombreuses méthodes de calcul numérique parallèle sont développées pour utiliser les super-ordinateurs d'aujourd'hui, mais ces méthodes utilisent rarement les mécanismes de régulation et perdent en efficacité sur des problèmes non structurés. En particulier, la simulation numérique, par dynamique moléculaire (DM), du mouvement des atomes des protéines dans les structures biologiques est un de ces problèmes irréguliers qui demande beaucoup de puissance de calcul. Cette thèse, à travers la réalisation d'un programme parallèle de DM opérationnel pour l'étude des protéines, s'intéresse à montrer l'apport des processus légers pour la parallélisation de ce type d'application. Ce travail s'inscrit dans le projet INRIA-IMAG APACHE de réalisation du support d'exécution ATHAPASCAN pour les applications parallèles irrégulières et en collaboration avec le laboratoire BMC du CEA-Grenoble. Après une introduction sur la parallélisation d'applications, nous présentons les concepts de base de la parallélisation par des processus légers et des échanges de messages. La deuxième partie du document propose une synthèse des éléments du modèle de DM pour l'étude des protéines et présente la méthode du rayon de coupure pour l'approximation des forces. Dans la suite nous proposons une parallélisation de cette méthode du rayon de coupure par décomposition du domaine de simulation. Nous étudions plusieurs stratégies de placement des calculs afin de trouver le meilleur compromis entre l'équilibre de charge et la minimisation des communications. Puis nous montrons comment la multiprogrammation permet de recouvrir les communications par des calculs. Enfin nous terminons en proposant un mécanisme d'équilibre dynamique de la charge de calcul. De nombreuses mesures sur le IBM-SP1 et le CRAY-T3E sont présentées et montrent l'extensibilité de nos algorithmes parallèles.

Le travail de recherche mené dans cette thèse consiste à développer de nouveaux algorithmes de répartition de charge pour les systèmes de traitement de données massives. Le premier algorithme mis au point, nommé "WACA" (Workload and Cache Aware Algorithm) améliore le temps d'exécution des traitements en se basant sur des résumés de contenus. Le second algorithme, appelé "CAWA" (Cost Aware Algorithm) tire partie de l'information de coût disponible dans les plateformes de type "Cloud Computing" en étudiant l'historique d'exécution des services.L'évaluation de ces algorithmes a nécessité le développement d'un simulateur d'infrastructures de "Cloud" nommé Simizer, afin de permettre leur test avant le déploiement en conditions réelles. Ce déploiement peut se faire de manière transparente grâce au système de distribution et de surveillance de service web nommé "Cloudizer", développé aussi dans le cadre de cette thèse. Ces travaux s'inscrivent dans le cadredu projet de plateforme de traitement de données Multimédia for Machine to Machine (MCUBE), dans le lequel le canevas Cloudizer est mis en oeuvre.

Le travail de recherche mené dans cette thèse consiste à développer de nouveaux algorithmes de répartition de charge pour les systèmes de traitement de données massives. Le premier algorithme mis au point, nommé "WACA" (Workload and Cache Aware Algorithm) améliore le temps d’exécution des traitements en se basant sur des résumés de contenus. Le second algorithme, appelé "CAWA" (Cost Aware Algorithm) tire partie de l’information de coût disponible dans les plateformes de type "Cloud Computing" en étudiant l’historique d’exécution des services.L’évaluation de ces algorithmes a nécessité le développement d’un simulateur d’infrastructures de "Cloud" nommé Simizer, afin de permettre leur test avant le déploiement en conditions réelles. Ce déploiement peut se faire de manière transparente grâce au système de distribution et de surveillance de service web nommé "Cloudizer", développé aussi dans le cadre de cette thèse. Ces travaux s’inscrivent dans le cadredu projet de plateforme de traitement de données Multimédia for Machine to Machine (MCUBE), dans le lequel le canevas Cloudizer est mis en oeuvre. / The research work carried out in this thesis consists in the development of new load balancing algorithms aimed at big data computing. The first algorithm, called « WACA » (Workload and Cache Aware Algorithm), enhances response times by locating data efficiently through content summaries. The second algorithm, called CAWA (Cost AWare Algorithm) takes advantage of the cost information available on Cloud Computing platforms by studying the workload history.Evaluation of these algorithms required the development of a cloud infrastructure simulator named Simizer, to enable testing of these policies prior to their deployment. This deployment can be transparently done thanks to the Cloudizer web service distribution and monitoring system, also developed during this thesis. These works are included in the Multimedia for Machine to Machine (MCUBE) project, where the Cloudizer Framework is deployed.

Dans le futur, les réseaux de distribution deviendront intelligents et actifs et seront utilisés au plus près de leurs limites car l'avènement de la dérégulation avec l'introduction massive de la production décentralisée induira une optimisation des infrastructures de l'énergie pour des besoins environnementaux d'une part, mais aussi par l'introduction de la concurrence dans un secteur autrefois monopolistique. Si on veut utiliser pleinement le potentiel des productions décentralisées dans les réseaux de distribution, on devra rendre ces réseaux observables au moyen de mesures qui seront intégrées dans les systèmes de supervision et de contrôle car sans observabilité et reconstruction d'état du réseau, le contrôle du réseau est impossible. Pour un grand réseau de distribution (quelques milliers de nœuds), avec un taux d'insertion important de productions décentralisées, l'observabilité en temps-réel devient très difficile. Dans la littérature scientifique, on ne trouve pas de travaux prenant en compte les réseaux intelligents et reconfigurables de demain avec production décentralisée massive. L'enjeu du projet sera donc de développer des algorithmes de reconstruction d'état prenant en compte les spécificités des réseaux du futur, à les valider et à les intégrer dans les outils de gestion des réseaux du distributeur. La reconstruction d'état permettra d'aider à l'automatisation et donc à l'introduction d'intelligence dans les réseaux de distribution du futur ainsi qu'à l'insertion massive de productions décentralisées.________________________________________

L'utilisation des vis à rouleaux satellites au cœur d'actionneurs électromécaniques destinées aux commandes de vol nécessite une connaissance la plus précise possible de leur durée de vie suivant le profil de mission. Le calcul de durée de vie d’une vis à rouleaux dans les conditions aéronautiques nécessite des investigations à la fois en résistance (mécanique des contacts) et en fatigue. En résistance, il faut être en mesure de déterminer la répartition de charge dans le système, calculer les pressions de contact et les contraintes en sous-couche pour une charge donnée. En fatigue de contact, il faut, pour un spectre de charges, construire le trajet de chargement tout en prenant en compte le caractère multiaxial des états de contraintes. Moyennant des hypothèses simplificatrices pertinentes, l’étude en résistance de la vis peut être ramenée à celui d’un assemblage mécanique en mouvement stationnaire et à un secteur représentatif. Une analyse tridimensionnelle par éléments finis (EF 3D) nous a permis de cerner le comportement de la vis à rouleaux en statique. Les résultats issus de cette analyse sont ensuite confrontés à des tests de rigidité et ont montré la solidité de notre étude. Enfin, en se servant de ce modèle numérique comme référence, nous avons alors développé un outil de prédimensionnement basé sur le couplage de trois modules qui représentent des modèles semi-analytiques, robustes et ultra-rapides, pour réaliser des calculs en résistance et en fatigue. Le premier modèle est construit sur la base de modèles d’éléments finis filaires (EF 1D). Il sert à déterminer la répartition de charge (statique) dans le système pour n’importe quelle configuration géométrique ou de fonctionnement et pour toute charge axiale. Il permet ainsi de suivre la vis dans son déplacement axial et d’identifier les filets critiques pour chacun des composants de la structure. Le second modèle calcule les pressions de contact et les états de contraintes multiaxiaux, grâce aux méthodes combinées du gradient conjugué (CGM) et de la transformée rapide de Fourier (FFT). Le troisième module procède à une analyse en fatigue suivant trois critères : Crossland, Dang Van et Papadopoulos / The use of satellite roller screws in the core of electromechanical actuators for flight control requires knowledge as accurate as possible in their lifetime according to the mission profile. The calculation of life of a roller screw in aeronautical conditions requires investigations in both resistance (mechanical contacts) and fatigue. In resistance, we must be able to calculate to determine the load distribution in the system, calculate the contact pressures and the in-depth stresses for a given load. In contact fatigue, it is necessary to build for any spectrum loading the loading path taking into account the aspect of the multiaxial stresses. Owing to relevant assumptions, the study in resistance of the screw can be reduced to that of a sectorial mechanical assembly with stationary moving. A three-dimensional analysis based on the three-dimensional Finite Element (FEM 3D) allowed us to identify the behavior of the roller screw in static. The results of this analysis are then compared to stiffness tests and show the pertinence of our study as they were in good agreement. Finally, using this numerical model as a reference, we then developed a preliminary design tool based on the coupling of three modules that represent semi-analytical models, robust and ultra-fast, to perform the calculations in resistance and fatigue. The first model is based on finite element models wired (EF 1D) determines the distribution of load (static) in the system for any geometric configuration and operation and for any axial load. It thus makes it possible to follow the screw in its axial movement and to identify the critical nets for each component of the structure. The second model calculates the contact pressures and multiaxial stresses states, thanks to the combined conjugated gradient method (CGM) and the Fast Fourier Transform (FFT). The third module performs a fatigue analysis according to three criteria: Crossland, Dang Van and Papadopoulos

Nous nous intéressons aux systèmes distribués d'information ouverts, mettant en oeuvre un grand nombre de sources d'informations autonomes et hétérogènes, tels que les systèmes pairs à pairs. Dans un tel contexte, un pair peut jouer à la fois le rôle d'initiateur de requêtes et celui de fournisseur d'informations. Le rôle du médiateur consiste à faire le lien entre initiateurs et fournisseurs, en allouant les requêtes qui lui sont confiées aux fournisseurs qui lui paraissent les plus pertinents. Les attentes des initiateurs et celles des fournisseurs peuvent être antagonistes : les premiers préférant des réponses pertinentes, les seconds privilégiant de traiter certains types de requêtes. Souvent, les médiateurs permettent de prendre en compte qu'un seul des deux points de vue. Cette thèse propose un mécanisme de médiation flexible qui permet de considérer les deux points de vue en même temps, de façon à assurer la satisfaction de tous les acteurs du système. D'un côté, les fournisseurs font des offres monétaires représentant leur intérêt pour la requête. De l'autre, les préférences des initiateurs pour les fournisseurs sont prises en compte au travers de la notion de qualité. Ces deux critères sont la base de la phase de sélection des fournisseurs de notre médiation. De plus, la médiation flexible propose la réquisition de fournisseurs lorsqu'ils ne veulent pas traiter une requête. Nous étudions notre médiation d'un point de vue théorique tout d'abord, en considérant des propriétés usuelles de microéconomie et en proposant une nouvelle définition pour prendre en compte la satisfaction à long terme des participants (initiateurs et fournisseurs). L'étude théorique est complétée par un ensemble de simulations dans différents contextes qui permettent de la comparer à d'autres mécanismes d'allocation de requêtes. Les résultats montrent que la médiation flexible assure généralement la satisfaction sur le long terme des participants et permettent de déterminer les conditions dans lesquelles il est préférable de l'utiliser.

Ce travail a pour but d'améliorer l'efficacité énergétique des réseaux de cœur en éteignant un sous-ensemble de liens par une approche SDN (Software Defined Network). Nous nous différencions des nombreux travaux de ce domaine par une réactivité accrue aux variations des conditions réseaux. Cela a été rendu possible grâce à une complexité calculatoire réduite et une attention particulière au surcoût induit par les échanges de données. Pour valider les solutions proposées, nous les avons testées sur une plateforme spécialement construite à cet effet.Dans la première partie de cette thèse, nous présentons l'architecture logicielle ``SegmenT Routing based Energy Efficient Traffic Engineering'' (STREETE). Le cœur de la solution repose sur un re-routage dynamique du trafic en fonction de la charge du réseau dans le but d'éteindre certains liens peu utilisés. Cette solution utilise des algorithmes de graphes dynamiques pour réduire la complexité calculatoire et atteindre des temps de calcul de l'ordre des millisecondes sur un réseau de 50 nœuds. Nos solutions ont aussi été validées sur une plateforme de test comprenant le contrôleur SDN ONOS et des commutateurs OpenFlow. Nous comparons nos algorithmes aux solutions optimales obtenues grâce à des techniques de programmation linéaires en nombres entiers et montrons que le nombre de liens allumés peut être efficacement réduit pour diminuer la consommation électrique tout en évitant de surcharger le réseau.Dans la deuxième partie de cette thèse, nous cherchons à améliorer la performance de STREETE dans le cas d’une forte charge, qui ne peut pas être écoulée par le réseau si des algorithmes de routages à plus courts chemins sont utilisés. Nous analysons des méthodes d'équilibrage de charge pour obtenir un placement presque optimal des flux dans le réseau.Dans la dernière partie, nous évaluons la combinaison des deux techniques proposées précédemment : STREETE avec équilibrage de charge. Ensuite, nous utilisons notre plateforme de test pour analyser l'impact de re-routages fréquents sur les flux TCP. Cela nous permet de donner des indications sur des améliorations à prendre en compte afin d'éviter des instabilités causées par des basculements incontrôlés des flux réseau entre des chemins alternatifs. Nous croyons à l'importance de fournir des résultats reproductibles à la communauté scientifique. Ainsi, une grande partie des résultats présentés dans cette thèse peuvent être facilement reproduits à l'aide des instructions et logiciels fournis. / This work seeks to improve the energy efficiency of backbone networks by automatically managing the paths of network flows to reduce the over-provisioning. Compared to numerous works in this field, we stand out by focusing on low computational complexity and smooth deployment of the proposed solution in the context of Software Defined Networks (SDN). To ensure that we meet these requirements, we validate the proposed solutions on a network testbed built for this purpose. Moreover, we believe that it is indispensable for the research community in computer science to improve the reproducibility of experiments. Thus, one can reproduce most of the results presented in this thesis by following a couple of simple steps. In the first part of this thesis, we present a framework for putting links and line cards into sleep mode during off-peak periods and rapidly bringing them back on when more network capacity is needed. The solution, which we term ``SegmenT Routing based Energy Efficient Traffic Engineering'' (STREETE), was implemented using state-of-art dynamic graph algorithms. STREETE achieves execution times of tens of milliseconds on a 50-node network. The approach was also validated on a testbed using the ONOS SDN controller along with OpenFlow switches. We compared our algorithm against optimal solutions obtained via a Mixed Integer Linear Programming (MILP) model to demonstrate that it can effectively prevent network congestion, avoid turning-on unneeded links, and provide excellent energy-efficiency. The second part of this thesis studies solutions for maximizing the utilization of existing components to extend the STREETE framework to workloads that are not very well handled by its original form. This includes the high network loads that cannot be routed through the network without a fine-grained management of the flows. In this part, we diverge from the shortest path routing, which is traditionally used in computer networks, and perform a particular load balancing of the network flows. In the last part of this thesis, we combine STREETE with the proposed load balancing technique and evaluate the performance of this combination both regarding turned-off links and in its ability to keep the network out of congestion. After that, we use our network testbed to evaluate the impact of our solutions on the TCP flows and provide an intuition about the additional constraints that must be considered to avoid instabilities due to traffic oscillations between multiple paths.

Dans le futur, les réseaux de distribution deviendront intelligents et actifs et seront utilisés au plus près de leurs limites car l'avènement de la dérégulation avec l'introduction massive de la production décentralisée induira une optimisation des infrastructures de l'énergie pour des besoins environnementaux d'une part, mais aussi par l'introduction de la concurrence dans un secteur autrefois monopolistique. Si on veut utiliser pleinement le potentiel des productions décentralisées dans les réseaux de distribution, on devra rendre ces réseaux observables au moyen de mesures qui seront intégrées dans les systèmes de supervision et de contrôle car sans observabilité et reconstruction d’état du réseau, le contrôle du réseau est impossible. Pour un grand réseau de distribution (quelques milliers de nœuds), avec un taux d’insertion important de productions décentralisées, l’observabilité en temps-réel devient très difficile. Dans la littérature scientifique, on ne trouve pas de travaux prenant en compte les réseaux intelligents et reconfigurables de demain avec production décentralisée massive. L'enjeu du projet sera donc de développer des algorithmes de reconstruction d'état prenant en compte les spécificités des réseaux du futur, à les valider et à les intégrer dans les outils de gestion des réseaux du distributeur. La reconstruction d'état permettra d'aider à l'automatisation et donc à l'introduction d'intelligence dans les réseaux de distribution du futur ainsi qu'à l'insertion massive de productions décentralisées.________________________________________ / In the future, distribution networks will become intelligent and active and will be operated as close as possible to their limits, with the advent of deregulation and with the introduction of mass production that will lead to a decentralized infrastructure, this will guide to an optimization of energy for environmental issues in one side, but also to the introduction of competition in a sector once monopolistic. If the potential of distributed generation in the distribution networks is to be fully exploited, we will make these networks observable through measures which will be integrated into supervision systems and control, because without observability and reconstruction of network status, control network is impossible. For a large distribution network (a few thousand nodes), with an important quantity of distributed generation, real-time observability becomes very difficult. In the scientific literature, there is no work taking into consideration intelligent networks and reconfigurable of the future with decentralized mass power generation. The challenge of the project will be to develop algorithms of reconstruction of the state of the network, taking into account the characteristics of the networks of the future, to validate and integrate them into management tools distribution networks. The reconstruction of the state will assist in the automation and hence the introduction of intelligence in the distribution networks of the future and the insertion massive distributed generation.

La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.