MPI

MPI kennzeichnet ein Konzept und eine dazugehörige Schnittstelle mit der Programme auf parallelen Systemen, in diesem Fall sogenannten PC-Clustern, verteilt und ausgeführt werden können. Im folgenden soll ein kleiner Einblick in dieses Interface gewährt werden. Des weiteren steht, in Anlehnung an die Seite Mandelbrotbaum, ein Programm zum Download bereit, welches auf mehreren PC's gleichzeitig eine Bilderfolge durch einen Mandelbrotbaum berechnet.

Cluster:

Hierbei handelt es sich um mehrere über ein Netzwerk verbundene Workstations. Häufig sogar Standard-PC's. Sie haben den Vorteil, dass bereits vorhandene Ressourcen genutzt werden können, bzw. die Anschaffung sehr preisgünstig ist. Außerdem dienen sie häufig als Entwicklungsplattformen für parallele Software, um teure Rechenzeit auf massiv parallelen Systemen zu sparen. Der eindeutige Nachteil dieses Parallelrechnerkonzepts liegt in der Unausgewogenheit von Rechen- und Kommunikationszeit. Bei diesen klassischen Clustern handelt es sich um NoRMA-Systeme.

NoRMA (No Remote Memory Access):

Die einzelnen Prozessoren haben jeweils ihren privaten Hauptspeicher und sind untereinander durch ein Kommunikationsnetzwerk (z.B. Ethernet) verbunden, über das sie Nachrichten austauschen können.
Ein hardwaretransparenter Zugriff auf den Speicher eines anderen Prozessors ist bedingt durch die Verwendung von handelsüblichen PC's nicht möglich. Gemeinsamer Speicher kann nur virtuell zur Verfügung gestellt werden.
Der Vorteil liegt in der guten Skalierbarkeit. Nachteilig ist der Einsatz eines Message-Passing-Programmiermodell, welches den Datenaustausch koordinieren muss.

Distributed Memory oder Message Passing:

Das Message-Passing-Programmiermodell beruht auf der Kommunikation von Prozessen auf unterschiedlichen Prozessoren durch den Versand von Nachrichten zwischen den Rechenknoten.
Die Kommunikation erfordert sowohl die Zeit zur Übermittlung der Nachricht und impliziert zugleich Synchronisation, die viel Zeit kosten kann.Aus diesem Grund ist es Ziel der Parallelisierung, die Kommunikation zwischen den Prozessen (Interprozesskommunikation) möglichst gering zu halten.Insgesamt führt dies dazu, dass das Kommunikationsmuster bei der Programmierung der Anwendung bereits bekannt sein muss, was die Erstellung solcher Programme nicht einfach macht. Zudem besteht ein hohes Risiko für eine Verklemmung, wenn etwa zwei Prozesse endlos auf eine Nachricht vom jeweils anderen Prozess warten. Darüber hinaus tritt bei jeder Kommunikation dieser Art implizit eine Synchronisation auf, obwohl der Sender ja nur eine Information loswerden möchte und unter Umständen direkt weiterarbeiten könnte. Das Erlangen von Informationen von anderen Prozessen ist ohne deren Mitwirkung gar nicht möglich.Trotz all dieser Probleme ist dieses Modell weit verbreitet, da sich auf vielen Systemen keine anderen Modelle mit akzeptabler Effizienz einsetzen lassen (siehe NoRMA und ähnliche Architekturen).
Viele Anwendungen haben aber ein Kommunikationsaufkommen, das sich gut über Message-Passing abwickeln lässt. Inzwischen hat sich eine Programmierschnittstelle als Quasi-Standard für dieses Programmiermodell entwickelt, das sogenannte Message Passing Interface (MPI).
Rechtstehende Abbildung verdeutlicht die Funktionsweise von Distributed Memory. Zwei Prozesse laufen auf unterschiedlichen Prozessoren mit jeweils eigenem lokalen Speicher. Daten werden von den Prozessen über das Verbindungsnetzwerk (z.B. MPI) augetauscht.

Message Passing Interface (MPI):

MPI ist für verschiedene Prozessoren und Betriebssysteme erhältlich. Alle basieren sie auf dem Message Passing Interface Konzept und wurden individuell angepasst. So verwundert es nicht, dass Varianten für Win 9x, Win NT, Linux, Unix aber auch Macintosh erhältlich sind.
Inzwischen zählen nicht nur Universitäten, sondern auch führende Hardwareentwickler wie SGI und IBM zu den Programmierern neuer Implementierungen für firmeneigene Produkte.

Programmiermodell:

Auf jedem Prozessor (im PC-Cluster in der Regel auf jedem PC) wird ein eigenständiger Prozess des Programms gestartet und ausgeführt. Variablen werden lokal gespeichert und die Kommunikation erfolgt mittels der MPI-Funktionen über das Netzwerk.
Identifizierbar sind die einzelnen Prozesse mit Hilfe einer ID-Nr, die den Rang (rank) wiedergeben. Werden mindestens zwei Prozesse gestartet, bildet sich eine Art Client-Server-Struktur. Der Master-Prozess trägt den rank 0. Alle anderen mit rank größer 0 werden als Slave-Prozesse bezeichnet.
Im Allgemeinen ist der Master-Prozess für die Koordination und die Datenverteilung zuständig. Er präsentiert nach erfolgreicher Bearbeitung einer Aufgabe auch das Ergebnis, während die Slaves nur die Verarbeitung der Daten erledigen.
Die Vergabe der rank-Nr erfolgt in der Reihenfolge, in der die Prozesse gestartet werden. Der erste (Master) erhält die 0, der zweite die 1,... Der Master-Prozess wird auch immer auf dem System ausgeführt, auf dem das gesamte Programm gestartet wird.
Als Kommunikator wird die Gesamtheit aller zugehöriger PC's bezeichnet, auf denen die gleichen Prozesse laufen.

Kommunikation:

Der Begriff Message bzw. Nachricht bezeichnet hier das Datenpaket, welches zwischen den einzelnen Prozesses ausgetauscht wird.
Um eine Datenübertragung zu ermöglichen, müssen dem Message Passing System folgende Dinge bekannt sein:

Prozesskontrolle:

Soll ein Programm einem Cluster laufen, ist es notwendig, den Austausch von Nachrichten (Messages) mit Hilfe von MPI zu realisieren. Entsprechend existieren eine Reihe von Befehlen, die diese Aufgaben im Groben übernehmen.
Um das Interface überhaupt nutzen zu können, sind vier entscheidende Befehle in den Quellcode einzubinden:

Beispiel zur Prozesskontrolle:

#include <stdio.h>
#include "mpi.h"
void main(int argc, char *argv[])
{

int numprocs, myid;
MPI_Init(&argc,&argv); // initialisiert MPI
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
// gibt die Anzahl aller Prozesse wieder
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
// gibt die Prozessnummer (Rank) des Prozesses wieder

if (myid == 0) // Master
{

printf("Ich bin der Master, ProzessNr.: %d, %d Prozesse gesamt\n", myid, numprocs);

}
else // Slave
{

printf("Ich bin ein Slave, meine ProzessNr.: %d, %d Prozesse gesamt\n", myid, numprocs);

}

MPI_Finalize(); // beendet MPI

}

Ausgabe:

Ich bin der Master, ProzessNr.: 0, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 1, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 7, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 8, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 9, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 2, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 3, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 4, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 5, 10 Prozesse gesamt
Ich bin ein Slave, meine ProzessNr.: 6, 10 Prozesse gesamt

Startet man dieses kleine Beispiel ergibt sich ungefähr die oben abgebildete Audgabe. Jeder einzelne Prozess wird gestartet und macht nichts anderes, als sein Prozessnummer und die Anzahl der gesamten Prozesse auszugeben. Es wird hierbei immer in nur eine Konsole geschrieben, und zwar in die, auf der das Programm gestartet wurde. Anhand der Prozessnummer '0' lässt sich problemlos der Master identifizieren, der in der Regel das Zusammenspiel der Slaves koordinieren soll.

Punkt-zu-Punkt-Kommunikation:

Eine Message wird generell nur zwischen zwei Prozessen ausgetauscht. Unterschieden wird zwischen Blockierenden und Nichtblockierenden Operationen.
Sendet ein Prozess eine Nachricht und setzt seine Programmausführung erst dann fort, wenn die Übertragung vollständig abgeschlossen wurde, spricht man von synchronem Senden.
Nachteilig ist hierbei die entstehende Wartezeit, in der das Programm bzw. der Prozess steht. Diese Methode erlaubt die Nutzung der Datenbereiche, die die Nachricht gespeichert haben, nach dem Senden. Auch kann so gewährleistet werden, dass die Message ordnungsgemäß übertragen wurde.
Im Gegensatz hierzu steht die Nichtblockierende Kommunikation. Das Programm wird nach Aufruf der Sende-Funktion sofort weiter ausgeführt. Um eine gesicherte Übertragung zu gewährleisten, ist es erforderlich, in gewissen Abständen eine Übertragungskontrolle durchzuführen. Leider kann dies den gleichen Effekt wie eine blockierende Operation haben. Ungünstig ist auch die Tatsache, dass gewisse Datenbereiche nach Aufruf der Sende-Funktion nicht sofort neu genutzt und überschrieben werden können, da Ungewissheit über den Status der Datenübertragung herrscht. Diese Form der Kommunikation wird auch als asynchrones Senden bezeichnet.
Bei beiden Varianten gibt es noch eine optionale Pufferung. Der Unterschied ist der, dass über den Empfangsvorgang nun keine Informationen mehr vorliegen. Sicher ist nur, dass der Sendevorgang abgeschlossen (synchron) oder begonnen hat (asynchron).
Beim Empfangen von Nachrichten unterscheidet man ebenfalls zwischen nicht- undblockierendem Empfangen. Im ersten Fall springt der Prozess in die Empfangsroutine und wartet solange, bis die Übertragung abgeschlossen ist. Erst jetzt wird die Ausführung des Programmcodes fortgesetzt. Dagegen ist im nichtblockierenden Fall über den Sendevorgang nichts bekannt. Der Empfänger wird lediglich in Bereitschaft versetzt, Daten zu empfangen, die dann in einem Empfangspuffer gelangen.

Die vorangegangenen Befehle stellen nur einen kleinen Auszug aus dem Befehlsvorat von MPI dar. Sie reichen aber völlig aus, um nicht nur die ersten Schritte, sondern auch größere Applikationen zu realisieren. Wem dies nicht reichen sollte, mögel einen kurzen Blick in die mitgelieferten Unterlagen wagen.

Beispiel für eine einfache Kommunikation:

#include <stdio.h>
#include "mpi.h"
void main(int argc, char *argv[])
{

int numprocs, myid;
int i;
MPI_Status stat;
MPI_Init(&argc,&argv); // initialisiert MPI
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
// gibt die Anzahl aller Prozesse wieder
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
// gibt die Prozessnummer (Rank) des Prozesses wieder

if (myid == 0) // Master
{

for (i=0; i<numprocs-1; i++)
{

MPI_Send(&i, sizeof(i), MPI_BYTE, i+1, 0,MPI_COMM_WORLD);
printf("Master sendet Wert: %d\n", i);

}
for (i=0; i<numprocs-1; i++)
{

MPI_Recv(&i, sizeof(i), MPI_BYTE, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &stat);
printf("Master empfaengt Wert: %d\n", i);

}

}
else // Slave
{

MPI_Recv(&i, sizeof(i), MPI_BYTE, 0, 0, MPI_COMM_WORLD, &stat);
i*=2;
MPI_Send(&i, sizeof(i), MPI_BYTE, 0, 0,MPI_COMM_WORLD);
printf("Slave %d empfaengt Wert: %d -> sendet 2*%d=%d\n", myid, i/2, i/2, i);

}

MPI_Finalize(); // beendet MPI

}

Ausgabe:

Master sendet Wert: 0
Master sendet Wert: 1
Master sendet Wert: 2
Master sendet Wert: 3
Slave 1 empfaengt Wert: 0 -> sendet 2*0=0
Master empfaengt Wert: 0
Slave 2 empfaengt Wert: 1 -> sendet 2*1=2
Slave 3 empfaengt Wert: 2 -> sendet 2*2=4
Slave 4 empfaengt Wert: 3 -> sendet 2*3=6
Master empfaengt Wert: 2
Master empfaengt Wert: 4

Nach Ausführung des obigen Mehrzeilers ergibt sich ein wie oben ähnliche Ausgabe in der Konsole. Zum Programmablauf lässt sich sagen, dass der Master jedem Slave eine Zahl von '0' beginnend schickt. Der Slave empfängt diesen Wert, verdoppelt ihn und schickt ihn dann zum Master zurück.Aufmerksamen Lesern mag aufgefallen sein, dass in diesem Beispiel der Master den Wert '6' nicht anzeigt. Hierbei handelt es sich um ein Problem in der Ausgabe mittels 'printf', da dies gepuffert wird und nicht mehr rechtzeitig ausgegeben werden kann. Es ist aber ziemlich sicher anzunehmen, dass der Wert dennoch an den Master geschickt wurde.


Installation von MPICH

Kaum vorstellbar, aber MPICH ist sehr einfach installierbar. Einfach die unter MPICH verfügbare mpich.nt.1.2.3.exe ausführen. Das Setup installiert dann die notwendigen Dateien und sorgt dafür, dass die Schnittstelle bei Systemstart automatisch gestartet wird. MPI läuft aktiv im Hintergrund, wenn im Task-Manager der Prozess 'mpd.exe' eingetragen ist.

Ausführen von MPI-basierenden Programmen

Wurde ein Programm erstellt, ist dies zwar häufig direkt und ohne Fehlermeldung startbar, dennoch kann es sich nicht wie geplant verhalten, da die Anbindung mit der Schnittstelle so nicht gegeben ist. Um dies zu erzwingen, werden MPI-Programme folgendermaßen gestartet (einfach unter Win2000 in die Eingabeaufforderung tippen, bzw. Batch-Datei mit folgendem Inhalt erstellen):

c:\MPICH.NT.1.2.3\mpd\bin\mpirun -np 5 -localonly kommunikation.exe

"mpirun" ist das eigentlich zu startende Programm, welches ein paar entscheidende Zeilenparameter braucht. "-np 5" gibt die Anzahl der zu startenden Prozesse an, in diesem Fall wären es eben '5'. "-localonly", wie der Begriff schon sagt, die Prozesse werden lokal auf dem Rechner gestartet. "kommunikation.exe", als letzter Parameter, ist das eigentliche auszuführende Programm.

Möchtet man das Programm, bzw. die Prozesse in einem PC-Cluster verteilt starten, gibt man anstelle der oben genannten Parameter nur den Ort der "config.cfg" an, die man selbst ersellen muss.

c:\MPICH.NT.1.2.3\mpd\bin\mpirun c:\mpi\config.cfg

In ihr sind die Anweisungen vorhanden, wo sich das ausführbare Programm "kommunikation.exe" befindet. Des weiteren werden die Rechner, die zum Cluster gehören unter "hosts" aufgeführt. "pc1 3" ist der erste Eintrag. Auf ihm werden der Master und zwei weitere Slaves gestartet. Somitist klar, dass die Zahl hinter dem Computernamen immer der Anzahl der Prozesse auf dem jeweiligen Rechner entspricht.

exe c:\mpi\kommunikation.exe
hosts
pc1 3
pc2 2
pc3 2
pc4 2

Der obige Text ist in einer Datei namens "config.cfg" abzuspeichern und im Verzeichnis "c:\mpi" abzulegen.
Führt man nun die Cluster-Variante aus, wird erst nach dem Win2000 Benutzernamen und Passwort gefragt. Beide müssen auf jedem Rechner im Cluster identisch sein, ansonsten ist MPI nicht in der Lage, die Prozesse auf den entsprechenden Rechnern zu starten.

Beispielprogramm

Ein etwas komplexeres Programm kann auf der Seite Mandelbrotbaum heruntergeladen werden. Dort findet sich auch eine generelle Einleitung in das Thema Mandelbrotbaum.
Das Programm berechnet eine Sequenz von Teilbildern aus einem Mandelbrotbaum. Diese aneinandergehängt, ergeben eine Art "Fahrt" in die Tiefen des Fraktals. Um die Geschwindigkeit zu erhöhen, werden die Berechnungen aufgeteilt und auf mehreren PC's, eben in einem Cluster-Verbund abgearbeitet.
Die generelle Arbeitsweise ist in unten gegebener Abbildung verdeutlicht.

Download

MPICH

Sourcecode + ausführbare Datei Beispiel 'Prozesskontrolle'

Sourcecode + ausführbare Datei Beispiel 'einfache Kommunikation'