mpi

Danke!

Literatur

Dorr B. J., Lee J.-H., Lin D., Suh S. Efficient Parsing for Korean and English: A Parameterized Message Passing Approach. In Computational Linguistics, Vol. 21, Num. 2, MIT Press, Boston 1995.

Hennesey, J. L., Patterson, D. A. Computer Architecture, Fifth Edition: A Quantitative Approach. Morgan Kaufmann, Burlington 2011.

Lin, D., Goebel, R. Context-free Grammar Parsing by Message Passing. In Proceedings of PACLING-93. Vancouver, 1993.

MacKay, D. J.C. Information Theory, Inference, and Learning Algorithms. Campbridge University Press, Campbridge 2003.

Radenski, A. Shared Memory, Message Passing, and Hybrid Merge Sorts for Standalone and Clustered SMPs. PDPTA’11, the 2011 International Conference on Parallel and Distributed Processing Techniques and Applications. CSREA Press, Las Vegas 2011.

Rauber T, Günger G. Parallel Programming: for Multicore and Cluster Systems. Springer Berlin Heidelberg, 2010.

Rauber T, Günger G. Parallele Programmierung. Springer Berlin Heidelberg, 2012.

Rolfe, T. A Specimen of Parallel Programming: Parallel Merge Sort Implementation. In ACM Inroads, Vol. 1, Issue 4. ACM, New York 2012.

MPP: Beispiele

Graphen: Counting

Language-Parsing problem

Lin D., Goebel R. Context-Free Grammar by Message-Passing

Ziel: für einen beliebigen Satz die syntaktische Struktur zu bilden

Kontext-freie Grammatik

Seit 1997 ist eine zweite Version des MPI-Standards verfügbar, die einige Erweiterungen zu dem weiterhin bestehenden MPI-1.1 Standard hinzufügt. Zu diesen Erweiterungen gehören unter anderem

• eine dynamische Prozessverwaltung, d.h. Prozesse können nun zur Laufzeit erzeugt und gelöscht werden
• [paralleler] Zugriff auf das Dateisystem
• einseitige Kommunikation
• Spezifikation zusätzlicher Sprachschnittstellen (C++, Fortran 90)

<N, O, T, s, P, L>:

N - Nichterminalsymbole

O - Pre-terminalsymbole (Wortarten); O ist eine Untermenge von N

T - Terminalsymbole; T ist disjunkt mit N

s - Startzustand

P - die Menge der Produktionen

L - Wörterbuch (w, p)

Was machen wir?

1. Wir bilden einen Graph.

Problem: Soldaten marschieren im Nebel. Wie kann der Kommandeur wissen, ob niemand verloren ist?

Schlechte Lösung: Jeder Soldat muss jede Minute schreien , dass er mitmarschiert.

Bessere Lösung: global function

2. Die Knoten unterhalten miteinander mit den Nachrichten

3. Für den Satz markieren wir, welche Position welches Wort besetzt.

iii

Grammatik

Graph

Wie funktioniert es:

1. Die Nachrichten sind Intervalle, die von unten nach oben übergeben werden

2. Jeder Knoten sammelt die Paare <Nachricht, Label der Kante, mit der diese Nachricht angekommen ist>

3. Produktionsknoten können neue Paare aus zwei angekommenen Paaren <m, l> und <n, k> erzeugen, wenn:

• es i, j, k existieren: m = [i, j] und n = [j, k]
• k-l=1

4. Wenn Startsymbol das Intervall [0, n] bekommt, bedeutet das, das eine syntaktische Struktur für den Satz gefunden ist.

Beste Lösung: MPP. Alle Soldaten in Gruppen zu bilden. Dadurch entsteht ein Graph

wie die Nachrichten übergeben wurden

was am Ende bleibt

Graphen: Path-counting

Sortieralgorithmen

Sortieralgorithmen laufen schneller beim Benutzen von MPP

