1 Couplage à hautes performances de codes parall è les et distribu é s Hamid-Reza HAMIDI Thèse préparée dans le projet APACHE puis le projet MOAIS au sein

1

Couplage à hautes performances de codes parallèles et distribués

Hamid-Reza HAMIDI

Thèse préparée dans le projet APACHE puis le projet MOAIS

au sein du laboratoire ID-IMAG

et financée par l’Iran et la France (SFERE)

5 Oct 2005

Montbonnot - France

2

Contexte : calcul scientifique

But : Etude de phénomènes complexes impliquant plusieurs modèles déjà étudiés

Nécessite l’exécution de plusieurs codes différents langages de programmation (C+, F90, HPF, OpenMP, …) différents paradigmes de communication (RPC/RMI, MPI, ...) besoin très important de puissance (calcul, stockage, visualisation)

Visualisation

Dynamique Moléculaire

Méthode du Continuum

simulation moléculaire complexe

[ARC SIMBIO 97-99][ARC COUPLAGE 00-01]

3

Problématique : Couplage de codes Construction d’applications distribuées

certains codes sont parallélisés

Des objectifs complémentaires Calcul parallèle

- Exploitation de l’architecture- Performances

Systèmes distribués - Réutilisation de codes existants- Hétérogénéité du logiciel et du matériel

??

4

Composantséquentiel

process

Composantparallèle

process

processusprocessusprocessus

processusprocess

Composantparallèle

Composantséquentiel

processusprocessus

processusprocessus

process

intergiciel

grappe

Réseau haut débit

Réseau haut débit

grappe

Réseau

Réseau

SupercomputerVisualisation

Architecture logicielle Architecture matérielle

Approche orientée composant

Un modèle « structuré » de programmation concept structurant : objets ou composants

- composants sont interconnectés par un intergiciel- [CORBA, PACO++, Pardis, FlowVR]

besoin d’un modèle/langage de « coordination »

- assemblage des composants

5

Coordination de composants

Séparation de la partie calculatoire et de la partie contrôle

Définition des composants : le calcul- interface, cycle de vie, déploiement, ...

Description des interactions entre composants : le contrôle - flux de données, dépendance écrivain-lecteur, expression, ...

Problèmes Deux langages

- un langage (parallèle) pour la description du code des composants- un langage pour la description de la coordination entre composants

Ordonnancement sur une architecture distribuée- quel modèle d’exécution ?

6

Thèse : coordination pour le couplage de codes

Quel langage de coordination permettant à la fois : exécution parallèle

- passage à l’échelle

adaptation aux ressources

- ordonnancement

Il existe des langages parallèles pour ces deux points Linda, Stampede, FlowVR, Athapascan

Contribution « Athapascan » comme langage de coordination

- deux extensions

HOMA : compilateur CORBA + support exécutif

- application au couplage de codes dans une grille RPC (CORBA)

7

Plan

Athapascan : « flot de données macroscopique »

Modèle de programmation et d’exécution

Limitations pour la coordination

Extension d’Athapascan comme un langage de coordination

Collection temporelle

Collection spatiale

HOMA : compilateur de CORBA pour une coordination efficace

Dédié « grille de calcul RPC »

Implémentation sur Athapascan

Evaluations expérimentales

Mesures élémentaires

Mesures sur une application réelle : SIMBIO

Conclusion et perspectives

8

Athapascan/Kaapi Une API de haut niveau [Athapascan98]

Permet de construire une représentation de l’exécution par interprétation de certaines instructions

- Expression explicite du parallélisme et contrôle implicite des interactions– une tâche dans le programme = une succession d’instructions

● création d’une tâche : mot clé « Fork »– une donnée dans la mémoire = une succession de valeurs (versions)

● création d’une donnée et l’accès initial : déclaration « Shared » Représentation de l’exécution = graphe de flot de données

- Objet important pour le calcul d’un ordonnancement– Connaissance des précédences et des communications

Modèle algorithmique de coût prédictif

Un support exécutif KAAPI [Kaapi04]

Ordonnancement en ligne Bonnes performances Grille hétérogène

9

« Fork » : création de tâche

« Shared » : création de donnée

« Shared_w » : accès en écriture

« Shared_r » : accès en lecture

Programme indépendant de l’architecture

programme ATHAPASCAN…

Shared<int> a, b, c;Fork<t1>( a ); // “a” Shared_wFork<t2>( b ); // “b” Shared_wFork<t3>( c ); // “c” Shared_wFork<t4>( a, b ); // “a, b” Shared_r

...

Athapascan : exemple et exécution (1/2)

…struct t1 { void operator( Shared_w<int> p ) { … }};

…struct t4 { void operator( Shared_r<int> p1, Shared_r<int> p2) { … }};

10

ressource de calcul

Interprétation abstraite

à l’exécution

Ordonnancement

t2

b

t4

t1

a

Représentationde l’exécution

t3

c

tâche

version

accès

programme ATHAPASCAN…

Shared<int> a, b, c;Fork<t1>( a ); // “a” Shared_wFork<t2>( b ); // “b” Shared_wFork<t3>( c ); // “c” Shared_wFork<t4>( a, b ); // “a, b” Shared_r

...

Athapascan : exemple et exécution (2/2)

Calcul en ligne des dépendances anticipation du futur de l’exécution meilleur contrôle sur :

- mouvement des données- ordonnancement des tâches

libération automatique de la mémoire

11

Quelles sont les versions retournées lors des accès en lecture ?

Sémantique Athapascan : séquentielle un accès en lecture retourne la dernière version produite

Adapté au calcul scientifique

Lisibilité + Performance [Doreille 99, Maillard 02, Revire 04]

accès en lecture

accès en écriture

versiondonnée partagée

Par rapport à un ordre lexicographique

Sémantique séquentielle

mémoire partagée

tâchetâche tâchetâche

X

tâche

......

Ordre

12

Un modèle algorithmique de coût Le temps d’exécution parallèle sur P machines

Tp = O(T1 / p + T + h( C1 / p + C )) + O( )

- les temps de calcul sans communication (modèle PRAM)– T1 : la somme de temps d’exécution de toutes les tâches– T : le temps d’exécution d’un chemin critique

- les temps de communication sur architecture homogène – C1 : (latence séquentielle) la somme de tailles de toutes les données– C : (latence parallèle) la somme de tailles de données sur un chemin

critique

- h : le coût d’envoi d’une unité de données : le coût de l’algorithme d’ordonnancement

Exécution parallèle Communication parallèle

Athapascan : garantie de performances

13

accès en lecture

accès en écriture

versiondonnée partagée X

mémoire partagée

X ......

machine Amachine Bmachine C

mémoire partagée

X ......

Distribution spatiale des données et limitation 1

Athapascan : différentes versions d’une donnée sont distribuées sur plusieurs machines

ex. X est un vecteur

Limitation 1 : pas de support direct pour les « données parallèles »

Comment exprimer la distribution d’une version de donnée sur plusieurs machines ?

14

accès en lecture

accès en écriture

versiondonnée

mémoire partagée

X ......

Ordre

Ordre

tâche

tâche tâche

tâche tâche

tâche tâche

. . .

flux de données

Sémantique séquentielle et limitation 2

Limitation-2 : besoin de synchronisations « flux de données »

un accès en lecture retourne la valeur produite par une écriture selon :

- un type d’entrelacement donné

- des conditions à l’exécution

Exemple : « flux FIFO »

15

Plan






Collection spatiale








16

Se baser sur une nouvelle définition des objets partagés

Intérêt

Conserve le modèle de programmation et le support d’exécution

accès en lecture « Shared_r »

accès en écriture « Shared_w »

versiondonnée dans la mémoire

mémoire partagée

X ......mémoire partagée

X ......

« Shared »

« Shared »

Définition Athapascan : objet partagé X = succession de versions

Définition proposée:

objet partagé X = ensemble d’accès

TempsTemps

Comment lever ces limitations ?

17

Collection spatiale et collection temporelle Collection spatiale « SpaceCollection »

But: « données parallèle » distribution d’une version sur plusieurs machines

Définition : ensemble d’accès + fonction d’indexation- accès à la i-ème partie d’une version distribuée

Collection temporelle « TimeCollection »

But: description de synchronisations de type « flux de données »

