Message Passing Interface (MPI)

Sem

inar

Par

alle

le u

nd V

erte

ilte

Pro

gram

mie

rung

Julian Pascal Werra

Message Passing Interface (MPI)

2

Gliederungsübersicht

B. Parallele und Verteilte Programmierung

C. MPI

A. Motivation

D. Fazit

3

Gliederungsübersicht

B. Parallele und Verteilte Programmierung

C. MPI

A. Motivation

D. Fazit

4

Motivation

Technische Fortschritte Hardware ist günstiger geworden Entwicklung von Hochgeschwindigkeits-Netzwerken (z.B. LAN)

Entwicklung von Parallelrechnern

Warum MPI? Je nach Parallelrechner kann Nachrichtenaustausch notwendig sein MPI ist eine Spezifikation für Datenaustausch auf nachrichtengekoppelten

Systemen

3. MPI4. Fazit

2. Parallele und …1. Motivation

5

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

6

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

7

Klassifizierung von Parallelrechnern2. Parallele und …

3. MPI4. Fazit

1. Motivation

Single Instruction Multiple Instruction

Single Data SISD MISD

Multiple Data SIMD MIMD

SISD Ein Prozessor mit einem Programmspeicher

Einprozessorsysteme (klassische Von-Neumann-Architektur)

SIMD Mehrere Prozessoren Zugriff auf gemeinsamen Programm-/Datenspeicher

Vektor- und Feldrechner

Flynnsche Klassifikation

8

Klassifizierung von Parallelrechnern2. Parallele und …

3. MPI4. Fazit

1. Motivation

Single Instruction Multiple Instruction

Single Data SISD MISD

Multiple Data SIMD MIMD

MISD Jeweils eigener Programm-, aber gemeinsamer Datenspeicher Jeder Prozessor erhält das selbe Datum aus dem Datenspeicher

wenig sinnvoll

MIMD Jeweils eigener Programm-, aber gemeinsamer Datenspeicher Jeder Prozessor erhält ein separates Datum

alle Arten von Multicomputer-/Multiprozessorsystemen

Flynnsche Klassifikation

9

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

10

Verteilter und gemeinsamer Speicher2. Parallele und …

3. MPI4. Fazit

1. Motivation

MIMD

Multiprozessorsysteme Gemeinsamer Speicher

Multicomputersysteme Verteilter Speicher

Gemeinsamer Speicher shared memory machine (SMM) Speicher kann zum Datenaustausch genutzt werden Anwendungsgebiet für OpenMP

Verteilter Speicher distributed memory machine (DMM) Keine gemeinsame Datenablage, somit Zwang zum Nachrichtenaustausch Anwendungsgebiet für MPI

11

Verteilter und gemeinsamer Speicher2. Parallele und …

3. MPI4. Fazit

1. Motivation

ProzessorProgrammspeicher

ProzessorProgrammspeicher

ProzessorProgrammspeicher

ProzessorProgrammspeicher

ProzessorProgrammspeicher

Netzwerk

Message Passing Programmiermodell System der Klasse MIMD

Kollektion von Prozessoren Je eigener Programmspeicher Verteilter Speicher

Nachrichtenaustausch erfolgt über ein Netzwerk

12

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

13

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

14

Grundlagen

MPI Spezifikation, die den Nachrichtenaustausch auf verteilten Systemen

beschreibt Legt Programm-Bindings (Sprachkonstrukte) fest Implementierungen für C und Fortran (mittlerweile auch Java) Durch einheitliche Schnittstellen portabel

Versions-Historie 1994 MPI-1 Standard 1995 MPI-1.1 (Fehlerbereinigung) 1997 MPI-1.2 (Fehlerbereinigung) 1997 MPI-2 Standard (Erweiterung um dynamische Prozessverwaltung,

parallele Ein/Ausgabe und einseitige Kommunikationsoperationen)

3. MPI2. Parallele und …

4. Fazit

1. Motivation

15

Grundlagen

Programmaufbau Innerhalb eines Programms müssen MPI-Funktionen von MPI_Init und MPI_Finalize umschlossen sein MPI_Init

Muss die erste aufgerufene MPI-Funktion sein Veranlasst notwendige Vorbereitungen für den Einsatz von MPI

MPI_Finalize Muss die letzte aufgerufene MPI-Funktion sein Gibt reservierte Ressourcen wieder frei Sorgt für eine saubere Umgebung (behandelt z.B. nicht zugestellte Nachrichten)

3. MPI2. Parallele und …

4. Fazit

1. Motivation

16

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

17

Menge von geordneten Prozessen Ein Prozess kann mehreren Gruppen angehören

MPI stellt Funktionen bereit für: Vereinigung / Löschen Schnitt- / Differenz- / Untermengenbildung Anzahl der Prozesse / Bestimmung des Indizes des aufrufenden Prozesses Gleichheitsprüfung zweier Gruppen

Das Kommunikationsumfeld einer Prozessgruppe nennt sich Kommunikationsgebiet

Prozessgruppen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Prozess A

Prozess B

Prozess C

Rang 0 à

Rang 1 à ß Rang 0

ß Rang 1

Gruppe 1

Gru

ppe

2

18

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

19

Kommunikatoren

Treten nur in Verbindung mit einer Prozessgruppe auf Lokale Darstellung eines Kommunikationsgebiets

Inter-Kommunikator: Kommunikation zwischen Gruppen Intra-Kommunikator: Kommunikation innerhalb einer Gruppe

MPI stellt Funktionen bereit für: Erzeugung Duplizierung Aufspaltung

3. MPI2. Parallele und …

4. Fazit

1. Motivation

20

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

21

Einzeltransfer-Operationen

Kommunikation zwischen zwei Prozessen (klassische Sender/Empfänger-Beziehung) Sendeoperation MPI_Send Empfangsoperation MPI_Recv Misch-Operation MPI_Sendrecv Beteiligte Prozesse rufen entsprechende Funktion auf

3. MPI2. Parallele und …

4. Fazit

1. Motivation

22

Einzeltransfer-Operationen

#include <stdio.h>

#include <string.h>

#include “mpi.h”

int main (int argc, char *argv[])

{

int my_rank, source, dest, tag=0;

char msg [20];

MPI_Status status;

// MPI Initialisieren

MPI_Init (&argc, &argv);

// Eigenen Rang bestimmen

MPI_Comm_rank (MPI_COMM_WORLD, &my_rank);

// Der Prozess mit Rang 0 sendet eine Nachricht...

if (my_rank == 0){

strcpy (msg, “Testnachricht”);

MPI_Send (msg, strlen(msg)+1, MPI_Char, 1, tag, MPI_COMM_WORLD); }

// ...und Prozess 1 empfängt sie

if (my_rank == 1){

MPI_Recv (msg, 20, MPI_Char, 0, tag, MPI_COMM_WORLD, &status); }

// MPI beenden

MPI_Finalize();

}

3. MPI2. Parallele und …

4. Fazit

1. Motivation

23

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

24

Globale Kommunikations-Operationen

Kommunikation zwischen mehreren Prozessen Beteiligte Prozesse rufen die gleiche Funktion mit ggf. unterschiedlichen

Parametern auf Welche Funktionalitäten können durch solche Funktionen abgedeckt

werden? Broadcast Akkumulation Gather (Unterschiedliche Daten sammeln) Scatter (Unterschiedliche Daten verteilen) Multi-Broadcast Multi-Akkumulation Totaler Austausch

3. MPI2. Parallele und …

4. Fazit

1. Motivation

25

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

A

Ap1 Empfangspuffer

Ap2 Empfangspuffer

Ap3 Empfangspuffer

Ap4 Empfangspuffer

p0 Sendepuffer

Broadcast MPI_Bcast Der Wurzelprozess beschickt die beteiligten Prozesse mit den selben Daten

26

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Akkumulation MPI_Reduce Der Wurzelprozess empfängt Daten von den beteiligten Prozessen Auf diese Daten wendet er eine Reduktionsoperation an

8p0 Empfangspuffer

4

3

8

1

p1 Sendepuffer

p2 Sendepuffer

p3 Sendepuffer

