Choisir les bons APIs et outils pour faciliter le parallélisme

Envoyer un nouvel article

April 13, 2009 4:00 PM PDT


Version PDF

Cet article est également disponible en téléchargement [PDF de 101 ko].

Résumé

Les éditeurs de logiciels doivent aborder la généralisation du parallélisme matériel en faisant la meilleure utilisation possible des API et des autres outils à leur disposition, sans pour autant interrompre leurs travaux de développement en cours. Une vision à long terme amène à considérer qu’un fort niveau de parallélisme applicatif devient nécessaire, mais que la refonte architecturale totale d’un logiciel existant est rédhibitoire. Dans cet article, nous préconisons une approche itérative et progressive de la parallélisation, tout en prêtant fortement attention à la nécessité d’une amélioration continue.

Introduction

La tendance au multicœur va sans nul doute se poursuivre et le génie logiciel devra ainsi aborder le parallélisme afin d’en tirer tous les avantages. Le multithreading est l’un des moyens les plus répandus pour aborder ce parallélisme, et toute une panoplie d’outils et de méthodes s’est développée à cet égard. Parallèlement, nombreux sont les développeurs à estimer que la parallélisation est, dans le meilleur des cas, un mal nécessaire et, au pire, une pente glissante conduisant à l’échec des projets.

Dans les faits, l’introduction du threading dans les applications est une entreprise très complexe, mais chargée de larges promesses en gains performances, de réactivité et de productivité. Le surcroît de performances né de la parallélisation permet par ailleurs d’ajouter des nouvelles fonctions à une application et même de modifier radicalement la manière dont les utilisateurs interagissent avec les données.

Si l’on considère d’abord l’objectif commercial qui est de dimensionner les applications pour les générations matérielles actuelles et futures, les éditeurs de logiciels devront choisir parmi un certain nombre d’approches. De toute évidence, un logiciel nouveau, construit à partir de rien, doit être conçu d’emblée pour le parallélisme, car les processeurs multicœurs ne peuvent que se généraliser. Pour les applications déjà établies, cet objectif à long terme est tout aussi valable, mais la manière de l’aborder dans l’immédiat est plus complexe.

Dans certains milieux, on préconise une refonte architecturale totale pour intégrer le parallélisme, mais la dépense et le temps qu’exige cette démarche sont souvent rédhibitoires. Joel Spolsky, auteur du blog Joel on Software, signale que, si les développeurs préféreront toujours faire table rase du code existant et recommencer de zéro, cette démarche risque pourtant de conduire à la catastrophe commerciale. En fait, il va jusqu’à affirmer que la réécriture totale d’un code est « la pire erreur stratégique qu’un éditeur de logiciels puisse commettre ».

L’introduction progressive du parallélisme permet au contraire de concilier des perspectives à long terme et l’impératif à moyen terme qui consiste à poursuivre la commercialisation des produits. Il est donc nécessaire de trouver des moyens simples pour introduire la parallélisation. Ces moyens sont, dans la mesure du possible, l’automatisation du processus, le recours à des bibliothèques de threads et, lorsque le codage manuel du threading est inévitable, le choix des méthodes les plus simples pour atteindre les objectifs que l’on s’est fixés.

Threading explicite : maîtriser, mais à quel coût ?

Outre l’adoption de la démarche graduelle que cet article préconise, les développeurs seront aussi amenés à décider jusqu’à quel niveau ils souhaiteront maîtriser le threading de tel ou tel algorithme, et l’intérêt pour eux de ce contrôle. On notera d’ailleurs que certaines applications peuvent nécessiter un style de threading hybride.

Les options du threading ne sont pas mutuellement exclusives, mais, en général, Intel déconseille l’utilisation du threading explicite. L’arbitrage doit se faire autour du fait que ce type de threading est un codage de très bas niveau et très puissant, mais en même temps très complexe. James Reinders, de l’équipe Software Development Products d’Intel est à ce titre tout à fait catégorique :

« N’utilisez pas les threads natifs à l’état brut (Pthreads, Windows threads, Boost threads ou similaires). Les threads et l’interface MPI constituent les langages assembleur du parallélisme. Ils offrent une flexibilité maximale, mais exigent trop de temps de codage, de débogage et de maintenance. »[1]

Dans un souci de transparence, il est important de reconnaître que le threading explicite permet d’exercer un contrôle à forte granularité, par exemple sur l’ordonnancement des threads que les développeurs voudraient mettre en œuvre dans certaines applications complexes. Il assure aussi un contrôle sans limitation des problèmes tels que le traitement des erreurs, les mécanismes à forte granularité pour le contrôle du mappage thread-processeur et la synchronisation dans un sous-ensemble de threads.

