MPI-1, MPI-2 und PVM - wi1.uni- · PDF fileMPI-1 Gruppen und Kommunikatoren (1) • Prozesse k¨onnen in Gruppen eingeteilt werden • Nutzlich, um eine Gruppe Daten generieren zu

MPI-1, MPI-2 und PVM

Seminar”Parallele Programmierung“

Sommersemester 2003

Bjorn Eilers

– Typeset by FoilTEX – 1

Gliederung

1. Einleitung

2. MPI-1

3. MPI-2

4. PVM

5. Vergleich MPI und PVM


Einleitung

• Vorstellung”Message Passing Interface“ (Versionen MPI-1 und MPI-2) sowie

”Parallel Virtual Machine“ (PVM)

• Bibliotheken zur parallelen Programmierung

• Grundlage: Message-Passing Modell

– Prozesse kommunizieren in parallelem Netzwerk per Nachrichtenaustausch– Nachrichten konnen Direktiven und/oder Daten enthalten

• Betrachtung von:

– Programmaufbau– Kommunikationsmethoden– Rechenoperationen– Gruppierungs- und Synchronisationsmethoden– Besonderheiten


MPI-1Allgemeines

• Gedacht als Standard fur Message-Passing-Bibliotheken

• Gegrundet 1992 durch MPI-Forum

• Bibliotheken fur C und Fortran-77


MPI-1Programmaufbau (1)

• Alle Rechner konnen gleiches Programm ausfuhren

• Instanzen arbeiten i.d.R. auf verschiedenen Daten(Single Program, Multiple Data)

• Master-Slave-Aufbau empfohlen:

– Master verteilt Aufgaben, fuhrt Ergebnisse zusammen, signalisiert Programmende– Slaves leisten eigentliche Rechenarbeit

• Auch Moglichkeit gleichberechtigter Prozesse


MPI-1Programmaufbau (2)

Grundsatzliche Struktur eines Prozesses:

1. MPI-Programm aufrufen

2. Initialisierung des MPI-1-Interfaces

3. Feststellung eigener ID/Rang und Anzahl weiterer MPI-Prozesse

4. Bei Master-Slave-Aufbau:

• Prozess mit ID=0: Master• Prozesse mit ID6=0: Slaves

5. Prozesse fuhren Berechnungen durch und kommunizieren Ergebnisse

6. Nach Abschluß aller Berechnungen Deinitialisierung des MPI-1-Interfaces �


MPI-1Kommunikationsmethoden (1)

• Einfache Form der Kommunikation uber blockierende Sende- und Empfangsopera-tionen �

• Prozess sendet Nachricht bestimmter Lange aus Datenpuffer an uber Rang identi-fizierten Prozess

• Zielprozess ruft Empfangsmethode auf, um Nachricht zu erhalten

• Beide Operationen blockieren aufrufenden Prozess, bis Nachrichten vollstandigausgetauscht⇒ Vorteil: Datenpuffer konnen nicht unbeabsichtigt uberschrieben werden⇒ Nachteil: Gefahr von Deadlocks �



• Bei hohem Kommunikationsaufkommen Senden und Empfangen je einer Nachrichtmit einem Aufruf

• Nutzung von zwei Datenpuffern; wenn ein Datenpuffer gewunscht, wird Sendepuffermit empfangener Nachricht uberschrieben

• Auch Moglichkeit, Nachrichten an alle Prozesse zu senden (Broadcast) �



• Bei blockierenden Sendeoperationen keine Verpflichtung, Nachrichten zu puffern,wenn Empfanger beschaftigt

• Explizite Pufferung aber moglich:

1. Prozess bereitet Puffer fur Nachrichtenspeicherung vor2. Verschicken der gepufferten Nachricht (wird von normalem MPI_RECV empfan-

gen)3. Puffer freigeben �



• Vermeidung von Deadlocks mit Hilfe nicht-blockierender Kommunikation

• Bis zu drei Befehle, um Nachricht zu ubermitteln:

1. Initiierung der Nachrichtenubertragung2. Uberprufung der Nachrichtenubertragung:

– Blockierend– Nicht-blockierend

• Prufmoglichkeit fur eine bestimmte, irgendeine, oder alle Nachrichten �


MPI-1Gruppen und Kommunikatoren (1)

• Prozesse konnen in Gruppen eingeteilt werden

• Nutzlich, um eine Gruppe Daten generieren zu lassen, auf denen zweite GruppeBerechnungen ausfuhren kann

• Prozesse innerhalb einer Gruppe haben eindeutigen Rang

• Ohne explizite Gruppeneinteilung hat Prozess Vorgabegruppe

• Mitglieder einer Gruppe haben gemeinsamen Kommunikator :Bereich, in dem Gruppenmitglieder gemeinsame Rechenoperationen ausfuhren undauf topologische Strukturen zuruckgreifen konnen

• Kommunikation zwischen Kommunikatoren explizit per Nachrichtenaustausch


MPI-1Gruppen und Kommunikatoren (2)

• Mengenoperationen auf Gruppen:

– Gruppen erzeugen– Vereinigen, Schnittmenge oder Differenzmenge bilden– Mitglieder entfernen– Gruppen auflosen

• Operationen auf Kommunikatoren:

– Kommunikator erzeugen– Duplizieren oder in disjunkte Menge neuer Kommunikatoren aufsplitten– Kommunikator auflosen


MPI-1Topologien (1)

• Topologie: Art, wie Prozesse miteinander verbunden sind

• Moglichkeit, virtuelle Topologien fur Programm zu definieren⇒ Abbildung eines Kommunikators auf raumliche Struktur (kann von physischerTopologie abweichen)

• Bestimmung des Kommunikationswegs einer Nachricht durch Benutzer⇒ ohne virtuelle Topologie kein Ruckschluss auf Weg der Nachricht

• Zwei vordefinierte Topologien:

– Kartesische Topologie– Graphen-Topologie


MPI-1Topologien (2)

• Kartesische Topologie: Anordnung der Prozesse in Raum mit n Dimensionen

• Aufteilung einer Dimension in weitere Bereiche

• Adressierung uber Koordinaten

• Rangvergabe von kleinsten Koordinaten aufwarts(also erhalt z.B. (0,0) den Rang 0)

• Anordnung der Bereiche pro Dimension periodisch oder nicht

– Bei periodischer Anordnung letzter Bereich Nachbar von erstem Bereich (z. B.fur Matrixmultiplikation)

– Bei nicht-periodischer Anordnung: Erster Bereich kein Vorganger, Letzter keinNachfolger


MPI-1Topologien (3)

• Gute Eignung fur haufigen Nachrichtenaustausch mit benachbarten Prozessen

– Nachbarn feststellen– Nachrichtenaustausch dann z. B. uber MPI_SENDRECV

(0,0)

(0,1)

(0,2)

(1,0)

(1,1)

(1,2)

(2,0)

(2,1)

(2,2)

0 1 2

3 4 5

6 7 8

(0) (1) (2)

0 1 2


MPI-1Topologien (4)

• Graphen-Topologie: Anordnung der Prozesse als Graph

• Prozesse sind Knoten, Kommunikationswege sind Kanten

• Beliebige Moglichkeit der Definition(z. B. Baum oder zyklischer Graph)

• Feststellen der Nachbarn uber MPI_GRAPH_NEIGHBORS

0

2

3 4

1

65

3

1 2

4

0


MPI-1Gemeinsame Rechenoperation (1)

• Mitglieder einer Gruppe konnen gemeinsame Rechenoperationen ausfuhren

• Einteilung in zwei Kategorien:

– Arithmetische Sammeloperationen– Sammel- und Verteiloperationen (Scattering/Gathering)

• Arithmetische Rechenoperationen reduzieren Daten aller Prozesse zu Gesamtergeb-nis (Aufruf meist durch Master-Prozess)

