Chapitre 2
Architectures Parallèles
Plan du cours
1. Quatre décennies de calcul
2. Principales architectures parallèles
3. Réseaux d’interconnexion
4. Clusters
5. Grids
1. Quatre décennies de calcul
La plus part des informaticiens admettent qu’il existe 4 domaines de
calcul distincts : batch, time-sharing, desktop et network.
Caractéristique Batch Time-sharing Desktop Network
Décennie 1960s 1970s 1980s 1990s/2000s
Emplacement Computer room Terminal room Desktop Mobile
(ordinateur) (mini-ordi) (micro-ordi)
Utilisateurs Experts spécialistes Individus Groupes
Connectivité Aucune Câble LAN Internet/Wireless
périphérique
Propriétaires Centre de calcul Divisional IS Utilisateurs N’importe qui
shops
2
Calcul parallèle
Le domaine de la programmation parallèle est visiblement en continuelle
évolution.
Depuis 1985, le domaine du parallélisme s’est considérablement
développé à cause des demandes toujours croissantes en puissance de
calcul.
Historiquement, il s’est développé dans le cadre de la construction de
systèmes d’exploitation.
Puis, des machines parallèles composées de multiples processeurs sont
apparues.
3
Elles peuvent généralement être classées en deux principales catégories :
• Machines à mémoire partagée (incluant les machines vectorielles).
• Machines à mémoire distribuée.
Autre type de machines : Machines synchrones (grand nombre d’éléments
de calcul (jusqu’à 65536) de faible puissance).
Le nombre de processeurs composant une machine peut varier de :
• Quelques dizaines dans une machine à mémoire partagée.
• Centaines de milliers dans un système massivement parallèle (MPP).
Actuellement : dominance des clusters (grappes).
4
2. Principales architectures parallèles
De nombreuses classifications des machines parallèles existent. La plus
répandue est celle de Flynn.
2.1. Classification de Flynn (1966)
C’est une classification simpliste, basée sur le nombre (seul ou
multiple) de :
• Flux d’instructions : séquence d’instructions exécutées par la
machine.
• Flux de données : séquence des données appelées par le flux
d’instructions.
Elle divise les machines parallèles en 4 catégories : SISD, SIMD,
MISD (n’est pas concrétisée par une machine réelle!) et MIMD.
Insuffisante pour classer finement les architectures parallèles.
5
Single Data Stream Multiple Data Stream
Single Instruction SISD SIMD
Stream Machines séquentielles machines vectorielles
Multiple Instruction
Stream MISD MIMD
machines multiprocesseurs
SPMD (Single Program Multiple Data) : variante de MIMD. Même programme
sur des données différentes.
SIMD < SPMD < MIMD
6
2.2. Architecture SIMD
Le modèle SIMD consiste en 2 parties : un frontal et un ensemble de
processeurs identiques synchronisés.
Chaque processeur exécute la même opération que les autres mais sur
des données différentes.
Chaque processeur possède une petite mémoire locale.
Les processeurs sont liés en utilisant un réseau d’interconnexion.
Ce modèle convient principalement pour des calculs numériques
réguliers (comme le traitement d’images).
En voie de disparition : il demande des processeurs spécifiques: PAS
ceux du marché -> dépassés par l’évolution constante des processeurs
du marché et par les machines parallèles MIMD qui les utilisent.
Exemples :
Cray-1 (1976), NEC SX-5, Tera/Cray SV1, Connection Machine CM-1
(1985),…
7
2.3. Architecture MIMD
Classe de machines la plus répandue.
Chaque processeur exécute son propre code sur ces propres données
de manière asynchrone et indépendante.
On distingue habituellement 2 sous-classes :
• MIMD à mémoire partagée : les processeurs de la machine ont
accès à une mémoire commune.
• MIMD à mémoire distribuée : les processeurs disposent chacun
d’une mémoire locale. Dans ce cas, un réseau d’interconnexion est
nécessaire pour échanger les informations entre processeurs.
8
M M M Réseau d’interconnexion
Réseau d’interconnexion
P P P
P P P M M M
MIMD à mémoire partagée MIMD à mémoire distribuée
9
Système à mémoire partagée
La coordination inter-processeurs est accomplie à travers une mémoire
globale partagée par tous les processeurs.
Ces systèmes sont aussi appelés SMP (Symmetric Multiprocessors).
En général entre 2 et 64 processeurs.
Leur programmation est relativement facile puisqu’il n’est plus
nécessaire de mettre en ouvre des communications explicites.
Extensibilité? En raison des coûts très élevés et de la complexité de
réalisation (il est très difficile de gérer une mémoire partagée à laquelle
pourraient accéder plusieurs dizaines de processeurs), les concepteurs
de machines parallèles ont opté pour le « distribué ».
Exemples : PC bi-processeurs, Cray SV1, SGI Origin3000, un nœud
de l’IBM SP3, …
10
Organisation de la mémoire : ces systèmes peuvent être classés en :
UMA (Uniform Memory Access) :
• Tous les processeurs ont le même temps d’accès à n’importe quelle
case mémoire.
• Aussi nommé SMP.
NUMA (Non UMA) : le temps d’accès à un module mémoire dépend de
la distance le séparant au processeur
• Appelé aussi cc-NUMA.
• Exp : SGI ORIGIN3000.
• Souvent construit comme reliant plusieurs SMP.
• Chacun des SMP peut accéder à la mémoire des autres SMP.
• Temps d’accès à la mémoire n’est pas égal pour tous.
• Extensible.
11
Système à mémoire distribuée
La notion de mémoire globale n’existe pas.
Les machines à mémoire distribuée sont les seules susceptibles de
fournir de très hautes performances : Extensibilité.
Exemples de systèmes dans les années 90 : Systèmes à base de
Transputers, Tera/Cray T3E, IBM SP3,…
MIMD CLUMPS : Clusters of SMP
Construits à partir de SMP.
Mémoire partagée au sein de chacun des SMP.
Mémoire distribuée entre SMP.
Exemple : IBM SP3 : des nœuds SMP de 16 processeurs chacun
reliés par un réseau dédié.
12
Remarque :
Malheureusement, pour exécuter un programme p fois plus rapide, il ne
suffit pas de faire exécuter ce programme sur p processeurs.
En effet, les processeurs devront échanger des données. Or, les coûts
de communication sont très importants. Les échanges de données
s’effectueront ainsi au détriment de la performance globale du calcul.
Optimiser les temps des mouvements de données au sein des machines
parallèles à mémoire distribuée est ainsi une clé pour l’obtention de
performances significatives sur ces machines.
13
Architectures parallèles et distribuées
(Leopold, 2001)
SIMD SMP CC-NUMA DMPC Cluster Grid
SIMD MIMD
Mémoire partagée
Mémoire distribuée
étroit Degré de Couplage vrac
fines Tailles de grains supportées
grossières
rapide Vitesse de Communication lente
14
2.4. Architecture hybride
La situation réelle est plus compliquée. On peut avoir des architectures
qui présentent des aspects couvrant plus d’une catégorie. En effet,
plusieurs machines sont de conception hybride.
Combiner les avantages des architectures à mémoire partagée et à
mémoire distribuée.
Donner naissance à une architecture à mémoire distribuée-partagée.
La mémoire est physiquement distribuée : l’architecture matérielle peut
suivre le modèle de passage de message, et la façon de programmation
suit le modèle à mémoire partagée.
Exemple de système : SGI Origin2000.
15
Systèmes parallèles et systèmes distribués
Systèmes parallèles :
• Ensemble d’éléments de calcul.
• Qui peuvent communiquer et coopérer.
• Pour résoudre rapidement de grands problèmes.
Systèmes distribués :
• Ensemble de processeurs autonomes.
• Qui ne se partagent pas de mémoire primaire.
• Mais qui coopèrent par envoi de messages à travers un réseau de
communication.
16
Systèmes parallèles / systèmes distribués
Pas parallèles, pas distribués
• PCs ou stations de travail (qui ne peuvent pas communiquer)
Parallèles, pas distribués
• Machines vectorielles
• Machines multiprocesseurs à mémoire partagée (SMP)
Distribués, pas parallèles
• Réseau de stations large distance (communications trop lentes)
Parallèles et distribués
• Réseau de stations de travail connectées à un réseau local/spécialisé
CLUMPS
17
3. Réseaux d’interconnexion
Les réseaux d’interconnexion des multiprocesseurs peuvent être classés
en se basant sur un nombre de critères, comme:
• Mode d’opération (synchrone vs asynchrone).
• Stratégie de contrôle (centralisée vs décentralisée).
• Techniques de switching (circuit vs paquet).
• Topologie (statique vs dynamique).
18
Topologie
• Généralement, un réseau de processeurs est représenté par un
graphe, dont les arêtes sont les liens de communication et les
sommets (nœuds), les processeurs.
• La plus part des architectures se fondent sur des topologies
régulières et statiques.
• Un réseau dynamique établit une connexion entre deux nœuds ou
plus à la volée lorsque des messages arrivent sur les liens.
19
Les topologies statiques les plus populaires sont les suivantes :
Anneau Grille 2D Hypercube Arbre Complet
Topologies dynamiques : crossbar, multi-étages,…
20
4. Clusters (Grappes)
4.1. Motivation
Les plateformes de super-calcul traditionnelles spécialisées, (comme le
Cray/SGI,T3E…) n’étaient accessibles qu’à une minorité d’individus à
cause de leurs prix élevés.
Avancés dans la technologie des réseaux et la disponibilité de stations
de travail de coût faible.
D’où la naissance des clusters dans les années 90.
21
4.2. Définition
Un cluster est une collection de noeuds faiblement couplés et
connectés à travers un réseau d’interconnexion.
Chaque nœud dans un cluster peut être un PC, une station de travail
ou même un système multiprocesseurs.
Lorsque tous les nœuds dans un cluster ont la même architecture et
exécutent le même SE, le cluster est dit homogène, sinon il est dit
hétérogène.
Le réseau d’interconnexion peut être par exemple un LAN rapide.
Les clusters fournissent un moyen économique pour avoir de la haute
performance. Un réseau de communication où sa bande passante est
élevée et sa latence est faible est nécessaire.
Les clusters dédiés utilisent souvent des réseaux rapides comme Fast
Ethernet et Myrinet.
22
4.3. Exemples de clusters
Tera-10 TSUBAME Grid Cluster
Largest system in Europe Largest system in Japan
No. 5 (Top500) No. 7 (Top500)
42,9 Tflops 38,18 TFlops
8704 procs, Itanium 2, 1.6 Ghz 10368 procs, Opteron 2.4 Ghz
Quadrics Infiniband
Bull NEC
France (CEA), 2006 Japan (TIT), 2006
23
5. Grids (Grilles)
Ian Foster (1998) : Analogie avec la distribution d’électricité
24
Réalité invisible à l’utilisateur
Infrastructure pour délivrer des capacités de
calcul/stockage/communication de façon transparente à l’utilisateur,
quand et où il les demande.
L’utilisateur ne perçoit pas l’architecture sous-jacente de la grille (son
middleware la masque).
L’utilisateur se contente de soumettre des requêtes à la grille !
• Où sont stockées mes données ?
• Où sont lancés mes calculs ?
25
Une grille de calcul est une collection de clusters hétérogènes éparpillés
géographiquement et connectés à travers des réseaux WAN ou Internet.
Elle est caractérisée par:
• Forte hétérogénéité
• Structure hiérarchique
• Distribution géographique des ressources
• Décentralisation
• Etc.
Exemples de plateformes : GRID5000 (France), TeraGrid (USA)
Chaque nœud est un cluster (256-1024 CPU)
Le débit du réseau peut atteindre 10GB/s
26
Les machines les plus puissantes dans les 20 dernières années
1985-1995
Cray-2 (1985-1990) CM-5/1024 MPP Numerical Wind Tunnel
(1992-1993) (1995)
1.2 GFlops 59.7 GFlops 170.4 GFlops
4 processeurs vectoriels 1024 processeurs SPARC 140 processeurs vectoriels
Mémoire partagée Réseau arbre plat Switch crossbar
Cray TMC Fujitsu
27
Earth Simulator MPP (2002-2004)
• 35.86 TFlops, 5120 processeurs
• 640 nœuds avec 8 processeurs vectoriels chacun
• Switch crossbar (2400 km de câbles)
• NEC
28
IBM BlueGene/L MPP (2005-2006)
• 280 TFlops, 131072 processeurs
• Chaque nœud a 2 PowerPC 440 à 700 Mhz
• Réseau toroidal 3D pour des communications peer-to-peer
• IBM
29
Quatre ères de calcul parallèle
1970s 1980s 1990s 2000s Au-delà 2000
Niveau du Processeur Machine LAN WAN Puce
parallélisme
Architecture Vectorielle SMP/MPP Cluster Grid Multi-core
Réseau Aucun Bus, Switch, Ethernet, Internet Sur le puce
d’interconnexion Grille, Switch
Hypercube
Programmation Vector, C*, C-Linda, PVM, MPI, MPI, ?
Fortran Occam, autres HPF, … OpenMP, …
30
