Cette thèse traite du problème de la redistribution dynamique parallèle efficace de la charge pour les problèmes numériques de très grande taille. Nous présentons tout d'abord un état de l'art des algorithmes permettant de résoudre les problèmes du partitionnement, du repartitionnement, du placement statique et du re-placement. Notre première contribution vise à étudier, dans un cadre séquentiel, les caractéristiques algorithmiques souhaitables pour les méthodes parallèles de repartitionnement. Nous y présentons notre contribution à la conception d'un schéma multi-niveaux k-aire pour le calcul sequentiel de repartitionnements. La partie la plus exigeante de cette adaptation concerne la phase d'expansion. L'une de nos contributions majeures a été de nous inspirer des méthodes d'influence afin d'adapter un algorithme de raffinement par diffusion au problème du repartitionnement.Notre deuxième contribution porte sur la mise en oeuvre de ces méthodes sur machines parallèles. L'adaptation du schéma multi-niveaux parallèle a nécessité une évolution des algorithmes et des structures de données mises en oeuvre pour le partitionnement. Ce travail est accompagné d'une analyse expérimentale, qui est rendue possible grâce à la mise en oeuvre des algorithmes considérés au sein de la bibliothèque Scotch.

Les Alimentations Sans Interruption sont utilisées pour assurer la qualité et la continuité de l'énergie fournie aux charges sensibles. Basées sur deux conversions d'énergie électrique, ces alimentations supportent en permanence la puissance de la charge, rendant crucial leur rendement. Cette thèse a exploré différentes voies d'amélioration du rendement du commutateur assurant la conversion : le choix des composants semi-conducteurs, celui de la structure de conversion et du mode de fonctionnement. Le filtrage a été pris en compte sans faire l'objet d'investigations poussées. La méthode d'estimation du rendement, exploitant des données des constructeurs, a permis de quantifier l'impact et les limites de chaque voie explorée. Plusieurs structures de conversion multi-niveaux en commutation douce ont été développées, utilisant un pôle résonant. Enfin, plusieurs expérimentations ont validé les modèles utilisés, le concept du pôle résonant et la réalisation d'un prototype fonctionnel de 125 kVA.

Cette thèse s'inscrit dans le cadre de la programmation par contraintes quantifiées, un formalisme étendantla programmation par contraintes classique en ajoutant aux variables des quantificateurs existentiels ouuniversels, ce qui apporte en théorie une expressivité suffisante pour modéliser des problèmes avec adversaireou incertitude sur certains paramètres sous forme de problèmes appelés QCSP (Quantified Constraintsatisfaction Problem).Nous commençons par apporter une réponse aux difficultés de modélisation de problèmes réels dont estfrappée la programmation par contraintes quantifiées en introduisant une extension aux QCSP permettantd'expliciter les actions possibles de l'agent principal et de son adversaire. Puis, nous décrivons différentproblèmes grâce à ce formalisme, et discutons de la place de cette extension parmi les formalismes voisins créésen réponse à cette même difficulté de modélisation. Enfin, nous nous intéressons à la notion d'optimisationdans le cas des contraintes quantifiées, et apportons un formalisme d'optimisation de contraintes quantifiéespermettant d'exprimer des problèmes multi-niveaux non linéaires.

