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.

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

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

Cette thèse, réalisée en collaboration avec le Groupe Renault dans le cadre d’un projet d’automatisation du kitting, s’intéresse à l’optimisation du processus de kitting en termes de maximisation du temps de cycle. Pour cela, nous étudions différentes configurations de système de kitting hybride avec robots(s) et opérateur(s) travaillant en série et séparés par un stock de découplage. Le(s) robot(s) commence(nt) la préparation des kits de pièces puis le(s) opérateur(s) se trouvant dans la partie manuelle du kitting récupère(nt) cette préparation et la complète(nt) avec les pièces affectées à cette zone.Notre objectif est de développer un outil d’aide à la décision permettant d’évaluer la performance d’un kitting hybride et de simuler son fonctionnement dans une configuration donnée (layout, politique de picking, etc.) avant son déploiement physique.Tout d’abord, à travers une modélisation des opérationsélémentaires de kitting effectuées par des robots et des opérateurs (prise et dépose, déplacement, etc.), nous proposons un modèle de temps de cycle permettant d’évaluer la performance du système hybride en termes de temps de cycle. Ensuite, nous développons un modèle d’affectation de pièces (PLMNE) permettant de les répartir entre kitting robotisé et manuel. L’objectif est de minimiser les temps de cycle et d’équilibrer la charge de travail entre les deux modes de kitting. Le modèle est appliqué à deux études de cas pratiques issues d’une usine Renault. Les résultats permettent d’identifier les paramètres qui impactent le plus les temps de cycle et le choix d’affectation des pièces entre kitting automatisé et manuel. Enfin, nous développons un modèle de simulation afin de calculer la taille optimale du stock de découplage entre kitting automatisé et manuel dans le but de maximiser la cadence du système hybride de kitting. / In this thesis, conducted with Renault in the context of a kitting automation project, we are interested in the optimisation of kitting processes in terms of cycle time maximisation. To do so, we study different configurations of hybrid robot-operator kitting systems where robots (two types of robots considered) and operators are connected in series by an intermediate buffer (to decouple their activities). The robotic kitting area starts the preparation of kits then the operators in the manual kitting area retrieve the preparation of robots and complete with the remaining parts.Our objective is to develop a decision-making tool that assesses the hybrid system performance in a given configuration (layout, picking policy, etc.).First, through a modelling of elementary kitting operations performed by robots and operators (pick and place, travel, etc.), we develop a cycle time model to assess the performance of hybrid kitting systems. Then, we develop an assignment model that assigns parts (formulated as a mixed integer linear programming (MILP) problem) either to robotic or manual kitting areas with the objective of minimising cycle times and balancing workload between them. The model is applied to two case studies pertaining to a Renault plant. This analysis identifies the parameters that influence cycle times and the choice between robotic and manual kitting. Finally, we develop a simulation model to find the optimal buffer size between robotic and manual kitting so that throughput is maximised.

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.

Les applications multimédias, dans les réseaux de capteurs sans fil, véhiculent des données volumineuses, qui nécessitent un taux de transmission élevé et un traitement intensif et par conséquent une consommation d'énergie importante. Transmettre efficacement ces flux hétérogènes, tout en assurant leur fiabilité et garantir les exigences de QoS, avec les ressources limitées disponibles, en particulier dans les contextes critiques, demeure un verrou scientifique ouvert. C’est pourquoi, dans le cadre de cette thèse, nous nous sommes intéressés aux aspects liés : au routage, à la tolérance aux pannes et à la gestion des interférences dans les RCMSF.Compte tenu, du très faible nombre de protocoles de routage, qui ont approché la phase expérimentale et encore moins ceux qui l’ont abordé pendant la transmission des données en temps réel, nous avons développé dans ce contexte, un protocole routage géographique baptisé GNMFT (Geographic Non-interfering Multipath Fault-tolerant),En premier lieu, nous avons amélioré le mode de sélection des nœuds, utilisé par le transfert glouton, pour faire face au problème du Minimum-local, où une fonction objective multicritères (distance, énergie et puissance de réception) relative au choix du prochain saut a été définie. Puis, nous avons introduit une phase d’optimisation des chemins construits afin d’éliminer les boucles et une approche adaptative gérant les transmissions simultanées des différents trafics.Par la suite, nous nous sommes orientés vers la tolérance aux pannes, pour assurer la fiabilité des données transmises ainsi que la connectivité du réseau. A cet effet, nous avons modélisé le nombre des paquets perdus durant la livraison des paquets et proposé deux mécanismes : un curatif pour réparer les défaillances soudaines et un préventif afin d’anticiper l’épuisement des batteries. Les deux mécanismes sont combinés avec une stratégie de basculement dynamique lors de la construction des chemins alternatives.En dernier lieu, nous avons présenté un modèle d’interférence et un troisième mécanisme qui limite les interactions entre les liens adjacents. De plus, nous avons défini également un modèle de perte de chemins dans un environnement multi-paires (source,sink) et nous avons calculé le coefficient de probabilité d’erreurs basée sur une fonction de distance qui sépare les flux de données. Une nouvelle métrique a été ajouté dans la fonction objective, relative à la somme des bruits des nœuds actifs qui interférent sur les nœuds du ForwardingSet du nœud courant.Les résultats obtenus montrent l’efficacité des approches proposées qui ont été étudiées et validées à la fois par simulation et sur un banc d’essai expérimental. / Multimedia applications in WSNs convey large data (image, audio and video) that requires high transmission rate and intensive treatment and therefore high energy consumption. Effectively transmit these heterogeneous flows, while ensuring their reliability and guaranteeing QoS requirements, with the limited resources available, especially in critical contexts, remains an open scientific problem. That is why, in this thesis, we are interested in aspects related to : routing, fault tolerance and interference management in WMSNs.Given the very low number of routing protocols, that have approached the experimental phase and still less those who approached it during data transmission in real time, we developed in this context, a geographic routing protocol baptised GNMF (Geographic Non-interfering Multipath Fault-tolerant),First, we improved node's selection mode used by the greedy-forwarding, to deal with local minimum problem, where a multi-criteria objective function (distance, energy and reception power) related to next-hop choice has been defined. Then, we introduced an optimization phase of built paths to eliminate loops and an adaptive approach to manage simultaneous traffic transmissions.After that, we oriented towards fault tolerance, to ensure transmitted data reliability and network connectivity. To this end, we modeled the number of lost packets during package delivery and proposed two mechanisms. The curative is used when sudden failures occurs and the preventive to anticipate batteries depletion. Both are combined with a dynamic failover strategy during alternative paths construction.Finally, we presented an interference model and a third mechanism that limits interactions between adjacent links. In addition, we also defined a path loss model in a multipairs environment (source, sink) and computed the error probability coefficient based on a distance function that separates the data flows. A new metric has been added in the objective function, related to noise sum of the active nodes that interferes on forwarding set nodes of the current node.Obtained results show the effectiveness of the proposed approaches that have been studied and validated both by simulation and on an experimental testbed.