Les travaux présentés dans cette thèse portent sur l'exécution d'applications sur les environ- nements hétérogènes et distribués que sont les grilles de calcul. Nous étudions de bout en bout le processus permettant à des utilisateurs d'exécuter des applications scientifiques complexes. Les contributions de cette thèse se situent donc à plusieurs niveaux. 1) Déploiement d'inter- giciel hiérarchique : nous proposons dans un premier temps un modèle d'exécution pour les intergiciels hiérarchiques. À partir de ce modèle, nous présentons plusieurs heuristiques pour définir automatiquement la meilleure hiérarchie en fonction des exigences des utilisateurs et du type de plate-forme. Nous évaluons la qualité de ces heuristiques en conditions réelles avec l'intergiciel Diet. 2) Partitionnement de graphe : nous proposons un algorithme distribué et auto-stabilisant pour partitionner un graphe quelconque ayant des arêtes pondérées entre les nœuds. Le partitionnement est réalisé en fonction des distances pondérées entre les nœuds et forme des grappes au sein desquelles les nœuds sont à une distance maximale k d'un nœud élu dans la grappe. 3) Ordonnancement : nous étudions l'ordonnancement de tâches indépen- dantes sous des contraintes de limitation d'utilisation des ressources. Nous définissons des formulations en programme linéaire pour résoudre ce problème dans deux cas : lorsque les tâches arrivent toutes en même temps et lorsqu'elles ont des dates d'arrivée. 4) Simulations cosmologiques : nous avons étudié le comportement d'applications nécessaires à l'exécution de workflows de simulations cosmologiques. Puis, en se basant sur l'intergiciel de grille Diet, nous avons mis en place une infrastructure complète permettant à des utilisateurs non expérimentés de soumettre facilement des simulations cosmologiques sur une grille de calcul.

Classiquement deux approches sont utilisées pour simuler les systèmes électroniques de puissance. La première, dite à topologie fixe, assimile les semi-conducteurs à des impédances de faible ou forte valeur en fonction de leur état. Les équations topologiques du système restent ainsi inchangées. Malgré sa simplicité, cette approche pose de sérieux problèmes de compromis entre précision des résultats et stabilité des méthodes numériques d'intégration. La deuxième, dite à topologie variable, assimile les semi-conducteurs à des connexions qui s'établissent ou disparaissent en fonction de l'état des semi-conducteurs. Il n'y a plus de problèmes de stabilité d'intégration ou de précision mais les équations topologiques du système sont dépendantes de l'état des interrupteurs. La détermination des conditions de transition (commutations) et la ré-écriture des équations sont des points délicats. Dans ce travail nous proposons une nouvelle approche, dite à topologie pseudo-variable qui combine les avantages des approches classiques sans en avoir les inconvénients. Les semi-conducteurs sont traités comme des dipôles comme dans les méthodes à topologie fixe, mais en fonction de leur état ils sont assimilés à des sources, de tension ou de courant, de valeur nulle ce qui leur donne une caractéristique idéale, comme dans les méthodes à topologie variable. La principale difficulté de cette nouvelle approche réside dans les contraintes algébriques, variables en fonction du temps, que les sources qui représentent les semi-conducteurs introduisent sur les variables d'état du circuit. Pour cette raison elle n'a, à notre connaissance, jamais été proposée. En adaptant au cas que nous traitons les techniques de partitionnement des coordonnées utilisées en mécanique de systèmes multicorps, nous montrons que ces contraintes peuvent être facilement prises en compte. Nous aboutissons ainsi à un algorithme de simulation à la fois très performant et bien adapté à la simulation des systèmes électromécaniques.

