Thèse de doctorat : Informatique : Lyon, École normale supérieure (sciences) : 2004. / Bibliogr. p. 139-146.

Reproduction de : Thèse de doctorat : Dynamique des fluides : Toulouse, INPT : 2007. / Titre provenant de l'écran-titre. Bibliogr. 266 réf.

Thèse de doctorat : Mathématiques et Informatique. Informatique : Bordeaux 1 : 2008. / Titre provenant de l'écran-titre.

Ce manuscrit s'inscrit dans le domaine du calcul intensif (HPC) où le besoin croissant de performance pousse les fabricants de processeurs à y intégrer des mécanismes de plus en plus sophistiqués. Cette complexité grandissante rend l'utilisation des architectures compliquée. La modélisation des performances des architectures multi-cœurs permet de remonter des informations aux utilisateurs, c'est à dire les programmeurs, afin de mieux exploiter le matériel. Cependant, du fait du manque de documentation et de la complexité des processeurs modernes, cette modélisation est souvent difficile. L'objectif de ce manuscrit est d'utiliser des mesures de performances de petits fragments de codes afin de palier le manque d'information sur le matériel. Ces expériences, appelées micro-benchmarks, permettent de comprendre les performances des architectures modernes sans dépendre de la disponibilité des documentations techniques. Le premier chapitre présente l'architecture matérielle des processeurs modernes et, en particulier, les caractéristiques rendant la modélisation des performances complexe. Le deuxième chapitre présente une méthodologie automatique pour mesurer les performances des instructions arithmétiques. Les informations trouvées par cette méthode sont la base pour des modèles de calculs permettant de prédire le temps de calcul de fragments de codes arithmétique. Ce chapitre présent également comment de tels modèles peuvent être utilisés pour optimiser l'efficacité énergétique, en prenant pour exemple le processeur SCC. La dernière partie de ce chapitre motive le fait de réaliser un modèle mémoire prenant en compte la cohérence de cache pour prédire le temps d'accès au données. Le troisième chapitre présente l'environnement de développement de micro-benchmark utilisé pour caractériser les hiérarchies mémoires dotées de cohérence de cache. Ce chapitre fait également une étude comparative des performances mémoire de différentes architectures et l'impact sur les performances du choix du protocole de cohérence. Enfin, le quatrième chapitre présente un modèle mémoire permettant la prédiction du temps d'accès aux données pour des applications régulières de type \openmp. Le modèle s'appuie sur l'état des données dans le protocole de cohérence. Cet état évolue au fil de l'exécution du programme en fonction des accès à la mémoire. Pour chaque transition, une fonction de coût est associée. Cette fonction est directement dérivée des résultats des expériences faites dans le troisième chapitre, et permet de prédire le temps d'accès à la mémoire. Une preuve de concept de la fiabilité de ce modèle est faite, d'une part sur les applications d'algèbre et d'analyse numérique, d'autre part en utilisant ce modèle pour modéliser les performance des communications \mpi en mémoire partagée. / In the race for better performance, computer architectures are becoming more and more complex. Therefore the need for hardware models is crucial to i) tune software to the underling architecture, ii) build tools to better exploit hardware or iii) choose an architecture according to the needs of a given application. In this dissertation, we aim at describing how to build a hardware model that targets all critical parts of modern computer architecture. That is the processing unit itself, memory and even power consumption. We believe that a large part of hardware modeling can be done automatically. This would relieve people from the tiresome task of doing it by hand. Our first contribution is a set of performance models for the on-core part of several different CPUs. This part of an architecture model is called the computational model. The computational model targeting the Intel SCC chip also includes a power model allowing for power aware performance optimization. Our other main contribution is an auto-tuned memory hierarchy model for general purpose CPUs able to i) predict performance of memory bound computations, ii) provide programmer with programming guidelines to improve software memory behavior.

