Fonctionnement d'un ordinateur/Les architectures parallèles

De nos jours, les processeurs avec plusieurs cœurs sont devenus la norme. L'utilité de tels processeurs est très simple : la performance ! Ils 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.

Le partage de la mémoire

On peut classer les architectures parallèles suivant comment se partage la mémoire entre les processeurs. Pour simplifier, il existe deux méthodes simples pour partager la mémoire. La première est la mémoire partagée, l'autre est celle des mémoires distribuées, avec une méthode intermédiaire.

La première méthode utilise une mémoire partagée entre tous les processeurs. Les processeurs peuvent alors entrer en conflit pour l'accès à la mémoire, ce qu'il convient de gérer au mieux. Par contre, l'implémentation peut être très efficace, particulièrement sur les architectures multicœurs.

Architecture à mémoire partagée.

Viennent ensuite les architectures switchées, où plusieurs processeurs sont reliés à plusieurs mémoires par l'intermédiaire d'un réseau de type crossbar. Grâce à l'interconnexion crossbar, tout processeur peut accéder à toutes les mémoires. Elle est possible avec un petit nombre de processeurs, où elle permet de réduire les conflits d'accès à la mémoire. Par contre, le temps d'accès à la mémoire est augmenté, le réseau d'interconnexion entre processeur et mémoire ajoutant un délai non-négligeable.

Architecture hybride à interconnexion crossbar.

Les architectures distribuées interconnectent plusieurs ordinateurs séparés avec un réseau local. Avec elles, chaque processeur possède sa propre mémoire rien que pour lui, qu'il est le seul à pouvoir l'adresser directement. Si un autre processeur veut accéder au contenu de sa mémoire, il doit passer par une transmission sur le réseau local. Les conflits d'accès à la mémoire disparaissent, mais l'implémentation est alors plus compliquée et les transferts sur le réseau ont un cout en performance important.

Architecture distribuée.

D'autres architectures sont des intermédiaires entre mémoire partagée et architectures distribuées. Par exemple, sur un système à 8 processeurs, on peut avoir deux ordinateurs reliés par un réseau, mais avec chaque ordinateur ayant une mémoire partagée entre 4 processeurs.

Architecture hybride.

Les avantages et inconvénients de la mémoire partagée/distribuée

Concrètement, les trois méthodes sont utilisées dans des cas bien différents. Les deux premières marchent bien avec un petit nombre de processeurs, alors que les architectures distribuées sont adaptées à un grand nombre de processeurs. Par contre, la mémoire partagée est un peu à part en termes de performances, comparé aux deux autres méthodes.

La raison est que partager un bus unique entre un grand nombre de processeurs ne marche pas très bien. Le débit binaire du bus est partagé entre tous les processeurs. Toutes choses égales par ailleurs, plus on ajoute de processeurs, moins chaque processeur aura de débit alloué. Et le débit binaire des bus a des limites rapidement atteintes, ce qui fait que la mémoire partagée est rarement mise en œuvre au-delà d'une dizaine de processeurs. Mais en utilisant des mémoires séparées, les deux mémoires seront accédées en parallèle, les deux processeurs n'entreront pas en conflit pour l'accès à la mémoire.

Niveau performances, les deux solutions font face à des défis différents. Exécuter beaucoup d'opérations sur des processeurs différents demande d'alimenter ces opérations en opérandes, ce qui implique une mémoire RAM avec un débit binaire suffisant. Dans le chapitre sur la performance d'un ordinateur, nous avions vu le roofline model, qui nous disait que dans certaines conditions, les applications voient leur performance limitée par le débit de la mémoire.

Roofline model

Et c'est un point où les mémoires partagées n'aident pas. Avec une mémoire partagée, le débit de la mémoire est partagé entre plusieurs cœurs/processeurs, ce qui fait qu'il devient un facteur limitant assez rapidement. Plus on cherche à exécuter de programmes/tâches/threads avec une intensité calculatoire fixe, plus on utilisera de débit mémoire et plus on se rapproche de ce point limitant. Par contre, avec une architecture distribuée, on n'a pas ce problème. Chaque processeur a sa propre mémoire, le débit binaire de sa mémoire lui est totalement dédié. Pour le dire autrement, le débit binaire total augmente avec le nombre de mémoires dans une architecture distribué, alors qu'il est fixe avec une mémoire partagée.

