Struktur des Master-Prozesses

Die nachfolgend beschriebene Struktur und der Ablauf innerhalb des Master-Prozesses ist auch in Abb. 5.2 in Form eines Flußdiagramms dargestellt.

 

Abbildung:   Struktur des Master-Prozesses bei der Parallelversion von pfastDNAml, inklusive der Master/Slave-Kommunikation zum Übermitteln der Bäume. Die Kommunikation während des init- und exit-Schrittes ist nicht eingezeichnet, da sie von untergeordneter Bedeutung ist.

init

Am Anfang geschieht eine Initialisierung des Master-Prozesses genau wie in den Punkten 1. bis 3. im sequentiellen Programm. Zusätzlich werden alle angeforderten Slave-Prozesse angesprochen und ihnen der gesamte Inhalt der Eingabedatei über das Netzwerk zugeschickt. Dieses geschieht, da es Parallelrechnersysteme gibt, in denen nicht alle Knoten oder Prozessoren Zugriff auf die Festplatte haben (, )[persönliche Kommunikation]keller-mitteilung. Zusätzlich werden alle weiteren nötigen Daten, wie z.B. die Startzeit, an die Slave-Prozesse gesandt.

Anschließend wird der erste Baum aus drei Spezies generiert und die Kantenlängen vom Master-Prozeß selbst bestimmt (Punkt 4.). Hiermit ist die Initialisierung des Master-Prozesses abgeschlossen.

generate

Dann beginnt der Master-Prozeß der Reihe nach neue Bäume durch Einfügen einer neuen Spezies in den letzten gefundenen optimalen Baum zu generieren. Mit jedem neu generierten Baum wird die Routine zur Master/Slave-Kommunikation (dispatch/receive) aufgerufen. Es werden so alle möglichen Baumtopologien generiert und an den Kommunikationsteil übergeben.

Nach Übergabe des letzten in diesem Schritt zu generierenden Baumes verharrt der Master-Prozeß in der Kommunikationsroutine und kehrt mit dem besten der berechneten Bäume wieder an diese Stelle zurück. Der gefundene Baum wird in der checkpoint-Datei abgelegt, und der Master-Prozeß geht dann zum Optimieren durch Rearrangement (optimize) über. Sollten noch nicht mehr als vier Spezies im Baum enthalten sein, beginnt der generate-Schritt mit dem besten Baum und der nächsten Spezies.

optimize

Mit dem besten im generate-Schritt gefundenen Baum wird nun ein Rearrangement durchgeführt, wie es in der Eingabedatei spezifiziert wurde. Hierbei werden alle Teilbäume aus dem existierenden Baum ausgeschnitten und in die Nachbarkanten eingesetzt. So entstehen Schritt für Schritt neue Bäume, mit denen wieder die dispatch/receive-Routine aufgerufen wird.

Auch jetzt verharrt der Master-Prozeß wieder nach Übergabe des letzten in diesem Schritt zu generierenden Baumes in der Kommunikationsroutine und kehrt mit dem besten der berechneten Bäume wieder an diese Stelle zurück. Wurde in diesem Durchlauf ein besserer Baum gefunden, wird dieser in der checkpoint-Datei abgelegt und der optimize-Schritt wiederholt, bis kein neuer optimaler Baum mehr gefunden wird.

Sind im Baum alle Spezies enthalten so geht der Master-Prozeß zum exit-Schritt über, anderenfalls wird mit dem diesem optimalen Baum und der nächsten Spezies wieder der generate-Schritt durchlaufen.

dispatch/receive

Wird ein Baum an diese Routine übergeben, so wird geprüft, ob Anforderungen von Slave-Prozessen vorliegen. Falls dem so ist, wird der übergebene Baum sowie eventuell in der Warteschlange befindliche Bäume an die Slave-Prozesse geschickt, bis alle Anfragen bearbeitet oder keine Bäume mehr vorhanden sind.

Sind keine Anfragen vorhanden, wird der übergebene Baum in eine Warteschlange eingereiht.

Anschließend an das Versenden wird geprüft, ob berechnete Bäume von Slave-Prozessen zurückgesandt wurden. Solche Bäume werden in eine mittels eines Heaps implementierte Priority-Queue (Cormen et al., 1990) eingereiht, um die besten gefundenen Bäume heraussortieren zu können.

Sind im generate-Schritt bzw. optimize-Schritt noch neue Bäume zu generieren, so kehrt der Master-Prozeß zu diesem Schritt zurück.

Sind im generate-Schritt bzw. optimize-Schritt keine neuen Bäume mehr zu generieren, so verbleibt der Master-Prozeß in dieser Routine, bis alle Bäume an die Slave-Prozesse verteilt und von diesen nach der Berechnung des ML-Wertes zurückgesandt wurden.

Anschließend wird der von allen berechneten Bäumen optimale Baum aus der Priority-Queue gezogen und der Master-Prozeß springt an das Ende des generate- bzw. optimize-Schrittes.

exit

Nach der Analyse wird der gefundene ML-Baum, falls nicht anders angegeben, als Ergebnis in der Ausgabedatei und der der Baum in der treefile-Datei ausgegeben.

Anschließend wird den Slave-Prozessen übermittelt, daß die Analyse beendet ist. Der Master-Prozeß gibt dann den belegten Speicherplatz wieder frei und endet, nachdem auch die Slave-Prozesse gestoppt haben.

Während der Analyse wird kontinuierlich jeder auszuführende Schritt und dessen Laufzeiten in der Ausgabedatei dokumentiert.