Es gibt 2 Punkte (A und B) auf der Ebene. Wie viele Wege von A nach B gibt es?

Viele klassische Sortieralgorithmen haben parallelisierte Version

MPI-2

Beispiel: Mergesort

Schlechte Lösung: alle Wege einfach zählen

Gute Lösung: Message-Passing. Schicke „1“ aus A. Wenn ein Knoten Nachrichten von allen seinen oberen und linken Nachbarn bekommt, dann schickt er die Summe von allen diesen Zahlen weiter unten und rechts.

Weitere Probleme, die man mit MPP lösen kann: Random path sampling, Finding the lowest-cost path

Es gibt auch besondere parallele Meggesort-Varianten, z.B. Odd-even Mergesort and Bitonic Mergesort. Die beiden haben die Komplexität O(log n).

2

Technisches

Bibliotheken:

• MPI (Message-Passing Interface)

Programmiersprachen: C, C++, Fortran-77, Fortran-95

MPI_IDENT

MPI_SIMILAR

MPI_UNEQUAL

int MPI_Group_compare

MPI_IDENT

MPI_CONGRUENT

MPI_SIMILAR

MPI_UNEQUAL

int MPI_Group_size

int MPI_Group_rank

Das Duplizieren eines Kommunikators

int MPI_Comm_create

int MPI_Comm_size

int MPI_Comm_rank

int MPI_Comm_compare

int MPI_Comm_dup

int MPI_Comm_free

int MPI_Comm_split

int MPI_Group_excl

• Parallel Virtual Machine

Erzeugung einer Untergruppe

Löschen der Prozesse

int MPI_Group_incl

Allgemeines

erlauben die Ausführung von Punkt-zu-

Punkt-Kommunikation zwischen zwei Prozessgruppen

int MPI_Group_difference

Kommunikatoroperationen

erlauben die Ausführung beliebiger kollektiver Kommunikationsanweisungen auf einer Gruppe von Prozessen

int MPI_Group_intersection

• mpiJava

inter

int MPI_Group_union

intra

Gruppenoperationen

Kommunikatoren

Klassifikation der Kommunikatoren

1. Message-Passing Programmierung (weiter MPP) ist eine Model die auf die Abstraktion von dem parallelen Rechnern basiert, wobei:

• jeder Prozessor seinen eigenen Speicherplatz hat;

• es keinen globalen Speicher gibt;

2. MPP wird mit einem Set von Prozessen realisiert.

• jeder Prozessor zu jedem anderen eine Nachricht (message) schicken kann.

• Gruppe ist eine geordnete Menge von Prozessen, wobei jedem dieser Prozesse innerhalb der Gruppe einen Rang bezeichnet wird.
• ein Prozess kann mehreren Gruppen angehören und hat bzgl. dieser Gruppen evtl. verschiedene Range
• Darstellung und die Verwaltung von Gruppen wird vom MPI-System übernommen.
• Jede Punkt-zu-Punkt-Kommunikation und jede kollektive Kommunikation in MPI findet innerhalb eines Kommunikationsgebietes statt.

• Jeder Prozess hat einen eigenen lokalen Speicher

Wichtige Begriffe

• Gewöhnlich ist die Anzahl von den Prozessoren fixiert, wenn das Programm startet

Blockierende vs. Nichtblockierende Operationen

• Eine Operation heißt blockierend, falls die Rückkehr der Kontrolle zum aufrufenden Prozess bedeutet, dass alle Ressourcen (z. B. Puffer), die für den Aufruf benötigt wurden, erneut für die anderen Operationen benutzt werden können.

Prozessgruppen und Kommunikatoren

• Eine Operation heißt nichtblockierend, falls die aufgerufene Kommunikationsanweisung die Kontrolle zurückgibt, bevor die durch ausgelöste Operation vollständig abgeschlossen ist und bevor eingesetzte Ressourcen wieder benutzt werden dürfen.

Message-Passing

