Tri parallèle par fusion avec des threads / beaucoup / plus lent que Seq. Tri par fusion. Aidez-moi

http://pastebin.com/YMS4ehRj

^ Ceci est mon implémentation du sorting par fusion parallèle. En gros, ce que je fais est que, pour chaque scission, la première moitié est gérée par un fil alors que la seconde moitié est séquentielle (ie) disons que nous avons un tableau de 9 éléments, [0..4] est gérée par le fil 1, [0 ..1] est traité Sujet 2, [5..6] est traité par le fil 3 (Regardez le code source pour plus de précisions).

Tout le rest rest le même, comme la fusion. Mais le problème est que cela fonctionne beaucoup plus lentement que le type de fusion, même plus lent que le type de bulle normal! Et je veux dire pour un tableau de 25 000 int. Je ne sais pas où se trouve le goulet d’étranglement: s’agit-il du locking mutex? Est-ce la fusion?

Des idées sur la façon de rendre cela plus rapide?

Vous créez un grand nombre de threads, dont chacun ne fait alors que très peu de travail. Pour sortinger 25 000 ints, vous créez environ 12500 threads qui génèrent d’autres threads et fusionnent leurs résultats, et environ 12500 threads qui ne sortingent que deux ints chacun.

La surcharge liée à la création de tous ces threads dépasse de loin les gains que vous obtenez grâce au traitement en parallèle.

Pour éviter cela, assurez-vous que chaque thread a un travail raisonnable à faire. Par exemple, si un thread constate qu’il ne doit sortinger que <10000 nombres, il peut simplement les trier lui-même avec un tri de fusion normal, au lieu de créer de nouveaux threads.

Étant donné que votre système contient un nombre fini de cœurs, pourquoi voudriez-vous créer plus de threads que de cœurs?

En outre, la raison pour laquelle vous devez avoir un mutex n’est pas claire. D’après ce que j’ai pu constater à partir d’une parsing rapide, le programme n’a pas besoin de partager les threads [lthreadcnt] en dehors de la fonction locale. Utilisez simplement une variable locale et vous devriez être en or.

Votre parallélisme est trop fin, il y a trop de fils qui ne font que de petits travaux. Vous pouvez définir un seuil afin que les tableaux dont la taille soit inférieure à celle du seuil soient sortingés séquentiellement. Faites attention au nombre de threads créés, une bonne indication est que le nombre de threads n’est généralement pas beaucoup plus grand que le nombre de cœurs.

Une grande partie de votre calcul étant en fonction de merge , une autre suggestion consiste à utiliser la fusion Divide-and-Conquer Merge au lieu de la fusion simple. L’avantage est double: le temps d’exécution est plus court et il est facile de générer des threads pour exécuter une fusion parallèle. Vous pouvez avoir une idée de la façon de mettre en œuvre la fusion parallèle ici: http://drdobbs.com/high-performance-computing/229204454 . Ils ont également un article sur le sorting par fusion parallèle qui pourrait vous être utile: http://drdobbs.com/high-performance-computing/229400239