Bernhard Seiwald, Christian Pfaffel, Pierre Schnizer
Juni, 1998
Bei der sequentiellen Verarbeitung wird ein Schritt nach dem anderen ausgeführt. Dies stellt die geläufigste Variante (Textverarbeitungen, Präsentationssoftware, ...) dar.
Parallel-Verarbeitung wird, abgesehen vom großen Bereich der numerischen
Simulationen (Finite-Elemente-Methoden in der Festigkeitslehre,
Wettervorhersagen, ...), unter anderem im Bereich der Datenbanken
eingesetzt.
Zur sinnvollen Parallel-Verarbeitung sind zwei Voraussetzungen zu erfüllen:
Hier soll nun speziell die Berechnung der Trajektorien von poitiven Ionen in einem Flugzeitmassenspektrometer parallelisiert werden.
Bei dem hier vorliegenden Problem einer Monte-Carlo-Simulation handelt es sich um einen klassischen Fall für Parallel-Programmierung. Keine der berechneten Trajektorien wird in irgendeiner Form von der Berechnung einer weiteren Bahn beeinflußt noch muß auf ein Ergebnis von einem anderen Teilchen zurückgegriffen werden. Damit ist die erste Bedingung erfüllt.
Die zweite Bedingung konnte auch erfüllt werden, da wir vorhandene PC´s, die
mit dem System V UNIX - Derivat Linux arbeiten und sich im Netzwerk befinden,
mit entsprechender Software zu einem Cluster umfunktionierten. Die Hardware
bestand aus drei kleineren PC´s (486er mit 66MHz CPU-Takt und jeweils 32 MB
RAM) sowie einem PC mit einem Pentium mit 200MHz CPU-Takt (48MB RAM) und einem
Pentium MMX mit 200MHz CPU-Takt (128MB RAM). Letzterer fungierte noch
als File-, Programm- und Internet-Server.
Prinzipiell gibt es nun zwei Möglichkeiten diese Aufgabe zu lösen:
![[*]](http://fubphpc.tu-graz.ac.at/icons.gif/foot_motif.gif){kind=icon}
benötigt, empfiehlt es sich
jeweils ein Szenario (oder auch mehrere, da es sich beim Betriebssystem um
UNIX handelt) auf jeweils einem Computer laufen zu lassen. Abhängig von der
Leistungsfähigkeit der Rechner werden mehr oder weniger viele Szenarien
einer Maschine zugeteilt. Die Änderungen eines nicht-parallelisierten
Programms beschränken sich im Wesentlichen auf ein erneutes Compilieren und
hinzulinken spezieller Libraries.
In diesem Fall entschied ich mich für die zweite Lösung. Dazu wurde vom
Sytemadministrator der Linux-Maschinen MPI (The Message-Passing
Interface) installiert. Die C-Sourcen sind via Internet frei erhältlich (z.B.
vom Argonne National Laboraty, University of Chicago;
http://www.mcs.anl.mpi/) und können problemlos auf diversen
UNIX-Plattformen kompiliert und installiert werden. Näheres zu MPI ist unter
anderem den Publikationen [1], [2] und [3] zu entnehmen.
Zudem ist MPI1 als Standard entwickelt worden. Die Implementation der University of Chicago (mpich ), die auch wir verwenden, ist unter anderem auf Systemen von SUN und DIGITAL (DEC) lauffähig.
Eine detailierte Beschreibung und kurze Demo-Programme zur verwendeten Technik der Non-Blocking -Communication findet der geneigte Leser in [2], Kapitel 2.8, Seite 49ff(Beschreibung der Technik) und [2], Kapitel 2.8, Seite 69ff(Listing).
Um ein Programm auf einer Maschine schnell auszuführen, ist es notwendig das Programm auch geeignet zu kompilieren und zu linken. Hier ist es nötig darauf zu achten, daß der Compiler auch richtig optimiert, das heißt die richtigen Optimierflags gesetzt sind. Gute Compiler lassen eine Optimierung nach der Größe und der Geschwindigkeit des exekutierbaren Programmes zu. Bei UNIX Compilern sind (fast) immer flags mit -0n (n = 1...) dafür zuständig.
Hier will ich als Beispiel ein wenig auf den Compiler von DIGITAL eingehen: Hier gibt es Optimierstufen von 1...5. Zusätzlich kann man noch angeben, ob hier schnelle Numerik (-D_FASTMATH, -D_INLINE_INTRINSICS, -float) interessant ist, oder genaue Numerik. Weiters sind die heutigen C Compiler imstande Funktionen ,,inlinen``. Zum Beispiel kennt der DEC Compiler die Optionen -inline speed. Hier schaut der Compiler, wo es sich auszahlt eine Funktion zu ,,inlinen``. Dazu ist aber notwendig, daß dem Compiler zum Zeitpunkt der Compilierung die Funktionen im Source vorliegen. (Eine einfache bzw. brutale Möglichkeit ist, alle Sourcefiles zu einem zusammenzufügen, und dieses dem Compiler zu ,,füttern``.)
Auch beim Linken kann man einiges in der Performance gewinnen oder verlieren.
Hierzu ein kurzer Exkurs in die Hardware: Jeder Prozessor besitzt heute einen kleinen eigenen Speicher, auf den er schneller zugreifen kann als auf den Hauptspeicher. Daher muß das Ziel sein, sein Programm so zusammenzubauen, daß es in diesem Speicher Platz hat, beziehungsweise jene Teile, die häufig verwendet werden, in diesem Speicher Platz haben.
Auch ein kurzer Exkurs über den Linker ist notwendig: Der Linker baut ein Programm so zusammen, wie er die Funktionen im Sourcefile findet, und nach der Reihenfolge der Sourcefiles.
Fügen wir die zwei Exkurse zusammen so folgt daraus, daß Funktionen die sich
häufig gegenseitig aufrufen, auch beim Linkeraufruf nahe bei einander sind.
(Der Linker kann das beim besten Willen nicht wissen!) . Auch ein strip des exekutierbaren Programmes kann
einen Performancegewinn bringen.
Unser Progamm hat im Vergleich zum Lauf ohne Optimierung im Lauf mit -fast auf der ALPHA500 ein fünftel der Zeit gebraucht.
Das Programm berechnet das Potential und 
-Feld auf jenem Rechner, auf
dem die Simulation gestartet wird. Diese Teile wurden wegen des hohen Aufwands
der Portierung nicht parallelisiert.
Im Anschluß daran folgt die Berechnung der einzelnen Trajektorien. Um eine
brauchbare Statistik zu erhalten benötigt man 10.000 bis 100.000 Teilchen.
Als Parallelisierungmodell wurde das BOSS - WORKER Modell hernagezogen.
Der Prozess 0 ist der BOSS. Dieser berechnet am Anfang das -Feld und
verteilt dieses an die WORKER. Ab dann verteilt der BOSS nur mehr die Anzahl
der zu rechnenden Teilchenbahnen.
Um in einem heterogenen Netzwerk alle Rechner gleich zu belasten, werden den Computern jeweils Pakete von unterschiedlicher Größe zugeteilt. Der Sinn besteht darin, daß jeder Rechner für sein Paket etwa die gleiche Zeit benötigt, wie jeder andere Prozessor.
Dazu wird zu Beginn der Simulation jedem WORKER eine vordefinierte Anzahl (z.B. 100) von zu rechnenden Trajektorien zugeteilt. Ab dann wird die Rechenzeit für ein solches Teilchenpaket ermittelt und zusammen mit der Anzahl vom jeweiligen WORKER und dem bisherigen Mittelwert für die Berechnung eines Teilchens die neue Anzahl für sein nächstes Teilchenpaket ausgerechnet.
| Pentium 200 | 1300s |
| Cluster I | 780s |
| ALPHA 500 | 361s |
| Cluster II | 350s |
Dabei ist aber zu beachten, daß es sich nicht um die reinen Prozess-Laufzeiten handelt, sondern um jene Zeiten die zwischen Start und Ende der Trajektorien-Berechnungen vergehen. Diese sind naturgemäß höher als die reinen Prozesszeiten, da auf jeden Knoten immer wieder diverse andere User-Prozesse ausgeführt werden.