Algorithmes Parallèleset Systèmes Réparties

Frédéric Gava (MCF)gava@u-pec.fr

LACL, bâtiment P2 du CMC, bureau 221Université de Paris XII Val-de-Marne

61 avenue du Général de Gaulle94010 Créteil cedex

Différents modèles de programmation

Modèles de programmation Modèles de programmation et modèles d’exécution d’exécution

Ordonnancement et placement

Modèles de programmation

D’exécution, une abstraction de l’architecture matérielle mémoire partagée vs mémoire distribuée

SIMD/MIMD

De programmation, une abstraction de la sources du parallélisme : données/contrôle

Modèles de prog : Djikstra/Flynn

Parallélisme de contrôle

Composition parallèle de processus séquentiels

PAR(SEQ) MIMD

pardo i = 1, n

a(i) = b(i) +c(i)

x(i) = y(i) + z(i)

end do

Parallélisme de données

Composition séquentielle de processus parallèles

SEQ(PAR) SIMD

forall(||) i = 1, na(i) = b(i) +c(i)

forall(||) i = 1, nx(i) = y(i) + z(i)

Modèles d’exécution Espaces d’adressage multiples

p processus

Communiquent par messagerie

Le programmeur ou le compilateur doit définir le placement des données et l’ordonnancement des calculs

Le placement des données peut définir celui des calculs

Espaces d’adressage unique p threads

Communiquent à travers des variables partagées

Le programmeur ou le compilateur doit définir le placement et l’ordonnancement des calculs

Ordonnancement Programme = Graphe de tâches

Une tâche est une unité de traitement séquentiel

Un arc (T1, T2) correspond à un transfert d’information à la fin de T2 vers le début de T1

Un graphe de tâches sans cycle définit un ordre partiel

T1 << T2 s’il existe un chemin de T1 vers T2

Ordre total : programme séquentiel

Ordre partiel : programme parallélisable

Ordonnancement et modèle de programmation

La définition de l’ordonnancement peut être : Réalisée dans un programme parallèle

Extraite automatiquement d’une spécification plus ou moins contrainte : parallélisation automatique

L’expression de l’ordonnancement dans les langages parallèles : Par structures de contrôle : SEQ(PAR)

Par synchronisation : PAR(SEQ)

Placement : L’ordonnancement ne prend pas en compte le nombre de processeurs disponibles

Le placement replie le parallélisme illimité sur les ressources réelles

Contrainte : minimisation des surcoûts

Parallélisation = placement + ordonnancement

Placement statique

Off-line, éventuellement paramétré par le nombre de processus et le numéro de processus

Les temps de calcul doivent être connus : Cas régulier : Bloc, cyclique, cyclique (k), …

Cas irrégulier : ad hoc (p. ex. bisection récursive)

Décalage, distribution bloc

Bisection récursiveLes éléments de calcul sont caractérisés par une donnée nD souvent une position spatiale

Applicable aussi à un maillage

Placement et ordonnancement dynamique

Motivation: La durée des calculs n’est pas prévisible

La puissance des machines n’est pas connue

Placement/ordonnancement on-line : décidé à l’exécution

Questions : Surcoûts : gestion des processus ou des threads, des échanges d’information

Robustesse à l’irrégularité des temps d’exécution

Centralisé: Maître-Esclave Maître :

Implémente un algorithme de partitionnement, par exemple bloc, avec possibilité de taille variable du bloc

– Taille fixe : équivalent à statique

– Guided self-scheduling: chaque esclave prend 1/p de ce qui reste

– Factoring: chaque esclave prend 1/P de la moitié du batch restant

Effectue les opérations globales par exemple réduction

p esclaves : Exécutent un bloc, et redemandent du travail dès que terminé

Placement et ordonnancement dynamique

Répartition par vol de travail Un processus pousse sur la pile des travaux en attente les tâches les plus longues

Les processus ou threads inactifs sélectionnent un autre processus auquel ils prennent du travail au fond de la pile

Peut être prouvé optimal pour une large classe d’applications

Implémentation délicate : gestion de verrous en espace d’adressage unique, protocole en espaces d’adressages multiples

http://supertech.lcs.mit.edu/cilk/

Placement et ordonnancement dynamique

Analyse de performances

Suite du cours ...

Parallelisation Automatique

Introduction Méthodes systématiques et automatisables

Analyse d’un programme séquentiel, fonctionnel, parallèle

Pour la définition d’un ordonnancement compatible avec la sémantique du programme

Exprimable dans une syntaxe parallèle

Aide à la parallélisation manuelle.

Les paralléliseurs automatiques et leurs limites

Reférence : Randy Allen and Ken Kennedy. Optimizing compilers for modern architectures. Morgan Kaufmann. 2002.

Mais les aspects avancés (“méthodes polyédriques”) ne sont pas traités.

Nids de boucles Boucles et séquences :

pas de conditionnelles,

ni de procédures

Instruction : occurrence textuelle

Opération, occurrence dynamique. Ex : A(1, 3, 2)= ...

Méthodologie Programme de départ :

Grain très finVectorisation

SIMD

Machines parallèles si grands vecteurs

Grain moyen : transcription directe en espace d’adressage unique

Dépendances Soient s et t deux opérations d'un programme P.

Collision : s et t sont en collision si s et t accèdent au même emplacement mémoire et l’une au moins écrit.

Dépendance : il existe une dépendance de s vers t si s et t sont en collision

ET

s avant t dans l’exécution de P

Notation : s -> t

L’ensemble des dépendances définit le graphe de dépendances développé du programme

Typologie : Dépendance de flot (RAW) ; s écrit, t lit

Anti-dépendance (WAR) ; s lit, t écrit

Dépendance de sortie (WAW) ; s et t écrivent

Repères d’instructions et prédicat de séquencement Repère d’instruction :

décrit une opération dans un nid de boucles

(nom_inst, i1, i2, …, in) où i1, i2, …, in sont les indices des boucles qui englobent l’instruction

Prédicat de séquencement : s, t deux instructions englobées dans n boucles

L’ ordre d’exécution des opérations est

(s, i1, i2, …, in) << (t, i’1, i’2, …, i’n) ssi (i1, i2, …, in) < (i’1, i’2, …, i’n) dans l’ordre lexicographique

OU (i1, i2, …, in)=(i’1, i’2, …, i’n) et s avant t dans l’ordre syntaxique de P

Niveau des dépendances et GDR La dépendance (s, i1, i2, …, in) -> (t, i’1, i’2, …, i’n)

est de niveau k si k est le premier indice tel que ik < i’k (inter-itération ; loop carried dependency)

est de niveau inf si (i1, i2, …, in) = (i’1, i’2, …, i’n) (intra-itération ; loop-independent dependency)

Graphe de dépendance réduit (GDR)Multi-graphe

Noeuds = instructions (statiques)

Arcs = dépendances étiquetées par leur niveau

Exemplefor (i=1;i<=N;i++) for (j=1;j<=N;j++) a(i+j) = a(i+j-1)+1;

Avec flèches pleines=flot sinon=anti/sortie

Suitefor (i=2;i<=N;i++) { S1: s(i) = 0; for (j=1;j<i-1;j++) S2: s(i) = s(i)+a(j,i)*b(j); S3: b(i) = b(i)-s(i);}

Avec a=anti o=sortie f=flot

Equivalence Deux programmes sont équivalents s’ils produisent le même résultat

Transformation Ré-ordonnancement, ré-indexation, parallélisation,…

Les instances dynamiques ne changent pas : pas d’instructions ajoutées ou supprimées

La structure de contrôle et les indices peuvent changer

« Proposition » Une transformation d’un programme P qui préserve le graphe de dépendances développé fournit un programme équivalent à P

Distribution de boucles

Autres transformations Échange de boucles

But : Modifier la granularité du parallélisme

Moyen : Modifier le parcours de l’espace d’itération pour faire apparaître du parallélisme

Torsion de boucles (Loop skewing) But : faire apparaître du parallélisme.

Moyen : Modifier le parcours de l’espace d’itération pour faire apparaître du parallélisme

Agrégation de boucles But : diminuer le surcoût de synchronisation

Transformations du code séquentiel But : faire apparaître du parallélisme

