Historique du calcul haute performance

Les sciences informatiques sont aujourd’hui devenues un outil essentiel dans le domaine de la recherche et de l’industrie. Ce domaine apporte en effet un moyen pratique de traiter de grandes quantités d’informations, que ce soit au travers de la simulation numérique comme outil prédictif ou pour l’analyse de données expérimentales. Au fil des années, les calculateurs mis en place pour résoudre ces problèmes sont devenus des objets extrêmement complexes offrant une puissance de calcul toujours croissante. C’est ainsi que l’on a aujourd’hui atteint l’échelle du pétaflops permettant idéalement d’effectuer 10¹⁵ opérations flottantes par secondes. Les nouvelles ambitions se tournent donc vers le pas suivant : l’exaflop avec 10¹⁸ opérations flottantes par secondes. L’évolution technologique a toutefois effectué un tournant au courant des années 2000. Ces années ont induit des changements en profondeur des architectures faisant apparaître de nouveaux problèmes qu’il nous faut aujourd’hui prendre en compte.

Ces problèmes viennent en partie de la consommation énergétique et des contraintes d’accès à l’information (mémoire, stockage) qui tendent à orienter les évolutions matérielles et logiciels. L’arrivée conjointe des architectures multicœurs permet de résoudre certains problèmes, mais en pose de nombreux autres en demandant notamment une prise en compte explicite de ce changement de paradigme par les programmeurs. Les échelles actuelles conduisent déjà à des calculateurs très hiérarchiques composés de quelques millions de cœurs. Il en résulte l’apparition de nouvelles problématiques notamment de passage à l’échelle nécessitant de revisiter certains points historiquement considérés comme “maîtrisés”. Nous verrons que c’est le cas pour les problèmes de gestion de la mémoire au cœur de notre sujet de thèse.

Introduction au calcul haute performance

Historique du calcul haute performance

Historiquement, le calcul haute performance prend ses racines dans les centres de recherche avec des calculateurs visant à résoudre des systèmes d’équations complexes, notamment dans le domaine de la physique nucléaire. Les plus gros systèmes ouvrent alors la voie aux supercalculateurs modernes. On trouve dans un premier temps, de gros serveurs massivement vectoriels , conçus spécialement pour le calcul scientifique. On peut citer par exemple le CDC6600[Tho80] livré en 1964 ou le Cray-1[Rus78] de 1976 offrant 166 MFlops à 83 MHz doté de 8 Mo de mémoire. Ces calculateurs exploitent des unités vectorielles de 8 ∗ 64 bits et voient l’introduction de registres spécifiques dédiés aux instructions vectorielles pour compenser la lenteur d’accès à la mémoire centrale, qui, très tôt, s’avère être un facteur limitant les performances.