Definition : ensemble d’accès + un ordre explicite - un ordre explicite donné par :

– un type d’entrelacement donné (FIFO, Last-Received, ...)– des conditions à l ’exécution (ex. tampon borné)

18

Exemples d’utilisation

Collection spatiale « SpaceCollection »- SpaceCollection<T> x; // x ~ vecteur de T

- Accès à un élément : x[i] = référence vers un objet partagé T– la donnée T n’est pas directement accessible– Fork<Utilisation d’un élément>( x[i] )

Collection temporelle « TimeCollection »- TimeCollection_w<T> tc_w; // flux de sortie d’éléments T- TimeCollection_r<T> tc_r; // flux d’entrée d’éléments T

- Accès à un élément : x[i] = référence vers un objet partagé T– la donnée T n’est pas directement accessible– Fork<Ecriture d’un élément>( tc_w.get_next() )– Fork<Lecture d’un élément>( tc_r.get_next() )

19

Conclusion

Résultat Un langage de coordination avec une implantation efficace

- Extensions à Athapascan pour exprimer des synchronisations complexes

- Implémentation efficace sur le support exécutif d’Athapascan

Comment utiliser ce langage pour des applications effectives ?

HOMA : un compilateur pour des applications décrites en CORBA

20

Plan






Collection spatiale








21

HOMAExemple : SIMBIO (INRIA 97-99)

Code de simulation numérique de système moléculaire complexe impliquant plusieurs modèles physiques

Les codes sont des objets CORBA

Un code « Pilote » contrôle la simulation

Deux modèles d’interaction

- Invocation de méthode à distance (RMI)

- Flux de données [non traité]

Pilote

VisualisationBordeaux

Dynamique Moléculaire


Nancy

GrenobleBordeaux

CORBA

. . .

flux de données

. . .

flu

x d

e d

onn

ées

RMIs

22

L’algorithme de couplage = une séquence de RMIs

Extraction automatique de parallélisme sur les RMIs Gestion automatique des communications parallèles

HOMA

int a, b, c;server-1.m1 ( a ); // a en outserver-2.m2 ( b ); // a en outserver-1.m3 ( c ); // c en inoutserver-3.m4 ( a, b ); // a, b en in

code du piloteserver-1

server-2

server-3

RMI

données en entréedonnées en sortie

RMI

RMI

Problématique

23

Passage du code d’un pilote à un ordonnancement global distribué de l’application

Deux étapes

1. Compilation IDL vers Athapascan- 1 invocation = 1 tâche- 1 paramètre = 1 donnée partagée

2. Ordonnancement et exécution- Dynamique, par le runtime Athapascan

Points critiques

Recouvrement des latences des RMIs Optimisation des transferts de données

HOMA

int a, b, c;server-1.m1 ( a ); // a en outserver-2.m2 ( a ); // a en outserver-1.m3 ( c ); // c en inoutserver-3.m4 ( a, b ); // a, b en in

code du pilote

ressource de calcul

Calcul en ligne des dépendance

Ordonnancement

t2

b

t4

t1

a

DAG associé

t3

c

Approche d’HOMA

24

HOMA

Client Serveur

attente

Invocation bloquante

Serveur

réception

réponse

Client

Invocationnon-bloquante

résultats

continuationcréation de tâche

Invocation-par-Continuation« HOMA »

Invocation synchrone« CORBA »

réception

résultats

réponse

Point critique I : recouvrement des RMIs Invocation de RMI => attente du retour de l’appel

Solution : HOMA transforme 1 invocation en 2 tâches - 1- une tâche prête qui invoque une méthode non-bloquante- 2- la tâche « continuation » qui met à jour les données

Recouvrement possible grâce à l’ordonnancement non préemptif des tâches Athapascan

25

HOMA

Serveur-CServeur-P

Client

Protocole standard« CORBA »

données

donnéesAcq.

Serveur-CServeur-P

Client

Communication-par-nécessité« HOMA »

Acq.

données

requête

référence

référenceréférence

requête

1 2 3 4 1 2 3 6

45

Point critique II : communication parallèle Éviter le transfert inutile de données via client

Solution : communication lorsque nécessaire (lecture ou écriture effective)