Les circuits FPGAs (Field Programmable Gate Arrays) sont devenus des acteurs importants dans le domaine du traitement numérique qui a été dominé auparavant par les microprocesseurs et les circuits intégrés spéci ques. Le plus grand dé pour les FPGAs aujourd'hui est de présenter un bon compromis entre une grande souplesse et de bonnes performances (vitesse, surface et consommation). La combinaison de trois facteurs dé nit les caractéristiques d'un circuit FPGA: la qualité de l'architecture, la qualité des outils CAO de con guration et la conception électrique du FPGA. L'objet de cette thèse est l'exploration de nouvelles architectures et de structures d'interconnexion qui pourront améliorer les performances de ces circuits. En effet, les ressources d'interconnexion occupent 90% de la surface totale et occasionnent 60% de la consommation électrique. Les architectures étudiées présentent des structures matricielles et arborescentes. Les principaux résultats sont les suivants: Au départ nous explorons différentes topologies arborescentes et nous comparons leurs surfaces à celles des architectures matricielles. Pour cela, nous développons une plateforme d'outils logiciels permettant d'implanter différents circuits logiques sur l'architecture cible. En se basant sur cette étude expérimentale, nous dé nissons une nouvelle architecture arborescente. Nous montrons, en nous appuyant sur un modèle d'estimation de surface, que cette architecture permet de réduire la surface totale de 56% par rapport à une architecture matricielle. Ceci est dû essentiellement à une meilleure utilisation des ressources d'interconnexion. Nous explorons les effets des différents paramètres de l'architecture proposée: le coef cient de Rent, la taille des groupes logiques et le nombre d'entrées par bloc logique. Ceci permet de régler l'architecture pour l'adapter à des domaines d'applications qui ont des contraintes spéci ques en terme de surface, vitesse et consommation. En n, nous proposons une architecture qui rassemble les avantages des structures arborescentes et matricielles. Nous uni ons les deux structures en construisant des groupes de blocs logiques qui ont localement un réseau d'interconnexion arborescent et qui sont connectés entre eux via un réseau matriciel. Nous montrons que l'architecture obtenue présente un bon compromis entre l'évolutivité de la vue physique et la densité de la surface.

Ce travail de thèse s'inscrit dans le domaine de la recherche de structures dans un graphe. <br />On étudie certaines propriétés algorithmiques et combinatoires pour successivement trois types de colorations : orientée, mixte et décomposition acircuitique. <br />Pour la coloration orientée, on obtient des résultats de NP-complétude pour des classes de graphes très spécifiques ainsi que des résultats d'inapproximabilité. Pour dépasser ces difficultés, nous définissons une notion de coloration mixte et obtenons un résultat d'approximation différentielle ainsi qu'une interprétation du polynôme chromatique mixte qui généralise le résultat de Stanley pour certains graphes mixtes. En relachant la contrainte de classe monochromatique stable, nous étudions finalement la complexité de la décomposition acircuitique, caractérisons une famille de tournoi critique indécomposable et établissons les premières propriétés du polynôme chromatique acircuitique.

Dans cette thèse, nous avons adapté trois versions d'une chaine d'algorithmes de reconnaissance biométrique par l'iris appelés OSIRIS V2, V3, V4 qui correspondent à différentes implémentations de l'approche de J. Daugman pour les besoins d'une implémentation logicielle / matérielle. Les résultats expérimentaux sur la base de données ICE2005 montrent que OSIRIS_V4 est le système le plus fiable alors qu'OSIRIS_V2 est le plus rapide. Nous avons proposé une mesure de qualité de l'image segmentée pour optimiser en terme de compromis coût / performance un système de référence basé sur OSIRIS V2 et V4. Nous nous sommes ensuite intéressés à l'implémentation de ces algorithmes sur des plateformes reconfigurables. Les résultats expérimentaux montrent que l'implémentation matériel / logiciel est plus rapide que l'implémentation purement logicielle. Nous proposons aussi une nouvelle méthode pour le partitionnement matériel / logiciel de l'application. Nous avons utilisé la programmation linéaire pour trouver la partition optimale pour les différentes tâches prenant en compte les trois contraintes : la surface occupée, le temps d'exécution et la consommation d'énergie

Dans ce mémoire de thèse, nous nous intéressons à l'affectation des vols aux avions dans une compagnie aérienne. Notre objectif est de proposer des plannings de vols qui prennent en compte des contraintes de maintenance, en utilisant des algorithmes efficaces. Au cours de nos recherches, nous avons ramené le problème de rotation des avions à des cas particuliers du problème de partitionnement d'un graphe orienté acyclique par des chemins disjoints. Nous avons fait des études de complexité pour différents cas et nous avons proposé des algorithmes de liste, un recuit simulé et une approche heuristique basée sur la génération de colonnes. Nous avons finalement comparé la performance de ces méthodes sur différentes instances.

