Bulk Synchronous Parallel Bulk Synchronous Parallel ML: implémentation ML: implémentation

modulaire et prévision de modulaire et prévision de performancesperformances

Stage de David BillietStage de David BillietEncadrement:Encadrement:

Frédéric Loulergue & Frédéric GavaFrédéric Loulergue & Frédéric Gava

Université Paris 12 Val de MarneUniversité Paris 12 Val de Marne

Laboratoire d’Algorithmique, Laboratoire d’Algorithmique, Complexité et LogiqueComplexité et Logique

ContexteContexte

Cadre général : Programmation fonctionnelle

parallèle Déterministe, sans blocage Prévision de performances (BSP)

Le projet Caraml (2002-2004, ACI Le projet Caraml (2002-2004, ACI Grid)Grid)

PréliminairesPréliminaires

Bulk Synchronous Bulk Synchronous ParallelismParallelism Machine BSP : Machine BSP : p p paires processeur-memoire paires processeur-memoire

+ réseau+ unité de synchronisation globale+ réseau+ unité de synchronisation globale Execution BSP : séquence de super-étapes:Execution BSP : séquence de super-étapes:

T(s) = (maxT(s) = (max00i<i<pp w wii) + h) + hgg + + ll

La bibliothèque BSMLlibLa bibliothèque BSMLlib

Pour Objective CamlPour Objective Caml Un programme parallèle = Un programme parallèle =

Programme séquentiel habituel + Programme séquentiel habituel + operations sur une structure parallèleoperations sur une structure parallèle

Vecteurs parallèles de taille Vecteurs parallèles de taille pp: : par par Accès aux paramètres BSP : Accès aux paramètres BSP :

bsp_pbsp_p,, bsp_g bsp_g,, bsp_l bsp_l

Les primitives BSMLlib Les primitives BSMLlib (1)(1)

mkparmkpar: (int->: (int->) -> ) -> par par

mkpar f = <(f 0), … , (f (p-1))>mkpar f = <(f 0), … , (f (p-1))>

apply: apply: (() par -> ) par -> par -> par -> par par

apply <fapply <f00,…f,…fp-1p-1> <v> <v00,…,v,…,vp-1p-1>=>=

<(f <(f00 v v00),…,(f),…,(fp-1p-1 v vp-1p-1)>)>

projection: projection: atat

Les primitives BSMLlib Les primitives BSMLlib (2)(2)

type type option = None | Some of option = None | Some of

putput: (int: (int option) par option) par(int(int option) paroption) par

put put = =

NoneNone Some Some vv22

NoneNone NoneNone

NoneNone NoneNone Some Some vv55

NoneNone

NoneNone Some Some vv33

NoneNone NoneNone

Some Some vv11

Some Some vv44

NoneNone NoneNone

00 11 22 33NoneNone NoneNone NoneNone Some Some

vv11

Some Some vv22

NoneNone Some Some vv33

Some Some vv44

NoneNone Some Some vv55

NoneNone NoneNone

NoneNone NoneNone NoneNone NoneNone

00 11 22 33

Travail effectuéTravail effectué

Objectifs du travailObjectifs du travail

ExistantExistant: implémentation basée sur MPI: implémentation basée sur MPI

Implémentation modulaire pour faciliter Implémentation modulaire pour faciliter la mise en œuvre et les évolutionsla mise en œuvre et les évolutions

Utiliser d’autres bibliothèques de Utiliser d’autres bibliothèques de communication: MPI, PVM, TCPIP, PUBcommunication: MPI, PVM, TCPIP, PUB

Outil pour la prévision de performances: Outil pour la prévision de performances: programme de benchmark des programme de benchmark des paramètres BSPparamètres BSP

Nouvelle organisation Nouvelle organisation du noyau de la BSMLlib du noyau de la BSMLlib

Noyau (contenant seulement les Noyau (contenant seulement les primitives) générique (module primitives) générique (module foncteur) prenant en argument un foncteur) prenant en argument un module de communicationmodule de communication

Module de communication:Module de communication: pidpid nprocsnprocs sendsend

Modules CommModules Comm

MPI: MPI: Utilisant MPI_AlltoallvUtilisant MPI_Alltoallv Send/receive avec carré latinSend/receive avec carré latin

PVM: PVM: avec carré latinavec carré latin traitement particulier de la sortie traitement particulier de la sortie

standardstandard TCPIP: TCPIP:

carré latin carré latin pur Ocaml avec threadspur Ocaml avec threads

Le programme Le programme bmslprobebmslprobe

Détermine les paramètres BSPDétermine les paramètres BSP Principe:Principe:

pp le nombre de processeurs est connu le nombre de processeurs est connu détermine la vitesse détermine la vitesse rr des processeurs des processeurs

(opérations sur les flottants)(opérations sur les flottants) communications avec messages de communications avec messages de

taille croissante (h-relation croissante): taille croissante (h-relation croissante): méthode des moindres carrés pour méthode des moindres carrés pour obtenir obtenir gg et et LL

Une expérience (1)Une expérience (1) Le programme: produit scalaireLe programme: produit scalairelet inprod_array v1 v2 = let s = ref 0. in

for i = 0 to (Array.length v1)-1 do

s:=!s+.(v1.(i)*.v2.(i));

done; !s

let inprod_list v1 v2 =List.fold_left2 (fun s x y -> s+.x*.y) 0. v1 v2

let inprod seqinprod v1 v2 =

let localinprod = Bsmlbase.parfun2 seqinprod v1 v2 in

Bsmlcomm.fold_direct (+.) localinprod

Une expérience (2)Une expérience (2)

ConclusionsConclusions

Travail incorporé Travail incorporé dans la future BSMLlib 0.3dans la future BSMLlib 0.3 dans la première version dedans la première version de

Departmental Metacomputing ML (DMML)Departmental Metacomputing ML (DMML)

Travail présenté (par F. Gava) au Travail présenté (par F. Gava) au workshop Implementation of workshop Implementation of Functional Languages (IFL’04) 8-10 Functional Languages (IFL’04) 8-10 septembre 2004septembre 2004