Qu'est-ce qui peut ralentir un programme lorsqu'il utilise plus de threads?

Question

Cette question concerne le même programme que je déjà demandé à propos de . Pour récapituler, j'ai un programme avec une structure de boucle comme celle-ci:

for (int i1 = 0; i1 < N; i1++)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        histogram[bin_index(i1, i2, i3, i4)] += 1;

bin_index est une fonction complètement déterministe de ses arguments qui, aux fins de cette question, n'utilise ni ne modifie aucun état partagé - en d'autres termes, il est manifestement réentrant.

J'ai d'abord écrit ce programme pour utiliser un seul thread. Ensuite, je l'ai converti pour utiliser plusieurs threads, de telle sorte que le thread n exécute toutes les itérations de la boucle externe où i1% nthreads == n . Donc, la fonction qui s'exécute dans chaque fil ressemble à

for (int i1 = n; i1 < N; i1 += nthreads)
  for (int i2 = 0; i2 < N; i2++)
    for (int i3 = 0; i3 < N; i3++)
      for (int i4 = 0; i4 < N; i4++)
        thread_local_histogram[bin_index(i1, i2, i3, i4)] += 1;

et tous les histogrammes_local_local sont ajoutés dans le thread principal à la fin.

Voici l'étrange chose: lorsque je lance le programme avec un seul thread pour une taille de calcul particulière, cela prend environ 6 secondes. Quand je le lance avec 2 ou 3 threads, en faisant exactement le même calcul, cela prend environ 9 secondes. Pourquoi donc? Je m'attendrais à ce que l'utilisation de 2 threads soit plus rapide que 1 thread puisque j'ai un processeur dual-core. Le programme n’utilise pas de mutex ni d’autres primitives de synchronisation. Par conséquent, deux threads doivent pouvoir fonctionner en parallèle.

Pour référence: sortie typique de heure (sous Linux) pour un thread:

.

real    0m5.968s
user    0m5.856s
sys     0m0.064s

et deux threads:

real    0m9.128s
user    0m10.129s
sys     0m6.576s

Le code se trouve à l'adresse http://static.ellipsix.net/ext-tmp. /distintegral.ccs

P.S. Je sais qu'il existe des bibliothèques spécialement conçues pour ce genre de choses, qui pourraient probablement offrir de meilleures performances, mais c'est de cela que parlait ma dernière question. Je n'ai donc plus besoin d'entendre ces suggestions. (De plus, je voulais utiliser les pthreads comme expérience d'apprentissage.)

Answer 1

Tout ce que j'ai dit jusqu'à présent dans mon autre réponse est toujours valable, car votre question visait à savoir ce que vous pouvez "...", mais maintenant que j'ai vu votre code réel, mon premier pari serait que votre utilisation de la fonction random () ralentit tout. Pourquoi?

Voir, random conserve une variable globale en mémoire qui stocke la dernière valeur aléatoire calculée ici. Chaque fois que vous appelez random () (et que vous l’appelez deux fois dans une même fonction), il lit la valeur de cette variable globale, effectue un calcul (ce n’est pas si rapide; random () est à lui seul une fonction lente) et écrit le retourne là-bas avant de le retourner. Cette variable globale n'est pas par thread, elle est partagée par tous les threads. Donc ce que j’ai écrit concernant l’empoisonnement du cache s’applique ici tout le temps (même si vous l’évitiez pour le tableau en ayant des tableaux séparés par thread; c’était très intelligent de votre part!). Cette valeur est constamment invalidée dans le cache de l'un des noyaux et doit être extraite de la mémoire. Cependant, si vous n'avez qu'un seul thread, rien de tel ne se produit, cette variable ne quitte jamais le cache après sa lecture initiale, car on y accède en permanence, encore et encore.

Pour aggraver encore les choses, glibc propose une version thread-safe de random () - je viens de vérifier cela en regardant le code source. Bien que cela semble être une bonne idée dans la pratique, cela signifie que chaque appel à random () provoquera le verrouillage d'un mutex, l'accès à la mémoire et le déverrouillage d'un mutex. Ainsi, deux threads appelant de manière aléatoire au même moment provoquent le blocage d’un thread pendant deux cycles de la CPU. Ceci est spécifique à l'implémentation, cependant, comme AFAIK, il n'est pas nécessaire que random () soit thread-safe. La plupart des fonctions standard de lib ne sont pas obligées d'être thread-safe, car le standard C ne connaît même pas le concept de thread. Quand ils ne l'appellent pas au même moment, le mutex n'aura aucune influence sur la vitesse (même une seule application filetée doit verrouiller / déverrouiller le mutex), mais l'empoisonnement du cache s'appliquera à nouveau.

Vous pouvez pré-construire un tableau avec des nombres aléatoires pour chaque thread, contenant autant de nombres aléatoires que nécessaire. Créez-le dans le thread principal avant de créer les threads et ajoutez-y une référence au pointeur de structure que vous remettez à chaque thread. Ensuite, obtenez les nombres aléatoires à partir de là.

Ou implémentez simplement votre propre générateur de nombres aléatoires si vous n'avez pas besoin du "meilleur" des nombres aléatoires sur la planète, qui fonctionnent avec une mémoire par thread pour conserver son état - celui-ci pourrait même être plus rapide que le générateur intégré du système.

Si une solution uniquement Linux fonctionne pour vous, vous pouvez utiliser random_r . Il vous permet de transmettre l'état à chaque appel. Utilisez simplement un objet d'état unique par thread. Cependant, cette fonction est une extension de glibc, elle n’est probablement pas prise en charge par d’autres plates-formes (ni partie des normes C ni des normes POSIX AFAIK - cette fonction n’existe pas sous Mac OS X par exemple, elle ne peut pas non plus exister sous Solaris ou FreeBSD).

Créer un propre générateur de nombres aléatoires n’est en réalité pas si difficile. Si vous avez besoin de vrais nombres aléatoires, vous ne devriez pas utiliser random () en premier lieu. Aléatoire ne crée que des nombres pseudo-aléatoires (des nombres qui paraissent aléatoires, mais prévisibles si vous connaissez l'état interne du générateur). Voici le code de celui qui produit de bons nombres aléatoires uint32:

static uint32_t getRandom(uint32_t * m_z, uint32_t * m_w)
{
    *m_z = 36969 * (*m_z & 65535) + (*m_z >> 16);
    *m_w = 18000 * (*m_w & 65535) + (*m_w >> 16);
    return (*m_z << 16) + *m_w;
}

Il est important de "semer" m_z et m_w d’une manière ou d’une autre, sinon les résultats ne sont pas aléatoires. La valeur de départ elle-même devrait déjà être aléatoire, mais vous pouvez utiliser ici le générateur de nombres aléatoires du système.

uint32_t m_z = random();
uint32_t m_w = random();
uint32_t nextRandom;

for (...) {
    nextRandom = getRandom(&m_z, &m_w);
    // ...
}

De cette façon, chaque thread n'a besoin d'appeler que random () deux fois, puis utilise votre propre générateur. Par ailleurs, si vous avez besoin de doubles randos (compris entre 0 et 1), la fonction ci-dessus peut être facilement encapsulée pour cela:

static double getRandomDouble(uint32_t * m_z, uint32_t * m_w)
{
    // The magic number below is 1/(2^32 + 2).
    // The result is strictly between 0 and 1.
    return (getRandom(m_z, m_w) + 1) * 2.328306435454494e-10;
}

Essayez d’apporter cette modification à votre code et laissez-moi savoir comment se présentent les résultats du test: -)

Answer 2

Pour éviter d’autres commentaires à ce sujet: lorsque j’ai écrit ma réponse, l’interlocuteur n’a pas encore posté de lien vers sa source. Je ne pouvais donc pas adapter ma réponse à ses problèmes spécifiques. Je ne faisais que répondre à la question générale de ce que "peut". cause un tel problème, je n’ai jamais dit que cela s’appliquerait nécessairement à son cas. Lorsqu’il a posté un lien vers sa source, j’ai écrit une autre réponse, celle-ci se concentrant uniquement sur son problème même (qui est causé par l’utilisation de la fonction random (), comme je l’ai expliqué dans mon autre réponse). Cependant, étant donné que la question de ce message reste "Qu'est-ce qui peut ralentir un programme lorsqu'il utilise plus de threads?" et non "Qu'est-ce qui ralentit mon application très spécifique?", je n'ai pas non plus eu besoin de modifier ma réponse plutôt générale (question générale - > réponse générale, question spécifique - & réponse spécifique).

1) Empoisonnement de la mémoire cache
Tous les threads accèdent au même tableau, qui est un bloc de mémoire. Chaque cœur a son propre cache pour accélérer l’accès à la mémoire. Comme ils ne se contentent pas de lire dans le tableau, mais modifient également le contenu, le contenu est modifié dans le cache uniquement, pas dans la mémoire réelle (du moins, pas immédiatement). Le problème est que l’autre thread sur l’autre cœur peut avoir des parties de la mémoire en cache qui se chevauchent. Si maintenant le noyau 1 change la valeur dans le cache, il doit dire au noyau 2 que cette valeur vient de changer. Pour ce faire, le contenu du cache sur le noyau 2 et le noyau 2 doivent être invalidés pour relire les données de la mémoire, ce qui ralentit le traitement. L'empoisonnement du cache ne peut se produire que sur des machines multi-cœurs ou multi-processeurs. Si vous avez juste un processeur avec un noyau, ce n'est pas un problème. Donc, pour savoir s’il s’agit ou non de votre problème, il suffit de désactiver un cœur (la plupart des systèmes d’exploitation vous le permettent) et de répéter le test. Si c'est maintenant presque aussi rapide, c'était votre problème.

