La tomographie sismique des temps de trajet est un problème d'optimisation mal-posé du fait de la non-linéarité entre les temps et le modèle de vitesse. Par ailleurs, l'unicité de la solution n'est pas garantie car les données peuvent être expliquées par de nombreux modèles. Les méthodes de Monte-Carlo par Chaînes de Markov qui échantillonnent l'espace des paramètres sont généralement appréciées pour répondre à cette problématique. Cependant, ces approches ne peuvent pleinement tirer partie des ressources computationnelles fournies par les super-calculateurs modernes. Dans cette thèse, je me propose de résoudre le problème de tomographie sismique à l'aide d'algorithmes évolutionnistes. Ce sont des méthodes d'optimisation stochastiques inspirées de l'évolution naturelle des espèces. Elles opèrent sur une population de modèles représentés par un ensemble d'individus qui évoluent suivant des processus stochastiques caractéristiques de l'évolution naturelle. Dès lors, la population de modèles peut être intrinsèquement évaluée en parallèle ce qui rend ces algorithmes particulièrement adaptés aux architectures des super-calculateurs. Je m'intéresse plus précisément aux trois algorithmes évolutionnistes les plus populaires, à savoir l'évolution différentielle, l'optimisation par essaim particulaire, et la stratégie d'évolution par adaptation de la matrice de covariance. Leur faisabilité est étudiée sur deux jeux de données différents: un jeu réel acquis dans le contexte de la fracturation hydraulique et un jeu synthétique de réfraction généré à partir du modèle de vitesse Marmousi réputé pour sa géologie structurale complexe. / Seismic traveltime tomography is an ill-posed optimization problem due to the non-linear relationship between traveltime and velocity model. Besides, the solution is not unique as many models are able to explain the observed data. The non-linearity and non-uniqueness issues are typically addressed by using methods relying on Monte Carlo Markov Chain that thoroughly sample the model parameter space. However, these approaches cannot fully handle the computer resources provided by modern supercomputers. In this thesis, I propose to solve seismic traveltime tomography problems using evolutionary algorithms which are population-based stochastic optimization methods inspired by the natural evolution of species. They operate on concurrent individuals within a population that represent independent models, and evolve through stochastic processes characterizing the different mechanisms involved in natural evolution. Therefore, the models within a population can be intrinsically evaluated in parallel which makes evolutionary algorithms particularly adapted to the parallel architecture of supercomputers. More specifically, the works presented in this manuscript emphasize on the three most popular evolutionary algorithms, namely Differential Evolution, Particle Swarm Optimization and Covariance Matrix Adaptation - Evolution Strategy. The feasibility of evolutionary algorithms to solve seismic tomography problems is assessed using two different data sets: a real data set acquired in the context of hydraulic fracturing and a synthetic refraction data set generated using the Marmousi velocity model that presents a complex geology structure.

