Diviser le travail en plusieurs threads prend plus de temps, pourquoi?

J’ai un petit programme en C qui calcule pi en utilisant une simulation de monte-carlo qui, fondamentalement, teste simplement un point aléatoire [x, y] s’il se trouve à l’intérieur ou à l’extérieur d’un cercle.

Pour approcher pi, je dois utiliser un grand nombre d’échantillons n qui ont une complexité proportionnelle directe de O (n) . Alors, essayant de calculer un très grand nombre d’échantillons n, j’ai implémenté les threads POSIX api pour mettre en parallèle la puissance de calcul.

Mon code ressemble à ceci:

pthread_t worker[nthreads]; /* creates workers for each thread */ struct param aparam[nthreads]; /* struct param{ long* hits; long rounds; }; */ long nrounds = nsamples / nthreads; /* divide samples to subsets of equal rounds per thread */ for (int i = 0; i < nthreads; ++i) { /* loop to create threads */ aparam[i].hits = 0; aparam[i].rounds = nrounds; pthread_create(&worker[i], NULL, calc_pi, &aparam[i]); /* calls calc_pi(void* vparam){} */ } long nhits = 0; for (int j = 0; j < nthreads; ++j) { /* collects results */ pthread_join(worker[j], NULL); nhits += (long)aparam[j].hits; /* counts hits inside the cicrle */ } 

Et voici ce que fait chaque thread:

 void* calc_pi(void* vparam) { /* counts hits inside a circle */ struct param *iparam; iparam = (struct param *) vparam; long hits = 0; float x, y, z; for (long i = 0; i rounds; ++i) { x = (float)rand()/RAND_MAX; y = (float)rand()/RAND_MAX; z = x * x + y * y; if (z hits = (long*)hits; return NULL; } 

Maintenant, j’ai une observation étrange. Avec le même ensemble d’échantillons n et un nombre croissant de threads i, ce programme prend plus de temps que de moins .

Voici quelques temps d’exécution moyens (reproductibles):

 ------------------------------------------------- | Threads[1] | Samples[1] | Rounds[1] | Time[s] | ------------------------------------------------- | 32 | 268435456 | 8388608 | 118 | | 16 | 268435456 | 16777216 | 106 | | 8 | 268435456 | 33554432 | 125 | | 4 | 268435456 | 67108864 | 152 | | 2 | 268435456 | 134217728 | 36 | | 1 | 268435456 | 268435456 | 15 | ------------------------------------------------- 

Pourquoi, par exemple, deux threads effectuant le même travail prennent plus du double de temps qu’un seul thread? Mon hypothèse est que deux tâches divisant le travail devraient réduire le temps d’au moins 50%.

Compilé avec GCC 4.9.1 et les drapeaux suivants:

 gcc -O2 -std=gnu11 -pthread pipa.c -lpthread -o pipa 

Mon matériel est un processeur double Intel Xeon E5520 (2 processeurs avec 4 cœurs) @ 2,26 GHz, hyperthreading désactivé, exécutant Linux scientifique avec un kernel 2.6.18.

Des idées?

L’opération la plus chère que votre thread effectue consiste à appeler rand() . La fonction rand() est une fonction évolutive naïve, simpliste et généralement non MT (car elle garantit que la même graine produira la même séquence de nombres aléatoires ). Je pense que le verrou à l’intérieur de rand() est en train de sérialiser tous les threads. (*)

Une astuce simple pour confirmer si le problème existe ou non est de démarrer le programme sous le débogueur, puis plusieurs fois: mettez-le en pause, capturez la trace de stack des threads, continuez. Ce qui apparaît le plus souvent dans les stacktraces est très probablement le goulot d’étranglement.

(*) Ce qui le ralentit encore plus, c’est le fait que le conflit de locking entraîne une pénalité de performance supplémentaire. En outre, les nombreux threads ajoutent un temps système supplémentaire à la planification des processus et aux commutateurs de contexte.