2) Prévention des rafales de mémoire
La mémoire est lue plus rapidement si elle est lue séquentiellement en rafales, comme lorsque les fichiers sont lus à partir de la HD. L'adressage d'un certain point de la mémoire est en fait terriblement lent (tout comme le "temps de recherche" sur un disque dur), même si votre PC dispose de la meilleure mémoire disponible sur le marché. Cependant, une fois ce point résolu, les lectures séquentielles sont rapides. Le premier adressage consiste à envoyer un index de ligne et un index de colonne, ainsi que des temps d’attente entre les deux avant que les premières données ne puissent être consultées. Une fois que ces données sont là, la CPU commence à éclater. Alors que les données sont toujours en cours, il envoie déjà la demande pour la prochaine rafale. Tant qu'il maintient la rafale (en envoyant toujours des requêtes "Ligne suivante, s'il vous plaît"), la RAM continuera à extraire les données aussi vite que possible (et c'est en fait assez rapide!). La mise en rafale ne fonctionne que si les données sont lues de manière séquentielle et uniquement si les adresses de la mémoire augmentent (AFAIK: vous ne pouvez pas transmettre en rafale des adresses haute à basse). Si maintenant deux threads fonctionnent en même temps et que les deux continuent à lire / écrire de la mémoire, mais à partir d'adresses de mémoire complètement différentes, chaque fois que le thread 2 doit lire / écrire des données, il doit interrompre une éventuelle rafale de thread 1 et inversement . Ce problème s'aggrave si vous avez encore plus de threads et qu'il s'agit également d'un problème sur un système ne disposant que d'un seul processeur.

Si vous exécutez plus de threads que de cœurs, votre processus ne sera jamais plus rapide (comme vous avez mentionné 3 threads), il le ralentira plutôt (les commutateurs de contexte de thread ont des effets secondaires qui réduisent le débit de traitement) - ce qui est différent de votre exécution. plusieurs threads, car certains threads sont en veille ou bloquent certains événements et ne peuvent donc traiter activement aucune donnée. Dans ce cas, il peut être judicieux d’exécuter plus de threads que de cœurs.

Answer 3

Vous observez le rebond de la ligne de cache . Je suis vraiment surpris que vous n'ayez pas de mauvais résultats, en raison des conditions de compétition sur les compartiments de l'histogramme.

Answer 4

Une possibilité est que le temps nécessaire à la création des threads dépasse les économies réalisées en utilisant des threads. Je pense que N n’est pas très grand, si le temps écoulé n’est que de 6 secondes pour une opération O (n ^ 4).

Rien ne garantit non plus que plusieurs threads fonctionneront sur différents cœurs ou processeurs. Je ne sais pas quelle est l'affinité de thread par défaut avec Linux - peut-être que les deux threads s'exécutent sur un seul cœur, ce qui annulerait les avantages d'un morceau de code gourmand en ressources, tel que celui-ci. / p>

Cet article détaille l'affinité de fil par défaut et la procédure à suivre. modifiez votre code pour vous assurer que les threads fonctionnent sur des cœurs spécifiques.

Answer 5

Même si les threads n'accèdent pas aux mêmes éléments du tableau en même temps, tout le tableau peut se trouver dans quelques pages de mémoire. Lorsqu'un cœur / processeur écrit sur cette page, il doit invalider son cache pour tous les autres processeurs.

Évitez de faire fonctionner plusieurs threads sur le même espace mémoire. Attribuez des données distinctes à chaque thread sur lequel travailler, puis réunissez-les à la fin du calcul.

Answer 6

De mémoire:

• Changements de contexte
• Conflit de ressources
• Conflits de processeurs (s'ils ne sont pas divisés en plusieurs processeurs).
• Cache du cache

Answer 7

David,

Êtes-vous sûr d’exécuter un noyau prenant en charge plusieurs processeurs? Si un seul processeur est utilisé dans votre système, la création de threads supplémentaires gourmands en ressources processeur ralentira votre programme.

Et, êtes-vous certain que la prise en charge des threads de votre système utilise plusieurs processeurs? Par exemple, top indique-t-il que les deux cœurs de votre processeur ont été utilisés lors de l’exécution de votre programme?