Turing : optimisation séquentielle

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 réflexion 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écialisés 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 considérable et il est souvent 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 Turing sont présentées sur cette page.

La bibliothèque MASS

Une bibliothèque pouvant vous donner sans efforts et sans modifications de vos fichiers source des gains parfois très importants en performance est la bibliothèque 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 de la précision de ces opérations, négligeable pour la plupart des applications.

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 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 documentation du compilateur. 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/Q sont capables de faire beaucoup d'opérations d'optimisation (déroulage ou fusion de boucles, calcul d'invariants,…) que l'on devait faire à la main il y a encore quelques années. 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’appeler 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 cache beaucoup plus rapides qui servent d'intermédiaires entre les unités de calcul et la mémoire centrale. Les mémoires cache ont des latences moindres et permettent de stocker une partie du contenu de la mémoire au plus près du processeur. Turing possède 2 niveaux de caches appelés L1 et L2. Les caches L1 sont les plus proches des cœurs de calcul et les plus rapides. Le second niveau de taille plus importante mais plus lent sert de dernier niveau avant d'aller vers la mémoire centrale.

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 cache.

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 8 éléments, on fera un mauvais usage du 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 64 octets càd 8 flottants double précision). Dans ce cas, seul un élément sur 8 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.

Autre règle à respecter, utiliser plusieurs fois les mêmes 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.

Conseils divers

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

  • Éviter les tests à l'intérieur des boucles de calcul ;
  • Éviter les appels de procédure à l'intérieur des boucles de calcul ;
  • Éviter les références indirectes à la mémoire ;
  • Éviter les accès aléatoires à la mémoire ;
  • Éviter 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/Q, la mémoire par cœur de calcul est relativement limitée (1 Gio, voire seulement 256 Mio si vous lancez 4 processus par cœur) : 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 application.

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 suivies. 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 hybride MPI et OpenMP (ou pthreads). En effet, les différents threads s'exécutant dans le même espace mémoire le partagent : 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/Q 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 reste assez de mémoire libre. Ce phénomène est discuté sur la page suivante.

Sur Blue Gene/Q, la mémoire de chaque est noeud est divisée par le nombre de processus (option –ranks-per-node de la commande runjob). Des 16 Gio, il faut retrancher la mémoire réservée au système d'exploitation (16 Mio) et celle en espace shared (64 Mio par défaut si plusieurs processus par noeud). Cette dernière valeur peut être modifiée si nécessaire en positionnant la variable BG_SHAREDMEMSIZE, mais un minimum est nécessaire pour la bibliothèque MPI (si insuffisant, plantage). En réalité, le partage par défaut n'est pas équitable entre tous les processus. Certains auront donc moins de mémoire disponible que d'autres. Il est possible de forcer un partage équitable en positionnant la variable d'environnement BG_MAPCOMMONHEAP à 1. Cependant, si vous le faites, la protection de la mémoire entre les processus ne sera plus aussi stricte. Cela peut rendre plus difficile le diagnostic de certains bugs.

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/Q.

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