Discussion :

[myzu69]

Bonjour,

je suis en train d'étudier la bibliothèque TBB et n'en suis qu'au début de mon apprentissage (je lis le livre de James Reinders).

Voilà mon problème : j'ai lu la partie sur parallel_for et ai voulu tester, pour voir si j'avais bien compris ce que j'avais lu et là, je vois qu'en executant une boucle parallélisée sur deux Threads, le programme est plus lent que le même calcul réalisé en série.

Voici le résultat d'éxécution :

Debut du calcul en serie ...
version serie executee en 26 s

Debut du calcul en parallele ...
Calcul_fibo::nb_appel_copie = 0
Calcul_fibo::nb_appel_copie = 2
version parallele executee en 45.1546 s

----------- Fin de verification des resultats -----------

Gain = 0.575799

Cette fonction calcule le 30ème terme de la suite de fibonachi récursivement (donc je fais fibo(n) = fibo(n-1) + fibo(n-2) ). Je sais que ce n'est pas optimisé mais ce n'est pas le but ici, je teste juste la parallélisation de la boucle.

J'ai un tableau de 500 entiers et je recalcule pour chaque élément le 30ème terme de la suite. En ce qui concerne le grain, j'ai mis 250, pour que chaque thread éxécute 250 éléments du tableau. La boucle en série calcule elle l'ensemble des éléments du tableau.

Dans le constructeur par copie de Calcul_fibo, j'ai mis un compteur pour savoir combien de fois il est appelé. On peut voir qu'il a été appelé deux fois, un pour chaque thread.

Ha j'oubliais, je fais une vérification des résultats à la fin et les deux tableaux sont identiques. De plus, on voit bien dans la fenêtre de surveillance du système que lors de l'éxécution de la fonction en série, un seul core est utilisé (à 100%), alors que pendant la version parallele, les deux cores sont à 100% d'utilisation.

Je ne sais pas si je suis très clair, je peux mettre le code source si besoin ...

Encore une chose : je suis sous linux 64 bits et ai un Core 2 Duo T9300.

Voilà, si quelqu'un peut m'aider, je m'arrache les cheveux depuis 2 jours pour trouver d'où vient l'erreur/le problème ...


EDIT : En fait le problème était dû à mon installation de TBB, je l'avais installé via le gestionnaire de paquets d'Arch Linux et je ne sais pas trop pourquoi j'avais ces résultats là mais bon ... en téléchargeant sur le site d'Intel et en configurant les variables d'environnement correctement, tout fonctionne à merveille

[CoinForever]

Bonjour,

Je ne connais pas bien TBB, mais j'ai une version parallele de Fibonacci avec OpenMP si ca tinteresse.

A quel niveau tu parallelises ton algo Fibo ?

J'ai un tableau de 500 entiers et je recalcule pour chaque élément le 30ème terme de la suite.

Ce n'est pas tres clair. Le mieux a faire est de distribuer a deux threads differents le calcul de fibo(n-1) et fibo(n-2).
Si tu pouvais montrer l algo que tu utilises plus precisement.

[myzu69]

Heu non, mon but n'est pas de calculer fibo(n) mais de donner beaucoup de calculs à faire à l'ordi pour pouvoir voir la différence des temps d'éxécution de la fonction qui fait le calcul en série et de celle qui l'effectue en parallele.

J'ai donc créé un tableau de 500 entiers et pour chaque élément du tableau je recalcule fibo(30). A la rigueur je me contrefiche du résultat, je voudrais juste que le temps nécessaire pour calculer 500 fois fibo(30) soit divisé par 2 quand je fais le calcul sur les deux core, cependant pour l'instant il est multiplié par 2 donc ce n'est pas vraiment l'effet souhaité .

Pour le calcul de fibo(n), je fais fibo(n) = fibo(n-1)+fibo(n-2) dans les deux cas (série et parallele), de toute façon j'appelle la même fonction dans les deux cas. Le seul truc qui change c'est la boucle de parcours du tableau des 500 entiers : l'une est parallélisée, l'autre non .

[CoinForever]

Ah d'accord, tous les elements de ton tableau calculent fibo(30).
Un coeur s'occupe donc de calculer les 250 premiers elements tandis que l'autre coeur s'occupe des 250 derniers dans la version parallele.

En effet, la le probleme est simple et le temps de calcul ne devrait pas etre multiplie par 2... A noter par ailleurs que tu ne reussiras pas a diviser par 2 le temps de calcul dans le meilleur des cas. Ce serait trop beau :p.

Peux tu montrer le code par curiosite ?

edit : ah je l'ai lu un peu ce livre mais je n'ai rien teste dommage...

[myzu69]

oui oui, je me doute bien que je ne pourrais jamais avoir un facteur de gain de temps de 2 mais bon, un truc supérieur à 1 serait pas trop mal .

edit : je mets le code ici, ce sera peut-être plus facile à lire

Code main.cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "essai_fibo.h"
 
 
 
int main(int argc, char *argv[]) 
{
 
     int taille = 500;
     //je souhaite calculer le Nieme terme de la suite de fibo si uo = 0 et u1 = tab[i]
 
 
     //je cree 2 tableaux pour comparer les resultats en serie et en parallele
     int * tab_serie = new int [taille];
     int * tab_paral = new int [taille];
 
 
     for (int i = 0; i < taille; ++i) 
     {
     tab_serie[i] = 1;
     tab_paral[i] = 1;
     }
 
 
     //----------------------------------------------
     //---------------------------------------------
     //1. on fait les calculs en serie
     //---------------------------------------------
     cout << "Debut du calcul en serie ..." << endl;
     tick_count serial_t0 = tick_count::now();
 
     calcul_fibo_serie(tab_serie, taille, N);
 
     tick_count serial_t1 = tick_count::now();
     cout << " version serie executee en " << (serial_t1 - serial_t0).seconds() << " d apres tick_count " << endl;
 
 
     //----------------------------------------------
     //---------------------------------------------
     //2. on fait les calculs en parallele
     //---------------------------------------------
     cout << "\nDebut du calcul en parallele ..." << endl;
     tick_count parallel_t0 = tick_count::now();
 
     /* on affiche la valeur du membre static nb_appel_copie de Calcul_fibo avant l'appel de la fonction */
     cout << " Calcul_fibo::nb_appel_copie = " <<  Calcul_fibo::nb_appel_copie << endl;
 
     calcul_fibo_parallele(tab_paral, N, 0, taille);
 
     /* et après, pour voir le nombre de copies effectuées */
     cout << " Calcul_fibo::nb_appel_copie = " <<  Calcul_fibo::nb_appel_copie << endl;
 
     tick_count parallel_t1 = tick_count::now();
     cout << " version parallele executee en " << (parallel_t1 - parallel_t0).seconds() << " d'apres tick_count " << endl;
 
     //----------------------------------------------
     //---------------------------------------------
     //3. verification des resultats
     //---------------------------------------------
     for (int i = 0; i < taille; ++i) 
     {
          if (tab_serie[i] != tab_paral[i])
               cout << " !!!!!!!!!! erreur - resultats differents !!!!!!!!!!" << endl;
     }
     cout << " ----------- Fin de verification des resultats -----------" << endl << endl;
 
 
     cout << "\nGain = " << (double)(serial_t1 - serial_t0).seconds() / (parallel_t1 - parallel_t0).seconds() << endl << endl;
 
 
     delete [] tab_paral;
     delete [] tab_serie;
 
 
  return 0;
}

Code essai_fibo.h :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#ifndef ESSAI_FIBO
#define ESSAI_FIBO
 
#include <iostream>
 
 
#include "tbb/parallel_for.h"
#include "tbb/blocked_range.h"
#include "tbb/tick_count.h"
 
using namespace tbb;
using namespace std;
 
//rang fibo qu'on va calculer
static const size_t N = 30;
 
 
//--------------------------------------------------
//classe pour calcul parallele
 
class Calcul_fibo
{
  int * tab;
  int rang;
 
public: 
  static int nb_appel_copie;
 
  //operateur () a priori indispensable...
  // -- range definit la partie du tableau sur laquelle va agir l'operateur
  // -- rang est une variable qui donne le rang du terme de la suite fibo a calculer
  void operator() ( const blocked_range<int>& range) const;
 
  //constructeur : initialise tab avec le_tab
  Calcul_fibo(int * le_tab, int le_rang);
 
  //constructeur de copie bete pour compter les appels
  Calcul_fibo(const Calcul_fibo & cf);
 
 
};
 
 
void calcul_fibo_parallele(int * tab_paral, int rang, int range_begin, int range_end);
 
 
 
//--------------------------------------------------
// fonctions pour calcul serie
 
//applique fibo sur chaque element de tab_serie en serie
void calcul_fibo_serie(int * tab_serie, int taille, int rang);
 
 
 
//-----------------------------------------------------------
// fonction recursive pour calcul termes de la suite fibo
 
//retourne le terme de rang rang sachant u0 = 0 et u1 = u1 (fonction recursive)
int fibo( int u1, int rang);
 
#endif

Code essai_fibo.cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "essai_fibo.h"
 
 
 
//=================================================================
//  IMPLEMENTATION POUR LA CLASSE Calcul_fibo
//=================================================================
 
 
 
//initialisation du membre static
int Calcul_fibo::nb_appel_copie = 0;
 
//operateur ()
void Calcul_fibo::operator() ( const blocked_range<int>& range) const
{
  //on charge le tableau dans une variable locale (pour les perfs)
  int * tab_local = tab;
 
  //on applique notre operateur fibo sur la partie du tableau donnee par le blocked_range
  for (int i = range.begin(); i != range.end(); ++i)
    tab_local[i] = fibo( tab_local[i], rang);
}
 
 
//constructeur
Calcul_fibo::Calcul_fibo(int * le_tab, int le_rang)
{
  tab = le_tab;
  rang = le_rang;
}
 
//constructeur de copie
Calcul_fibo::Calcul_fibo(const Calcul_fibo & cf)
{
  tab = cf.tab;
  rang = cf.rang;
  nb_appel_copie++;
}
 
 
//=================================================================
// FONCTION QUI EFFECTUE LE CALCUL PARALLELE
//===================================================================
void calcul_fibo_parallele(int * tab_paral, int rang, int range_begin, int range_end)
{
     parallel_for(blocked_range<int>(range_begin, range_end, 250),  Calcul_fibo(tab_paral, rang) );
}
 
 
 
//=================================================================
// FONCTION QUI EFFECTUE LE CALCUL SERIE
//===================================================================
void calcul_fibo_serie(int * tab_serie, int taille, int rang)
{
  for (int i = 0; i < taille; ++i)
    tab_serie[i] = fibo( tab_serie[i], rang);
}
 
//=================================================================
// FONCTION RECURSIVE POUR LE CALCUL D UN TERME DE LA SUITE FIBO
//===================================================================
//complexite de l'ordre de 2^(rang) appels recursifs...
int fibo( int u1, int rang)
{
     if (rang == 1)
          return u1;
     if (rang == 0)
          return 0;
     return ( fibo(u1, rang-1) + fibo(u1, rang-2)  );
}

[myzu69]

Bon, après avoir laissé de côté pendant les fêtes je suis revenu dessus et me suis aperçu que j'avais oublié d'initialiser le task_scheduler

Maintenant j'ai le résultat suivant :

Debut du calcul en serie ...
version serie executee en 29.5716 s

Debut du calcul en parallele ...
Calcul_fibo::nb_appel_copie = 0
Calcul_fibo::nb_appel_copie = 2
version parallele executee en 26.5277 s

----------- Fin de verification des resultats -----------

Gain = 1.11474

J'ai donc un gain (youpi, enfin ) de 1.11 mais je trouve que ce n'est pas énorme ... ne devrait-on pas avoir un gain de 1.6, 1.8 voire un peu plus même avec un système non surchargé ?

EDIT : Je viens de m'appercevoir qu'en fonction de l'endroit où l'on place le task_scheduler_init, le temps d'éxécution n'est pas du tout le même :

Debut du calcul en serie ...
version serie executee en 16.5359 s

Debut du calcul en parallele ...
Calcul_fibo::nb_appel_copie = 0
Calcul_fibo::nb_appel_copie = 2
version parallele executee en 26.5928 s

----------- Fin de verification des resultats -----------

Gain = 0.621819

Debut du calcul en serie ...
version serie executee en 27.8825 s

Debut du calcul en parallele ...
Calcul_fibo::nb_appel_copie = 0
Calcul_fibo::nb_appel_copie = 2
version parallele executee en 26.4002 s

----------- Fin de verification des resultats -----------

Gain = 1.05615

Donc pour l'instant le gain est loin d'être suffisant pour qu'il soit intéressant d'implémenter une solution parallèle ... il doit encore y avoir un truc que j'ai oublié et/ou mal fait.