Upload
nina-valentin
View
112
Download
6
Embed Size (px)
Citation preview
Informatique parallèle hautes performances
Présentation à l’université de Franche-Comté
19 novembre 2003
Page 2
bru
no.r
icha
rd@
com
pute
r.org
Plan de la présentation
Introduction Le matériel Programmation parallèle Expérience TOP500 L’architecture I-Cluster
Page 3
bru
no.r
icha
rd@
com
pute
r.org
Les segments de marché
Conception mécanique Science des matériaux Défense et sécurité Conception
microélectronique Géo-sciences Sciences de la vie Visualisation
Page 4
bru
no.r
icha
rd@
com
pute
r.org
Besoins du calcul parallèle
Calcul hautes performances Trop gros
En mémoire Sur disque
Trop long Météo Mais de durée rarement
infinie
Les limites Les processeurs/mémoires
sont limités
Les objectifs Efficacité Optimisation du coût Matériel Héritage de vieux codes
Les solutions Work Faster
Matériel plus rapide Work Smarter
Meilleur algorithme Work Harder
Parallélisme
Page 5
bru
no.r
icha
rd@
com
pute
r.org
Différents domaines applicatifs
Algèbre linéaire Mécanique des fluides (Navier-Stockes)
Manipulations spectrales Transformées de Fourier, DCT
Simulations Monte-Carlo
Extraction Repliement de protéines (recherche de sous-chaînes)
Autres Le reste ne représente que 10 à 20% du marché
Page 6
bru
no.r
icha
rd@
com
pute
r.org
Plan de la présentation
Introduction Le matériel Programmation parallèle Expérience TOP500 L’architecture I-Cluster
Page 7
bru
no.r
icha
rd@
com
pute
r.org
Composants Matériel
RAM CPU
ALU Registres Pipeline, VLIW, out-of-order
Cache IO Réseau
Cartes faible latence Routage Stockage
Temps d’accès différents registre << cache << ram << réseau <<
disque Coût inversement proportionnel au
temps d’accès
Logiciel Middleware
Système d’exploitation Coordination Ordonnancement de travaux
Librairies Passage de messages Algèbre linéaire
Compilateurs Hints
Page 8
bru
no.r
icha
rd@
com
pute
r.org
Architectures
Vectoriel SMP Cluster de calcul Constellation Grille Métaordinateurs
Retour vers le futur Les infrastructures du passé reviennent Ex.: Web, LDAP
Page 9
bru
no.r
icha
rd@
com
pute
r.org
Types d’architectures selon Flynn
Classification de Flynn Un peu désuète (sixties) Ne reflète pas l’architecture mémoire
MIMD-SM (Shared Memory) MIMD-DM (Distributed Memory)
SPMD (Single Program Multiple Data) est un cas courant (cf. MPI)
Flot de données
Unique Multiple
Flot d’instructions Unique SISD (Von Neumann)
SIMD
(Vectoriel)
Multiple MISD (Systolic)
MIMD
Page 10
bru
no.r
icha
rd@
com
pute
r.org
Symmetric Multiprocessing (SMP)
Cas le plus courant (bipros) Mémoire partagée
Le cache est essentiel Assure la cohérence Relation « happens-before »
Accès par lignes de cache 4096 bits par exemple 0x00cf2351 accède la ligne 0x00cf2000: 0x00cf2fff
Une écriture rend la ligne invalide (dirty) Différentes politiques possibles
Write-back Write-through Cache
Mémoire
CPU 1 CPU 2
Page 11
bru
no.r
icha
rd@
com
pute
r.org
SMP avec Crossbar Accès cohérent
p processeurs n mémoires Chaque processeur peut être mis en relation avec chaque mémoire
Exemple du réseau butterfly (où n=p) Composé de multiplexeurs 2x2
p1
p2
p3
p4
m1
m2
m3
m4
p5
p6
p7
p8
m5
m6
m7
m8
Page 12
bru
no.r
icha
rd@
com
pute
r.org
Cluster
Définition : Mémoire distribuée Coût faible Il faut gérer le passage de messages
Cohérence Transmission des messages « lente » Code spécifique et complexe
Réseau
Proc 1 Proc 2 Proc 3
Mem. 1 Mem. 2 Mem. 3
Page 13
bru
no.r
icha
rd@
com
pute
r.org
Réseaux faible latence Souvent présents dans les clusters de calcul Plusieurs implémentations disponibles
SCI, Myrinet, Quadrics Débit élevé Latence en ns
Routage à la source Chaque machine va router le message Les cartes réseau sont intelligentes Routage Wormhole
Topologie virtuelle en tores 2D ou 3D Possibilités de remote DMA, Scatter/Gather Solutions très chères
Exemple : Tore 2D Routage de [1,2] (en rouge) à [2,4] (orange)
Sud, Est, Est est le chemin pré calculé
1 2 3 4
1
2
3
4
Page 14
bru
no.r
icha
rd@
com
pute
r.org
Technologies d’interconnexion
Technologie Débit [Mo/s] Latence [us] Remarques
Gigabit Ethernet
125 60 à 90 Lenteur de la pile TCP-IP
Myrinet 2000 250 3 à 10 PCI 64 bits 66 MHz
SCI D330 666 1,5 Topologie en anneau
Page 15
bru
no.r
icha
rd@
com
pute
r.org
Grilles (GRID) Vision : Disposer de puissance de calcul de la même manière que de puissance
électrique Power outlet / Power grid
Cluster = Machines homogènes locales Grille = Machines hétérogènes globales
Fédération de ressources Répartition souvent mondiale Liaison entre plusieurs grappes par liens rapides
Mais… Aspects humains (tu peux me donner ton mot de passe ?) Les administrateurs sont sur chacun des différents sites
Passage à l’échelle difficile Copie d’un fichier vers 5000 machines = gros problèmes en vue…
Problèmes algorithmiques Couplage de Composants
Page 16
bru
no.r
icha
rd@
com
pute
r.org
Stockage hautes performances
Problème : Accès simultané aux fichiers Nombreuses machines en parallèle Visibilité homogène des données
Solutions Caches coopératifs
NFS Réplication des données
Pré chargement (prefetch) RAID logiciel et matériel
Problème de cohérence PVFS NFSp
Page 17
bru
no.r
icha
rd@
com
pute
r.org
Parlons d’argent…
La vitesse des processeurs dépend du carré de leur coût Speed = Cost2
L’accélération est généralement liée logarithmiquement au nombre de processeurs Speedup = log2(#processors)
Le logiciel coûte très cher Il faut donc faire attention a ses choix d’infrastructure
La tentation des clusters est grande Le choix n’est pas facile
Mais La plupart des projets ont un budget militaire ou scientifique
Ils sont riches A quoi bon changer de modèle et passer aux clusters ? Résultat : On en reste aux machines sur-performantes, par facilité
Page 18
bru
no.r
icha
rd@
com
pute
r.org
Plan de la présentation
Introduction Le matériel Programmation parallèle Expérience TOP500 L’architecture I-Cluster
Page 19
bru
no.r
icha
rd@
com
pute
r.org
Complexité
Il faut caractériser les algorithmes Complexité
En nombre d’instructions En nombre d’emplacements mémoire En nombre de messages à échanger
Ordre des algorithmes Fonctions O (coût réel), Ω (min), θ (max)
Caractérise le coût relativement a une fonction simple Ex.: O(n3), O(n log2n)
Un ordre non polynomial interdit le passage à l’échelle Un ordre (poly-)logarithmique est souhaitable
Page 20
bru
no.r
icha
rd@
com
pute
r.org
Taille de grain Grain Gros (niveau d’une tâche) Programme
Grain moyen (niveau contrôle) Fonction
Grain fin (niveau données) Boucle
Grain très fin (multiples niveaux) Hardware
Tâche i-lTâche i-l Tâche iTâche i Tâche i+lTâche i+l
func1 ( ){........}
func1 ( ){........}
func2 ( ){........}
func2 ( ){........}
func3 ( ){........}
func3 ( ){........}
a (0) = ..b (0) = ..
a (0) = ..b (0) = ..
a (1) = ..b (1) = ..
a (1) = ..b (1) = ..
a (2) = ..b (2) = ..
a (2) = ..b (2) = ..
++ xx LoadLoad
Page 21
bru
no.r
icha
rd@
com
pute
r.org
Exemple : Multiplication de matrices carrées (séquentielle) Soient A=[aij], B=[bij], C=[cij] , 1≤i≤n, 1≤j≤n On veut calculer C = A x B
cik=Σj=1..naij.bjk, 1≤i≤n, 1≤k≤n Complexité de calcul
Ceci nécessite, pour chaque cik : n multiplications n additions
n.n cik , donc n2 éléments, d’où 2n3 opérations L’ordre de la multiplication de matrices par un programme séquentiel est donc
O(n3) Place mémoire
3 matrices de taille n2
Le besoin en mémoire est donc de O(n2)
Page 22
bru
no.r
icha
rd@
com
pute
r.org
Multiplication plus efficace Si on a un cache trop petit, la performance s’écroule
3n2 valeurs ne tiennent plus en cache Le cache ne sert plus !
On va faire des calculs par blocs Même ordre, mais plus efficace (gains de 2000% en Pentium-class)
B
AC
Pour chaque sous-bloc : I bandes verticales J bandes horizontales
Pour chaque sous-bloc Cmp de Ccik=Σj=1..naij.bjk m≤i≤m+I, p≤k≤p+J
Mémoire nécessaire par bloc : I.n + J.n + I.J Au lieu de 3.162=768, on a 2.16 + 2.16 + 2.2 = 68 seulement
Problème identique : Out of coreEx.: n=16, I=J=2
Page 23
bru
no.r
icha
rd@
com
pute
r.org
Multiplication parallèle
p processeurs pour calculer Calcul par sous-blocs
n/p sous-blocs calculés par processeur Mais :
Chacun doit d’abord disposer des données de départ (Matrices A et B)
Mémoire partagée (SMP) : gratuit Les données sont accessibles à chaque processeur
Cluster : Envoi des 2n2 données (A et B) vers p processeurs, retour de n2 données (C) Donc coût de communication O(2p.n2) acceptable
Question : Quel est le grain de calcul de matmut() ?
Page 24
bru
no.r
icha
rd@
com
pute
r.org
OpenMP
Open Multi Processing Standard industriel de 1997 Clauses de compilation explicites (hints)
Modèle master-worker, fork & join Description des structures parallélisables
Matrices décomposées en sous blocs Le code contient des hints de gestion des sous-blocs
Le compilateur est intelligent Parallélise automatiquement le code Gère les communications inter-nœuds Parallélisme de données ou de processus
Page 25
bru
no.r
icha
rd@
com
pute
r.org
Le passage de messages
MPI (Message Passing Interface) Abstraction de la topologie de proc/RAM Routines de communication
MPI_Send(), MPI_Recv() Gestion par numéro de machine Primitives de groupes (communicators)
Synchrones ou asynchrones Simple a appréhender
Mais… mise au point douloureuse Portage pas si trivial que ça
Page 26
bru
no.r
icha
rd@
com
pute
r.org
Recouvrement calcul-communication
Objectif : efficacité Lors d’une attente de communication, un processus
va continuer à calculer Difficile à formaliser Très difficile à programmer Extrèmement difficile à débugger
Décomposition des communications Emballage du message (par l’émetteur) Temps de transport Déballage (par le récepteur)
Page 27
bru
no.r
icha
rd@
com
pute
r.org
Problèmes liés au parallélisme Horloges logiques Synchronisation
Systèmes asynchrones : Comment alerter un processus distant ? Accès sérialisé aux ressources partagées
Exclusion mutuelle False sharing Deadlocks
Fautes – Terminaison Détection de fautes Tolérance
Communication de groupe Élection d’un coordinateur (leader)
Réplication Cohérence
Mise au point répartie Bugs Performance
Connaissance du métier de l’application
Page 28
bru
no.r
icha
rd@
com
pute
r.org
Précédence causale
Relation happens-before (précède) Élément essentiel en informatique distribuée
Asynchronisme du monde réel => race conditions Illustre bien qu’en informatique distribuée, les choses simples
deviennent plus complexes… ei précède ej (ei < ej) ssi une de ces 3 conditions est vraie :
1. ei et ej se produisent sur le même processus et ei se produit physiquement avant ej
2. ei et ej se produisent sur deux processus distincts et ei est l’émission d’un message tandis que ej est la réception de ce même message
3. Il existe k tel que ei < ek et ek < ej
Exemples…
Page 29
bru
no.r
icha
rd@
com
pute
r.org
Horloges logiques
Horloge logique : e < e’ => LC(e) < LC (e’) quels que soient e et e’ Horloge logique de Lamport
Chaque nœud Pi détient un compteur Ti
Lors d’un évènement local Ti est incrémenté Lors d’un envoi par Pi, Ti est incrémenté et transmis avec le message Lors d’une réception par Pj, Tj est mis à jour
Tj = max(Tj, Ti ) + 1 Solution simple et élégante, très utilisée en pratique
Une version vectorielle existe, qui vérifie aussi LC(e) < LC (e’) => e < e’ Exemple :
P1
P2
P3
P4
1 2
31
1
1 2
4
7 8
9
4 53 6
Page 30
bru
no.r
icha
rd@
com
pute
r.org
Ordonnancement
Objectif : Optimisation des ressources Lancer n tâches sur p processeurs
Notion de graphe de flot d’exécution (ex.: POVray) Comment utiliser les processeurs inactifs ?
Différentes politiques Temps global d’exécution (makespan) Charge de calcul Tâches prioritaires
Allocation dynamique (online) ou statique (off-line) L’allocation statique nécessite un graphe de flot connu
Problème NP-complet On a recours à des heuristiques Beaucoup de recherche
Page 31
bru
no.r
icha
rd@
com
pute
r.org
Plan de la présentation
Introduction Le matériel Programmation parallèle Expérience TOP500 L’architecture I-Cluster
Page 32
bru
no.r
icha
rd@
com
pute
r.org
Les 500 ordinateurs les plus puissants Classement ouvert à tous Publication tous les 6 mois Objectif : le plus grand nombre possible d’instructions
par seconde Inversion d’une matrice dense Calcul itératif par décomposition de Cholesky Une implémentation de base : HPL (Linpack)
Notre objectif :entrer au TOP500 avec du matériel de grande
consommation
Page 33
bru
no.r
icha
rd@
com
pute
r.org
Infrastructure d’évaluation
Partenariat HP Labs, IMAG-ID, INRIA
225 HP e-Vectra: Pentium® III 733 MHz 256 MB Standard Ethernet
(100 MBps)
Page 34
bru
no.r
icha
rd@
com
pute
r.org
Mise en place du programme
Coordination entre 225 machines Pas facile Il ne faut pas ralentir par excès de communication
Chaque élément n’est plus un réel On passe à des petites matrices (sous-blocs)
Calcul de la taille de sous-bloc optimale Division en 15x15 machines
Problématique du broadcast
Page 35
bru
no.r
icha
rd@
com
pute
r.org
Résultats
Premier cluster de grande consommation au TOP500
385ème Superordinateur au monde, 15ème en France
81,6 Gflop/s en mai 2001
Page 36
bru
no.r
icha
rd@
com
pute
r.org
Leçons clés La latence réseau est
critique On attend autant qu’on
calcule
Homogénéité des machines Sinon l’algorithmique est
trop difficile
Questions ?
Page 38
bru
no.r
icha
rd@
com
pute
r.org
Exemple didactique
Un incendie Un robinet Des robots-pompiers R[i], i = 1, 2, 3…
Chacun possédant un seau et un seul Actions possibles :
Remplir pour remplir le seau au robinet Echanger(j) pour échanger son seau avec R[j] Déverser pour verser le seau sur l’incendie Marcher pour aller au robinet ou au foyer
Contraintes 1 seul robot peut remplir son seau à la fois Échange possible uniquement si les 2 robots sont prêts Pas de collisions pendant la marche, ni le déversage de seaux
Problème : Comment programmer le fonctionnement des pompiers ?
Page 39
bru
no.r
icha
rd@
com
pute
r.org
Quel algorithme
Solution 1 : Robots autonomes (SIMD) Chacun va remplir son seau, le déverse etc…
Solution 2 : La chaîne (pipeline) Un robot remplit les seaux, un autre les déverse et
tous les autres échangent seaux vides contre seaux pleins
Ces deux approches sont très différentes Goulot d’étranglements différents