Upload
shaeleigh-aguirre
View
23
Download
1
Embed Size (px)
DESCRIPTION
Bulk Synchronous Parallel ML: implémentation modulaire et prévision de performances Stage de David Billiet. Encadrement: Frédéric Loulergue & Frédéric Gava Université Paris 12 Val de Marne Laboratoire d’Algorithmique, Complexité et Logique. Contexte. Cadre général : - PowerPoint PPT Presentation
Citation preview
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