Synchrone vs. asynchrone Kommunikation

Im sendbuf stellt jeder Prozess für jeden anderen Prozess einen Datenblock mit sendcount Elementen vom Typ sendtype zur Verfügung.

int MPI_Alltoall (void *sendbuf,

int sendcount,

MPI_Datatype sendtype,

void *recvbuf,

int recvcount,

MPI_Datatype recvtype,

MPI_Comm comm)

Bei einem Gesamtaustausch schickt jeder beteiligte Prozess an jeden anderen beteiligtem Prozess eine eventuell unterschiedliche Nachricht

• Bei synchroner Kommunikation findet die Übertragung einer Nachricht nur statt, wenn Sender und Empfänger zur gleicher Zeit an der Kommuniation teilnehmen.

Hier benutzt man dieselben Operationen, wie in Akkumulationsoperation

Gesamtaustausch

int MPI_Allreduce (void *sendbuf,

void *recvbuf,

int count,

MPI_Datatype type,

MPI_Op op,

MPI_Comm comm).

Bei einer Multi-Akkumulationsoperation führt jeder beteiligte Prozess eine (Einzel-) Akkumulationsoperation aus, wobei für jede dieser Akkumulationsoperationen von jedem Prozess unterschiedliche Daten zur Verfügung gestellt werden.

Totaler Austausch

Multi-Akkumulationsoperation

int MPI_Allgather (void *sendbuf,

int sendcount,

MPI_Datatype sendtype,

void *recvbuf,

int recvcount,

MPI_Datatype recvtype,

MPI_Comm comm).

Multi-Akkumulationsoperation

• Bei asynchroner Kommunikation kann der Sender Daten versenden, ohne sicher zu sein, dass der Empfänger bereit ist, die Daten zu empfangen.

Durch Ausführen der Multi-Broadcastingoperation werden die Daten aller beteiligten Prozesse aufgesammelt und jedem der Prozesse zur Verfügung gestellt.

Es gibt keinen Wurzelprozess.

Multi-Broadcastoperation

int MPI_Gather (void *sendbuf,

int sendcount,

MPI_Datatype sendtype,

void *recvbuf,

int recvcount,

MPI_Datatype recvtype,

int root,

MPI_Comm comm)

int MPI_Scatter (void *sendbuf,

int sendcount,

MPI_Datatype sendtype,

void *recvbuf,

int recvcount,

MPI_Datatype recvtype,

int root,

MPI_Comm comm)

die Anzahl der Elemente, die Wurzelprozess von jedem Sender empfängt

die Anzahl der Elemente von jedem Sender

Multi-Broadcastoperation

Bei einer Gatheroperation stellt jeder an der Operation beteiligte Prozess Daten zur Verfügung, die (ohne Anwendung einer Reduktionsoperation) am angegebenen Wurzelprozess aufgesammelt werden

Bei einer Scatteroperation stellt ein Wurzelprozess für jeden an der Operation beteiligten Prozess eventuell unterschiedliche Daten zur Verfügung, die durch Ausführen der Operation an die beteiligten Prozesse verteilt werden.

Gatheroperation

Scatteroperation

int MPI_Reduce (void *sendbuf,

void *recvbuf,

int count,

MPI_Datatype type,

MPI_Op op,

int root,

MPI_Comm comm)

MPI_MAX Maximum

MPI_MIN Minimum

MPI_SUM Summe

MPI_PROD Produkt

MPI_LAND logisches Und

MPI_BAND bitweises Und

MPI_LOR logisches Oder

MPI_BOR bitweises Oder

MPI_LXOR logisches exklusives Oder

MPI_BXOR bitweises exklusives Oder

MPI_MAXLOC maximaler Wert und dessen Index

MPI_MINLOC minimaler Wert und dessen Index

Gatheroperation

Scatteroperation