Cette thèse a pour but d'établir le lien entre la microstructure des matériaux et leurs propriétés macroscopiques qui est un verrou technologique et scientifique important, dans un contexte de conception de matériaux miniaturisés, directement intégrés et aux performances améliorées. Pour permettre le plein essor de ces nouveaux matériaux, des efforts doivent notamment être fournis sur le développement de nouveaux procédés technologiques, capables de déposer la matière avec un contrôle à l'échelle atomique. Ceci ne peut se faire sans un accompagnement théorique pour accéder à une compréhension fondamentale des mécanismes gérant la croissance de ces matériaux. Dans ce contexte, la modélisation prédictive du procédé de dépôt s'avère stratégique pour guider les technologues vers la conception de matériaux nanostructurés avancés. Pour répondre au mieux à cette problématique, les travaux présentés dans cette thèse suivent une approche multi-niveaux. Dans un premier temps, une étude à l'échelle atomique avec des calculs DFT est faite, afin de relever des énergies, des mécanismes et des structures, localement. Ces résultats sont ensuite utilisés comme paramètres d'entrée dans un outil de simulation utilisant la méthodologie Monte Carlo cinétique, développé spécialement au cours de ces travaux. Cet outil permet de simuler des systèmes de plusieurs dizaines de milliers d'atomes sur des temps longs, pour des coûts en calculs faibles. Les résultats obtenus avec cet outil sont directement comparables avec des résultats expérimentaux. Nous avons donc un outil doté d'une granularité à l'échelle atomique équipé d'une plateforme de simulation pour permettre à l'ingénieur une utilisation simple et intuitive de celui-ci. Cet outil se veut prédictif et permettra ainsi au technologue de réaliser des simulations prédictives et par suite de limiter les coûts et les essais en salle blanche. L'objectif est d'établir un lien entre la nanostructuration à l'échelle atomique et le procédé de fabrication, à travers cette plateforme de simulation simple d'utilisation. Ici, nous proposons un modèle basé sur une méthodologie de type Monte Carlo cinétique pour simuler le dépôt PVD de matériaux multicouches Al/CuO. / The aim of this thesis is to link materials microstructure and their macroscopic properties which are a very important technologic and scientific barrier, especially for material miniaturising, directly integrated and with improved specifications. Enabling this new material booming implies efforts in the development of new technological processes able to make mater deposition with atomic scale control. This can't be done without a theoretical support in order to access to a fondamental understanding of material growth mechanisms. In this context, predictive modelling of deposition process is strategic, leading technologists toward advanced nanostructured materials conception. We choose the multi-scale approach to answer this problematic. First, an atomic scale study is done, using DFT, in order to measure local energies, mechanisms and structures. Then, those results are used as input parameters in a home made simulation tool using kinetic Monte Carlo. This tool is able to simulate systems with several tens of thousands atoms, during long simulation time, for low calculation time. The outputs are directly comparable to experimental data. In summary, we obtain an atomic grain texture tool, fitted with simulation platform, for an easy and intuitive use for the engineer. This tool is predictive and allows technologists to make predictive simulations, restricting cost and test in clean room. The aim is to set up a link between the atomic scale nanostructuration and the fabrication process, toward this user-friendly simulation platform. We suggest a model based on kinetic Monte Carlo, for the PVD deposition simulation of Al/CuO multilayered materials.