« Cache distribué » pour éviter les communications- 1- cache de données en sortie permettant la communication parallèle- 2- cache de données en entrée évitant la duplication des communication

26

HOMA

POA

Objet

Bus logiciel (ORB)

Serveur

Squelette

Objet

Client

compilateurIDL

interface server1{void m3( T in a, T’ in b );

}

Stub

Description d’interface

Fonctionnement de CORBA

Le compilateur IDL génère le « stub client » et le « squelette serveur »

« stub client » et « squelette serveur » prend en charge l’invocation à distance

27

HOMA

POA

Objet

Bus logiciel (ORB)

Serveur

Squelette

Objet

Client

compilateurIDL

Stub

compilateurHOMA

interface étendu

Stubétendu

Squeletteétendu

interface server1{void m3( T in a, T’ in b );

}

Description d’interface

Fonctionnement de HOMA Le compilateur d’HOMA génère un « stub étendu » + « squelette

étendu »

L’exécution d’un stub étendu permet : l’interception les invocations de méthodes pour créer des tâches Athapascan

Athapascan contrôle l’ordonnancement local des tâches

28

HOMA génère un « bon » programme Athapascan

1- les tâches sont non bloquantes : « invocation-par-continuation »

2- communication directe : « communication-par-necéssité »

Autorise l’ordonnancement local non préemptif parallèle et efficace

Intérêt : HOMA hérite du modèle de coût Athapascan

Le temps d’exécution d’un code sur P machines

THOMA= Tp = O( T1 / p + T + h( C1 / p + C ) ) + O( )

Mieux que CORBA qui séquentialise les appels RMI distants

TCORBA = O( T1 + h C1 ) + O( )

Pour un programme très parallèle (T << T1) impliquant un grand volume de données (C << C1) exécuté sur P machines

THOMA = TCORBA / P

Exécution séquentielle Communication via client

HOMARésultats théoriques

29

Plan






Collection spatiale




Evaluations expérimentales Mesures élémentaires



30

HOMAMesures expérimentales

Mesures élémentaires sur HOMA les surcoûts d’invocation de méthode [non présenté]

communication parallèle dues aux invocations parallèles

Une application réelle : SIMBIO exécution parallèle

Plate-forme expérimentale : une grappe de PC OmniORB3 CORBA

iCluster-I de l’INRIA

- PC 733 Mhz,- 256 MB, réseau fast-ethernet 100Mb/s

31

Mesurer la communication parallèle

Analyse du coût sur N machines- K = la taille de données- N = le nombre de pairs de serveurs- T1= O( N ) , T = O( 1 )- C1= O( N*K ) , C = O( 1 )

HOMA : THOMA = TN = O( K )

CORBA : TCORBA = O( N*K )

HOMA

for i=1 to N doSP[i]->ms ( x[i] ); // x en sortieSC[i]->mc ( x[i] ); // x en entrée

code du pilote en CORBA

SP[1].ms

x[1]

Exécution du programme Athapascan

SC[1].mc

SP[N].ms

x[N]

SC[N].mc

HOMA

Mesures élémentaires II

32

Résultats expérimentaux II HOMA

0

5

10

15

20

25

30

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64Number of servers

Tim

e (s

ec)

CORBA 9,6MB

CORBA 3,2MB

Homa 9,6MB

Homa 3,2MB

Nombre de serveurs

33

Bande passante cumulée HOMA

Le bande passante pair-à-pair moyenne

HOMA = 9.5 Mbytes/s, MPI (TCP) = 11 Mbytes/s, PACO de 9.1 à 11.3MBytes/s

0

50

100

150

200

250

300

350

0 4 8 12 16 20 24 28 32Nombre de paires de serveurs

Mb

yte

/sec

Bloc 6,4MB Bloc 3,2MB Bloc 0,8MB

34

HOMARetour à l’application SIMBIO

Un code « Pilote » contrôle la simulation

PiloteDynamique Moléculaire


serverMC

serverDM

CORBA

RMIs

35

HOMA

