Soutenance mémoire
L’informatique haute performance
Pour concevoir les machines utilisées en HPC, il est nécessaire d’assembler des composants de diverses natures. L’architecture de ces machines est le fruit de nombreuses évolutions depuis l’invention du microprocesseur en 1969 par M. Hoff et F. Fagin alors ingénieurs chez Intel. Le but de ce chapitre est de définir certaines notions indispensables à la bonne compréhension du manuscrit de thèse sans pour autant faire une description chronologique des avancées technologiques dans le domaine de l’informatique.
L’évolution des architectures HPC
Avant l’invention du circuit intégré, les processeurs étaient constitués de plusieurs composants électroniques interconnectés. Cette invention permit de placer tous ces composants sur un seul circuit intégré afin de créer le microprocesseur. En 1971, la société américaine Intel commercialise le premier microprocesseur : l’Intel 4004. Depuis, le nombre de transistors dans les microprocesseurs ne cesse de croître. L’augmentation de la finesse de gravure des microprocesseurs a permis d’avoir de plus en plus de transistors par unité de surface disponible sur un microprocesseur, ce qui contribue à l’augmentation de la puissance de calcul des microprocesseurs. En 1965, G. E. Moore prédit que le nombre de transistors dans un circuit intégré doublerait tous les ans [3]. En 1975, il réévalue sa prédiction et prédit que le nombre de transistors dans un microprocesseur doublerait tous les 18 mois. Cependant, la finesse de gravure des microprocesseurs atteint bientôt ses limites physiques. En effet, après un certain seuil, il ne sera plus possible d’augmenter la finesse de gravure tout en gardant les propriétés physiques des matériaux qui permettent aux microprocesseurs de fonctionner correctement.
Le parallélisme d’instruction
Afin d’améliorer les performances des microprocesseurs, l’utilisation du parallélisme d’instruction où Instruction-Level Parallelism (ILP) est particulièrement importante. La technique est d’utiliser un pipeline d’instruction . Cela consiste à diviser le traitement d’une instruction en N étapes et de recouvrir l’étape j de l’instruction i avec l’étape j + 1 de l’instruction i − 1. De cette façon, il est possible de traiter plusieurs étapes provenant d’instructions différentes en parallèle. Dans le cas idéal, au cycle N, le pipeline est rempli et le débit d’instructions est maximal. Cependant, le pipeline n’est pas toujours rempli au maximum. Lorsque l’étape d’une instruction ne peut pas être exécutée à cause d’une dépendance de donnée, il se produit un phénomène appelé « bulle » retardant l’exécution des instructions suivantes. Plusieurs techniques existent pour limiter les bulles dans le pipeline telles que la prédiction de branchement ou bien le pipeline out-of-order. La prédiction de branchement consiste à remplir le pipeline avec les instructions d’un des branchements. Si la prédiction s’avère juste, le pipeline restera rempli et aucun temps n’est perdu. Dans le cas contraire, le pipeline est réinitialisé. Le pipeline out of-order optimise l’ordre d’exécution des instructions dans le pipeline afin d’éviter les bulles dans le pipeline. Toutes ces techniques permettent d’améliorer le nombre de cycles par instruction (CPI) du pipeline. Le temps pris pour exécuter les instructions d’un programme sur un microprocesseur, noté T, peut être décrit par l’équation 2.1.
T = N × CP I × P (2.1)
Une des façons simples pour améliorer les performances d’un microprocesseur est donc d’augmenter sa fréquence d’horloge. C’est la raison pour laquelle les sociétés fabriquant des microprocesseurs ont mené une course à la fréquence pour augmenter leurs performances. Il suffisait donc aux utilisateurs de supercalculateurs d’attendre la génération suivante de processeur pour bénéficier d’une augmentation des performances de leurs programmes. C’était sans compter que la consommation énergétique (E) des microprocesseurs est proportionnelle à la fréquence (F), au carré de la tension (V ) et la capacité électrique (C) tel que décrit par l’équation 2.3.
E = C × V² × F (2.3)
Étant donné que la consommation électrique génère de la chaleur, l’augmentation de la fréquence d’horloge devient problématique. Cela provoque une hausse de la température des microprocesseurs jusqu’à atteindre un seuil où il n’est plus possible d’augmenter la fréquence d’un microprocesseur sans qu’il soit inutilisable.
La hiérarchie de la mémoire
Afin de réaliser des calculs, les microprocesseurs sont dotés d’unités arithmétiques et logiques. Néanmoins, ces calculs doivent être effectués sur des données stockées en mémoire.
Les composants matériels
Il existe différents types de mémoires établis dans ce qu’on appelle « la hiérarchie de la mémoire ». Cette hiérarchie est née d’un compromis entre la latence de la mémoire, sa capacité et son coût de production .
Les registres : Accéder à la mémoire coûte des cycles d’horloge. Plus la mémoire est proche du microprocesseur et moins de cycles il faudra pour charger une donnée en mémoire. Afin d’avoir des bonnes performances, il est donc nécessaire d’avoir la mémoire au plus proche du microprocesseur. C’est pourquoi, les unités arithmétiques et logiques ne travaillent que sur les données stockées dans les registres. Les registres sont au plus haut niveau de la hiérarchie mémoire. Il s’agit d’une mémoire très rapide intégrée aux microprocesseurs et c’est la seule mémoire en accès direct. Le nombre de registres dépend du microprocesseur utilisé mais leur nombre est généralement très limité.
Les caches : La mémoire cache est aussi intégrée aux microprocesseurs. Il s’agit de niveaux de mémoire avec des protocoles de cohérence afin d’avoir des données toujours valides lorsque le CPU a besoin d’une donnée qui y est stockée. En effet, étant donné que le CPU ne travaille qu’avec les registres, il est nécessaire de transférer les données des caches vers les registres. La mémoire cache est disponible en très faible quantité et ne nécessite que très peu de cycles pour y accéder. Afin d’optimiser les performances des codes de calcul, il est commun de vouloir utiliser efficacement cette mémoire.
La mémoire centrale (RAM) : La mémoire RAM Random Access Memory est la mémoire principale d’un ordinateur. C’est là où sont chargés les programmes quand ils sont exécutés. Néanmoins, accéder à cette mémoire coûte approximativement 300 cycles [5]. C’est donc une mémoire lente si nous voulons avoir un programme performant.
Les disques : Les disques sont utilisés pour stocker le système de fichier d’un ordonnateur. Accéder à cette mémoire coûte approximativement 2 millions de cycles [5]. Il existe aussi le stockage sur bande magnétique pour archiver les données. Elles peuvent contenir des données sur de très longue période. Ils ne nécessitent pas de courant pour garder les données en mémoire contrairement aux mémoires que nous avons vues précédemment.
Temps d’accès aux données non uniforme
Bien que le temps d’accès aux données varie en fonction de la hiérarchie mémoire (latence), il est possible que le temps d’accès entre deux mémoires du même niveau de la hiérarchie ne soit pas uniforme. Un système numa (Non Uniform Memory Access) est constitué de plusieurs microprocesseurs disposant chacun d’une zone de mémoire propre. les CPU sont reliés entre eux par des liens QPI [6] sur les processeurs Intel, et peuvent utiliser n’importe quelle mémoire de manière cohérente. Cependant, les temps d’accès ne seront pas uniformes suivant que le CPU accède à des données sur la mémoire locale ou bien à des données se trouvant sur un banc mémoire d’un autre CPU.
La technologie « Simultaneous Multi-Threading »
La technologie Simultaneous Multi-Threading [7], plus connue sous le nom d’Hyper-Threading pour les microprocesseurs d’Intel, est incluse dans la plupart des microprocesseurs actuels. Il s’agit, pour un cœur, d’exécuter simultanément plusieurs threads matériels se partageant les mêmes unités arithmétiques et logiques. Selon la terminologie d’Intel, ces threads matériels sont appelés des Hyper-Threads. Concrètement, il s’agit de la duplication des registres de données et de contrôle au sein même d’un cœur permettant l’exécution de plusieurs fils d’exécution ou « threads » sur ce même cœur. Les Hyper-Threads se partagent donc non seulement les mêmes unités arithmétiques et logiques mais aussi la même hiérarchie mémoire dont les caches font partie. Le but est d’exécuter plusieurs threads sur le même pipeline d’instruction. Cela permet d’avoir moins de bulles et d’améliorer l’ILP. C’est pourquoi l’utilisation des Hyper-Threads n’est pas toujours synonyme de performance. En effet, l’utilisation des mêmes unités arithmétiques et logiques par plusieurs Hyper-Threads signifie que si tous les threads ont besoin des mêmes unités au même moment, il ne sera pas possible de le faire.
|
Table des matières
1 Introduction
I Contexte
2 L’informatique haute performance
2.1 L’évolution des architectures HPC
2.1.1 Le parallélisme d’instruction
2.1.2 La hiérarchie de la mémoire
2.1.2.1 Les composants matériels
2.1.2.2 Temps d’accès aux données non uniforme
2.1.3 La technologie « Simultaneous Multi-Threading »
2.1.4 Les microprocesseurs multi-cœurs
2.1.5 Les microprocesseurs manycores
2.1.6 L’avènement des systèmes massivement parallèles
2.1.7 Les classements Top500, HPCG et Green500
2.2 Les modèles de programmation
2.2.1 Modèle à mémoire partagée
2.2.1.1 Les threads posix
2.2.1.2 Le standard OpenMP
2.2.2 Modèle à mémoire distribuée : Message Passing Interface
2.2.2.1 Les communications point-à-point
2.2.2.2 Les communications collectives
2.3 Modèle d’exécution
2.3.1 L’ordonnancement
2.3.2 Les bibliothèques de threads
2.3.2.1 Bibliothèque de thread utilisateur
2.3.2.2 Bibliothèque de thread système
2.3.2.3 Bibliothèque thread mixte
2.4 Le framework MPC
2.4.1 Caractéristiques
2.4.2 La bibliothèque de threads mixte
2.4.3 L’implémentation MPI
2.4.4 L’implémentation OpenMP
2.5 Conclusion
3 État de l’art et problématique
3.1 Liens entre recouvrement, progression et ressources matérielles
3.2 Le recouvrement des communications point-à-point
3.2.1 La progression Matérielle
3.2.2 La progression Logicielle
3.2.2.1 La progression manuelle
3.2.2.2 Les threads de progression
3.2.2.3 Ordonnancement opportuniste des threads de progression
3.3 Le recouvrement des communications collectives
3.3.1 La progression Matérielle
3.3.2 La progression Logicielle
3.3.2.1 Module noyau
3.3.2.2 Une implémentation des collectives non-bloquantes : LibNBC
3.3.2.3 La progression des communications non-bloquantes dans MPC
3.4 Problématique de la thèse
II Contributions
4 Placement statique des tâches MPI et des threads de progression
4.1 Outils d’évaluation des performances
4.1.1 Mesure du taux de recouvrement et du temps d’exécution
4.1.2 Intel MPI Benchmarks : IMB-NBC
4.1.3 MPC-NBC-Bench : une suite de tests dédiés aux collectives MPI
4.1.4 Discussion
4.2 Impact du placement des threads de progression pour les collectives MPI non-bloquantes
4.2.1 Placement des tâches MPI
4.2.2 Placement des threads de progression
4.2.3 Implémentation
4.2.4 Évaluation du taux de recouvrement
4.2.5 Évaluation du temps d’exécution
4.2.6 Conclusion
4.3 Étude du placement des threads de progression sur les HyperThreads
4.3.1 Description de la méthode de test
4.3.2 Utilisation des Hyper-Threads pour les communications inter-nœuds
4.3.3 Utilisation des Hyper-Threads pour les communications intra-nœuds
4.3.4 Influence des effets de cache lors de l’utilisation des HyperThreads
4.4 Conclusion
5 Placement dynamique des threads de progression en fonction des algorithmes de collectives utilisés
5.1 L’algorithme « split-tree » pour les collectives MPI non-bloquantes en arbre
5.1.1 L’algorithme « split-tree »
5.1.2 Modélisation
5.1.2.1 Modèle pour les opérations collectives
5.1.2.2 Modèle pour l’algorithme proposé
5.1.2.3 Conclusion
5.1.3 Implémentation
5.1.4 Résultats expérimentaux
5.1.5 Discussion
5.2 Le placement « pair-impair » pour les collectives MPI nonbloquantes en chaîne
5.2.1 Étude des algorithmes en chaîne
5.2.2 Le placement « pair-impair »
5.2.3 Résultats expérimentaux
5.2.4 Conclusion sur l’algorithme « pair-impair »
5.3 Conclusion
6 Politiques d’ordonnancement des threads de progression sur les cœurs dédiés
6.1 Problématique de la surcharge des cœurs par les threads de progression
6.2 Suspension des threads de progression inutiles
6.2.1 Mécanisme de progression interne à MPC
6.2.2 Implémentation
6.2.3 Résultats expérimentaux
6.2.4 Conclusion
6.3 Ordonnancement statique à l’aide de sémaphores
6.3.1 Gestion des threads de progression avec des sémaphores
6.3.2 Résultats expérimentaux
6.3.3 Conclusion
6.4 Ordonnancement dynamique à l’aide de priorité
6.4.1 Gestion des threads de progression avec des priorités
6.4.2 Implémentation
6.4.3 Résultats expérimentaux
6.4.4 Conclusion
6.5 Conclusion
III Conclusion