Les primitives de la cryptographie à clé publique reposent sur la difficulté supposée de résoudre certains problèmes mathématiques. Dans ce travail, on s'intéresse à la cryptanalyse du problème du logarithme discret dans les sous-groupes multiplicatifs des corps finis. Les algorithmes de calcul d'index, utilisés dans ce contexte, nécessitent de résoudre de grands systèmes linéaires creux définis sur des corps finis de grande caractéristique. Cette algèbre linéaire représente dans beaucoup de cas le goulot d'étranglement qui empêche de cibler des tailles de corps plus grandes. L'objectif de cette thèse est d'explorer les éléments qui permettent d'accélérer cette algèbre linéaire sur des architectures pensées pour le calcul parallèle. On est amené à exploiter le parallélisme qui intervient dans différents niveaux algorithmiques et arithmétiques et à adapter les algorithmes classiques aux caractéristiques des architectures utilisées et aux spécificités du problème. Dans la première partie du manuscrit, on présente un rappel sur le contexte du logarithme discret et des architectures logicielles et matérielles utilisées. La seconde partie du manuscrit est consacrée à l'accélération de l'algèbre linéaire. Ce travail a donné lieu à deux implémentations de résolution de systèmes linéaires basées sur l'algorithme de Wiedemann par blocs : une implémentation adaptée à un cluster de GPU NVIDIA et une implémentation adaptée à un cluster de CPU multi-cœurs. Ces implémentations ont contribué à la réalisation de records de calcul de logarithme discret dans les corps binaires GF(2^{619}) et GF(2^{809} et dans le corps premier GF(p_{180}) / The security of public-key cryptographic primitives relies on the computational difficulty of solving some mathematical problems. In this work, we are interested in the cryptanalysis of the discrete logarithm problem over the multiplicative subgroups of finite fields. The index calculus algorithms, which are used in this context, require solving large sparse systems of linear equations over finite fields. This linear algebra represents a serious limiting factor when targeting larger fields. The object of this thesis is to explore all the elements that accelerate this linear algebra over parallel architectures. We need to exploit the different levels of parallelism provided by these computations and to adapt the state-of-the-art algorithms to the characteristics of the considered architectures and to the specificities of the problem. In the first part of the manuscript, we present an overview of the discrete logarithm context and an overview of the considered software and hardware architectures. The second part deals with accelerating the linear algebra. We developed two implementations of linear system solvers based on the block Wiedemann algorithm: an NVIDIA-GPU-based implementation and an implementation adapted to a cluster of multi-core CPU. These implementations contributed to solving the discrete logarithm problem in binary fields GF(2^{619}) et GF(2^{809}) and in the prime field GF(p_{180})

Cette thèse vise à la conception d'un environnement pour le calcul haute performance dans un cadre d'optimisation numérique. Les outils de conception et d’optimisation sont répartis dans plusieurs équipes distantes, académiques et industrielles, qui collaborent au sein des mêmes projets. Les outils doivent être fédérés au sein d’un environnement commun afin d'en faciliter l'accès aux chercheurs et ingénieurs. L'environnement que nous proposons, pour répondre aux conditions précédentes, se compose d’un système de workflow et d’un système de calcul distribué. Le premier a pour objectif de faciliter la tâche de conception de l'application tandis que le second se charge de l’exécution sur des ressources de calcul distribuées. Bien sûr, des services de communication entre les deux systèmes doivent être développés. Les calculs doivent être réalisés de manière efficace, en prenant en compte le parallélisme interne de certains codes, l’exécution synchrone ou asynchrone des tâches, le transfert des données et les ressources matérielles et logicielles disponibles (répartition de charge par exemple). De plus, l’environnement doit assurer un bon niveau de tolérance aux pannes et aux défaillances logicielles, afin de minimiser leur influence sur le résultat final ou sur le temps de calcul. Une condition importante en particulier est de pouvoir implanter des dispositifs de reprise sur erreur, de telle sorte que le temps supplémentaire de traitement des erreurs reste très inférieur au temps de re-exécution total. Dans le cadre de ce travail, notre choix s'est porté sur le moteur de workflow Yawl, qui présente de bonnes caractéristiques en termes i) d'indépendance vis à vis du matériel et du logiciel (système client-serveur pouvant fonctionner sur du matériel hétérogène) et ii) de mécanisme de reprise sur erreur. Pour la partie calcul distribué, nos expériences ont été réalisées sur la plateforme Grid5000, en utilisant jusqu'à 64 machines différentes réparties sur cinq sites géographiques. Ce document détaille les choix de conception de cet environnement ainsi que les ajouts et modifications que nous avons été amenés à apporter à Yawl pour lui permettre de fonctionner sur une plateforme distribuée. / This thesis aims conceiving an environment for high performance computing in a numerical optimization context. The tools for conception and optimization are distributed across several teams, both academics and industrial, which collaborate inside a unique project. The tools should be federated within a common environment to facilitate access to researchers and engineers. The environment that we offer, in order to meet the above conditions, consists of a workflow system and a distributed computing system. The first system aims to facilitate the application design task while the latter is responsible for executing on distributed computing resources. Of course, communication services between the two systems must be developed. The computation must be performed effectively, taking into account the internal parallelism of some software code, synchronous or asynchronous task execution, the transfer of data and hardware and software resources available (e.g. load balancing). In addition, the environment should provide a good level of fault tolerance and software failures, to minimize their influence on the final result or the computation time. An important condition in particular is to implement recovery devices on error occurence, so that the extra time for error handling remains well below the total time of re-execution. As part of this work, our choice fell on the Yawl workflow engine, which has good characteristics in terms of i) hardware and software independence (client-server system that can run on heterogeneous hardware) and ii) error recovery mechanism. For distributed computing part, our experiments were performed on the Grid5000 platform, using up to 64 different machines on five geographical sites. This document details the design of this environment and the extensions and changes we have had to perform on Yawl to enable it to run on a distributed platform.

Cette thèse présente une méthode de résolution parallèle de systèmes linéaires creux qui combine efficacement les techniques de résolutions directes et itératives en utilisant une approche de type complément de Schur. Nous construisons une décomposition de domaine. L'intérieur des sous-domaines est éliminé de manière directe pour se ramener à un problème sur l'interface. Ce problème est résolu grâce à une méthode itérative préconditionnée par une factorisation incomplète. Un réordonnancement de l'interface permet la construction d'un préconditionneur global du complément de Schur. Des algorithmes minimisant le pic mémoire de la construction du préconditionneur sont proposés. Nous exploitons un schéma d'équilibrage de charge utilisant une répartition de multiples sous-domaines sur les processeurs. Les méthodes sont implémentées dans le solveur HIPS et des résultats expérimentaux parallèles sont présentés sur de grands cas tests industriels.

Les normes drastiques sur les émissions d'espèces polluantes et la volonté de réduire les délais de mise sur le marché incitent les motoristes à repenser les concepts de la nouvelle génération de chambres de combustion ainsi que leurs méthodes de conception. Les codes de simulation numérique des écoulements turbulents réactifs, basés sur une approche de moyenne de Reynolds (RANS), sont utilisés depuis quelques années par les ingénieurs dans les phases de conception des foyers aéronautiques. Leur emploi a permis de réduire les temps et les coûts de conception en diminuant notamment le nombre d'essais expérimentaux. La manière d'utiliser ces outils demeure un point clé pour élaborer des environnements performants d'aide à la décision.<br /><br />Le but de ces travaux de thèse est de fournir une méthodologie basée sur des considérations issues de l'optimisation multi-objectif pour développer un outil de conception automatisé qui intègre des codes de simulation numérique pour évaluer les configurations. En premier lieu, les études concernent l'automatisation des procédures de simulation en insistant sur les aspects de génération automatique de maillage. Ensuite, le problème des temps de restitution liés à l'utilisation conjointe de techniques d'optimisation et de codes de calcul coûteux en ressources informatiques est adressé en proposant un algorithme basé sur des méta-modèles. L'outil final est construit à partir d'un coupleur de codes parallèles, lui conférant ainsi des caractéristiques intéressantes de performance et de flexibilité. Finalement, après divers tests de validation et d'évaluation, une application sur une chambre de combustion industrielle montre les capacités de la méthode à identifier des configurations prometteuses.

Cette thèse porte sur l'étude de la simulation des solides par des méthodes de couplage multi-échelles (méthode atomique/continue ACM). Dans ce travail de thèse, nous abordons des modéles mathématiques jusqu'à la réalisation informatique dans un contexte de calculs hautes performances parallèles. Après avoir appelé le fonctionnement des méthodes numériques utilisées dans le cadre de la simulation des solides, tels que la dynamique moléculaire et la mécanique des milieux continus, nous présentons les différentes méthodes de couplage existantes utilisées pour les coupler. Nous considérons la méthode Bridging Method développée par T. Belytschko et S. Xiao qui utilise une zone de recouvrement spatiale entre les deux modèles pour réaliser le couplage des degrès de libertés. Après avoir présenté une modification améliorant la stabilité de cette solution, nous ferons une analyse spectrale d'un cas unidimensionel couplé par cette méthode. Nous présenterons ensuite les techniques informatiques qui ont été mise en place afin de réaliser l'implémentation d'un prototype. La plateforme informatique est basé sur une philosophie de composants des entités logicielles qui autorise, in fine, de coupler les codes génériques dans un environnement logiciel. Notamment on s'intéressera à l'implémentation des routines qui permettent de paralléliser le couplage. Nous présenterons enfin les résultats numériques obtenus sur des cas tests en dimension 2 et 3 pour des cas de propagations d'ondes et de propagation de fissures.

