Fonctionnement d'un ordinateur/Les architectures parallèles

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

De nos jours, il n'est pas rare de posséder des processeurs contenant plusieurs cœurs. L'utilité de tels processeurs est très simple : la performance ! De tels processeurs exécutent des instructions indépendantes dans des processeurs séparés, ce qui porte le doux nom de parallélisme. Mais les processeurs multicœurs ne sont pas les seuls processeurs permettant de faire ceci : entre les ordinateurs embarquant plusieurs processeurs, les architectures dataflow, les processeurs vectoriels et les autres architectures parallèles, il y a de quoi être perdu. Pour se faciliter la tâche, diverses classifications ont été inventées pour mettre un peu d'ordre dans cette jungle de processeurs.

Partage de la mémoire[modifier | modifier le wikicode]

On peut classer les architecture suivant la façon dont les processeurs doivent se partager la mémoire est aussi très importante. Dans le premier cas, on a une mémoire partagée entre tous les processeurs. Avec ce genre d'architecture, rien n’empêche plusieurs processeurs de vouloir accéder à la mémoire en même temps, ce qui n'est pas possible sans mémoires multiports. Il va donc falloir trouver des moyens pour arbitrer les accès à la mémoire entre les processeurs. Pour cela, le matériel fournit des instructions pour faciliter la communication ou la synchronisation entre les différents morceaux de programmes (interruptions inter-processeurs, instructions atomiques, et autres). Les couts de synchronisation peuvent être conséquents et peuvent réduire les performances. Il est possible de n'utiliser qu'une seule mémoire reliée à un bus, ou plusieurs mémoires reliées aux processeurs via un réseau crossbar.

Architecture à mémoire partagée avec une seule mémoire.
Architecture à mémoire partagée avec plusieurs mémoires.

Viennent ensuite les architectures distribuées : chaque processeur possède sa propre mémoire et les processeurs sont reliés par un réseau local (ou par internet). Les processeurs peuvent ainsi accéder à la mémoire d'un autre processeur via le réseau local : il leur suffit de faire une demande au processeur qui détient la donnée. Cette demande va traverser le réseau local et arriver à son destinataire : la donnée demandée est alors envoyée via le réseau local et est copiée dans la mémoire locale de l’ordinateur demandeur. Il va de soi que les communications entre les différents processeurs peuvent prendre un temps relativement long, et que ceux-ci sont loin d'être négligeables. Avec une organisation de ce genre, la qualité et les performances du réseau reliant les ordinateurs est très important pour les performances. Il va de soi que les communications sur le réseau peuvent prendre du temps : plus le réseau est rapide, meilleures seront les performances.

Architecture à mémoire partagée.
Architecture distribuée.

Il est possible d'utiliser des caches aussi bien sur des architectures distribuées qu'avec la mémoire partagée. Néanmoins, la gestion de ces caches peut poser quelques problèmes, comme nous le verrons d'ici quelques chapitres. Ces problèmes surviennent quand une donnée est présente dans plusieurs caches distincts : chaque processeur pouvant modifier cette donnée indépendamment des autres, les données dans un cache peuvent ne pas être à jour. Or, un processeur doit toujours avoir, pour éviter tout problème, une valeur jour de la donnée dans l'ensemble de ses caches : cela s'appelle la cohérence des caches. Pour cela, les mises à jour dans un cache doivent être propagées dans les caches des autres processeurs. Nous aborderons le sujet en détail plus tard, dans quelques chapitres.

Architecture à mémoire partagée avec des caches dédiés pour chaque CPU.
Architecture distribuée avec des caches.

Taxonomie de Flynn[modifier | modifier le wikicode]

Dans les années 1966, un scientifique américain assez connu dans le milieu du hardware qui se nomme Flynn a classé ces architectures en 4 grandes catégories : SISD, SIMD, MISD, et MIMD. Cette classification a remarquablement tenu le coup au fil du temps. Mais elle n'est pas parfaite, et certaines architectures sont difficiles à classer. Mais cette classification, bien que simpliste, est particulièrement didactique.

Architecture Description
Architectures SISD Processeurs incapables de toute forme de parallélisme.
Architectures SIMD Architectures capables d'exécuter une instruction sur plusieurs données à la fois. Avec cette solution, les processeurs exécutent un seul et unique programme ou une suite d'instructions, mais chaque processeur travaille sur une donnée différente.
Architectures MISD Exécutent des instructions différentes en parallèle sur une donnée identique. Autant prévenir tout de suite : on ne verra aucun exemple de ce type dans le tutoriel. Cette catégorie d’architectures est vraiment très rare. On peut citer comme exemples d'architectures MISD les architectures systoliques et cellulaires.
Architectures MIMD Architectures capables d’exécuter des instructions différentes sur des données différentes. Les processeurs multicœurs et multiprocesseurs font partie de la catégorie MIMD. La catégorie MIMD est elle-même découpée en deux sous-catégories.
  • Le Single Program Multiple Data , ou SPMD, consiste à exécuter un seul programme sur plusieurs données à la fois : la différence avec le SIMD est que le SPMD peut exécuter des instructions différentes d'un même programme sur des données.
  • Le Multiple Program Multiple Data, qui consiste à exécuter des programmes en parallèle sur des données différentes. On peut ainsi découper un programme en sous-programmes indépendants exécutables en parallèle ou exécuter plusieurs copies d'un programme. Dans les deux cas, chaque copie ou morceau de programme est appelé un thread.
SIMD - taxonomie de Flynn.
MIMD - taxonomie de Flynn.
MISD - taxonomie de Flynn.
\ Données traitées en série Données traitées en parallèle
Instructions traitées en série SISD SIMD
Instructions traitées en parallèle MISD MIMD

Parallélisme de données et de tâches[modifier | modifier le wikicode]

Les architectures SIMD et SPMD effectuent ce qu'on appelle du parallélisme de données, à savoir exécuter un même flux d'instruction ou un même programme sur des données différentes, en parallèle. Les processeurs pouvant faire ce genre de chose ne sont pas rares, bien au contraire : la quasi-totalité des processeurs est aujourd'hui de ce type. Plus précisément, tous les processeurs Intel et AMD actuels, ainsi que leurs confrères de chez ARM, MIPS et VIA en sont capables. Le parallélisme de donnée est aussi massivement utilisé dans les cartes graphiques, qui sont des composants devant exécuter les mêmes instructions sur un grand nombre de données : chaque calcul sur un pixel est plus ou moins indépendant des transformations qu'on effectue sur ses voisins.

Ce parallélisme de données s'oppose au parallélisme de tâches, qui exécute plusieurs programmes en parallèle. Celui-ci s'exploite en découpant un programme en plusieurs sous-programmes indépendants qu'on peut faire exécuter en parallèle. Ces sous-programmes indépendants sont ce qu'on appelle des Threads. Il suffit de faire exécuter chaque Thread sur un processeur séparé pour pouvoir paralléliser le tout. Les architectures permettant d’exécuter des threads en parallèle sont donc des architectures multiprocesseurs ou multicœurs, ainsi que quelques autres processeurs un peu spéciaux. Avec ce genre de parallélisme, le découpage d'un programme en threads est avant tout un problème logiciel, du ressort du compilateur, du programmeur, voire du langage de programmation. Mais, plus étonnant, certains processeurs sont capables de découper un programme à l’exécution, éventuellement grâce à des indications fournies par le programme lui-même ! C'est tout de même assez rare, même si cela a déjà été tenté : on reviendra dessus quand je parlerai des architectures EDGE et du spéculative multithreading dans ce tutoriel.

Parallélisme de tâches[modifier | modifier le wikicode]

Ces deux formes de parallélisme n'ont pas du tout la même efficacité, comme nous allons le voir. Pour cela, nous allons aborder la loi d'Amdhal, une loi qui donne l’amélioration maximale que l'on peut obtenir d'un programme parallèle, quand il s’exécute sur plusieurs processeurs. Pour calculer le gain maximal que l'on peut obtenir sur N processeurs, on suppose que ce code parallèle peut tout aussi bien exploiter la puissance d'un seul processeur, que de 2, 20, voir 10 000 000 processeurs. Bref, ce code est quasiment parfait et on s'interdit les situations du style : on observe un gain énorme avec 2 ou 4 processeurs, mais pas au-delà. De plus, ce programme est exécuté sur la même quantité de données : on ne rajoute pas de données en même temps qu'on ajoute des processeurs, et ces données ont toujours la même taille, histoire de comparer ce qui est comparable.