Un autre problème est celui des couts de synchronisation et d'arbitrage. Avec la mémoire partagée, rien n’empêche plusieurs processeurs de vouloir accéder à la mémoire en même temps, ce qui demande d'implémenter de quoi arbitrer les accès à la mémoire entre les processeurs. Les couts de synchronisation peuvent être conséquents et peuvent réduire les performances. Avec une architecture distribuée, les processeurs ne se marchent pas sur les pieds en accédant à la mémoire. Par contre, les transferts entre processeurs sont plutôt lents. Les processeurs peuvent accéder à la mémoire d'un autre processeur via le réseau local, qui permet les transferts entre processeurs. Les communications entre les différents processeurs peuvent prendre un temps relativement long, loin d'être négligeable. Il va de soi que la performance du réseau est primordiale : plus le réseau est rapide, meilleures seront les performances.

Le partage de l'espace d'adressage

Le partage de la mémoire impacte aussi un autre point très important : l'espace d'adressage des processeurs. Pour rappel, l'espace d'adressage d'un processeur correspond à l'ensemble des adresses utilisables par le processeur. Par exemple, si je prends un processeur 16 bits, il peut adresser en tout 2^16 = 65 536 adresses et l'ensemble de ces adresses forme son espace d'adressage. L'espace d'adressage n'est pas la mémoire réellement installée : s'il n'y a pas assez de RAM installée, des adresses seront inoccupées. De plus, une partie de l'espace d'adressage peut être détourné pour communiquer avec les périphériques.

Quand on dispose de plusieurs processeurs, deux possibilités surviennent : soit ils ont chacun leur espace d'adressage, soit ils partagent le même espace d'adressage. La mémoire partagée partage l'espace d'adressage sur plusieurs processeurs, pas d'erreur là-dessus. Les architectures switchées ont aussi un espace d'adressage partagé entre tous les processeurs. Logique : sans cela, ils n'auraient aucun intérêt à avoir un crossbar pour les relier à toutes les mémoires RAM. Pour résumer : si plusieurs CPU accèdent à la même mémoire, ils partagent leur espace d'adressage.

Sur les architectures distribuées, on s'attend à ce que chaque processeur ait son propre espace d'adressage, adossé à sa mémoire privée, sa mémoire locale. Mais ce n'est pas le cas pour un sous-type d'architectures distribuées, appelé les architectures NUMA (Non Uniform Memory Architecture). Avec elles, tous les processeurs voient un espace d'adressage global, qui contient les différentes mémoires locales. Lors des accès mémoire, les adresses utilisées sont des adresses de l'espace d'adressage global, de la totalité des mémoires. Si l'adresse est dans la mémoire locale du processeur, l'accès est direct. Dans le cas contraire, le système d'exploitation prend la relève et prépare une communication sur le réseau. Bien tirer parti de ces architectures demande de placer le plus possible les données en mémoire locale : l'idée est d'éviter les accès au réseau, qui sont lents.

Espace d'adressage d'une architecture NUMA.

Sur les architectures NUMA, migrer les données à la main peut aboutir à des migrations inutiles, le processeur n'ayant pas besoin des données transférées. Pour éviter ces copies inutiles, le meilleur moyen est de les faire à la demande. En faisant ainsi, chaque mémoire locale se comporte comme un cache, mais sans qu'il y ait de mémoire principale. On obtient alors une architecture COMA : Cache Only Memory Architecture. Ces architectures font cependant face à quelques problèmes. Premièrement, il faut pouvoir localiser la mémoire qui contient le bloc demandé à partir de l'adresse de ce bloc. Ensuite, on doit gérer la migration de blocs dans une mémoire locale pleine. Sur les architectures Simple-COMA, ces opérations sont déléguées au système d'exploitation. Seules les architectures Flat-COMA et Hierarchical-COMA effectuent ces opérations en matériel, en modifiant les circuits de cohérence des caches. La différence entre ces deux architectures tient dans le réseau d'interconnexion utilisé pour relier les processeurs.

Pour résumer :

	Mémoire partagée	Architecture switchée	Architecture distrbuée
Espace d'adressage partagé	Mémoire partagée	Architecture switchée	Architecture NUMA/COMA
Espace d'adressage séparé			Architecture distribuée

La taxonomie de Flynn

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.

Les architectures SISD sont incapables de toute forme de parallélisme.

Les architectures SIMD exécutent 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.

SIMD - taxonomie de Flynn.

Les architectures MISD exécutent des instructions différentes en parallèle sur une donnée identique. Les architectures MISD sont vraiment très rares.

MISD - taxonomie de Flynn.

Les architectures MIMD exécutent des instructions différentes sur des données différentes. 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.

MIMD - taxonomie de Flynn.

Les processeurs multicœurs et multiprocesseurs font partie de la catégorie MIMD.

\	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

La taxinomie de Flynn n'est pas parfaite, dans le sens où certaines architectures sont difficiles à classer. Mais cette classification, bien que simpliste, est particulièrement didactique et a remarquablement tenu le coup au fil du temps.

Le parallélisme de données et de tâches

Les architectures SIMD et SPMD effectuent ce qu'on appelle du parallélisme de données, à savoir exécuter un même programme sur des données différentes, en parallèle. La quasi-totalité des processeurs est aujourd'hui de ce type, qu'il s'agisse des processeurs Intel et AMD actuels ou de leurs confrères de chez ARM, MIPS et VIA. Le parallélisme de donnée est aussi massivement utilisé dans les cartes graphiques : chaque calcul sur un pixel est plus ou moins indépendant des transformations qu'on effectue sur ses voisins.

Le parallélisme de données s'oppose au parallélisme de tâches, qui exécute plusieurs programmes en parallèle. Il s'exploite en découpant un programme en sous-programmes indépendants qu'on peut exécuter en parallèle. Ces sous-programmes indépendants sont ce qu'on appelle des Threads. Les architectures permettant d’exécuter des threads en parallèle sont les architectures multiprocesseurs ou multicœurs, ainsi que quelques autres processeurs un peu spéciaux. 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 speculative multithreading dans ce tutoriel.

Les deux formes de parallélisme n'ont pas du tout la même efficacité, comme nous allons le voir. Pour faire la comparaison entre les deux, nous allons voir la loi d'Amdhal, qui décrit le parallélisme de tâche, et la loi de Gustafson, qui décrit le parallélisme de données.

Le parallélisme de tâches : la loi d'Amdhal

La loi d'Amdhal donne l’amélioration maximale que l'on peut obtenir d'un programme parallèle, quand il s’exécute sur plusieurs processeurs. Pour la calculer, 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, le 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.

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 conserve une certaine portion de code qui ne profite 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 $T_{s}$ et $T_{p}$. On sait que le temps $T$ mis par un programme à s'exécuter vaut donc :

$T=T_{s}+T_{p}$

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

$T_{\text{parallele}}=T_{s}+{\frac {T_{p}}{N}}$

Divisons par T :

${\frac {T_{\text{parallele}}}{T}}=\left(T_{s}+{\frac {T_{p}}{N}}\right){\frac {1}{T}}={\frac {T_{s}}{T}}+{\frac {T_{p}}{T}}{\frac {1}{N}}$

Maintenant, notons $S$ et $P$ 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 ${\frac {T_{s}}{T}}$ et ${\frac {T_{p}}{T}}$. Dans l'équation précédente, on peut identifier ces deux pourcentages (leur inverse, précisément). On a alors, en faisant le remplacement :

${\frac {T_{\text{parallele}}}{T}}=S+{\frac {P}{N}}$

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.

$G={\frac {1}{S+{\frac {P}{N}}}}={\frac {1}{1-P+{\frac {P}{N}}}}$

Cette formule, la loi d'Amdhal proprement dit, 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

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

${\text{Gain}}={\frac {1}{1-P}}={\frac {1}{S}}$

Quand N tend vers l'infini, le code parallélisé est exécuté en un temps qui tend vers 0 et seul reste le code série. 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. La solution la plus simple est donc réduire S et augmenter P le plus possible. 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

La loi d'Amdhal nous dit qu'augmenter le ombre de processeur permet de diminuer le terme ${\frac {P}{N}}$ et 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. 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%

Les chiffres précédents nous disent qu'aller au-delà de 5 ou 6 processeurs ne sert pas vraiment à grand-chose. Doubler leur nombre revient souvent à augmenter les performances d'un misérable pourcent. 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. 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.

Les limites pratiques

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.

Le parallélisme de données : la loi de Gustafson

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 $T_{s}$ à éxecuter le code série et un temps $T_{p}$ pour traiter une donnée. On a donc :

$T=T_{s}+T_{p}\times N$

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

$T_{\text{parallele}}=T_{s}+T_{p}\times N$

Le gain est donc :

${\frac {T_{\text{parallele}}}{T}}={\frac {T_{s}+T_{p}\times N}{T}}={\frac {T_{s}}{T}}+{\frac {T_{p}}{T}}\times N$

On peut utiliser les définitions $S={\frac {T_{s}}{T}}$ et $P={\frac {T_{p}}{T}}$ pour reformuler l'équation précédente :

$G=S+P\times N=1-P+P\times N$

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.