Les simulations dites multi-physiques couplent plusieurs phases de calcul. Lorsqu’elles sont exécutées en parallèle sur des architectures à mémoire distribuée, la minimisation du temps de restitution nécessite dans la plupart des cas d’équilibrer la charge entre les unités de traitement, pour chaque phase de calcul. En outre, la distribution des données doit minimiser les communications qu’elle induit. Ce problème peut être modélisé comme un problème de partitionnement de graphe multi-critères. On associe à chaque sommet du graphe un vecteur de poids, dont les composantes, appelées « critères », modélisent la charge de calcul porté par le sommet pour chaque phase de calcul. Les arêtes entre les sommets, indiquent des dépendances de données, et peuvent être munies d’un poids reflétant le volume de communication transitant entre les deux sommets. L’objectif est de trouver une partition des sommets équilibrant le poids de chaque partie pour chaque critère, tout en minimisant la somme des poids des arêtes coupées, appelée « coupe ». Le déséquilibre maximum toléré entre les parties est prescrit par l’utilisateur. On cherche alors une partition minimisant la coupe, parmi toutes celles dont le déséquilibre pour chaque critère est inférieur à cette tolérance. Ce problème étant NP-Dur dans le cas général, l’objet de cette thèse est de concevoir et d’implanter des heuristiques permettant de calculer efficacement de tels partitionnements. En effet, les outils actuels renvoient souvent des partitions dont le déséquilibre dépasse la tolérance prescrite. Notre étude de l’espace des solutions, c’est-à-dire l’ensemble des partitions respectant les contraintes d’équilibre, révèle qu’en pratique, cet espace est immense. En outre, nous prouvons dans le cas mono-critère qu’une borne sur les poids normalisés des sommets garantit que l’espace des solutions est non-vide et connexe. Nous fondant sur ces résultats théoriques, nous proposons des améliorations de la méthode multi-niveaux. Les outils existants mettent en oeuvre de nombreuses variations de cette méthode. Par l’étude de leurs codes sources, nous mettons en évidence ces variations et leurs conséquences à la lumière de notre analyse sur l’espace des solutions. Par ailleurs, nous définissons et implantons deux algorithmes de partitionnement initial, se focalisant sur l’obtention d’une solution à partir d’une partition potentiellement déséquilibrée, au moyen de déplacements successifs de sommets. Le premier algorithme effectue un mouvement dès que celui-ci améliore l’équilibre, alors que le second effectue le mouvement réduisant le plus le déséquilibre. Nous présentons une structure de données originale, permettant d’optimiser le choix des sommets à déplacer, et conduisant à des partitions de déséquilibre inférieur en moyenne aux méthodes existantes. Nous décrivons la plate-forme d’expérimentation, appelée Crack, que nous avons conçue afin de comparer les différents algorithmes étudiés. Ces comparaisons sont effectuées en partitionnant un ensembles d’instances comprenant un cas industriel et plusieurs cas fictifs. Nous proposons une méthode de génération de cas réalistes de simulations de type « transport de particules ». Nos résultats démontrent la nécessité de restreindre les poids des sommets lors de la phase de contraction de la méthode multi-niveaux. En outre, nous mettons en évidence l’influence de la stratégie d’ordonnancement des sommets, dépendante de la topologie du graphe, sur l’efficacité de l’algorithme d’appariement « Heavy-Edge Matching » dans cette même phase. Les différents algorithmes que nous étudions sont implantés dans un outil de partitionnement libre appelé Scotch. Au cours de nos expériences, Scotch et Crack renvoient une partition équilibrée à chaque exécution, là où MeTiS, l’outil le plus utilisé actuellement, échoue une grande partie du temps. Qui plus est, la coupe des solutions renvoyées par Scotch et Crack est équivalente ou meilleure que celle renvoyée par MeTiS. / Multiphysics simulation couple several computation phases. When they are run in parallel on memory-distributed architectures, minimizing the simulation time requires in most cases to balance the workload across computation units, for each computation phase. Moreover, the data distribution must minimize the induced communication. This problem can be modeled as a multi-criteria graph partitioning problem. We associate with each vertex of the graph a vector of weights, whose components, called “criteria”, model the workload of the vertex for each computation phase. The edges between vertices indicate data dependencies, and can be given a weight representing the communication volume transferred between the two vertices. The goal is to find a partition of the vertices that both balances the weights of each part for each criterion, and minimizes the “edgecut”, that is, the sum of the weights of the edges cut by the partition. The maximum allowed imbalance is provided by the user, and we search for a partition that minimizes the edgecut, among all the partitions whose imbalance for each criterion is smaller than this threshold. This problem being NP-Hard in the general case, this thesis aims at devising and implementing heuristics that allow us to compute efficiently such partitions. Indeed, existing tools often return partitions whose imbalance is higher than the prescribed tolerance. Our study of the solution space, that is, the set of all the partitions respecting the balance constraints, reveals that, in practice, this space is extremely large. Moreover, we prove in the mono-criterion case that a bound on the normalized vertex weights guarantees the existence of a solution, and the connectivity of the solution space. Based on these theoretical results, we propose improvements of the multilevel algorithm. Existing tools implement many variations of this algorithm. By studying their source code, we emphasize these variations and their consequences, in light of our analysis of the solution space. Furthermore, we define and implement two initial partitioning algorithms, focusing on returning a solution. From a potentially imbalanced partition, they successively move vertices from one part to another. The first algorithm performs any move that reduces the imbalance, while the second performs at each step the move reducing the most the imbalance. We present an original data structure that allows us to optimize the choice of the vertex to move, and leads to partitions of imbalance smaller on average than existing methods. We describe the experimentation framework, named Crack, that we implemented in order to compare the various algorithms at stake. This comparison is performed by partitioning a set of instances including an industrial test case, and several fictitious cases. We define a method for generating realistic weight distributions corresponding to “Particles-in-Cells”-like simulations. Our results demonstrate the necessity to coerce the vertex weights during the coarsening phase of the multilevel algorithm. Moreover, we evidence the impact of the vertex ordering, which should depend on the graph topology, on the efficiency of the “Heavy-Edge” matching scheme. The various algorithms that we consider are implemented in an open- source graph partitioning software called Scotch. In our experiments, Scotch and Crack returned a balanced partition for each execution, whereas MeTiS, the current most used partitioning tool, fails regularly. Additionally, the edgecut of the solutions returned by Scotch and Crack is equivalent or better than the edgecut of the solutions returned by MeTiS.

Une performance soutenable et importante est l'objectif principal du management de toute organisation. La viabilité d'une entreprise dépend de sa capacité à trouver un équilibre entre deux activités très différentes. D’une part elle doit exploiter les certitudes existantes pour garantir la réussite des opérations courantes et d’autre part explorer de nouvelles opportunités pour la mise en œuvre rapide des nouvelles idées qui garantissent l'avenir de l'organisation. Les organisations ambidextres ont une aptitude à poursuivre de manière simultanée ces activités et produisent des innovation radicales et incrémentielles. Notre recherche montre que pour être ambidextre seulement la séparation des activités n’est pas suffisante. Sans une intégration et une combinaison de ces structures et ces processus, l’unité d’exploration sera incapable d’exploiter ses résultats et a plus de chance disparaitre avec le temps comme la structure inefficace. Pour survivre sur le long terme, l’entreprise doit intégrer l’ambidexterité de manière fractale et dynamique. Ce nouveau concept propose une solution à la question de l’équilibre entre les activités et elle se définit comme la capacité organisationnelle à reproduire l’exploration et l’exploitation simultanément à différents niveaux organisationnels et être capable de changer leurs proportions quand cela est nécessaire / The main objective in management of any organization is a successful and sustainable performance. To survive over time, a company should combine two competing activities. On the one hand, it must exploit existing certainties to be effective in the short term, and on the other hand, being capable at the same time to explore new opportunities to be innovative in the future. Ambidextrous organizations have the ability to pursue these activities simultaneously and produce radical and incremental innovation. In our research, we show that to achieve ambidexterity separation of activities is important, but not sufficient. Without integration between business structures and processes, the exploratory activity of the innovation unit is more likely to shrink and disappear with time as unprofitable function. To survive and sustain in the long term, a company should adapt fractal and dynamic ambidexterity. This new concept provides us with a solution to the question of balance and determines the organizational ability to define and set the appropriate proportions of exploration and exploitation simultaneously at multiple organizational levels and re-configure them when it is necessary to meet the change.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les cartes représentent l'information géographique d'une zone donnée de manière d'autant plus simplifiée que l'échelle de la carte est petite. Le procédé de simplification, appelé généralisation cartographique, est soumis au respect de contraintes de lisibilité, d'adéquation de la représentation avec le niveau d'abstraction souhaité et de cohérence avec la réalité. La volonté d'automatiser le processus de création de cartes à partir de bases de données géographiques, a conduit à la création d'algorithmes permettant d'effectuer cette simplification objet par objet. Néanmoins, les choix des algorithmes, tout comme leur paramétrage, sont autant influencés par l'objet sur lequel ils s'appliquent que par les autres objets en relation (e.g. bâtiment à proximité d'un autre, route parallèle à un alignement de bâtiments). Ce constat a motivé l'utilisation de modèles multi-agents pour la généralisation automatisée de cartes. Le principe de ces modèles multi-agents repose sur la modélisation des objets (e.g. bâtiment, tronçon de route, îlot urbain) sous forme d'agents qui cherchent à se généraliser de façon à satisfaire leurs contraintes. Plusieurs modèles multi-agents ont été proposés, chacun ayant une approche différente des interactions entre niveaux. Ici, nous entendons par niveau, par exemple, la distinction entre les agents individuels comme un bâtiment, des agents représentant un groupe d’autres agents, comme un îlot urbain composé des routes l’entourant et des bâtiments inclus dans l’îlot.Nous étudions l'unification de ces modèles en nous appuyant sur le paradigme multi-niveaux PADAWAN, afin de faciliter les interactions entre agents de niveaux différents. Nous proposons ainsi le modèle DIOGEN, adaptant les principes d’interaction entre agents de niveaux différents à la généralisation cartographique guidée par des contraintes, ce qui a permis d’unifier les précédents modèles AGENT, CartACom et GAEL, tout en disposant de nouvelles capacités prometteuses.Nous avons évalué notre proposition sur un ensemble de cas d’étude. Parmi ces cas, nous nous sommes penchés sur la généralisation de carte de randonnée, où les itinéraires sont symbolisés individuellement avec des symboles différents, à la manière des plans de bus. La présence de plusieurs symboles d’itinéraires sur une même route support amène des problèmes de généralisation particuliers, comme le choix du positionnement des itinéraires de part et d’autre de la route, ou les implications pour les autres objets de la carte (e.g. points d’intérêts, bâtiments) se retrouvant sous le symbole de l’itinéraire, problèmes que nous essayons de résoudre en nous appuyant sur notre proposition de représentation formelle multi-niveaux.Ce travail nous a ensuite conduit à identifier des comportements multi-niveaux récurrents. Nous les avons exprimés de façon générique sous forme de patterns d’analyse, affranchies des spécificités de la généralisation cartographique, et de la résolution de problèmes contraints / Maps show geographic information of a given area in a simplified way, particularly when the scale is small. The simplification process, called cartographic generalisation, is submitted to several constraints : legibility, adequation to the abstraction level, and consistency with reality. The will to automate the maps creation process from geographical databases led to the creation of algorithms allowing the simplification object by object. However the choice of the algorithms, as their settings, are influenced by the object on which it is applied, and by the other objects in relation with this object (e.g. a building close to another one, a road parallel to a buildings alignment). This motivates the use of multi-agents models for automated map generalisation. Several multi-agent models were proposed, each of them having a different approach to manage multi-levels relations. Here, what we call a level is, for instance, the distinction between individual agents, like a building, and agents representing a group of other agents, like a urban block composed by the surrounding roads and buildings inside.We study the unification of existing models, using the multi-level paradigm PADAWAN, in order to simplify interactions between agents in different levels. We propose the DIOGEN model, in which the principle of interactions between agents of different levels is adapted to cartographic generalisation guided by constraints, those allowing to unify the existing models AGENT, CartACom and GAEL, and giving promising features.We evaluate our proposal on different case studies. Among them, we study the generalisation of trekking maps, where the routes are symbolized individually by a different couloured line symbols, like on bus maps. The presence of several route symbols on a same road leads to specific generalisation issues, like the choice of the side of each route symbol position, or the implications for the other objects on the map (e.g. points of interest, buildings) under the route symbol – issues tackled using our proposal of formal multi-levels representation.This work leads us to the identification of recurrent behaviours. We express them as analysis patterns, in a way that is independent from cartographic generalisation and constraint solving problems

