Ecrire des applications parallèles se simplifie, et nous avons vu précédemment que chasser les bugs parallèles était rapide et intuitif avec Intel Parallel Inspector. Reste maintenant le principal problème : utiliser pleinement tous les coeurs simultanément.

Une station de travail multi-core a typiquement 8 coeurs, 16 vus par l’OS avec la nouvelle technologie SMT (Simultaneous Multi Threading) et dans l’avenir beaucoup plus. Le consensus actuel dans l’industrie des processeurs est que les gains de performance viendront essentiellement par l’ajout de coeurs : nous sommes à l’orée de l’ère du " many-core ".

QUATRE DÉFIS

C’est Gene Amdahl qui nous explique dans la loi éponyme le premier défi : un logiciel parallèle est très vite limité par les parties non parallèles. En pratique imaginez que 20% de votre logiciel est sériel et 80% parallèle, vous pouvez supposer qu’il tirera bien parti d’une machine multi-core. Or si vous ajoutez une infinité de coeurs et que la partie parallèle de 80% en tire parfaitement bénéfice, votre logiciel n’ira que 5 fois plus vite. Pour 8 coeurs il n’ira que 3,3 fois plus vite. Il faut donc à tout prix réduire ces régions sérielles. Le second problème de performance vient de la synchronisation entre threads dans la partie parallèle. Une variable dont l’étendue est vaste et englobe la région parallèle doit être protégée pour les écritures depuis différents threads, par exemple par une section critique. Cette section critique garantira qu’un seul thread accédera à cette variable à un moment donné, créant une mini région sérielle à décompter de la partie parallèle. L’idéal est que les threads puissent travailler indépendamment sans avoir à se synchroniser ou à s’attendre les uns les autres. Le troisième problème vient de l’équilibre de charge entre threads. Pour que votre tâche s’exécute le plus vite possible vos threads doivent avoir la même charge de travail. Si vous en donnez plus à l’un qu’aux autres il finira plus tard et les autres attendront. Si votre charge est facile à prédire vous pouvez la scinder en parties égales dès le début et la répartir entre vos threads, si elle ne l’est pas, scindez la en petites parties et faites une queue où les threads iront piocher au cours du travail.
Le quatrième problème est le coût de la communication entre threads. Il est timide et ne se montre que lorsque vous avez traité les trois autres. Imaginez par exemple que, pour avoir une balance correcte entre threads, vous ayiez scindé votre charge en une multitude de petites tâches et mis en place une queue de travail. Il faudra, certes, très peu de temps à chaque thread pour aller chercher un élément de la queue mais mis bout à bout cette communication est un poids. Tout est question de mesure : une granularité des éléments dans la queue assez fine pour avoir une bonne balance, mais pas trop fine pour minimiser les communications.

INTEL PARALLEL AMPLIFIER

