Im dritten Teil geht es um die Parallelisierung mit OpenMP. Auf dem Arbeitsrechner werden 1000 zufällig gefüllte Strings in 71.6 sec. Der Algorithmus ist trivial über die äusserste Schleife zu parallelisieren, da ein String unabhänig der anderen Berechnet werden kann.
Um eine schnelle Übersicht über die systime zu bekommen, wird das Programm mittels dem Hilfsprogramm 'time' gestartet. Die systime beträgt 0m0.004s dieses Wert müssen wir nach der Parallelisierung optimalerweise wieder erreichen.
Ein einfaches
#pragma omp parallel for
for(int i=0; i < strings.size(); ++i) {
und schon brummen alle 8 Threads des AMD FX 8350 los. Die Zeit sagt 12.7 sec mit 0m0.008s systime. Das entspricht einem Speedup von 5.6 70%. Ein normaler Wert für den ersten Versuch. Um ein besseres Gefühl zu bekommen wie der Algorithmus skaliert, wird nochmal mit nur 4 Threads getestet. Es ist stark CPU abhängig ob ob auch alle Kerne einer CPU mit voller Leistung brummen können.
$ OMP_NUM_THREADS=4 time ./LevenshteinTerror
Mit 4 Threads ergeben sich 18.4 sec und ein Speedup von 3.89 97%. Besser geht es eigentlich garnicht.
Damit können wir gleich zu einer dickeren CPU wechseln: Intel Xeon E5-2680 mit 32 Kerne. Hier die Ergebnisse:
Threads Time [sec] Speedup Eff [%] 1 67.7 - - 2 33.9 2 100 4 17.0 3.98 99.5 8 9.22 7.34 91.8 16 4.94 13.7 85.6 32 4.54 14.9 46.6
Bis zu der Hälfte der Threads skaliert der Algorithmus gut, danach gibt es keinen Weiteren Speedup. Es werden in diesem Beispiel auch keine Unmengen an Daten verarbeitet, die CPU ist der Flaschenhals, nicht der RAM Bus.
Zum Abschluss noch eine Messung mit 16 und 32 Threads mit der 10-fachen Menge an Strings.
Threads Time [sec] Speedup Eff [%] 1 6709 - - 16 475 14.1 88.1 32 447 15.0 46.9
Zwei Stunden v.s. 8 Minuten.