La première partie de ce travail présente un état de l'art des principaux critères non supervisés, non paramétriques, d'évaluation d'une partition, des méthodes d'estimation préliminaires du nombre de classes, et enfin des méthodes de classification supervisées, semi-supervisées et non supervisées. Une analyse des avantages et des inconvénients de ces critères et méthodes est menée. L'analyse des performances des méthodes de classification et des critères d'évaluation a été également conduite via l'application visée dans cette thèse. Une approche de partitionnement non supervisée, non paramétrique et hiérarchique s'avère la plus adaptée au problème posé. En effet, ce type d'approche et plus particulièrement la classification descendante donne un partitionnement à plusieurs niveaux et met en évidence des informations plus détaillées d'un niveau à l'autre, ce qui permet une meilleure interprétation de la richesse d'information apportée par l'imagerie hyperspectrale et ainsi conduire à une meilleure décision. Dans ce sens, la deuxième partie de cette thèse présente, tout d'abord l'approche de classification descendante hiérarchique non supervisée (CDHNS) développée. Cette approche non paramétrique, permet l'obtention de résultats stables et objectifs indépendamment des utilisateurs finaux. Le second développement conduit, porte sur la sélection de bandes spectrales parmi celles qui composent l'image hyperspectrale originale afin de réduire la quantité d'information à traiter avant le processus de classification. Cette méthode est également non supervisée et non paramétrique. L'approche de classification et la méthode de réduction ont été expérimentées et validées sur une image hyperspectrale synthétique construite à partir des images réelles puis sur des images réelles dont l'application porte sur l'identification des différentes classes algales. Les résultats de partitionnement obtenus sans réduction montrent d'une part, la stabilité des résultats et, d'autre part, la discrimination des classes principales (végétation, substrat et eau) dès les premiers niveaux. Les résultats de la sélection des bandes spectrales font apparaître leur bonne répartition sur toute la gamme spectrale du capteur (visible et proche-infrarouge). Les résultats montrent aussi que le partitionnement avec et sans réduction sont globalement similaires. De plus, le temps de calcul est fortement réduit. / The upstream location of the different algal species causing clogging in the EDF nuclear power plants cooling systems along the Channel coastline, by analyzing hyperspectral aerial image is today the most appropriate means. Indeed, hyperspectral imaging allows, through its spatial resolution and its broad spectral range covering the areas of visible and near infrared, the objective discrimination of plant species on the foreshore, necessarily yielding accurate maps on large coastal areas. To provide a solution to this problem and achieve the objectives, the work conducted within the framework of this thesis lies in the development of unsupervised partitioning approaches to data with large spectral and spatial dimensions. The first part of this work presents a state of the art of main unsupervised criteria, and nonparametric, for partitioning evaluation, the preliminary methods for estimating the number of classes, and finally, supervised, semi-supervised and unsupervised classification methods. An analysis of the advantages and drawbacks of these methods and criteria is conducted. The analysis of the performances of these classification methods and evaluation criteria was also conducted through the application targeted in this thesis. An unsupervised, nonparametric, hierarchical partitioning approach appears best suited to the problem. Indeed, this type of approach, and particularly the descending classification, gives a partitioning at several levels and highlights more detailed information from one level to another, allowing a better interpretation of the wealth of information provided by hyperspectral imaging and therefore leading to a better decision. In this sense, the second part of this thesis presents, firstly the unsupervised hierarchical descending classification (UHDC) approach developed. This nonparametric approach allows obtaining stable and objective results regardless of end users. The second development proposed concerns the selection of spectral bands from those that make up the original hyperspectral image, in order to reduce the amount of information to be processed before the classification process. This method is also unsupervised and nonparametric. The classification approach and the reduction method have been tested and validated on a synthetic hyperspectral image constructed from real images, and then on real images, with application to the identification of different algal classes. The partitioning results obtained without reduction show firstly, the stability of the results and, secondly, the discrimination of the main classes (vegetation, substrate and water) from the first levels. The results of the spectral bands selection method show that the retained bands are well distributed over the entire spectral range of the sensor (visible and near-infrared). The results also show that partitioning results with and without reduction are broadly similar. Moreover, the computation time is greatly reduced.

Dans le contexte du calcul scientique, l'équilibrage de la charge est un problème crucial qui conditionne la performance des simulations numériques parallèles. L'objectif est de répartir la charge de travail entre un nombre de processeurs donné, afin de minimiser le temps global d'exécution. Une stratégie populaire pour résoudre ce problème consiste à modéliser la simulation à l'aide d'un graphe et à appliquer des algorithmes de partitionnement. En outre, les simulations numériques tendent à se complexifier, notamment en mixant plusieurs codes représentant des physiques différentes ou des échelles différentes. On parle alors de couplage de codes multi-physiques ou multi-échelles. Dans ce contexte, le problème de l'équilibrage de charge devient également plus difficile, car il ne s'agit plus d'équilibrer chacun des codes séparément, mais l'ensemble de ces codes pris dans leur globalité. Dans ce travail, on propose de resoudre ce problème en utilisant le modèle de partitionnement à sommets fixes qui pourrait représenter efficacement les contraintes supplémentaires imposées par les codes couplés (co-partitionnement). Nous avons donc développé un algorithme direct de partitionnement de graphe qui gère des sommets fixes. L'algorithme a été implémenté dans le partitionneur Scotch et une série d'expériences ont été menées sur la collection des graphes DIMACS. Ensuite nous avons proposé trois algorithmes de co-partitionnement qui respectent les contraintes issues des codes couplés respectifs. Nous avons egalement validé nos algorithmes par une étude expérimentale en comparant nos méthodes aux strategies actuelles sur des cas artificiels ainsi que sur des codes réels couplés. / Load balancing is an important step conditioning the performance of parallel applications. The goal is to distribute roughly equal amounts of computational load across a number of processors, while minimising interprocessor communication. A common approach to model the problem is based on graph structures and graph partitioning algorithms. Moreover, new challenges involve the simulation of more complex physical phenomena, where different parts of the computational domain exhibit different physical behavior. Such simulations follow the paradigm of multi-physics or multi-scale modeling approaches. Combining such different models in massively parallel computations is still a challenge to reach high performance. Additionally, traditional load balancing algorithms are often inadequate, and more sophisticated solutions should be explored. In this thesis, we propose new graph partitioning algorithms that balance the load of such simulations, refered to as co-partitioning. We formulate this problem with the use of graph partitioning with initially fixed vertices which we believe represents efficiently the additional constraints of coupled simulations. We have therefore developed a direct algorithm for graph partitioning that manages successfully problems with fixed vertices. The algorithm is implemented inside Scotch partitioner and a series of experiments were carried out on the DIMACS graph collection. Moreover we proposed three copartitioning algorithms that respect the constraints of the respective coupled codes. We finally validated our algorithms by an experimental study comparing our methods with current strategies on artificial cases and on real-life coupled simulations.

La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.