Etc.

Exemples Fusion de boucles

forall(i=1;i<=N;i++)

D[i]=E[i]+F[i];

forall(j=1;j<=N;j++)

E[j]=D[j]*F[j];

Composition de boucles

forall(j=1;j<=N;j++)

forall(k=1;k<=N;k++)

Échange de boucles

for(i=1;i<=N;i++)

for(j=2;j<=M;j++)

A[i,j]=A[i,j-1]+1;

DONNE :

forall(i=1;i<=N;i++)

D[i]=E[i]+F[i];

E[i]=D[i]*F[i];

forall(i=1;i<=N*N;i++)

for(j=2;j<=M;j++)

A[1:N,j]=A[1:N,j-1]+1;

Exemples Déroulement de boucle

for (i=1;i<=100;i++)

A[i]=B[i+2]*C[i-1];

Rotation de boucle [skewing]

for (i=1;i<=N;i++)

for (j=1;j<=N;j++)

a[i,j]=(a[i-1,j]+a[i,j-1])/2;

DONNE :

for (i=1;i<=99;i=i+2)

A[i]=B[i+2]*C[i-1];

A[i+1]=B[i+3]*C[i];

for(k=2;k<=N;k++)

forall(l=2-k;l<=k-2;l+=2)

a[(k-l)/2][(k+l)/2] = a[(k-l)/2-1][(k+l)/2]+a[(k-l)/2][(k+l)/2-1];

for(k=1;k<=N;k++)

forall(l=k-N;l<=N-k;l+=2)

a[(k-l)/2][(k+l)/2] = a[(k-l)/2-1][(k+l)/2]+a[(k-l)/2][(k+l)/2-1];

Exemple : décomposition LUSoit donc à résoudre le système triangulaire supérieur : Ux=b pour i=n-1, n-2,…, 1x[n]=b[n]/U[n,n] ;for(i=n-1;i>=1;i--) x[i]=0; for(j=i+1;j<=n;j++) L:x[i]=x[i]+U[i,j]*x[j]; x[i]=(b[i]-x[i])/U[i,i];

Graphe de dépendances

Il est à noter qu'il y a aussi des anti-dépendances des itérations (i,j) vers (i-1,j)

En faisant une rotation et une distribution de boucles

H':forall(i=1;i<=n-1;i++) x[i]=b[i];T': x[n]=b[n]/U[n,n];H: for(t=1;t<=n-1;t++) forall(i=1;i<=n-t;i++) L:x[i]=x[i]-x[n-t+1]*U[i],n-t+1]; T:x[n-t]=x[n-t]/U[n-t,n-t];

« Contre-exemple »

Préfixe parallèle

Algo d'Allen et KennedyLe principe est de remplacer certaines boucles for par des boucles forall (avec distribution de boucles pour limiter les dépendances)

Commencer avec k=1

Supprimer dans le GDRN G toutes les arêtes de niveau inférieur à k

Calculer les Composantes Fortement Connexes (CFC) de G

Pour tout CFC C dans l'ordre topologique : Si C est réduit à une seule instruction S sans arête, alors générer des boucles parallèles dans toutes les dimensions restantes (i.e. niveaux k à nS) et générer le code pour S

Sinon, l=l_min(C), et générer des boucles parallèles du niveau k au niveau l-1, et une boucle séquentielle pour le niveau l. Puis reboucler l'algorithme avec C et k=l+1

Illustrationfor(i=1;i<=N;i++) for(j=1;j<=N;i++) { S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2); S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1); S3: a(i,j+2) = b(i+1,j+1)-1; }

Ce GDRN est fortement connexe et a des dépendances de niveau 1. La boucle sur i sera donc séquentielle. On enlève maintenant les dépendances de niveau 1

Illustration

for(i=1;i<=N;i++) { for(j=1;j<=N;j++) S1: a(i+1,j+1) = a(i+1,j)+b(i,j+2); forall(j=1;j<=N;j++) S3: a(i,j+2) = b(i+1,j+1)-1; forall(j=1;j<=N;j++) S2: b(i+1,j) = a(i+1,j-1)+b(i,j-1);}