Discussion :

[Laurent Gomila]

Voili voilou

[epsilon68]

Je crois pas car il faut absolument que la réduction soit faite dans une section critique à cause de la modification d'une variable partagée. Avec ma syntaxe je ne peux/veux pas imposer les mêmes restrictions qu'OpenMP aux réductions (opérations atomiques). Et si je renonce d'une manière ou d'une autre à utiliser OpenMP, il faut que j'utilise les mutex de ma librairie (ce qui n'a plus de sens si on s'impose l'utilisation d'OpenMP).

par exemple

Code :

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

1
2
3
4
5
6
7
8
double threadvalues = new double[ omp_get_num_threads_max()]
 
#pragma omp for
for( i=0 ; i<end-begin ; i++) {
  threadvalues[omp_get_thread_num()] = xxx;
}
 
// maintenant tu fais ta reduction sur les quelques elements = au nombre de processeurs

Qu'en penses-tu ?

[Matthieu Brucher]

Astu essayé ICC 10 ? Apparemment, il y a une meilleure adéquation avec la bibliothèque de thread sous-jacente, y compris pour OpenMP - qui est utilisé dans MKL pour les FFT, avec une interface à la FFTW3 -

En ce qui concerne HT, il vaut mieux le désactiver dans ce genre de cas - même Intel l'indique dans sa doc maintenant -

Et je trouve aussi que limiter à un int le découpage pour OpenMP est débile, en fait, on ne peut même pas mettre un unsigned long, c'est dire !

Tu as testé/utilisé TBB jusqu'à quel point ?

[Charlemagne]

Les benchs de Laurent sont cohérents avec les tout premiers qu'il a fait avec des gains de x1.3 à x1.8 selon les tailles de matrices, voir même x2 quand le cache est complètement saturé. Vos tests à tous n'ont pas été vains!
Les différences avec les tout premiers benchs sont:
-meilleur détections des processeurs présents
-relativement bon threshold single/multi thread pour éviter des coûts exorbitants de synchronisation.
-meilleur répartition de la charge sur les divers processeurs.

J'ai compilé les derniers benchs FFT avec l'option Ob2 et donc c'est plus lent sur l'Athlon qu'avec l'option Ob1 comme constaté précédemment (la raison est toujours un mystère pour moi). Pourtant l'option Ob2 a l'avantage d'être légèrement plus rapide sur les Pentiums et me donne des exécutables nettement moins volumineux. Ca va pas être un choix facile à prendre au final...

Astu essayé ICC 10 ? Apparemment, il y a une meilleure adéquation avec la bibliothèque de thread sous-jacente, y compris pour OpenMP - qui est utilisé dans MKL pour les FFT, avec une interface à la FFTW3 -

J'ai pas eu l'occasion, c'est encore en version beta non?
Et puis j'ai fais arrêter mon abonnement à ICL, car je trouve ICL9 très mauvais. ICL8.1 me donne de bien meilleur résultats.
Je sais pas ce qu'Intel avait modifié, mais y'a pas que du bon.

En ce qui concerne HT, il vaut mieux le désactiver dans ce genre de cas - même Intel l'indique dans sa doc maintenant -

Quelle doc, t'as un lien?
Si tu sais comment désactiver (momentanément) l'hyper-threading ça m'intéresse.

Et je trouve aussi que limiter à un int le découpage pour OpenMP est débile, en fait, on ne peut même pas mettre un unsigned long, c'est dire !

Ca dépend du temps de calcul d'une itération, et puis 1 est la valeur par défaut. En fait c'est moi qui fait le découpage manuellement en morceau de taille 'grain'. J'ai pas trouvé mieux dans mon implémentation pour utiliser des itérateurs, et ça n'a visiblement pas d'incidence sur la rapidité.

Tu as testé/utilisé TBB jusqu'à quel point ?

J'avais la version beta pendant 7-8 mois. J'étais alors encore abonné à ICL et Intel me l'avait proposée.
Je l'ai testée un peu à l'époque (en particulier les fonctions PARALLEL_FOR et PARALLEL_REDUCE) et ça marchait bien, mais je trouvais la syntaxe un peu lourde. Je m'en suis inspiré pour mon implémentation, mais j'ai beaucoup simplifier la syntaxe (je trouve). Je pourrais si je voulais éventuellement encore l'utiliser en avançant la date de l'ordi car malheureusement TBB vérifie la date lors de l'exécution. (donc pas question de distribuer un exécutable).

[Matthieu Brucher]

J'ai pas eu l'occasion, c'est encore en version beta non?
Et puis j'ai fais arrêter mon abonnement à ICL, car je trouve ICL9 très mauvais. ICL8.1 me donne de bien meilleur résultats