Cette thèse présente une étude structurale qualitative et quantitative du socle paléozoïque des Pyrénées. Elle se base sur une étude de terrain et une compilation exhaustive et inédite des structures, harmonisées à l'échelle de toute la chaîne des Pyrénées. A partir de cette base de données, nous avons construit le champ de déformation régional varisque produit au Paléozoïque supérieur (310-295 Ma). On montre que lors du raccourcissement régional majeur, la déformation est partitionnée entre une croûte supérieure s'épaississant en régime transpressif et une croûte inférieure fluant latéralement. Une zone d' " attachement " a permis de maintenir la cohérence cinématique entre ces deux domaines aux comportements structuraux contrastés. Le fluage latéral au sein de la croûte inférieure permet l'emplacement de dômes extensifs dans ce contexte convergent. Le refroidissement progressif de la croûte favorise i) le couplage mécanique progressif entre ces deux domaines et ii) une localisation de la déformation dans des zones de cisaillement transpressives verticales d'échelle crustale. Bien que situées dans l'avant-pays de la chaîne varisque, les Pyrénées enregistrent une déformation typique d'une lithosphère anormalement chaude. Ce contexte thermique est l'expression d'une délamination progressive du manteau lithosphérique initiée dans les zones internes de l'orogène et qui a permis la fermeture de la syntaxe ibéro-armoricaine ainsi que l'échappement latéral de la croûte ductile pyrénéenne pris dans cette syntaxe. L'analyse quantitative du champ de déformation à partir d'outils géostatistiques montre que ce champ résulte d'une déformation assimilable à un cisaillement pur produit par un raccourcissement NS tandis que la composante dextre de la transpression se concentre aux bordures de plutons ou de dômes. Ainsi, la mise en place de ces objets structuraux gouverne l'hétérogénéité du champ de déformation. La cohérence du champ de déformation varisque met en question l'existence de nappes de socle lors de la construction du prisme orogénique pyrénéen à partir du Crétacé supérieur. En dehors de la bordure ouest et sud de la Zone Axiale, le socle n'est affecté que par des réactivations mineures, y compris dans les Pyrénées centrales où le chevauchement de Nogueres ne peut être enraciné. Ce chevauchement correspondrait plutôt à un décollement dans les séries paléozoïques supérieures, impliquant des quantités de raccourcissement moindres durant la collision pyrénéenne que celles calculées précédemment. / We present a qualitative and quantitative structural study of the Paleozoic basement of the Pyrenees. Based on new observations and an extensive compilation of structural data that were harmonized at the scale of the orogen, we built the regional-scale Variscan strain field. The main Variscan deformation was partitioned between transpressional thickening of the upper crust and the laterally flowing lower crust. An attachment zone acted to maintain the kinematic coherency between these two structural domains. Lateral flow of the lower crust accompanied emplacement of syn-convergence extensional domes. Regional cooling progressively increases the degree of mechanical coupling between the two structural levels and enhanced strain localization in steep regional transpressive shear zones. Though part of the foreland of the Variscan orogen the Pyrenees developed strain patterns typical of hot crusts/lithospheres. Such a hot thermal context is due to lithospheric mantle delamination that initiated beneath the hinterland of the orogen and allowed the Iberian-Armorican syntax to close and extrude the soft Pyrenean crust trapped in it. Geostatistical analysis of the strain field suggests that it results bulk pure shear deformation with a dextral transpressional component restricted to the boundaries of plutons and domes. Emplacement of such structural objects governed the degree of heterogeneity of the strain field. The coherency of the strain field argues against the stacking of large basement nappes in the Axial Zone of the Pyrenees during building of the orogenic prism since the Late Cretaceous. Only the southern and western parts of the Axial Zone are affected by "Alpine" thrusting and only minor local reactivation occurred elsewhere in the Axial Zone. Therefore, the Nogueres thrust cannot root into the Axial Zone but is a decollement within Late Paleozoic series. This suggests a lower amount of Alpine shortening in this part of the Pyrenees than previously estimated.

