S’il est toujours difficile d’optimiser un code existant, une méthodologie appropriée permet d’obtenir des résultats probants, durables et reproductibles. Dans ce premier article d’une série de deux, nous commencerons par l’évaluation et la validation des sources avant d’aborder la question de l’utilisation efficace du compilateur. Le mois prochain, nous nous focaliserons sur l’organisation des données, l’implémentation algorithmique et l’optimisation de la parallélisation.

Romain Dolbeau – HPC Fellow, CAPS Entreprise.

La performance en programmation est un sujet complexe, qui fait l’objet de nombreuses publications universitaires. Il existe évidemment un certain nombre de règles simples qu’un développeur disposant d’un minimum d’expérience peut appliquer à bon compte, à partir d’introductions et de tutoriels comme celui de Chellappa et al. [1]. L’idée de cet article est de proposer une approche de l’optimisation de code moins détaillée mais plus orientée vers la pratique. À partir de sources existantes, nous suggérons une méthodologie d’amélioration en un minimum de temps et d’effort, ainsi que quelques bonnes pratiques destinées à assurer la validité et l’efficacité du travail accompli.

La performance est une chose difficile à obtenir. D’abord parce que l’écriture d’algorithmes rapides est complexe, mais également parce que comprendre pourquoi l’efficacité manque est loin d’être trivial. Lorsque l’on doit améliorer la performance d’un code, des étapes bien connues peuvent être suivies de façon itérative : primo, identifier les segments qui interviennent pour la majorité du temps d’exécution de l’application ; secundo, analyser pourquoi ces segments sont si gourmands en temps ; tertio, améliorer leur performance en ciblant les goulets d’étranglement.

Cette méthode conventionnelle, basée sur la loi d’Amdalh [2], n’est toutefois que très succincte. Elle repose sur une vue globale de l’application, et non sur l’ensemble des détails que le programmeur doit impérativement prendre en compte. Il faut en effet bien comprendre que la performance n’est pas qu’une affaire de code. Elle dépend de l’ensemble du processus qui part du code et conduit à son exécution sur un ou plusieurs processeurs, à savoir :

1 – Les algorithmes utilisés

2 – Leur implémentation spécifique dans un langage donné

3 – L’organisation des données sur lesquelles reposent les calculs

4 – Les optimisations du compilateur qui convertit le code source en code binaire

5 – Les bibliothèques tierces dont le code dépend

6 – Le système matériel sur lequel il s’exécute.

Si l’objectif est véritablement la performance, aucun de ces points ne peut être ignoré, sauf à risquer une importante perte d’efficacité. Et bien que le processus d’écriture et d’exécution soit séquentiel à chaque étape, c’est toute la globalité de la chaîne qui doit être ciblée. Optimiser une étape pour certains états d’autres étapes ne garantit en rien qu’elle restera optimale une fois les autres modifiées.

Basée sur des années d’expérience dans l’optimisation de code, la stratégie décrite dans cet article se veut à la fois pragmatique et axée sur l’efficacité. Plutôt qu’une réécriture directe, la bonne approche consiste à d’abord tirer avantage des outils d’optimisation disponibles. Ce n’est qu’après avoir épuisé ces ressources qu’une réécriture totale ou partielle pourra éventuellement être envisagée. Concrètement, notre méthode repose sur quatre points clés :

– Reproductibilité : elle concerne à la fois les résultats du code (rapide mais faux n’est pas une option) et la mesure de la performance. Ce point est critique pour les codes dont la performance dépend des données, comme par exemple les algorithmes de convergence pour lesquels plusieurs jeux de données doivent être validés.

– Maintenance : même si l’on vise la performance ultime, le code doit rester maintenable. Cela peut paraître évident mais entre deux versions d’un code aux mêmes performances, celle qui se lit donc se maintient le plus facilement doit être privilégiée.

– Priorité : le temps doit être consacré en priorité aux améliorations susceptibles d’apporter les meilleurs résultats. Optimiser un kernel très finement est une tâche exaltante, mais trop d’optimisation équivaut parfois à une perte de temps. Lorsque une partie de code a été suffisamment travaillée, il n’est plus utile de continuer à l’améliorer.

– Performance : quand on est au clair avec l’ensemble des points évoqués ci-dessus, la performance devient plus facilement atteignable.
 

1 – La phase initiale d’évaluation et de validation

1.1 – Les test cases – Quand on travaille sur un code existant, il est tout aussi fondamental de maintenir la validité des résultats obtenus que de quantifier de façon fiable le gain ou la perte en performance d’une version modifiée et validée du code. Valider des résultats est une tâche délicate. Si certaines applications produisent des résultats qui dépendent entièrement des paramètres d’entrée, c’est loin d’être toujours le cas. Les codes impliquant des opérations flottantes de type IEEE754-2008 aboutissent à des approximations (sauf s’ils sont compilés avec des options de conformité stricte qui interdisent en pratique les gains en performance). Les codes Monte Carlo qui utilisent des nombres aléatoires produisent des résultats non reproductibles. Enfin, tous les algorithmes ne sont pas égaux en termes de précision numérique (cette problématique est couverte en détail par Higham [3]).

La première étape dans la phase initiale d’évaluation et de validation consiste donc à établir un ou plusieurs test case(s) caractérisés par les bonnes propriétés suivantes :

– Un temps d’exécution assez court pour réaliser des tests réguliers.

– Un temps d’exécution suffisamment long pour que les petites erreurs de résultats soient détectables et non masquées par les approximations numériques.

– Une bonne couverture de la part significative des calculs tant en termes de quantité de code que de type de données d’entrée. Par exemple, les toutes premières itérations de la propagation d’énergie dans un espace discret sont généralement pleines de zéros, et donc pas vraiment significatives. Les conditions de bornes n’étant pas atteintes, elles ne sont pas testées avant plusieurs itérations.

– Une procédure de validation claire qui atteste de la validité des résultats.

Tous ces éléments, ou au moins la plupart, devraient idéalement être fournis par les utilisateurs qui souhaitent exécuter le code en production. Quelques échanges sont à prévoir : les deuxième et troisième points, en particulier, ne sont pas toujours faciles à obtenir. Les codes impliquant des nombres aléatoires doivent être rendus explicites soit en fixant une sélection initiale, soit en précalculant un ou plusieurs jeux de valeurs. C’est généralement la meilleure façon d’assurer la reproductibilité.

La deuxième étape consiste à établir un ou plusieurs autres cas tests qui permettront de vérifier la performance du code. Ces cas seront plus importants, et donc plus long à exécuter, que ceux utilisés pour vérifier les résultats. Ils doivent aussi s’accompagner d’une procédure de validation claire pour que puissent être détectées les erreurs résiduelles non révélées par les cas plus petits. Il faut enfin qu’ils soient relativement proches du mode de production. Ces test cases peuvent s’avérer difficiles à construire pour les codes extrêmement longs et/ou larges. Il n’existe malheureusement pas de solution directe à ce problème tant la représentativité dépend fortement du type de code.

Terminons sur ce point en rappelant qu’améliorer un code qui contient des erreurs n’a aucun sens. Vérifier que le code se comporte normalement est donc une étape préliminaire fondamentale. Pour cela, plusieurs outils de validation à l’exécution peuvent être utilisés, notamment votre compilateur et la suite Valgrind qui traque les accès mémoire non alloués ou non initialisés. Toutes ces vérifications doivent être réalisées avant la phase d’optimisation, faut de quoi des comportements anormaux ne manqueront pas de se révéler par la suite.

1.2 – Quoi et comment mesurer – Si mesurer la performance peut sembler trivial (la commande time n’est-elle pas faite pour cela ?), cette problématique est en réalité assez complexe. Il faut en effet non seulement savoir quoi mesurer mais aussi comment mesurer. Heureusement, un certain nombre de dispositions peuvent être prises pour assurer la cohérence des mesures d’une exécution à l’autre.

Quoi mesurer est la première des décisions à prendre, sachant qu’au final, une procédure apparentée à time sera utilisée : lorsque le code est exécuté en production, seul compte pour l’utilisateur le temps d’exécution total. Ce temps d’exécution importe tout autant au programmeur puisqu’il impacte toute procédure de validation ou de quantification à grande échelle. Cette mesure est donc importante, mais elle n’est pas la seule. Une fois le profil d’exécution réalisé (voir section 1.3), le code se présente en différentes phases : prologue ou initialisation (soit généralement O(taille du problème)) ; une ou plusieurs étapes de calcul de complexité variable ; puis phase d’épilogue (soit là aussi généralement O(taille du problème)). La phase de calcul est souvent celle dont le coût est le plus élevé mais ce n’est pas toujours le cas. Les phases de prologue et d’épilogue sont typiquement dominées par des entrées/sorties et des mouvements de données, hors du contexte de cet article. Si ces mouvements prennent la majorité du temps d’exécution total alors soit le code ne pourra être que difficilement amélioré, soit le test case est trop petit pour obtenir une mesure significative.

La loi de Gustafson [4] indique que pour la majorité des codes, il existe une taille de problème assez importante pour que la phase de calcul domine le temps d’exécution de l’application. Cette loi doit absolument être prise en compte : même si le test case utilisé pendant la phase d’optimisation ne montre pas d’amélioration globale importante (en raison de phases de prologue et d’épilogue significatives combinées à la loi d’Amdhal), des cas de production plus larges le peuvent, tout simplement parce que le temps passer en calcul sera plus long. Il est donc important de suivre non seulement le temps d’exécution global mais aussi celui de chaque phase du code. Pour un facteur 2 de gain en performance sur une phase de calcul représentant 50 % du temps d’exécution, on obtient un facteur de 1,33 sur l’ensemble du code. Un facteur 2 sur une phase de calcul représentant 98 % du temps d’exécution en production constitue un facteur global d’amélioration de 1,96.

