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