L'efficacité des services de compression vidéo est de nos jours un enjeu essentiel, et est appelé à le devenir d'autant plus dans le futur, comme l'indique la croissance constante du trafic vidéo et la production de nouveaux formats tels que la vidéo à haute résolution, à gamme de couleur ou dynamique étendues, ou encore à fréquence d'images augmentée. Le standard MPEG HEVC est aujourd'hui un des schémas de compression les plus efficaces, toutefois, il devient nécessaire de proposer de nouvelles méthodes originales pour faire face aux nouveaux besoins de compression. En effet, les principes de bases des codecs modernes ont été conçu il y a plus de 30 ans : la réduction des redondances spatiales et temporelles du signal en utilisant des outils de prédiction, l'utilisation d'une transformée afin de diminuer d'avantage les corrélations du signal, une quantification afin de réduire l'information non perceptible, et enfin un codage entropique pour prendre en compte les redondances statistiques du signal. Dans cette thèse, nous explorons de nouvelles méthodes ayant pour but d'exploiter d'avantage les redondances du signal vidéo, notamment à travers des techniques multi-patchs. Dans un premier temps, nous présentons des méthodes multi-patchs basées LLE pour améliorer la prédiction Inter, qui sont ensuite combinées pour la prédiction Intra et Inter. Nous montrons leur efficacité comparé à H.264. La seconde contribution de cette thèse est un schéma d'amélioration en dehors de la boucle de codage, basé sur des méthodes de débruitage avec épitome. Des épitomes de bonne qualité sont transmis au décodeur en plus de la vidéo encodée, et nous pouvons alors utiliser coté décodeur des méthodes de débruitage multi-patchs qui s'appuient sur les patchs de bonne qualité contenu dans les épitomes, afin d'améliorer la qualité de la vidéo décodée. Nous montrons que le schéma est efficace en comparaison de SHVC. Enfin, nous proposons un autre schéma d'amélioration en dehors de la boucle de codage, qui s'appuie sur un partitionnement des patchs symétrique à l'encodeur et au décodeur. Coté encodeur, on peut alors apprendre des projections linéaires pour chaque partition entre les patchs codés/décodés et les patchs sources. Les projections linéaires sont alors envoyés au décodeur et appliquées aux patchs décodés afin d'en améliorer la qualité. Le schéma proposé est efficace comparé à HEVC, et prometteur pour des schémas scalables comme SHVC. / Efficient video compression is nowadays a critical issue, and is expected to be more and more crucial in the future, with the ever increasing video traffic and the production of new digital video formats with high resolution, wide color gamut, high dynamic range, or high frame rate. The MPEG standard HEVC is currently one of the most efficient video compression scheme, however, addressing the future needs calls for novel and disruptive methods. In fact, the main principles of modern video compression standards rely on concepts designed more than 30 years ago: the reduction of spatial and temporal redundancies, through prediction tools, the use of a transform to further reduce the inner correlations of the signal, followed by quantization to remove non-perceptive information, and entropy coding to remove the remaining statistical redundancies. In this thesis, we explore novel methods which aims at further exploiting the natural redundancies occurring in video signals, notably through the use of multi-patches techniques. First, we introduce LLE-based multi-patches methods in order to improve Inter prediction, which are then combined for both Intra and Inter predictions, and are proven efficient over H.264. We then propose epitome-based de-noising methods to improve the performances of existing codecs in a out-of-the-loop scheme. High quality epitomes are transmitted to the decoder in addition to the coded sequence, and we can then use at the decoder side multi-patches de-noising methods relying on the high quality patches from the epitomes, in order to improve the quality of the decoded sequence. This scheme is shown efficient compared to SHVC. Finally, we proposed another out-of-the-loop scheme relying on a symmetric clustering of the patches performed at both encoder and decoder sides. At the encoder side, linear mappings are learned for each cluster between the coded/decoded patches and the corresponding source patches. The linear mappings are then sent to the decoder and applied to the decoded patches in order to improve the quality of the decoded sequence. The proposed scheme improves the performances of HEVC, and is shown promising for scalable schemes such as SHVC.