Très vite l’approche s’oriente vers une multiplication des composants en utilisant plusieurs processeurs partageant une même mémoire dite partagée telle que le Cray-X/MP[ABHS89] de 1982 avec 4 processeurs. Un an plus tard (1985), le Cray-2 fonctionne à 283 Mhz soit 1.7 GFlops pour 4 Go de mémoire, proche des ordres de grandeur de ce que l’on trouve dans nos téléphones portables actuels. L’évolution des machines uniques à mémoire partagée se poursuit ainsi jusqu’au milieu des années 90 en utilisant jusqu’à 2048 processeurs (Hitachi SR2201 [FYA+97].

Toutefois, l’accroissement de ces systèmes centralisés pose d’énormes problèmes de conception, notamment pour les accès à la mémoire qui ne parviennent plus à nourrir efficacement les unités de traitement. Les années 1990 orientent l’évolution vers des supercalculateurs de type grappes[BB99, EKTB99] (clusters) composés de multiples unités autonomes (nœuds) interconnectées par des réseaux spécialisés. Ce type d’approche est déjà exploité pour d’autres usages à moindre échelle tels que les systèmes VAX/VMS[KLS86] de 1986. Chaque unité est alors plus simple à concevoir et à exploiter. La complexité est donc repoussée sur l’utilisation de l’ensemble qui doit notamment prendre en charge les communications nécessaires entre les nœuds. L’évolution mène en 1992 au Paragon XP/S[EK93], doté de 2048 processeurs pour 32 nœuds. Ce contexte génère un besoin de nouveaux environnements de programmation multi-nœuds tels que PVM[FM90, Sun90]. Le travail conjoint de divers organismes et entreprises a également mené à l’interface MPI(Message Passing Interface [MPI94] dont on reparlera plus en détail dans la suite et qui reste aujourd’hui la manière commune de programmer les calculateurs de type grappe.

Avec un coût croissant de développement, les processeurs spécialisés pour le calcul scientifique commencent à devenir un facteur limitant dans les années 2000. Certains se tournent alors vers les marchés grands publics pour y trouver des processeurs moins adaptés, mais moins chers, tels que ceux fabriqués pour les stations de travail plus classiques. Cette évolution pousse donc à un retour du calcul scalaire, l’utilisation de vecteurs intéressant moins l’industrie du PC. En terme de calcul scientifique, on observe dans ces années une divergence avec l’apparition des grilles de calcul[FK99]. Cette approche est axée sur des calculs intrinsèquement parallèles et indépendants, utilisés principalement pour les analyses de données expérimentales, notamment en physique des particules ou astrophysique. Pour ce type d’usage, chaque machine traite les données d’une mini-expérience sans dépendance avec les autres. On évite ainsi la contrainte des communications inter-nœuds qui, devenue inexistante, ne nécessite plus de placer l’ensemble des nœuds dans le même lieu ni de recourir à l’utilisation de réseaux rapides onéreux. La communauté scientifique dispose aujourd’hui de projets à l’échelle nationale, tels que Grid5000[CCD+05] ou mondiale avec la grille du CERN (WLCG)[Rob12]. De manière complémentaire, le domaine des supercalculateurs se concentre autour des simulations à grandes échelles et vise à répartir un calcul unique sur une part importante du supercalculateur. Ce besoin maintient la nécessité de faire communiquer efficacement un nombre croissant de composants.

Les années 2000 ont ainsi été marquées par la course au pétaflops avec une approche multinœuds, multi-processeurs et multi-cœurs entraînant une envolée du nombre de cœurs. La barre symbolique est franchie en 2008 par les Américains (DOE/IBM) avec Roadrunner [BDH+08] : 1.046 pétaflops pour 129 600 cœurs, dont une part d’accélérateurs de type Cell. Du côté français (CEA/Bull), c’est Tera 100 qui franchit le pas en 2009 : 1.05 pétaflops pour 138 368 cœurs. La barre symbolique du million de cœurs est atteinte fin 2012 par la machine Sequoia (DOE/IBM). Cette évolution continue aujourd’hui avec 3.1 millions de cœurs pour le supercalculateur chinois Thiane-2 (NUDT), offrant 33.8 pétaflops. La tendance se poursuit ; il nous faut donc appréhender le développement de logiciels devant à l’avenir fonctionner sur des millions de cœurs.

L’histoire du HPC est ponctuée de tests de performances qui permettent de comparer les capacités de calcul des machines dans le temps. À ce titre, le Linpack [Don88] sert de base au classement mondial des 500 calculateurs les plus puissants[Top10].

Évolution actuelle des architectures

Dans cette section, nous allons nous centrer sur l’évolution survenue dans les processeurs au cours des années 2000. Cette évolution notamment marquée par l’arrêt de l’augmentation des fréquences s’est vue associée à l’arrivée du multicœur. Ceci change la manière d’exploiter le matériel et impacte les mécanismes de gestion de la mémoire en faisant apparaître les problématiques abordées dans cette thèse.

Un équilibre entre débit et latence 

Avant d’entrer dans les détails de l’évolution des architectures, il semble important d’introduire les notions capitales de débit et latence pour les architectures informatiques. On définira tout d’abord le débit comme le nombre d’actions effectuées en un laps de temps déterminé. Remarquons que l’on ne s’intéresse pas ici au temps propre de ces actions, mais au temps de l’ensemble. À l’opposé, la latence s’intéresse au temps d’exécution d’une instruction, donc le temps que l’appelant doit attendre pour voir cette action se terminer. Les recherches d’optimisation des architectures, peuvent, d’une certaine manière, se décrire comme une recherche d’équilibre entre ces deux concepts.

Ces concepts s’appliquent à l’exécution des instructions par le processeur, aux transferts mémoires ou aux échanges réseau. Idéalement, le débit devrait être favorisé pour maximiser les performances en effectuant un maximum d’actions en un temps limité. Un programme est toutefois conçu comme une suite d’actions dont certaines dépendent du résultat de la précédente. Dans un tel contexte, la réduction de la latence est critique car elle contraint la capacité à exécuter rapidement l’action suivante, donc le débit d’exécution. L’ augmentation des fréquences de fonctionnement est par exemple un moyen mécanique de gagner sur les deux postes. Ceci en réduisant par définition la latence et en augmentant le débit. Nous verrons toutefois qu’elle a aujourd’hui atteint ses limites au niveau de l’exécution des instructions.

Les échanges entre les composants physiques peuvent toutefois introduire des contraintes sur ces débits et latences en fonction des capacités des liens utilisés pour les faire communiquer. Les améliorations basées sur la sémantique d’échange entre composants sont malheureusement souvent contraintes à favoriser l’un des deux points. Nous évoquerons indirectement ce problème dans les sections qui suivent au vu des architectures exploitées dans les calculateurs actuels.

L’arrivée du multicœur 

À ses débuts, l’informatique a connu une croissance exponentielle des performances permise par la vérification des lois de Moore[Moo65, Moo75] et Dennard[DGR+74]. La première loi prédit un doublement du nombre de transistors imprimables sur une surface donnée tous les dix-huit mois. La seconde remarque que la réduction de taille des transistors permet de réduire leur consommation électrique. Ces deux lois ont une conséquence sur les performances. Tout d’abord, la réduction de taille des transistors permet d’augmenter leur fréquence de fonctionnement. A partir les quelques MHz des premiers calculateurs, on atteint le GHz peu avant l’an 2000, donc une croissance de 2 ordres de grandeur en 25 ans. D’autre part, la loi de Moore implique une augmentation du nombre de transistors utilisés dans les puces. Cela se traduit, dès les années 80[RF92], par une multiplication des unités de traitement à l’intérieur du processeur, offrant la possibilité d’extraire du parallélisme d’applications séquentielles (parallélisme d’instruction, ILP ou Instruction Level Parallelism) implémenté par deux approches complémentaires : utilisation de pipeline et d’architectures superscalaires.

L’introduction de la notion de pipeline[HP06]  permet de découper l’exécution d’une instruction en plusieurs étages, à la manière d’une chaîne d’assemblage d’usine. Plusieurs instructions peuvent donc être en cours de décodage et traitement. Cette technique ne réduit pas le temps d’exécution de l’instruction, mais permet d’augmenter le débit par l’exécution simultanée de plusieurs d’entre elles. Les processeurs actuels utilisent essentiellement des pipelines d’une profondeur allant de 10 à 20. D’autre part, certaines unités de traitement lentes peuvent être la source de ralentissement (accès mémoire, calcul flottant…). Disposer de plus de transistors permet donc de dupliquer certaines d’entre elles (architectures superscalaires). L’exploitation efficace de ces unités passe donc par un ordonnancement adapté des instructions pour maximiser l’utilisation des unités disponibles. Cet ordonnancement peut être pris en charge de manière statique par le compilateur (architecture dite in-order) ou de manière dynamique par le processeur (architecture dites out-of-order). Le réordonnancement dynamique des instructions offre également un moyen efficace de réduire l’impact des latences d’accès à la mémoire. Ceci en permettant au processeur d’exécuter dans l’intervalle les instructions disposant déjà de leurs données.

Or, au début des années 2000, ces démarches atteignent leurs limites. Les raisons tiennent en partie à la fin d’application de la loi de Dennart[DCK07]. La fin d’application de cette loi entraîne des problèmes de consommation électrique et de dissipation thermique non compensés par l’évolution des finesses de gravure. De plus, l’évolution plus lente des technologies de stockage mémoire creuse le fossé entre la vitesse de traitement d’une donnée et son temps d’accès en mémoire. Les augmentations de fréquences sont donc rendues moins intéressantes, voir inefficaces. Ce problème est connu sous le nom de mur de la mémoire depuis sa formalisation en 1995 par Wulf[WM95]. D’un autre côté, l’exploitation du parallélisme d’instruction se heurte à une problématique de complexité croissante. Concernant l’allongement des pipelines, on observe ainsi chez Intel, un pic à 30 niveaux pour les Pentium 4, contre 14 pour les Core 2 Duo qui suivent. Avec des pipelines très longs, les opérations impliquant une purge de ces derniers deviennent très pénalisantes avec un temps important de re-remplissage de ce dernier. Le réordonnancement des instructions, lui, se trouve limité par les dépendances entre ces dernières, limitant les gains au-delà d’un certain seuil.

Table des matières

INTRODUCTION
I Contexte
1 Introduction au calcul haute performance
1.1 Introduction
1.2 Historique du calcul haute performance
1.3 Évolution actuelle des architectures
1.3.1 Un équilibre entre débit et latence
1.3.2 L’arrivée du multicœur
1.3.3 Processeur versus GPGPU
1.4 Les défis de l’Exaflops
1.4.1 Gestion de l’énergie
1.4.2 La mémoire
1.4.3 Nombre de cœurs
1.4.4 Pannes
1.4.5 Entrées/sorties
1.4.6 Résumé
1.5 Environnement de calcul de la thèse
1.6 Modèles d’exécution
1.7 Modèles de programmation
1.7.1 Modèle à mémoire partagée ou distribuée
1.7.2 MPI : Message Passing Interface
1.7.3 Threads : pthread, OpenMP
1.7.4 CUDA / OpenCL
1.7.5 Tâches : Cilk, OpenMP-3
1.7.6 Les PGAS
1.7.7 Résumé
1.7.8 Problème du mélange
1.7.9 Le projet MPC
1.8 Question ouverte sur les DSL
1.9 Le système d’exploitation
1.10 Applications tests
1.11 Conclusion
2 Gestion de la mémoire
2.1 Introduction
2.2 Le système d’exploitation
2.2.1 Problématiques du multiprogramme/multiutilisateur
2.2.2 Adresses virtuelles, adresses physiques
2.2.3 Segmentation et pagination
2.2.4 Notion de processus et threads
2.2.5 Espace noyau et utilisateur
2.3 Interface avec les applications
2.3.1 Les appels systèmes
2.3.2 Fautes de pages
2.4 L’allocateur mémoire (malloc)
2.4.1 Interface
2.4.2 Fragmentation
2.4.3 Ramasse-miettes
2.4.4 Problématique d’implémentation
2.5 Accès à la mémoire
2.5.1 Les caches
2.5.2 MMU et TLB
2.5.3 Grosses pages
2.5.4 Accès mémoire non uniformes : NUMA
2.5.5 OS et support NUMA
2.6 Conclusion
II Contribution
3 Interférences des mécanismes d’allocations
3.1 Pagination et associativité
3.2 Politiques de pagination
3.2.1 Pagination aléatoire : Linux
3.2.2 Coloration de pages
3.2.3 Grosses pages
3.2.4 Conclusion
3.3 Résultats expérimentaux
3.3.1 Protocole expérimental
3.3.2 Résultats des NAS séquentiels
3.3.3 Résultats des NAS parallèles
3.3.4 Résultats sur EulerMHD
3.4 Pagination et stratégie de malloc
3.4.1 Impact de l’implémentation de malloc
3.4.2 Problématique des paginations régulières
3.4.3 Associativité des caches partagés
3.4.4 Parallélisme des accès en lecture et écriture
3.4.5 Effet de la table des pages et des TLB
3.4.6 Impacte de la table des pages
3.5 Analyse générale et recommandations
3.5.1 Conséquence sur les politiques de pagination
3.5.2 Extension matérielle pour les grosses pages ?
3.5.3 Conséquence sur malloc
3.6 Outil d’analyse
3.6.1 Objectifs
3.6.2 Points techniques sur la méthode
3.6.3 Informations collectées
3.7 Application de règles de décalage
3.8 Conclusion
4 Mécanismes d’allocations parallèles et contraintes mémoires
4.1 Approche générale
4.2 Description du besoin
4.3 Aspects génériques des allocateurs
4.3.1 Gestion des blocs libres
4.3.2 Fusion et scission de blocs
4.3.3 Contraintes d’alignements
4.3.4 Placement des métadonnées
4.4 Allocateurs disponibles
4.4.1 Linux : dlmalloc et ptmalloc
4.4.2 Hoard
4.4.3 Jemalloc
4.4.4 TCmalloc
4.4.5 MAMA
4.5 Impact des allocateurs
4.6 Structure de l’allocateur
4.6.1 Organisation générale
4.6.2 Gestion des blocs
4.6.3 Discussion à propos des petits blocs
4.6.4 Suivi des macro-blocs alloués
4.6.5 Surchage possible de la fonction de libération
4.6.6 Libérations distantes
4.6.7 Realloc
4.7 Réutilisation des gros segments
4.7.1 Méthode de réutilisation de TCMalloc
4.7.2 Méthode proposée
4.7.3 Recomposition de gros segments
4.7.4 Problème de surallocation
4.8 Remise à zéro pour calloc
4.9 Destruction du tas
4.10 Adaptation consommation versus performances
4.11 Aspect NUMA
4.12 NUMA et initialisation
4.13 Gestion de segments utilisateurs
4.14 Méthode d’implémentation
4.15 Évaluation
4.15.1 Micro-benchmarks
4.15.2 Résultats sur sysbench
4.15.3 Résultats sur la simulation numérique Hera
4.16 Bilan général
4.17 Discussion d’améliorations possibles
4.17.1 Niveaux topologiques
4.17.2 Politique de consommation dynamique
4.17.3 Surcharge de mmap/munmap ?
4.17.4 Modification de Jemalloc ?
4.17.5 API, sémantique NUMA ?
5 Problématique de remise à zéro de la mémoire
5.1 Évaluation du problème de performance
5.2 Utilisation de grosses pages
5.3 Le problème de la remise à zéro
5.4 Solutions existantes
5.5 Proposition : réutilisation des pages
5.6 Extension de la sémantique mmap/munmap
5.7 Détails d’implémentation
5.7.1 Modification de Linux
5.7.2 Capture des zones sans réutilisation ?
5.7.3 Limite de consommation et réclamation
5.7.4 Intégration dans les allocateurs
5.8 Résultats expérimentaux
5.8.1 Micro-benchmark
5.8.2 Application HydroBench
5.8.3 Application Hera
5.9 Conclusion
6 Étude complémentaire sur le problème de consommation : KSM
6.1 Introduction
6.2 Mémoire partagée
6.3 Principe de KSM
6.3.1 L’idée maîtresse
6.3.2 Fonctionnement interne
6.3.3 Marquage des pages
6.3.4 Activation et configuration
6.4 Test sur Hera
6.4.1 Méthode de test
6.4.2 Résultats
6.5 Limitations de KSM
6.6 Bénéfices potentiels de KSM
6.7 Piste non évaluée : extension de la sémantique de mmap
6.8 Conclusion
III Conclusion
CONCLUSION

Lire le rapport complet