• Vordefinierte Reduktionsfunktionen umfassen:Summe, Produkt, logische und bitweise boolesche Operationen, Minimum undMaximum �



• Gathering als Operation, um Daten zusammenzufuhren:

– Alle Prozesse senden Nachricht an Masterprozess, die dieser in Speicher anordnet– Vector Gathering fur Nachrichten unterschiedlicher Lange

• Mit All Gathering erhalten alle Prozesse anstelle des Masterprozesses Daten

A

B

C

D

A B C DP0

P1

P2

P3

P0

P1

P2

P3



• Scattering, um Daten an Prozesse zu verteilen

– Normales Scattering verteilt Daten des Masterprozess an alle Prozesse in derGruppe

– Vector Scattering fur Nachrichten variabler Lange

• Hybride Methode MPI_ALLTOALL erlaubt gleichzeitiges Sammeln und Verteilen(All-to-all-Scatter/Gather)

A

B

C

D

A B C DP0

P1

P2

P3

P0

P1

P2

P3

A1 A2 A3 A4

B1 B2 B3 B4

C1 C2 C3 C4

D1 D2 D3 D4

A1 B1 C1 D1

A2 B2 C2 D2

A3 B3 C4 D3

A4 B4 C4 D4

P0

P1

P2

P3

P0

P1

P2

P3

All to All


MPI-1Synchronisation

• Datenaustausch zwischen Prozessen zu gemeinsamem Zeitpunkt durch Barriereerleichtert

• Aufrufender Prozess blockiert solange, bis alle Prozesse im Kommunikator ebenfallsBarriere aufrufen �

P0 P1 P2 P3

Barriere


MPI-2Allgemeines

• Verbesserung von MPI-1

• Uberwiegend Detailanderungen

•”Echte“ Neuerungen:

– Unterstutzung fur C++ und Fortran– Prozessmanagement– Portbasierte Kommunikation– Einseitige Kommunikation– Threadunterstutzung– Dateioperationen


MPI-2Prozessmanagement

• In MPI-1 nur rudimentares Prozessmanagement

• In MPI-2 erweitert:

– Prozess kann neue Prozesse erzeugen (Spawning)(entweder einen bzw. mehrere Kopien des gleichen Prozesses oder eine Mengevon Prozessen)

– Neu erzeugte Prozesse erzeugendem Prozess untergeordnet


MPI-2Portbasierte Kommunikation

• Moglichkeit, Kommunikation zwischen Prozessen in verschiedenen Kommunikato-ren (auch in verschiedenen Programmen) herzustellen

• Portbasierte Client-Server-Verbindungen

• Prozess 1 fungiert als Server

• Prozess 2 meldet sich als Client an

• Adressierung uber allgemein gultige Internet-Adressen (host:port)

1. Server offnet Port und warten auf eingehende Verbindungsanfragen2. Client stellt Anfrage an Server3. Server nimmt eingehende Anfrage des Clients an4. Server schließt Verbindung �


MPI-2Einseitige Kommunikation (1)

• Prozess kann auf Daten eines Anderen zugreifen und diese manipulieren

• Zugreifender Prozess vergibt Parameter des Kommunikationsvorgang (remote me-mory access)

• Entfernter Prozess nimmt nicht explizit an Kommunikation teil, muss aber”Fens-

ter“ auf Daten offnen

• Kommunikation dann uber MPI_PUT (uberschreibt Daten in entferntem Speicher)und MPI_GET (liest Daten aus)Wenn Daten nicht zu uberschrieben: Akkumulationsfunktion



• Synchronisierung bei einseitiger Kommunikation notig, um Inkonsistenzen zu ver-meiden

• Entfernter Prozess stellt Berechnungen fur Dauer der Fensteroffnung ein(window exposure epoch)

• Ablauf:

1. Entfernter Prozess offnet Fenster2. Wartet auf Beendigung der ein-

seitigen Kommunikation3. Zugreifender Prozess beginnt Zu-

