Cette thèse a pour but de proposer un algorithme de partitionnement matériel/logiciel optimisé. On travaille sur l'hypothèse de que quelques caractéristiques spécifiques à certains algorithmes déjà publiés puissent être combinées de façon avantageuse, menant à l'amélioration d'un algorithme de partitionnement de base et, par conséquence, des systèmes hétérogènes générés par cet algorithme. L'ensemble d'optimisations proposées pour être réalisées dans ce nouvel algorithme consiste en : généralisation des architecturescible candidates avec l'ajout de FPGA's pour le partitionnement, considération précise des coûts et puissances des fonctions allouées en matériel, ordonnancement de systèmes au matériel dynamiquement reconfigurable, et prise en compte de plusieurs alternatives d'implémentation d'un noeud d'application dans un même processeur. Ces optimisations sont implémentées en versions successives de l'algorithme de partitionnement proposé, lesquelles sont testées avec deux applications de traitement du signal. Les résultats du partitionnement démontrent l'effet de chaque optimisation sur la qualité du système hétérogène obtenu.

Le partitionnement de graphes est une technique employée dans de nombreux domaines scientifiques. Il est utilisé pour résoudre des problèmes d'optimisation, modélisés sous la forme de graphes valués ou non, et pour lesquels la recherche de bonnes solutions équivaut au calcul, éventuellement récursivement, de coupes sommet ou arête les plus petites possible et qui équilibrent les tailles des sous-parties séparées. La plupart des méthodes actuelles de partitionnement de graphes mettent en oeuvre un schéma multi-niveaux, dans lequel le graphe à partitionner est successivement contracté pour former une famille de graphes de plus en plus petits, mais de structure topologique similaire, de sorte qu'une partition initiale calculée sur le plus petit graphe puisse être propagée de proche en proche, par prolongations et raffinements successifs, jusqu'à obtenir un partitionnement du graphe initial. Du fait de l'augmentation croissante de la taille des problèmes à résoudre, ceux-ci ne peuvent plus être traités de façon séquentielle sur un unique ordinateur. Il est donc nécessaire de concevoir des algorithmes parallèles de partitionnement de graphes, aptes à traiter des graphes à plusieurs milliards de sommets distribués sur plusieurs milliers de processeurs. Plusieurs auteurs s'étaient déjà attelés à cette tâche, mais la performance des algorithmes proposés, ou la qualité des solutions produites, se dégradent lorsque le nombre de processeurs augmente. Ce mémoire présente les travaux réalisées au sein du projet PT-Scotch sur la conception d'algorithmes efficaces et robustes pour la parallélisation du schéma multi-niveaux. Il se concentre en particulier sur les phases de contraction et de raffinement, qui sont les plus critiques en termes de performance et de qualité des solutions produites. Il propose un algorithme parallèle probabiliste d'appariement, ainsi qu'un ensemble de méthodes permettant de réduire l'espace des solutions au cours la phase de raffinement et facilitant l'usage de méthodes globales, qui passent mieux à l'échelle mais sont en général bien plus coûteuses que les algorithmes d'optimisation locale habituellement mis en oeuvre dans le cas séquentiel.

Les systèmes d'information (S.I.) d'entreprise se construisent à partir de progiciels configurés, intégrés et déployés dans des organisations en mouvement, à l'exemple des ERP ( Enterprise Resource Planning). Les enjeux d'efficacité des projets, d'efficience des usages, de performances opérationnelles, d'alignement aux stratégies d'entreprise sont connus. Ils fondent la problématique de l'intégration organisationnelle et informationnelle, avec la généricité nécessaire à la diffusion des bonnes pratiques et normes, dans une démarche continue mêlant analyse de l'existant, conception et mise en oeuvre par l'organisation. Un cadre d'ingénierie dirigée par les modèles se diffuse progressivement à partir des travaux en modélisation d'entreprise et en système d'information. Ce mémoire propose une approche centrée sur l'intégration organisationnelle et informationnelle afin d'enrichir ce cadre dans les phases de conception, d'intégration et d'usage pour prendre en compte les interdépendances entre les éléments d'un système et entre les points de vue différents sur ce système. Ce cadre étendu repose sur un méta-modèle de l'intégration et une démarche d'alignement entre les points de vue. Il s'appuie sur la théorie des graphes pour définir une « distance » et un « voisinage » permettant de représenter les différentes formes d'intégration qui conditionnent, permettent ou limitent les résultats des projets. L'analyse de différents cas issus de référentiels métiers permet de valider la pertinence du cadre proposé pour enrichir les représentations de ces modèles.

