Embed Size (px)
Citation preview
Programmierung paralleler Algorithmen mit MPI
Eine Einführung in dasBetriebssystempraktikum
Parallelverarbeitung
Lehrstuhl für Betriebssysteme
Parallelverarbeitung
Die Grundidee der Parallelverarbeitung ist es, ein gegebenes Problem, bzw. einen gegebenen Algorithmus so auf mehrere Rechner, bzw. Prozessoren zu verteilen, dass die Laufzeit des Algorithmus entsprechend der Prozessorenanzahl sinkt.
Lehrstuhl für Betriebssysteme
Parallele Algorithmen
Parallele Algorithmen
Aber wie ???
Die Frage ist nun jedoch, wie man einen solchen Algorithmus (um-) programmieren kann, dass er von mehreren Prozessoren gleich- zeitig abgearbeitet werden kann.Dazu müssen unabhängige Teilaufgaben des Algorithmus auf die Prozessoren verteilt werden.
Lehrstuhl für Betriebssysteme
Nachrichtenaustausch
Jeder Prozessor löst also eine Teil des gesamten Problems.Früher oder später müssen sich die Prozessoren dann die Lösungen ihrer Teilaufgaben austauschen, damit aus den Teillösungen die Gesamtlösung entstehen kann.Allgemein nennt man dies einen „Nachrichtenaustausch“.
Lehrstuhl für Betriebssysteme
Beispiel: Addition von Zahlen
Beispiel: es sollen 20 Zahlen (grün) aufsummiert werden.Diese Arbeit soll von vier Prozessoren parallel durchgeführt werden.
Jeder Prozessor addiert dazu zunächst seine fünf Zahlen.
+ + + +
Proc0 Proc1 Proc2 Proc3
Lehrstuhl für Betriebssysteme
Beispiel: Addition von Zahlen
Dann werden die Teilsummen baumartig an die Nachbarprozes-soren weitergeleitet und wieder addiert, bis schließlich das Ender-gebnis vorliegt.
+
+
+
+ +
+
+
Lehrstuhl für Betriebssysteme
Beispiel: Addition von Zahlen
Man erkennt, dass so die Laufzeit von 19 benötigten Additionen im seriellen Fall auf die Zeit von 4+3=7 Additionen im parallelen Fall reduziert werden konnte.Hinzugekommen ist jedoch die zusätzliche Zeit für den Nachrichten-austausch!
+
+
+
+ +
+
+
4
+1
+1
+1
19
Lehrstuhl für Betriebssysteme
Message Passing Interface
Nachrichtenaustausch
Aber wie ???
Wie programmiert man nun jedoch diesen Nachrichtenaustausch?
Im Bereich der Parallelverarbeitung hat sich dazu in den letzten Jahren ein dominierender Standard herausgebildet:Das Message-Passing-Interface, kurz: MPI
Lehrstuhl für Betriebssysteme
Message Passing Interface
Die Programmierung erfolgt dabei durch den Aufruf expliziter Sende- und Empfangsfunktionen (z.B. MPI_Send und MPI_Recv).
Hier oben ist z.B. das Muster einer sog. Ping-Pong-Kommunikation zwischen zwei MPI-Prozessen einmal dargestellt.
Proc0 Proc1
Berechnung
MPI_Send()
Berechnung
MPI_Recv()
MPI_Send()MPI_Recv()
Lehrstuhl für Betriebssysteme
Message Passing Interface
Dies ist der entsprechende C-Code zu einer solchen PingPong-Kommunikation mit MPI.Wie man erkennt, besitzt jeder Prozessor in der MPI-Umgebung eine eigene ID (den sog. rank), mit Hilfe derer er identifiziert und adressiert werden kann.
MPI_Get_rank(&my_rank, …);…if(my_rank==0) { /* ich bin Proc0: */ MPI_Send(&SendePuffer,…,1,…); /* <- sende an Proc1 */ MPI_Recv(&EmpfangPuffer,…,1,…); /* <- empfange von 1 */}else { /* ich bin Proc1: */ MPI_Recv(&EmpfangPuffer,…,0,…); /* <- empfange von 0 */ MPI_Send(&SendePuffer,…,0,…); /* <- sende an Proc0 */}
Lehrstuhl für Betriebssysteme
Das physikalische Medium
Der MPI-Standard macht keinerlei Aussage über das physikalische Medium, über welches die Nachrichten übertragen werden.So sind z.B. parallele MPI-Programme sowohl auf gekoppelten Rechnern (sog. Cluster), als auch auf speziellen Multiprozessor- Machinen (z.B. SMP-Server) lauffähig.
SHARED MEMORYTCP
CPU 0 CPU 1
Host 0
Host 1
Lehrstuhl für Betriebssysteme
Das physikalische Medium
In dem einen Fall funktioniert dabei der Nachrichtenaustausch über das koppelnde Netzwerk (z.B. TCP über Ethernet).In dem anderen Fall gelangen die Nachrichten dann z.B. über den gemeinsamen Hauptspeicher (shared memory) von einem Prozessor zum anderen.
SHARED MEMORYTCP
CPU 0 CPU 1
Host 0
Host 1
Lehrstuhl für Betriebssysteme
Betriebssystempraktikum
Im Betriebssystempraktikum „Parallelverarbeitung“ kommt neben TCP (auf einem unserer Intel-Cluster) und Shared-Memory (auf einer Sun-Enterprise mit vier Prozessoren) auch eine weitere Variante zum Einsatz: das Scalable Coherent Interface, kurz: SCI, welches den Aufbau sog. speichergekoppelter Cluster ermöglicht.
TCP
SHMEM
SCI
