36
Seminar Parallele und Verteilte Programmierung Julian Pascal Werra Message Passing Interface (MPI)

Message Passing Interface (MPI)

  • Upload
    lumina

  • View
    38

  • Download
    0

Embed Size (px)

DESCRIPTION

Message Passing Interface (MPI). Julian Pascal Werra. Gliederungsübersicht. A. Motivation. B. Parallele und Verteilte Programmierung. C. MPI. D. Fazit. Gliederungsübersicht. A. Motivation. B. Parallele und Verteilte Programmierung. C. MPI. D. Fazit. Motivation. 1. Motivation. - PowerPoint PPT Presentation

Citation preview

Page 1: 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)

Page 2: Message Passing Interface (MPI)

2

Gliederungsübersicht

B. Parallele und Verteilte Programmierung

C. MPI

A. Motivation

D. Fazit

Page 3: Message Passing Interface (MPI)

3

Gliederungsübersicht

B. Parallele und Verteilte Programmierung

C. MPI

A. Motivation

D. Fazit

Page 4: Message Passing Interface (MPI)

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

Page 5: Message Passing Interface (MPI)

5

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

Page 6: Message Passing Interface (MPI)

6

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

Page 7: Message Passing Interface (MPI)

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

Page 8: Message Passing Interface (MPI)

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

Page 9: Message Passing Interface (MPI)

9

Gliederungsübersicht

A. Motivation

C. MPI

1. Klassifizierung von Parallelrechnern2. Verteilter und gemeinsamer Speicher

B. Parallele und Verteilte Programmierung

D. Fazit

Page 10: Message Passing Interface (MPI)

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

Page 11: Message Passing Interface (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

Page 12: Message Passing Interface (MPI)

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

Page 13: Message Passing Interface (MPI)

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

Page 14: Message Passing Interface (MPI)

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

Page 15: Message Passing Interface (MPI)

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

Page 16: Message Passing Interface (MPI)

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

Page 17: Message Passing Interface (MPI)

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

Page 18: Message Passing Interface (MPI)

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

Page 19: Message Passing Interface (MPI)

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

Page 20: Message Passing Interface (MPI)

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

Page 21: Message Passing Interface (MPI)

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

Page 22: Message Passing Interface (MPI)

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

Page 23: Message Passing Interface (MPI)

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

Page 24: Message Passing Interface (MPI)

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

Page 25: Message Passing Interface (MPI)

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

Page 26: Message Passing Interface (MPI)

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)

Page 27: Message Passing Interface (MPI)

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

Page 28: Message Passing Interface (MPI)

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

Page 29: Message Passing Interface (MPI)

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

Page 30: Message Passing Interface (MPI)

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

Page 31: Message Passing Interface (MPI)

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

Page 32: Message Passing Interface (MPI)

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

Page 33: Message Passing Interface (MPI)

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

Page 34: Message Passing Interface (MPI)

34

Gliederungsübersicht

A. Motivation

B. Parallele und Verteilte Programmierung

C. MPI

D. Fazit

Page 35: Message Passing Interface (MPI)

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

Page 36: Message Passing Interface (MPI)

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