.

Dans cette thèse, nous présentons notre travail de recherche dans le domaine du calcul haute performance en mécanique des fluides (CFD) pour architectures de type cluster et cloud. De manière générale, nous nous proposons de développer un solveur efficace, appelé ADAPT, pour la résolution de problèmes de CFD selon une vue classique correspondant à des développements en MPI et selon une vue qui nous amène à représenter ADAPT comme un graphe de tâches destinées à être ordonnancées sur une plateforme de type cloud computing. Comme première contribution, nous proposons une parallélisation de l’équation de diffusion-convection couplée àun système linéaire en 2D et en 3D à l’aide de MPI. Une parallélisation à deux niveaux est utilisée dans notre implémentation pour exploiter au mieux les capacités des machines multi-coeurs. Nous obtenons une distribution équilibrée de la charge de calcul en utilisant la décomposition du domaine à l’aide de METIS, ainsi qu’une résolution pertinente de notre système linéaire creux de très grande taille en utilisant le solveur parallèle MUMPS (Solveur MUltifrontal Massivement Parallèle). Notre deuxième contribution illustre comment imaginer la plateforme ADAPT, telle que représentée dans la premièrecontribution, comme un service. Nous transformons le framework ADAPT (en fait, une partie du framework)en DAG (Direct Acyclic Graph) pour le voir comme un workflow scientifique. Ensuite, nous introduisons de nouvelles politiques à l’intérieur du moteur de workflow RedisDG, afin de planifier les tâches du DAG, de manière opportuniste.Nous introduisons dans RedisDG la possibilité de travailler avec des machines dynamiques (elles peuvent quitter ou entrer dans le système de calcul comme elles veulent) et une approche multi-critères pour décider de la “meilleure”machine à choisir afin d’exécuter une tâche. Des expériences sont menées sur le workflow ADAPT pour illustrer l’efficacité de l’ordonnancement et des décisions d’ordonnancement dans le nouveau RedisDG. / In this thesis, we present our research work in the field of high performance computing in fluid mechanics (CFD) for cluster and cloud architectures. In general, we propose to develop an efficient solver, called ADAPT, for problemsolving of CFDs in a classic view corresponding to developments in MPI and in a view that leads us to represent ADAPT as a graph of tasks intended to be ordered on a cloud computing platform. As a first contribution, we propose a parallelization of the diffusion-convection equation coupled to a linear systemin 2D and 3D using MPI. A two-level parallelization is used in our a implementation to take advantage of thecurrent distributed multicore machines. A balanced distribution of the computational load is obtained by using the decomposition of the domain using METIS, as well as a relevant resolution of our very large linear system using the parallel solver MUMPS (Massive Parallel MUltifrontal Solver). Our second contribution illustrates how to imagine the ADAPT framework, as depicted in the first contribution, as a Service. We transform the framework (in fact, a part of the framework) as a DAG (Direct Acyclic Graph) in order to see it as a scientific workflow. Then we introduce new policies inside the RedisDG workflow engine, in order to schedule tasks of the DAG, in an opportunistic manner. We introduce into RedisDG the possibility to work with dynamic workers (they can leave or enter into the computing system as they want) and a multi-criteria approach to decide on the “best” worker to choose to execute a task. Experiments are conducted on the ADAPT workflow to exemplify howfine is the scheduling and the scheduling decisions into the new RedisDG.

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. / Network analysis is an important step in the understanding of complex systems studied in various areas such as biology, geography or sociology. This thesis focuses on the problems related to the decomposition of those networks when they are modeled by graphs. Graph decomposition methods are useful for data compression, community detection or network visualisation. One possible decomposition is a hierarchical partition of the set of vertices. We propose a method to evaluate the quality of such structures using quality measures and algorithms to maximise those measures. We also discuss the design of effective visual metaphors to represent various graph decompositions.

.

