Vers des noyaux de calcul intensif pérennes

Les codes scientifiques : un compromis entre maintenabilité et performances

    EDF R&D développe des logiciels de simulation pour de nombreux domaines scientifiques comme la mécanique des structures (Code-Aster [2]), la mécanique des fluides (Code-saturne [3, 4]), la thermique (Syrthes [5]) ou encore la neutronique (COCCINELLE [6] et COCAGNE [7]). Compte tenu de la complexité des problèmes à résoudre, les temps de résolution sont une très forte contrainte sur ces codes comme en témoigne le nombre de travaux effectués afin de réduire le temps de calcul des simulations [1, 8, 9, 10, 11, 12, 13, 14, 15]. Cette contrainte conduit à vouloir spécialiser fortement ces codes pour les machines sur lesquelles ils doivent s’exécuter. La chaîne de calcul COCCINELLE est dédiée à la simulation du fonctionnement des cœurs de centrale nucléaire. Elle est utilisée aussi bien pour optimiser des paramètres d’exploitation que pour répondre aux exigences croissantes de l’Autorité de Sûreté Nucléaire (ASN). Pour l’exploitant EDF, COCCINELLE permet ainsi de déterminer des paramètres de pilotage, comme la concentration en bore nécessaire à l’équilibre de la réaction en chaîne, ou des paramètres d’optimisations comme la « longueur naturelle de campagne » qui correspond à la durée d’exploitation du combustible nucléaire avant qu’un rechargement du cœur ne soit nécessaire. COCCINELLE permet également à EDF de déterminer des éléments nécessaires aux dossiers de sûreté. Par exemple, lors d’un rechargement de combustible nucléaire, un dossier de sûreté doit être envoyé à l’ASN en vue d’obtenir l’autorisation de redémarrage de la centrale. Ce dossier nécessite entre autres la détermination du « point chaud », c’est-à-dire l’emplacement du réacteur qui atteint la température la plus élevée lors du fonctionnement de la centrale. Le code COCCINELLE est utilisé afin de calculer les températures maximales pouvant être obtenues dans les différentes parties du réacteur et permet donc l’identification de ce point chaud.Afin de mieux prendre en compte certains phénomènes physiques, la chaîne de calcul COCAGNE a été mise au point. COCAGNE repose sur des modèles physiques plus complets que la chaîne COCCINELLE et permet donc d’effectuer des simulations plus proches de la réalité. Dans cette perspective, COCAGNE sert de code de référence afin d’estimer les erreurs liées au modèle physique de COCCINELLE [16]. COCAGNE a aussi pour vocation, à terme, de remplacer COCCINELLE. L’augmentation de la complexité des modèles induit une augmentation importante du nombre de calculs et donc, des contraintes sur les temps d’exécution. Par exemple, la validation par COCAGNE d’un calcul 3D COCCINELLE nécessite de traiter beaucoup plus d’inconnues. Un problème 3D COCCINELLE comportant 1 million d’inconnues sera validé par un calcul 3D COCAGNE sur un problème dit « crayon par crayon », correspondant à une discrétisation plus fine et comportant 100 millions d’inconnues [17]. Afin de pouvoir obtenir les résultats dans des délais raisonnables, il est important de réduire les temps de calcul de cette chaîne.

La composition de fonctions avec les langages procéduraux

   Afin de répondre de manière plus pérenne aux problèmes soulevés par notre exemple, il conviendrait de pouvoir composer les fonctions entre elles. Le rôle du vecteur Z est d’établir un lien entre les différents appels BLAS. La composition des fonctions entre elles permettrait de supprimer ce besoin et donc de conserver une seule boucle comme dans l’implémentation en C. La seule possibilité offerte par les langages procéduraux pour composer des fonctions entre elles passe par l’utilisation de fonctions d’ordre supérieur acceptant comme argument des pointeurs sur fonction. Outre la complexité d’utilisation induite par l’utilisation des pointeurs sur fonction, ces derniers introduisent un surcoût du fait de l’indirection et de l’impossibilité d’effectuer des optimisations interprocédurales. Sur notre 32 2×4Nehalem, ce surcoût est d’environ 30 cycles par appel de fonction. Lorsque le corps de cette fonction est suffisamment important, le surcoût peut être négligé. Ce n’est plus le cas lorsque le corps de la fonction de rappel est petit. Dans notre exemple, le corps de ces fonctions de rappel correspondrait à l’itération élémentaire des boucles équivalentes à l’implémentation BLAS et contiendrait donc très peu d’instructions. Par exemple, le corps de la fonction équivalent à la fonction cblas_saxpy contiendrait deux instructions flottantes (y=a*x+y), traitées en un cycle. Le surcoût d’une fonction de rappel étant d’environ 30 cycles, cette approche conduirait à une implémentation 30 fois plus lente que la version en C. En résumé,  dans le contexte du calcul numérique avec un langage procédural, le seul compromis entre maintenabilité et optimisation des performances est obtenu via l’utilisation de bibliothèques externes. Cependant, dans les cas où il n’existe pas de bibliothèque répondant exactement aux besoins de l’application, l’adaptation de l’application pour utiliser les bibliothèques existantes peut être contre-productive comme dans notre exemple. Il convient donc de trouver d’autres approches permettant de dépasser cette limite dans l’expressivité des opérations à réaliser

Autres solutions pour exploiter les structures de données

    Dans la section précédente, nous avons vu qu’il est impossible de décrire précisément les structure de toutes les matrices creuses avec les langages procéduraux. Avec ces langages, la seule solution permettant d’exploiter la structure d’une matrice consiste à implémenter les différentes opérations souhaitées manuellement. Pour contourner cette limitation, différentes approches ont été explorées. Nous allons en détailler quelques-unes ici. Certains algorithmes peuvent être optimisés en modifiant la structure des matrices. Cependant, cette restructuration des données a un coût important qui doit être amorti par le gain en performance induit. Les solveurs creux directs comme PaStiX [89] utilisent par exemple des outils d’analyse de la structure de la matrice comme Scotch [90] ou Metis [91]. Ces outils permettent de déterminer les échanges de lignes et de colonnes permettant d’aboutir à une structure plus adaptée pour l’algorithme de résolution utilisé. Dans les cas où un tel réordonnancement ne permet pas d’améliorer les performances, la question de l’exploitation de la structure de la matrice se pose. Une approche intéressante consiste à laisser l’utilisateur implémenter les opérations élémentaires sur ses matrices (ex : produit, somme, accès aux éléments) sous la forme de fonctions de rappel  (callbacks). En s’appuyant sur ces fonctions de rappel, il est possible de mettre au point une couche logicielle implémentant des algorithmes de plus haut niveau. Le solveur PetSc [92, 93, 94] propose ce type de fonctionnalité. Cela peut également permettre de mettre en place des matrices non stockées dont les éléments sont calculés « à la volée ». Cette approche permet à l’utilisateur de choisir de manière générique parmi un catalogue d’algorithmes tout en exploitant une partie des spécificités des structures de ses matrices. Cependant, cela suppose encore une fois de disposer, pour chaque opération élémentaire, d’une implémentation optimisée pour chaque type de matrice et pour chaque architecture matérielle ciblée. Tout ce travail est laissé à la charge de l’utilisateur de la bibliothèque et ne permet pas toujours d’aboutir à un compromis satisfaisant entre performances et maintenabilité des codes. Enfin, une dernière solution consiste, comme pour le problème des expressions vectorielles étudié précédemment, à définir un langage. En effet, la définition d’un langage permettant de décrire de manière abstraite la structure des matrices (denses, bande, …) devrait permettre de dissocier les algorithmes de haut niveau, les structures de matrices et leur stockage. Cette structure pourrait donc être utilisée pour déterminer les structures de données et donc les formats de stockage optimaux.

Les processeurs : des machines parallèles

   L’amélioration des procédés de fabrication permet de multiplier par deux le nombre de transistors par unité de surface tous les deux ans [98], et ce depuis 1971. Cette réduction permet d’augmenter la fréquence et donc la puissance des processeurs. De plus, les transistors supplémentaires disponibles permettent l’ajout de nouvelles fonctionnalités augmentant le nombre d’opérations effectuées par cycle. Entre autres améliorations apportées aux processeurs au cours des dernières années, mentionnons ici les unités de pré-chargement des données (prefetching), de prédiction de branchement, ou encore l’augmentation de la taille de la mémoire cache. Le graphique de la figure 2.1 montre les choix effectués par INTEL afin d’améliorer la puissance de calcul de ses processeurs 11 12. Nous avons distingué différents éléments permettant l’amélioration de la puissance de calcul des processeurs.