Deuxième décision à prendre, comment mesurer ? L’échelle de temps sur les ordinateurs varie de plusieurs ordres de grandeur. Pour un CPU à 2,5 GHz, un cycle prend 0,4 ns, ou 4×10^-10 s. Des temps d’exécution de l’ordre de l’heure prennent 10^14 cycles dont seuls les chiffres les plus significatifs sont intéressants. Inversement, la mesure en secondes d’une petite fonction de quelques milliers de cycles est de l’ordre de 10^-7 s, une précision si fine que la plupart des systèmes ne pourront la représenter, ce qui la rend totalement inutile.

Il faut garder ces ordres de grandeur à l’esprit pour choisir la bonne chronométrie. Pour toutes les mesures à l’échelle humaine (des dizaines de secondes ou plus), la fonction gettimeofday est adéquate. Pour des centaines de microsecondes ou moins (millions de cycles ou moins), les compilateurs x86_64 permettent d’appeler _rdtsc, qui renvoie le nombre courant de cycles CPU. Pour des échelles situées entre les deux, le choix est moins tranché. gettimeofday offre une précision théorique en microsecondes et devrait donc convenir. Mais _rdtsc retourne un entier sur 64 bits, qu’on peut aussi utiliser pour mesurer des milliards de cycles.

La cohérence des mesures est l’aspect du problème le plus fréquemment ignoré. Un code est rarement seul à tourner sur le système. Il s’exécute dans un environnement qui inclut l’OS, des applications internes tournant continuellement ou presque en tâche de fond, et éventuellement d’autres utilisateurs. Pour être fiables, les mesures doivent être réalisées sur un système aussi inactif que possible, c’est-à-dire dans lequel très peu de programmes s’exécutent au dessus de l’OS. Toute application autre peut influer sur les résultats en consommant de la bande passante mémoire, en mobilisant les bus inter-CPU, en polluant les caches, en utilisant les bus I/O ou même tout simplement en élevant la consommation électrique du CPU, ce qui affecte le comportement thermique des autres processeurs.

Ce n’est pas tout : le comportement de l’OS lui-même peut aussi altérer sensiblement la performance CPU. Toutes les machines contiennent de multiples cœurs, chacun avec son propre cache L1 (et souvent un second cache L2 privé). Le fait que l’OS positionne le code sur le même cœur ou non pendant toute son exécution influence fortement la performance puisque le déplacement d’un cœur à un autre nécessite de recharger les caches locaux. Le déplacement du code d’un socket à un autre dégrade les performances plus fortement encore : non seulement le cache partagé interne au socket (L3 sur Sandy Bridge) doit être rechargé, mais les effets de l’interconnexion NUMA pèsent également. Linux offre des commandes permettant de câbler (pin) ou de bloquer (lock) un processus sur certains cœurs, et de contraindre l’utilisation d’un domaine mémoire NUMA spécifique. On peut par exemple utiliser la commande numactl. Pour connaître précisément la topologie d’une machine, des bibliothèques telles que hwloc peuvent être utilisées. De même, lorsqu’un code est parallélisé, plusieurs outils peuvent positionner automatiquement les processus : la variable d’environnement KMP_AFFINITY de la version OpenMP  d’Intel, GOMP_CPU_AFFINITY avec GNU, l’option –binding de la bibliothèque MPI d’Intel, etc. Assurer un placement cohérent des processus et des threads sur la machine garantit des mesures reproductibles (voir pour cela plusieurs de nos précédents articles, dont celui-ci).

1.3 – Savoir profiler son application – Profiler une application permet d’évaluer le coût relatif de chaque partie d’un code. Sans profilage adéquat, il n’est pas possible de déterminer quelle partie du code doit être améliorée. Peu importe les arguments qui décrivent la fonction XYZ comme la plus importante, seule compte une évaluation objective. L’intuition, l’expérience, les versions alternatives ou les tests sur du matériel différent ne représentent pas l’état actuel du code sur la machine courante.

Il existe deux types de profilage : par instrumentation et par échantillonnage. L’instrumentation insère des instructions dans le code binaire afin de mesurer à l’exécution l’utilisation relative de chaque fonction. Bien que comparativement fiable pour créer des arbres d’appels, ce type de profilage a le défaut d’ajouter du code, et donc potentiellement d’altérer le comportement de l’application. L’échantillonnage, pour sa part, vérifie l’exécution à intervalles réguliers afin de déterminer l’importance relative de chaque partie du code. Bien que moins intrusif, il peut avoir d’étranges effets secondaires dûs à la fréquence d’échantillonnage choisie. Aucune des deux méthodes n’est strictement meilleure que l’autre. Des outils complémentaires tels que gprof, Intel VTune ou callgrind sont tous utiles, à condition d’utiliser tous ceux dont vous disposez plutôt qu’un seul uniquement. Chacun a ses forces et ses faiblesses. Seule la combinaison de leurs résultats est à même de donner une image précise du comportement dynamique de l’application.