Akkumulationsoperation stellt jeder beteiligte Prozess Daten zur Verfügung, die mit Hilfe der angegebenen binären Operation verknüpft werden. Das Ergebnis wird von einem ausgezeichneten Wurzelprozess aufgesammelt.

Akkumulationsoperation

die Anzahl der Nachrichten

Programmierung

Akkumulationsoperation

Bei einer Broadcastoperation schickt ein ausgewählter Prozess die gleichen Daten an alle anderen Prozesse einer Gruppe.

int MPI_Bcast (void *message,

int count,

MPI_Datatype type,

int root,

MPI_Comm comm)

a

Broadcastoperation

Broadcastoperation

Eine globale Kommunikationsoperation ist eine Kommunikationsoperation, an der alle Prozesse eines parallelen Programms bzw. einer Teilmenge oder Gruppe dieser Prozesse beteiligt sind.

Es gibt blockierende und nichtblockierende Versionen von den globalen Kommunikationsoperationen.

Globale Kommunikationsoperationen

Kommunikator und Kommunikationsgebiet

Alle Kommunikationsoperationen werden in MPI mit Hilfe von Kommunikatoren verschickt, wobei ein Kommunikator eine Menge von Prozessen . Diese Menge von Prozessen heißt Kommunikationsgebiet.

MPI_COMM_WORLD ist Kommunikator, der by default benutzt wird.

Aber man kann neue Kommunikatoren für die bestimmten Untermengen von den Prozessen erzeugen.

Puffermodus: der Sender wartet nicht auf den Start der zugehörigen Empfangsoperation. Wenn die zugehörige Empfangsoperation noch nicht gestartet wurde, muss das Laufzeitsystem die Nachricht in Puffern ablegen

Evgeny Fedko (evgfedko@yandex.ru)

Alexandra Faynveyts (fainalex@yandex.ru)

Synchroner Modus: eine Sendeoperation beendet erst dann, wenn die zugehörige Empfangsoperation gestartet und mit dem Empfang von Daten begonnen wurde

Standardmodus: das Laufzeitsystem bestimmt, ob Nachrichten in Systempuffern zwischengespeichert werden oder ob sie direkt dem Empfänger zugestellt werden

bestimmen Koordination der Sende- und Empfangsoperationen.

print: "Hello, World! My rank is: " + str(comm.rank)

Übertragungsmodi

Proseminar "Parallele Programmierung"

Jeder Prozess, der an der Kommunikation teilnimmt, hat seinen einzigartigen Rang (die Nummer). Die Range sind von 0 bis n-1 numeriert, wobei n die Anzahl der Prozesse ist.

Jede Nachricht hat einen Tag. Der Tag hilft dem Empfänger, die verschiedenen Nachrichten von demselben Sender zu unterscheiden.

int MPI_Irecv (void *buffer,

int count,

MPI_Datatype type,

int source,

int tag,

MPI_Comm comm,

MPI_Request *request).

der zusätzliche Parameter bezeichnet eine für den Programmierer nicht direkt zugreifbare Datenstruktur

Eine nichtblockierende Empfangsoperation startet eine Empfangsoperation, bringt diese aber nicht zum Abschluss, sondern informiert das Laufzeitsystem darüber, dass Daten im Empfangspuffer abgelegt werden können.

Allgemeine Beschreibung

ein Empfangsprozess (Empfänger)

Empfangspuffer

maximale Anzahl der Elemente

MPI_Recv

der Rang des Prozesses, von dem die Nachricht empfangen werden soll

der Status

Status

enthält folgende Information:

• status.MPI_SOURCE spezifiziert den Sender der empfangenen Nachricht,
• status.MPI_TAG gibt die Markierung der empfangenen Nachricht an,
• status.MPI_ERROR enthält einen Fehlercode.
• die Länge der Nachricht

Die einfachste Form des Datenaustausches zwischen Prozessen ist ein Einzeltransfer (Punkt-zu-Punkt-Kommunikation), da genau zwei Prozesse beteiligt sind:

int MPI_Recv(void *rmessage,

int count,

MPI_Datatype datatype,

int source,

int tag,

MPI_Comm comm,

MPI_Status *status)

Typ der zu empfangenden Elemente

int MPI_Isend (void *buffer,

int count,

MPI_Datatype type,

int dest,

int tag,

MPI_Comm comm,

MPI_Request *request)

flag=true, wenn die von request bezeichnete Operation beendet ist

Die Funktion MPI_Wait blockiert den ausführenden Prozess, bis die von request bezeichnete Operation vollständig beendet ist.

MPI_CHAR signed char

MPI_SHORT signed short int

MPI_INT signed int

MPI_LONG signed long int

MPI_UNSIGNED_CHAR unsigned char

MPI_UNSIGNED_SHORT unsigned short int

MPI_UNSIGNED unsigned int

MPI_UNSIGNED_LONG unsigned long int

MPI_FLOAT float

MPI_DOUBLE double

MPI_LONG_DOUBLE long double

MPI_PACKED

MPI_BYTE

int MPI_Wait (MPI_Request *request,

MPI_Status *status)

ein Sendeprozess (Sender)

int MPI_Test (MPI_Request *request,

int *flag,

MPI_Status *status).

Mit Hilfe von MPI_Test kann es überprüft werden, ob eine gestartete nichtblockierende Operation bereits abgeschlossen ist bzw. die den ausführenden Prozess blockieren, bis die entsprechende Operation beendet ist.

der Typ der Elemente

Nichtblockierende Variante von MPI_Send und MPI_Recv

Anzahl der zu sendenden Elemente

MPI_Test und MPI_Wait

Sendepuffer

MPI_Send

der Kommunikator

der Rang des Zielprozesses

der Tag

int MPI_Send (void *smessage,

int count,

MPI_Datatype datatype,

int dest,

int tag,

MPI_Comm comm)

Eine nichtblockierende Sendeoperation startet den Sendevorgang ohne sicherzustellen, dass nach Abschluss der Operation die Nachricht aus dem Sendepuffer kopiert wurde.

Wie MPI_Send und MPI_Recv funktionieren

Die Daten werden aus dem Sendepuffer smessage in einen Systempuffer kopiert. Ein Kopf (header) hinzugefügt wird, der Informationen über den Sender der Nachricht, den Zielprozess, die Markierung und den Kommunikator enthält.

Die Daten werden über das Netzwerk des Parallelrechners vom Sender zum Empfänger geschickt.

Die Daten werden vom Empfänger dest aus dem Systempuffer, in dem die Nachricht empfangen wurde, in den angegebenen Empfangspuffer kopiert.

die maximale Anzahl der zu empfangenden Elemente

der Rang des Empfängers

der Rang des Senders

sendbuf und recvbuf sollen disjunkt sein, aber können verschiedene Länge haben.

Die Daten von verschiedenen Typen können geschickt und empfangen werden.

Intialisierung ist notwendig

Deadlock-freie Operation

int MPI_Sendrecv (void *sendbuf,

int sendcount,

MPI_Datatype sendtype,

int dest,

int sendtag,

void *recvbuf,

int recvcount,

MPI_Datatype recvtype,

int source,

int recvtag,

MPI_Comm comm,

MPI_Status *status)

MPI_Send und MPI_Recv sind beide blockierend und asynchron

Deadlocks

Finalisierung ist auch notwendig

Ein MPI-Programm wird als sicher (engl. secure) bezeichnet, wenn seine Korrektheit nicht auf Annahmen über das Vorhandensein von Systempuffern oder die Größe von Systempuffern beruht, d. h. sichere MPI-Programme werden auch ohne Systempuffer korrekt ausgeführt.

Das Auftreten eines Deadlocks kann auch davon abhängen, ob die Implementierung des Laufzeitsystems von MPI einen Systempuffer benutzt