Cette thèse explore les possibilités algorithmiques offertes par la synthèse de haut niveau de circuits dans le cadre de la logique synchrone et à destination d'une Mémoire Active Programmable. Une chaîne de compilation expérimentale permettant de générer automatiquement un circuit reconfigurable à partir d'une spécification de haut niveau y est présentée. Le langage de haut niveau est DSL (Design Source Language). DSL est basé sur le langage fonctionnel Jazz. DSL permet de décrire tout type de circuit dans le modèle de la logique synchrone, d'en faire la simulation et la synthèse, puis de l'exécuter sur une Mémoire Active Programmable. Le compilateur procède par étapes successives pour synthétiser un circuit à partir de son code-source de haut niveau. Chacune des étapes de la compilation génère des annotations qui précisent les propriétés du circuit jusqu'à une forme synthétisable. Les annotations sont pour la plupart ajoutées automatiquement par le compilateur mais sont partie intégrante de la syntaxe de DSL et peuvent ainsi être précisées par le concepteur. DSL prend en charge la génération automatique de l'ensemble des routines systèmes qui permettent au circuit de communiquer avec son hôte. Ce système de prototypage et d'accélération matérielle automatique sur PAM est testé sur des circuits variés, comme des algorithmes de tramage, d'estimation de mouvement et de détection des points de Harris.

Dans cette thèse, nous montrons que les optimisations source-à-source sont un moyen efficace pour générer des programmes irréguliers ou parallèles performants à partir d'une implémentation. Après avoir présenté l'évolution des architectures des processeurs, nous proposons deux méthodes distinctes. La première pour extraire des codelets d'un programme irréguliers, les optimiser et prédire les performances du programme modifié. L'autre pour limiter l'impact des problèmes d'alignements dus à la vectorisation ou aux conflits de bancs. Nous présentons aussi différentes techniques de parallélisation, l'une générant des codelets parallèles, l'autre ordonnançant un graphe de taches sur un système hétérogène.