La Dynamique des Dislocations modélise le comportement de défauts linéiques - les dislocations - présents dans la structure des matériaux cristallins. Il s'agit d'un maillon essentiel de la modélisation multi-échelles des matériaux utilisé par exemple dans l’industrie du nucléaire pour caractériser le comportement mécanique et le vieillissement des matériaux sous irradiation. La capacité des dislocations à se multiplier, s’annihiler et interagir pose de nombreux défis informatiques, notamment sur la manière de stocker et traiter de manière efficace les données de la simulation. L'objectif de cette thèse est de répondre à ces défis que posent les simulations massives de Dynamique des Dislocations dans un environnement parallèle et distribué au travers du logiciel Optidis. Dans cette thèse, je propose des améliorations au simulateur Optidis afin de permettre des simulations plus complexes en utilisant la puissance des super-calculateurs. Mes contributions sont axées sur l'amélioration de la fiabilité et de la performance d'Optidis. La mise en place d'une nouvelle interface d'accès aux données a permis de dissocier l'implémentation des algorithmes de l'optimisation des performances. Cette structure de données permet de meilleures performances tout en améliorant la maintenabilité du code, même lorsque les données sont distribuées. Un nouvel algorithme de gestion des collisions entre dislocations et de formation des jonctions fiable et performant a été mis en place. Des techniques de détection de collision empruntées aux application en temps réel et à la dynamique moléculaire sont utilisées pour accélérer le calcul. S’appuyant sur l’utilisation de la nouvelle structure de données et un traitement des collisions plus élaboré, il permet une gestion de collisions fiable et autorise l'utilisation de pas de temps plus grands. La précision du résultat a été étudiée en se comparant au code NUMODIS, et la performance d'Optidis a été mesurée sur des simulations massives contenant plusieurs millions de segments de dislocations en utilisant plusieurs centaines de cœurs de calcul, démontrant que de telles simulations sont réalisables en un temps raisonnable. / Dislocation dynamics simulations investigate the behavior of linear defects, called dislocations, in crystalline materials. It is an essential part multiscale modelling of the materials, used for instance in the nuclear industry to characterize the behavior and aging of materials under irradiation. The ability of dislocations to multiply, annihilate and interact presents many challenges, for instance in terms of storage and access to data. This thesis addresses some challenges of dislocation dynamics simulation on parallel and distributed computers. In this thesis, I improve the Optidis simulator to open the way to more complex simulations. My contributions focuses mainly on improving the reliability and performance of Optidis. A new interface to access simulation data is proposed to dissociate its implementation form the physical algorithms. This data structure allows better performance as well as better code maintainability, even with distributed data. A new fast and reliable collision detection and handling algorithm has been implemented. Collision detection techniques from the robotics and 3D animation industries are used to speedup the detection process. With the use of the new data structure and a more reliable design, this algorithm enables more precise collision handling and the use of a larger simulation timestep. The precision of the results have been measured by comparing Optidis to Numodis. The performance of the code has been studied on larger scale simulations with millions of segments and hundreds of CPU cores, demonstrating that such simulations can now be achieved.

La bioinformatique nécessite l'analyse de grandes quantités de données. Avec l'apparition de nouvelles technologies permettant un séquençage à haut débit à bas coût, la puissance de calcul requise pour traiter les données a énormément augmenté.. Cette thèse examine la possibilité d'utiliser les processeurs graphiques (GPU) pour des applications de bioinformatique. Dans un premier temps, ce travail s'intéresse au calcul des structures secondaires d'ARN. Ce problème est en général calculé par programmation dynamique, avec un algorithme qui pose de sérieux problèmes pour un code GPU. Nous introduisons une nouvelle implémentation tuilée qui fait apparaitre une bonne localité mémoire, permettant ainsi un programme GPU très efficace. Cette modification permet également de vectoriser le code CPU et donc de faire une comparaison honnête des performances entre GPU et CPU. Dans un deuxième temps, ce travail aborde le problème d'alignements de séquences. Nous présentons une parallélisation GPU d'une méthode utilisant une indexation par graines. L' implémentation sur GPU n'étant pas efficace, nous nous tournons vers le développement d'une version CPU. Notre contribution principale est le développement d'un nouvel algorithme éliminant rapidement les nombreux alignements potentiels, basé sur le précalcul de portions de la matrice de programmation dynamique. Ce nouvel algorithme a conduit au développement d'un nouveau programme d'alignement très efficace. Notre travail fournit l'exemple de deux problèmes différents dont seulement un a pu être efficacement parallélisé sur GPU. Ces deux expériences nous permettent d'évaluer l'efficacité des GPU et leur place en bioinformatique.

Reproduction de : Thèse de doctorat : Informatique et télécommunications : Toulouse, INPT : 2006. / Texte en anglais. Titre provenant de l'écran-titre. Bibliogr. 106 réf.

