1、Algorithmes parallles auto-adaptatifs et applications,Daouda TRAORDirecteurs de thse Jean-Louis ROCH & Denis TRYSTRAM Projet MOAIS Laboratoire dInformatique de Grenoble (UMR 5217), FranceVendredi 19 Dcembre 2008,Motivations,Evolution des machines parallles: de machines avec processeurs identiques ve
2、rs: Grilles de calcul = ressources htrognes et dynamiquesSystmes multi-processus (Processeurs multi-curs, SMP, MPsoc) applications concurrentes sur une mme unit = les curs apparaissent comme de vitesses variablesProcesseurs graphiques : GPUs + CPUs= htrognit, frquences et oprations diffrentesQuestio
3、ns: Est-ce quun algorithme parallle peut fonctionner dans ce contexte? Avec quelles garanties de performance ? Sous quelles hypothses?,2/52,Evolution de la programmation parallle,Grille,Multi-coeurs, SMP,GPU,Google MapReduce,OpenMP, Cilk+, intel TBB,Cuda,Athapascan/Kaapi,Initialement: processeurs id
4、entiques (MPI)Aujourdhui: Interfaces de haut-niveau permettant dabstraire larchitecture.,3/52,Construction dalgorithmes parallles adaptatifsSadaptent la plate-forme dexcution Inconscients du nombre de processeurs (en anglais, processor oblivious) Adaptation la charge de la plate-forme Avec des garan
5、ties defficacit Temps dexcution si possible optimal p/r aux ressources (dynamiquement) allouesContexte: LIG / EP INRIA Moais:Thme sur la conception dalgorithmes adaptatifs Roch&al gzip2001, TSI2005,.Master ROCO D. Traor 2005 : un algorithme de prfixe adaptatif (mais clairvoyant),4/52,Objectif de la
6、thse,Introduction objectifs et contributions, organisationProgrammation parallle notionsAlgorithmes parallles adaptatifsdfinitionsUn algorithme adaptatif pour le calcul parallle des prfixes EUROPAR06, CARI06Algorithmes adaptatifs de tri parallle RENPAR08Schma gnrique des algorithmes parallles adapta
7、tifs PDP08, EUROPAR08Application du schma la librairie standard STL EUROPAR08, MSAS08Conclusion et perspectives,5/52,Plan du mmoire et contributions,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes Ordonnancement par vol de travailSchma gnrique adaptatifAlgori
8、thme adaptatif pour le calcul parallle des PrfixesApplication du schma la STLConclusion et perspectives,6/52,Plan de la prsentation,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes,Calcul des prfixes Entre : x0, x1, , xn Sortie : p0, p1, ., pn avec Application
9、s : paralllisation de boucles, additions modulaires Blelloch89Algorithme squentiel :for(p0=x0, i=1; i = n; i+) pi=pi-1*xi; / n oprationsBorne infrieure sur p processeurs identiques : Paralllisation optimale sur p processeurs identiques Snir86, Nicolau-Wang96,7/52,Fich83,Algorithmes pour processeurs
10、identiques: illustration sur le calcul parallle des prfixes,Un nouvel algorithme optimal pour le calcul des prfixes chap. 3, pages 27-36- Soit s et q le quotient et le reste de la division de n+1 par p+1:n+1 = s(p+1) + qDivision du tableau initial en p+1 blocs de taille ventuellement diffrentes,8/52
11、,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes,s+1,s+1,s+2,s+2,Algorithme statique en p+1 blocs,9/52,10/52,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes,Analyse thorique du temps dexcution de lalgorithme propos et
12、le nombre doprations vrifie :Remarque: Une variante donne un temps toujours optimal, mais na pas t programme,Si 0 q 1 et (p+3)/2 q p, alors le temps dexcution de lalgorithme (optimal) sur p processeurs identiques vrifie,Thorme chap. 3, page 30,Si 2 q (p+3)/2, alors le temps dexcution de lalgorithme
13、1 de loptimal sur p processeurs identiques vrifie,Thorme chap. 3, pages 31 et 32,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes,11/52,taille,temps,acclration,taille,Machine AMD Opteron,n petit, temps dune opration assez lev,n grand, temps dune opration trs p
14、etit (temps daddition de deux Doubles par exemple). Dans lalgorithme de Nicolau-Wang On a 2n/(p+1) synchronisations,4 processeurs,1 processeur,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes,Inconvnients de la paralllisation sur des processeurs identiquesNomb
15、re doprations : toujours le mme si les p processeurs initialement prvus pour lexcution ne sont pas disponibles. Exemple : si on suppose que Un seul processeur excute lalgorithme parallle Les autres tant mobiliss pour dautres calculs= le nombre doprations effectues par un seul processeur est Lalgorit
16、hme optimal sur processeurs identiques nest pas performant Si les processeurs sont de vitesses diffrentes (temps dexcution final = temps dexcution du processeur le plus lent) Si le temps de lopration * est variable,12/52,Algorithmes pour processeurs identiques: illustration sur le calcul parallle de
17、s prfixes Ordonnancement par vol de travailSchma gnrique adaptatifAlgorithme adaptatif pour le calcul parallle des PrfixesApplication du schma la STLConclusion et perspectives,13/52,Plan de la prsentation,Principe Suit le principe glouton : tout instant o il existe une tche prte non encore ordonnanc
18、e, tous les processeurs sont actifs. Algorithme distribu Chaque processeur gre localement une pile des tches quil a rendues prtes (cres, ou dbloques).,tches,P0,P1,P2,Lorsquun processeur devient inactif, il choisit (au hasard) un processeur dont la pile en cours dexcution contient une tche prte et lu
19、i vole une tche (la plus ancienne, en haut de la pile (FIFO).,steal,14/52,Ordonnancement par vol de travail,Blelloch90, , Leiserson & Kuszmaul 2001,Modle de cot associ au vol de travail (1/2),Notations W = travail = le nombre doprations de lalgorithme parallle sur 1 processeur Tp = la dure dexcution
20、 de lalgorithme parallle sur p processeurs D = la profondeur de lalgorithme parallle (le nombre doprations sur le chemin critique)Pave = la vitesse moyenne des p processeurs :ThormeArora, Blumofe, Plaxton 02, Bender, Rabin 02Avec une grande probabilit; Le temps dexcution Tp dun programme utilisant l
21、ordonnancement par vol de travail est major par : Le nombre de vols (russis ou chous) est infrieure O(p.D),15/52,Modle de cot associ au vol de travail (2/2),Efficacit de la paralllisation Wseq = travail de l algorithme squentiel Tseq = temps dexcution de lalgorithme squentiel : Intrt : Si W Wseq et
22、D trs petit, En gnral W c1Wseq, c1 mesure le surcot d lordonnancement et au paralllisme. Surcot de paralllisme Gestion des tches : tches empiles dans une pile Exemple : algorithme rcursif,Grain fin : surcot arithmtique (rcursivit)Minimisation du surcot dordonnancement Principe du travail dabordFrigo
23、 et al98, Roch01Ce principe consiste minimiser le surcot de cration de tches de lordonnancement par vol de travail. Appels de cration de tches traduits en appel local de fonction squentielle.,16/52,Cilk Frigo et al 98 Cration de tches : spawn Synchronisation : sync Architectures cibles : mmoires par
24、tagesAthapascan/Kaapi Athapascan Roch et al, PACT 98 : interface applicative Bas sur le graphe de flot de donnes Cration de tches : Fork Cration de donnes : Shared Architectures cibles : mmoires partages et distribues Kaapi Gautier et al 07 : moteur excutif, qui supporte Athapascan,17/52,Bibliothque
25、s implmentant le vol de travail,Emulation squentielle de lalgorithme parallle Nombre doprations arithmtiques suprieur celui de lalgorithme squentielExemple : Calcul des prfixes, optimal avec n oprations !- Entre : x0, x1, , xn- Sortie : p0, p1, ., pn avec Un algorithme parallle rcursif (Diviser Pour
26、 Rgner) :,18/52,Ordonnancement par vol de travail : limite,W(n) = 2W(n/2) + n/2 = (1/2) n*log(n) = lmulation squentielle de lalgorithme parallle fait plus doprations que lalgorithme squentiel optimal !,Algorithmes pour processeurs identiques: illustration sur le calcul parallle des prfixes Ordonnanc
27、ement par vol de travailSchma gnrique adaptatifAlgorithme adaptatif pour le calcul parallle des PrfixesApplication du schma la STLConclusion et perspectives,19/52,Plan de la prsentation,Ordonnancement par vol de travail: amlioration Principe de base Roch&al TSI 2005 Remplacer lmulation squentielle d
28、e lalgorithme parallle par un vrai algorithme squentiel plus efficace.=Utiliser le couplage de deux algorithmes : Un squentiel: qui minimise le travail (nombre doprations) W Un parallle: qui minimise la profondeur parallle DPoints clefs: tout instant, chaque processus actif excute un algorithme sque
29、ntiel, mais peut tre vol par un processus inactif Un processus suit lalgorithme squentiel (optimal),20/52,Schma gnrique adaptatif,Un processeur occup a une tche et lexcute avec un algorithme squentiel,T0.Run_seq(),21/52,Couplage adaptatif de deux algorithmes,Ps,Un processeur devient libre et excute
30、une opration dextraction de travail chez un processeur actif sans linterrompre.,Ps,Pv,21/52,Couplage adaptatif de deux algorithmes,steal,T0.Run_seq(),Un processeur devient libre et excute une opration dextraction de travail chez un processeur actif (victime) sans linterrompre.,Ps,21/52,Couplage adap
31、tatif de deux algorithmes,Pv,T0.Run_seq(),T0.Run_seq(),La victime a fini sa tche et prempte son voleur,Ps,21/52,Couplage adaptatif de deux algorithmes,Pv,T0.Run_seq(),Prempts,La victime effectue un saut (jump) sur le travail dj fait par le voleur, le voleur finalise ventuellement ses calculs grce au
32、x rsultats de la victime.,Ps,21/52,Couplage adaptatif de deux algorithmes,Pv,jump,T0.Finalize,T0.Run_seq(),gets,Ps,A la fois les processeurs victime et voleur peuvent modifier les informations sur le travail en cours de traitement Ncessit de se synchroniser ( pour la cohrence des donnes),22/52,Coupl
33、age adaptatif : Amortissement des synchronisations (extraction squentielle du travail),work extract_seq() lock(); /verrouillerws = NextWorkSeq();unlock(); /dverrouillerreturn ws; ,Ct victime,work extract_par() /Micro-looplock(); /verrouillerwv = WorkToSteal();unlock(); /dverrouillerreturn wv; ,Ct vo
34、leur,- Si taille(ws) est petite = surcot lv. - Choix de taille (ws) :taille (ws) = profondeur (wrest);= travail arithmtique Wseq,23/52,Couplage adaptatif : Amortissement des synchronisations (extraction squentielle du travail),Exemple : transform STL : boucle avec n calculs indpendants,alog(n1),ni=l
35、-fi,alog(n2),f1,l,f2,taille,Tempss,Machine utilise : AMD Opteron Opteron 875 2,2 Ghz, Compilateur gcc, option O2,Schma adaptatif : Amortissement du surcot arithmtique,Pour Certains dalgorithmes: Wseq nest pas connu davance W WseqExemple: algorithme find_if qui permet de trouver le premier lment dune
36、 squence vrifiant un predicat,Le temps final de lalgorithme parallle est le temps final du processeur ayant termin le dernier. Donc T4 = 6,Le temps squentiel de lalgorithme est Tseq = 2,24/52,Pour sadapter : division dynamique du travail global en des tapes (Macro-loop Danjean, Gillard, Guelton, Roc
37、h, Roche, PASCO07), avec synchronisation aprs chaque pas schma de type algorithme de Floyd,25/52,Schma adaptatif : Amortissement du surcot arithmtique,Exemple : find_if,B1,B2,B3,P0, P1, P2,P0, P1, P2,P0, P1, P2,Exemple : find_if STL Comparaison avec find_if parallle MPTL Baertschiger 06,26/52,Schma
38、adaptatif : Amortissement du surcot arithmtique,Machine utilise : AMD Opteron (16 curs); Donnes : doubles; Taille tableau : 106; Position lment : 105; Temps STL : 3,60 s; Temps prdicat 36,Acclration infrieure 1,Exemple : find_if STL Acclration par rapport au temps STL en fonction de la position o se
39、 trouve llment,Nombre de processeurs,acclration,27/52,Schma adaptatif : Amortissement du surcot arithmtique,Machine utilise : AMD Opteron (16 curs); Donnes : doubles; Taille tableau : 106; Temps prdicat 36,Si le temps parallle dexcution dun algorithme sur un nombre infini de processeurs fait (1+s)Ws
40、eq oprations avec s 0, alors avec une grande probabilit,Thorme chap. 6, pages 89 et 90,28/52,Schma adaptatif : Analyse thorique,Trois niveaux de boucles utiliss dans lalgorithme du du schma nano-loop = limite le surcot de synchronisation micro-loop = permet le vol de travail et la premption macro-lo
41、op = limite le surcot arithmtiqueAnalyse de la complexit de lalgorithme du schma,Suit le schma de lalgorithme adaptatif Classes instancier : WorkAdapt, JumpWork, FinalizeWork Les fonctions instancier :,29/52,Spcification et implantation du Schma Interface C+ sur Kaapi,Pour construire un algorithme a
42、daptatif, lutilisateur remplit les fonctions ncessairesClass MyWorkAdapt : public WorkAdapt bool extract_seq() .bool extract_par() .void local_run() void join(const WorkAdapt stolenwork) .Lancement du moteur adaptatif sur le travail construit void MyalgoAdapt ( ) MyWorkAdapt my_work = new MyWorkAdap
43、t(.);adapt:run(my_work);,30/52,Spcification et implantation du Schma Interface C+ sur Kaapi,Implmentation sans pile du couplage squentiel-parallle Mais le paralllisme rcursif sans surcot peut rester gr par Kaapi avec sa pile Gestion des vols: Remplacer la pile distribue de tches cres par une liste d
44、istribue de tches voles Intrt : peu de vols = peu de tches insres dans la liste; les surcots de cration sont aussi limits. Gestion lors de la premption :,31/52,Spcification et implantation du schma Gestion des vols,v1,v2,v3,w,(a) avant premption de v1,Algorithmes pour processeurs identiques: illustr
45、ation sur le calcul parallle des prfixes Ordonnancement par vol de travailSchma gnrique adaptatifAlgorithme adaptatif pour le calcul parallle des PrfixesApplication du schma la STLConclusion et perspectives,32/52,Plan de la prsentation,Algorithme adaptatif du calcul parallle des prfixes (1/7),Calcul
46、 des prfixes Entre : x0, x1, , xn Sortie : p0, p1, ., pn avec Algorithme squentiel :for(p0=x0, i=1; i = n; i+) pi=pi-1*xi; / n oprationsBorne infrieure sur p processeurs identiques : Paralllisation optimale sur p processeurs identiques Snir86, Nicolau-Wang96Ne sont pas adapts si le temps de lopratio
47、n * varie ou si les processeurs sont vitesse variableParalllisation sur un nombre non born de processeurs Ladner-Fischer80, Lin-Su02 Peuvent tre muls par vol de travail mais effectuent plus de 2n oprationsBut : trouver un algorithme adaptatif qui se comporte optimalement EUROPAR2006, CARI2006,33/52,Fich83,p1,p2,p3,a5,a1 a2 a3,
