Discussion :

[Laurent Gomila]

Ok, effectivement on dirait qu'OpenMP est bien activé. Bizarre...

[epsilon68]

flute j'avais loupe l'init du t0

en corrigeant tous ca j'obtiens:

number max of threads:4
C =10000000: 1.094s
OpenMP=10000000: 0.625s
STL =10000000: 0.625s

[epsilon68]

a priori un benchmark comme cela ne montre pas vraiment la superiorité du MT...
il faut charger la mule pour le voir...
juste en mettant: sum+=cos(X[j]/(double)i);
j'obtiens:

C =0: 37.813s
OpenMP=0: 15.25s

et en STL ?

[Charlemagne]

Le mystère est (en bonne partie) résolu.

J'ai l'impression que c'est à cause d'une histoire de fonctions non inlinées correctement. Ce qui corrobore ma première impression sur OpenMP sur le fait que c'est trop "C" et pas assez "C++".

En utilisant un pointeur plutôt qu'un std::vector j'obtiens les résultats suivant.
C++ : 0.797s
OpenMP: 0.61s
STL : 0.765s
(Ma lib: 0.532s)

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
#include <vector>
#include <numeric>
#include <iostream>
#include <ctime>
#include <omp.h>
using namespace std;
 
inline double get_time() { return double(clock())/CLOCKS_PER_SEC; }
 
int main()
{
  typedef int value_type;
  vector<value_type> X(10000000,1);
  value_type *pX=&X[0];
 
  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<50; ++i)
  {
    value_type sum=0;
    int imax=X.size();
    for (int i=0; i<imax; ++i)
      sum+=pX[i];
    *psum=sum;  
  }
  cout << "C     =" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  t0=get_time();
  for (int j=0; j<50; ++j)
  {
    value_type sum=0;
    int imax=X.size();
    //#pragma omp parallel for schedule(static) reduction(+:sum)
    #pragma omp parallel for schedule(dynamic,100000) reduction(+:sum)
    for (int i=0; i<imax; ++i)
      sum+=pX[i];
    *psum=sum;  
  }
  cout << "OpenMP=" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  t0=get_time();
  for (int i=0; i<50; ++i)
    *psum=accumulate(X.begin(),X.end(),0);
  cout << "STL   =" << *psum << ": " << get_time()-t0 << "s" << endl;
}

[epsilon68]

il faudrait vraiment faire plus qu'une addition dans cette boucle ...
une expression mathematique ? un cos tan etc..

[Charlemagne]

pourquoi pas, mais le hic c'est que ça ne serait plus vraiment comparable avec l'un des très peu nombreux algos mathématiques de la STL. Peut-être un produit scalaire (inner_product).

Quoiqu'il en soit je pourrai bientôt reposter un nouveau bench FFT.

[epsilon68]

... j'attends tres impatiemment le nouveau bench ....

[mchk0123]

Résultats de cpuid :

name Intel(R) Pentium(R) 4 CPU 3.00GHz
vendor GenuineIntel
intel 1
amd 0

mmx 1
sse 1
sse2 1
sse3 1
3dnow 0

L1 cache 1048576
L2 cache 1

processors 2
logical cores 2
physical cores 1

Résultats de CPU-Z : <piece jointe>

Résultats des benchs sur un Intel x2 : <pieces jointes>

Benchmark FFT 64 SSE2.txt
Benchmark FFT 64 SSE2 MT2.txt
Benchmark FFT 64 SSE2 OpenMP2.txt

[epsilon68]

pourquoi pas, mais le hic c'est que ça ne serait plus vraiment comparable avec l'un des très peu nombreux algos mathématiques de la STL. Peut-être un produit scalaire (inner_product).

je ne pense pas que l'addition soit representatif pour un benchmark. Regarde le mien quand j'ai utilisé un cos ... OpenMP etait plus de 2 fois plus rapide...

... j'adore OpenMP

[Charlemagne]

Merci mchk0123
C'est vraiment 2 processeurs P4 HT ????!!! C'est bizarre parce que mon programme ainsi qu'OpenMP ne reconnaissent qu'un seul processeur. CPUZ ne semble pas faire mention d'un 2ème processeur également.
Et comme l'hyper-threading n'apporte malheureusement rien à ma FFT, c'est pas meilleur que le single-thread.

je ne pense pas que l'addition soit representatif pour un benchmark. Regarde le mien quand j'ai utilisé un cos ... OpenMP etait plus de 2 fois plus rapide...

ok c'est normal tu fais moins appel aux accès mémoires et donc tu te rapproches du gain théorique de x2.
Finalement le seul benchmark qui compte, c'est celui du programme qui répond au problème propre à chacun.


Je travaille encore sur ma FFT, les prochains benchs ne sont pas encore près...
(Faut dire qu'au départ je n'avais pas prévu les comparer avec OpenMP)

[mchk0123]

@Charlemagne, je pensais vraiment que c'était un bi-core car j'ai une double courbe sur le gestionnaire de tâches et l'exe systeminfo me donne les résultats suivants :


systeminfo.txt

En revanche CPU-Z et cpuid, comme tu l'as dit, ne semblent détecter qu'un seul core ... Qui est dans le vrai ?

[epsilon68]

c'est l'hyperthreading si je ne m'abuse...

[Charlemagne]

Je confirme c'est l'hyper-threading, moi aussi j'ai 2 courbes dans le gestionnaire de tâches.
(je suis rassuré, mon programme fonctionne!)

Voici le nouveau bench (comme avant il suffit d'exécuter le fichier '.bat' et de me rendre les 3 fichiers textes) Merci d'avance.
http://www.ient.rwth-aachen.de/team/...ads/Benchs.zip

J'ai pas réussi à rendre le coût de synchronisation négligeable, et donc les perfs pour les petites matrices sont de l'ordre de 10-20% moins bonnes par rapport au single-thread. Mais en tout cas mon implémentation s'en sort beaucoup mieux qu'OpenMP malgré sa clause 'if' (pour dire en deçà de quelle valeur il n'y a pas de multi-threading) qui l'améliore mais pas suffisamment.

J'espère que c'est le dernier bench pour les matrices complexes, mais attendez vous en tout cas à un bench pour la généralisation du multi-threading aux matrices réelles.

[epsilon68]

voila...

[epsilon68]

ca me surprend quand meme drolement que OpenMP est plus lent que ta solution ... ca peut pas venir d'autre chose ?

[Charlemagne]

Y'a un problème auquel j'avais pas pensé.
En fait j'avais demandé à mon programme de ne pas tenir compte de l'hyper-threading (pas efficace pour ma FFT), donc il ne crée que 2 threads (et non 4 comme OpenMP) sur ton 2x Xeon HT.
Le problème c'est que mon programme multi-thread n'est pas plus rapide que le single-thread de référence. Je suppose donc que le 2ème thread a été affecté à un CPU "virtuel". C'était pas le cas dans ton bench précédent, j'imagine que c'est une question de "chance".
En bref: l'hyper-threading c'est ici la merde. Je ne vois pas quoi faire pour imposer un thread à un processeur précis.

Voici un bench qui tiendra compte de l'hyper-threading (seul le programme Benchmark_FFT_64_SSE2_MT.exe a changé, pas la peine pour Epsilon68 d'exécuter les autres)
http://www.ient.rwth-aachen.de/team/...ads/Benchs.zip

ca me surprend quand meme drolement que OpenMP est plus lent que ta solution ... ca peut pas venir d'autre chose ?

Pour les petites matrices tu veux dire? (car pour les grandes à cause du problème ci-dessus c'est pas le cas).
je sais en tout cas que j'ai eu du mal a réduire le temps de synchonisation sur mon implémentation. Essaye d'en juger par toi-même pour OpenMP dans les fonctions parrallel_for et parallel_reduce à la fin de ce fichier. Je vois pas comment faire mieux.

[Charlemagne]

A la réflexion je ne vois rien à faire pour améliorer cette "latence" d'OpenMP pour les petites matrices.
Tu te rappelles de mon premier bench FFT avec OpenMP? J'avais mentionné que c'était vite fait bien fait: j'avais parallélisé les 2-3 boucles directement dans mon implémentation de la FFT, alors que les benchmarks actuels utilisent la fonction parallel_for réécrite avec OpenMP.
Eh bien, j'avais déjà remarqué ce temps de latence prééminent pour OpenMP.
La clause 'if' permet de rattraper ce retard en partie mais pas assez pour rendre l'utilisation d'OpenMP transparente sur des petites boucles.

PS: En tout cas sur l'implémentation d'OpenMP que j'utilise

[epsilon68]

voila:

[epsilon68]

j'ai un doute sur:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
#pragma omp parallel if (nchunks>1) firstprivate(func)
  {
    #pragma omp for schedule(dynamic,1)
    for (int i=0; i<nchunks; ++i)
    {
      int d=i*grain;
      RanIt it=begin+d;
      func(it,it+__min(n-d,grain));
    }
    #pragma omp critical
    f.join(func);
  }

je ne comprends pas le schedule(dynamic,1)
et je l'aurais surement ecrit en boucle for normal.

Code :

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

1
2
#pragma omp for
for( i=0; i<end-begin; i++)

j'aurais au préalable declaré un tableau de taille avec le max processor
puis j'aurais appliquer le reduce sur ce nombre d'element (sans openmp donc).
Qu'en penses-tu ?

il faut que je creuse plus ton code de toute facon, c'est tres interessant.

[Charlemagne]

Merci, les benchs sont meilleurs.
Mais j'arrive pas à avoir des gains en multi-threading faramineux sur ton 2x Xeon HT, OpenMP non plus d'ailleurs. J'obtiens des gains de l'ordre de x1.2 à x1.4 pour les matrices de grande taille. Ca varie mais ma librairie se tient dans les mêmes eaux qu'OpenMP.


Il faudrait que quelqu'un fasse le dernier bench (pour rappel http://www.ient.rwth-aachen.de/team/...ads/Benchs.zip) sur un CPU multi-core pour que je me fasse une opinion sur ce style de processeurs.
Avis aux volontaires: HanLee, Laurent...?

je ne comprends pas le schedule(dynamic,1)
et je l'aurais surement ecrit en boucle for normal.

Je me doutais que t'allais poser la question. La fonction-objet passée en paramètre prend un intervalle en paramètre (avec 2 itérateurs), donc que le découpage vu par OpenMP soit de 1 n'est pas génant.
J'avais certes pensé à changer la syntaxe de la fonction-objet pour qu'elle ne prenne qu'un paramètre:
-mais il aurait fallu changer les appels à parallel_for dans ma librairie
-je ne veux pas renoncer à une programmation dans le style de la STL avec des itérateurs
Pour l'instant je ne vois pas meilleur compromis, et je t'assure que ça n'a pas d'incidence sur la vitesse (j'ai comparé avec la FFT "vite fait bien fait" avec OpenMP)

j'aurais au préalable declaré un tableau de taille avec le max processor
puis j'aurais appliquer le reduce sur ce nombre d'element (sans openmp donc).
Qu'en penses-tu ?

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).