La présence de défauts sur les surfaces des failles tectoniques peut modifier le comportement de la rupture sur ces interfaces. Cependant, le rôle de ces hétérogénéités reste difficile à quantifier du fait de la résolution limitée de l’imagerie des failles en profondeur. Une approche analogique permettant de préciser l’impact des hétérogénéités dans la propagation de la fracture est présentée ici. Cette analyse repose, tout d’abord, sur l’utilisation d’un montage expérimental assurant le suivi de la propagation d’une fracture sous contrainte de traction normale au plan de rupture (mode I). Le dispositif utilisé, mettant en jeu un suivi acoustique et optique de l’avancée du front de fracture, nous amène à déterminer l’impact des aspérités sur le partitionnement de l’énergie entre processus sismiques et asismiques. Nous faisons le lien entre efficacité de radiation et vitesse de rupture, localement perturbée par la présence de microstructures le long de l’interface. Afin d’étendre nos résultats à d’autres modes de rupture, plus fréquemment observés lors de ruptures le long de failles tectoniques, nous nous intéressons à l’adaptation de notre montage expérimental pour l’observation d’une fracture se propageant en mode de cisaillement (mode III). L’analyse des propriétés morphologiques et dynamiques de l’avancée d’un front de rupture en mode III révèle des résultats semblables à ceux obtenus en mode I. Cela suggère que les résultats obtenus en mode I peuvent être étendus aux autres modes de ruptures. / The presence of defaults on the surface of tectonic faults can affect the behaviour of the rupture along those interfaces. However, because of the limited resolution of the faults imaging at depth, the implication of these heterogeneities remains hard to quantify. We present here an analogic approach enabling the precision of the impact of the heterogeneities on the fracture propagation. On one hand, this analysis lays on the use of an experimental setup ensuring the monitoring of a fracture propagating under an imposed stress, normal to the rupture interface (mode I). The used model, implying an acoustic and an optical monitoring of the fracture front advance, leads us to the determination of the impact of asperities on the energy partitioning between seismic and aseismic processes. We make the link between radiation efficiency and rupture velocity, locally affected by the presence of microstructures along the interface. On another hand, to extend our results to other rupture modes, which are observed more often during rupture on tectonic faults, we get interested in the adaptation of our experimental setup for the observation of a fracture propagating under shear stress (mode III). The analysis of morphologic and dynamic properties of the mode III crack advance shows results similar to those obtained for mode I. This suggests eventually that the results observed in mode I can be extended to other rupture modes.

Au cours des dernières années, le volume des données qui sont capturées et générées a explosé. Les progrès des technologies informatiques, qui fournissent du stockage à bas prix et une très forte puissance de calcul, ont permis aux organisations d'exécuter des analyses complexes de leurs données et d'en extraire des connaissances précieuses. Cette tendance a été très importante non seulement pour l'industrie, mais a également pour la science, où les meilleures instruments et les simulations les plus complexes ont besoin d'une gestion efficace des quantités énormes de données.Le parallélisme est une technique fondamentale dans la gestion de données extrêmement volumineuses car il tire parti de l'utilisation simultanée de plusieurs ressources informatiques. Pour profiter du calcul parallèle, nous avons besoin de techniques de partitionnement de données efficaces, qui sont en charge de la division de l'ensemble des données en plusieurs partitions et leur attribution aux nœuds de calculs. Le partitionnement de données est un problème complexe, car il doit prendre en compte des questions différentes et souvent contradictoires telles que la localité des données, la répartition de charge et la maximisation du parallélisme.Dans cette thèse, nous étudions le problème de partitionnement de données, en particulier dans les bases de données parallèles scientifiques qui sont continuellement en croissance. Nous étudions également ces partitionnements dans le cadre MapReduce.Dans le premier cas, nous considérons le partitionnement de très grandes bases de données dans lesquelles des nouveaux éléments sont ajoutés en permanence, avec pour exemple une application aux données astronomiques. Les approches existantes sont limitées à cause de la complexité de la charge de travail et l'ajout en continu de nouvelles données limitent l'utilisation d'approches traditionnelles. Nous proposons deux algorithmes de partitionnement dynamique qui attribuent les nouvelles données aux partitions en utilisant une technique basée sur l'affinité. Nos algorithmes permettent d'obtenir de très bons partitionnements des données en un temps d'exécution réduit comparé aux approches traditionnelles.Nous étudions également comment améliorer la performance du framework MapReduce en utilisant des techniques de partitionnement de données. En particulier, nous sommes intéressés par le partitionnement efficient de données d'entrée / During the last years, the volume of data that is captured and generated has exploded. Advances in computer technologies, which provide cheap storage and increased computing capabilities, have allowed organizations to perform complex analysis on this data and to extract valuable knowledge from it. This trend has been very important not only for industry, but has also had a significant impact on science, where enhanced instruments and more complex simulations call for an efficient management of huge quantities of data.Parallel computing is a fundamental technique in the management of large quantities of data as it leverages on the concurrent utilization of multiple computing resources. To take advantage of parallel computing, we need efficient data partitioning techniques which are in charge of dividing the whole data and assigning the partitions to the processing nodes. Data partitioning is a complex problem, as it has to consider different and often contradicting issues, such as data locality, load balancing and maximizing parallelism.In this thesis, we study the problem of data partitioning, particularly in scientific parallel databases that are continuously growing and in the MapReduce framework.In the case of scientific databases, we consider data partitioning in very large databases in which new data is appended continuously to the database, e.g. astronomical applications. Existing approaches are limited since the complexity of the workload and continuous appends restrict the applicability of traditional approaches. We propose two partitioning algorithms that dynamically partition new data elements by a technique based on data affinity. Our algorithms enable us to obtain very good data partitions in a low execution time compared to traditional approaches.We also study how to improve the performance of MapReduce framework using data partitioning techniques. In particular, we are interested in efficient data partitioning of the input datasets to reduce the amount of data that has to be transferred in the shuffle phase. We design and implement a strategy which, by capturing the relationships between input tuples and intermediate keys, obtains an efficient partitioning that can be used to reduce significantly the MapReduce's communication overhead.

Les systèmes hybrides sont des systèmes qui combinent des composantes discrètes et des composantes continues. Les composantes continues peuvent représenter un environnement physique obéissant à des règles de changement continu, par contre les composantes discrètes peuvent représenter des contrôleurs discrets qui sondent et manipulent les composantes continues en temps réel. Deux approches peuvent être adoptées pour spécifier ces systèmes, la première étant basée sur des automates (hybrides) et utilise des méthodes d'analyse algorithmiques. La seconde est basée sur les logiques et utilise des preuves formelles comme méthodes d'analyse. Dans une première partie de cette thèse nous considérons l'approche basée sur les automates. Nous étudions la décidabilité du problème de la vérification pour certaines classes de systèmes hybrides linéaires. Nous prenons comme modèles des automates hybrides linéaires avec des structures de données discrètes non bornées. Nous exhibons différents cas de tels systèmes dont le problème de la vérification est décidable. Dans une seconde partie nous considérons l'approche basée sur les logiques et plus particulièrement celle basée sur le «Calcul de Durées». Nous étudions les relations existantes entre cette approche et la précédente ; nous montrons comment cette liaison permet de mettre en évidence un fragment important du «Calcul de Durées» pour lequel le problème de la vérification est décidable

On élabore des politiques de test d'un grand système logique. On s'intéresse à la possibilité de partitionner un réseau à tester en plusieurs sous-réseaux. On introduit des paramètres de test que l'on utilise pour modéliser les problèmes de test sous forme de problèmes mathématiques de prise de décision.