Les Alimentations Sans Interruption sont utilisées pour assurer la qualité et la continuité de l'énergie fournie aux charges sensibles. Basées sur deux conversions d'énergie électrique, ces alimentations supportent en permanence la puissance de la charge, rendant crucial leur rendement. Cette thèse a exploré différentes voies d'amélioration du rendement du commutateur assurant la conversion : le choix des composants semi-conducteurs, celui de la structure de conversion et du mode de fonctionnement. Le filtrage a été pris en compte sans faire l'objet d'investigations poussées. La méthode d'estimation du rendement, exploitant des données des constructeurs, a permis de quantifier l'impact et les limites de chaque voie explorée. Plusieurs structures de conversion multi-niveaux en commutation douce ont été développées, utilisant un pôle résonant. Enfin, plusieurs expérimentations ont validé les modèles utilisés, le concept du pôle résonant et la réalisation d'un prototype fonctionnel de 125 kVA. / The Uninterruptible Power Supplies (UPS) are used to supply such critical load with a high level of quality and continuity. The topology based on two consecutive converters providing permanently the whole power leading to made the efficiency a key point of the UPS. To improve the efficiency of the semi-conductors part, three ways have been studied in this thesis: The semi-conductor area, the topology of the converter and the switching mode. The filter losses have been taken into account based on the state of the art. The estimation of the efficiency, based on the datasheet from manufacturers, allow quantifying each way. Some soft-switching multi-level topologies have been developped and patented. Finally, experimentations have been made to asses the relevance of the models, the working of new topologies and the efficiency of the proposed 125 kVA UPS.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.