Les FPGAs (Field-Programmable Gate Array)

   Sont des puces comportant un circuit logique programmable. Les FPGA permettent de programmer une architecture et d’obtenir, ainsi, une puce spécialisée pour le problème que l’on veut traiter. Certains PPU, comme SPARTA, sont construits autour d’un FPGA. Les FPGA sont couramment utilisés pour le décodage de séquences ADN [111]. Mais pour les calculs nécessitant l’utilisation de nombres flottants, les FPGA semblent aujourd’hui peu adaptés car l’implémentation d’unités de calcul flottant sur FPGA ne laisse pas beaucoup de place pour ajouter d’autres unités de calcul. Par la suite, nous ne nous intéresserons donc plus à cette catégorie d’accélérateurs.

Introduction à l’optimisation pour GPUs NVIDIA

   Dans la section précédente, nous avons brièvement présenté l’architecture des processeurs X86_64. Afin d’exploiter efficacement les cœurs disponibles, le code applicatif doit exposer deux niveaux de parallélisme correspondant à une hiérarchie des unités de calcul. Un premier niveau de parallélisme (multicœur) permet d’exploiter les différents cœurs disponibles. Un second niveau de parallélisme (SIMD) permet d’exploiter les différentes unités de calcul disponibles dans chaque cœur. Dans cette section, après avoir présenté un historique de l’architecture des accélérateurs graphiques, nous verrons que l’architecture des GPUs modernes conduit égalementle code applicatif à exposer deux niveaux de parallélisme. Nous verrons que pour exploiter efficacement un GPU, les contraintes d’optimisations conduisent à envisager l’architecture du GPU comme un processeur multicœur disposant de larges unités vectorielles, voire comme un processeur vectoriel.
