Intereting Posts

Comment obtenir la colonne d’un tableau multidimensionnel en C / C ++? Pourquoi l’opérateur de sortie est-il «os <> os»? Devrais-je utiliser () ou {} lors du transfert d’arguments? Envoi de “request payload” avec libcurl? Créer un boost :: shared_ptr à une variable existante enable_shared_from_this et l’inheritance Pourquoi la castration d’un signe euro dans un littéral de chaîne utilisant UTF8 ne produit-elle pas un UCN? Setbuf () affecte-t-il cout? GCC, ssortingngification et GLSL en ligne? Optimisation d’une twig pour un chemin plus commun connu éviter d’abort dans libgmp obtenir pour les variantes échouent sous clang ++ mais pas g ++ L’expression d’erreur C ++ ne peut pas être utilisée comme fonction Conversion de l’expression lambda en pointeur de fonction Comment puis-je convertir wssortingng en u16ssortingng?

Mauvaises performances dans les programmes C ++ multithreads

J’ai un programme C ++ fonctionnant sous Linux dans lequel un nouveau thread est créé pour effectuer un travail coûteux en calcul indépendant du thread principal (le travail de calcul se termine en écrivant les résultats dans des fichiers très volumineux). Cependant, mes performances sont relativement médiocres.

Si j’implémente directement le programme (sans introduire d’autres threads), la tâche est terminée en 2 heures environ. Avec le programme multi-thread, il faut environ 12 heures pour effectuer la même tâche (cela a été testé avec un seul thread généré).

J’ai essayé plusieurs choses, notamment pthread_setaffinity_np pour définir le thread sur un seul processeur (sur les 24 disponibles sur le serveur que j’utilise), ainsi que pthread_setschedparam pour définir la stratégie de planification (je n’ai essayé que SCHED_BATCH ). Mais les effets de ceux-ci ont été jusqu’à présent négligeables.

Existe-t-il des causes générales à ce type de problème?

EDIT: J’ai ajouté un exemple de code que j’utilise, qui est, espérons-le, le plus pertinent. La fonction process_job () est ce qui fait réellement le travail de calcul, mais ce serait trop pour l’inclure ici. Fondamentalement, il lit deux fichiers de données et les utilise pour effectuer des requêtes sur une firebase database de graphes en mémoire, dans laquelle les résultats sont écrits dans deux fichiers volumineux sur une période de quelques heures.

EDITER partie 2: Juste pour clarifier, le problème n’est pas que je veuille utiliser des threads pour augmenter les performances d’un algorithme que j’ai. Mais je veux plutôt exécuter plusieurs instances de mon algorithme simultanément. Par conséquent, je m’attends à ce que l’algorithme fonctionne à une vitesse similaire lorsqu’il est placé dans un fil de discussion s’il le faisait si je n’utilisais pas du tout des multi-threads.

EDIT part 3: Merci pour toutes les suggestions. Je suis en train de faire quelques tests unitaires (voir quelles pièces ralentissent) comme certains l’ont suggéré. Comme le programme prend un certain temps à charger et à exécuter, il prend du temps pour voir les résultats des tests et par conséquent je m’excuse pour les réponses tardives. Je pense que le point principal que je voulais clarifier est les raisons possibles pour lesquelles le threading peut ralentir un programme. D’après ce que je déduis des commentaires, cela ne devrait tout simplement pas être le cas. Je posterai quand je peux trouver une résolution raisonnable, merci encore.

(FINAL) EDIT part 4: Il s’avère que le problème n’était finalement pas lié au threading. Il serait trop compliqué de le décrire à ce stade (y compris l’utilisation des niveaux d’optimisation du compilateur), mais les idées présentées ici étaient très utiles et appréciées.