Durant cette derni��re d��cennie, la diffusion du format XML pour repr��senter les donn��es g��n��r��es par et ��chang��es sur le Web a ��t�� accompagn��e par la mise en ��uvre de nombreux moteurs d'��valuation de requ��tes et de mises �� jour XQuery. Parmi ces moteurs, les syst��mes " m��moire centrale " (Main-memory Systems) jouent un r��le tr��s important dans de nombreuses applications. La gestion et l'int��gration de ces syst��mes dans des environnements de programmation sont tr��s faciles. Cependant, ces syst��mes ont des probl��mes de passage �� l'��chelle puisqu'ils requi��rent le chargement complet des documents en m��moire centrale avant traitement.Cette th��se pr��sente une technique de partitionnement des documents XML qui permet aux moteurs " m��moire principale " d'��valuer des expressions XQuery (requ��tes et mises �� jour) pour des documents de tr��s grandes tailles. Cette m��thode de partitionnement s'applique �� une classe de requ��tes et mises �� jour pertinentes et fr��quentes, dites requ��tes et mises �� jour it��ratives.Cette th��se propose une technique d'analyse statique pour reconna��tre les expressions " it��ratives ". Cette analyse statique est bas��e sur l'extraction de chemins �� partir de l'expression XQuery, sans utilisation d'information suppl��mentaire sur le sch��ma. Des algorithmes sont sp��cifi��s, utilisant les chemins extraits par l'��tape pr��c��dente, pour partitionner les documents en entr��e en plusieurs parties, de sorte que la requ��te ou la mise �� jour peut ��tre ��valu��e sur chaque partie s��par��ment afin de calculer le r��sultat final par simple concat��nation des r��sultats obtenus pour chaque partie. Ces algorithmes sont mis en ��uvre en " streaming " et leur efficacit�� est valid��e exp��rimentalement.En plus, cette m��thode de partitionnement est caract��ris��e ��galement par le fait qu'elle peut ��tre facilement impl��ment��e en utilisant le paradigme MapReduce, permettant ainsi d'��valuer une requ��te ou une mise �� jour en parall��le sur les donn��es partitionn��es.

In this thesis, we introduce the Partitioning-Hub Location-Routing problem (PHLRP), which can be classied as a variant of the hub location problem. PHLRP consists of partitioning a network into sub-networks, locating at least one hub in each subnetwork and routing the traffic within the network such that all inter-subnetwork traffic is routed through the hubs and all intra-subnetwork traffic stays within the sub-networks all the way from the source to the destination. Obviously, besides the hub location component, PHLRP also involves a graph partitioning component and a routing component. PHLRP finds applications in the strategic planning or deployment of the Intermediate System-Intermediate System (ISIS) Internet Protocol networks and the Less-than-truck load freight distribution systems. First, we introduce three IP formulations for solving PHLRP. The hub location component and the graph partitioning components of PHLRP are modeled in the same way in all three formulations. More precisely, the hub location component is represented by the p-median variables and constraints; and the graph partitioning component is represented by the size-constrained graph partitioning variables and constraints. The formulations differ from each other in the way the peculiar routing requirements of PHLRP are modeled. We then carry out analytical and empirical comparisons of the three IP formulations. Our thorough analysis reveals that one of the formulations is provably the tightest of the three formulations. We also show analytically that the LP relaxations of the other two formulations do not dominate each other. On the other hand, our empirical comparison in a standard branch-and-cut framework that is provided by CPLEX shows that not the tightest but the most compact of the three formulations yield the best performance in terms of solution time. From this point on, based on the insight gained from detailed analysis of the formulations, we focus our attention on a common sub-problem of the three formulations: the so-called size-constrained graph partitioning problem. We carry out a detailed polyhedral analysis of this problem. The main benet from this polyhedral analysis is that the facets we identify for the size-constrained graph partitioning problem constitute strong valid inequalities for PHLRP. And finally, we wrap up our efforts for solving PHLRP. Namely, we present the results of our computational experiments, in which we employ some facets of the size-constrained graph partitioning polytope in a branch-and-cut algorithm for solving PHLRP. Our experiments show that our approach brings signicant improvements to the solution time of PHLRP when compared with the default branch-and-cut solver of XPress. / Dans cette thèse, nous introduisons le problème Partitionnement-Location des Hubs et Acheminement (PLHA), une variante du problème de location de hubs. Le problème PLHA partitionne un réseau afin d'obtenir des sous-réseaux, localise au moins un hub dans chaque sous-réseau et achemine le traffic dans le réseau de la maniére suivante : le traffic entre deux sous-réseaux distincts doit être éxpedié au travers des hubs tandis que le traffic entre deux noeuds d'un même sous-réseau ne doit pas sortir de celui-ci. PLHA possède des applications dans le planning stratégique, ou déploiement, d'un certain protocole de communication utilisé dans l'Internet, Intermediate System - Intermediate System, ainsi que dans la distribution des frets. Premièrement, nous préesentons trois formulations linéaires en variables entières pour résoudre PLHA. Le partitionnement du graphe et la localisation des hubs sont modélisées de la même maniére dans les trois formulations. Ces formulations diffèrent les unes des autres dans la maniére dont l'acheminement du traffic est traité. Deuxièmement, nous présentons des comparaisons analytiques et empiriques des trois formulations. Notre comparaison analytique démontre que l'une des formulations est plus forte que les autres. Néanmoins, la comparaison empirique des formulations, via le solveur CPLEX, montre que la formulation la plus compacte (mais pas la plus forte) obtient les meilleures performances en termes de temps de résolution du problème. Ensuite, nous nous concentrons sur un sous-problème, à savoir, le partitionnement des graphes sous contrainte de taille. Nous étudions le polytope des solutions réalisables de ce sous-problème. Les facettes de ce polytope constituent des inégalités valides fortes pour PLHA et peuvent être utilisées dans un algorithme de branch-and-cut pour résoudre PLHA. Finalement, nous présentons les résultats d'un algorithme de branch-and-cut que nous avons développé pour résoudre PLHA. Les résultats démontrent que la performance de notre méthode est meilleure que celle de l'algorithme branch-and-cut d'Xpress.

