PMP Report

  • View
    663

  • Download
    0

Embed Size (px)

DESCRIPTION

I did a report in "paralllisation & modles de programmation" during my MSc in HPC, here is the source.

Transcript

  • 1. Paralllisation & mod`les eede programmation Caner CandanM2 MIHP 6 mars 2011Table des mati`rese1 Produit matriciel21.1 Enonc . . . . . . . . . .e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.1 La diusion . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Le produit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.3 Limplmentatione. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Dcoupage dun tableau binairee 32.1 Enonc . . . . . . . . . . . . . .e. . . . . . . . . . . . . . . . . . . . . . . . . . . .32.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.2.1 Dterminer lindex . . . e . . . . . . . . . . . . . . . . . . . . . . . . . . . .42.2.2 Crer le tableau binairee. . . . . . . . . . . . . . . . . . . . . . . . . . . .42.2.3 Implmentation . . . . .e. . . . . . . . . . . . . . . . . . . . . . . . . . . .43 Design53.1 Diagramme de classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53.2 Surcharge doprateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .e 54 Mesure de performance 64.1 Prambule . . . . . . . . . . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . . .64.2 Identier les ressources les plus utilisese. . . . . . . . . . . . . . . . . . . . . . .64.3 Pseudo-code de la fonction apply . . . . . . . . . . . . . . . . . . . . . . . . . . .64.4 La fonction en parall`le . . . . . . . . .e. . . . . . . . . . . . . . . . . . . . . . .64.5 Speed-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74.6 Mesures . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .74.6.1 Fonctions objectifs . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .84.6.2 Benchmark . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .84.6.3 Dynamicit . . . . . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . . .94.6.4 Rsultats en O(1) . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . . .94.6.5 Rsultats en O(n) . . . . . . . . e . . . . . . . . . . . . . . . . . . . . . . . 105 Conclusion 10 1

2. 1 PRODUIT MATRICIEL21 Produit matriciel1.1 Enonc e Matrice : Dcrire un algorithme PRAM pour le mod`le EREW qui utilise O(n3 ) processeurs e epour multiplier deux matrices de taille n n. 11.2 Solution Une solution consisterait ` diuser dans un premier temps toutes les donnes des matrices `aeamultiplier ` chaque processus puis de faire le produit des matrices en prenant le soin que chaque aprocessus utilise les donnes qui leur est propre.e1.2.1 La diusion En respectant le mod`le EREW, les matrices A et B Knn sont copies, dans un premiereetemps, n fois dans les cubes A et B Knnn . Ceci permet de rserver une dimension du cube ea` un processus et viter toute lecture concurrente.eLalgorithme 1 prsente le pseudo-code de la fonction de diusion qui prend comme donne eeen entre une matrice M Knn et retourne un cube M Knnn . Elle est exprime enee2 tapes. La premi`re consiste ` aecter, en utilisant O(n2 ) processeurs, chaque point de laee amatrice dans la premi`re dimension du cube. La deuxi`me tape eectue la copie en diusion 2ee ede chaque point de la matrice situ ` la premi`re dimension du cube vers les autres dimensions ea edu cube en utilisant O(log n) processeurs et pour une matrice enti`re en O(n2 log n). eDonnes : M Knn , n NeRsultat : M Knnn e1 dbut e2parall`le e3pour i 0 ` n faire a4parall`le e5pour j 0 ` n fairea6m (0, i, j) m(i, j)7parall`le e8pour s 0 ` log2 n faire a9 parall`le e10pour h 0 ` s2 faire a11 parall`le e12 pour i 0 ` n faire a13 parall`le e14 pour j 0 ` n fairea15 m (2s + h, i, j) m (h, i, j)16nAlgorithme 1 : Copie de matrice en diusion n1. cij = k=0 aik bkj : http://fr.wikipedia.org/wiki/Produit_matriciel2. Hot potato routing : http://en.wikipedia.org/wiki/Hot_potato_routing 3. 2 DECOUPAGE DUN TABLEAU BINAIRE 31.2.2 Le produit En appliquant le mod`le EREW, le produit matriciel prend en param`tre les cubes A eteeB Knnn tel que chaque processus utilise sa dimension de cube respective pour lire lesdonnes de aij et bij .e Lalgorithme 2 prsente le pseudo-code de la fonction de produit matriciel qui prend comme edonne en entre les cubes A et B Knnn et retourne une matrice C Knn . Laectation e edes valeurs dans la matrice C se fait en O(n2 ) et le produit de cij se fait en O(n).Donnes : A, B Knnn , n NeRsultat : C Knn e1 dbut e2parall`le e3pour i 0 ` n fairea4parall`le e5pour j 0 ` n fairea6c(i, j) n a(p, i, k) b(p, k, j)k=07 nAlgorithme 2 : Produit matriciel1.2.3 Limplmentatione Apr`s avoir dcrit la fonction de diusion et le produit matriciel respectant tous deux le e emod`le EREW, nous allons voir limplementation dun produit de deux matrices A et B Knneproduisant une troisi`me matrice C Knn . eLalgorithme 3 dcrit limplmentation.e eDonnes : A, B Knn , n N eRsultat : C Knn e1 dbut e2A dif f usion(A, n)3B dif f usion(B, n)4C produit(A , B )5 nAlgorithme 3 : Implmentation du produit matriciele2 Dcoupage dun tableau binaire e2.1 Enonc eDcoupage dun tableau : Soit A un tableau de longueur n dont les lments sont soit deseee0 soit des 1. Concevez un algorithme EREW de complexit O(log n) utilisant O(n) processeurs epour ranger tous les lments 1 ` la droite du tableau tout en maintenant leur ordre relatifee a(proprit de stabilit des lments).eee eeHint : eectuer un calcul de prxe pour dterminer quel devrait tre la position de chaquee eelment.ee 4. 2 DECOUPAGE DUN TABLEAU BINAIRE42.2 SolutionNotre tableau tant binaire, contenant que des 0 et 1, il devient facile de compter le nombreede 1 en sommant toutes les valeurs du tableau pour ensuite dterminer ` quel index placer lese a0 et 1.Toute fois pour respecter lnonc et avoir une complexit en O(log n), nous allons devoire e eutiliser la fonction calculant la somme des prxes.e2.2.1 Dterminer lindex eLalgorithme 4 permet de dterminer lindex qui constituera la fronti`re entre les 0 et 1 dans e ele tableau. Pour cela il prend en param`tre le tableau binaire B Kn ainsi que la taille duetableau n N .Donnes : B Kn , n NeRsultat : i N e1 dbut e2i n calcul somme pref ixe(B)3 nAlgorithme 4 : Trouver lindex2.2.2 Crer le tableau binairee Lalgorithme 5 prend en param`tre lindex et la taille et cre un tableau binaire tri en e eefonction de lindex, 0 ` gauche et 1 ` droite. a aDonnes : i, n NeRsultat : B Kn e1 dbut e2parall`le e3pour j 0 ` i fairea4B (i) 05parall`le e6pour j i ` n fairea7 B (i) 18 n Algorithme 5 : Cration du tableau binaire triee2.2.3 Implmentatione Lalgorithme 6 illustre la solution.Donnes : B KneRsultat : B Kn e1 dbut e2i trouver index(B)3B creer tableau binaire(i)4 n Algorithme 6 : Dcoupage dun tableau binaire e 5. 3 DESIGN53 DesignTous les exercices ont t dvelopps en C++ en utilisant le paradigme de programmationee eeobjet et le design qui suit a t labor pour regrouper les dirents composants de calculs.ee ee eNanmoins une recherche a t eectu pour dterminer les limites de OpenMP et C++. Ileeeeesemblerait que les conteneurs fournit par la STL 3 ne soient pas threadsafe 4 . Une tude 5 donneeune liste non-exhaustive des prcautions ` prendre lors de lutilisation de OpenMP en C++.e aCependant la version OpenMP 3.0 apporte des concepts nouveaux permettant lutilisation no-tamment des iterateurs. On peut ainsi, par exemple, saranchir de simple indexeur de tableauet tendre la paralllisation sur des listes cha ees. ee n3.1Diagramme de classes Figure 1 Diagramme de classesDeux grandes familles dopration coexistent. Elles sont prsentes en gure 1. Les oprations e e eede calcul ` param`tre unique OMPComputeUnary et celles ` deux param`tres OMPCompu-a e aeteBinary. Tous deux renvoient un rsultat. Elles sont prxes de OMP pour OpenMP 6 . Le e e ecalcul de somme des prxes prenant un seul param`tre en entre OMPVector et renvoyante eeun Atom, cette classe se situe dans la famille OMPComputeUnary. Le produit matriciel sesitue, quant ` lui, dans la famille OMPComputeBinary, cette classe prend deux param`tres a eOMPMatrix et retourne le mme type. On peut imaginer dautres oprations comme, pare eexemple, un produit vectoriel.3.2Surcharge doprateur eCompte tenu des possibilits oertes par le langage C++, comme la surcharge des oprateurs, eeloprateur se voit ainsi surcharg dans la classe OMPMatrix an dappeler implicitemente ela classe OMPMatrixProduct pour le calcul du produit matriciel. Ainsi en crivant le codeeC = A B ceci revient ` crire C = OM P M atrixP roduct()(A, B). ae 3. Standard Template Library : http://www.sgi.com/tech/stl/ 4. On dit quun programme ou quune portion de code est thread-safe sil fonctionne correctement durant uneexcution simultane par plusieurs threads (processus lgers). http://fr.wikipedia.org/wiki/Threadsafee ee 5. C++ and OpenMP : http://www.compunity.org/events/pastevents/parco07/parco_cpp_openmp.pdf 6. Open Multi-Processing : http ://openmp.org/ 6. 4 MESURE DE PERFORMANCE 64 Mesure de performanceJe prote de ce rapport pour parler dun travail qui ma t demand en entreprise. Nous uti- ee elisons le framework EO7 pour dvelopper nos algorithmes volutionnaires 8 . Le sujet consistait e ea` implmenter, au framework EO, un paralllisme ` mmoire partage en utilisant OpenMP. e e a ee4.1Prambule eAvant de commencer il est important de prciser que les EA 9 travaillent sur une populationedindividu aussi appel chantillon. Un individu tant reprsent par un point dans lchantillon,eeeee ela complexit dun probl`me est dnit par le nombre de dimensions pour chaque individu.ee eLe probl`me est reprsent par la fonction objectif qui prend en param`tre un individu (unee e epoint dans lchantillon) et value toutes ses dimensions pour en dduire la qualit 10 . La qualitee e e eest le crit`re de comparaison dun point dans son chantillon. ee4.2Identier les ressourc