Ordonnancement d’E/S Transversal pour les Systèmes de Fichiers Parallèles : desApplications aux DispositifsCette thèse porte sur l’utilisation de l’ordonnancement d’Entrées/Sorties (E/S) pour atténuer leseffets d’interférence et améliorer la performance d’E/S des systèmes de fichiers parallèles. Ilest commun pour les plates-formes de calcul haute performance (HPC) de fournir une infrastructurede stockage partagée pour les applications qui y sont hébergées. Dans cette situation,où plusieurs applications accèdent simultanément au système de fichiers parallèle partagé, leursaccès vont souffrir de l’interférence, ce qui compromet l’efficacité des stratégies d’optimisationd’E/S.Nous avons évalué la performance de cinq algorithmes d’ordonnancement dans les serveurs dedonnées d’un système de fichiers parallèle. Ces tests ont été exécutés sur différentes platesformeset sous différents modèles d’accès. Les résultats indiquent que la performance des ordonnanceursest affectée par les modèles d’accès des applications, car il est important pouraméliorer la performance obtenue grâce à un algorithme d’ordonnancement de surpasser sessurcoûts. En même temps, les résultats des ordonnanceurs sont affectés par les caractéristiquesdu système d’E/S sous-jacent - en particulier par des dispositifs de stockage. Différents dispositifsprésentent des niveaux de sensibilité à la séquentialité et la taille des accès distincts, ce quipeut influencer sur le niveau d’amélioration de obtenue grâce à l’ordonnancement d’E/S.Pour ces raisons, l’objectif principal de cette thèse est de proposer un modèle d’ordonnancementd’E/S avec une double adaptabilité : aux applications et aux dispositifs. Nous avons extraitdes informations sur les modèles d’accès des applications en utilisant des fichiers de trace,obtenus à partir de leurs exécutions précédentes. Ensuite, nous avons utilisé de l’apprentissageautomatique pour construire un classificateur capable d’identifier la spatialité et la taille desaccès à partir du flux de demandes antérieures. En outre, nous avons proposé une approche pourobtenir efficacement le ratio de débit séquentiel et aléatoire pour les dispositifs de stockage enexécutant des benchmarks pour un sous-ensemble des paramètres et en estimant les restantsavec des régressions linéaires.Nous avons utilisé les informations sur les caractéristiques des applications et des dispositifsde stockage pour décider automatiquement l’algorithme d’ordonnancement le plus appropriéen utilisant des arbres de décision. Notre approche améliore les performances jusqu’à 75% parrapport à une approche qui utilise le même algorithme d’ordonnancement dans toutes les situations,sans capacité d’adaptation. De plus, notre approche améliore la performance dans 64%de scénarios en plus, et diminue les performances dans 89% moins de situations. Nos résultatsmontrent que les deux aspects - des applications et des dispositifs - sont essentiels pour faire desbons choix d’ordonnancement. En outre, malgré le fait qu’il n’y a pas d’algorithme d’ordonnancementqui fournit des gains de performance pour toutes les situations, nous montrons queavec la double adaptabilité il est possible d’appliquer des techniques d’ordonnancement d’E/Spour améliorer la performance, tout en évitant les situations où cela conduirait à une diminutionde performance. / This thesis focuses on I/O scheduling as a tool to improve I/O performance on parallel file systemsby alleviating interference effects. It is usual for High Performance Computing (HPC)systems to provide a shared storage infrastructure for applications. In this situation, when multipleapplications are concurrently accessing the shared parallel file system, their accesses willaffect each other, compromising I/O optimization techniques’ efficacy.We have conducted an extensive performance evaluation of five scheduling algorithms at aparallel file system’s data servers. Experiments were executed on different platforms and underdifferent access patterns. Results indicate that schedulers’ results are affected by applications’access patterns, since it is important for the performance improvement obtained througha scheduling algorithm to surpass its overhead. At the same time, schedulers’ results are affectedby the underlying I/O system characteristics - especially by storage devices. Differentdevices present different levels of sensitivity to accesses’ sequentiality and size, impacting onhow much performance is improved through I/O scheduling.For these reasons, this thesis main objective is to provide I/O scheduling with double adaptivity:to applications and devices. We obtain information about applications’ access patternsthrough trace files, obtained from previous executions. We have applied machine learning tobuild a classifier capable of identifying access patterns’ spatiality and requests size aspects fromstreams of previous requests. Furthermore, we proposed an approach to efficiently obtain thesequential to random throughput ratio metric for storage devices by running benchmarks for asubset of the parameters and estimating the remaining through linear regressions.We use this information on applications’ and storage devices’ characteristics to decide the bestfit in scheduling algorithm though a decision tree. Our approach improves performance byup to 75% over an approach that uses the same scheduling algorithm to all situations, withoutadaptability. Moreover, our approach improves performance for up to 64% more situations, anddecreases performance for up to 89% less situations. Our results evidence that both aspects- applications and storage devices - are essential for making good scheduling choices. Moreover,despite the fact that there is no scheduling algorithm able to provide performance gainsfor all situations, we show that through double adaptivity it is possible to apply I/O schedulingtechniques to improve performance, avoiding situations where it would lead to performanceimpairment. / Esta tese se concentra no escalonamento de operações de entrada e saída (E/S) como uma soluçãopara melhorar o desempenho de sistemas de arquivos paralelos, aleviando os efeitos dainterferência. É usual que sistemas de computação de alto desempenho (HPC) ofereçam umainfraestrutura compartilhada de armazenamento para as aplicações. Nessa situação, em quemúltiplas aplicações acessam o sistema de arquivos compartilhado de forma concorrente, osacessos das aplicações causarão interferência uns nos outros, comprometendo a eficácia de técnicaspara otimização de E/S.Uma avaliação extensiva de desempenho foi conduzida, abordando cinco algoritmos de escalonamentotrabalhando nos servidores de dados de um sistema de arquivos paralelo. Foramexecutados experimentos em diferentes plataformas e sob diferentes padrões de acesso. Osresultados indicam que os resultados obtidos pelos escalonadores são afetados pelo padrão deacesso das aplicações, já que é importante que o ganho de desempenho provido por um algoritmode escalonamento ultrapasse o seu sobrecusto. Ao mesmo tempo, os resultados doescalonamento são afetados pelas características do subsistema local de E/S - especialmentepelos dispositivos de armazenamento. Dispositivos diferentes apresentam variados níveis desensibilidade à sequencialidade dos acessos e ao seu tamanho, afetando o quanto técnicas deescalonamento de E/S são capazes de aumentar o desempenho.Por esses motivos, o principal objetivo desta tese é prover escalonamento de E/S com duplaadaptabilidade: às aplicações e aos dispositivos. Informações sobre o padrão de acesso dasaplicações são obtidas através de arquivos de rastro, vindos de execuções anteriores. Aprendizadode máquina foi aplicado para construir um classificador capaz de identificar os aspectosespacialidade e tamanho de requisição dos padrões de acesso através de fluxos de requisiçõesanteriores. Além disso, foi proposta uma técnica para obter eficientemente a razão entre acessossequenciais e aleatórios para dispositivos de armazenamento, executando testes para apenas umsubconjunto dos parâmetros e estimando os demais através de regressões lineares.Essas informações sobre características de aplicações e dispositivos de armazenamento são usadaspara decidir a melhor escolha em algoritmo de escalonamento através de uma árvore dedecisão. A abordagem proposta aumenta o desempenho em até 75% sobre uma abordagem queusa o mesmo algoritmo para todas as situações, sem adaptabilidade. Além disso, essa técnicamelhora o desempenho para até 64% mais situações, e causa perdas de desempenho em até 89%menos situações. Os resultados obtidos evidenciam que ambos aspectos - aplicações e dispositivosde armazenamento - são essenciais para boas decisões de escalonamento. Adicionalmente,apesar do fato de não haver algoritmo de escalonamento capaz de prover ganhos de desempenhopara todas as situações, esse trabalho mostra que através da dupla adaptabilidade é possívelaplicar técnicas de escalonamento de E/S para melhorar o desempenho, evitando situações emque essas técnicas prejudicariam o desempenho.