1. for(int k=0; k <MaxTimeStep; k++){

2. md->computeFF(Pin, Fmdout);

3. if (cmstep( k )){

4. md->computeRhs(Pin, bout);

5. cm->computeA(Sin,Pin,Vinout);

6. cm->computePol(bin,Fcmout);

7. }

8. md->mix(Fcmin,Fgout,Fmdinout);

9. md->integrate(Vinout,Fmdin,Pinout);

10. if (cmstep( k ))

11. cm->integrate(Sinout,Fgin); 12. }

Dépendances complexes !

Pilote de SIMBIO

Pilote de SIMBIO en CORBA

36

Résultats expérimentaux - II HOMA

L’application SIMBIO

0

50

100

150

200

250

300

350

400

450

0 1 2 3 4 5 6 7 8 9 10Number of atoms (*100k)

Tim

e (s

ec)

CORBA p=3

HOMA p=3

HOMA p=12

Le temps d’exécution sur p machines

Taille de données

gaine 2.98

gaine 10.57

37

Conclusion Un même code pour décrire coordination + exécution

Vers un modèle unifié Athapascan/Kaapi + FlowVR

Athapascan : un langage de coordination- Description en ligne des dépendances- Découpage de la déclaration d’un accès de l’accès effectif aux données

Les extensions- Collection temporelle : donner une consistance temporelle- Collection spatiale : décrire des données parallèles

– Données irrégulières : la distribution de données n’est pas connue à la compilation mais contrôlée à l’exécution

Utilisation dans une « grille RPC » pour les applications CORBA

Appliquer le modèle d’exécution d’Athapascan - Exécution non-préemptive par « invocation-par-continuation »- Communication parallèle par « communication-par-nécessité »

En se basant sur le développement d’un compilateur IDL vers Athapascan/Kaapi

- Transparence à l’utilisation

38

Perspectives

Expérimentales Expérimentations sur grille hétérogène Intégration de bibliothèque de redistribution de données

distribuées

Ouverture de la technologie développée Ouverture vers d’autre interface d’intergiciel

- DCOM (Cape-Open/IFP)- JavaRMI ?

Intégration avec PACO++ / GridCCM

39

Merci

40

Collection temporelle : intérêt pratique

Comparaison sur l’utilisation d’un flux de données (FIFO)

Expérience de type « calcul et communication »

- Un processus calcule et communique ses résultats

- Un processus lit et calcule

Programme en Athapscan

Programme sans collection temporelle- L’ordre des communications suit l’ordre de création des tâches

Programme avec collection temporelle- L’ordre des communications dépend uniquement de la disponibilité

des valeurs

Avantage Meilleure recouvrement calcul/communication

41

Résultats expérimentaux I HOMA

0%

20%

40%

60%

80%

100%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Taille des séquences (*10K)

% d

u t

em

ps t

otal d

'in

vocatio

n

Invocation CORBA de méthode

Coût de conversion (cache générique)

Surcoût de << communication-par-necéssité >>

42

Implantation sur intergiciel de communication

mémoire partagéeX ......

processusprocessus

processusprocessus

process

processusprocessus

processusprocessus

process

consommateur

. . .

TimeCollection_w TimeCollection_r

flux de données

Intergiciel

receive

producteur

mémoire partagéeX ......

sendestampille

43

0

0,02

0,04

0,06

0,08

0,1

0,12

0,14

0 2 4 6 8 10 12 14 16 18

Temps de calcul (10msec)

Tem

ps d

e 1

00

ité

rati

on

s (

sec)

sans CT 100k

CT 100K

sans CT 10

CT 10

gain entre 10% à 20%

Résultats expérimentaux

Comparaison par rapport à l’accès direct à un flux de données (FIFO)

iCluster-II de l’INRIA Itanium bi-processeurs 900MHz, 3GB

44

Retour à l’application SIMBIO

Les serveurs sont des objets CORBA

Modèle communication est RMI

Pilote

Dynamique MoléculaireMPI + Threads

Méthode du ContinuumOpenMP

ORB

serverDM

serverMC

client

HOMA

45

Exemples d’utilisation

Collection spatiale « SpaceCollection »- SpaceCollection<T> x; // x ~ vecteur de T- Accès à un élément : x[i] = référence vers un objet partagé T

– la donnée T n’est pas directement accessible– Fork<Utilisation d’un élément>( x[i] )