griff4. Zugriff wird abgeschlossen5. Entfernter Prozess schließt Fens-

ter

MPI_WIN_START

MPI_PUT

MPI_WIN_COMPLETE

MPI_WIN_POST

MPI_WIN_WAIT

... lokale Operationen ...

Proz

ess

1

... lokale Operationen ...

Proz

ess

2



• Auch Moglichkeit fur Barrieren (hier:”Zaune“)

• Blockiert entfernte Prozess, bis alle entfernten Speicherzugriffe beendet

• Weitere Moglichkeit uber Prozessperre und -freigabe ahnlich 2PL bei Daten-banktransaktionen


MPI-2Threadunterstutzung

• Unterstutzung fur Prozesse mit ≥ 1 Thread

• Zusatzliche Anforderungen an Implementierung:

– Alle MPI-Funktionen thread-sicher– Bei blockierender Kommunikation darf nur aufrufender Thread blockieren

• Bei Initialisierung des MPI-Interfaces Thread-Unterstutzung explizit anfordern


MPI-2Dateioperationen

• Unterstutzung fur verteilte Dateioperationen

• Datei wird kollektiv von Prozessen einer Gruppe verwaltet und bearbeitet (i.d.R.aber sequentielle Abarbeitung der Anforderungen)

• Ubliche Low-Level-Operationen:

– Offnen und Schließen von Dateien– Blockierendes Lesen und Schreiben von Daten– Veranderung des Positionszeigers innerhalb der Datei

• Zusatzlich noch nicht-blockierende Schreib- und Leseoperationen

• Methoden, um gleichzeitiges Lesen und Schreiben fur alle Prozesse zu erlauben


PVMAllgemeines

•”Beiprodukt“ einer Forschungsreihe zum verteilten Rechnen

• Grundidee: Alle Rechner im parallelen Netzwerk als virtuelle Maschine ansehen

– Programm fur VM besteht aus Tasks (Task = Prozess)– Task lost Teil des betrachteten Problems– Abstraktion von unterliegender Hardware– Moglichkeit, bestimmtem Rechner Task zuzuweisen (z. B. wg. geeigneter Pro-

zessorarchitektur)

• Drei Teile:

1. pvm3d-Daemon (im Hintergrund laufend): Infrastruktur fur VM2. pvm-Kommandozeilenapplikation: Aufruf Programm, Konfiguration VM3. PVM-Programmbibliothek: Routinen fur Kommunikation, Tasksteuerung, etc.

• Unterstutzung fur C, C++, Fortran


PVMProgrammaufbau

• Master-Slave-Anwendungen(getrennte Programmierung von Master und Slaves empfohlen, aber auch SPMDmoglich)

• Grundsatzlicher Programmablauf:

1. Master-Task uber pvm-Anwendung starten2. Master erzeugt Slaves3. Slaves fuhren Berechnungen durch und kommunizieren Ergebnisse

(eventuell Erzeugung weiterer Tasks)4. Nach Beendigung verlasst Task VM �


PVMKommunikationsmethoden (1)

• Zwei Arten der Kommunikation:

– Blockierende Kommunikation– Nicht-blockierende Kommunikation

• Sendebefehle immer blockierend:

– Senden einer Nachricht bzw. eines Arrays von Daten– Senden einer Nachricht an Liste von Tasks (Multicast)

• Wichtig: Zuvor Sendepuffer vorbereiten (gewahrleistet u. a. korrekte Kodierung vonNachricht in heterogenen Netzen - z. B. ASCII-Nachricht an EBCDIC-Mainframe)

• Daten vor Versand zuerst in Nachricht”packen“


PVMKommunikationsmethoden (2)

• Kommunikationsart durch Empfangsbefehl festgelegt:

– Tasks blockieren fur Dauer des Nachrichtenaustauschs– Nachrichtenaustausch nicht-blockierend– Time-out fur Nachricht festlegbar (nach Ablauf gilt Nachricht als nicht empfan-

gen)⇒ Grosser Wert simuliert blockierenden Empfang⇒ Wert 0: nicht-blockierend �


PVMGruppen

• Rudimentare Gruppenfunktionalitat:

– Task zu Gruppe hinzufugen– Task aus Gruppe entfernen

• Innerhalb einer Gruppe moglich:

– Broadcasts– Synchronisation– Arithmetische Rechenoperationen


PVMSynchronisation

• Wenn Task Mitglied einer Gruppe, Synchronisation uber Barriere moglich

• Unterschied zu MPI:Optionale Angabe der Anzahl von Tasks, die zu Losung von Barriere notig �


PVMArithmetische Rechenoperationen

• Innerhalb einer Gruppe Reduktion von Daten zu gemeinsamem Ergebnis

• Berechnungsfunktion als Parameter an Reduktionsfunktion zu ubergeben

• Vordefinierte Funktionen umfassen Summe, Produkt, Minimum und Maximum

• Wichtig:Reduktion arbeitet nicht-blockierend⇒ Fehler moglich, wenn Gruppenmitglieder wahrend Reduktion Task beitreten oderverlassen


PVMDynamische Konfiguration

• Mit PVM moglich, wahrend Programmausfuhrung Konfiguration der VM zu andern:

– Rechner zu VM hinzufugen– Rechner aus VM loschen

Beispiel:Fur Berechnungen in einigen Universitaten werden uber Nacht freistehende Worksta-tions zur Unterstutzung der VM herangezogen (

”Super Computers at Night“) und am

nachsten Morgen wieder aus der VM entfernt.


Vergleich von MPI und PVMVorteile von MPI

• Von Forschung und Wirtschaft akzeptiertes Modell

• Implementierungen fur viele Hardwarearchitekturen verfugbar

• Machtige Bibliotheksfunktionen verringern zusatzlichen Implementierungsaufwand

• Sehr effiziente Kommunikationsmethoden (z. B. Gathering und Scattering)

• Dennoch moglich, auch kompakte Programme zu schreiben

• Da nur ein Programm fur alle Rechner, besonders gute Eignung fur homogeneNetzwerke


Vergleich von MPI und PVMVorteile von PVM

• Intuitiveres Modell eines Parallelrechners erlaubt Abstraktion von unterliegenderHardware

• Vereinfachte Programmierung von parallelen Anwendungen durch leicht zu lernen-den API-Befehlssatz

• Durch Abstraktion und Konversionsfahigkeiten bessere Eignung fur heterogeneNetzwerke

• Dynamische Konfiguration ermoglicht es, wahrend Berechnung Lasten zu verteilen

• Aufteilung der Tasks auf mehrere Programme erleichtert Wartung und Erweiterung


Vergleich von MPI und PVMFazit

• Beide Modelle finden Anwendung

• MPI:

– Großere Verbreitung, da Standard– Umfangreiche Funktionalitat⇒ Gute Eignung fur komplexe Projekte mit hohem Kommunikationsaufkommen

• PVM:

– Schnelle Entwicklung kleinerer paralleler Anwendungen– Geschwindigkeit erfolgt auf Kosten komplexer Bibliotheksfunktionen– Grosse Verbreitung vor allem in Linux-Community

(Implementierungen u. a. bei RedHat und SuSE mitgeliefert)


Diskussion

Noch Fragen?


Ende

Vielen Dank fur Ihre Aufmerksamkeit!


Anhang

Anhang: Programmbeispiele


MPI-1Beispiel 1: Grundstruktur ⇐

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

bool done=false;int myID, numProcesses;MPI_Init(&argc, &argv);MPI_Comm_rank(MPI_COMM_WORLD, &myID);MPI_Comm_size(MPI_COMM_WORLD, &numProcesses);while (!done) {

if (myID == 0) {// ... fuhre Masteraktionen aus

} else {// ... fuhre Slaveaktionen aus// kommuniziere Ergebnisse

}}MPI_Finalize();


}