Notre étude porte sur les transporteurs ABC dans les génomes bactériens complets. L'analyse bioinformatique du répertoire de ces systèmes comprend l'identification des partenaires, l'assemblage, la reconstruction des systèmes incomplets, la classification en sous-familles, et l'identification du substrat transporté. Cette thèse propose des outils permettant l'étude de ces problèmes par l'utilisation de méthodes informatiques. Les hypothèses biologiques employées sont que : (i) des gènes voisins sur le chromosome peuvent être impliqués dans un même processus métabolique s'ils ont été conservés au cours de l'évolution, et (ii) des gènes présentant des similarités de séquence peuvent permettre la synthèse de protéines de même fonction. Trois études ont été menées sur le répertoire des transporteurs ABC : * L'exploration du voisinage chromosomique. D'après l'hypothèse selon laquelle plus les gènes conservés dans le voisinage d'un transporteur sont proches, plus leur lien fonctionnel avec le transporteur est fort, on essaye d'identifier le substrat transporté ou des associations de gènes. Ce problème est traité par une méthode de résolution issue des problèmes de satisfaction de contraintes. * La classification. Les transporteurs ABC sont classés par grandes catégories en fonction des molécules qu'ils transportent (sucres, ...). Pour chaque domaine, en représentant les relations d'homologie par un graphe, la recherche des zones de forte densité permet de déterminer des sous-classes de substrat. * La reconstitution des systèmes incomplets. Les transporteurs ABC sont assemblés en utilisant la proximité chromosomique des gènes codant pour les domaines et la compatibilité des sous-familles de domaines. Lorsque la proximité n'est pas respectée, on utilise une stratégie développée à partir d'une méthode d'analyse de graphes pour assembler les domaines et prédire des systèmes actifs. Ces méthodes, en complément de l'identification des partenaires et de l'assemblage, permettent une étude fonctionnelle des transporteurs ABC. Elles pourraient être appliquées à d'autres systèmes biologiques.

Récemment le domaine du traitement de l'image, de la vidéo, et l'audio a connu plusieurs évolutions importantes au niveau des algorithmes et des architectures. L'une de ces évolutions est l'apparition du nouveau standard ISO/IEC de compression d'image JPEG2000 qui succède à JPEG. Ce nouveau standard présente de nombreuses fonctionnalités et caractéristiques qui lui permettent d'être adapté à une large panoplie d'applications. Mais ces caractéristiques se sont accompagnées d'une complexité algorithmique beaucoup plus élevée que JPEG et qui le rend très difficile à optimiser pour certaines implémentations ayant des contraintes très sévères en terme de surface, de temps d'exécution ou de consommation d'énergie ou de l'ensemble de ces contraintes. L'une des étapes clé dans le processus de compression JPEG2000 est le codeur entropique qui constitue à lui seul environ 70% du temps de traitement global pour la compression d'une image. Il est donc essentiel d'analyser les possibilités d'optimisation d'implémentations de JPEG2000. Les circuits FPGA sont aujourd'hui les principaux circuits reconfigurables disponibles sur le marché. S'ils ont longtemps été utilisés uniquement pour le prototypage des ASIC, ils sont aujourd'hui en mesure de fournir une solution efficace à la réalisation matérielle d'applications dans de nombreux domaines. Vu le progrès que connaît l'industrie des composants FPGA du point de vue capacité d'intégration et fréquence de fonctionnement, les architectures reconfigurables constituent aujourd'hui une solution efficace et compétitive pour répondre aussi bien aux besoins du prototypage qu'à ceux des implémentations matérielles. Dans ce travail nous proposons une démarche pour l'étude des possibilités d'implémentations de JPEG2000. Cette étude a débuté avec l'évaluation d'implémentations logicielles sur plateformes commerciales. Des optimisations logicielles ont été ajoutées en utilisant des librairies SIMD spécialisées exploitant du parallélisme à grain fin. Suite à cette première étude on a réalisé une implémentation matérielle d'un bi codeur entropique sur FPGA qui a servi comme coprocesseur pour deux plateformes distinctes l'une étant une machine hôte et l'autre un système industriel embarqué. Suite à cette étape nous avons fait évoluer l'implémentation en passant à une deuxième approche qui est l'approche système sur puce programmable. Dans cette dernière partie nous avons effectué le partitionnement matériel/logiciel du codeur entropique sur FPGA, puis une implémentation multi codeur a été réalisée sur FPGA et utilisée comme coprocesseur sur puce pour la création d'un système sur puce programmable. Ces différents travaux ont permis de couvrir une partie de l'espace des applications que JPEG2000 peut cibler. En même temps ces implémentations donnent une vue globale sur les possibilités des implémentations de JPEG2000 ainsi que leurs limites. De plus cette étude représente un moyen pour décider de l'adéquation architecture application de JPEG2000.