Collection temporelle « TimeCollection »- TimeCollection_w<T> tc_w; // flux de sortie d’éléments T- TimeCollection_r<T> tc_r; // flux d’entrée d’éléments T- Accès à un élément : x[i] = référence vers un objet partagé T

– la donnée T n’est pas directement accessible– Fork<Ecriture d’un élément>( tc_w.get_next() )– Fork<Lecture d’un élément>( tc_r.get_next() )

46

Ancien type d’objet partagé d’Athapascan « Shared » = { accès }

sémantique séquentielle : une lecture est liée à la dernière écriture

Extension - I : Collection spatiale « SpaceCollection » = { accès }

en plus de sémantique associé, les accès possèdent une fonction d’indexation

ex. SpaceCollection < Shared >

*sémantique précise +

interface de programmation

dans le mémoire de thèse

Illustration et extensions

mémoire partagée

X

accès en lecture

accès en écriture

versiondonnée partagée X

machine Amachine Bmachine C

« SpaceCollection»

......

1 2 3

47

Extension - II: collection temporelle Collection temporelle « TimeCollection » = { accès }

sémantique de type flux de données

un ordre implicite donné par :- un type d’entrelacement donné (FIFO, Last-Received, ...)- les conditions à l ’exécution (ex. tampon borné)

« TimeCollection_r » = { accès en lecture } « TimeCollection_w » = { accès en écriture }

*sémantique précise +

interface de programmation

dans le mémoire de thèse

accès en lecture

accès en écriture

versiondonnée partagée mémoire partagée

X ......

« TimeCollection_r »« TimeCollection_w »

TempsTemps

entrelacement

48

Problématique - II

Extraction du parallélisme sur les invocations Dépendances sur paramètres effectifs Dépendances sur états partagés dans une server

…

server_1 -> m1( a );

server_2 -> m2( b );

server_1 -> m4( f );

server_3 -> m3( a, b );

...

ex. de code client

temps

m1m2

m3

server-1server-2server-3

client attent attent attentm4

attent

temps

m1m2

m3

server-1server-2server-3

client attent attentm4

ex. CORBA

Notreapproauch

Solutions existants:• « Request Sequencing » de NetSolve/Ninf• « ? « de DIET

explicite et à la charge de utilisateur

3-

49

Collection spatiale dans SIMBIO

Tous les objets serveurs et données sont distribués sur plusieurs machines

ATHAPASCAN

DM->computeFF( A, F )

A

SpaceCollection

ATHAPASCAN

for i=1 to N do DM[i]-> computeFF(A[i],F[I])

A

SpaceCollection

MAP : (f,C) -> {f(c[i])}

HOMA

50

Modèle I: problématique - III

Exploitation des “données parallèles”

redistribution de données entre les codes

Client parallèle

Server parallèl

...Pserver->foo( A )...

le code clientA

foo( A )

foo( A )

foo( A )

foo( A )

A

A

A

A

Pserver

Prédiction de l'exécution redistribution des données ordonnancement de tâches

Notre approauch :exploiter les solutions existants dans la communication directe

4-

Solutions existants:• objet parallèle de PARDIS, PaCO, PaCO++ (SPMD et implicite)• « Data Parallel CORBA » de OMG (MPMD et explicite)

le client reste toujours le glot d’etronglement de communication

5-

Notre approauch : construction on-line de graphe de flot de données

HOMA

51

Interprétation abstraite et l’architecture HOMA détecte le parallélisme et les dépendances à l’exécution

Le compilateur d’HOMA génère le « stub HOMA » de l’interface donné

« stub HOMA » intercepte les invocations de méthodes pour créer les tâches

La gestion des dépendances par Athapascan

HOMA

POA

Objet

modèleSPMD

Bus logiciel (ORB)

ServeurClient / Pilot

Stub Stub

Code Code

stubHoma

stub Homa

gestion de flot de données( Athapascan )

Skeleton

POA

Skeletonétendu

Objet

proxyHOMA

StubPOA

Skeletonétendu

Objet

Skeleton

Serveur

recompilé non-changé

Documents

1 Couplage à hautes performances de codes parall è les et distribu é s Hamid-Reza HAMIDI Thèse préparée dans le projet APACHE puis le projet MOAIS au sein