struct sched_param sched_param = { sched_get_priority_min(SCHED_BATCH) }; int set_thread_to_core(const long tid, const int &core_id) { cpu_set_t mask; CPU_ZERO(&mask); CPU_SET(core_id, &mask); return pthread_setaffinity_np(tid, sizeof(mask), &mask); } void *worker_thread(void *arg) { job_data *temp = (job_data *)arg; // get the information for the task passed in ... long tid = pthread_self(); int set_thread = set_thread_to_core(tid, slot_id); // assume slot_id is 1 (it is in the test case I run) sched_get_priority_min(SCHED_BATCH); pthread_setschedparam(tid, SCHED_BATCH, &sched_param); int success = process_job(...); // this is where all the work actually happens pthread_exit(NULL); } int main(int argc, char* argv[]) { ... pthread_t temp; pthread_create(&temp, NULL, worker_thread, (void *) &jobs[i]); // jobs is a vector of a class type containing information for the task ... return 0; }

Si vous avez beaucoup de cœurs de processeur et que vous avez beaucoup de travail à faire, son exécution en mode multithread ne devrait pas prendre plus de temps qu’en mode mono-thread – le temps de calcul réel peut être un peu plus long, mais le “temps d’horloge” plus court. Je suis à peu près sûr que votre code a une sorte de goulot d’étranglement où un thread bloque l’autre.

Ceci est dû à une ou plusieurs de ces choses – je vais d’abord les énumérer, puis entrer dans les détails ci-dessous:

Certains lockings dans un thread bloquent l’exécution du second thread.
Partage de données entre les threads (partage vrai ou “faux”)
Cache en cache.
Compétition pour certaines ressources externes provoquant des coups et / ou des blocages.
Code mal conçu en général …

Certains lockings dans un thread bloquent l’exécution du second thread.

Si un thread est verrouillé et qu’un autre thread souhaite utiliser la ressource verrouillée par ce thread, il devra attendre. Cela signifie évidemment que le fil ne fait rien d’utile. Les serrures doivent être réduites au minimum en ne les prenant que pendant une courte période. Utiliser un code pour identifier si des verrous retiennent votre code, tels que:

 while (!tryLock(some_some_lock)) { sortinged_locking_failed[lock_id][thread_id]++; } total_locks[some_lock]++;

L’impression de statistiques sur les verrous aiderait à identifier les points litigieux (ou vous pouvez essayer le vieux truc de “coupure de presse dans le débogueur et voir où vous en êtes”) si un thread attend constamment un verrou, c’est alors empêcher le progrès …

Partage de données entre les threads (partage vrai ou “faux”)

Si deux threads utilisent [et mettent fréquemment à jour la valeur de celle-ci] la même variable, ils devront échanger les messages “j’ai mis à jour”, et le processeur doit extraire les données de l’autre processeur avant de pouvoir continuer. avec son utilisation de la variable. Puisque “données” est partagé au niveau “par ligne de cache” et qu’une ligne de cache a généralement 32 octets, quelque chose comme:

 int var[NUM_THREADS]; ... var[thread_id]++;

classerait comme quelque chose appelée “faux partage” – les données ACTUAL mises à jour sont uniques par CPU, mais étant donné que les données se trouvent dans la même région de 32 octets, les cœurs auront toujours mis à jour les mêmes ressources en mémoire.

Cache en cache.

Si deux threads font beaucoup de lecture et d’écriture en mémoire, le cache de la CPU peut constamment jeter de bonnes données pour le remplir de données pour l’autre thread. Certaines techniques permettent de s’assurer que deux threads ne s’exécutent pas “en bloc” sur la partie de la mémoire cache utilisée par la CPU. Si les données sont 2 ^ n (puissance de deux) et assez volumineuses (un multiple de la taille du cache), il est conseillé d’append un décalage à chaque thread, par exemple 1 Ko ou 2 Ko. Ainsi, lorsque le deuxième thread lit la même distance dans la région de données, il n’écrasera pas exactement la même zone de cache que celle utilisée par le premier thread.

Compétition pour certaines ressources externes provoquant des coups et / ou des blocages.

Si deux threads lisent ou écrivent à partir du / sur le disque dur, la carte réseau ou une autre ressource partagée, cela peut conduire à un thread qui bloque un autre thread, ce qui entraîne une baisse des performances. Il est également possible que le code détecte différents threads et effectue un vidage supplémentaire pour s’assurer que les données sont écrites dans le bon ordre ou similaire, avant de commencer à travailler avec l’autre thread.

Il est également possible qu’il existe des verrous internes au code traitant de la ressource (bibliothèque en mode utilisateur ou pilotes en mode kernel) qui bloquent lorsque plusieurs threads utilisent la même ressource.

Conception généralement mauvaise

C’est un “fourre-tout” pour “beaucoup d’autres choses qui peuvent être fausses”. Si le résultat d’un calcul dans un thread est nécessaire pour faire avancer l’autre, il est évident que peu de travail peut être effectué dans ce thread.

Unité de travail trop petite, il faut donc passer tout le temps nécessaire pour démarrer et arrêter le fil de travail et ne pas effectuer suffisamment de travail. Disons par exemple que vous dissortingbuez de petits nombres pour “calculer s’il s’agit d’un nombre premier” à chaque fil, un nombre à la fois, il faudra probablement beaucoup plus de temps pour donner le nombre au fil que le calcul de “est-ce en fait, un nombre premier »- la solution consiste à atsortingbuer une série de nombres (peut-être 10, 20, 32, 64 ou plus) à chaque fil, puis de renvoyer le résultat du lot entier en une fois.

Il y a beaucoup d’autres “mauvais design”. Sans comprendre votre code, il est assez difficile de dire avec certitude.

Il est tout à fait possible que votre problème ne soit aucun de ceux que j’ai mentionnés ici, mais il est fort probable que ce soit l’un d’entre eux. Espérons que cette réponse sera utile pour identifier la cause.

Lisez les caches de processeur et pourquoi vous vous souciez de comprendre pourquoi le port naïf d’un algorithme d’un thread à plusieurs threads entraînera le plus souvent une réduction considérable des performances et une évolutivité négative. Les algorithmes spécialement conçus pour le parallélisme prennent en charge les opérations de locking hyperactives, le partage erroné et les autres causes de pollution par le cache.

Voici quelques points à examiner.

1 °) Entrez-vous une section critique (verrous, sémaphores, etc.) entre votre thread ouvrier et votre thread principal? (Cela devrait être le cas si vos requêtes modifient le graphique). Si tel est le cas, cela pourrait être l’une des sources de la surcharge multithreading: les threads en compétition pour un verrou dégradent généralement les performances.

2 °) Vous utilisez une machine à 24 cœurs, ce qui, je suppose, serait NUMA (access non uniforme à la mémoire). Étant donné que vous définissez les affinités des threads lors de vos tests, vous devez être particulièrement attentif à la topologie de la mémoire de votre matériel. L’examen des fichiers dans / sys / devices / system / cpu / cpuX / peut vous aider (attention, cpu0 et cpu1 ne sont pas nécessairement proches et ne partagent donc pas nécessairement de la mémoire). Les threads utilisant beaucoup de mémoire doivent utiliser la mémoire locale (allouée dans le même nœud NUMA que le kernel sur lequel ils s’exécutent).

3 °) Vous utilisez beaucoup d’E / S de disque. Quel genre de I / O est-ce? Si chaque thread exécute chaque fois une E / S synchrone, vous pouvez envisager des appels système asynchrones afin que le système d’exploitation rest responsable de la planification de ces demandes sur le disque.

4 °) Certains problèmes de caches ont déjà été mentionnés dans d’autres réponses. Par expérience, un faux partage peut nuire aux performances autant que vous l’observez. Ma dernière recommandation (qui aurait dû être la première) consiste à utiliser un outil de profilage, tel que Linux Perf ou OProfile. Avec une telle dégradation des performances que vous rencontrez, la cause apparaîtra clairement.

Les autres réponses ont toutes abordé les directives générales pouvant causer vos symptômes. Je vais donner ma propre version, espérons-le, pas excessivement redondante. Ensuite, je parlerai un peu de la manière dont vous pouvez aller au fond du problème en gardant à l’esprit tout ce qui a été discuté.

En général, il y a plusieurs raisons pour lesquelles vous vous attendez à ce que plusieurs threads fonctionnent mieux:

Un travail dépend de certaines ressources (disque, mémoire, cache, etc.), tandis que d’autres peuvent continuer indépendamment de ces ressources ou de ladite charge de travail.
Vous avez plusieurs cœurs de processeur capables de traiter votre charge de travail en parallèle.

Les principales raisons, énumérées ci-dessus, de vous attendre à ce que plusieurs threads fonctionnent moins bien sont toutes basées sur le conflit de ressources:

Conflit de disque: déjà expliqué en détail et peut être un problème possible, en particulier si vous écrivez de petites mémoires tampons à la fois au lieu du traitement par lots
Conflit de temps CPU si les threads sont programmés sur le même kernel: ce n’est probablement pas votre problème si vous définissez l’affinité. Cependant, vous devriez toujours vérifier
Cache de cache: de même, probablement pas votre problème si vous avez une affinité, bien que cela puisse être très coûteux si c’est votre problème.
Mémoire partagée: encore une fois parlé en détail et ne semble pas être votre problème, mais cela ne ferait pas de mal de vérifier le code pour le vérifier.
NUMA: encore parlé. Si votre thread de travail est épinglé sur un kernel différent, vous voudrez vérifier si le travail auquel il doit accéder est local par rapport au kernel principal.

Ok pour l’instant pas beaucoup de nouveau. Ce peut être n’importe lequel ou aucun des choix ci-dessus. La question est, dans votre cas, comment pouvez-vous détecter d’où vient le temps supplémentaire? Il y a quelques stratégies:

Auditer le code et rechercher des zones évidentes. Ne perdez pas trop de temps à le faire car il est généralement infructueux d’écrire le programme au début.
Refactorisez le code à thread unique et le code à threads multiples pour isoler une fonction process (), puis définissez le profil aux points de contrôle clés pour essayer de prendre en compte la différence. Puis rétrécissez-le.
Refactorisez l’access aux ressources en lots, puis profilez chaque lot à la fois sur le contrôle et sur l’expérience pour prendre en compte la différence. Cela vous indiquera non seulement les domaines (access disque, access mémoire, temps passé dans une boucle serrée) sur lesquels vous devez concentrer vos efforts, mais ce refactor pourrait même améliorer votre temps d’exécution en général. Exemple:
- Copiez d’abord la structure du graphe dans la mémoire locale des threads (effectuez une copie directe dans le cas à un seul thread)
- Puis effectuez la requête
- Puis configurez une écriture asynchrone sur le disque
Essayez de trouver une charge de travail minimalement reproductible présentant les mêmes symptômes. Cela signifie changer votre algorithme pour faire un sous-ensemble de ce qu’il fait déjà.
Assurez-vous qu’il n’y a pas d’autre bruit dans le système qui aurait pu causer la différence (si un autre utilisateur exécute un système similaire sur le kernel de travail).

Ma propre intuition pour votre cas:

La structure de votre graphique n’est pas compatible NUMA pour votre kernel de travailleurs.
Le kernel peut effectivement planifier votre thread de travail en dehors du kernel d’affinité. Cela peut arriver si vous n’avez pas d’isolement pour le kernel que vous épinglez.

Je ne peux pas vous dire ce qui ne va pas dans votre programme parce que vous n’en avez pas suffisamment partagé pour faire une parsing détaillée.

Ce que je peux vous dire, c’est que si c’était mon problème, la première chose que je voudrais essayer est d’exécuter deux sessions de profilage sur mon application, une sur la version à thread unique et une sur la configuration à double thread. Le rapport du profileur devrait vous donner une assez bonne idée de l’allocation du temps supplémentaire. Notez que vous n’aurez peut-être pas besoin de profiler l’exécution complète de l’application. Selon le problème, le décalage horaire peut devenir évident après quelques secondes ou quelques minutes de profilage.

En ce qui concerne les choix du profileur pour Linux, vous pouvez envisager oprofile ou gprof comme second choix.

Si vous avez besoin d’aide pour interpréter la sortie du profileur, n’hésitez pas à l’append à votre question.

Il peut être difficile à l’arrière de comprendre pourquoi les threads ne fonctionnent pas comme prévu. On peut le faire de manière analytique ou utiliser un outil pour montrer ce qui se passe. J’ai très bien exploité ftrace, le clone Linux de dtrace de Solaris (basé sur ce que VxWorks, Integrity OS de Greenhill et Mercury Computer Systems Inc ont fait depuis très longtemps.)

En particulier, j’ai trouvé cette page très utile: http://www.omappedia.com/wiki/Installing_and_Using_Ftrace , en particulier ceci et cette section. Ne vous inquiétez pas du fait qu’il s’agisse d’un site Web orienté OMAP; Je l’ai très bien utilisé sous Linux X86 (bien que vous deviez peut-être créer un kernel pour l’inclure). N’oubliez pas non plus que le visualiseur GTKWave est principalement conçu pour examiner les traces de journal issues des développements en VHDL. C’est pourquoi il a l’air “étrange”. C’est juste que quelqu’un s’est rendu compte que ce serait également un visualiseur utilisable pour les données de sched_switch, ce qui les a évité d’en écrire un.

En utilisant le traceur sched_switch, vous pouvez voir quand (mais pas nécessairement pourquoi) vos threads sont en cours d’exécution, et cela pourrait suffire à vous donner un indice. Le «pourquoi» peut être révélé par un examen attentif de certains des autres traceurs.

Si vous obtenez un ralentissement lié à l’utilisation d’un thread, cela est probablement dû à la surcharge liée à l’utilisation de fonctions de bibliothèque thread-safe ou à la configuration du thread. La création d’un thread pour chaque travail entraînera une surcharge importante, mais probablement pas autant que vous le souhaitez. En d’autres termes, il s’agit probablement d’une surcharge provenant d’une fonction de bibliothèque thread-safe.

La meilleure chose à faire est de profiler votre code pour savoir où le temps est passé. S’il s’agit d’un appel de bibliothèque, essayez de trouver une bibliothèque de remplacement ou de l’implémenter vous-même. Si le goulot d’étranglement est la création / destruction de threads, essayez de réutiliser les threads, en utilisant par exemple des tâches OpenMP ou std :: async en C ++ 11.

Certaines bibliothèques sont vraiment méchantes par rapport au temps système. Par exemple, de nombreuses implémentations de rand () utilisent un verrou global, plutôt que d’utiliser des prgn de threads locaux. Un tel temps système de locking est beaucoup plus important que la génération d’un nombre et est difficile à suivre sans profileur.

Le ralentissement peut également provenir de légères modifications que vous avez apscopes, par exemple en déclarant les variables volatiles, ce qui ne devrait généralement pas être nécessaire.

Je suppose que vous utilisez une machine avec un seul processeur. Ce problème n’est pas parallélisable sur ce type de système. Votre code utilise en permanence le processeur, qui a un nombre fixe de cycles à lui offrir. En réalité, il s’exécute plus lentement car le thread supplémentaire ajoute un changement de contexte coûteux au problème.

Les seuls types de problèmes qui se mettent bien en parallèle sur une machine monoprocesseur sont ceux qui permettent à un chemin d’exécution de s’exécuter tandis qu’un autre est bloqué en attente d’E / S, et aux situations un peu de temps processeur est plus important que d’exécuter votre code le plus rapidement possible.

Si vous souhaitez uniquement exécuter plusieurs instances indépendantes de votre algorithme, pouvez-vous simplement soumettre plusieurs travaux (avec des parameters différents, pouvant être gérés par un seul script) dans votre cluster? Cela éliminerait le besoin de profiler et de déboguer votre programme multithread. Je n’ai pas beaucoup d’expérience en programmation multithread, mais si vous utilisez MPI ou OpenMP, vous devrez également écrire moins de code pour la comptabilité. Par exemple, si une routine d’initialisation commune est nécessaire et que les processus peuvent s’exécuter indépendamment par la suite, vous ne pouvez le faire qu’en initialisant dans un thread et en diffusant. Pas besoin d’entretenir les serrures et autres.