Les problèmes de partitionnement de graphique sont une classe bien connue des problèmes d'optimisation combinatoire NP-difficiles avec un large éventail d'applications, telles que la conception de plans VLSI, la physique statistique, la planification d'une équipe sportive, la segmentation d'images et la structuration de protéines. En raison de la grande complexité de ces problèmes, les approches heuristiques et métaheuristiques sont couramment utilisées pour aborder les problèmes difficiles. Cette thèse considère trois problèmes représentatifs de cette famille, incluant le problème "max-k-cut", le problème "max-bisection" et le problème de séparation de sommets (VSP). Elle vise à élaborer des algorithmes heuristiques efficaces basés sur une ensemble d'opérateurs de recherche complémentaires. Plus précisément, nous développons une heuristique à opérateur multiple (MOH) pour "max-k-cut", un algorithme de recherche Tabu itérée (ITS) pour "max-bisection" et un algorithme "path relinking" (PR-VSP) pour VSP. Des résultats expérimentaux sur des jeux de test standard démontrent que les algorithmes proposés rivalisent favorablement avec les approches existantes de la littérature. L'utilisation combinée de plusieurs opérateurs de recherche est analysée afin de mettre en évidence l'influence de ces opérateurs sur la performance des algorithmes. / Graph partitioning problems are a class of well-known NP-hard combinatorial optimization problems with a wide range of applications, such as VLSI layout design, statistical physics, sports team scheduling, image segmentation, and protein conformation for instances. This thesis considers three representative problems in this family, including the max-k-cut problem, the max-bisection problem and the vertex separator problem (VSP). Due to high computational complexity, heuristic and metaheuristic approaches are commonly used for approximating the challenging problems. This thesis is devoted to developing efficient metaheuristic algorithms based on a collection of complementary search operators. Specifically, we develop a multiple operator heuristic (MOH) for max-k-cut, an iterated tabu search (ITS) algorithm for max-bisection and a path relinking (PR-VSP) algorithm for VSP. Extensive computational experiments and comparisons demonstrate that the proposed algorithms compete favorably with state-of-the-art approaches in the literature. The combined use of multiple search operators is analyzed to shed lights on the influence over the performance of the algorithms.

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. / In this thesis, we present approaches for adapting an alignment process to the characteristics of the aligned ontologies, whether in respect of the quantitative characteristics such as their volume or the particular characteristics related for example to the way in which the labels of the concepts are built.Concerning the quantitative characteristics, we propose two ontology partitioning methods that make the alignment of very large ontologies possible. Both methods generate in the input of the alignment process, subsets of reasonable size of the two ontologies to be aligned by taking into account, as soon as possible, the alignment objective in the partitioning process.Concerning the particular characteristics of the aligned ontologies, we present the TaxoMap Framework environment that allows the specification of refinement treatments from predefined primitives. We propose a pattern language MPL (the Mapping Pattern Language) that we use to specify the refinement treatments.In addition to the adaptation approaches to the characteristics of the aligned ontologies, we present approaches for re-using the alignment results for the ontological engineering. We focus specifically on the use of the alignment for the ontology enrichment. We study the contribution of the alignment techniques for the enrichment and the impact of the characteristics of the external resource used as a source of enrichment.Finally, we present how the TaxoMap Framework environment was implemented and the performed experiments: tests on the TaxoMap alignment module, on the mappings refinement approach, on the partitioning methods of very large ontologies and on the ontology enrichment approach.

Une séparation existe de longue date entre les domaines de la compilation et de l'ordonnancement temps-réel. Si ces deux domaines ont le même objectif - la construction d'implantations correctes - la séparation se justifie historiquement par des différences significatives entre les modèles et les méthodes utilisés. Cependant, avec la complexification des applications et du materiel qui les exécute, les problèmes étudiés dans ces deux domaines se confondent désormais largement. Dans cette thèse, nous nous concentrons sur la génération automatique de code pour des systèmes de contrôle embarqué incluant des contraintes complexes (notamment temps-réel). A ces fins, nous défendons l'idée qu'il est profitable de fournir un effort commun de recherche entre ces deux communautés. En adaptant une technique de compilation au problème d'ordonnancement temps réel d'applications sur des architectures multiprocessurs, nous montrons à la fois les difficultés inhérentes à cet effort commun, mais aussi les possibles avancées qu'il porte. En effet, nous montrons que l'adaptation de techniques d'optimisation à de nouveaux objectifs, dans un contexte différent facilite le développement de systèmes de meilleure qualité. Nous proposons d'utiliser les formalismes et langages synchrones comme base formelle commune dans ce travail d'adaptation. Ceux-cis étendent naturellement les modèles classiques utilisés pour l'ordonnancement temps réel (graphes de tâches dépendentes) et la compilation (SSA et graphes de dépendence de données), et fournissent également des techniques efficaces pour la manipulation de structures de contrôle complexes. Nous avons implanté nos résultats dans le compilateur LoPhT. / There is a long standing separation between the fields of compiler construction and real-time scheduling. While both fields have the same objective - the construction of correct implementations – the separation was historically justified by significant differences in the models and methods that were used. Nevertheless, with the ongoing complexification of applications and of the hardware of the execution platforms, the objects and problems studied in these two fields are now largely overlapping. In this thesis, we focus on the automatic code generation for embedded control systems with complex constraints, including hard real-time requirements. To this purpose, we advocate the need for a reconciled research effort between the communities of compilation and real-time systems. By adapting a technique usually used in compilers (software pipelining) to the system-level problem of multiprocessor scheduling of hard real-time applications, we shed light on the difficulties of this unified research effort, but also show how it can lead to real advances. Indeed we explain how adapting techniques for the optimization of new objectives, in a different context, allows us to develop more easily systems of better quality than what was done until now. In this adaptation process, we propose to use synchronous formalisms and languages as a common formal ground. These can be naturally seen as extensions of classical models coming from both real-time scheduling (dependent task graphs) and compilation (single static assignment and data dependency graphs), but also provide powerful techniques for manipulating complex control structures. We implemented our results in the LoPhT compiler.

Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]... / The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....