Ces problèmes sont presque impossibles à isoler par une simple analyse de l’exécution ou en ajoutant des printf à la main. Intel Parallel Amplifier fait partie de la suite Intel Parallel Studio, son rôle est de vous aider à améliorer la performance de votre logiciel multithreadé. Il est important d’avoir déjà résolu les bugs parallèles de votre logiciel : une fois debuggué, votre logiciel ira probablement beaucoup moins vite et c’est justement sur ces ralentissements qu’Amplifier est utile. Amplifier propose trois analyses intégrées à Visual Studio : par point chaud " hot spot ", par concurrence et enfin par blocages et attentes. Il travaille d’un côté avec des compteurs matériels du processeur pour connaître les temps d’exécution avec une infime précision, et de l’autre avec la librairie de threading que vous utilisez. Aucune interaction avec le cadre de travail haut niveau, donc aucun problème de compatibilité que vous travailliez au niveau du thread, avec OpenMP ou Intel Threading Building Blocks, par exemple. La première analyse est assez simple à comprendre, Amplifier exécute votre binaire et vous dit quelles sont les fonctions chronophages, mais rajoute aussi une colonne dans la vue du source pour vous montrer le détail ligne par ligne. Simple à dire, moins à programmer. Cette analyse ne repose pas sur une simple instrumentation des appels de fonction mais sur un décompte matériel dans le processeur du temps d’exécution de chaque micro instruction. Amplifier fait ensuite le lien avec l’assembleur en mémoire puis le code. La précision du décompte au niveau du processeur est redoutable mais l’analyse n’impacte pas le temps d’exécution. La seconde analyse, par concurrence, entre plus profondément dans le comportement parallèle de votre application. L’analyse vous renseigne tout d’abord sur le temps passé dans différents niveaux de concurrences, par exemple si vous exécutez sur un dual-core avec deux threads en exécution (l’idéal), ou un seul. Vous n’aurez qu’un seul thread en exécution si vous êtes dans une région sérielle ou bien potentiellement dans une section critique d’une région parallèle. Cette donnée est affichée pour tout le logiciel, les fonctions et même pour chaque ligne de code. Non seulement il a fallu qu’Amplifier analyse le temps pris par chaque micro instruction en interagissant avec le décompte du processeur, mais qu’en plus il aligne les résultats de différents threads. Au final, vous pouvez différencier les lignes parallèles des lignes sérielles. La troisième et dernière analyse détecte les attentes et blocages (Wait and Locks). Il s’agit ici pour Amplifier d’instrumenter les communications entre threads pour détecter des attentes, comme dans le cas d’un défaut de balance, ou des blocages

EXEMPLE

Pour commencer, il faut établir un temps de base en prenant une charge de travail assez importante pour que le temps soit significatif. La charge doit stresser différentes parties de votre code comme le feraient des charges de production, et de la même manière. C’est un point simple mais souvent sous-estimé. Lorsque vous calculez des temps, lancer une exécution pour chauffer la machine (au sens propre du terme, pour que la fréquence du processeur remonte) puis quelques exécutions pour faire une moyenne. Le cas du jour est un calcul de nombres premiers dans un intervalle d’entiers. Nous l’avons parallélisé avec OpenMP, puis debuggé avec Parallel Inspector en ajoutant deux sections critiques. Temps de base : 22,5s.

POINTS CHAUDS

Lançons l’analyse par point chaud (menu outils, sous-menu " Intel Parallel studio " et enfin " hot spots ") pour commencer. Le résultat est très simple : un tableau des fonctions (avec modules et arbre d’appel), classés par temps processeur. Cliquez sur une fonction et vous verrez le source avec le temps processeur pour chaque ligne. Astuce : si votre ligne est très longue et que vous voulez savoir quelle partie de la ligne est fautive, répartissez-là sur deux lignes, recompilez etrelancez l’analyse. Dans notre cas, c’est la fonction chargée d’indiquer l’avancement du calcul qui arrive en tête avec les 2/3 du temps. Je clique sur la fonction et le source correspondant m’indiqueque c’est surtout le printf. Apres réflexion je remarque que le printf est demandé beaucoup plus souvent que nécessaire. Jechange le code et calcule le temps : 5.26s (4.3x plus vite). Je relance la même analyse et la fonction d’avancement est presque invisible, cette fois c’est la fonction de calcul principale qui occupe l’essentiel du temps processeur.

CONCURRENCE

L’analyse de la concurrence affiche en bas à droite un graphique à barres qui indique pour différents niveaux de concurrence le temps passé. Je passe une partie importante du temps avec un seul thread en exécution ou même aucun. Inquiétant, car j’ai un dualcore. [Fig.1] Je regarde le détail par fonction et vois réapparaître la fonction d’avancement. Elle n’accapare plus le processeur mais empêche les threads de s’exécuter en parallèle. Le détail du source est sans appel : la section critique qui protège l’incrémentation de gProgress est pointée. Il existe une fonction Windows qui protège l’incrémentation en parallèle d’une variable : " InterlockedIncrement ". Fonction très spécialisée et extrêmement optimisée. Je remplace donc mes deux sections critiques, recompile et calcule : 4,98s (6% plus vite). Le gain peut paraître faible mais la loi d’Amdahl nous enseigne qu’une région sérielle est extrêmement pénalisante pour un grand nombre de coeurs. J’ai en fait résolu un problème gravement handicapant sur une machine largement multi-core, mais peu visible sur mon dual-core. Après avoir relancé l’analyse par concurrence c’est la partie de calcul intensif qui est pointée. Ce n’est donc plus un problème de concurrence.

ATTENTES ET BLOCAGES

Il est maintenant temps de lancer la dernière (et plus amusante) des analyses : attentes et blocages. Le résultat est intuitif : je vois en bas à droite que je passe une grande partie de mon temps avec un seul thread, et dans la vue par fonction que tout cela est dû à la fonction qui lance le calcul parallèle. Le détail du source pointe la ligne de pragma OpenMP " parallel for ". J’ai probablement un problème de répartition de charge entre mes threads par OpenMP. [Fig.2] L’instruction parallel for accepte des arguments. Pour commencer testons le cas simple : découpe de la charge en deux parties identiques avec " parallel for schedule (static,2) ". Résultat : 4.41s, bien, mais si je tente de perturber un peu la machine pendant l’exécution le temps augmente rapidement (un des threads travaille alors plus vite que l’autre). Avec (static,8) je suis plus robuste face aux perturbations et atteint un respectable 4.12s. Allons jusqu'à (static,2000000) : 4.42s, les deux threads finissent, quoiqu’il arrive, en même temps mais nous voyons le coût de la gestion de queue qui augmente. L’idéal se trouve probablement avec (guided) où la queue donne de gros morceaux au début et de petits à la fin, pour optimiser l’équilibre balance/communication, résultat : 4.09s. Le graphique nous indique que le logiciel s’exécute à 99% avec deux threads, le rêve ! Vous pouvez maintenant escompter une excellente utilisation d’un grand nombre de coeurs. En pratique, il est préférable que votre logiciel accepte des paramètres différents (ou les calcule à l’exécution) pour s’adapter à des configurations matérielles différentes.

CONCLUSION

L’optimisation de logiciels parallèles est parfois complexe mais souvent passionnante. Un peu de méthode (pensez à Amdahl !) et le bon outil vous seront très utiles dans cette aventure. Intel Parallel Amplifier est tellement intuitif et précis que vous regretterez de n’avoir que votre logiciel à optimiser.

Paul Guermonprez - Ingénieur logiciel Intel

IntelliJ IDEA 12.1

Intel : vers de meilleurs expériences mobiles

Arrêtez le chasse-neige, programmez parallèle avec TBB
Threading Building Block est une librairie qui a pour but d'offrir une interface agréable pour les développeurs en C++ qui souhaitent paralléliser leur code. Agréable, car vous avez la liberté de rester à un haut niveau d'abstraction, garder une formulation objet fonctionnelle et de ne pas vous intéresser aux détails d'implémentation. Le croirez-vous, modélisation objet et performance ne sont cette fois-ci pas incompatibles, bien au contraire. Le fait de définir avec précision les données du problème en mode objet sans entrer dans les détails techniques donne à la librairie tout ce dont...

Pourquoi passer à la programmation parallèle ? (2ème partie)
Nous poursuivons ce mois-ci les raisons pour passer à la programmation parallèle et surtout les pièges à éviter et à maîtriser. Et ils sont nombreux ! Deadlock Parfois nommé étreinte fatale, le deadlock est provoqué par des threads mutuellement verrouillés. Cette situation peut être comparée à deux personnes dessinant des diagrammes tout en se partageant un crayon et une règle. Si une personne prend le crayon et l'autre prend la règle, un blocage se produit lorsque la personne avec le crayon a besoin de la règle pour terminer son travail alors que la personne avec la règle a besoin...

Pourquoi passer à la programmation parallèle
A l’occasion de la sortie d’Intel Parallel Studio et des nombreuses avancées que les éditeurs préparent pour 2009 et 2010, Programmez ! vous propose de mieux comprendre la programmation adaptée aux processeurs à plusieurs coeurs. C’est ce que l’on appelle la programmation parallèle. C’est- à-dire capable d’exécuter plusieurs opérations, instructions, parallèlement sur plusieurs processeurs ou plusieurs coeurs. Complexe à maîtriser, le parallélisme est le mont Everest du développement. Nous vous proposons de l’aborder méthodiquement en posant les fondamentaux pour bien l’assimiler et éviter...

Version finale : Intel Parallel Studiodébarque
La programmation est l’art de schématiser et simplifier un processus pour l’automatiser. Nous aboutissons donc le plus souvent à un code sériel. Avec l’arrivée de puces multi-core, et bientôt massivement multi-core cette approche atteint ses limites : Il vous faut passer à la programmation parallèle. N’ayez crainte, Intel est là pour vous aider avec un ensemble logiciel aussi convivial que complet : Intel Parallel Studio. Le parallélisme se conçoit à plusieurs niveaux, mais celui qui nous intéresse ici est le " thread ". Intel Parallel Studio est un ensemble de logiciels pour vous aider à...

Intel Parallel Studio : Vous ne reconnaîtrez plus votre C++
Dans les deux précédents articles sur Intel Parallel Studio, nous nous sommes intéressés aux outils Inspector et Amplifier qui permettent respectivement de corriger et accélérer vos logiciels parallèles. Mais nous n'avons pas encore abordé Composer, qui est le compilateur associé à diverses librairies comme Intel Threading Building Blocks et Intel Performance Primitives (TBB et IPP). De nos jours, un compilateur ne peut se contenter de produire un binaire minimaliste, même optimisé. Il doit vous aider à adopter une syntaxe plus claire, apporter un éclairage nouveau sur votre code et...

Plus de coeurs, plus rapide, plus scalable : du multi-core au " many-core ”
Ecrire des applications parallèles se simplifie, et nous avons vu précédemment que chasser les bugs parallèles était rapide et intuitif avec Intel Parallel Inspector. Reste maintenant le principal problème : utiliser pleinement tous les coeurs simultanément. Une station de travail multi-core a typiquement 8 coeurs, 16 vus par l’OS avec la nouvelle technologie SMT (Simultaneous Multi Threading) et dans l’avenir beaucoup plus. Le consensus actuel dans l’industrie des processeurs est que les gains de performance viendront essentiellement par l’ajout de coeurs : nous sommes à l’orée de l’ère...

La chasse aux bogues parallèles avec Intel Parallel Inspector
Nous avons été formés à programmer en mode sériel et passer à la programmation parallèle n'a rien d'évident, mais plusieurs technologies existent pour vous faciliter la vie : Intel Threading Building Blocks ou le standard OpenMP par exemple. Une fois les concepts de base assimilés, implémenter un programme parallèle qui utilise à peu près efficacement un processeur à deux ou quatre coeurs va assez vite si votre algorithme s'y prête. Mais il est surtout très facile de transformer un logiciel sériel sans bogue en un logiciel multithreadé fortement bogué sans que ce soit évident, ni à...

Intel Parallel Studio: simplifier le développement parallèle !
Alors que les processeurs multi-cores (multi-coeurs) prolifèrent, améliorer les performances logicielles, et mieux utiliser la puissance processeur, demeure un enjeu important pour rester compétitif, surtout pour les applications développées en C ou C++. Mais jusqu’à présent le développement parallèle restait complexe à aborder pour le développeur. Programmez ! vous invite à découvrir en avant-première la nouvelle solution Intel, avec un tout nouveau plug-in Visual Studio, qui va radicalement changer votre vision du développement parallèle. L’année 2009 sera non seulement l’année de la...