Dans l’idéal, le profilage devrait être réalisé sur un code quasiment prêt à la production, c’est à dire hautement optimisé. Or, il arrive que les optimisations obfusquent le code de telle manière qu’elles rendent les résultats de profilage inexploitables. Pour résoudre ce problème, les optimisations, et en particulier l’inlining, doivent être désactivées étape par étape et la cohérence du profilage vérifiée à chaque fois, jusqu’à ce que des résultats significatifs apparaissent. Par exemple, si les premiers résultats indiquent que la fonction “do_the_computation” prend 95 % du temps d’exécution, alors les profilages suivants avec moins d’inlining doivent montrer le même ordre de grandeur à la fois pour les temps passés à l’exécution de la fonction et pour son arbre d’appels (toutes les fonctions appelées par “do_the_computation”, toutes les autres appelées par celles-ci, etc.). Lorsque des résultats incohérents sont obtenus, ils doivent être analysés. Il faut en effet comprendre pourquoi une optimisation a modifié le comportement du code au point d’altérer le résultat du profilage. Comprendre ce phénomène est indispensable pour comprendre comment améliorer la performance in fine.

Enfin, le profilage ne doit pas être conçu comme une approche one-shot. Une fois que les parties les plus critiques ont été identifiées et améliorées, il est important de profiler à nouveau, ne serait-ce que pour obtenir une image à jour du profil d’exécution. Non seulement l’amélioration d’une seule partie du code rend les autres parties plus critiques mais des effets secondaires telles que la pollution des caches peuvent aussi modifier leur performance, en mieux comme en pire.
 

2 – De la bonne utilisation des compilateurs

La plupart des développeurs voient le compilateur comme un mal nécessaire, sauf ceux qui l’ont totalement délaissé (du moins le pensent-ils) pour des langages prétendument interprétés. Les applications écrites dans de tels langages ne sont évidemment pas exécutées directement sur le matériel mais requièrent une couche de traduction préalable. Il peut s’agir d’une machine virtuelle mais, pour des raisons de performance, on a généralement affaire à un compilateur à la volée. Un compilateur sur lequel l’utilisateur n’a finalement que très peu de contrôle, et qui privilégie généralement la rapidité plutôt que l’efficacité. Pour la vaste majorité des codes axés sur la performance et rien que la performance, le compilateur est un outil hautement réglable avec lequel on doit collaborer. Dans les paragraphes suivants, nous allons nous référer aux compilateurs Intel C/C++ et Fortran, très largement adoptés dans la communauté HPC, mais nos commentaires s’appliquent indistinctement à d’autres langages aussi bien qu’à d’autres compilateurs.

2.1 – Le problème du point de vue matériel – Pour comprendre pourquoi la compilation du langage de programmation en langage machine est si cruciale, il faut d’abord considérer les choses d’un point de vue architectural (avec une bonne première référence : Hennessy-Patterson [5]). Un processeur n’exécute que des instructions élémentaires dont seules trois classes sont importantes pour nous : les opérations mémoire, les opérations de calcul et les opérations de contrôle d’exécution. Toutes les boucles de calcul (y compris d’ailleurs les kernels sans boucles) sont essentiellement composées d’instructions de contrôle qui englobent une séquence d’opérations de chargement de données, de calcul et de stockage. Le reste n’est constitué que d’overheads qui n’apportent rien d’utile à l’algorithme mais consomment du temps CPU : appels de fonctions, mouvements de registres, sauvegardes des registres, appels de fonctions virtuelles, références indirectes, etc.

Le travail d’un bon compilateur-optimiseur va donc consister à éliminer le plus possible ces opérations superflues et à produire un code binaire qui exécute le plus efficacement possible les parties calcul sur le processeur cible. Toute opération inutile dans le flux d’instruction ne fait que dégrader la performance, en particulier lorsque le code est hautement optimisé.

Pour clarifier ce point, regardons de plus près un exemple synthétique, en l’occurrence une version x86_64 assez naïve de la fonction saxpy de BLAS. Le listing 1 en montre une version C basique ; le listing 2 en montre la version assembleur. Lire un code assembleur est fastidieux mais l’exercice s’avère nécessaire dans le cas qui nous occupe.

On pourrait penser que les lignes 11 (incq) et 12 (cmpq), deux instructions de contrôle, sont superflues et doivent être traitées. En réalité, elles sont non coûteuses : sur les processeurs modernes, elles s’exécutent dans les unités integer par ailleurs non utilisées, en même temps que les instructions flottantes. Le souci, dans notre code, ce sont les instructions de chargement de données (ligne 7) qui prennent des centaines de cycles en cas de cache miss. Ensuite, on a une dépendance producteur-consommateur entre la multiplication (ligne 8) et l’addition (ligne 9), ainsi qu’entre l’addition et le stockage des données (ligne 10). La littérature offre de nombreuses solutions à ces problèmes. Par exemple, dérouler (unroll) les boucles permet de masquer le coût des instructions de contrôle. De même, le pipelining logiciel devrait pouvoir masquer les dépendances producteur-consommateur. Mais on peut se passer de ces considérations pédagogiques dans la mesure où ces optimisations sont déjà prises en charge par le compilateur (ou la bibliothèque BLAS elle-même).

L’intérêt de cet exemple est d’illustrer ce qui se passe lorsque le compilateur fait bien son travail. Utiliser l’unité de vectorisation (voir section 2.3) avec les optimisations précitées permet d’améliorer la performance du code, mais toute autre instruction superflue la dégradera. Le pire se produit lorsque l’on introduit dans la boucle des opérations de chargement de données supplémentaires et interdépendantes. N’importe quelle opération de ce type, que ce soit l’accès à un objet avant l’accès à l’un de ses champs ou un accès indirect via un pointeur de pointeur, ajoute des latences potentiellement importantes à la chaîne de dépendances. Sur Sandy Bridge, une instruction mulsd a une latence de 5 cycles. Une instruction mémoire movsd consomme quant à elle soit 3 cycles (succès du cache L1), soit 230-250 cycles (hit sur la mémoire principale dans le même nœud NUMA d’un bi-socket Sandy Bridge), soit encore 350-370 cycles (hit sur la mémoire d’un autre nœud NUMA) et jusqu’à plus de 600 cycles (hit sur le nœud NUMA le plus éloigné dans un quad-socket Sandy Bridge). Voilà pourquoi la lecture du code assembleur est si importante : optimiser pour la performance nécessite de comprendre comment le CPU fonctionne.

2.2 – Les bonnes options de compilation – La première bonne pratique pour l’utilisation d’un compilateur est de laisser les ingénieurs qui l’ont créé faire le travail à votre place. Les compilateurs offrent beaucoup d’options d’optimisation, dont la majorité se révèlent plus ou moins obligatoires compte tenu de leur faible coût en temps de compilation et des gains potentiels qu’elles peuvent apporter. D’autres, moins fréquentes, s’avèrent à l’usage assez profitables rapportées là encore au surcoût qu’elles impliquent en temps de compilation. Enfin, certaines peuvent se révéler très coûteuses et avoir des effets totalement différents en fonction du type de code.

Avec quel compilateur travailler ? Celui que propose le constructeur du matériel est le choix le plus évident : il devrait normalement être le plus optimisé pour l’architecture sous-jacente. Mais les compilateurs tiers sont tout aussi intéressants car, avec leurs forces et leurs faiblesses respectives, ils peuvent se montrer meilleurs en fonction de l’application ciblée. Si plusieurs compilateurs sont disponibles, il faut évidemment tous les essayer. Avantage annexe, cela permet d’identifier des erreurs ou des approximations dans le code. Aucun choix n’est à cet égard définitif : modifier tout ou partie du code dans le but de l’optimiser peut changer la donne au profit d’un autre compilateur. Dans tous les cas, à moins de bugs fatals et avérés, il est recommandé d’utiliser la dernière version de l’outil.

Les premières options de compilation à tester sont évidemment les options d’optimisation globales, préfixées par “-O” et suffixées d’un nombre qui détermine combien de passes de compilation seront appliquées. Tous les codes devraient normalement fonctionner avec tous les niveaux d’optimisation – à moins d’un problème dans le source ou dans le compilateur lui-même. On se laisse souvent aller à blâmer le compilateur pour des erreurs déclenchées à des niveaux d’optimisation élevés mais, en règle générale, c’est le code qui est fautif, parce qu’on est à la limite du langage. La première chose à faire est donc de s’assurer de la reproductibilité à tous les niveaux d’optimisation, soit en réglant les problèmes dans le code, soit en démontrant qu’il y a réellement un bug dans le compilateur. À chaque compilation, dès lors que de nouvelles options sont utilisées, une vérification de conformité des résultats du code s’impose.

Certains compilateurs, ceux d’Intel notamment, effectuent des passes dites “inter-procédurales” qui tentent d’optimiser le code au-delà des limites des fonctions. Dans les versions récentes, cette option est généralement activée par défaut pour chaque “unité de compilation” (traduisez : pour chaque fichier). L’option “-ipo” permet d’activer cette optimisation sur la globalité des unités de compilation. Ainsi, plutôt que de compiler ces unités indépendamment en créant des fichiers « .o » à chaque fois, le compilateur produit des stubs et les compile ensuite tous ensemble pour créer le binaire final. L’inconvénient, c’est qu’à la moindre modification du code, tout doit être recompilé. L’avantage, c’est que le compilateur dispose d’informations globales telles que les valeurs en dur (tailles de tableaux, constantes, etc.) ou l’arbre des appels de fonctions. Le travail qu’il réalise est donc bien plus efficace. Par exemple, s’il peut déterminer le nombre d’itérations d’une boucle, il saura la dérouler de façon plus adéquate. Si le paramètre scalaire d’une fonction s’avère être une constante, alors le compilateur peut dans certains cas en déduire que certains calculs sont inutiles.

Avec les compilateurs Intel récents, il faut également essayer les options d’inlining. Classiquement, tous les compilateurs tentent d’inliner quelques fonctions (notamment celles que le programmeur définit) mais des heuristiques intégrées limitent la taille du code et/ou les temps de compilation. Ce qui par contrecoup limite la capacité du compilateur à fusionner les boucles et/ou les fonctions et à éliminer les calculs et/ou les accès mémoire redondants.

Regardez la combinaison d’options d’inlining suivante, particulièrement agressive :

–inline-forceinline
–no-inline-factor
–no-inline-max-per-compile
–no-inline-max-per-routine
–no-inline-max-total-size
–no-inline-max-size
–no-inline-min-size

Ajoutée à “–ipo“, elle commande au compilateur de fusionner le plus de code possible en une fonction de calcul unique, quels que soient le temps de compilation, l’utilisation mémoire et la taille du binaire final. Certains codes se prêtent bien à l’ensemble de ces options. L’application QCD Qiral [6] est un bon exemple : avec le compilateur Intel 11.1.1.163, sa performance est améliorée d’un facteur supérieur à 2.

Chaque compilateur offre par ailleurs des options avancées spécifiques qui peuvent se révéler efficaces en fonction du code concerné. Tant que les résultats applicatifs restent valides, toute combinaison d’options peut être utilisée. Encore une fois, si “le compilateur casse le code”, alors il y a un problème qui doit être identifié, faute de quoi il est susceptible de réapparaître avec un compilateur différent, une machine différente ou, pire, un autre jeu de données.

2.3 – Savoir vectoriser son code – La deuxième règle d’or pour l’utilisation d’un compilateur est de comprendre s’il a bien vectorisé le code. Le mot ” vecteur” ne doit pas être pris au sens trop littéral. Aujourd’hui, ce terme fait référence aux registres à taille fixe des CPU et aux instructions qui leur sont associées – SSE ou AVX sur les systèmes x86_64, QPX sur IBM BlueGene/Q, etc. De nombreux travaux ont été publiés sur le sujet, à commencer par ceux d’Intel [7]. Si ces papiers sont intéressants pour les programmeurs avancés, ils peuvent en revanche s’avérer trop touffus pour le novice en vectorisation.

Le principe des jeux d’instructions vectorielles est de réaliser en même temps plusieurs opérations à partir d’une instruction unique, et donc d’apporter un gain à faible coût. Examiner en détail pourquoi ces instructions sont un bon compromis demanderait de trop longues explications ; le fait que la plupart des CPU en expose suffit à les justifier. Nous détaillerons dans la section 2.4 quelques différences intéressantes entre les principaux.

Prenons l’exemple de l’instruction mulsd du jeu SSE2 que nous venons de mentionner. Le nom complet de cette instruction est “Multiply Scalar Double-Precision Floating-Point Values”. Comme son nom l’indique, elle réalise une multiplication sur des valeurs à virgule flottante double précision. Cette instruction a un équivalent, mulpd (“Multiply Packed Double-Precision Floating-Point Values”) qui, plutôt que de se limiter à une seule multiplication, en réalise une pour chacun des éléments du vecteur. La taille des vecteurs dépend du jeu d’instructions. Pour SSE, par exemple, les registres vectoriels ont une taille de 128 bits qui permet de stocker dans chaque registre deux valeurs double précision (64 bits chacune selon la norme IEEE754-2008). Ainsi, chaque instruction mulpd calcule deux opérations flottantes au lieu d’une seule. La fonction saxpy du listing 1 peut être modifiée pour utiliser cette nouvelle instruction, comme le montre le listing 3.

Le code calculant deux valeurs par itération, il ne fonctionnera évidemment pas si le nombre d’éléments dans le vecteur n’est pas un multiple de 2. Il a donc été modifié manuellement à partir du code assembleur généré (listing 2). Un code vectorisé automatiquement par le compilateur contiendrait toutes les vérifications nécessaires mais ne serait pas adapté à cette simple illustration. Voilà qui montre en tout cas qu’avec le même nombre d’instructions, on peut accomplir deux fois plus de travail. Bien sûr, il ne s’agit pas de programmer à la main mais de laisser faire le compilateur. Sur une boucle aussi simple, celui-ci n’a aucune difficulté à vectoriser. Il ira même jusqu’à vous l’indiquer si vous utilisez l’option –vec-report3 (listing 4). Cela étant, toutes les boucles ne sont pas aussi simples et c’est pourquoi comprendre le travail du compilateur est important. Les compilateurs récents affichent leurs erreurs ; reste à savoir les interpréter.

Prenons un autre exemple concret avec le code Hydro. Il s’agit d’une mini application construite à partir du code RAMSES utilisé pour étudier la formation de galaxies et de structures à grande échelle. Ce code comprend plusieurs variantes, chacune développée pour s’exécuter sur un type de matériel spécifique : une version C avec directives OpenMP et des appels à MPI ; une version avec directives OpenACC pour exploiter les accélérateurs ; une autre avec OpenCL pour les accélérateurs également, etc. Nous allons nous attarder sur la fonction “riemann” qui existe en deux versions radicalement différentes : l’une d’origine agrémentée de directives OpenACC, l’autre modifiée et rendue vectorisable. La compilation de la version originale non optimisée est montrée au listing 5.

Intéressons-nous aux boucles des lignes 102, 107 et 138 dont la structure est présentée au listing 6. La sortie du compilateur indique qu’il ne parvient pas à vectoriser la boucle la plus interne, ligne 138, parce qu’il ne peut pas garantir que toutes les itérations sont indépendantes les unes des autres. C’est tout à fait juste : la boucle la plus interne est une boucle de convergence et chaque itération dépend des résultats de toutes les itérations précédentes. Par conséquent, non seulement cette boucle ne peut pas être vectorisée, mais le compilateur n’essaye même pas de vectoriser les deux boucles extérieures car vectoriser la plus interne est un prérequis des compilateurs récents.

Il y a cependant un moyen simple de forcer la vectorisation : si nous remplaçons la borne supérieure de la boucle interne (Hniter_rieman) par une valeur fixée en dur à 10 (valeur extraite d’un jeu de test de référence), alors le compilateur peut dérouler complètement la boucle interne et ainsi faire de la boucle narray la nouvelle boucle la plus interne. En pratique, la vectorisation échouera à nouveau car le compilateur ne peut pas déterminer si les deux boucles externes sont totalement parallèles. Mais si l’on applique la directive #pragma ivdep à chacune de ces boucles, le compilateur est maintenant capable de vectoriser le code comme le montre le listing 7 (les numéros de ligne diffèrent légèrement).

Le hic, c’est que l’algorithme est devenu faux (nous avons utilisé une valeur fixe comme borne supérieure d’itération), ce qui n’est pas acceptable. D’autres modifications sont donc nécessaires pour que le compilateur puisse vectoriser le code en conservant sa sémantique initiale. On peut par exemple décider d’intervertir la boucle de convergence qui pose problème (ligne 138) avec la boucle narray (ligne 107), ce qui implique une totale réorganisation des boucles avec l’introduction de tableaux temporaires supplémentaires. Cette nouvelle structure est montrée listing 8 et le résultat de sa compilation listing 9. Notez que le terme SIMD présent dans la sortie est un artefact des directives requises pour indiquer au compilateur que les itérations des boucles sont indépendantes.

Beaucoup de raisons peuvent expliquer qu’un compilateur ne parvient pas à vectoriser. Malheureusement, les messages du compilateur peuvent parfois manquer de clarté. Dans tous les cas, des règles simples peuvent vous aider à identifier et résoudre ces problèmes :

– Le compilateur Intel tente de vectoriser la boucle la plus interne uniquement. Donc, les petites boucles internes doivent être déroulées (automatiquement à l’aide d’une directive ou à la main) si le nombre d’itérations est connu. S’il n’est pas connu, la situation se complique mais on peut souvent intervertir une boucle avec une autre plus externe, parallèle et plus importante, en ajoutant des tableaux temporaires.

– À part quelques types de réduction (accumulation arithmétique de variables scalaires…), le compilateur Intel est capable de vectoriser les boucles parallèles. S’il se plaint d’une dépendance entre vecteurs, vérifiez qu’il n’y en a vraiment pas et utilisez les directives appropriées pour l’aider.

– Les instructions conditionnelles dans les boucles imbriquées peuvent empêcher la vectorisation et la rendent de toute façon moins efficace. Déplacer en dehors de la boucle celles qui ne dépendent pas des itérations est généralement une bonne pratique.

Outre la vectorisation des boucles, d’autres conditions déterminent l’utilisation des jeux d’instructions vectorielles. En général, le compilateur produit plusieurs variantes d’une même boucle en fonction de divers paramètres (nombre d’itérations, alignement des tableaux, etc.) mais rien ne garantit que la version vectorisée sera utilisée à l’exécution. A ce propos, il est possible de solliciter les compteurs matériels du CPU pour valider les résultats. Des outils tels que Vtune ou Likwid peuvent s’avérer très utiles pour vérifier si la version vectorielle a bien été exploitée.

2.4 – Les jeux d’instructions vectorielles – On l’a vu dans les sections précédentes, la plateformes x86_64 compte deux jeux d’instructions vectorielles principaux : SSE et AVX. SSE a été conçu initialement pour les données entières et à virgule flottante simple précision. La double précision a été ajoutée dans SSE2 et les versions suivantes ont vu l’introduction de nouvelles instructions pour divers objets. Toutes ces versions ont en commun des registres XMM de 128 bits, une taille suffisante pour contenir quatre valeurs SP ou deux valeurs DP.