Dans cette thèse nous étudions un problème fondamental, le partitionnement de graphe, dans le contexte de la croissance rapide des données, le volume des données continues à augmenter, allant des réseaux sociaux à l'internet des objets. En particulier, afin de vaincre les propriétés intraitables existant dans de nombreuses graphies, par exemple, la distribution des degrés en loi de puissance, nous appliquons un nouveau mode pour coupe de sommet, à la place de la méthode traditionnelle (coupe de bord), ainsi que pour assurer une charge de travail équilibrée et raisonnablement dans le traitement de graphe distribué. En outre, pour réduire le coût de communication inter-partitions, nous proposons une méthode de partition de bord basée sur les blocs, qui peut explorer efficacement les structures graphiques sous-jacentes au niveau local. , afin d'optimiser l'exécution de l'algorithme de graphe. Par cette méthode, le temps d'exécution et des communications généraux peuvent être considérablement réduits par rapport aux approches existantes. Les challenges qui se posent dans les grands graphiques comprennent également leur grande variété. Comme nous le savons, la plupart des applications graphiques au monde réel produisent des ensembles de données hétérogènes, dans lesquels les sommets et / ou les arêtes peuvent avoir des différents types ou des différentes étiquettes. De nombreuses algorithmes de fouille de graphes sont également proposés avec beaucoup d'intérêt pour les attributs d'étiquette. Pour cette raison, notre travail est étendu aux graphes de multicouches en prenant en compte la proximité des arêtes et la distribution des étiquettes lors du processus de partitionnement. En fin de cette thèse, Nous démontré à la ses performances exceptionnelles sur les ensembles de données du monde réel. / In this thesis, we mainly focus on a fundamental problem, graph partitioning, in the context of unexpectedly fast growth of data sources, ranging from social networks to internet of things. Particularly, to conquer intractable properties existing in many graphs, e.g. power-law degree distribution, we apply the novel fashion vertex-cut, instead of the traditional edge-cut method, for achieving balanced workload in distributed graph processing. Besides, to reduce the inter-partition communication cost, we present a block-based edge partition method who can efficiently explore the locality underlying graphical structures, to enhance the execution of graph algorithm. With this method, the overhead of both communication and runtime can be decreased greatly, compared to existing approaches. The challenges arising in big graphs also include their high-variety. As we know, most of real life graph applications produce heterogenous datasets, in which the vertices and/or edges are allowed to have different types or labels. A big number of graph mining algorithms are also proposed with much concern for the label attributes. For this reason, our work is extended to multi-layer graphs with taking into account the edges closeness and labels distribution during partitioning process. Its outstanding performance over real-world datasets is demonstrated finally.