MPI-1Beispiel 2: Blockierendes Senden/Empfangen ⇐

...if (myID == 0) {

int* buf = 5;MPI_Send(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD);

} else {int* buf;int status;MPI_Recv(buf, 1, MPI_INTEGER, 0, 0, MPI_COMM_WORLD, status);printf("Received integer: %x\n", buf);

}...


MPI-1Beispiel 3: Deadlocks ⇐

...if (myID == 0) {

int* buf = 5;int status;MPI_Recv(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD, status);MPI_Send(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD);

} else {int* buf = 3;int status;MPI_Recv(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD, status);MPI_Send(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD);

}...


MPI-1Beispiel 4: Weitere Kommunikationsmethoden ⇐

...if (myID == 0) {

int* buf = 5;int status;MPI_SendRecv(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD, status);

} else {int* buf = 3;int status;MPI_Recv(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD, status);MPI_Send(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD);

}...


MPI-1Beispiel 5: Gepufferte Kommunikation ⇐

...if (myID == 0) {

int* buf = 5;MPI_Buffer_attach(buf, 1);MPI_Bsend(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD);MPI_Buffer_detach(buf, 1)

} else {int* buf;int status;MPI_Recv(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD, status);

}...


MPI-1Beispiel 6: Nicht-blockierende Kommunikation ⇐

...int request;if (myID == 0) {

int* buf = 5;MPI_Isend(buf, 1, MPI_Integer, 1, 1, MPI_COMM_WORLD, &request);

} else {int* buf;int status;int flag=0;while (flag==0) {

MPI_Testany(request, &flag, status);}MPI_IRecv(buf, 1, MPI_Integer, 0, 0, MPI_COMM_WORLD, status, request);

}...


MPI-1Beispiel 7: Reduktion ⇐

...int ergebnis, teilErgebnis;if (myID == 0) {

...// Ende der Berechnungen: Gesamtergebnis zusammenfuhrenint ergebnis;MPI_Reduce(&teilErgebnis, &ergebnis, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

} else {// berechne teilErgebnisteilErgebnis = ...;MPI_Reduce(&teilErgebnis, &ergebnis, 1, MPI_INT, MPI_SUM, 0, MPI_COMM_WORLD);

}...


MPI-1Beispiel 8: Barriere ⇐

...if (myID == 0) {

... // auch Master muss Barriere aufrufenMPI_Barrier(MPI_COMM_WORLD);...

} else {// berechne DatenMPI_Barrier(MPI_COMM_WORLD);// Daten austauschen

}...


MPI-2Beispiel 1: Client-Server-Kommunikation ⇐

...// Server "Erwin":MPI_Comm intercomm;MPI_Open_port(MPI_INFO_NULL, "erwin:12345");MPI_Comm_accept("erwin:12345", MPI_INFO_NULL, 0, MPI_COMM_SELF, &intercomm);// kommuniziere mit Prozess uber intercommMPI_Close_port("erwin:12345");

// Client:MPI_Comm intercomm;MPI_Comm_connect("erwin:12345", MPI_INFO_NULL, 0, MPI_COMM_SELF, &intercomm);...


PVMBeispiel 1: Grundstruktur

// Master:#include "pvm3.h"

main() {int cc = pvm_spawn("slave", (char**)0, 0, "", 1, &taskID);if (cc == 1) {

// initialisiere und versende Slavedaten}pvm_exit();

}


PVMBeispiel 1: Grundstruktur ⇐

// Slave:#include "pvm3.h"

main() {int parentID = pvm_parent();// empfange Masterdaten// berechne etwas// kommuniziere Ergebnissepvm_exit();

}


Documents

MPI-1, MPI-2 und PVM - wi1.uni- · PDF fileMPI-1 Gruppen und Kommunikatoren (1) • Prozesse k¨onnen in Gruppen eingeteilt werden • Nutzlich, um eine Gruppe Daten generieren zu