AVX, quant à lui, a vu le jour avec un tout nouveau schéma d’encodage des instructions appelé VEX. Ce schéma ne concerne pas vraiment les programmeurs ; le point réellement important, ici, est le doublement de la largeur des registres à 256 bits, soit 8 valeurs SP ou 4 valeurs DP. Dans la version initiale, seules des valeurs à virgule flottante pouvaient être stockées dans les registres 256 bits YMM – la première moitié des registres YMM correspondant aux registres XMM. Point à noter, mélanger dans un même code les instructions SSE par des instructions AVX engendre une petite pénalité de performance.

Une des fonctionnalités les plus ignorées du jeu AVX est son sous-ensemble d’instructions VEX.128. Comme ce nom le laisse penser, les instructions fonctionnent uniquement avec les 128 bits de poids faible des registres YMM, soit la partie correspondant aux registres XMM. Bien qu’elles semblent redondantes avec SSE, les instructions AVX apportent un avantage non négligeable : elles utilisent trois opérandes alors que SSE fonctionne pour l’essentiel avec deux seulement.

Regardons au listing 10 un extrait de la documentation Intel [8]. La version SSE stocke ses résultats dans l’opérande source xmm1 tandis que la version VEX.128 ne détruit aucun des opérandes. À chaque fois que les opérandes sources doivent être réutilisés, ce mécanisme économise une instruction movapd de copie de registres. Rien de spectaculaire a priori, surtout pour les codes numériques dont un des opérandes n’est généralement utilisé qu’une fois. Mais VEX.128 ne se limite pas aux instructions à virgule flottante ; beaucoup d’instructions entières ont également été redéveloppées. Si elle ne peuvent pas accéder aux 128 bits de poids fort des registres 256 bits YMM, elles utilisent néanmoins le format à trois opérandes.

Un code qui bénéficie particulièrement de ce mécanisme est l’algorithme Keccak de Bertoni et al., gagnant du concours NIST pour la création de SHA-3. L’implémentation “SIMD instructions and tree hashing” utilise des instructions SSE pour exécuter simultanément deux occurrences 64 bits de l’algorithme. Le programme est écrit en C avec des intrinsèques plutôt qu’en assembleur. Les instructions utilisées sont essentiellement des or et xor logiques et des shifts (pour les rotations de valeurs 64 bits). Un court extrait d’une rotation en  SSE est montré au listing 11, en AVX au listing 12.

Cet algorithme nécessite des copies additionnelles afin de préserver les valeurs d’entrée, réutilisées plusieurs fois. Les statistiques sur le code partiellement déroulé montrent que le nombre d’instructions de déplacement de données a été réduit de 396 (35 % des 1132 instructions) à 111 (13 % des 837 instructions). Tous les mouvements restant sont des accès mémoire ; aucun n’implique de déplacement registre à registre. La mesure des performances montre par ailleurs une amélioration de 20 % pour le hachage des petits tableaux. Ce qui prouve qu’une simple option de compilation permettant de passer d’une version SSE à une version AVX, en l’occurrence –mavx (ou équivalente), offre de réelles améliorations à moindre coût.

Le mois prochain, nous regarderons dans le détail comment les structures de données impactent à la fois la performance des codes et la complexité des algorithmes – avec un focus tout particulier sur l’optimisation des codes parallèles.

Bons développements !

[1] S. Chellappa, F. Franchetti, and M. Püschel, How to write fast numerical code: A small introduction in Summer School on Generative and Transformational Techniques in Software Engineering (GTTSE), ser. Lecture Notes in Computer Science, vol. 5235. Springer, 2008, pp. 196–259.

[2] G. M. Amdahl, Validity of the single processor approach to achieving large scale computing capabilities in Proceedings of the April 18-20, 1967, spring joint computer conference, ser. AFIPS ’67 (Spring). New York, NY, USA: ACM, 1967, pp. 483–485.

[3] N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2002.

[4] J. L. Gustafson, Reevaluating Amdahl’s law in Commun. ACM, vol. 31, no. 5, pp. 532–533, May 1988.

[5] J. L. Hennessy and D. A. Patterson, Computer Architecture: A Quantitative Approach. San Mateo, CA: Morgan Kaufmann, 1990.

[6] D. Barthou, G. Grosdidier, M. Kruse, O. Pene, and C. Tadonki, QIRAL: A High Level Language for Lattice QCD Code generation, CoRR, vol. abs/1208.4035, 2012.

[7] A. J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance. Intel Press, 2004.

[8] Intel Corporation, Intel 64 and IA-32 Architectures Software Developer’s Manual Volume 2 (2A, 2B & 2C): Instruction Set Reference, A-Z, March 2013, no. 325383-046.