Certains développeurs opteront donc pour le threading explicite dans certains cas. Toutefois, l’approche progressive préconisée ici est plutôt axée sur les techniques suivantes :

  • Recours à un compilateur pour paralléliser automatiquement le code. Cette démarche est limitée, mais facile à mettre en œuvre, de sorte que sa rentabilité est incontournable.
  • Mise à profit des directives OpenMP*. Cette syntaxe relativement simple peut indiquer au compilateur comment décomposer les parties d’un programme séquentiel pour son exécution en parallèle.
  • Pour les tâches communes, utilisation d’une une bibliothèque d’exécution (runtime) contenant des threads en interne. La bibliothèque Intel® Threading Building Blocks (TBB) permet de mettre en œuvre du code avec des threads en se concentrant sur les possibilités de parallélisation et sans fastidieuse gestion des threads.

Les écueils du threading

Souvent, le threading peut rendre les algorithmes parfaitement extensibles (race), mais il peut aussi introduire des résultats imprévisibles ou nuire aux performances. La mise à jour par plusieurs threads de la même variable globale risque de provoquer la perte de données, et une mauvaise synchronisation entre les threads peut aboutir à une version parallélisée d’une application qui est largement moins performante que la version séquentielle qu’elle remplace.

Nous aborderons dans cette partie certaines difficultés courantes liées au threading, afin de montrer la complexité qu’implique la parallélisation par threading explicite. Il est évident que ce type de problèmes et d’autres, similaires, peuvent surgir même si l’application ne fait pas appel au threading explicite, mais, en général, si la complexité de la mise en œuvre du threading augmente, le risque de rencontrer des problèmes augmente aussi.

Lorsque deux threads ou plus accèdent à la mémoire sans synchronisation adéquate, ils risquent de provoquer une course d’accès aux données (data race), qui conduit à l’imprévisibilité des résultats. La Figure 1 illustre une course aux données où, selon le thread qui s’exécute en premier, la valeur de x sera différente : si le thread n° 1 s’exécute avant le thread n° 2, le programme sortira de sa région parallélisée avec x égal à 3 ; si c’est le thread n° 2 qui s’exécute d’abord, le programme en sortira avec x égal à 43.

Figure 1. Situation de course aux données (datarace).

Lorsque plusieurs threads arrivent à une situation où chacun attend l’autre, il s’ensuit un blocage mutuel (« interblocage » ou deadlock), qui provoque une boucle d’exécution infinie dans l’application (hang condition). La figure 2 illustre cette situation, où la combinaison des verrous (locks) appliqués sur A et B par les threads n° 1 et 2 empêche les deux threads de poursuivre, ce qui bloque l’application. Dans les situations bien plus complexes du réel, des bogues comme celui-là peuvent survenir sous certaines conditions très particulières, ce qui les rend très difficile à prévoir et à reproduire.

Figure 2. Situation d’interblocage (deadlock).

Outre ce type d’erreurs, le code parallélisé peut présenter des problèmes de performances qui risquent très vite de ralentir inopinément l’exécution d’un programme, voir à tel point qu’il est plus lent que sa version séquentielle. Le verrouillage excessif, par exemple, est une source fréquente de pertes de performances : la séquentialité des zones verrouillées limite l’extensibilité, et un verrouillage trop fréquent augmente les évictions du cache en ralentissant les threads. La correction de ces problèmes peut être ardue et chronophage, de même qu’il est difficile de savoir si le scénario optimal a été atteint pour différentes situations d’exécution.

Parallélisation à partir d’un code existant

Avant de plonger dans la réécriture totale avec threading explicite, il vaut mieux envisager une démarche plus progressive où, au lieu d’essayer de paralléliser toute une application d’un coup, on n’introduit que graduellement le threading, en commençant par les modifications les plus simples à mettre en œuvre. Il faut donc se concentrer sur une introduction du parallélisme qui fournit les performances dont une application a vraiment besoin : soucions-nous de l’utilisateur, pas du matériel. Il convient ainsi d’optimiser d’abord la version séquentielle du code et, si l’on cherche encore à gagner en performances, on pourra alors adopter l’approche suivante :

  • Utiliser le compilateur Intel® pour paralléliser les boucles internes serrées.
    • Utiliser les options de compilation d’auto-parallélisation /Qparallel pour Windows* et -parallel pour Linux* et Mac OS*.
    • Utiliser les options de compilation OpenMP* /Qopenmp pour Windows et -openmp pour Linux et Mac OS, tout en insérant des directives OpenMP dans le code.
  • S’assurer que les bibliothèques sont compatibles avec le threading (threadsafe), en prévision des appels qui peuvent s’effectuer à partir du code parallélisé.
  • Repérer les zones de code qui peuvent bénéficier du parallélisme, en utilisant l’analyseur VTune™ ou d’autres outils similaires.
  • Utiliser les modules Intel Threading Building Blocks pour mettre en œuvre le parallélisme au niveau des tâches.
  • Remplacer les appels de fonctions volumineuses les plus courantes par des appels de bibliothèques parallélisées, telles que les primitives Intel® IPP (Integrated Performance Primitives) et la bibliothèque Intel® MKL (Math Kernel Library).
  • Utiliser OpenMP ainsi que les outils Intel® Thread Checker et Intel® Thread Profiler pour faire des prototypes de possibles mises en œuvre du threading.


Pour obtenir d’autres conseils sur la définition des objectifs et l’établissement des processus, on pourra consulter la documentation suivante proposée sur l’Intel® Software Network :



Utilisation des directives OpenMP pour la mise en œuvre du parallélisme

OpenMP présente un avantage pour le threading explicite, car il est relativement simple, de haut niveau et neutre par rapport aux systèmes d’exploitation propriétaires. Il se compose d’un ensemble de « pragmas », d’interfaces API et de variables d’environnement, et il est supporté par une large palette de plates-formes, dont Windows, Linux et Mac OS.

Il est conçu pour paralléliser graduellement une application, de telle sorte que l’on peut travailler à un moment donné sur une partie de programme sans avoir à effectuer des modifications importantes ailleurs dans le code, car les instructions du code séquentiel ne nécessitent en général aucune modification, ce qui réduit le risque d’y introduire de nouveaux bogues. Par l’ajout d’un pragma parallèle en C/C++ ou d’une directive en Fortran, OpenMP créé dans le code des zones paralléliséees (cf. figure 3). Après la directive #pragma omp parallel, le thread principal (maître) représenté en couleur magenta, génère le nombre voulu de threads esclaves pour compléter le travail en parallèle (selon le travail à accomplir et les ressources matérielles disponibles). En sortant de la région parallèle, une pause se produit sur le chemin d’exécution du thread maître, dans l’attente que tous les threads esclaves terminent leur travail. Lorsque tel est le cas, les threads esclaves s’interrompent et le programme revient à l’exécution séquentielle.

Figure 3. La directive OpenMP* PARALLEL qui crée une zone de code parallélisée.

L’un des vecteurs de la souplesse d’OpenMP est le fait que les compilateurs qui ne reconnaissent pas son pragma (ou sa directive) l’ignorent tout simplement et que le code se compile de façon séquentielle. De même, OpenMP peut être désactivé, et le code de base se compilera alors de façon séquentielle. Cette caractéristique (régulée par la norme ANSI) fait qu’OpenMP est très peu envahissant. Un autre de ses points forts est sa capacité à déterminer le nombre de threads nécessaires et à automatiser la distribution du travail, ce qui est particulièrement important eu égard au nombre croissant de cœurs dont seront dotés les futurs processeurs.

L’envers de la médaille est qu’OpenMP ne produit pas, par lui-même, du code parallèle à toute épreuve (threadsafe). Il est toujours nécessaire de détecter et de corriger des erreurs de threading, ce que peut néanmoins faciliter le recours à l’outil Intel® Thread Checker. On peut aussi être confronté à des situations où OpenMP n’assure pas le contrôle de forte granularité nécessaire à l’ordonnancement optimal de chaque thread. Par exemple, dans les cas où plusieurs aspects d’une charge de travail pourraient bénéficier de l’attribution d’un nombre spécifique de threads dédiés, qui travailleraient avec des priorités spécifiques, les API natives conçues pour développer du threading explicite peuvent fournir de meilleures performances, quoiqu’au prix d’une complexité accrue.

Au bout du compte, le compromis à trouver entre OpenMP et le threading explicite nous est familier. OpenMP apporte en effet de la simplicité, mais à un certain prix en matière de contrôle et de visibilité sur la majeure partie de ce que le code accomplit en coulisses. Toutefois, il fournit certaines API qui peuvent offrir un plus grand degré de détail dans certaines situations. Dans la majorité des cas, OpenMP constitue, de toute façon, un moyen convenable pour obtenir un niveau d’accélération plutôt élevé de l’exécution parallèle, en équilibre avec ses caractéristiques favorables en matière de temps, effort et coût consentis.

Bibliothèques de threading : le Meccano du parallélisme

Des bibliothèques de threading commencent à apparaître sur le marché. Elles proposent des fonctions pré-parallélisées qui dispensent le programmeur d’avoir à entrer dans le détail de leur fonctionnement. Les Intel® Threading Building Blocks sont ainsi une bibliothèque d’exécution (runtime) C++ à base de modèles (templates), construite pour simplifier le portage de structures de données et d’algorithmes séquentiels courants vers du code parallèle performant. L’application résultante peut atteindre des performances, une extensibilité et une fiabilité excellentes, sous Windows, Linux et Mac OS, tout en détectant automatiquement le nombre de cœurs disponibles et en se dimensionnant en conséquence.

