Architectures
parallèles
Chargé de cours: Lévis Thériault
Département de génie logiciel et des TI
Sommaire
Introduction
Réseaux d’interconnexion
Tableaux de processeurs
Multiprocesseurs
Multi-ordinateurs
LOG645 – Architectures de calculs parallèles 2
Matériel développé par Lévis Thériault, Automne 2014
Introduction
1960-1990 : beaucoup de développement dans les
architectures, mais trop de variété
- Processeurs : fabrication propriétaire vs. générique
- Petit nombre de processeurs super-puissants vs. grand nombre de
processeurs « ordinaires »
Aujourd’hui :
- Utilisation de CPU génériques, croissance plus rapide que les
technologies propriétaires
Questions
- Comment relier ces processeurs les uns aux autres?
- Comment relier ces processeurs à la mémoire ?
LOG645 – Architectures de calculs parallèles 3
Matériel développé par Lévis Thériault, Automne 2014
Réseau d’interconnexion
Sert à :
- Relier les processeurs à une mémoire partagée
- Relier les processeurs les uns aux autres
Le médium du réseau peut être :
- Partagé
- Commuté
Problématique :
- Vitesse de communication vs. vitesse des processeurs
LOG645 – Architectures de calculs parallèles 4
Matériel développé par Lévis Thériault, Automne 2014
Médium partagé
Les messages sont envoyés à tous, un à la fois
Tous les processeurs reçoivent le message mais
seuls ceux identifiés comme destinataires le
conservent
Exemple : Ethernet
Beaucoup de communications collisions
P P P P
LOG645 – Architectures de calculs parallèles 5
Matériel développé par Lévis Thériault, Automne 2014
Médium commuté
Permet des communications point-à-point entre paires
de processeurs
Chaque processeur a un lien avec le médium
Principaux avantages sur le médium partagé
- Permet des communications simultanées
- Plus extensible à de grand nombre de processeurs
Médium commuté
Principaux inconvénients :
- Complexité
P P P P
- Coût
LOG645 – Architectures de calculs parallèles 6
Matériel développé par Lévis Thériault, Automne 2014
Topologie du réseau d’interconnexion
Directe : 1 processeur = 1 commutateur
Indirecte : Nb processeurs < Nb commutateurs
Critères de performance du réseau :
- Diamètre : Distance maximum entre 2 nœuds
- Largeur bissectionnelle : Nombre min. de liens devant
être enlevés pour sectionner le réseau en deux moitiés
- Degré : Nb de liens directs d’un nœud vers d’autres
nœuds
- Longueur des liens entre les noeuds
LOG645 – Architectures de calculs parallèles 7
Matériel développé par Lévis Thériault, Automne 2014
Topologie du réseau d’interconnexion
Exemples:
Point-à-point Grille
Étoile Arbre hyperbolique
Arbre binaire Bus
Maillé Multi-étage
Hypercube Matriciel (« crossbar »)
Anneau
Aucune topologie n’est supérieure sur tous les
critères
LOG645 – Architectures de calculs parallèles 8
Matériel développé par Lévis Thériault, Automne 2014
Tableaux de processeurs (arrays)
Ordinateur vectoriel : ordinateur contenant des
instructions sur des vecteurs (tableau de valeurs)
Tableau (réseau) de processeurs : ordinateur
vectoriel comprenant un ensemble d’éléments de
calcul identiques et synchrones
Les éléments de calcul sont des processeurs primitifs
contrôlés par un processeur standard
Les processeurs effectuent simultanément la même
opération sur des données différentes
LOG645 – Architectures de calculs parallèles 9
Matériel développé par Lévis Thériault, Automne 2014
Tableaux de processeurs (arrays)
Parallélisme de données
Vecteur < Tableau = Perte de performance
Vecteur > Tableau = « Mapping » (manuel ou
système)
LOG645 – Architectures de calculs parallèles 10
Matériel développé par Lévis Thériault, Automne 2014
Besoin d’architectures flexibles
Problèmes associés aux ordinateurs vectoriels
- Peu flexibles (limité principalement au parallélisme
de données)
- Difficiles à programmer
- Technologie progressant trop lentement par rapport
aux processeurs génériques
- …
LOG645 – Architectures de calculs parallèles 11
Matériel développé par Lévis Thériault, Automne 2014
Besoin d’architectures flexibles
2 types d’ordinateurs mieux adaptés aux
besoins actuels se sont développés depuis les
années 90
- Multiprocesseurs
- Multi-ordinateurs
LOG645 – Architectures de calculs parallèles 12
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur
Ordinateur comprenant plusieurs processeurs
pouvant être génériques
Mémoire partagée
Supporte plusieurs utilisateurs
2 types :
- Centralisé
- Distribué
LOG645 – Architectures de calculs parallèles 13
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur centralisé
Extension de l’architecture séquentielle typique
- Un bus relie les processeurs à la mémoire et aux E/S
- La mémoire cache permet d’accélérer les calculs sur
chaque processeur en réduisant les accès à la mémoire
2 autres appellations, liées au temps d’accès à la
mémoire par tous les processeurs :
- Uniform Memory Access (UMA)
- Symmetric MultiProcessor (SMP)
LOG645 – Architectures de calculs parallèles 14
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur centralisé
Les processeurs communiquent par des
lectures/écritures sur des variables en mémoire
partagée
Les caches réduisent la CPU CPU CPU
charge sur bus/mémoire
Cache Cache Cache
Bus
Mémoire Entrées
principale /Sorties
LOG645 – Architectures de calculs parallèles 15
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur centralisé
Exemples :
- IBM p5 570, 16 procs 1.9 GHz, 32 GB RAM
- Sun Blade X6250, 8 procs 3 GHz, 32 GB RAM
2 Problèmes :
- Cohérence de cache
- Synchronisation
LOG645 – Architectures de calculs parallèles 16
Matériel développé par Lévis Thériault, Automne 2014
Cohérence de cache
La duplication de certaines données dans les caches
permet de minimiser les accès mémoire
Que fait-on lorsqu’une écriture est effectuée?
Protocole de cohérence de cache : ensemble de règles
assurant que les processeurs possèdent la même
valeur d’un emplacement mémoire
- Snoopy bus (espionnage)
LOG645 – Architectures de calculs parallèles 17
Matériel développé par Lévis Thériault, Automne 2014
Synchronisation
Dans certains cas d’exécution parallèle, des règles de
précédence doivent être respectées
Dans un contexte de mémoire partagée, des mécanismes
permettent d’assurer un certain ordre dans les opérations
- Exclusion mutuelle : seulement un processeur doit effectuer une
partie de programme
- Section critique : partie de programme ne pouvant être effectuée
que par un processeur à la fois
- Barrière de synchronisation : les processeurs sont arrêtés à un
certain point du programme jusqu’à ce que tous les processeurs
aient atteint ce point
Ces mécanismes peuvent être implémentés de façon matérielle
ou logicielle
LOG645 – Architectures de calculs parallèles 18
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur distribué
La mémoire principale est distribuée entre les
processeurs
Les accès à la mémoire locale sont plus rapides
que ceux à la mémoire distante
Permet un plus grand nombre de processeurs
CPU CPU CPU
Cache Cache Cache
Mémoire E/S Mémoire E/S Mémoire E/S
Réseau d’interconnexion
LOG645 – Architectures de calculs parallèles 19
Matériel développé par Lévis Thériault, Automne 2014
Multiprocesseur distribué
Même si elle est physiquement distribuée, la
mémoire est vue logiquement comme unique
Non Uniform Memory Access (NUMA) : les
temps d’accès à la mémoire peuvent varier
considérablement selon la localité
Réseau d’interconnexion :
- Problème : cohérence de cache
- Solution : protocole basé sur un répertoire
LOG645 – Architectures de calculs parallèles 20
Matériel développé par Lévis Thériault, Automne 2014
Multi-ordinateur
La mémoire est physiquement organisée comme celle du
multiprocesseur distribué
Logiquement, espaces d’adressage disjoints
Chaque processeur n’a accès qu’à sa propre mémoire locale
Interactions entre processeurs effectuées par passage de
messages
Peut être :
- Asymétrique
- Symétrique
LOG645 – Architectures de calculs parallèles 21
Matériel développé par Lévis Thériault, Automne 2014
Multi-ordinateur asymétrique
Composé d’un ordinateur principal complet et de plusieurs
ordinateurs dédiés au calcul
Ordinateur principal
- Point d’entrée du système
- Fonctionnalités standard d’un ordinateur (OS, E/S, etc.)
- Contient le programme qui contrôle les autres procs (ordinateurs)
Ordinateur
Ordinateur Réseau Ordinateur
Utilisateur
principal d’interconnexion
Ordinateur
Multi-ordinateur
LOG645 – Architectures de calculs parallèles 22
Matériel développé par Lévis Thériault, Automne 2014
Multi-ordinateur asymétrique
Ordinateurs dédiés au calcul
- Système d’exploitation minimal
- Pas d’entrées/sorties
Problèmes
- Une panne sur l’ordinateur principal, plus de machine !
- Beaucoup d’utilisateurs = goulot d’étranglement sur la
machine principale !
- Programmes difficiles à débugger, pas d’E/S sur les procs
- Nécessite l’écriture de 2 programmes (maître-esclave)
LOG645 – Architectures de calculs parallèles 23
Matériel développé par Lévis Thériault, Automne 2014
Multi-ordinateur symétrique
Ordinateurs identiques, même fonctionnalités
Plusieurs points d’entrée pour les utilisateurs
Avantages
- Charge répartie sur le système plutôt que concentrée
- Un ordinateur peut se permettre de tomber en panne
- Un seul programme pour tous les ordinateurs
Utilisateur
Ordinateur Ordinateur
Ordinateur Réseau Ordinateur
Utilisateur d’interconnexion
Ordinateur Ordinateur
Multi-ordinateur
LOG645 – Architectures de calculs parallèles 24
Matériel développé par Lévis Thériault, Automne 2014
Multi-ordinateur symétrique
Désavantages :
- Chaque nœud pouvant servir d’entrée et ayant sa propre
identité, l’illusion d’un seul système est difficile à
maintenir
- Difficulté de répartition de la charge de calcul générale,
de tous les utilisateurs, sur tous les processeurs
- Compétition entre les programmes pour le temps CPU
limite la performance
LOG645 – Architectures de calculs parallèles 25
Matériel développé par Lévis Thériault, Automne 2014
Clusters vs. réseaux de stations
Cluster
- Ensemble homogène d’ordinateurs
- Réunis géographiquement
- Nœuds dédiés au calcul parallèle
- Ressource unifiée de calcul parallèle
- Réseau haut débit (Fast/Gigabit Ethernet, Myrinet)
Exemple
- IBM Roadrunner (superordinateur, #7 mondial du
Top 500)
LOG645 – Architectures de calculs parallèles 26
Matériel développé par Lévis Thériault, Automne 2014
Clusters vs. réseaux de stations
Réseau de stations (Network of Workstations, NOW) :
- Ensemble hétérogène d’ordinateurs
- Souvent réparti géographiquement
- Les nœuds sont souvent déjà utilisés localement
- Calcul parallèle utilisation secondaire des machines
- Connectés par un réseau générique, souvent Ethernet
Exemple:
- LCA de l’ÉTS
LOG645 – Architectures de calculs parallèles 27
Matériel développé par Lévis Thériault, Automne 2014
Clusters vs. réseaux de stations
Comparaison des réseaux :
Latence Largeur de bande Coût par nœud
(sec) (Mbit/s) ($)
Ethernet ~150 10 ~10
Fast Ethernet 100 100 100
Gigabit Ethernet 100 1000 1000
Myrinet 7 1920 2000
Principal avantage des NOW = Peu coûteux et facile à
construire avec des composantes génériques
LOG645 – Architectures de calculs parallèles 28
Matériel développé par Lévis Thériault, Automne 2014
Conclusion
L’intérêt pour les tableaux de processeurs a
diminué avec
- Diminution du coût des microprocesseurs
- Rigidité du parallélisme de données
« Petits » ordinateurs parallèles
- 2 < Nombre de processeurs < 64
- Typiquement de type multiprocesseur
- Vue globale de la mémoire, cohérence de cache
LOG645 – Architectures de calculs parallèles 29
Matériel développé par Lévis Thériault, Automne 2014
Conclusion
« Grands » ordinateurs parallèles
- 64 < Nombre de processeurs < Quelques centaines
- Typiquement de type multi-ordinateur
- Souvent des clusters de multiprocesseurs
« Supers » ordinateurs parallèles
- Des milliers de processeurs
- Typiquement de type multi-ordinateur
- Souvent des clusters de multiprocesseurs
LOG645 – Architectures de calculs parallèles 30
Matériel développé par Lévis Thériault, Automne 2014