Mes recherches concernent les outils de développement pour le calcul intensif. Une application sera dite intensive s'il faut fortement l'optimiser pour obtenir la puissance de calcul requise pour répondre aux contraintes, d'une part, de temps d'exécution et, d'autre part, de ressources de la plateforme d'exécution. De telles applications se retrouvent aussi bien dans le domaine du calcul scientifique que dans le domaine du traitement de signal intensif (télécommunications, traitement multimédia). Les difficultés de développement de telles applications sont principalement l'exploitation du parallélisme des architectures d'exécution (des supercalculateurs aux systèmes sur silicium en passant par les grappes de stations de travail), l'hétérogénéité de ces mêmes architectures et le respect des contraintes de temps et de ressources. Le but de mes recherches est de proposer des outils permettant la programmation efficace des applications de calcul intensif. Ceux-ci peuvent être des compilateurs, des paralléliseurs ou des environnements de spécification. Mes travaux ont commencé par les compilateurs paralléliseurs et s'orientent de plus en plus vers les environnements de spécification. Ces environnements comportent des compilateurs paralléliseurs. Cette évolution consiste donc à remplacer le langage de programmation et la phase d'analyse des programmes par une spécification des algorithmes de plus haut niveau et facilitant la phase d'analyse de dépendances. En effet, le but de cette analyse est de retrouver l'essence de l'algorithme codé par le programme analysé. La spécification de l'algorithme par les seules dépendances de données permet d'éliminer l'analyse de dépendances et d'avoir toute l'information nécessaire pour les optimisations du compilateur paralléliseur. Quatre principes dirigent mes recherches : 1. Programmer au plus haut niveau possible. Il ne devrait pas être de la responsabilité du programmeur de gérer les détails de l'exécution de son application. Idéalement, il devrait exprimer son algorithme et les compilateurs devraient générer le code le plus efficace possible sur l'architecture visée. 2. Promouvoir le parallélisme de données. Ce paradigme de programmation permet justement une programmation de haut niveau dans bien des cas. Il est bien adapté au calcul intensif où les traitements sont souvent réguliers et la quantité de données manipulées importante. 3. Optimiser au plus tôt dans la chaîne de développement. Je suis convaincu que plus les informations de performances et les optimisations sont faites tôt dans le développement d'une application, plus ce développement sera rapide et l'application efficace. L'environnement de conception doit donc faire apparaître ces informations si elles sont disponibles, y compris avant compilation de l'application. 4. Restreindre le domaine d'application. Il est très difficile d'optimiser tous les programmes en général. Le domaine du calcul intensif lui-même est déjà ambitieux. En se focalisant sur un domaine d'application précis, on peut espérer réduire la variété des applications et ainsi proposer des optimisations adaptées. C'est la voie que j'ai suivie dans mes recherches les plus récentes en restreignant le domaine d'application au traitement de signal intensif.

La tendance des constructeurs pour le calcul scientifique est à l'imbrication de technologies permettant un degré de parallélisme toujours plus fort au sein d'une même machine : architecture NUMA, puces multicœurs, SMT. L'efficacité de l'exécution d'une application parallèle irrégulière sur de telles machines hiérarchiques repose alors sur la qualité de l'ordonnancement des tâches et du placement des données, pour éviter le plus possible les pénalités NUMA et les défauts de cache. Les systèmes d'exploitation actuels, pris au dépourvu car trop généralistes, laissent les concepteurs d'application contraints à « câbler » leurs programmes pour une machine donnée.<br /><br />Dans cette thèse, pour garantir une certaine portabilité des performances, nous définissons la notion de /bulle/ permettant d'exprimer la nature structurée du parallélisme du calcul, et nous modélisons l'architecture de la machine cible par une hiérarchie de listes de tâches. Une interface de programmation et des outils de débogage de haut niveau permettent alors de développer simplement des ordonnanceurs dédiés, efficaces et portables. Différents ordonnanceurs mettant en œuvre des approches variées ont été développés, en partie notamment par des stagiaires encadrés au sein de l'équipe, ce qui montre à la fois la puissance et la simplicité de l'interface. C'est ainsi une véritable plate-forme de développement et d'expérimentation d'ordonnanceurs à bulles qui a été intégrée au sein de la bibliothèque de threads utilisateur marcel. Le support OpenMP du compilateur GCC, GOMP, a été étendu pour utiliser cette bibliothèque et exprimer la nature structurée des sections parallèles imbriquées à l'aide de bulles. Avec la couche de compatibilité POSIX de marcel, ces supports ont permis de tester les différents ordonnanceurs à bulles développés, sur différentes applications. Les gains obtenus, de l'ordre de 20 à 40%, montrent l'intérêt de notre approche.

De nombreuses applications scientifiques utilisent et génèrent d'énormes quantités de données. Ces applications qui exploitent des modèles d'accès parallèles spécifiques (principalement des accès disjoints) sont souvent pénalisées par des systèmes de stockage inadaptés. Pour éviter les dégradations de performances, les bibliothèques d'Entrées/Sorties parallèles telles que ROMIO sont généralement utilisées pour agréger les petites requêtes séparées en de plus grosses contiguës habituellement plus performantes. Toutefois, les optimisations apportées pour un programme ne tiennent pas compte de l'ensemble des interactions avec d'autres applications s'exécutant en concurrence sur la grappe. La conséquence est que ces routines spécifiques visant à optimiser les accès d'une application vont s'avérer inutiles, car leur effet va être perturbé par les autres applications !<br /><br />Ce document décrit une nouvelle approche, appelée aIOLi, permettant le<br />contrôle, le réordonnancement et la régulation de l'ensemble des interactions générées par les différentes applications s'exécutant simultanément sur une grappe et ce, en s'appuyant uniquement sur l'interface POSIX.<br /><br />Dans un tel contexte, la performance, l'interactivité et l'équité sont des critères pour lesquels il est important de trouver un bon compromis. Pour y parvenir, une stratégie d'ordonnancement globale prenant en compte également les problématiques d'Entrées/Sorties parallèles locales aux applications a été définie. Le service aIOLi consiste en un support d'ordonnancement générique pouvant être rattaché à différentes parties d'un système de fichiers. L'exécution concurrente de jeux de tests IOR sur un serveur NFS traditionnel ont montré des améliorations particulièrement significatives pour les accès en lecture en comparaison aux performances pouvant être atteintes avec les routines POSIX ou MPI I/O.