Durant cette dernière décennie, la diffusion du format XML pour représenter les données générées par et échangées sur le Web a été accompagnée par la mise en œuvre de nombreux moteurs d'évaluation de requêtes et de mises à jour XQuery. Parmi ces moteurs, les systèmes " mémoire centrale " (Main-memory Systems) jouent un rôle très important dans de nombreuses applications. La gestion et l'intégration de ces systèmes dans des environnements de programmation sont très faciles. Cependant, ces systèmes ont des problèmes de passage à l'échelle puisqu'ils requièrent le chargement complet des documents en mémoire centrale avant traitement.Cette thèse présente une technique de partitionnement des documents XML qui permet aux moteurs " mémoire principale " d'évaluer des expressions XQuery (requêtes et mises à jour) pour des documents de très grandes tailles. Cette méthode de partitionnement s'applique à une classe de requêtes et mises à jour pertinentes et fréquentes, dites requêtes et mises à jour itératives.Cette thèse propose une technique d'analyse statique pour reconnaître les expressions " itératives ". Cette analyse statique est basée sur l'extraction de chemins à partir de l'expression XQuery, sans utilisation d'information supplémentaire sur le schéma. Des algorithmes sont spécifiés, utilisant les chemins extraits par l'étape précédente, pour partitionner les documents en entrée en plusieurs parties, de sorte que la requête ou la mise à jour peut être évaluée sur chaque partie séparément afin de calculer le résultat final par simple concaténation des résultats obtenus pour chaque partie. Ces algorithmes sont mis en œuvre en " streaming " et leur efficacité est validée expérimentalement.En plus, cette méthode de partitionnement est caractérisée également par le fait qu'elle peut être facilement implémentée en utilisant le paradigme MapReduce, permettant ainsi d'évaluer une requête ou une mise à jour en parallèle sur les données partitionnées.

Le long de l'orocline des Andes Centrales, sous l'avant-arc, la sismicité intracontinentale se connecte à la subduction en profondeur s'expliquant probablement par l'accumulation de contraintes générées dans la croûte par le glissement asismique de la zone de transition de l'interface de subduction en période inter-sismique. <br />Le long de l'orocline des Andes Centrales, sous la Précordillère et l'arc volcanique, la sismicité intracontinentale se distribue en essaims superficiels dont les plus grands séismes (Mw>5.0) ont lieu en général quelques mois après de grands séismes de subduction de magnitude Mw>7.5, déclenchés par le changement de contraintes dû à la période cosismique et probablement post-sismique.<br />L'analyse d'images et les observations de terrains interprétées conjointement avec les données sismologiques montrent que la déformation de l'orocline est partitionnée dans la Précordillère et l'arc volcanique le long d'une grande zone de cisaillement parallèle à la marge dont la cinématique varie de sénestre au Sud Pérou à dextre au Nord Chili. Le partitionnement observé est attribué à l'obliquité de la convergence et à l'architecture de l'avant-arc et de l'arc volcanique alors que les variations de la déformation le long de l'orocline sont principalement attribuées à la forme de la marge. <br />L'analyse sismologique, morphologique, et structurale de la déformation indique que le tenseur de contraintes le long de l'arc volcanique est caractérisé par un σ2 vertical et que σ1 et σ3 montrent une rotation anti-horaire depuis le Sud du Coude vers le Nord. En effet, σ1 s'oriente NE-SW au Nord du Chili, NW-SE à l'extrême Sud du Pérou et E-W au sud Pérou.

