Babel : optimisation séquentielle

Sommaire

Introduction

L'optimisation séquentielle consiste à diminuer les besoins en ressources (temps d'exécution ou mémoire) au niveau des processus. Le travail se fait donc dans le cadre des performances de chaque processus et non pas au niveau de leurs interactions (ce sujet est traité dans la page web optimisation MPI) ou au niveau des entrées/sorties (voir page optimisation des entrées/sorties).

Cette page a pour but de vous donner des éléments de reflexion et des pistes pour réduire les ressources consommées par votre code. Certains aspects seront illustrés par de petits exemples. Cependant, il n'est pas possible d'être exhaustif.

Méthodologie

Comme déjà expliqué dans la page Optimisation : introduction, il faut commencer par profiler votre application pour déterminer les sections de code qui prennent le plus de temps (ou de mémoire) afin de déterminer les endroits les plus pertinents à optimiser. Cette étape est absolument nécessaire car il est souvent très difficile de deviner où les ressources sont les plus utilisées (et les erreurs d'appréciation sont généralement la règle).

De plus, un profilage initial sera très utile pour comparer les gains en performance obtenus par la suite.

Il faut bien entendu commencer par s'attaquer aux parties les plus consommatrices et aller progressivement vers des sections moins gourmandes. Il ne sert à rien d'aller trop loin car les gains potentiels diminuent très rapidement par rapport au temps et au travail nécessaires pour y parvenir.

La procédure à suivre sera découpée en deux phases.

La première forme d'optimisation et souvent la plus importante se fait lors de la conception. Il s'agit de choisir les bons algorithmes. Idéalement, c'est aussi ici que vous avez à décider quelles bibliothèques externes vous allez utiliser.

Dans une deuxième phase, lorsque le code de calcul fonctionne correctement, l'optimisation peut se dérouler en plusieurs étapes :

  1. Choisir les bonnes options de compilation ;
  2. Effectuer un profilage ;
  3. Choisir une section de code à améliorer ;
  4. Optimiser la zone choisie ;
  5. Vérifier que les résultats sont corrects ;
  6. Vérifier si il y a gain de performance ;
  7. Une fois satisfait pour cette section, retourner au point 3 ;
  8. Effectuer un profilage et éventuellement reboucler.

En cours d'optimisation, il peut être utile de refaire des profilages pour s'assurer que votre application se comporte bien comme attendu.

Algorithmes et conception

Avant même d'écrire votre application, lors de la phase de conception, il est essentiel de choisir les bons algorithmes. Il faut décider lesquels sont les plus adaptés à votre code de calcul en terme de type de problème traité, de taille, d'extensibilité (nombre de processus),… Il ne faut pas non plus sous-estimer la taille des problèmes qui seront étudiés et essayer de concevoir un code qui pourra encore servir dans plusieurs années (voire bien plus).

Durant l'existence d'un code, il est toujours possible de revenir sur ces choix mais il est plus simple de partir dans la bonne direction dès le début. Un code ayant une longue durée de vie changera probablement d'algorithmes au cours du temps. Certaines bibliothèques permettent également de changer facilement d'algorithmes sans avoir à modifier fondamentalement votre code (par exemple en utilisant PETSc).

Bibliothèques

De nombreuses bibliothèques de calcul numérique et scientifique existent. Celles-ci sont généralement fortement optimisées par les constructeurs ou par des équipes de développeurs spécialistes dans ces domaines. Il est donc fortement conseillé de les utiliser plutôt que de tenter de réinventer la roue. Recréer tout par vous même demande un travail souvent considérable et il est très difficile d'égaler leurs performances.

L'utilisation de bibliothèques préexistantes est donc crucial pour la performance de votre code de calcul.

Les différentes bibliothèques disponibles sur Babel sont présentées sur [[web:su:scalaire:babel:bibliotheques|cette page.]]

La bibliothèque MASS

Une bibliothèque pouvant vous donner sans efforts et sans modifications de vos sources des gains parfois très importants en performance est la bibliothèque [[web:su:scalaire:babel:biblis:mass|MASS. Cette dernière remplace les principales opérations mathématiques classiques (cos, sin, exp, sqrt, power,…) par des versions beaucoup plus performantes. L'inconvénient est une réduction très légère (et négligeable pour la plupart des applications) de la précision de ces opérations.]]

Compilateur

Options d'optimisation

L'optimisation séquentielle la plus simple qui peut être faite est de changer les options d'optimisation du compilateur. Le plus gros avantage est que vous n'avez pas à modifier votre code source.

Les options principales concernant l'optimisation vous sont décrites dans la page suivante. Attention, n'oubliez jamais de vérifier que les résultats donnés par votre application sont toujours corrects. En effet, des options agressives peuvent modifier le comportement de votre application, faire apparaître un bug de votre application ou générer un exécutable incorrect. Vérifiez également qu'il y a bien un gain en terme de performance car là aussi il peut y avoir des pertes.

Lors de vos tests avec les options du compilateur, il peut être intéressant de jeter un ?il à la documention du compilateur ou au document PDF Using the IBM XL Compilers for Blue Gene. Les autres options du compilateur peuvent également s'avérer utiles.

Aider le compilateur

Les compilateurs modernes et en particulier celui de la Blue Gene/P sont capables de faire beaucoup d'opérations d'optimisation que l'on devait faire à la main il y a encore quelques années (déroulage de boucle, fusion de boucles, calcul d'invariants,…). Actuellement, il vaut généralement mieux ne plus le faire car certaines de ces optimisations sont plus adaptées à certaines architectures. De plus, cela risque de compliquer le travail de l'optimiseur du compilateur et provoquer des pertes de performances.

Certaines choses sont à privilégier pour faciliter le travail du compilateur. Une liste non exhaustive et à résultats non garantis vous est donnée juste après. Notez que les conseils concernant des boucles ne sont à suivre que dans des boucles appelées de nombreuses fois et dont chaque passage ou itération est relativement court.

  • éviter les tests à l'intérieur d'une boucle ;
  • éviter d'appeller des fonctions ou sous-programmes dans les boucles ;
  • ne pas abuser des pointeurs ;
  • éliminer les GOTO qui empêchent le compilateur de faire des prédictions de branchements ;

Caches

L'accès à la mémoire étant généralement très lent, les processeurs disposent de mémoires caches beaucoup plus rapides qui servent d'intermédiaires entre les unités de calcul et la mémoire centrale. Les mémoires caches ont des latences moindres et permettent de stocker une partie du contenu de la mémoire au plus près du processeur. Babel possède 3 niveaux de caches appellés L1, L2 et L3. Les caches L1 sont les plus proches des coeurs de calcul et les plus rapides. Le deuxième niveau L2 est en réalité une unité de prefetching dont le rôle est d'essayer de charger de manière spéculative des données avant même qu'elles soient demandées par l'application. Le troisième niveau de taille plus importante mais plus lent sert de dernier niveau avant d'aller vers la mémoire centrale.

Les caractéristiques détaillées des caches de la Blue Gene/P sont données dans cette page.

Fonctionnement des caches

Lorsqu'un coeur de calcul souhaite accéder à une donnée en mémoire, il génère une instruction de chargement (load). Si cette donnée ne se trouve pas dans les mémoires0cachmsl elle doit être chargée directement à partir de la mémoire centrale. Les unités de calcul doivent alors attendre que la donnée soit transmise avant de pouvoir l'utiliser. Le temps d'attente est appellé la latence et est généralement exprimé en cycles d'horloge. Sur Blue Gene/P, la latence de la mémoire est de 104 cycles. Cela signifie que le coeur aurait eu le temps d'exécuter 104 instructions pendant ce temps. S'il fallait à chaque fois attendre que les données soient ramenées une par une de la mémoire centrale, les coeurs ne travailleraient pratiquement jamais !

Pour réduire ce problème, toute donnée chargée de la mémoire centrale est recopiée dans les caches. Si le coeur a de nouveau besoin de celle-ci et qu'elle se trouve toujours dans le cache, il devra attendre beaucoup moins longtemps (par exemple le cache L1 à une latence de 4 cycles pour un nombre en virgule flottante).

En pratique, les données ne sont pas chargées une par une mais sont groupées par ligne de cache. Chaque donnée se trouve à une adresse donnée en mémoire. Lors du chargement d'une ligne de cache, les données se trouvant à l'adresse demandée seront chargées ainsi que ses voisines (alignées sur un multiple de la taille de la ligne de cache). Si plus tard, le coeur à besoin de l'adresse suivante, elle sera probablement déjà dans le cache (sauf si la précédente se trouvait à la fin de la ligne de cache). Les économies en temps et en performance peuvent donc être très élevées. Les lignes de cache font 32 octets (4 flottants double précision) pour le cache de niveau L1 et 128 octets (16 flottants double précision) pour les L2 et L3.

Les mémoires caches ayant des tailles plus réduites que la mémoire centrale, elles ne peuvent pas contenir toutes les données. A chaque fois qu'une ligne de cache est chargée, elle écrase les données d'une ancienne. Selon le niveau de cache, différents algorithmes sont utilisés (voir cette page) qui vont décider de la ligne qui sera remplacée. Si des données effacées du cache doivent être à nouveau utilisées, il faudra de nouveau les chercher en mémoire centrale (si elles ne sont pas dans le cache de niveau suivant).

Le cache de niveau L2 de la Blue Gene/P a comme unique fonction de servir d'unité de prefetching (ou préchargement). Lorsqu'une donnée est demandée par le cache L1, le cache L2 va également chercher en mémoire centrale (en passant par le L3) la ligne de cache qu'il estime qui sera la suivante. Il peut détecter automatiquement des accès mémoire espacés de façon régulière (avec des pas de maximum 128 octets). Cela permet de charger à l'avance des lignes qui pourraient être utiles au cache L1 peu après. Le cache L2 peut ainsi charger 7 flux en lecture et également 7 en écriture. A noter également qu'une ligne de cache L2 fait 128 octets et peu donc correspondre à 4 lignes pour le L1. Le cache L3 a également une unité de prefetching qui tente d'aller chercher en mémoire centrale les futures requêtes du cache L2.

Lorsque des données sont modifiées ou écrites par un coeur, elles sont réécrites de manière synchrone vers la mémoire centrale (approche de type write-through).

Optimisation de l'utilisation des caches

L'accès à la mémoire centrale étant extrêmement coûteux, il est essentiel d'utiliser le plus possible les mémoires caches.

Pour pouvoir en profiter au mieux, il faut essayer tout d'abord d'utiliser le contenu complet de chaque ligne de cache. Par exemple, si on accède à des flottants double précision dans un tableau espacés chacun de 4 éléments, on fera un mauvais usage de cache de niveau L1. En effet, chaque élément utilisé se trouve sur une ligne de cache différente (une ligne de cache L1 fait 32 octets càd 4 flottants double précision). Dans ce cas, seul un élément sur 4 du cache aura une utilité. Les autres auront été chargé pour rien. Il faut donc essayer de travailler sur des données contiguës en mémoire. C'est ce qu'on appelle la localité spatiale.

Dans une application idéale Blue Gene/P, il faudrait que tous les accès se fassent de façon contiguë en mémoire avec un maximum de 3 flux en lecture et 3 en écriture (le cache L1 peut fournir 3 flux de données dans chaque sens de manière optimale, le cache L2 peut en alimenter 7). Des accès contigus en mémoire sont également optimaux pour les unités de prefetching qui peuvent ainsi chercher en mémoire les données avant même que les coeurs en aient besoin. De cette manière, une grande partie des latences peut être masquée.

Autre règle à respecter, utiliser plusieurs fois les même données. En effet, si des données se trouvant dans les caches sont réutilisées plusieurs fois, il n'est pas nécessaire d'aller les rechercher en mémoire à chaque fois qu'on en a besoin. C'est ce qu'on appelle la localité temporelle.

Pour exploiter la localité temporelle, une approche souvent suivie est de travailler par blocs. Au lieu d'effectuer une opération sur chaque élément d'un gros tableau, suivie par une autre opération sur tous les éléments de ce même tableau,…, il est plus performant de prendre un bloc de ce tableau qui tient dans le cache, de faire la série d'opérations sur tous les éléments du bloc, de passer au bloc suivant et d'effectuer la série d'opérations,…

Dans le pire des cas, des accès aléatoires en mémoire ou avec des écarts importants (plus de 128 octets) rendent très difficile l'utilisation des caches et l'obtention de bonnes performances. Dans ce cas, si les données utilisées nécessitent plusieurs opérations chacune, une optimisation possible consiste à créer des tableaux intermédiaires qui contiennent une copie de ces données. Ces tableaux ne doivent pas être trop gros pour tenir dans le cache. L'avantage ici sera de pouvoir charger toutes les données dans le cache, de réaliser des opérations dessus et ensuite de recopier les nouvelles données dans leurs structures d'origine. Ce type d'optimisation ne donne des gains en performance que si le nombre d'opérations à effectuer par élément est suffisamment important car il nécessite deux opérations de copie supplémentaires.

Optimiser l'utilisation des caches se fait donc en écrivant des algorithmes exploitant les localités spatiale et temporelle. Seule la réutilisation des données dans les caches couplée avec l'utilisation de tout le contenu des lignes de cache permettent de s'approcher de la puissance maximale de la machine.

Sur la Blue Gene/P, il est conseillé d'optimiser principalement pour le cache de niveau L1. Le cache L2 étant essentiellement une unité de prefetching, il n'y a pas d'optimisation à faire. Pour le L3, les latences sont déjà importantes (50 cycles) et il vaut mieux porter les efforts sur le L1.

Unité double de calcul en virgule flottante (double FPU)

L'unité double de calcul en virgule flottante (double FPU ou double Floating Point Unit) est une unité de calcul pour nombres réels à virgule flottante double précision (64 bits, 8 octets). Cette unité peut réaliser des opérations identiques ou relativement proches en parallèle sur 2 nombres en virgule flottante (par exemple : opérations sur des complexes, additions,…). Il s'agit d'une approche de type SIMD (Single Instruction Multiple Data) assez similaire à ce qui est fait dans les processeurs Intel avec les jeux d'instructions SSE. Cette unité exécute jusqu'à 2 opérations en virgule flottante par cycle. Si les opérations sont de type FMA (Fused Multiply-Add) càd une multiplication et une addition couplées (a*b+c), 4 opérations par cycle pourront être exécutées. Par contre, la double FPU ne supporte pas les exceptions IEEE (norme IEEE 754, détection des divisions par zéro, des overflows, des NaNs,…) lorsqu'elle est utilisée en mode SIMD. Il faut donc éviter de l'utiliser en phase de développement.

cn2rack

Utilisation et contraintes

Attention : pour pouvoir utiliser l'unité double de calcul en virgule flottante, il est nécessaire de compiler avec l'option -qarch=450d (celle-ci est activée par défaut à l'IDRIS).

L'utilisation de cette unité est malheureusement assez délicate à mettre en ?uvre. En théorie, si elle est utilisée pour toutes les opérations et qu'elle est alimentée correctement en données (voir l'optimisation des caches), un facteur 2 peut être gagné sur les noyaux de calcul. En pratique, il est souvent assez difficile de l'exploiter et les gains réels sont moindres. Ce n'est malgré tout pas une piste à négliger car dans certains cas les bénéfices peuvent être importants. Avant de vous attaquer à ce type d'optimisation, il est fortement conseillé d'avoir déjà réalisé une optimisation réussie de l'utilisation des caches. En effet, il ne sert à rien d'utiliser la double FPU si elle ne peut être alimentée en données suffisamment vite.

Le plus simple pour profiter des capacités de cette unité est d'utiliser des bibliothèques déjà optimisées telles que MASS ou ESSL.

A l'opposé, il est possible d'utiliser directement des fonctions fournies par IBM. Celles-ci travaillent sur des paires d'éléments en double précision (des nombres complexes par exemple). C'est le moyen le plus sûr d'utiliser la double FPU mais cela nécessite un travail de réécriture des procédures assez lourd. L'autre inconvénient majeur est bien entendu que ces fonctions ne sont pas portables sur d'autres architectures. Cette approche n'est donc à utiliser que pour des équipes ayant des moyens importants et de grosses allocations sur Blue Gene/P. Toutes ces fonctions sont détaillées dans le document Blue Gene/P Application Development (en PDF).

Alignement mémoire

Pour qu'un coeur de calcul utilise la double FPU, les données doivent avoir un alignement mémoire naturel (càd sur 16 octets pour les flottants en double précision). Cela veut dire que l'adresse mémoire d'une paire de données (la double FPU travaille toujours par paire) doit obligatoirement commencer à une adresse multiple de 16. Cette contrainte est assez forte et empèche très souvent le compilateur d'utiliser cette unité de calcul.

Le compilateur peut déterminer l'alignement mémoire (ou même le modifier) pour toutes les variables globales et pour les variables locales qui ne sont pas des pointeurs. L'alignement des variables pointeurs ou passées en argument par référence ne peut généralement pas être déterminé.

Pour les pointeurs ou arguments passés par référence, l'alignement sur 16 octets peut être testé manuellement en C/C++ en utilisant par exemple :

void fct(double *x) {

if ( (int)x & 0xf==0 )  x is 16 bytes aligned
else                    x is not 16 bytes aligned
}

Pour le Fortran, il n'y a malheureusement pas de solution.

Si vous activez lors de la compilation des options d'IPA (InterProcedural Analysis, par défaut avec un niveau d'optimisation 4 ou 5), le compilateur peut dans certains cas déterminer l'alignement. Le compilateur peut également faire du versioning, càd générer 2 versions du code, une utilisant les instructions doubles et une autre pas. C'est lors de l'exécution que le choix sera fait. Cela entraîne évidemment des surcoûts qui peuvent réduire les performances surtout sur les boucles courtes.

L'option du compilateur -qattr permet d'obtenir certaines informations sur l'alignement mémoire (un fichier avec l'extension .lst est créé lors de la compilation).

Vous trouverez des informations générales à propos de l'alignement mémoire sur Wikipedia.

Aider le compilateur

A moins d'utiliser les fonctions non portables d'IBM qui utilisent directement la double FPU, il va falloir faciliter le travail du compilateur. Voici une liste de propositions/idées pour l'aider :

  • Organiser les données en paires adjacentes (déclaration et utilisation) ;
  • Utiliser les pragmas spécifiant que les données sont alignées :
    • en C/C++ : __alignx(alignement,adresse)
    • en Fortran : ALIGNX(alignement,nom_variable) Attention : vous garantissez qu'elles le sont. Il n'y aura pas de vérifications ;
  • Préciser l'absence d'aliasing (chevauchement des données) en C : #pragma disjoint (a,b) ou restrict en C99 ;
  • Eviter l'aliasing et éventuellement passer par des variables locales

void test(double *a,double *b){

    double a0=a[0],a1=a[1],...;
    ...
    b[0]=b0;b[1]=b1;
  }
* Avoir des boucles avec un nombre d'itérations connu dès la compilation ;
* Utiliser select à la place de if/then/else ;
* Pour les boucles très courtes : désactiver la double FPU
  * en C : ''#pragma nosimd''
  * en Fortran : ''!IBM* NOSIMD''
* Utiliser des pas de 1 pour les accès mémoire ;
* Ne pas utiliser de tableaux à taille implicite en Fortran (''dimension(*)'') ;
* Eviter les appels de fonctions dans les boucles internes ;
* Eviter les dépendances entre itérations dans une boucle.

Options du compilateur

Certaines options du compilateur sont nécessaires pour générer un exécutable exploitant l'unité double de calcul en virgule flottante. D'autres ont une influence sur celle-ci. En voici les principales :

  • -qarch=450d : cette option doit être positionnée pour produire du code SIMD (par défaut sur Babel) ;
  • Le compilateur génère du code SIMD pour exploiter la double FPU dès que l'on utilise une des options suivantes (en plus de -qarch=450d) :
    • -O3, -O4 ou -O5
    • -qhot=simd
    • -qhot
  • -qarch=450 ne génère pas de code pour la double FPU ;
  • -qsigtrap désactive la double FPU (car il n'y a pas d'exceptions IEEE si la double FPU est employée) ;
  • -qdebug=diagnostic affiche lors de la compilation l'analyse des boucles et si elles utilisent les instructions doubles ou pas ;
  • -qreport -qattr -qsource -qlist : créent un fichier .lst contenant de nombreuses informations sur l'utilisation de l'unité double.

Conseils divers

Cette rubrique fournit quelques petits conseils pour aider à améliorer les performances séquentielles d'un code de calcul :

  • Eviter les tests à l'intérieur des boucles de calcul ;
  • Eviter les appels de procédure à l'intérieur des boucles de calcul ;
  • Eviter les références indirectes à la mémoire ;
  • Eviter les accès aléatoires à la mémoire ;
  • Eviter les conversions de type.

Occupation mémoire

Généralement, l'optimisation d'un code se fait sur le critère du temps d'exécution. Cependant, sur des architectures comme la Blue Gene/P, la mémoire par coeur de calcul est relativement limitée (512 Mo). Certaines applications peuvent se retrouver avec des problèmes d'occupation mémoire.

L'optimisation de la consommation mémoire consiste donc à réduire les besoins en mémoire d'une aplication.

Réduire la consommation de mémoire peut parfois avoir un impact négatif sur les performances en temps d'exécution. En effet, il est courant de créer des tableaux pour contenir des données qui seront réutilisées plutôt que recalculées. Il s'agit dans ce cas de choisir le meilleur compromis.

Pour optimiser l'occupation mémoire, plusieurs pistes peuvent être creusées. Encore souvent, de nombreux codes créent des tableaux de travail de taille plus grande que nécessaire. C'est fréquemment le cas de codes écrits à l'origine en Fortran 77 et qui n'utilisent pas les fonctions d'allocation dynamique de la mémoire. La solution ici est assez simple : faire de l'allocation dynamique de mémoire et n'allouer que ce dont on a besoin.

Beaucoup de codes sont également écrits avec une inhomogénéité dans le travail de chaque processus. Un processus peut par exemple se charger de distribuer ou collecter des données à l'ensemble des processus de l'application. Cette approche est à éviter car la taille des structures de données à gérer sur celui-ci devient rapidement prohibitive lorsque le nombre de processus augmente. Cela est également mauvais pour l'extensibilité d'une application car ce processus peut saturer très facilement.

Une autre manière d'économiser de la mémoire est d'utiliser une approche de programmation mixte MPI et OpenMP (ou pthreads). En effet, les différents threads s'exécutant dans le même espace mémoire le partage. Cela permet d'éviter la duplication d'une partie des données.

La bibliothèque MPI consomme également des ressources mémoire. Il est possible de réduire ses besoins en modifiant certaines variables d'environnement. Vous trouverez la liste de celles-ci et leurs caractéristiques dans les annexes du document Blue Gene/P Application Development.

Dans certaines utilisations de la mémoire et particulièrement pour les codes faisant beaucoup de cycles d'allocations/désallocations de tailles variables, la mémoire peut se fragmenter. Cela peut avoir pour conséquence, l'impossibilité d'allouer des structures de données alors qu'il y a assez de mémoire libre. Ce phénomène est discuté sur la page suivante.

La bibliothèque libbgpidris développée à l'IDRIS peut vous aider à déterminer combien de mémoire votre application occupe.

Pour en savoir plus

Vous trouverez sur internet de nombreux documents traitant de l'optimisation séquentielle. La plupart du temps, ils concernent des processeurs plus standards mais la majorité des idées peuvent être adaptée à la Blue Gene/P.

Les principaux documents concernant la Blue Gene/P traitent également de l'optimisation ou peuvent vous aider à mieux comprendre le fonctionnement de Babel.