Sortieren mit Multithreading

Eine Barriere muss man sich so vorstellen, dass verschiedene Threads jeweils ihre eigene Aufgabe durchführen und dann auf die Barriere „warten“, was bedeutet, dass sie darauf warten, dass alle anderen beteiligten Threads auch auf die Barriere warten, also die davor angesetzte Aufgabe abgeschlossen haben.

Als Anwendung für die sogenannte „Barriere“ habe ich einmal ein kleines C-Programm geschrieben, das eingelesene Zeichenketten sortiert. Über einen Parameter kann man wählen, ob Heapsort oder Flashsort oder Quicksort verwendet wird. Dafür habe ich zwei Funktionen (mit Header-Datei) hsort und hsort_r geschrieben, die das gleiche Interface wie qsort und qsort_r haben, so dass man sie austauschbar nutzen kann. Entsprechend auch drei Funtkionen fsort, fsort_r und fsort_f (mit Headern), die sich an das Interface von qsort anlehnen, aber noch einen zusätzlichen Funktionisparameter haben, der eine Art monotone Hash-Funktion nach double darstellt. Die gegebenen Zeichenketten werden zu möglichst gleichen Teilen auf eine frei wählbare Anzahl Threads verteilt. Jeder Thread sortiert seinen Teil mittels hsort_r oder fsprtr oder qsort_r. Anschließend wird mit einer Barriere sichergestellt, dass alle Threads ihren Teil sortiert haben und dann werden baumartig die Ergebnisse von jeweils zwei Threads zusammengefügt, jeweils gefolgt von einer weiteren Verwendung Barriere. An Schluss bleibt ein Thread mit seinem Ergebnis übrig und das ist das Sortierergebnis.

Bei einer Beispieleingabe mit 8603049 Wörtern war fsort mit einem Thread etwas schneller als qsort und qsort war etwa viermal so schnell wie hsort, aber mit einer größeren Anazhl Threads ließen sich alle drei beschleunigen.
Interessant war auf einem Rechner mit 4 Core-CPU und Hyperthreading, also 8 logischen CPUs, die unter /proc/cpuinfo angezeigt wurden, dass das Sortieren mit mehr Threads bei hsort mehr profitierte als bei qsort und um Faktor 5 schneller wurde, während fsort nur um Faktor 2 schneller wurde.

Das erklärt sich wohl vor allem durch das assymptotisch gute Verhalten von fsort (O(n)), was beim Sortieren großer Datenmengen in einem Thread besonders stark zum Tragen kommt. hsort ist im „worst case“ auch noch O(n \log n)

Threads Messwert Quicksort Heapsort Flashsort
1 real 4.090s 16.909s 3.757s
1 user 4.028s 16.815s 3.686s
1 sys 0.053s 0.053s 0.062s
           
2 real 2.753s 8.915s 2.672s
2 user 4.177s 16.457s 3.925s
2 sys 0.074s 0.054s 0.066s
           
3 real 2.333s 6.584s 2.392s
3 user 4.261s 16.676s 4.159s
3 sys 0.070s 0.064s 0.067s
           
4 real 2.027s 5.288s 2.093s
4 user 4.331s 16.202s 4.137s
4 sys 0.067s 0.072s 0.077s
           
5 real 2.151s 5.013s 2.254s
5 user 4.681s 17.423s 4.567s
5 sys 0.060s 0.056s 0.076s
           
6 real 2.039s 4.519s 2.104s
6 user 5.264s 18.511s 4.892s
6 sys 0.072s 0.062s 0.078s
           
7 real 1.928s 4.127s 2.092s
7 user 5.333s 18.878s 5.265s
7 sys 0.080s 0.056s 0.094s
           
8 real 1.862s 3.879s 1.931s
8 user 5.638s 19.338s 5.380s
8 sys 0.080s 0.061s 0.069s
           
9 real 2.032s 4.079s 2.174s
9 user 5.484s 19.594s 5.460s
9 sys 0.072s 0.066s 0.081s
           
10 real 2.017s 4.040s 2.130s
10 user 5.426s 19.091s 5.356s
10 sys 0.084s 0.080s 0.090s
           
11 real 1.954s 4.055s 2.081s
11 user 5.427s 19.240s 5.460s
11 sys 0.077s 0.081s 0.095s
           
12 real 1.928s 3.842s 2.053s
12 user 5.409s 18.860s 5.462s
12 sys 0.078s 0.075s 0.092s
           
13 real 1.923s 3.884s 2.040s
13 user 5.384s 19.123s 5.511s
13 sys 0.077s 0.072s 0.080s
           
14 real 1.870s 3.793s 2.037s
14 user 5.482s 18.566s 5.610s
14 sys 0.064s 0.070s 0.089s
           
15 real 1.895s 3.679s 1.979s
15 user 5.578s 18.549s 5.554s
15 sys 0.090s 0.067s 0.084s
           
16 real 1.861s 3.790s 1.979s
16 user 5.576s 19.033s 5.640s
16 sys 0.088s 0.085s 0.101s
           
17 real 2.025s 3.885s 2.181s
17 user 5.647s 18.699s 5.799s
17 sys 0.090s 0.076s 0.102s
           
18 real 2.019s 3.879s 2.156s
18 user 5.688s 18.532s 5.723s
18 sys 0.069s 0.107s 0.095s
           
19 real 2.022s 3.918s 2.140s
19 user 5.774s 18.783s 5.681s
19 sys 0.093s 0.085s 0.091s
           
20 real 1.975s 3.774s 2.129s
20 user 5.588s 18.095s 5.732s
20 sys 0.093s 0.087s 0.105s
           
100 real 1.978s 3.263s 2.099s
100 user 5.686s 15.371s 6.034s
100 sys 0.150s 0.115s 0.141s
           
400 real 2.013s 2.996s 2.092s
400 user 5.719s 13.150s 6.184s
400 sys 0.242s 0.185s 0.259s
           
1000 real 1.992s 2.876s 2.106s
1000 user 5.802s 12.608s 6.469s
1000 sys 0.325s 0.250s 0.392s

Man sieht also, was auch zu erwarten ist, dass Parallelisierung beim Sortieren hilfreich sein kann. In diesem Fall eignet sich der Algorithmus gut für die Parallelisierung, weil im ersten Schritt jeder Thread seinen getrennten Bereich sortiert und in den weiteren Schritten jeweils ein Thread die eigenen Daten mit denen eines anderen Threads zusammenfügt, während dieser andere Thread nur auf die Barriere wartet. Es gibt sicher noch bessere Verfahren, das zu parallelisieren, aber man sieht, dass es sich lohnt, wenn man wirklich genug CPUs zur Verfügung hat.

Share Button

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

*