Le "free-lunch" est_il vraiment terminé?

Auparavant, obtenir des gains de performances applicatives consistait tout simplement à attendre la prochaine génération de processeurs. Il était ainsi inutile, pour la majorité des développeurs, d’investir dans l’optimisation de leurs logiciels et, grâce aux améliorations matérielles, ils bénéficiaient ainsi de ce que l’on pourrait qualifier de « rasage gratis ». A présent que l’informatique est passée au multicœur, la situation n’est cependant plus la même : les gains performances passent par la parallélisation, au travers d’applications adaptables, c’est-à-dire pensées pour s’adapter à la multiplication des cœurs d’exécution. Dans cet article d’introduction, nous examinerons ainsi certains aspects cette adaptabilité, en posant la question : L’évolutivité par la parallélisation est-elle le nouveau rasage gratis ?

Version PDF

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

Introduction

Durant l’« ère de la programmation séquentielle », cette période de l’évolution de l’informatique où les plates-formes matérielles étaient élaborées autour d’un processeur simple cœur, les plus astucieux des développeurs avaient remarqué que leurs applications bénéficiaient de gains de performances qui leur étaient servies plus ou moins sur un plateau et sans rien demander, lors de la sortie de la génération de processeurs suivante. Le blogueur Joel Spolsky l’a exprimé de la façon suivante :

Grâce à la chute du prix de la mémoire vive, et la rapidité des processeurs doublant chaque année, les programmeurs dont je suis avaient le choix : soit passer les six mois suivants à réécrire leurs boucles internes en assembleur, soit prendre six mois de congés pour jouer de la batterie dans un groupe de rock. Dans les deux cas, le résultat était identique : le programme sur lequel ils travaillaient tournait plus vite. Or, malheureusement, coincés qu’ils sont devant leur ordinateur, les programmeurs en assembleur n’ont pas de groupies…
Nous ne nous intéressions donc plus tellement aux performances ni à l’optimisation.

Bien que publié avec un certain décalage (à l’automne 2007, alors que l’ère de la programmation en série était bel et bien terminée), ce billet décrit assez bien la situation : Avec des gains de performances « gratis », attendons simplement un peu la sortie de nouveaux processeurs !

Herb Sutter, gourou du C++ et à présent de la parallélisation pour Dr. Dobb’s Journal, nous a alertés de la fin de tout cela dans son fameux article de 2005 (sic), « Aujourd’hui, on ne rase plus gratis » (« The Free Lunch is Over »). Pour de nombreuses bonnes raisons, y compris celles qui ont trait à la physique des semi-conducteurs, la conception des puces est passée au multicœur et les gains de performance des processeurs simple cœur seront beaucoup moins spectaculaires que par le passé. Il y a des gains à obtenir, certes, mais plus sans efforts : les logiciels doivent dorénavant être conçus et implémentés pour le parallélisme de traitement.

Comme Sutter et beaucoup d’autres le font remarquer, la parallélisation est difficile. Peu de développeurs sont en effet déjà à l’aise avec sa pratique, les modèles de programmation classiques l’ignorent et la voie de mise en œuvre qui reste la plus empruntée - le threading - est parsemée d’embûches (concurrence critique). L’un des enjeux est ainsi l’évolutivité (scalability) : comment une application se comporte-t-elle lorsque l’on met davantage de cœurs à sa disposition ? Cette série d’articles se propose donc d’examiner certains aspects de cette évolutivité (désignée également par les termes dimensionnabilité et adaptabilité).

Prévoir l’évolutivité

Le terme évolutivité est très bien défini par le blogueur Werner Vogels :

Un service est dit « évolutif » si, lorsque l’on renforce les ressources d’un système, cette opération dégage des gains de performances proportionnelles aux ressources ainsi ajoutées.

Ce concept a de très larges applications. Dans les datacenters, par exemple, prévoir l’impact d’un renfort en serveurs ou de leur virtualisation représente un enjeu important. Les ressources sur lesquelles nous nous concentrerons cependant ici sont les cœurs d’exécution et nous circonscrirons la discussion au modèle d’implémentation que représentent les fils d’exécution.

On nous rappelle (Sutter, encore lui) que les « cœurs » sont à la fois une ressource d’exécution et une ressource mémoire, au travers du cache qu’intègrent désormais tous les processeurs, et nous aborderons l’évolutivité sur ce double aspect en partie III.

Or les choses se présentent mal (Amdahl était optimiste).

Les débats sur l’évolutivité commencent presque toujours par la « loi d’Amdahl », l’équation de prime abord astucieuse qui affirme que le code séquentiel n’est pas du code parallèle, ou plutôt qu’il n’est pas possible d’accélérer du code séquentiel en ajoutant des cœurs. Son expression habituelle est la suivante :

