Segmentation fault

Programmation
#21

Oh que si c’est très important. :wink:
L’idéal c’est que les threads soient complètement découplés (ils accumulent chacun dans leur coin, et leurs résultats sont additionnés à la fin), c’est vachement plus efficace… Si au contraire ils incrémentent tous la même variable à chaque itération, il faut de la synchronisation (et donc il y a goulot d’étranglement, sans même parler du cache-trashing). Dans la catégorie “algos simples” Il n’y a pas vraiment d’intermédiaire possible (mais encore une fois, je ne sais pas jusqu’où OpenMP pousse le vice, si ça se trouve il utilise des algos de malade pour gérer tout ça). D’où l’importance de l’algo utilisé par OpenMP.

En fait faudrait tester quoi. :smiley:

#22

Ok, je viens de comprendre ce que tu veut dire. Je sais je suis dur de la compréhension ces derniers temps veillez m’excuser.

Je lirais pas la doc d’OpenMP pour ça, mais j’ai codé la version OpenMP et une version qui implémente l’isolation des threads sur un bench qui ne veut rien dire la seconde version un demi seconde plus vite (sur 52) la version monothreadée s’exécute en 1 minute et 18s. On ne gagne pas grand chose parce que j’ai un seul core hyperthreadé. Le code est prévu pour deux threads pour le faire évoluer je pense que vous trouverais (demain soir s’y j’en ai le courage je le passerais sur mon Athlon X3).

[code]#include <stdio.h>
#include <omp.h>

double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
unsigned long rang;
double p = 4;
while (scanf ("%d",&rang) == 0) getchar ();

#pragma omp parallel for
for(unsigned long i = 1; i <= rang; ++i)
{
p += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1);
}

printf(“valeur approchée de pi au rang %d : %.10f\n”, rang, p);
}[/code]

et la version améliorée :

[code]#include <stdio.h>
#include <omp.h>

double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
const int nb_thread = 2;
double result[] = {0., 0.};
unsigned long rang;
double p = 4;
while (scanf ("%d",&rang) == 0) getchar ();

#pragma omp parallel for num_threads(nb_thread)
for(unsigned long i = 1; i <= rang; ++i)
{
result[omp_get_thread_num()] += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1);
}

for(double* I = result; I < result+nb_thread; ++I)
{
p+=*I;
}

printf(“valeur approchée de pi au rang %d : %.10f\n”, rang, p);
}[/code]
Pour compiler ça une fois qu’on l’a mis dans le fichier pi.c :

export CFLAGS='-std=c99 -O2 -fopenmp' make pi
(c’est dommage d’appeler le compilateur à la main ;_) )

#23

Résultat bizarre chez moi (dual core), apparemment OpenMP a besoin d’une synchronisation explicite lorsque plusieurs threads accèdent à un même emplacement mémoire.

pi1.c

[code]#include <stdio.h>
#include <omp.h>

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
double p = 4.;
unsigned long rang = 1000000000;

#pragma omp parallel for
for(unsigned long i = 1; i <= rang; ++i)
{
p += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1.);
}

printf(“valeur approchée de pi au rang %ld : %.10f\n”, rang, p);
}[/code]

pi2.c

[code]#include <stdio.h>
#include <omp.h>

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
const int nb_thread = 2;
double result[nb_thread]; // désolé j’aime pas devoir modifier 2 endroits pour un même paramètre :smiley:
double p = 4.;
unsigned long rang = 1000000000;

// du coup faut initialiser le tableau
for (double* I = result; I < result + nb_thread; ++I)
*I = 0.;

#pragma omp parallel for num_threads(nb_thread)
for(unsigned long i = 1; i <= rang; ++i)
{
result[omp_get_thread_num()] += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1.);
}

for(double* I = result; I < result + nb_thread; ++I)
{
p += *I;
}

printf(“valeur approchée de pi au rang %ld : %.10f\n”, rang, p);
}[/code]

[code]$ export CFLAGS=’-std=c99 -O2 -fopenmp’
$ make pi1 pi2
$ time ./pi1
valeur approchée de pi au rang 1000000000 : 3.9999999990

real 0m3.675s
user 0m6.944s
sys 0m0.000s
$ time ./pi2
valeur approchée de pi au rang 1000000000 : 3.1415926546

real 0m3.596s
user 0m6.928s
sys 0m0.016s[/code]

En premier j’ai pensé à un bug que j’aurais introduit quand j’ai légèrement modifié le code, mais le fait est que non. En plus si je supprime la ligne OpenMP dans pi1 le résultat redevient correct, c’est donc clairement un problème de synchronisation. Le plus bizarre c’est que dans ta version (pas dans la mienne) le résultat n’est correct que si la déclaration double p = 4 utilise un transtypage int -> double (si j’utilise double p = 4. le résultat est mauvais).
Bref y’a un truc vraiment pas clair qui me semble provenir d’OpenMP, mais comme je ne le connais pas je ne saurais pas dire d’où ça vient précisément. À vue de nez il semble avoir besoin d’une synchronisation explicite sur p (peut-être à rajouter dans la ligne #pragma omp ?).

Bon sinon si on ne tient pas compte de la correction du résultat, au niveau performance pure c’est kif-kif chez moi : pas plus de 150ms d’écart pour 10¹⁰ itérations sur 35.3 secondes au total. Mais bien entendu si on rajoute de la synchro à pi1 ses perfs vont chuter.

Dernière remarque : sur un système mono-CPU multi-core le code de pi2 marche bien tel qu’il est car les différents cores partagent le même cache (L1 et/ou L2 je sais jamais).
Par contre sur un système réellement multi-CPU il va y avoir énormément de cache-trashing (et donc une terrible perte de performance) car (sauf hasard) les variables modifiées dans les différents threads sont trop proches les unes des autres dans la mémoire (même ligne de cache). Pour résoudre ce souci il faut ajouter assez de padding pour que les différents éléments du tableau soient certains de se trouver sur des lignes de cache différentes (padding dépendant du CPU).

Edit : je crois qu’on s’est un peu éloignés de la question d’origine là… :icon-lol:
Incorrigibles j’vous dis !

#24

J’ai pas ce problème. Je pense que c’est due à l’enfer de la manipulation des nombres flotants. Sinon tente peut être avec p déclaré comme volatile (mais ça va impacter les perf).

Pour ce qui est du cache c’est un domaine que je connais mal. Je ne sais pas exemple pas ce qui différencie :

de

int a; int b;
par rapport au cache.

#25

Aucune différence, ni au niveau du résultat (toujours 3.9999…) ni au niveau des perfs.

[quote=“MisterFreez”]Pour ce qui est du cache c’est un domaine que je connais mal. Je ne sais pas exemple pas ce qui différencie :

de

int a; int b;
par rapport au cache.[/quote]
Rien, dans les deux cas les variables sont contiguës en mémoire donc très probablement sur la même ligne de cache.
Pour faire une différence au niveau du cache il faudrait insérer artificiellement du padding :

int a; char cache_padding[...dépendant du CPU...]; // y'a quand même un problème si l'optimiseur détecte que c'est inutilisé et le vire int b;
Ou, pour pouvoir l’utiliser en tableau :

struct padded_int { int value; char cache_padding[...]; // là l'optimiseur n'a pas le choix, il *doit* respecter la structure }; struct padded_int result[2];

#26

Ok, OpenMP a une syntaxe particulière pour les accumulations de ce type (toutes les réductions en fait, voir par exemple ici : software.intel.com/en-us/article … th-openmp/ dans la section “Reductions”) :

[code]#include <stdio.h>
#include <omp.h>

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
double p = 4.;
unsigned long rang = 1000000000;

#pragma omp parallel for reduction(+:p)
for(unsigned long i = 1; i <= rang; ++i)
{
p += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1.);
}

printf(“valeur approchée de pi au rang %ld : %.10f\n”, rang, p);
}[/code]
Du coup le résultat est correct, mais malheureusement mon exemple à 10¹⁰ itérations passe de 35 à 40 secondes.

Edit : la perte de perfs semble due au nombre de threads utilisés : quand je spécifie 3 threads dans le programme pi2 j’obtiens des résultats équivalents (+5 secondes par rapport à 2 threads).

#27

Merci pour l’apprentissage. Tu vois ce que j’aime bien avec OpenMP c’est que pour un multitâche simple il se met en place très facilement.
Dans le cas présent sur mon Athlon II X3, j’ai des résultats qui vont de 7.3s à 2.5 en fonction du nombre de threads que je lui demande. Le tout ne demande que 2 lignes en plus dans le programme.

Je trouve le concept génial, même si je n’ai pas eu beaucoup d’occasion de m’en servir ni de potasser comme il faut la doc.

#28

C’est vrai que sa simplicité d’utilisation le rend particulièrement sympa.
J’ai plutôt l’habitude de gérer le multithreading à la main, ce qui est (forcément) énormément plus lourd à mettre en place et à cause de ça j’utilise beaucoup moins le multithread que je ne pourrais (pour les boucles de calcul du moins). :blush:
En fait la plupart du temps j’utilise un modèle “pipeline” qui a l’avantage de simplifier énormément l’implémentation et de se débarrasser de la plupart des problèmes de synchronisation (deadlocks etc). Bref, on fait comme on peut avec ce qu’on connaît… :smiley:

#29

Ça dépend de ton programme tout ne se prête pas à un pipeline/bus.

Personnellement j’ai utilisé OpenMP sur un projet où l’on devait faire des calculs de descripteur des images (en sortir des vecteurs) puis calculer les distance entre toutes. Là c’est d’une puissance, puisque tu as une boucle qui lis les images et calcule le descripteur qui est facilement parallélisable, puis 2 boucles imbriquées qui vont faire les calculs de distances et là aussi comme on ne calcul pas 2 fois la même distance il n’y a pas de synchronisation à faire. Dans ce cas là OpenMP m’a permis de gagner un facteur 2 à 3 très facilement (alors que gérer ça à la main, ça prend énormément de temps, le code est plus complexe donc moins fiable et moins maintenable).

Ensuite je sais qu’au CEA ils le combinent avec MPI pour envoyer les calculs sur un cluster, ils semble que ça s’associe plutôt bien (MPI permet de faire discuter les machines entre elles).

PS : Oui j’aime dire du bien des bibliothèques qui déchirent (comme pour boost et pour eigen). :smiley: