La division d'un programme en 4 threads est plus lente qu'un seul thread

https://stackoverflow.com/questions/8980056

12-11-2019
|

Question

J'ai écrit un Raytracer la semaine dernière et je suis arrivé à un point où il fait assez pour que le multi-threading ait du sens. J'ai essayé d'utiliser OpenMP pour le paralléliser, mais l'exécuter avec plus de threads est en fait plus lent que l'exécuter avec un.

En lisant d'autres questions similaires, en particulier sur OpenMP, une suggestion était que GCC optimise mieux le code série. Cependant, exécuter le code compilé ci-dessous avec export OMP_NUM_THREADS=1 est deux fois plus rapide qu'avec export OMP_NUM_THREADS=4. C'est-à-dire que c'est le même code compilé sur les deux exécutions.

Exécuter le programme avec time:

> export OMP_NUM_THREADS=1; time ./raytracer
real    0m34.344s
user    0m34.310s
sys     0m0.008s


> export OMP_NUM_THREADS=4; time ./raytracer
real    0m53.189s
user    0m20.677s
sys     0m0.096s

Le temps de l'utilisateur est beaucoup plus petit que réel, ce qui est inhabituel lors de l'utilisation de plusieurs noyaux utilisateur devrait être plus grand que réel Comme plusieurs cœurs fonctionnent en même temps.

Code que j'ai parallélisé à l'aide d'OpenMP

void Raytracer::render( Camera& cam ) {

    // let the camera know to use this raytracer for probing the scene
    cam.setSamplingFunc(getSamplingFunction());

    int i, j;

    #pragma omp parallel private(i, j)
    {

        // Construct a ray for each pixel.
        #pragma omp for schedule(dynamic, 4)
        for (i = 0; i < cam.height(); ++i) {
            for (j = 0; j < cam.width(); ++j) {
                cam.computePixel(i, j);
            }
        }
    }
}

Lors de la lecture cette question Je pensais avoir trouvé ma réponse. Il parle de la mise en œuvre de Gclib Rand () Synchroniser les appels à lui-même pour préserver l'état pour la génération de nombres aléatoires entre les threads. J'utilise beaucoup Rand () pour l'échantillonnage de Monte Carlo, donc j'ai pensé que c'était le problème. Je me suis débarrassé des appels à Rand, en les remplaçant par une seule valeur, mais l'utilisation de plusieurs threads est encore plus lente. Edit: oups Il s'avère que je n'ai pas testé cela correctement, c'était les valeurs aléatoires!

Maintenant que ceux-ci sont à l'écart, je vais discuter d'un aperçu de ce qui est fait à chaque appel à computePixel, j'espère qu'une solution peut être trouvée.

Dans mon Raytracer, j'ai essentiellement un arbre de scène, avec tous les objets. Cet arbre est beaucoup traversé pendant computePixel Cependant, lorsque les objets sont testés pour l'intersection, aucune écriture n'est effectuée à cet arbre ou à aucun objet. computePixel Lit essentiellement sur la scène un tas de fois, appelant des méthodes sur les objets (qui sont tous des méthodes const), et à la fin écrit une seule valeur à son propre tableau de pixels. C'est la seule partie que je sache où plus d'un thread essaiera d'écrire dans la même variable de membre. Il n'y a aucune synchronisation nulle part, car il n'y a pas deux threads à écrire sur la même cellule dans le réseau de pixels.

Quelqu'un peut-il suggérer des endroits où il pourrait y avoir une sorte de discorde? Des choses à essayer?

Merci en avance.

ÉDITER:Désolé, c'était stupide de ne pas fournir plus d'informations sur mon système.

Compiler GCC 4.6 (avec-o2 optimisation)
Ubuntu Linux 11.10
OpenMP 3
Intel i3-2310m Quad Core 2.1 GHz (sur mon ordinateur portable pour le moment)

Code de calcul Pixel:

class Camera {

    // constructors destructors
    private:
        // this is the array that is being written to, but not read from.
        Colour* _sensor; // allocated using new at construction.
}

void Camera::computePixel(int i, int j) const {

    Colour col;

    // simple code to construct appropriate ray for the pixel
    Ray3D ray(/* params */);
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col;
}

D'après les suggestions, ce pourrait être la traversée des arbres qui provoque le ralentissement. Quelques autres aspects: il y a beaucoup de récursives impliquées une fois que la fonction d'échantillonnage est appelée (rebond récursif des rayons) - cela pourrait-il causer ces problèmes?

La solution

Merci à tous pour les suggestions, mais après le profilage supplémentaire et se débarrasser des autres facteurs contributifs, génération de numéros aléatoires a fait se révèlent être le coupable.

Comme indiqué dans la question ci-dessus, Rand () doit suivre son état d'un appel à l'autre. Si plusieurs threads tentent de modifier cet état, cela entraînerait une condition de course, donc l'implémentation par défaut dans GLIBC est de Verrouiller à chaque appel, pour faire la fonction filiale. C'est terrible pour la performance.

Malheureusement, les solutions à ce problème que j'ai vues sur Stackoverflow sont toutes locales, c'est-à-dire avec le problème Dans la portée où Rand () est appelé. Au lieu de cela, je propose une solution "rapide et sale" que n'importe qui peut utiliser dans son programme pour implémenter une génération de nombres aléatoires indépendants pour chaque thread, ne nécessitant aucune synchronisation.

J'ai testé le code, et cela fonctionne - il n'y a pas de verrouillage et pas de ralentissement notable à la suite d'appels vers ThreadRand. N'hésitez pas à souligner toutes les erreurs flagrantes.

threadrand.h

#ifndef _THREAD_RAND_H_
#define _THREAD_RAND_H_

// max number of thread states to store
const int maxThreadNum = 100;

void init_threadrand();

// requires openmp, for thread number
int threadrand();

#endif // _THREAD_RAND_H_

threadrand.cpp

#include "threadrand.h"
#include <cstdlib>
#include <boost/scoped_ptr.hpp>
#include <omp.h>

// can be replaced with array of ordinary pointers, but need to
// explicitly delete previous pointer allocations, and do null checks.
//
// Importantly, the double indirection tries to avoid putting all the
// thread states on the same cache line, which would cause cache invalidations
// to occur on other cores every time rand_r would modify the state.
// (i.e. false sharing)
// A better implementation would be to store each state in a structure
// that is the size of a cache line
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum];

// reinitialize the array of thread state pointers, with random
// seed values.
void init_threadrand() {
    for (int i = 0; i < maxThreadNum; ++i) {
        randThreadStates[i].reset(new unsigned int(std::rand()));
    }
}

// requires openmp, for thread number, to index into array of states.
int threadrand() {
    int i = omp_get_thread_num();
    return rand_r(randThreadStates[i].get());
}

Vous pouvez maintenant initialiser les états aléatoires pour les fils de main utilisant init_threadrand(), puis obtenez un nombre aléatoire en utilisant threadrand() Lorsque vous utilisez plusieurs threads dans OpenMP.

Autres conseils

La réponse est, sans savoir sur quelle machine vous exécutez ceci, et sans vraiment voir le code de votre computePixel fonction, cela dépend.

Il y a pas mal de facteurs qui pourraient affecter les performances de votre code, une chose qui me vient à l'esprit est l'alignement du cache. Peut-être que vos structures de données, et vous avez mentionné un arbre, ne sont pas vraiment idéaux pour la mise en cache, et le CPU finit par attendre que les données proviennent du RAM, car elles ne peuvent pas intégrer les choses dans le cache. Les mauvais alignements de la ligne de cache pourraient provoquer quelque chose comme ça. Si le processeur doit attendre que les choses viennent de RAM, il est probable que le fil sera répandu de contexte et un autre sera exécuté.

Votre planificateur de threads OS est non déterministe, par conséquent, lorsque Un fil qui s'exécutera n'est pas une chose prévisible, donc s'il se produit que vos fils ne fonctionnent pas beaucoup ou ne se disputent pas pour les noyaux de processeur, cela pourrait également ralentir les choses.

Thread Affinity, joue également un rôle. Un fil sera planifié sur un noyau particulier, et normalement Il sera tenté de garder ce fil sur le même cœur. Si plus l'un de vos fils fonctionne sur un seul noyau, ils devront partager le même noyau. Une autre raison pour laquelle les choses pourraient ralentir. Pour des raisons de performances, une fois qu'un fil particulier a fonctionné sur un noyau, il est normalement gardé là, à moins qu'il n'y ait une bonne raison de l'échanger dans un autre noyau.

Il y a d'autres facteurs, dont je ne me souviens pas du haut de ma tête, cependant, je suggère de faire une lecture sur le filetage. C'est un sujet compliqué et étendu. Il y a beaucoup de matériel là-bas.

Les données sont-elles écrites à la fin, les données que d'autres threads doivent être capables de faire computePixel ?

Une forte possibilité est Faux partage. Il semble que vous calculiez les pixels en séquence, donc chaque thread peut fonctionner sur des pixels entrelacés. C'est généralement une très mauvaise chose à faire.

Ce qui pourrait se passer, c'est que chaque fil essaie d'écrire la valeur d'un pixel à côté d'un écrit dans un autre thread (ils écrivent tous sur le tableau des capteurs). Si ces deux valeurs de sortie partagent la même ligne de cache CPU, cela oblige le CPU à rincer le cache entre les processeurs. Il en résulte une quantité excessive de rinçage entre les CPU, ce qui est une opération relativement lente.

Pour résoudre ce problème, vous devez vous assurer que chaque fil fonctionne vraiment sur une région indépendante. En ce moment, il semble que vous vous divisez sur les lignes (je ne suis pas positif puisque je ne connais pas OMP). Le fait que cela fonctionne dépend de la taille de vos lignes - mais la fin de chaque ligne se chevauchera avec le début de la suivante (en termes de lignes de cache). Vous voudrez peut-être essayer de diviser l'image en quatre blocs et faire fonctionner chaque fil sur une série de lignes séquentielles (pour le 1..10 11..20 21..30 31..40). Cela réduirait considérablement le partage.

Ne vous inquiétez pas de lire des données constantes. Tant que le bloc de données n'est pas modifié, chaque thread peut lire efficacement ces informations. Cependant, soyez méfiant de toutes les données mutables que vous avez dans vos données constantes.

J'ai juste regardé et le Intel i3-2310m N'a pas réellement 4 cœurs, il a 2 cœurs et hyper-threading. Essayez d'exécuter votre code avec seulement 2 threads et voyez-le qui aide. Je trouve que l'hyper-threading général est totalement inutile lorsque vous avez beaucoup de calculs, et sur mon ordinateur portable, je l'ai éteint et j'ai obtenu de bien meilleurs temps de compilation de mes projets.

En fait, allez simplement dans votre BIOS et désactivez HT - il n'est pas utile pour les machines de développement / calcul.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow