Next: Impuls-Null-Potentiale Up: Monte-Carlo-Simulation mit fixierten Previous: Wärmebad-Algorithmus für GAUSS-Blockspins

Geometrische Parallelisierung

Auf den benutzten Workstations kann es lange dauern, bis man Erwartungswerte mit ausreichend kleinen Fehlertoleranzen gemessen hat. Eine Möglichkeit, während einer tolerierbaren Zeit Ergebnisse mit vernünftigen Fehlern zu bekommen, besteht in der Parallelisierung des Algorithmus. Als Parallelrechner habe ich gewöhnliche Workstations genommen, deren Kommunikation das Ethernet übernahm. Um den geringen Kommunikationskapazitäten gerecht zu werden, wurde eine geometrische Parallelisierung vorgenommen ([BUR93], [HB90]).
Dazu unterteilt man das gesamte Gitter in Quadrate, wobei die Grenzen dieser Quadrate entlang von Blockspin-Grenzen verlaufen. Jedem Prozessor werden je nach Leistungsfähigkeit eines oder mehrere solcher Quadrate zugewiesen. Haben nun sowohl das Potential als auch der kinetische Term eine Reichweite , so muß jeder Prozessor zum Update seines Quadrates nur die Ränder der Breite seiner Nachbarquadrate kennen. Es sind insgesamt sechs streng hintereinander durchzuführende Kommunikationseinheiten nötig, bei denen ein Prozessor jeweils in einem Teil seiner Randgebiete das Update durchführt und dieses Gebiet dann an seinen Nachbarn verschickt, um dann auf den Empfang der entsprechenden Daten des gegenüberliegenden Nachbarn zu warten. Direkt anschließend oder noch während des Wartens auf Daten von anderen Rechnern wird das Update im Zentralbereich des jeweiligen Quadrates durchgeführt, wozu ein Prozessor nicht das ``Wissen'' um die Spins in anderen, fremden Quadraten braucht. Die explizite Netzprogrammierung und die Datenkonvertierung zwischen Rechnern verschiedener Architektur wurde dabei mit Hilfe des Programmpaketes PVM realisiert. Einen Überblick zur aktuellen Message-Passing-Software liefert [TUR94].
Problematisch bei dieser Art der Parallelisierung ist der Verlust eines Nachrichtenpaketes im Netzwerk. Der Empfänger dieser Nachricht kann damit das Update seines Quadrates nicht zu Ende führen und blockiert innerhalb von kurzer Zeit den gesamten Parallelrechner. Es entsteht ein sog. ``Deadlock''. Man kann das Auftreten von solchen Patt-Situationen durch die Verwendung von fehlertoleranter Netzwerksoftware verhindern. Diese Softwarepakete arbeiten i. a. nach dem Handshake-Verfahren, bei dem sich der Sender eines Nachrichtenpakets den Empfang quittieren läßt. Erfolgt diese Rückmeldung nicht innerhalb eines vorgeschriebenen Zeitraums, so wird das Nachrichtenpaket nochmal versendet. Zu dieser Kategorie zählt das zu PVM kompatible, aber fehlertolerante Softwarepaket FT-PVM. Allerdings bedingt das Handshake-Verfahren immer eine zusätzliche Netzwerkbelastung. Da aber gerade das Netzwerk den Engpaß für Parallelrechner am Rechenzentrum der Westfälischen Wilhelms-Universität darstellt, wurde auf die Fehlertoleranz der Software verzichtet.
Da der langsamste Rechner den Zeitraum für ein Update bestimmt, sollte man große Sorgfalt auf die Wahrung der ``load balance'' legen. Diese Balance wurde häufig durch andere Benutzer des Workstation-Clusters gestört. Deshalb wurde für je 4-6 Rechner immer ein Ersatzrechner eingeplant, der in solch einem Fall während der Laufzeit die Arbeit der belasteten Workstation übernahm. Zusätzlich lief auf einem Rechner noch das sog. Master-Programm, das die Aufgabenverteilung koordinierte, Meßwerte zusammentrug und den einzelnen Update-Programmen Zufallszahlenkontingente zuteilte.
In Abbildung sind die Rechenleistungen verschiedener Kombinationen von Workstations zu einem Parallelrechner für eine MC-Simulation eines modifizierten Sine-GORDON-Modells mit einem kinetischen Term der Reichweite eingetragen. Vergleicht man diese praktische Rechenleistung mit der theoretischen Rechenleistung, so zeigt sich der für MIMD-Rechner typische Abfall der Effizienz mit zunehmender Prozessorzahl.

In der Praxis haben sich Rechner mit 8-16 Prozessoren bewährt. Schaltet man mehr Prozessoren zusammen, so muß man an der Westfälischen Wilhelms-Universität bis zu vier verschiedene Rechnerarchitekturen berücksichtigen. Zudem war das lokale Netz ab einer Größe von 64 Rechnern überlastet; solche Parallelrechner liefen im Durchschnitt nur zwei Stunden, bis sie von einem ``Deadlock'' lahmgelegt wurden.



Next: Impuls-Null-Potentiale Up: Monte-Carlo-Simulation mit fixierten Previous: Wärmebad-Algorithmus für GAUSS-Blockspins


spander@
Dienstag, 6. September 1994, 17:45:39 Uhr MES