Download pdf - PMP Report

Transcript
Page 1: PMP Report

Parallelisation & modeles

de programmation

Caner CandanM2 MIHP

6 mars 2011

Table des matieres

1 Produit matriciel 21.1 Enonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2.1 La diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2.2 Le produit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.3 L’implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Decoupage d’un tableau binaire 32.1 Enonce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2.1 Determiner l’index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.2 Creer le tableau binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Design 53.1 Diagramme de classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Surcharge d’operateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Mesure de performance 64.1 Preambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.2 Identifier les ressources les plus utilisees . . . . . . . . . . . . . . . . . . . . . . . 64.3 Pseudo-code de la fonction apply . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.4 La fonction en parallele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.5 Speed-up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.6 Mesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.6.1 Fonctions objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.6.2 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.6.3 Dynamicite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.6.4 Resultats en O(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.6.5 Resultats en O(n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 Conclusion 10

1

Page 2: PMP Report

1 PRODUIT MATRICIEL 2

1 Produit matriciel

1.1 Enonce

Matrice : Decrire un algorithme PRAM pour le modele EREW qui utilise O(n3) processeurspour multiplier deux matrices de taille n ∗ n. 1

1.2 Solution

Une solution consisterait a diffuser dans un premier temps toutes les donnees des matrices amultiplier a chaque processus puis de faire le produit des matrices en prenant le soin que chaqueprocessus utilise les donnees qui leur est propre.

1.2.1 La diffusion

En respectant le modele EREW, les matrices A et B ∈ Kn∗n sont copiees, dans un premiertemps, n fois dans les cubes A′ et B′ ∈ Kn∗n∗n. Ceci permet de reserver une dimension du cubea un processus et eviter toute lecture concurrente.

L’algorithme 1 presente le pseudo-code de la fonction de diffusion qui prend comme donneeen entree une matrice M ∈ Kn∗n et retourne un cube M ′ ∈ Kn∗n∗n . Elle est exprimee en2 etapes. La premiere consiste a affecter, en utilisant O(n2) processeurs, chaque point de lamatrice dans la premiere dimension du cube. La deuxieme etape effectue la copie en diffusion 2

de chaque point de la matrice situe a la premiere dimension du cube vers les autres dimensionsdu cube en utilisant O(log n) processeurs et pour une matrice entiere en O(n2 ∗ log n).

Donnees : M ∈ Kn∗n, n ∈ NResultat : M ′ ∈ Kn∗n∗ndebut1

parallele2

pour i← 0 a n faire3

parallele4

pour j ← 0 a n faire5

m′(0, i, j)← m(i, j)6

parallele7

pour s← 0 a log2 n faire8

parallele9

pour h← 0 a s2 faire10

parallele11

pour i← 0 a n faire12

parallele13

pour j ← 0 a n faire14

m′(2s + h, i, j)← m′(h, i, j)15

fin16

Algorithme 1 : Copie de matrice en diffusion

1. cij =∑n

k=0aikbkj : http://fr.wikipedia.org/wiki/Produit_matriciel

2. Hot potato routing : http://en.wikipedia.org/wiki/Hot_potato_routing

Page 3: PMP Report

2 DECOUPAGE D’UN TABLEAU BINAIRE 3

1.2.2 Le produit

En appliquant le modele EREW, le produit matriciel prend en parametre les cubes A etB ∈ Kn∗n∗n tel que chaque processus utilise sa dimension de cube respective pour lire lesdonnees de aij et bij .

L’algorithme 2 presente le pseudo-code de la fonction de produit matriciel qui prend commedonnee en entree les cubes A et B ∈ Kn∗n∗n et retourne une matrice C ∈ Kn∗n. L’affectationdes valeurs dans la matrice C se fait en O(n2) et le produit de cij se fait en O(n).

Donnees : A,B ∈ Kn∗n∗n, n ∈ NResultat : C ∈ Kn∗ndebut1

parallele2

pour i← 0 a n faire3

parallele4

pour j ← 0 a n faire5

c(i, j)←∑n

k=0 a(p, i, k) ∗ b(p, k, j)6

fin7

Algorithme 2 : Produit matriciel

1.2.3 L’implementation

Apres avoir decrit la fonction de diffusion et le produit matriciel respectant tous deux lemodele EREW, nous allons voir l’implementation d’un produit de deux matrices A et B ∈ Kn∗nproduisant une troisieme matrice C ∈ Kn∗n.

L’algorithme 3 decrit l’implementation.

Donnees : A,B ∈ Kn∗n, n ∈ NResultat : C ∈ Kn∗ndebut1

A′ ← diffusion(A,n)2

B′ ← diffusion(B,n)3

C ← produit(A′, B′)4

fin5

Algorithme 3 : Implementation du produit matriciel

2 Decoupage d’un tableau binaire

2.1 Enonce

Decoupage d’un tableau : Soit A un tableau de longueur n dont les elements sont soit des0 soit des 1. Concevez un algorithme EREW de complexite O(log n) utilisant O(n) processeurspour ranger tous les elements 1 a la droite du tableau tout en maintenant leur ordre relatif(propriete de stabilite des elements).

Hint : effectuer un calcul de prefixe pour determiner quel devrait etre la position de chaqueelement.

Page 4: PMP Report

2 DECOUPAGE D’UN TABLEAU BINAIRE 4

2.2 Solution

Notre tableau etant binaire, contenant que des 0 et 1, il devient facile de compter le nombrede 1 en sommant toutes les valeurs du tableau pour ensuite determiner a quel index placer les0 et 1.

Toute fois pour respecter l’enonce et avoir une complexite en O(log n), nous allons devoirutiliser la fonction calculant la somme des prefixes.

2.2.1 Determiner l’index

L’algorithme 4 permet de determiner l’index qui constituera la frontiere entre les 0 et 1 dansle tableau. Pour cela il prend en parametre le tableau binaire B ∈ Kn ainsi que la taille dutableau n ∈ N .

Donnees : B ∈ Kn, n ∈ NResultat : i ∈ Ndebut1

i← n− calcul somme prefixe(B)2

fin3

Algorithme 4 : Trouver l’index

2.2.2 Creer le tableau binaire

L’algorithme 5 prend en parametre l’index et la taille et cree un tableau binaire trie enfonction de l’index, 0 a gauche et 1 a droite.

Donnees : i, n ∈ NResultat : B′ ∈ Kn

debut1

parallele2

pour j ← 0 a i faire3

B′(i)← 04

parallele5

pour j ← i a n faire6

B′(i)← 17

fin8

Algorithme 5 : Creation du tableau binaire trie

2.2.3 Implementation

L’algorithme 6 illustre la solution.

Donnees : B ∈ Kn

Resultat : B′ ∈ Kn

debut1

i← trouver index(B)2

B′ ← creer tableau binaire(i)3

fin4

Algorithme 6 : Decoupage d’un tableau binaire

Page 5: PMP Report

3 DESIGN 5

3 Design

Tous les exercices ont ete developpes en C++ en utilisant le paradigme de programmationobjet et le design qui suit a ete elabore pour regrouper les differents composants de calculs.Neanmoins une recherche a ete effectue pour determiner les limites de OpenMP et C++. Ilsemblerait que les conteneurs fournit par la STL 3 ne soient pas threadsafe 4. Une etude 5 donneune liste non-exhaustive des precautions a prendre lors de l’utilisation de OpenMP en C++.Cependant la version OpenMP 3.0 apporte des concepts nouveaux permettant l’utilisation no-tamment des iterateurs. On peut ainsi, par exemple, s’affranchir de simple indexeur de tableauet etendre la parallelisation sur des listes chaınees.

3.1 Diagramme de classes

Figure 1 – Diagramme de classes

Deux grandes familles d’operation coexistent. Elles sont presentees en figure 1. Les operationsde calcul a parametre unique “OMPComputeUnary” et celles a deux parametres “OMPCompu-teBinary”. Tous deux renvoient un resultat. Elles sont prefixees de “OMP” pour OpenMP 6. Lecalcul de somme des prefixes prenant un seul parametre en entree “OMPVector” et renvoyantun “Atom”, cette classe se situe dans la famille “OMPComputeUnary”. Le produit matriciel sesitue, quant a lui, dans la famille “OMPComputeBinary”, cette classe prend deux parametres“OMPMatrix” et retourne le meme type. On peut imaginer d’autres operations comme, parexemple, un produit vectoriel.

3.2 Surcharge d’operateur

Compte tenu des possibilites offertes par le langage C++, comme la surcharge des operateurs,l’operateur ∗ se voit ainsi surcharge dans la classe “OMPMatrix” afin d’appeler implicitementla classe “OMPMatrixProduct” pour le calcul du produit matriciel. Ainsi en ecrivant le codeC = A ∗B ceci revient a ecrire C = OMPMatrixProduct()(A,B).

3. Standard Template Library : http://www.sgi.com/tech/stl/4. On dit qu’un programme ou qu’une portion de code est thread-safe s’il fonctionne correctement durant une

execution simultanee par plusieurs threads (processus legers). http://fr.wikipedia.org/wiki/Threadsafe5. C++ and OpenMP : http://www.compunity.org/events/pastevents/parco07/parco_cpp_openmp.pdf6. Open Multi-Processing : http ://openmp.org/

Page 6: PMP Report

4 MESURE DE PERFORMANCE 6

4 Mesure de performance

Je profite de ce rapport pour parler d’un travail qui m’a ete demande en entreprise. Nous uti-lisons le framework EO 7 pour developper nos algorithmes evolutionnaires 8. Le sujet consistaita implementer, au framework EO, un parallelisme a memoire partagee en utilisant OpenMP.

4.1 Preambule

Avant de commencer il est important de preciser que les EA 9 travaillent sur une populationd’individu aussi appele echantillon. Un individu etant represente par un point dans l’echantillon,la complexite d’un probleme est definit par le nombre de dimensions pour chaque individu.

Le probleme est represente par la fonction objectif qui prend en parametre un individu (unpoint dans l’echantillon) et evalue toutes ses dimensions pour en deduire la qualite 10. La qualiteest le critere de comparaison d’un point dans son echantillon.

4.2 Identifier les ressources les plus utilisees

Un test de profiling a ete execute afin d’identifier les ressources les plus utilisees dans leframework EO. Le test nous a permit d’identifier une fonction qui est utilisee par une grandemajorite des operateurs 11 EO. Il s’agit de la fonction “apply”. Elle prend en parametres unepopulation d’individu et un operateur. Cette fonction va iterer sur tous les individus de lapopulation et appliquer l’operateur. Il peut etre interessant d’optimiser cette fonction. Nousallons nous limiter a transformer le code sequentiel en parallele.

4.3 Pseudo-code de la fonction apply

L’algorithme 7 prend en parametre une population ainsi qu’un operateur a appliquer achaque individu.

Donnees : P ∈ Kn, F ∈ OperateurResultat : B′ ∈ Kn

debut1

pour i← 0 a n faire2

F (P (i))3

fin4

Algorithme 7 : La fonction apply

4.4 La fonction en parallele

L’algorithme 8 transforme la fonction “apply” en parallele en utilisant le modele PRAMCREW 12 et O(n) processeurs pour parcourir tous les individus de la population.

7. Evolving Object, http://eodev.sf.net8. Algorithme evolutionnaire : http://fr.wikipedia.org/wiki/Algorithme_evolutionnaire9. Algorithmes evolutionnaires

10. Fitness en anglais11. Operateurs de selection et variation12. Concurantial Read Exclusive Write

Page 7: PMP Report

4 MESURE DE PERFORMANCE 7

Donnees : P ∈ Kn, F ∈ OperateurResultat : B′ ∈ Kn

debut1

parallele2

pour i← 0 a n faire3

F (P (i))4

fin5

Algorithme 8 : La fonction omp apply

4.5 Speed-up

Apres avoir cree la fonction alternative employant le parallelisme a memoire partagee, appele“omp apply”, nous allons etudier une solution de mesure du speed-up 13.

L’equation, en figure 2, presente une methode de mesure du speed-up et est implementeedans l’algorithme 9.

Mesure du Speedup = rP,D∑

k=0,l=0

Spkl

Figure 2 – Mesure du Speedup

Une description des parametres est disponible dans la figure 3.

Parametres Description

p la taille minimum de la population

popStep le pas d’iteration de la population

P la taille maximum de la population

d la taille minimum de la dimension

dimStep le pas d’iteration de la dimension

D la taille maximum de la dimension

r le nombre d’execution pour chaque com-binaison de p et d

Figure 3 – Description des parametres utilises

4.6 Mesures

En prenant en compte les parametres decrits precedemment, nous allons lancer les tests surdeux architectures materielles differentes presente en figure 4.

Pour visualiser l’evolution du speed-up, nous utilisons un outil de generation de graphiques 15,avec les donnees produits par les tests.

13. Sp =T∗1

Tp: http://en.wikipedia.org/wiki/Speedup

15. Utilisation de matplotlib en python pour generer des boites a moustache

Page 8: PMP Report

4 MESURE DE PERFORMANCE 8

Donnees : p, P, popStep, d,D, dimStep, r ∈ Ndebut1

pour k ← p a P faire2

pour l← d a D faire3

pour m← 0 a r faire4

Ts ← 05

Tp ← 06

debut7

t1 ← omp get wtime()8

... code sequentiel avec k et l execute m fois ...9

apply( ... )10

t2 ← omp get wtime()11

Ts ← t2 − t112

fin13

debut14

t1 ← omp get wtime()15

... code parallele avec k et l execute m fois ...16

omp apply( ... )17

t2 ← omp get wtime()18

Tp ← t2 − t119

fin20

... on conserve le speed-up TsTp

pour k et l ...21

fin22

Algorithme 9 : La fonction de mesure du speedup

Processeur Nombre de coeurs Frequence Cache L1

Intel Centrino vPro 2 2.40GHz 3072KB

Intel Core i7 8 (hyperthreading 14) 2.67GHz 8192KB

Figure 4 – Architectures materielles

4.6.1 Fonctions objectifs

Il est important de simuler toutes les complexites de problemes que l’on peut etre amenea resoudre. Pour nos tests, le choix a ete oriente vers deux fonctions objectifs de complexitedifferente presente en figure 5.

Fonction objectifs Complexite en temps Algorithme

La fonction Sphere O(1) Sphere =∑n

k=0 individukProbleme a temps variable quelconque O(n) usleep(U(0, 1) ∗ 10)

Figure 5 – Fonctions objectifs

4.6.2 Benchmark

Pour faciliter et automatiser les tests, une liste de mesures a ete elabore avec les parametresdecrits precedemment et un script contenant l’ensemble des tests a executer a ete cree. La listedes mesures est presentee en figure 6.

Page 9: PMP Report

4 MESURE DE PERFORMANCE 9

Mesure Description

1 mesure pour toutes les combinaisons de P et D

2 mesure pour P ∈ [1, 101[ avec D = 1000

3 mesure pour P ∈ [1, 1001[ avec popStep = 10 et D = 1000

4 mesure pour D ∈ [1, 101[ avec P = 1000

5 mesure pour D ∈ [1, 1001[ avec dimStep = 10 et P = 1000

Figure 6 – Liste des mesures

4.6.3 Dynamicite

Parmi les optimisations possibles en OpenMP, il existe deux types de planification, la pla-nification statique, utilise par defaut, divise le nombre de taches a traiter a tous les processusdisponibles et la planification dynamique maintient une file de taches traitee au fur et a mesurepar les processus disponibles. Nous evaluons la dynamicite par le rapport entre une mesure despeedup en mode statique et une mesure de speedup en mode dynamique 16.

4.6.4 Resultats en O(1)

Le benchmark a ete execute dans un premier temps pour la fonction Sphere qui se resoud entemps constant. Les resultats de chaque mesure sont numerotes d’apres le tableau des mesuresdecrit precedemment.

Les mesures sont presentees en fonction des processeurs utilises et disponibles en figure 7,8, 9, 10 et 11.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121100 iterations from 1,1 to 101,101

0.0

0.5

1.0

1.5

2.0

spee

dup

- 1

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121100 iterations from 1,1 to 101,101

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

1

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121100 iterations from 1,1 to 101,101

0.0

0.5

1.0

1.5

2.0

2.5

spee

dup

- 1

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121100 iterations from 1,1 to 101,101

0

1

2

3

4

5

6

7

dyna

mic

ity -

1

(d) dynamicite sur 8 coeurs

Figure 7 – Mesure 1 en O(1) sur 2 et 8 coeurs

16. Dynamicite : Dp =Sp

Sdp

Page 10: PMP Report

5 CONCLUSION 10

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 101,1000

0.0

0.5

1.0

1.5

2.0

spee

dup

- 2

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 101,1000

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

2

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 101,1000

0

1

2

3

4

5

6

spee

dup

- 2

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 101,1000

0

1

2

3

4

5

6

7

8

dyna

mic

ity -

2

(d) dynamicite sur 8 coeurs

Figure 8 – Mesure 2 en O(1) sur 2 et 8 coeurs

4.6.5 Resultats en O(n)

Dans un second temps, le benchmark est execute pour le probleme qui se resoud en tempsvariable. Les resultats de chaque mesure sont numerotes d’apres le tableau des mesures decritprecedemment en figure 6.

Il est important d’ajouter que compte tenu de la resolution du probleme en O(n) et nonplus en fonction de la dimension, celle ci perd de son importance. Ainsi les mesures 1, 4 et 5 nesont plus nessaire a mesurer. Seules les mesures 2 et 3 seront presentees ci-dessous.

Un algorithme sequentiel execute sur un processeur a 8 coeurs en comparaison avec un pro-cesseur a 2 coeurs est plus performant sur des petits echantillons. Nous avons donc choisit dedefinir les bornes des parametres, decrits en figure 6, comme multiple du nombre de coeursdisponible.

Les mesures sont presentees en fonction des processeurs utilises et disponibles en figure 12et 13.

5 Conclusion

Pour un processeur a 2 coeurs, selon la complexite du probleme utilisee, nous pouvonsobserver par la mesure du speedup que les ressources sont utilisees au maximum 17 pour degrandes tailles d’echantillon. Les petites tailles d’echantillon restant dominees par une executionsequentielle.

Pour un processeur a 8 coeurs, en hyperthreading, notre premiere observation consiste amontrer les limites de l’hyperthreading, en effet nous utilisons pas plus de 4 coeurs. Et pour

17. cpu-bound

Page 11: PMP Report

5 CONCLUSION 11

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 1001,1000

0.0

0.5

1.0

1.5

2.0

spee

dup

- 3

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 1001,1000

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

3

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 1001,1000

0

1

2

3

4

5

6

7

spee

dup

- 3

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1,1000 to 1001,1000

0

1

2

3

4

5

6

7

8

dyna

mic

ity -

3

(d) dynamicite sur 8 coeurs

Figure 9 – Mesure 3 en O(1) sur 2 et 8 coeurs

rejoindre ce qui a ete dit sur 2 coeurs, un plus grand nombre de petites tailles d’echantillonreste dominee par une execution sequentielle.

La difference entre les deux complexites de probleme s’observe dans la mesure de la dyna-micite. En effet pour un probleme en O(1), la planification statique en OpenMP permet d’avoirune meilleur efficacite de travail tandis que en O(n), la planification dynamique apporte quelqueamelioration.

Pour resumer nous avons compare par nos mesures les 2 types de planification de taches enOpenMP, les 2 complexites de problemes que nous serons amene a paralleliser et finalement sur2 types de processeurs differents.

Un point que je n’ai pas eu le temps d’eclaircir que j’invite a regarder est l’utilisation del’auto parallelisation integre au compilateur GCC 18. Il s’agit d’un niveau d’optimisation quiconsiste a verifier la non dependance des donnees dans les boucles et les paralleliser.

18. Automatic Parallelization : http://gcc.gnu.org/wiki/openmp

Page 12: PMP Report

5 CONCLUSION 12

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,101

0.0

0.5

1.0

1.5

2.0

spee

dup

- 4

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,101

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

4

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,101

0

1

2

3

4

5

6

spee

dup

- 4

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,101

0

1

2

3

4

5

6

7

dyna

mic

ity -

4

(d) dynamicite sur 8 coeurs

Figure 10 – Mesure 4 en O(1) sur 2 et 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,1001

0.0

0.5

1.0

1.5

2.0

spee

dup

- 5

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,1001

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

5

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,1001

0

1

2

3

4

5

6

spee

dup

- 5

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 1000,1 to 1000,1001

0

1

2

3

4

5

6

7

8

dyna

mic

ity -

5

(d) dynamicite sur 8 coeurs

Figure 11 – Mesure 5 en O(1) sur 2 et 8 coeurs

Page 13: PMP Report

5 CONCLUSION 13

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 2,1000 to 202,1000

0.0

0.5

1.0

1.5

2.0

varia

ble_

spee

dup

- 2

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 2,1000 to 202,1000

0.0

0.5

1.0

1.5

2.0

varia

ble_

dyna

mic

ity -

2

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 8,1000 to 808,1000

0

1

2

3

4

5

6

7

varia

ble_

spee

dup

- 2

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 8,1000 to 808,1000

0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

varia

ble_

dyna

mic

ity -

2

(d) dynamicite sur 8 coeurs

Figure 12 – Mesure 2 en O(n) sur 2 et 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 2,1000 to 2002,1000

0.0

0.5

1.0

1.5

2.0

spee

dup

- 3

(a) speedup sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 2,1000 to 2002,1000

0.0

0.5

1.0

1.5

2.0

dyna

mic

ity -

3

(b) dynamicite sur 2 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 8,1000 to 8008,1000

0

1

2

3

4

5

6

7

8

varia

ble_

spee

dup

- 3

(c) speedup sur 8 coeurs

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101100 iterations from 8,1000 to 8008,1000

0.0

0.5

1.0

1.5

2.0

2.5

3.0

varia

ble_

dyna

mic

ity -

3

(d) dynamicite sur 8 coeurs

Figure 13 – Mesure 3 en O(n) sur 2 et 8 coeurs


Recommended