Cette thèse étudie la gestion de ressources pour des services de calcul intensif à la demande sur une grappe de calcul partagée. Dans un tel contexte, il s'agissait de définir des outils d'exploitation qui permettent d'allouer dynamiquement les ressources pour l'exécution des requêtes à la demande, de partager équitablement les ressources entre les différents services, tout en maximisant leur utilisation. Financé par le pôle de compétitivité Minalogic dans le cadre du projet Ciloe (http://ciloe.minalogic.net), ce travail s'adresse à des organisations de types PME ou PMI, où les budgets de fonctionnement ne permettent pas de supporter les charges d'une infrastructure de calcul dédiée. Dans un premier temps, nous avons dressé un état de l'art sur la gestion de ressources dans les domaines de nuage de calcul et de calcul intensif. Puis, tirant partie de cette étude, nous avons défini une architecture virtualisée pour faciliter l'exécution dynamique des requêtes grâce à un gestionnaire de ressources spécifique. Nous avons enfin proposé une stratégie de partage et d'allocation de ressources flexible qui offre un compromis entre équité et utilisation efficace de ressources. Ayant travaillé dans un contexte de collaboration avec des industriels, nous avons développé un prototype comme une preuve de concept. Basé sur des standards ouverts, ce prototype s'appuie sur des outils existants de virtualisation tel que OpenNebula pour allouer et manipuler les machines virtuelles sur les noeuds de la grappe. A partir de ce prototype et diverses charges de travail qui sont détaillés dans cette thèse, nous avons mené des expériences pour évaluer l'architecture et les algorithmes de gestion de ressources. Les résultats montrent que ces différentes contributions satisfont les objectifs fixés tout en étant performantes et efficaces.