parallèle, mais plus lent

Question

J'utilise la méthode monte carlo pour calculer pi et faire une expérience de base avec la programmation parallèle et OpenMP

le problème est que lorsque j'utilise 1 fil, x itérations, court toujours plus vite que les fils n , x itérations. Quelqu'un peut-il me dire pourquoi?

Par exemple, le code fonctionne comme celui-ci "a.out 1 1000000", où 1 est fils et 1000000 les itérations

include <omp.h> 
include <stdio.h> 
include <stdlib.h> 
include <iostream> 
include <iomanip> 
include <math.h> 

using namespace std; 

int main (int argc, char *argv[]) { 

double arrow_area_circle, pi; 
float xp, yp; 
int i, n; 
double pitg= atan(1.0)*4.0; //for pi error 
cout << "Number processors: " << omp_get_num_procs() << endl; 

//Number of divisions 
iterarions=atoi(argv[2]); 
arrow_area_circle = 0.0; 

#pragma omp parallel num_threads(atoi(argv[1])) 
{ 
srandom(omp_get_thread_num()); 

#pragma omp for private(xp, yp) reduction(+:arrow_area_circle) //*,/,-,+ 
for (i = 0; i < iterarions; i++) { 
    xp=rand()/(float)RAND_MAX; 
    yp=rand()/(float)RAND_MAX; 

    if(pow(xp,2.0)+pow(yp,2.0)<=1) arrow_area_circle++; 
} 
} 

pi = 4*arrow_area_circle/iterarions; 
cout << setprecision(18) << "PI = " << pi << endl << endl; 
cout << setprecision(18) << "Erro = " << pitg-pi << endl << endl; 

return 0; 
} 

Answer 1

Changement de contexte.

Answer 2

Une tâche intensive en termes d'UC comme celle-ci sera plus lente si vous effectuez le travail dans plus de threads qu'il n'y en a dans le système. Si vous l'utilisez sur un seul système CPU, vous verrez certainement un ralentissement avec plus d'un thread. Cela est dû au fait que le système d'exploitation doit basculer entre les différents threads - c'est un surcoût pur. Vous devriez idéalement avoir le même nombre de threads que les cœurs pour une tâche comme celle-ci.

Un autre problème est que arrow_area_circle est partagé entre les threads. Si vous avez un thread s'exécutant sur chaque core, l'incrémentation de arrow_area_circle invalidera la copie dans les caches des autres cœurs, ce qui les obligera à se refaire. arrow_area_circle ++ qui devrait prendre quelques cycles prendra des dizaines ou des centaines de cycles. Essayez de créer un arrow_area_circle par thread et de les combiner à la fin.

EDIT: Joe Duffy vient de poster un blog entry sur le coût de partage des données entre les threads.

Answer 3

Il semble que vous utilisiez une sorte de compilateur auto-paralléliseur. Je vais supposer que vous avez plus d'un noyau/processeur dans votre système (car ce serait trop évident) et aucune hyperthreading sur un Pentium 4 ne compte pas comme ayant deux cœurs, indépendamment de ce que le marketing d'Intel voudrait vous faire croire .) Il y a deux problèmes que je vois. Le premier est trivial et sans doute pas votre problème:

1. Si la arrow_area_circle variable est partagée entre vos processus, l'acte d'exécution arrow_area_circle ++ entraînera une instruction de verrouillage à utiliser pour synchroniser la valeur d'une manière qui est sonique atomiquement. Vous devez incrémenter une variable "privée", puis ajouter cette valeur une seule fois à la fin de la variable commune arrow_area_circle au lieu d'incrémenter arrow_area_circle dans votre boucle interne.

2. La fonction rand() pour fonctionner correctement, doit s'exécuter en interne avec une section critique. La raison en est que son état interne/seed est une variable statique statique; si ce n'était pas le cas, il serait possible que deux processus différents obtiennent la même sortie de rand() avec une probabilité anormalement élevée, juste parce qu'ils appelaient rand() presque en même temps. Cela signifie que rand() s'exécute lentement, et surtout que plus de threads/processus l'appellent en même temps. Contrairement à la variable arrow_area_circle (qui a juste besoin d'un incrément atomique), une vraie section critique doit être invoquée par rand() car sa mise à jour d'état est plus compliquée. Pour contourner ce problème, vous devez obtenir le code source de votre propre générateur de nombres aléatoires et l'utiliser avec un code privé. Le code source de l'implémentation standard de rand() dans la plupart des compilateurs est largement disponible.

Je voudrais également souligner que vous utilisez la fonction pow (,) pour effectuer la même chose que x * x. Ce dernier est environ 300 fois plus rapide que le premier. Bien que ce point ne soit pas pertinent à la question que vous posez.:)

Answer 4

Juste pour souligner que vous devez faire très attention en utilisant des nombres aléatoires dans un réglage parallèle. En fait, vous devriez utiliser quelque chose comme SPRNG

Quoi que vous fassiez, assurez-vous que chaque thread n'utilise pas les mêmes nombres aléatoires.

Answer 5

La fonction rand() est bloquante. Cela signifie qu'il a une section critique à l'intérieur.