p4 Sendepuffer

(Anwendung von MAXIMUM als Reduktionsoperation)

27

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Gather MPI_Gather Der Wurzelprozess sammelt Daten von den beteiligten Prozessen

A B C Dp0 Empfangspuffer

A

B

C

D

p1 Sendepuffer

p2 Sendepuffer

p3 Sendepuffer

p4 Sendepuffer

28

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Scatter MPI_Scatter Entspricht grundlegend einem Broadcast Es kann aber an jeden Prozess eine separate Nachricht verschickt werden

A B C D

Ap1 Empfangspuffer

Bp2 Empfangspuffer

Cp3 Empfangspuffer

Dp4 Empfangspuffer

p0 Sendepuffer

29

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Multi-Broadcast MPI_Allgather Die beteiligten Prozesse beschicken sich gegenseitig mit Nachrichten Jeder Prozess erhält jede versandte Nachricht Kommt somit ohne ausgezeichneten Wurzelprozess aus

A B C Dp1 EmpfangspufferA

B

C

D

p1 Sendepuffer

p2 Sendepuffer

p3 Sendepuffer

p4 Sendepuffer

A B C D

A B C D A B C Dp3 Empfangspuffer

p2 Empfangspuffer

p4 Empfangspuffer

30

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Multi-Akkumulation MPI_Allreduce Entspricht einer Akkumulation gefolgt von einem Broadcast Benötigt einen Wurzelprozess, der die Reduktionsoperation vornimmt

4

3

8

1

p1 Sendepuffer

p2 Sendepuffer

p3 Sendepuffer

p4 Sendepuffer

(Anwendung von MAXIMUM als Reduktionsoperation)

8

8

8

8

p1 Empfangspuffer

p2 Empfangspuffer

p3 Empfangspuffer

p4 Empfangspuffer

31

Globale Kommunikations-Operationen 3. MPI2. Parallele und …

4. Fazit

1. Motivation

Totaler Austausch MPI_Alltoall Alle beteiligten Prozesse tauschen sich gegenseitig mit Nachrichten aus Jeder Prozess erhält eine für ihn explizit bestimmte Nachricht

A1

p1 Sendepuffer

A3A2

B1

p2 Sendepuffer

B3B2

C1

p3 Sendepuffer

C3C2

A1

p1 Empfangspuffer

C1B1

A2 C2B2

A3 C3B3

p2 Empfangspuffer

p3 Empfangspuffer

32

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

D. Fazit

1. Grundlagen2. Prozessgruppen

C. MPI

3. Kommunikatoren4. Einzeltransfer-Operationen5. Globale Kommunikations-Operationen6. Zeitmessung

33

Zeitmessung

Typische Fragestellungen Wie lange nimmt die Bearbeitung eines speziellen Problems in Anspruch? Welcher Zeitvorteil ergibt sich durch zusätzliche Hardware? Identifizierung und Quantifizierung von brachliegenden Ressourcen

MPI_Wtime liefert einen Zeitstempel MPI_Wtick gibt die Genauigkeit von MPI_Wtime an. Beispielcode

Differenz zwischen end und start ergibt benötigte Zeit in Sekunden:...

start = MPI_Wtime();

... // zu messender Programmteilend = MPI_Wtime();

...

3. MPI2. Parallele und …

4. Fazit

1. Motivation

34

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

C. MPI

D. Fazit

35

Fazit

MPI ist Spezifikation zur Datenübertragung auf nachrichtengekoppelten Systemen

Die Kommunikation erfolgt über Kommunikatoren innerhalb von bzw. zwischen Prozessgruppen

Eine Kommunikation kann zwischen zwei (Einzeltransfer) oder mehreren (globaler Transfer) Prozessen stattfinden

4. Fazit

2. Parallele und …3. MPI

1. Motivation

36

Ende

Vortragender

Thema

Themensteller

Betreuer

Julian Pascal Werra

Message Passing Interface (MPI)Im Rahmen des Seminars „Parallele und Verteilte Programmierung“

Prof. Dr. Herbert Kuchen

Dipl.-Wirt.-Inform. Philipp Ciechanowicz