Discussion :

[Charlemagne]

Ca vaut le coup de tester OpenMP, ne serait-ce que pour comparer, car d'un autre coté:
-je crois déjà avoir programmé le plus dur pour ma gestion du multi-thread
-j'ai pas besoin de plus
-je peux toujours l'étendre moi-même comme je l'entends
-c'est portable (à condition d'être sous Windows ou d'avoir la libairie pthreads)
-je préfère une solution 100% C++

Dommage qu'OpenMP ce ne soit intégré que dans les compilos les plus récents car malheureusement je n'ai que:
-VC2003
-VC2005 Express
-GCC 3.4.4 (sous Windows). Les versions 4.x ne sont toujours pas disponibles sous Windows (depuis le temps!...)
Par contre j'ai ICL (Intel C++ compiler). La liste ne précise pas qu'elle version d'ICL intègre OpenMP, mais j'ai les versions récentes 8 et 9.

Je me demande quand même pourquoi Intel à pris la peine d'implémenter sa bibliothèque de multi-threading TBB (qui "concurrence" en quelque sorte OpenMP) si vraiment OpenMP était la panacée. TBB intègre des fonctions du genre parallel_for et parallel_reduce, mais est bien plus complète que la mienne à ce niveau (je trouve quand même leur syntaxe lourde).

Par contre j'ai un Athlon bicore au travail, je lancerai les tests la semaine prochaine. A voir aussi si un bench sur AMD Sempron 3400+ t'intéresse, c'est un monocore, mais ça pourrait permettre d'identifier des différences entre CPU & constructeurs.

Si ça te pose pas de problème au boulot, ok. merci

PS: Je viens de faire l'essai avec ma version favorite d'ICL, la version 8.1, et OpenMP ne marche pas. Je ferai l'essai avec ICL 9 ou 9.1 (quand je les aurai installés) mais c'est mal parti pour que j'utilise OpenMP

[Charlemagne]

Finalement, OpenMP marche avec ICL 8.1. Il suffisait de compiler avec l'option /Qopenmp, encore fallait-il le savoir...

[mchk0123]

Incroyable epsilon, tu as raison : http://gcc.gnu.org/gcc-4.2/changes.html

Du coup ça rend OpenMP portable sur toute plateforme (enfin en théorie, car gcc / mingw est encore en 3.4.5).

[Charlemagne]

Voila, je vous ai préparé de nouveaux benchmarks, vous pouvez oublier les précédents. J'ai tenu compte de la proposition de les regrouper en un seul téléchargement pour vous faciliter la tâche. Vous n'avez qu'à lancer le fichier 'benchs.bat' (qui lancera automatiquement pour vous les 3 benchs) et à me poster les 3 fichiers textes résultant.
http://www.ient.rwth-aachen.de/team/...ads/Benchs.zip
-bench de référence single-thread
-bench multi-thread
-bench muti-thread avec OpenMP
J'ai compilé les 3 benchs avec l'option /Ob2 qui se révéla donner de médiocres résultats sur l'Athlon, qu'a cela ne tienne, je veux comparer les 3 benchs entre eux pour l'instant.

Merci Epsilon68 pour ta suggestion d'utiliser OpenMP, que je ne connaissais pas.
A priori je compte mettre une option de compilation dans ma bibliothèque pour choisir la méthode de multi-threading a employer: la mienne ou OpenMP.
Pour l'instant le bench avec OpenMP a été fait vite fait bien fait en modifiant légèrement les parties de code concernée, mais à l'avenir je vais tâcher d'implémenter les fonctions de ma bibiothèque (parallel_for et parallel_reduce) à l'aide d'OpenMP. Ceci dit c'est pas franchement évident puisque j'utilise systématiquement des itérateurs pour les boucles (et pas uniquement un int comme OpenMP), et qu'OpenMP ne propose que des opérations élémentaires pour une réduction.

Sur mon vieux P4 HT
-le bench avec OpenMP est nettement plus lent que le bench de référence single-threadé pour les matrices de petite et de moyenne taille, là ou le multi-threading n'est pas justifié à cause du temps de synchronisations. Ce n'est pas le cas pour mon implémentation (j'avais déjà remarqué le problème et passé du temps à avoir des résultats convenables comme écris plus haut)
-OpenMP est un chouilla plus rapide pour les très grandes matrices qui ne tiennent plus entièrement dans la mémoire cache, mais c'est quasi négligeable.

[mchk0123]

Content que tu ai réussi à utiliser OpenMP.
Je ne sais vraiment pas si l'avenir sera propice à l'émergence de OpenMP comme standard, mais au moins cela à 2 vertues :

- éviter de ré-écrire du code à chaque nouveau programme MT (syndrome NIH)
- simplifier la relecture et la maintenance de code

[epsilon68]

C'est cool, vraiment cool que tu utilises OpenMP
Je crois que sa grande force est de laisser au compilo le soin de choisir ce qu'il fait de mieux pour la plateforme....

[Charlemagne]

Pour être franc je suis pas vraiment enthousiasmé par la syntaxe d'OpenMP.
Je lui préfère largement des solutions 100% C++ du genre Intel TBB ou de ma bibliothèque (ok ok... cette dernière est loin d'être complète du point de vue multi-threading mais elle se défend).
De toute façon je vais tâcher de garder ma syntaxe pour avoir des appels de fonctions génériques uniformes et l'utilisateur aura le choix du "moteur" qui fera tourner la gestion multi-thread (à condition que son compilo comprenne bien OpenMP).

Je trouve qu'OpenMP fait trop "C". Y'a pas vraiment moyen de l'utiliser pour paralléliser des algorithmes de la STL par exemple.

Ceci dit c'est une solution plus qu'acceptable pour faire assez aisément du multi-threading mathématique.

[epsilon68]

voici mes resultats

name Intel(R) Xeon(TM) CPU 3.40GHz
vendor GenuineIntel
intel 1
amd 0
mmx 1
sse 1
sse2 1
sse3 1
3dnow 0

physical core count 1
logical processor count 2
L1 cache size 2097152
L2 cache size 1


[EDIT] je crois que ton cpuid n'est pas bon... il y a deux processeurs physiques hyperthreadés ...

[epsilon68]

s'il te plait pourrais-tu nous montrer comment interpreter tes resultats ?
je suis incapable de savoir si openmp donne de meilleurs resultats ou non ....

[Charlemagne]

Les résultats sont des Mflops. Il est facile de les mettre dans Excel (il suffit de tirer le fichier teste) et d'en faire des courbes. Les benchs font des FFTs de matrices complexes (de floats et de doubles) tout comme le 3ème graphique des benchs que tu pourras trouver en bas de mon site:
http://www.ient.rwth-aachen.de/team/...al/genial.html
En abscisse les differentes tailles de matrices testées, en ordonnées les Mflops.

Pour comparer les perfs, 6 séries de mesures sont faites pour chaque taille de matrices selon
- le type: complexes de floats / complexes de doubles
- la bibliothèque utilisée: ma bibliothèque / FFTW en mode 'estimate' / FFTW en mode 'mesure'

Chaque Bench utilise une variante de compilation de ma librairie:
-single thread
-multi-thread
-multi-thread avec OpenMP

je crois que ton cpuid n'est pas bon... il y a deux processeurs physiques hyperthreadés ...

En fait, mon test de détection n'est pas capable de détecter le nombre de processeurs physiques différents, mais uniquement le nombre de cores dans le processeur utilisé. J'avais ouvert une discussion y'a quelque jours et on m'avait proposé de faire un appel à l'API Windows. J'aurais préféré sans appel à Windows mais je sais pas comment faire autrement. Je vais peut-être intégrer cet appel Windows à ma détection automatique.
OpenMP détecte lui 4 processeurs à ton systèmes, mais l'hyper-threading n'apporte visiblement quasiment aucun gain de vitesse. (c'est sans doute moins vrai pour des processus complêtement indépendants). A priori je vais donc intégrer cet appel Windows.

Les résultats sur ton double Xeon sont intéressants:
-bonnes performances vis-à-vis de FFTW ,alors que j'ai encore environ 6-7% de réserve en branchant SSE3
-mon implémentation multi-threading s'en sort bien face à OpenMP. C'est nettement plus rapide qu'OpenMP quand le muti-threading n'est pas justifié pour les petites matrices. OpenMP a visiblement plus de synchronisation à faire, malgré le fait que j'utilise bien la clause "if" prévues dans ce genre de cas.
-Mais les gains n'atteignent que le x1.4-1.5 et non le théorique x2. C'est sans doute dû au fait que les caches sont propres à chaque processeur contrairement à certains CPU à 2 noyaux.

C'est pas facile de régler le programme pour faire plaisir à tous les CPUs. Je vais quand même préparer d'autres benchs...
Je vais régler les benchs préparer

[Charlemagne]

@Epsilon68 et quiconque avec un système avec plusieurs processeurs rééls

voici un nouveau programme d'identification. J'ai rajouté l'appel de la fonction à l'API Windows pour demander le nombre de processeurs.
http://www.ient.rwth-aachen.de/team/...oads/cpuid.zip
J'obtiens 2 sur mon Pentium4 HT, j'espère que logiquement tu obtiendras 4 sur ton ordi avec 2 processeurs Xeon HT.
Merci

Sinon je suis en train d'intégrer OpenMP dans ma bibliothèque pour avoir une API unique pour le multi-thread.
Ca marche déjà pour la function 'parallel_for'. Par contre je suis pas sûr du tout que ce soit possible pour la function 'parallel_reduce' car (comme tu le mentionnais plus haut) il y a des restrictions dans OpenMP pour la réduction. Je vais tenter de m'en sortir avec les sections critiques...

[epsilon68]

voila ce que j'obtiens:

name Intel(R) Xeon(TM) CPU 3.40GHz
vendor GenuineIntel
intel 1
amd 0

mmx 1
sse 1
sse2 1
sse3 1
3dnow 0

L1 cache 2097152
L2 cache 1

processors 4
logical cores 2
physical cores 1

Aussi utilises-tu le meme principe dans ton bench ?
sinon openmp devait donner de meilleurs resultats ?

[epsilon68]

j'ai lu quelque part que l'hyper threading n'apportait qu'entre 5 et 10% de perf en plus ... et aussi que le rendement etait de 1.7 dans le cas de deux processors, certainement du aux raisons que tu as citées.

[mchk0123]

D'après ce que tu dis, epsilon, je rajouterais que pour des multi-cores mono-processeurs on devrait donc se situer au dessus de x1.7 vu que les cores sont sur le même "die" (accès plus rapides à la mémoire et aux caches).

[Charlemagne]

OK le nombre de processeur est bien reconnu. Dommage que je doive faire appel à une fonction de Windows.

J'avais entendu parlé de gains de l'ordre de 30% pour l'hyper-threading à l'époque. J'arrive à les obtenir de temps en temps, mais dans le cas de la FFT j'obtiens rien du tout, a priori à cause des chargements/écritures incessants dans la mémoire. J'arrive tout juste a gratter quelques pour cents pour les grandes matrices, alors que la mémoire cache est complètement saturée.

J'ai réussi à reprogrammé également ma fonction 'parallel_reduce' grace à une section critique, mais les perfs d'OpenMP sont catastrophiques vis-à-vis de mon implémentation.
J'ai fais quelques tests dont celui ci dessous. A moins d'une erreur grossière de ma part que je ne vois pas pourquoi OpenMP y est nettement plus lent qu'une simple implémentation C ou STL. J'obtiens encore des perfs meilleures en utilisant ma bibliothèque multi-thread.
-C: 1.375s
-OpenMP 2.703s
-STL: 0.766s
(-ma lib: 0.531s)
Tu veux bien compiler et exécuter ce petit programme sur un de tes ordis:

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
#include <vector>
#include <numeric>
#include <iostream>
#include <ctime>
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);
 
  double t0=0;
  value_type *psum = new value_type; // alloué dynamiquement pour dupper l'optimisation d'ICL
 
  for (int i=0; i<50; ++i)
  {
    value_type sum=0;
    int imax=X.size();
    for (int i=0; i<imax; ++i)
      sum+=X[i];
    *psum=sum;  
  }
  cout << "C     =" << *psum << ": " << get_time()-t0 << "s" << endl;
 
  for (int i=0; i<50; ++i)
  {
    value_type sum=0;
    int imax=X.size();
    #pragma omp parallel for schedule(dynamic,100000) reduction(+:sum)
    for (int i=0; i<imax; ++i)
      sum+=X[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;
}

PS:

Aussi utilises-tu le meme principe dans ton bench ?
sinon openmp devait donner de meilleurs resultats ?

J'utilise effectivement les même fonctions de détection dans mon bench.
Mais comme dans ce cas il n'y a pas ou peu de gain grâce à l'hyper-threading, les perfs d'OpenMP n'étaient pas (sensiblement) meilleures.
En tout cas je vais rectifier la détection du nombre réel de processeurs dans mes prochains benchs.

[epsilon68]

... heu j'obtiens aussi les memes resultats ...
STL < c < OpenMP

alors deux solutions: l'implementation de VC++ est nulle, ou on a loupé quelque chose ....

[Laurent Gomila]

ou on a loupé quelque chose ....

Oui
Il manque un "t0=get_time();" juste avant le test OpenMP, donc le temps mesuré contient également le test C.

Attention aussi à l'utilisation de la même variable (i) dans les boucles imbriquées.

En corrigeant ce petit détail, et en incluant <omp.h> pour que mon Visual Studio ne me fasse pas d'erreur avec vcomp.dll, j'obtiens les résultats suivants :

C : 1.484 s
OpenMP : 0.812 s
STL : 0.907 s

[Charlemagne]

Merci Laurent
Flute. Je suis confus. (J'ai dû faire un copier-coller trop rapidement)
Désolé pour la fausse alerte. On oublie...

Mais il reste quand-même des incohérences sur mon ordi.
-C: 1.344
-OpenMP: 1.344
-STL: 0.766
-ma lib: 0.531

Je constate
-qu'il n'y a pas de gain avec OpenMP vis-à-vis du C sur mon P4HT.
-que l'implémentation STL est plus rapide qu'une implémentation C basique et qu'OpenMP.
-ma lib (basée sur l'algo de la STL) gagne effectivement 30% en vitesse grâce à l'hyper-threading.

PS: Pour Laurent, OpenMP sur un Athlon duo, est à peine plus rapide que l'implémentation STL single-thread...

[Laurent Gomila]

Vu les temps identiques entre les tests C et OpenMP, je dirais plutôt qu'OpenMP n'est pas activé lors de tes tests.

Tu utilises Visual Studio ?

[Charlemagne]

Vu les temps identiques entre les tests C et OpenMP, je dirais plutôt qu'OpenMP n'est pas activé lors de tes tests.
Tu utilises Visual Studio ?

J'utilise ICL (je n'ai pas VC2005).
J'ai pensé également à cette explication, et pourtant, je confirme qu'OpenMP est activé:
-option de compilation mise
-le compilo confirme la parallélisation (remark: OpenMP DEFINED LOOP WAS PARALLELIZED.)
-la fonction omp_get_max_threads() renvoie la valeur 2