Historique Dans cette section, nous allons présenter l’évolution de l’architecture des accélérateurs graphiques afin de comprendre l’émergence des architectures actuelles. Le lecteur intéressé pourra également se référer à [123]. En 1988 le studio d’animation Pixar publie RenderMan Interface Specification [124, 125], une interface de bibliothèque permettant d’unifier l’interface de programmation pour les différentes bibliothèques de rendu photoréaliste de scènes 3D. RenderMan permet de dissocier les activités de modélisation et de rendu graphique. Afin de combler le manque d’expressivité des bibliothèques procédurales, RenderMan inclut un DSL dédié au rendu photoréaliste : RenderMan Shading Language [126]. L’utilisation de ce DSL permet aux utilisateurs de définir leurs propres effets visuels. RenderMan est une interface de rendu graphique photoréaliste et ne cible pas les applications de rendu en temps-réel : le rendu des 77 minutes du film d’animation Toy Story a pris près de 4 mois sur 300 processeurs [127]. En 1992, Silicon Graphic Inc (SGI) propose le standard OpenGL [128] afin de faciliter le développement et la portabilité des applications scientifiques et industrielles nécessitant un rendu de scènes 3D en temps réel. Afin de permettre un rendu des images en temps réel, OpenGL ne peut pas prendre en charge toutes les fonctionnalités de RenderMan. En particulier, OpenGL ne propose pas de DSL. Les différents types de traitement sont prédéfinis par le standard. Ceci permet en contrepartie des implémentations très efficaces capables d’afficher des scènes 2D entemps réel sur les stations de travail disponibles à cette époque. À partir de 1995, le rendu de scène 3D en temps réel trouve un débouché auprès du grand public grâce aux jeux vidéos. L’ouverture de ce marché, très important en volume, permet de financer le développement d’accélérateurs matériels dédiés au support d’OpenGL. Afin d’améliorer la qualité graphique et les performances des jeux vidéo, des accélérateurs 3D supportant matériellement une partie des traitements OpenGL sont alors intégrés aux consoles de salon et aux ordinateurs grand public [129, 130].

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Chapitre 1  Introduction
1.1 Les codes scientifiques : un compromis entre maintenabilité et performances
1.2 Recensement des solutions pour le domaine de l’algèbre linéaire 
1.2.1 Limitation des bibliothèques procédurales
1.2.2 Une plus grande expressivité des opérations d’algèbre linéaire
1.2.3 Vers une description plus avancée de la structure des matrices
1.2.4 Notre objectif : la maintenabilité des langages dédiés et les performances des bibliothèques optimisées
1.3 Legolas++ : une bibliothèque dédiée aux problèmes d’algèbre linéaire
1.4 Objectif de la thèse : conception d’une version multicible de Legolas++
1.5 Plan de lecture 
Chapitre 2 Programmation multicible : une structure de données par cible ?
2.1 Présentation des différentes architectures cibles 
2.1.1 Les processeurs : des machines parallèles
2.1.2 Du processeur au processeur assisté : les accélérateurs de calcul
2.1.3 Introduction à l’architecture des processeurs X86_64 et à leur programmation
2.1.4 Introduction à l’optimisation pour GPUs NVIDIA
2.1.5 Comparaison des stratégies d’optimisation CPU et GPU
2.2 Optimisation pour CPU et pour GPU d’un exemple plus complexe
2.2.1 Présentation du problème
2.2.2 Implémentations optimisées
2.3 La plate-forme de tests : les configurations matérielles 
2.4 Analyse des performances : à chaque architecture sa structure de données
2.5 Programmation multicible : un code source unique, différents exécutables optimisés 
Chapitre 3 État de l’art des environnements de développement parallèle multicible
3.1 Vers un niveau d’abstraction plus élevé
3.2 Éléments de discrimination 
3.2.1 Type de conception de l’environnement
3.2.2 Niveau d’abstraction du parallélisme
3.2.3 Support des accélérateurs de calcul
3.2.4 Adaptation du stockage à l’architecture matérielle
3.3 Différentes approches pour permettre le développement d’applications parallèles multicibles
3.3.1 Les approches basées sur la programmation événementielle
3.3.2 Les approches basées sur les patrons parallèles
3.3.3 Les approches basées sur la programmation par tableaux
3.3.4 Les autres approches
3.3.5 Synthèse
3.4 Choix stratégique : positionnement de MTPS
Chapitre 4 MTPS : MultiTarget Parallel Skeleton
4.1 Modèle de programmation : introduction aux contextes vectoriels
4.1.1 Modèle d’architecture matérielle
4.1.2 Rappel du cas d’application : résolution du système AX = B
4.1.3 Introduction au modèle de données
4.1.4 Un parallélisme restreint aux opérations vectorisables
4.1.5 Extension de la structure de données
4.1.6 Les contextes vectoriels
4.2 Principes de fonctionnement de MTPS 
4.2.1 Choix technologiques d’implémentation
4.2.2 Définition et instanciation de la structure de données
4.2.3 Abstraction du parallélisme et accès aux données
4.2.4 Vue d’ensemble
4.3 Contraintes d’utilisation et architectures matérielles 
Chapitre 5 Conception et réalisation d’un démonstrateur multicible de Legolas++
5.1 Legolas++ : présentation de l’existant 
5.1.1 Les vecteurs
5.1.2 Les matrices
5.1.3 Les solveurs
5.2 Contraintes pour une version multicible de Legolas++ 
5.2.1 L’expérience MTPS : rappel des contraintes pour un code multicible
5.2.2 Famille de problèmes compatibles avec une implémentation multicible
5.3 Un démonstrateur de Legolas++ multicible  
5.3.1 Structures de données Legolas++ et vues parallèles
5.3.2 Un démonstrateur capable de cibler les différentes générations de processeurs X86_64
5.3.3 Utilisation et limitations du démonstrateur
Chapitre 6 Analyse des performances du démonstrateur
6.1 Premier cas : les blocs ont une structure bande symétrique 
6.1.1 Structure de la matrice A et paramètres du problème
6.1.2 Performances d’une implémentation idéale
6.1.3 Performances de MTPS
6.1.4 Performances du démonstrateur Legolas++ multicible
6.1.5 Bilan : accélérations obtenues
6.2 Deuxième cas : les blocs ont une structure bande symétrique sur deux niveaux
6.2.1 Structure de la matrice A et paramètres du problème
6.2.2 Performances du démonstrateur
6.3 Bilan 
Chapitre 7 Conclusions et perspectives
7.1 Bilan
7.2 Perspectives
Annexe
Annexe A Du polymorphisme dynamique au polymorphisme statique
A.1 Programmation orientée objet
A.2 La programmation générative
A.3 Avantages de la programmation générative
Annexe B Introduction aux formats de stockage creux Compressed Row Storage
Annexe C Définitions Legolas++
C.1 Définition d’une matrice Legolas++
C.1.1 Concept C++ de définition de matrice Legolas++
C.1.2 Matrice Legolas++ à un niveau
C.1.3 Création d’une matrice à plusieurs niveaux
C.2 Les solveurs
Glossaire
Bibliographie

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *