Speedup und Skalierbarkeit

Die Untersuchungen der verschiedenen Testdatensätze zeigen ein interessantes Ergebnis. In der graphischen Darstellung der Analyse von rrna10 ist kein befriedigender Speedup der Rechenzeit mit steigender Anzahl an Slave-Prozessen zu erkennen (Abb. 5.4). Der Speedup, der sich aus dem Laufzeitverhältnis der einzelnen Analysen zur Analyse mit einem einzelnen Slave-Prozeß berechnet (Burkhardt, 1993), weicht sehr schnell vom linearen Verlauf ab und beginnt in Sättigung überzugehen.

Bei näherem Hinsehen ist dies allerdings einfach verständlich. Da die während eines Schrittes keine große Anzahl an Bäume zur Berechnung generiert werden (im letzten Schritt generiert der Master-Prozeß durch Zufügen der zehnten Spezies 15 neue Bäume), bedeutet dies, daß bis zum globalen Rearrangement, bei dem 182 Bäume generiert werden, bei höheren Prozessorzahlen, niemals alle Prozessoren genutzt werden. Auch im globalen Rearrangement geht der Speedup einer Sättigung entgegen. Dies liegt daran, daß die Zeit, die benötigt wird, um die Kantenlängen und den Likelihood-Wert dieser relativ kleinen Bäume zu berechnen (<1s), in einem schlechten Verhältnis zum entstandenen Mehraufwand durch das Verschicken der Bäume an die Slave-Prozesse steht.

 

Abbildung:   Zeit- und Skalierungsverhalten beim rrna10-Datensatz; gestrichelte Linie - Gesamtprozeß; durchgezogene Linie - globales Rearrangement; gepunktet - linearer Speedup; (Anzahl Spezies: 10; Bäume gesamt: 306; Bäume eines globalen Rearrangements: 182; Anzahl globaler Rearrangements: 1)

 

Abbildung:   Zeit- und Skalierungsverhalten beim rrna20-Datensatz gestrichelte Linie - Gesamtprozeß; durchgezogene Linie - globales Rearrangement; gepunktet - linearer Speedup; (Anzahl Spezies: 20; Bäume gesamt: 1890; Bäume des globalen Rearrangements: 1122; Anzahl globaler Rearrangements: 1)

 

Abbildung:   Zeit- und Skalierungsverhalten beim rrna28-Datensatz kurz gestrichelte Linie - Gesamtprozeß; lang gestrichelte Linie - Gesamtprozeß abzüglich des zweiten globalen Rearrangements; durchgezogene Linie - globales Rearrangement; gepunktet - linearer Speedup; (Anzahl Spezies: 28; Bäume gesamt: 6212; Bäume des ersten globalen Rearrangements: 2450; Anzahl globaler Rearrangements: 2)

Bei der Betrachtung des Speedups der Analysenlaufzeiten bei den größeren Datensätzen (Abb. 5.5 und 5.6) zeigt sich schon ein erheblich besseres Bild. Vor allem der Speedup der globalen Rearrangements ist hier schon fast linear. Dies liegt an der exponentiell mit der Anzahl der benutzten Spezies wachsenden Anzahl der in einem globalen Rearrangement generierten Bäume. Die Anzahl beträgt für n Spezies annähernd

4n² - 26n + 38

Bäume (, )[unveröffentlicht]matsuda94. Da die Bäume im globalen Rearrangement, verglichen mit den Bäumen aller anderen Schritte (2i-5 Bäume beim Einfügen der i-ten Spezies und 2i-6 beim darauffolgenden lokalen Rearrangement über einen Ast), den bei weitem größten Anteil ausmachen, verbessert sich bei Vergrößerung des Eingabedatensatzes zusehends auch die zu beobachtende Skalierbarkeit. D.h. je mehr Spezies eingegeben werden, um so mehr kann die Berechnung durch Erhöhung der Anzahl der Slave-Prozesse beschleunigt werden, bis Sättigungseffekte auftreten.

Das Ziel der Parallelisierung, die Rechenzeit effektiv zu verringern, ist mit der Implementierung von pfastDNAml gelungen. Die Parallelversion sollte ja dafür genutzt werden, um größere Probleme in einem annehmbaren Zeitraum lösbar zu machen. Berechnungen mit bis zu 15 Spezies, die auch vorher schon mit den sequentiellen Implementierungen berechnet wurden, spielen bei den Betrachtungen nur eine untergeordnete Rolle, da sie ohnehin kein größeres zeitliches Problem darstellten.