Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Nous n’y sommes pas, mais il faut y penser :
Fin de la loi de Moore : repousser les limites du calcul
La loi d’Amdahl selon Peter J. Denning et Ted G. Lewis
Article mis en ligne le 15 mars 2017
dernière modification le 17 mars 2017

par Laurent Bloch

Périodiquement un article vient nous rappeler que la loi de Moore, qui soutient la croissance exponentielle de la vitesse de calcul des ordinateurs depuis 50 ans, n’est pas éternelle, et qu’un jour (après-demain ou dans vingt ans) il faudra trouver autre chose pour étancher notre soif informatique. Un autre article de ce site décrit les avatars de la loi de Moore, nous avons regroupé dans celui-ci les considérations un peu plus techniques relatives aux moyens d’accélérer les ordinateurs actuels en s’affranchissant de la synchronisation des opérations ou par la parallélisation des calculs.

Cet article a un prédécesseur :
Les lois de Moore en perspective

Il ne manque pas d’idées pour continuer à accroître la puissance de calcul des ordinateurs lorsque les limites physiques de la technologie CMOS actuelle seront atteintes, même si on laisse de côté les espoirs suscités par l’hypothétique ordinateur quantique, par le recours à l’ADN ou, avec plus de vraissemblance, par les nanotubes de carbone.

*Asynchronisme

Les processeurs actuels sont synchrones, c’est-à-dire que l’exécution de toutes les opérations est scandée par une horloge : au top d’horloge les opérations en cours sont censées être effectuées et leurs résultats disponibles pour les opération suivantes. L’intervalle entre deux tops d’horloge est de l’ordre de la nanoseconde, son inverse en est la fréquence, de l’ordre du gigahertz.

Cette synchronisation, qui a déjà fait l’objet d’un article plus détaillé de ce site, a un coût. La simultanéité d’un grand nombre d’opérations entraîne une consommation électrique instantanée qu’il serait souhaitable de répartir dans le temps. La circuiterie destinée à acheminer le signal d’horloge à chaque circuit logique occupe entre le tiers et la moitié de la surface du composant (et consomme un bon tiers de l’énergie utilisée). Il faut des circuits supplémentaires pour calculer et compenser la dérive (clock skew) induite par cette propagation du signal.

Pour éviter ces inconvénients on a pensé, depuis longtemps, à des circuits asynchrones, mais l’asynchronisme ne va pas sans contraintes : ainsi, chaque circuit logique devrait, à la fin de chacune de ses opérations, envoyer à la cantonnade un message « ça y est, j’ai fini ! » pour annoncer la disponibilité de ses résultats, et les autres circuits logiques devraient recevoir le message et l’analyser. Tout ceci a un coût, et à ce jour les processeurs asynchrones sont moins efficaces que les synchrones.

À noter que les architectures data flow, qui consistent à stocker dans un buffer les opérations en attente de données et à en déclencher l’exécution dès que leurs données sont disponibles sans tenir compte du fil d’exécution auquel elles appartiennent, réalisent une forme d’asynchronisme macroscopique. Toutes les architectures contemporaines sont peu ou prou de type data flow.

*Et les multi-processeurs ?

S’il devient difficile d’accroître la vitesse d’un processeur, il est logique d’essayer d’en faire travailler plusieurs en parallèle pour effectuer le même calcul. Cette idée a été explorée dans les années 1960, 1970 et 1980 pour les ordinateurs à logique discrète (c’est-à-dire dont le processeur était constitué d’un grand nombre de circuits électroniques distincts), elle est reprise depuis plusieurs années pour les microprocesseurs.

L’agrégation de plusieurs processeurs peut se faire à des degrés d’intimité variés :

 les processeurs multicore comportent plusieurs unités arithmétiques et logiques (ALU) sur le même chip, qui partagent la même mémoire ;
 une carte électronique peut comporter plusieurs processeurs (éventuellement multicore) reliés par un bus (ensemble de fils commandés par un circuit logique) rapide ;
 plusieurs cartes de ce type peuvent être connectées au même fond de panier dans le même boîtier d’ordinateur ;
 plusieurs ordinateurs peuvent être reliés par un réseau rapide dans le même local pour former un cluster ;
 enfin on peut imaginer (et réaliser) un calcul réparti entre toute une collection d’ordinateurs reliés par Internet.

Il va de soi que plus le lien entre ces processeurs sera distant, plus les délais de propagation des informations seront longs. La répartition des tâches entre les processeurs devra en tenir compte, et plus les délais de propagation seront longs moins il devra y avoir d’interdépendance de données entre les sous-tâches.

*La loi d’Amdahl

De toutes les façons, la répartition d’un calcul entre n processeurs ne permettra jamais de l’effectuer n fois plus vite que sur un processeur, parce qu’il y aura toujours du temps consommé ne serait-ce que pour la coordination entre les sous-tâches, ainsi que pour les parties forcément séquentielles du programme. Le premier à étudier formellement ce problème fut Gene Amdahl, l’architecte principal de la gamme IBM 360, qui formula en 1967 la loi qui porte son nom.

La loi d’Amdahl exprime le gain de temps que l’on peut attendre d’un groupe de n processeurs qui coopèrent à l’exécution d’un programme donné. Soit T(1) = a+b le temps d’exécution du programme considéré sur un système monoprocesseur, avec a le temps consacré à la partie séquentielle du programme et b le temps consacré à la partie parallélisable. La fraction séquentielle du programme est p = a/(a+b), et la fraction parallélisable est 1-p.

Le temps d’exécution du programme considéré réparti sur n processeurs sera T(n) = a+b/n, parce que seule la fraction parallélisable de l’algorithme pourra bénéficier du parallémisme. L’accélération espérée sera :

SA = T(1)/T(n)
= (a+b)/(a+b/n)
= n/(np+(1-p))
< 1/p

Les graphiques qui illustrent l’article sont accessibles en ligne ici.

*Gustafson pour les gros volumes de données

Si la loi d’Amdahl tient pour les programmes intensifs en calcul, John Gustafson a observé que les programmes qui appliquent des traitements assez simples à de grands volumes de données pouvaient bénéficier d’un meilleur rendement du parallélisme. C’est typiquement le cas des programmes de biologie moléculaire qui comparent par exemple une séquence de protéine aux 54 247 468 séquences de la banque UniProtKB/TrEMBL (pour un total de 17 207 833 179 acides aminés) : chaque comparaison est indépendante des autres, on peut partager la banque entre les n processeurs pour effectuer les comparaisons, et ce n’est qu’à la fin qu’il faudra interclasser les scores de similitude pour obtenir les séquences qui ressemblent le plus à la séquence à laquelle on s’intéresse.

Dans ce cas, soit W(1) = a+b la tâche à accomplir par un monoprocesseur (a et b sont toujours respectivement la partie séquentielle et la partie parallélisable de la tâche), avec n processeurs on a W(n) = a+bn, puisque chaque processeur exécute les mêmes opérations sur les données qui lui sont attribuées. L’accélération qui en résulte est :

SG = W(n)/W(1)
= (a+bn)/(a+b)
= p+n(1-p)
> n(1-p)

soit une accélération proportionnelle au nombre de processeurs.