Comparée aux threads natifs, cette bibliothèque est une solution plus portable et plus facile à utiliser par les développeurs en C++ qui veulent paralléliser des applications pour améliorer leurs performances, leur extensibilité et leur fiabilité. Elle dispense en effet de réécrire, de tester de nouveau comme d’optimiser les structures de données et algorithmes parallèles les plus courants. L’application se contente en l’occurrence d’appeler le code parallélisé qu’elle comporte. En revanche, son objectif n’est pas de traiter tous les problèmes de parallélisation et elle est prévue pour une utilisation conjointe avec d’autres techniques de threading.

Elle propose des versions parallèles et optimisées d’algorithmes courants, ce qui permet aux développeurs de se concentrer sur les niveaux supérieurs d’abstraction, par le biais de tâches et de patrons (patterns) extensibles : elle permet de spécifier des tâches au lieu de threads. Comme nous l’avons déjà dit, la programmation directe des threads est complexe et se traduit souvent par des programmes peu performants parce que les threads sont des ressources logicielles lourdes et de bas niveau, très proches du matériel. Or la bibliothèque d’exécution Intel Threading Building Blocks effectue l’ordonnancement automatique de ces tâches sous forme de threads, de telle sorte qu’on obtient une utilisation efficace des ressources du processeur.

Elle privilégie une programmation parallèle évolutive, axée sur les données (data parallel programming). La méthode qui consiste à découper un programme en blocs fonctionnels distincts et à attribuer un thread particulier à chaque bloc se prête mal l’« extensibilisation », parce que le nombre de blocs fonctionnels est en général fixe. Or les Intel Building Blocks mettent au contraire l’accent sur une programmation parallèle axée sur les données, ce qui permet de travailler sur les différentes parties d’une collection. Ce type de parallélisme permet d’« extensibiliser » un logiciel de façon à ce qu’il tire parti d’une multiplication des cœurs en scindant la collection en morceaux plus petits ou bien en gérant des collections plus grandes de sorte qu’il y ait plus de morceaux à gérer.

Avec les modèles des Intel Threading Building Blocks, les applications peuvent utiliser des algorithmes d’autres bibliothèques Intel. Les primitives de la bibliothèque Intel® IPP ont ainsi été conçues pour accélérer les applications multimédias, de communication et bien d’autres. La bibliothèque Intel MKL propose quant à elle des routines pour les applications scientifiques, d’ingénierie et financières qui exigent des performances maximales. Elles sont toutes deux performantes, à l’épreuve des erreurs de parallélisation (threadsafe) et comportent un nombre important de fonctions parallélisées destinées à assister l’expression du parallélisme dans les applications.

Conclusion

Lors de la mise en œuvre du parallélisme logiciel, il faut trouver un équilibre entre l’adaptation vis-à-vis du matériel futur et le besoin de faire avancer sans heurts la planification du développement logiciel. Il est difficile de faire du bon logiciel multithreading, ce qui constitue un excellent argument en faveur d’un parallélisme qui soit le moins envahissant possible. Il vaut mieux commencer par les modifications les plus simples, pour n’aller vers les plus compliquées qu’ensuite, en fonction des impératifs de performances. Puisque l’industrie continue de mûrir, les API et les outils de mise en œuvre du parallélisme gagneront en puissance et les éditeurs de logiciels devront se positionner dès à présent pour bénéficier de ces avancées au fur et à mesure de leur arrivée.

Que l’on ajoute des pans de code à une application existante ou que l’on en crée une de zéro, il faut « penser parallèle ». Au lieu d’envisager un problème comme d’une série d’étapes séquentielles, on cherchera à sciender les donnés en modules distincts, susceptibles d’un traitement parallèle. D’une certaine façon, il s’agit d’une adaptation psychologique très similaire à la différence qu’il y a à accomplir une tâche soi-même et à la déléguer à toute une équipe. La modularisation qu’implique cette méthode deviendra alors pour les programmeurs comme une seconde nature et la pénurie actuelle de moyens de parallélisation suivra.

Documentation

Les ressources et la documentation suivantes constituent un point de départ pour approfondir le sujet abordé ici :


Quelques mots sur l’auteur


Matt Gillespie est auteur et rédacteur technique indépendant. Il travaille dans la région de Chicago et se spécialise dans les technologies nouvelles, tant matérielles que logicielles. Avant cela, il élaborait des formations pour les développeurs d’Intel et a travaillé aussi au service Internet d’une banque californienne. En début de carrière, il était auteur et rédacteur dans les domaines des publications financières et des neurosciences.

© 2008, Intel Corporation. Tous droits réservés.

[1] « Rules for Parallel Programming for Multicore », Dr. Dobbs’ Portal, 5 septembre 2007 (www.ddj.com/hpc-high-performance-computing/201804248).