Il est sorti au début du mois, je le teste un peu sous Linux - car gratuit pour une utilisation non commerciale -
Je n'ai jamais pu tester ICC8, je suis directement passé au 9 qui était bon. J'ai tout de même des résultats parfois un peu moins bon avec le 10 qu'avec le 9.

Quelle doc, t'as un lien?
Si tu sais comment désactiver (momentanément) l'hyper-threading ça m'intéresse.

Je n'ai pas de lien, c'est dans la doc de MKL.
En revanche, à part le désactiver dans le bios, pas de salut. De toute manière, l'utiliser ralentit les perfs d'un code un tant soit peu optimisé

Ca dépend du temps de calcul d'une itération, et puis 1 est la valeur par défaut. En fait c'est moi qui fait le découpage manuellement en morceau de taille 'grain'. J'ai pas trouvé mieux dans mon implémentation pour utiliser des itérateurs, et ça n'a visiblement pas d'incidence sur la rapidité.

Pardon, je parlait du fait qu'on ne pouvait pas faire d'itération sur autre chose qu'un int
Lorsque j'ai tenté de parallélisé un code comme ça, j'ai forcé moi-même la taille d'un grain, par exemple pour du calcul patriciel, tu mets un 30, comme ça ça marche à partir de taille 30.
Je n'ia pas vu comment tu avais fait, mais j'ai constaté une sacré différence en modifiant l'ordre des boucles dans la multiplication matricielle, le problème étant de découper correctement les boucles pour maximiser le cache puisqu'il faut 2 boucles pour calculer complètement les valeurs à la place d'une seule dans l'implémentation "naïve".

J'avais la version beta pendant 7-8 mois. J'étais alors encore abonné à ICL et Intel me l'avait proposée.
Je l'ai testée un peu à l'époque (en particulier les fonctions PARALLEL_FOR et PARALLEL_REDUCE) et ça marchait bien, mais je trouvais la syntaxe un peu lourde. Je m'en suis inspiré pour mon implémentation, mais j'ai beaucoup simplifier la syntaxe (je trouve). Je pourrais si je voulais éventuellement encore l'utiliser en avançant la date de l'ordi car malheureusement TBB vérifie la date lors de l'exécution. (donc pas question de distribuer un exécutable).

Ah, c'est une bêta donc limité dans le temps, c'est ça ?
Je n'ai pas exactement encore compris l'intérêt de cette bibliothèque, personnellement. Déjà, pour vraiment en tirer partie, il faut au moins un biproc ou un dual-core, on n'a pas toujours ça sous la main

[Charlemagne]

Pardon, je parlait du fait qu'on ne pouvait pas faire d'itération sur autre chose qu'un int

Ok, on est d'accord. OpenMP est trop "C", pas assez "générique".

Ah, c'est une bêta donc limité dans le temps, c'est ça ?

C'était bien une beta limitée dans le temps, mais je crois qu'Intel en est au moins à la version 1.1 maintenant.

Je n'ai pas exactement encore compris l'intérêt de cette bibliothèque, personnellement. Déjà, pour vraiment en tirer partie, il faut au moins un biproc ou un dual-core, on n'a pas toujours ça sous la main

Je suis d'accord aussi mais on pourrait en dire autant pour OpenMP.
D'où l'utilité d'avoir ouvert cette discussion

Lorsque j'ai tenté de parallélisé un code comme ça, j'ai forcé moi-même la taille d'un grain, par exemple pour du calcul patriciel, tu mets un 30, comme ça ça marche à partir de taille 30.
Je n'ia pas vu comment tu avais fait, mais j'ai constaté une sacré différence en modifiant l'ordre des boucles dans la multiplication matricielle, le problème étant de découper correctement les boucles pour maximiser le cache puisqu'il faut 2 boucles pour calculer complètement les valeurs à la place d'une seule dans l'implémentation "naïve".

Je suis d'accord pour dire qu'avant de penser à l'optimisation multi-threads, y'a pleins de pistes à suivre. Avec la FFT l'optimisation du cache n'est malheureusement pas aussi facile que pour la multiplication matricielle, puique la FFT fait des accès randoms à la mémoire et pas sur des morceaux contigüs.
Tôt ou tard je vais quand même multi-threader mon implémentation de multiplication matricielle.

[Matthieu Brucher]

Tôt ou tard je vais quand même multi-threader mon implémentation de multiplication matricielle.

Tu pourras comparer avec l'impélemntation d'Intel

[epsilon68]

je pense qu'on peut eviter ta section critique.
Aussi je ne vois pas pourquoi OpenMP aurait une latence, c'est bizarre.
J'aurais bien aimé comparer vraiment en essayant d'autres facons de mon coté ...

[Charlemagne]

je pense qu'on peut eviter ta section critique.

Je crois pas. D'une manière ou d'une autre il faut protéger la réduction qui écrit dans une variable partagée (la variable 'f').
La réduction d'OpenMP contourne le problème en imposant d'utiliser une instruction atomique (instruction atomique=instruction spéciale de processeurs qui permet la lecture ou l'écriture concurrente sans avoir à recourir à un mutex.

Aussi je ne vois pas pourquoi OpenMP aurait une latence, c'est bizarre.
J'aurais bien aimé comparer vraiment en essayant d'autres facons de mon coté .

Je trouve ça pas si bizarre. Et puis, que mon implémentation batte OpenMP sur les petites tailles n'est pas pour me déplaire! J'ai l'impression qu'OpenMP est légèrement plus rapide que moi pour les grandes dimensions mais vraiment pas de beaucoup.

Il faudrait comparer avec ce que donne l'implémentation de VC2005 ou tout autre implémentation. Peut-être en utilisant le petit programme qui teste 'accumulate' plus haut en réduisant fortement la taille de vecteur (de l'ordre de l'unité ou de la dizaine), mais en augmentant le nombre de boucles pour garder un temps de mesure de l'ordre de la seconde.

[epsilon68]

Je crois pas. D'une manière ou d'une autre il faut protéger la réduction qui écrit dans une variable partagée (la variable 'f').
La réduction d'OpenMP contourne le problème en imposant d'utiliser une instruction atomique (instruction atomique=instruction spéciale de processeurs qui permet la lecture ou l'écriture concurrente sans avoir à recourir à un mutex.

je suis d'accord que la reduction avec openmp est limité.
je pense aussi que ta section critique peut etre evitée en gardant les valeurs de chaque thread puis de faire la reduction manuellement (pas multithread) car ce serait sur une tableau de taille toute petite (nombre de processeurs)

[epsilon68]

Et puis, que mon implémentation batte OpenMP sur les petites tailles n'est pas pour me déplaire!

;-) j'aime vraiment OpenMP c'est pour ca que je m'interesse beaucoup si il y a des eventuelles faiblesses, et de chercher la raison... Ton benchmark me passionne, la concurrence est un sujet qui me tient particulierement a coeur...
je ne suis pas encore convaincu par les resultats alors je cherche avec toi
et en tous les cas j'aime bien le code que tu as fait et que j'ai pu voir.

merci pour ton travail. (je le teste sur un server de prod )

[Charlemagne]

merci pour ton travail. (je le teste sur un server de prod )

Une seule condition et j'y tiens: licence GPL

[epsilon68]

Une seule condition et j'y tiens: licence GPL

Je suis tres respectueux des licences et j'apprecie ton travail.

[Charlemagne]

Merci, et merci pour le compliment.

Y'a rien à faire: OpenMP (en tout cas l'implémentation d'ICL) est lente pour les petites boucles.
Le petit programme suivant teste la clause 'if' d'OpenMP. (Y'a eu quelques changements mineurs dans mon implémentation que tu trouveras ci-joint).

Code :

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

1
2
3
4
5
 
C     : 0.828s
OpenMP: 1.953s
STL   : 0.812s
Ma lib: 0.828s

Code :

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
76
77
78
79
80
81
82
83
84
85
86
87
#include <vector>
#include <numeric>
#include <iostream>
#include <ctime>
#include <omp.h>
using namespace std;
 
 
#define inline __forceinline
#define MAX_THREADS 2
//#define OPENMP
#include "threads.h"
 
inline double get_time() { return double(clock())/CLOCKS_PER_SEC; }
 
template<class V>
struct fill_function
{
  V val;
  fill_function(const V &v) : val(v) {}
  template<class RanIt> void operator()(RanIt begin, RanIt end) const { fill(begin,end,val); }
};
 
template<class V>
struct accumulate_function
{
  typedef V result_type;
  mutable result_type val;
  accumulate_function() : val(0) {}
  void join(const accumulate_function &x) const { val+=x.val; }
  template<class It> void operator()(It begin, It end) const { val=accumulate(begin,end,val); }
};
 
template<class RanIt,class T>
T parallel_accumulate(RanIt begin, RanIt end, const T &val)
{
  accumulate_function<T> func;
  gmt::parallel_reduce(begin,end,func,10000);
  return val+func.val;
}
 
int main()
{
  typedef int value_type;
  vector<value_type> X(1000,1);
  value_type *pX=&X[0];
  int imax=1000000;
 
  //fill(X.begin(),X.end(),1);
  //gmt::parallel_for(X.begin(),X.end(), fill_function<value_type>(1), 10000);
 
  double t0=0;
  value_type *psum = new value_type; // alloué dynamiquement pour tromper l'optimisation d'ICL
 
  t0=get_time();
  for (int i=0; i<imax; ++i)
  {
    value_type sum=0;
    int jmax=X.size();
    for (int j=0; j<jmax; ++j)
      sum+=pX[j];
    *psum=sum;  
  }
  cout << "C     =" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  t0=get_time();
  for (int i=0; i<imax; ++i)
  {
    value_type sum=0;
    int jmax=X.size();
    #pragma omp parallel for if (jmax>10000) schedule(dynamic,10000) reduction(+:sum)
    for (int j=0; j<jmax; ++j)
      sum+=pX[j];
    *psum=sum;  
  }
  cout << "OpenMP=" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  t0=get_time();
  for (int i=0; i<imax; ++i)
    *psum=accumulate(X.begin(),X.end(),0);
  cout << "STL   =" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  t0=get_time();
  for (int i=0; i<imax; ++i)
    *psum=parallel_accumulate(X.begin(),X.end(),0);
  cout << "Ma lib=" << *psum << ": " << get_time()-t0 << "s" << endl;
}

PS: J'ai changé le code ci-dessus, y'avait un problème dans les includes.

[epsilon68]

je n'obtiens pas du tout des resultats coherents...
si on pouvait maintenant changer d'une addition et appliquer une formule telle que cosinus ...

[Charlemagne]

Tu peux essayer mais je crois pas que ça fasse une différence parce que le but ici c'est de mesurer le coût d'une condition de clause 'if' non remplie par rapport à une implémentation single-thread.

[epsilon68]

mais que ton implementation soit si rapide m'etonne vraiment ...
tu ne peux pas etre aussi rapide que le c quand meme .... tu as au minimum une legere penalité d'initialisation des threads ..

Tu fais appel a des std:accumulate dans ton implementation,
tu pourrais donner la fonction pour appliquer un cos par exemple ?

[Charlemagne]

mais que ton implementation soit si rapide m'etonne vraiment ...
tu ne peux pas etre aussi rapide que le c quand meme .... tu as au minimum une legere penalité d'initialisation des threads ..

Faut se rendre à l'évidence
C'est négligeable pour mon implémentation vis-à-vis de la taille du vecteur de 1000. Pour une raison X ce n'est pas négligeable pour l'OpenMP de ICL. Je peux pas faire mieux: c'est exactement le même code dans le petit programme entre les tests "C" et "OpenMP".
Tu n'as pas de résultats cohérents sous Visual?

[epsilon68]

number of thread max: 4
C =1000: 0.89s
OpenMP=1000: 10.735s

et j'ai le code suivant (apres beaucoup de tests/modifs)

Je ne comprends pas le if openmp,
autant faire un if (en dessous d'une certaine taille) prendre l'implementation single thread
[EDIT] J'ai rien dit, je comprends

Code :

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
	double t0=0; 
	double *psum = new double; // alloué dynamiquement pour tromper l'optimisation d'ICL   
 
	t0=get_time();
	for (int i=0; i<imax; ++i)  {  
		double sum=0; 
 
		for (int j=0; j<LEN; ++j)  
			//sum+=cos(pX[j]); 
			sum+=pX[j];
 
		*psum=sum; 
	}  
 
	cout << "C =" << *psum << ": " << get_time()-t0 << "s" << endl; 
 
	t0=get_time(); 
	for (int i=0; i<imax; ++i)  {  
		double sum=0; 
 
		#pragma omp parallel for reduction(+:sum)  
		for (int j=0; j<LEN; ++j)  
			//sum+=cos(pX[j]); 
			sum+=pX[j]; 
 
		*psum=sum; 
	}  
 
	cout << "OpenMP=" << *psum << ": " << get_time()-t0 << "s" << endl;

[Charlemagne]

Tu fais appel a des std:accumulate dans ton implementation,
tu pourrais donner la fonction pour appliquer un cos par exemple ?

Ca sert à rien de le faire, ça n'aurait pour effet que de rallonger les temps de calcul et donc de rendre moins flagrant les temps de latence...

autant faire un if (en dessous d'une certaine taille) prendre l'implementation single thread

A priori ça revient au même mais c'est pas dans "l'esprit" d'OpenMP.
Faut pas croire que les standards sont toujours bien.

number of thread max: 4
C =1000: 0.89s
OpenMP=1000: 10.735s

Pas terrible du tout pour l'implémentation OpenMP de Visual pour un code identique...