Dans cette thèse, nous présentons des approches d'adaptation d'un processus d'alignement aux caractéristiques des ontologies alignées, qu'il s'agisse de caractéristiques quantitatives telles que leur volume ou de caractéristiques particulières liées par exemple à la façon dont les labels des concepts sont construits. Concernant les caractéristiques quantitatives, nous proposons deux méthodes de partitionnement d'ontologies qui permettent l'alignement des ontologies très volumineuses. Ces deux méthodes génèrent, en entrée du processus d'alignement, des sous ensembles de taille raisonnable des deux ontologies à aligner en prenant en compte dès le départ l'objectif d'alignement dans le processus de partitionnement.Concernant les caractéristiques particulières des ontologies alignées, nous présentons l'environnement TaxoMap Framework qui permet la spécification de traitements de raffinement à partir de primitives prédéfinies. Nous proposons un langage de patrons MPL (the Mapping Pattern Language) que nous utilisons pour spécifier les traitements de raffinement.En plus des approches d'adaptation aux caractéristiques des ontologies alignées, nous présentons des approches de réutilisation des résultats d'alignement pour l'ingénierie ontologique. Nous nous focalisons plus particulièrement sur l'utilisation de l'alignement pour l'enrichissement d'ontologies. Nous étudions l'apport des techniques d'alignement pour l'enrichissement et l'impact des caractéristiques de la ressource externe utilisée comme source d'enrichissement. Enfin, nous présentons la façon dont l'environnement TaxoMap Framework a été implémenté et les expérimentations réalisées : des tests sur le module d'alignement TaxoMap, sur l'approche de raffinement de mappings, sur les méthodes de partitionnement d'ontologies de très grande taille et sur l'approche d'enrichissement d'ontologies.

Ce mémoire traite de la compression des images fixes par fractales, fondée sur la théorie des systèmes de fonctions itérées (IFS). Après quelques rappels sur les principales méthodes de codage entropique et de compression réversible et irréversible des images nous introduisons les notions nécessaires à la compréhension de la théorie des IFS. Nous détaillons ensuite les principaux algorithmes de compression des images naturelles selon l'approche fractale. Ces derniers consistent à approximer chacun des éléments d'une partition à l'aide d'une transformation locale contractante appliquée sur une autre partie de l'image. Ceci nous conduit à présenter les modèles de partitionnement utilisés pour coder les similarités locales des images. La partie suivante constitue la contribution majeure du travail. Nous présentons un algorithme de codage par fractales fondé sur la triangulation de Delaunay. La souplesse de ce modèle nous permet d'utiliser diverses triangulations adaptées au contenu de l'image à compresser. Nous proposons ensuite différentes solutions ayant pour but d'améliorer le schéma de codage-decodage. La premiere vise à réduire la complexité de la phase de codage en diminuant le nombre de comparaisons inter-blocs, par un algorithme de quantification vectorielle de l'espace de recherche. La seconde vise à réduire le nombre de blocs traités tout en améliorant les résultats visuels, pour des taux de compression élevés. Ceci est fait en introduisant des quadrilatères dans la triangulation de l'image. Nous concluons le mémoire en commentant différents résultats de décompression obtenus à partir des partitionnements étudiés, puis comparons ces résultats à ceux obtenus à partir de méthodes hybrides liant le codage par fractales à une décomposition multirésolution de l'image ou à la transformée en cosinus discrète.

Les architectures reconfigurables à base de FPGA sont capables de fournir des solutions adéquates pour plusieurs applications vu qu'elles permettent de modifier le comportement d'une partie du FPGA pendant que le reste du circuit continue de s'exécuter normalement. Ces architectures, malgré leurs progrès, souffrent encore de leur manque d'adaptabilité face à des applications constituées de tâches matérielles de taille différente. Cette hétérogénéité peut entraîner de mauvais placements conduisant à une utilisation sous-optimale des ressources et par conséquent une diminution des performances du système. La contribution de cette thèse porte sur la problématique du placement des tâches matérielles de tailles différentes et de la génération efficace des régions reconfigurables. Une méthodologie et une couche intermédiaire entre le FPGA et l'application sont proposées pour permettre le placement efficace des tâches matérielles de tailles différentes sur des partitions reconfigurables de taille prédéfinie. Pour valider la méthode, on propose une architecture basée sur l'utilisation de la reconfiguration partielle afin d'adapter le transcodage d'un format de compression vidéo à un autre de manière souple et efficace. Une étude sur le partitionnement de la région reconfigurable pour les tâches matérielles de l'encodeur entropique (CAVLC / VLC) est proposée afin de montrer l'apport du partitionnement. Puis une évaluation du gain obtenu et du surcoût de la méthode est présentée.

Je me focalise sur trois grands systèmes de failles transformantes obliques au Tibet et en Californie du Sud, et ce, afin de mieux comprendre et quantifier les relations entre les différentes structures qui les définissent. L'interférométrie radar à Synthèse d'Ouverture (InSAR) dispose du potentiel pour cartographier et localiser précisément la déformation sur des zones étendues et ainsi contraindre la géométrie des structures profondes. Cependant son utilisation en milieu naturel se trouve fortement entravée par la décorrelation due à la végétation, au relief, et aux cycles de gel et dégel, mais aussi par les délais troposphériques et les rampes orbitales résiduelles. J'ai développé des méthodes pour palier ces limitations. Au Tibet, j'ai ainsi traité les archives du satellite Envisat au niveau de deux zones de lacune sismique, à la bordure Nord du plateau, se présentant comme des zones intéressantes pour étudier le partitionnement de la convergence: le système de faille de Haiyuan au north-est Tibet et la faille sénestre de l'Altyn Tagh, au nord-ouest du plateau. Une attention spécifique sur les déformations liées au pergélisol m'a permis de (1) retrouver la continuité du signal sur de grandes zones, (2) de quantifier le comportement temporel des cycles de gel et dégel des sédiments recouvrant le pergélisol, (3) d'isoler les zones stables des sédiments se déformant. Je montre que les déformations saisonnières sont fortement dépendantes des unités géomorphologiques et que la fonte du pergélisol est plus important à faible qu'à haute altitude. J'analyse aussi le signal saisonnier au travers la marche topographique et je définie un proxy pour les incertitudes de la correction atmosphérique. J'observe un gradient de déformation au travers la faille de l'Altyn Tagh de l'ordre de 11-15 mm/an et un alignement claire de la déformation dans le Tarim, parallèle à la faille de l'Altyn Tagh, ainsi que des soulèvements de l'ordre de 1 mm/an associés à des chevauchements. Ce travail montre aussi un gradient de déformation associé à la terminaison ouest de la faille du Kunlun, re-définissant ainsi la géométrie des blocs tectoniques dans cette région. Parallèlement à cette acquisition de données, je développe des outils d'inversion basés sur des algorithmes de Monte Carlo afin d'explorer l'ensemble des géométries en accord avec les observations et d'estimer la compatibilité de la déformation actuelle avec des modèles tectoniques long-termes. Je montre ainsi une convergence uniforme de 8.5-11.5 mm/an et d'orientation N81-98E à travers le système de faille d'Haiyuan et quantifie son partitionnement le long des différentes structures. Par ailleurs, j'applique mon approche en Californie du Sud, au niveau du « Big Bend » de la faille de San Andreas où, en analogie avec des modèles structuraux géologiques, j'utilise des lois de conservations du mouvement pour contraindre la géométrie des chevauchements aveugles. Je montre la compatibilité du champs de déformation actuel avec un décollement grande échelle et quantifie une accumulation de contrainte de 2.5 mm/an le long de la structure majeure sous Los Angeles. / I focus on three major oblique transform faults in Tibet and in Southern California, in order to better measure and quantify the present-day strain accumulation on these structures. Interferometric synthetic Aperture Radar (InSAR) has the potential to map and localize precisely the deformation over wide areas and thus constrain the deep geometry of these structures. However, its application in natural environments in hindered by strong decorrelation of the radar phase due to vegetation, relief, and freeze and thaw cycles, but also due to variable tropospheric phase delays across topographic feature and long-wavelength residual orbital ramps. Here, I develop methodologies to circumvent these limitations and separate tectonic from other parasite signals. In Tibet, I process data from the Envisat satellite archives, at the boundary of the Tibetan plateau, in two seismic gaps, which appear interesting to study the partitioning of the convergence: the Haiyuan Fault system in northeastern Tibet and the left-lateral Altyn Tagh Fault, in northwestern Tibet. A specific focus on the permafrost related deformation signal allows us to: (1) correctly unwrap interferograms from north to south, (2) quantify the temporal behavior of the freeze/thaw cycles, and (3) isolate bedrock pixels that are not affected by the permafrost signal for further tectonic analysis. I show that the seasonal subsidence depends greatly on the geological land unit and that lower elevations are thawing faster than higher elevations. I analyze the atmospheric signal across the high plateau margin and estimate proxy for the uncertainty on atmospheric corrections. I observe a strike-slip deformation of around 11-15 mm/yr across the Altyn Tagh fault, a clear line of concentrated strike-slip deformation of around 3 mm/yr within the Tarim basin, trending parallel to the Altyn Tagh Fault trace, as well as thrust signal uplifting terraces at a rate of 1 mm/yr. This work also shows a strain accumulation around the west extension of the south trace of the Kunlun Fault, redefining the block boundaries in northwestern Tibet. In parallel this data acquisition, I develop Monte Carlo inversion tools in order to explore the various geometries in agreement with observations and estimate the compatibility of actual surface displacements with long-term slip partitioning models. I thus show a uniform convergence rate of 8.5-11.5 mm/yr with a N81-98E across the Haiyuan fault system and quantify the partitioning along the various structures. I also apply my approach in Southern California, across the « Big Bend » of the San Andreas Fault, where, in analogy with structural geological models, I use conservation of motion to help constraining the geometry and the kinematics of blind thrust faults. I show the compatibility of surface displacements with a large-scale décollement and quantify a loading rate of 2.5 mm/yr along the major thrust structure developing under Los Angeles.