9
votes

Comment faire fonctionner une algorithme de division et de conquérir efficacement?

J'ai rafraîchi ma mémoire sur le tri des algorithmes ces derniers jours et je suis tombé sur une situation où je ne trouve pas ce que la meilleure solution est la meilleure solution.

J'ai écrit une implémentation de base de Quicksort, et je voulais Pour renforcer ses performances en parallèle son exécution.

Ce que j'ai eu est que: xxx

tandis que cela fonctionne mieux que le naïf "sans threads "Mise en œuvre, cela présente de graves limitations, à savoir:

Si le tableau pour trier est trop gros ou que la récursion va trop profonde, le système peut s'épuiser de threads et l'exécution échoue de manière misérablement.
Le coût de la création de fils dans chaque appel récursif pourrait probablement être évité, en particulier, étant donné que les threads ne sont pas une ressource infinie.
Je voulais utiliser une piscine de thread pour éviter la création tardive, mais je fais face à un autre problème:
- La majeure partie du fil que je crée faire tout leur travail au début, alors ne faites rien pendant qu'ils sont attendus à la fin. Il en résulte que beaucoup de threads n'attendent que des appels de sous-appels qui semblent plutôt sous-optimaux.
  y a-t-il une technique / entité que je pourrais utiliser pour éviter de gaspiller des fils (permettre leur réutilisation)?
  Je peux utiliser Boost ou toute installation C ++ 11. < / p>

c++ multithreading sorting c++11 parallel-processing

5 commentaires

Vous recherchez une bibliothèque «vol de travail». Mais je doute que C ++ 11 ou Boost en a une.

Je suis à peu près sûr qu'il y a une mise en œuvre itérative sur place de Quicksort. Ce serait peut-être un moyen facile de gérer les filets en attente et de supprimer également les limitations récursives.

Vérifiez le parallèle QuickSort à partir de ce lien Stackoverflow.com/Questtions/16248321/... . Il s'agit d'une implémentation parallèle QuicksTort à partir de "C ++ Concurrence en action" de A.Williams (mise en œuvre de threads de boost). Et c'est le livre sur le sujet.

Vous voudrez peut-être jeter un coup d'œil à Intel Cilk-Plus qui utilise le vol de travail. Il y a une branche spéciale de GCC 4.8.

Une bonne piscine des tâches ne nécessitera pas rejoindre - au lieu de cela, vous créez des tâches et obtenez std :: futur sort. Les tâches envoyées à faire seront expédiées aux threads, générer une réponse et sortir. Pour votre code, vous partiriez, créez une tâche qui trie la première et la deuxième moitié, puis planifiez le message "Je suis terminé" lorsque ces deux tâches sont effectuées (peut-être via un Ensuite, Mécanisme sur les deux futur s ou de l'aide du pool de tâches). Ensuite, votre code quitterait, renvoyant le futur .

3 Réponses : 1 votes Je ne suis pas un expert en fil, mais une fois que vous avez résolu le problème du fil, vous en aurez un autre: L'appel à partition de l'entrée n'est pas parallélisé. Cet appel coûte assez cher (il nécessite une itération séquentielle sur le tableau). Vous pouvez lire la section parallèle de QSort à Wikipedia: 2 commentaires Eh bien, les appels vers Quicksort (qui appelez à titre appel partition ) sont paralellisés, donc les appels partition sont réellement paralellisés trop. Merci pour le lien d'article. @ cerneon: Oui, mais vous avez un problème de déséquilibre de charge grave. Votre récursion est uniquement O (lg (n)) profond (par exemple 20 niveaux pour les articles 1M) et votre premier niveau est entièrement séquentiel, votre deuxième niveau n'a que le parallélisme 2, etc. En utilisant une partition séquentielle (), vous limitez gravement votre vitesse maximale (bien en dessous de ce qui est possible.) 6 votes Si le tableau pour trier est trop gros ou que la récursion va trop profonde, le système peut manquer de threads et l'exécution échoue de manière misérablement. Alors allez séquentiel après une profondeur maximale ... xxx avec profondeur <5 Il créera un maximum de 50 fils, qui Saturera facilement la plupart des processeurs multi-coreaux - un autre parallisme ne donnera aucun avantage. Le coût de la création de threads dans chaque appel récursif pourrait probablement être évité, en particulier, étant donné que les threads ne sont pas une ressource infinie. Les fils endormis ne coûtent pas vraiment autant que les gens pensent, mais il ne sert à rien de créer deux nouveaux threads à chaque branche, peut aussi bien réutiliser le fil actuel, plutôt que de la mettre à dormir .. . xxx Alternativement à l'aide de de profondeur , vous pouvez définir une limite de thread globale, puis créer un nouveau fil si la limite n'a pas été atteint - si cela l'a, que de le faire séquentiellement. Cette limite de thread peut être traitée de manière large afin que les appels parallèles sur Quicksort seront recondiqués de manière coopératoire de créer trop de threads. 6 commentaires Merci. Je suis venu à la même conclusion sur la partie "Pourquoi devrais-je créer deux threads à chaque appel?" Si je devais utiliser un compteur mondial pour mes discussions, que utiliseriez-vous pour faire ce coiffe? @ cerneon, même avec ces suggestions, n'utilisez pas de fils brus ou de piscines threads directement pour des algorithmes parallèles de données imbriqués. @ user1131467 C'est bon si vous traitez avec un parallélisme de données purement plat, mais ce n'est pas ce que nous traitons ici et ce n'est pas ce dont je parle. Écrire des données récursives / nichées Les algorithmes parallèles avec cette approche sont médiocres et une méthode inefficace et il est bien connu pour avoir toutes sortes de problèmes, sur-abonnement, équilibrage de charge médiocre, etc., vous pouvez donc faire de manière significative mieux dans ce cas Et ce n'est pas "magique" (j'ai constaté que très insultant) Il existe différents papiers et implémentations sur le sujet, le courant principal étant l'algorithme de vol de travail. @ user1131467 Mais cette approche n'est pas optimale! (votre code posté) et n'allore pas bien, c'est mon point! Même le pot le sait. Un thread-piscine aide uniquement à atténuer le coût de la création de fil, mais vous utilisez toujours un nombre variable de threads en fonction de la taille large / profonde de la récursion. Si vous avez utilisé un système basé sur un emploi / tâche, il existe toujours un nombre fixe de fils de travailleurs, quel que soit le nombre de tâches engendrées. Le nombre de threads est fixé et généralement égal au nombre de filets matériels. Je travaille dans l'industrie des jeux et nous n'écrivons jamais d'algorithmes parallèles comme dans votre code. Cette approche est surchargée et passera probablement plus de temps à faire la chasse au filetage que le vrai travail. J'irais pour un niveau supérieur et faire le parallélisme là-bas. Comme @snk_kid, ce n'est pas la mesure où les choses sont effectuées dans certains contextes (secteur du jeu). @Traxnet: Démarrer 32 threads n'est pas une performance significative. Le noyau gère facilement le changement de contexte de manière à ce qu'il soit presque optimal. NPTL peut démarrer 100 000 threads en dessous une seconde. Veuillez tester des choses avant de faire des hypothèses sauvages. 1 votes Utilisation de threads directement pour écrire des algorithmes parallèles, en particulier des algorithmes de type Divide-et-Conquer, vous aurez une mauvaise idée, vous aurez une mauvaise mise à l'échelle, un équilibrage de la charge médiocre et tout comme vous savez que le coût de la création de fil est coûteux. Le fil-piscines peut aider avec ce dernier mais pas le premier sans écrire de code supplémentaire. De nos jours, presque tous les cadres parallèles modernes sont basés sur un planificateur de vol de travail basé sur une tâche, de tels exemples sont Intel TBB, Microsoft Concurrency Run-Time (concert) / PPL. au lieu de se frayer des filetages ou de la réutilisation des threads d'une piscine, ce qui se passe est une "tâche" (généralement une fermeture + certaines données de comptabilité) est mise sur la file (s) de vol de travail à voler à un moment donné par l'une des X nombre de threads de travailleurs. Généralement, le nombre de threads est égal au nombre de filets matériels disponibles sur le système, de sorte que cela n'a pas beaucoup d'importance si vous appartenez / la file d'attente de centaines / milliers de tâches (le fait dans certains cas dépend du contexte). C'est une bien meilleure situation pour les algorithmes parallèles de la division imbriquée et de la conquise / Fourche / Fourche. pour (imbriqué) des algorithmes parallèles parallèles Il est préférable d'éviter de reproduire une tâche par élément car, généralement une opération sur un seul élément, la granularité du travail est beaucoup trop petite pour obtenir des avantages et l'emporte sur les frais généraux de la gestion des planificateurs ainsi de suite. Haut du planificateur de travail au niveau inférieur, vous disposez d'une gestion de niveau supérieur qui traite de la division d'un conteneur en morceaux. C'est toujours une bien meilleure situation que d'utiliser des threads / thread-piscines, car vous ne divisez plus sur le thread-comptant optimal. Quoi qu'il en soit, il n'y a rien de tel que celui-ci normalisé en C ++ 11, si vous souhaitez une solution de bibliothèque standard pure sans ajouter de dépendances tierces, ce qui est préférable que vous puissiez faire est: a. Essayez d'utiliser STD :: ASYNC, certaines implémentations telles que VC ++ utiliseront un planificateur de vol de travail en dessous, mais il n'y a pas de garantie et la norme C ++ ne l'applique pas. b. Ecrivez votre propre planificateur de vol de travail sur les primitives de thread standard fournies avec C ++ 11, il est faisable mais pas si simple à mettre en œuvre correctement. Je dirais juste aller avec Intel TBB, il s'agit principalement de plate-forme multiplate-forme et fournit divers algorithmes parallèles de haut niveau tels que le tri parallèle. 3 commentaires Fondamentalement, vous vous conseillez dans ce cas et des cas similaires ne gèrent pas les threads par vous-même, mais pour permettre une sorte de planificateur (explicite ou implicite) de faire le travail. Malheureusement, toutes ces implémentations nécessitent une connaissance approfondie du sujet très difficile. OpenMP vaut la peine de mentionner ici. J'ai trouvé plus facile à utiliser que TBB Intel TBB, OpenMP, et similaires, sont des bibliothèques userland. Sous la hotte, ils appellent la méthode de fil de création ( clone sur Linux, créatethread sur Windows, etc.) comme std :: thread et tout le monde . Il est important de comprendre ce qu'est un fil réellement et comment le système d'exploitation les gère, afin de comprendre leurs implications de performance. Beaucoup de gens ne comprennent pas à quel point il est bon marché de créer un thread et de la qualité d'un travail que le noyau doit changer entre eux, par conséquent, ils s'inquiètent des optimisations triviales qui atteignent très peu.

Articles qui pourrait vous intéresser : Catalina C ++: L'utilisation d'en-têtes <cmath> génère une erreur: aucun membre nommé 'signbit' dans l'espace de noms global installation du compilateur c ++ 11 (+) sans autorisation d'administrateur Application de console C ++ VS2019 - Le débogueur n'acceptera pas les arguments de commande Meilleur moyen en C ++ de garder une grosse structure atomique?