L’accélération (Speedup) est fonction du nombre d’unités de traitement p. Elle dépend de la proportion de la partie séquentielle du code par rapport à la partie parallélisable (1 – s). Considérons par exemple un code parallélisable à 90 % (s = 0,1), qui s’exécute sur huit cœurs (p = 8) : le facteur d’accélération qui en résulte est de 4,7, ce qui représente l’accélération maximale possible dans ce cas. La figure 1 illustre graphiquement ce résultat, ainsi que ceux qui correspondent à du code comportant des composants séquentiels plus larges. Sachant que l’adaptabilité parfaite (s = 0) est représentée par la ligne diagonale bleue, on s’aperçoit que l’on en est bien loin.

Les résultats de la Figure 1-1 illustrent les prédictions d’adaptation, jusqu’à 8 cœurs. Que se passe-t-il sur un système multicœur ou avec une proportion plus favorable de code parallélisable ? C’est ce que montre la figure 1-2 (source Wikipédia), et la situation n’est pas encourageante : même un code parfaitement parallélisé à 95 % ne s’accélérera pas plus que d’un facteur de 20, indépendamment du nombre de cœurs disponibles.

Figure 1-1. Courbes de la loi d’Amdahl (accélération théorique maximale) pour 8 cœurs à différents niveaux de parallélisme.

Figure 2-1. Courbes de la loi d’Amdahl (accélération théorique maximale) pour 8 cœurs à différents niveaux de parallélisme.

Au-delà de ces considérations classiques, la situation peut même être pire : l’expression idéaliste d’Amdahl ignorant les dégradations de performances dues au coût de création des fils d’exécution, à la synchronisation et à la communication, une implémentation « parfaite » n’atteindra même pas la maigre adaptation indiquée dans ces graphiques. Quel espoir y a-t-il dans ce cas pour les applications parallélisées, en particulier pour obtenir un bon rendement d’exécution sur un grand nombre de cœurs ?

Réévaluer la loi d’Amdahl (Attention aux présupposés implicites !)

La faille de la loi d’Amdahl a été signalée dès 1988, par John Gustafson : cette loi suppose en effet une charge de calcul fixe ou une adaptation fixe des parties séquentielles ou parallèles à mesure de l’aggravation du problème.

La solution alternative, souvent nommée « accélération évolutive » (scaled speedup), cherche plutôt à accroître la taille problématique pour une durée donnée et peut s’exprimer de la manière suivante :

C’est-à-dire que l’accélération pour un nombre donné de processeurs p est ce nombre p, ajoutée de la partie du code parallèle (1 – p) qui est passée en opérations séquentielles s. Or il y a une différence subtile par rapport à la loi d’Amdahl : ce s représente le travail séquentiel lorsque l’application s’exécute sur p processeurs.

Examiner les chiffres d’adaptabilité pour des cas spécifiques est révélateur. Supposons qu’une application s’exécute sur 64 cœurs, avec une durée mesurée de 220 secondes, et que l’on détermine (par exemple par profilage) que 11 secondes sont consacrées à l’exécution séquentielle. Insérer ces valeurs dans la formule d’accélération évolutive donne :

C’est-à-dire que l’accélération est presque d’un facteur de 61 pour 64 cœurs. Or, si l’on utilise la même valeur pour la durée séquentielle (0,05), dans la loi d’Amdahl, cette formule ne prévoit qu’une accélération d’un facteur de 15 pour 64 cœurs.

Même si le modèle d’accélération évolutive effectue les mêmes idéalisations que la loi d’Amdahl (pas de coûts ajoutés, etc.), il expose un point de vue très largement plus optimiste en ce qui concerne l’évolutivité.

Conclusion

A ce stade, nous avons à peine commencé à planter le décor : la loi d’Amdahl ne décrit pas tout et, quoi qu’elle dise, l’évolutivité parallèle est possible dans de nombreux cas.

Avec une application totalement évolutive, doubler le nombre de cœurs doublerait quasiment les performances. L’investissement que représente la parallélisation dégagera désormais des gains de performances « gratuites » lorsque le nombre de cœurs matériels augmentera. Les développeurs astucieux pourraient ainsi simplement prendre des congés. (Vous connaissez des groupes de rock qui cherchent un batteur ?)

Dans le prochain épisode, nous examinerons les facteurs qui restreignent l’évolutivité, et la manière de les limiter.

Suite dans a partie II : « Du bon usage des blocages ».

 

Références

Joel Spolsky, « Strategy Letter VI », blog Joel on Software, 18 septembre 2007 (www.joelonsoftware.com/items/2007/09/18.html).

Herb Sutter, « The Free Lunch is Over: A Fundamental Turn Toward Concurrency in Software », Dr. Dobb’s Journal, 30(3), mars 2005.

Werner Vogels, « A Word on Scalability », blog All Things Distributed (www.allthingsdistributed.com/2006/03/a_word_on_scalability.html).

Herb Sutter, « Super Linearity and the Bigger Machine », site Dr. Dobb’s Portal, 12 mars 2008 (http://www.ddj.com/architect/206903306).

John Gustafson, « Reevaluating Amdahl’s Law », Communications of the ACM, 31(5), 1988 (republié sur http://www.scl.ameslab.gov/Publications/Gus/AmdahlsLaw/Amdahls.html).


 

Per informazioni più dettagliate sulle ottimizzazioni basate su compilatore, vedere il nostro Avviso sull'ottimizzazione.