Dans ces conditions, la limite du parallélisme de tâches tient dans le fait que tous les programmes ne peuvent pas utiliser plusieurs processeurs à la perfection. Tout programme conservera une certaine portion de code qui ne profitera pas du parallélisme. Appelons cette portion de code le code série, tandis que la portion de code qui profite du parallélisme sera appelée le code parallèle. Le ou les processeurs passeront un certain temps à exécuter le code série, et un autre temps dans le code parallèle. Notons ces deux temps et . On sait que le temps mis par un programme à s'exécuter vaut donc :

Maintenant, ajoutons une seconde hypothèse : le code parallèle profite au mieux de la présence de plusieurs processeurs. Dit autrement, si on possède processeurs, tous auront une part égale du code parallèle, en temps d'exécution. Dans ces conditions, le temps d'exécution du programme devient celui-ci :

Ces deux formules nous permettent de calculer le rapport entre le temps sans parallélisme et celui avec. On a alors :

Maintenant, notons et le pourcentage de temps d’exécution passé respectivement dans le code série et dans le code parallèle. Par définition, ces deux pourcentages valent et . Dans l'équation précédente, on peut identifier ces deux pourcentages (leur inverse, précisément). On a alors, en faisant le remplacement :

Cette formule nous permet de calculer le gain obtenu grâce au parallélisme. Ce gain se calcule en divisant le temps avant parallélisation et le temps obtenu après. C'est intuitif : si un programme va deux fois plus vite, c'est que son temps d’exécution a été divisé par deux entre avant et après. Dit autrement, il s'agit de l'inverse du rapport calculé précédemment. L'équation obtenue ainsi, qui donne le gain en performance que l'on peut attendre en fonction du nombre de processeur et du pourcentage de code parallèle, est appelée la loi d'Amdhal.

Cette loi nous donne donc une estimation du gain en temps d’exécution d'une application exécutée sur plusieurs processeurs. Mais que peut-on en déduire d'utile ? Peut-on trouver des moyens de gagner en performance efficacement grâce à cette loi ? Oui, et c'est ce qu'on va voir.

La limite du code série[modifier | modifier le wikicode]

On peut déduire de cette loi qu'il existe une limite maximale du gain obtenu par parallélisme de tâche. Tout d'abord, remarquons une chose : quand on fait tendre le nombre de processeurs vers l'infini, le gain atteint un maximum qui vaut :

On voit que quand N tend vers l'infini, le code parallélisé est exécuté en un temps qui tend vers 0. Seul reste le code série qui ne peut pas être accéléré par plusieurs processeurs. Si le nombre de processeurs devient infini, le gain tend naturellement la borne maximale . Dit autrement, le temps d’exécution d'un programme ne peut pas descendre en dessous du temps d’exécution du code série, même avec une infinité de processeurs. C'est la première limite que nous impose la loi d'Amdhal.

La solution la plus simple est donc de paralléliser le plus possible le code de notre programme, histoire de faire diminuer S et augmenter P le plus possible. C'est cela qui est le plus recherché à l'heure actuelle. Seul problème : tous les programmes ne se laissent pas paralléliser aussi facilement. Certains programmes se parallélisent facilement parce que les calculs qu'ils ont à faire sont assez indépendants. Mais d'autres n'ont pas cette particularité et sont très très difficilement parallélisables, voire pas du tout.

L'influence du nombre de CPU[modifier | modifier le wikicode]

La loi d'Amdhal nous dit qu'augmenter le ombre de processeur permet de diminuer le terme , et donc d'augmenter le gain. Mais cette solution a une efficacité assez limitée : il faut que la part de code parallélisable soit suffisante pour que cela ait un impact suffisant. Imaginons un exemple simple : 20% du temps d’exécution de notre programme (quand il est exécuté sur un seul processeur) est passé à exécuter du code parallèle. Avec N processeurs, le gain calculable par la loi d'Amdhal nous donne un gain maximal de . Si on calcule le gain en fonction du nombre de processeurs, on obtient alors la tableau suivant.

Nombre de processeurs Gain maximal
2 11.11%
3 15.38%
4 17.64%
5 19.04%
6 20%
7 20.6%
8 21.21%
... ...
16 23%
... ...
\infty 25%

On voit bien qu'au-delà de 5 ou 6 processeurs, augmenter le nombre de processeurs ne sert pas vraiment à grand-chose : doubler leur nombre revient souvent à augmenter les performances d'un misérable pourcent. Au-delà de 10 processeurs avec un code passant 20% de son temps à exécuter du code parallèle, le gain est négligeable. Pour prendre un autre exemple, au-delà de 8 processeurs, un code passant 50% de son temps à exécuter du code parallèle ne sera pas vraiment exécuté plus vite. 8 processeurs, cela correspond à un processeur à quatre cœurs incorporant la technologie SMT comme on en trouve chez Intel. Remarquons que les programmes qui passent la moitié de leur temps à exécuter du code parallèle sont rares chez les programmes grand-public. L'augmentation du nombre de processeur a donc une efficacité limitée. En clair : au-delà d'un certain nombre de processeurs, ça ne vaut plus le coup !

Pour résumer, le rendement du parallélisme diminue rapidement avec le nombre de processeurs. Passer de 2 à 4 processeurs permet d'obtenir des gains substantiels, alors que passer de 16 à 32 processeurs ne donne de gains sensibles que si P est extrêmement élevé.

Loi d'Amdhal.
Parallelization diagram.

Limites pratiques[modifier | modifier le wikicode]

Il faut préciser que la loi d'Amdhal est optimiste : elle a été démontrée en postulant que le code parallèle peut être réparti sur autant de processeurs qu'on veut et peut profiter d'un grand nombre de processeurs. Dans la réalité, rares sont les programmes de ce genre : certains programmes peuvent à la rigueur exploiter efficacement 2, 4 , voir 8 processeurs mais pas au-delà. Elle ne tient pas compte des nombreux problèmes techniques, aussi bien logiciels que matériels qui limitent les performances des programmes conçus pour exploiter plusieurs processeurs. La loi d'Amdhal donne une borne théorique maximale au gain apporté par la présence de plusieurs processeurs, mais le gain réel sera quasiment toujours inférieur au gain calculé par la loi d'Amdhal.

Parallélisme de données[modifier | modifier le wikicode]

Le parallélisme de données est très utilisé pour des applications où les données sont indépendantes, et peuvent se traiter en parallèle. Un bon exemple est le calcul des graphismes d'un jeu vidéo. Chaque pixel étant colorié indépendamment des autres, on peut rendre chaque pixel en parallèle. C'est pour cela que les cartes vidéo contiennent un grand nombre de processeurs et sont des architectures SIMD capables d’exécuter un grand nombre de calculs en parallèle.

Le parallélisme de données n'a pas les limitations intrinsèques au parallélisme de tâches. En effet, celui-ci est avant tout limité certes par le code série, mais aussi par la quantité de données à traiter. Prenons le cas d'une carte graphique, par exemple : ajouter des processeurs ne permet pas de diminuer le temps de calcul, mais permet de traiter plus de données en même temps. Augmenter la résolution permet ainsi d'utiliser des processeurs qui auraient été en trop auparavant. Reste à quantifier de tels gains, si possible avec une loi similaire à celle d'Amdhal. Pour cela, nous allons partir du cas où on dispose d'un processeur qui doit traiter N données. Celui-ci met un temps à éxecuter le code série et un temps pour traiter une donnée. On a donc :

Avec N processeurs, le traitement des N données s'effectuera en un temps , vu qu'il y a une donnée est prise en charge par un processeur, sans temps d'attente.

Le gain est donc :

On voit que le gain est proportionnel au nombre de données à traiter. Plus on a de données à traiter, plus on gagnera à utiliser un grand nombre de processeurs. Il n'y a pas de limites similaires à celles obtenues à la loi d'Amdhal, du moins, tant qu'on dispose de suffisamment de données à traiter en parallèle.

Loi de Gustafson.