Face au volume croissant de données audio et multimédia, les technologies liées à l'indexation de données et à l'analyse de contenu ont suscité beaucoup d'intérêt dans la communauté scientifique. Parmi celles-ci, la segmentation et le regroupement en locuteurs, répondant ainsi à la question 'Qui parle quand ?' a émergé comme une technique de pointe dans la communauté de traitement de la parole. D'importants progrès ont été réalisés dans le domaine ces dernières années principalement menés par les évaluations internationales du NIST. Tout au long de ces évaluations, deux approches se sont démarquées : l'une est bottom-up et l'autre top-down. L'ensemble des systèmes les plus performants ces dernières années furent essentiellement des systèmes types bottom-up, cependant nous expliquons dans cette thèse que l'approche top-down comporte elle aussi certains avantages. En effet, dans un premier temps, nous montrons qu'après avoir introduit une nouvelle composante de purification des clusters dans l'approche top-down, nous obtenons des performances comparables à celles de l'approche bottom-up. De plus, en étudiant en détails les deux types d'approches nous montrons que celles-ci se comportent différemment face à la discrimination des locuteurs et la robustesse face à la composante lexicale. Ces différences sont alors exploitées au travers d'un nouveau système combinant les deux approches. Enfin, nous présentons une nouvelle technologie capable de limiter l'influence de la composante lexicale, source potentielle d'artefacts dans le regroupement et la segmentation en locuteurs. Notre nouvelle approche se nomme Phone Adaptive Training par analogie au Speaker Adaptive Training

Les problèmes combinatoires basés sur le partitionnement de graphe permettent de modéliser un grand nombre d'applications pratiques. On retiendra des exemples aussi variés que la reconstruction de " super-arbres " en phylogénie, la planification de missions, ou la construction de tournées de véhicules en logistique. Ces applications, bien que provenant de domaines différents, peuvent toutes se voir comme un problème de partitionnement de graphe par des patrons tels que des cycles, des chemins, ou des arbres. Cependant, les problèmes pratiques se résument rarement à des problèmes " pur " comme peuvent l'être le problème de chemin Hamiltonien ou le problème des K-chemins disjoints. En effet, ils combinent bien souvent le problème de partitionnement avec un ensemble de restrictions sur la topologie des sommets et des arcs. La diversité des contraintes opérationnelles misent en jeu constitue souvent une limite à leur résolution par des approches considérant de manière séparée le problème de partitionnement et les restrictions supplémentaires imposées. Cette thèse se concentre sur les problèmes de satisfaction de contraintes li !es au partitionnement de graphe par des arbres mettant en jeu un certain nombre de restrictions sur la topologie des partitions autorisées. Notre travail se focalise d'une part sur la compréhension des propriétés structurelles inhérentes aux contraintes de partitionnement par des arbres, et d'autre part sur l'étude des interactions existantes entre le problème de partitionnement et les restrictions classiques (telles que les relations de précédences ou d'incomparabilités entre les sommets du graphe à partitionner). Nous nous attachons plus particulièrement à montrer comment prendre en compte de manière globale un certain nombre de ces restrictions au sein d'une contrainte de partitionnement de graphes par des arbres. Un autre aspect essentiel porte sur la mise en œuvre d'une telle contrainte : nous montrons en quoi une gestion dynamique des structures de données permet de s'abstraire significativement d'un problème récurrent à la plupart des contraintes globales liées aux graphes : la sensibilité des algorithmes de graphes à la densité des graphes manipulés par la contrainte.

L'analyse de réseaux (représentés par des graphes) est une composante importante dans la compréhension de systèmes complexes issus de nombreuses disciplines telles que la biologie, la géographie ou la sociologie. Nous nous intéressons dans cette thèse aux décompositions de ces réseaux. Ces décompositions sont utiles pour la compression des données, la détection de communautés ou la visualisation de graphes. Une décomposition possible est un partitionnement hiérarchique des sommets du graphe. Nous traitons de l'évaluation de la qualité de telles structures (leur capacité à bien capturer la topologie du graphe) par le biais de mesures de qualité. Nous discutons ensuite l'utilisation de ces mesures en tant que fonctions objectives à maximiser dans le cadre d'algorithmes de partitionnement. Enfin, nous nous intéressons à la définition de métaphores visuelles efficaces permettant de représenter différentes décompositions de graphes.