Parallele Programmierung - mathematik.uni-marburg.detseeger/Parallele_Programmierung/Blank... · 1 Einführung 1.1 Programmieren von parallelen Rechnern Problem ®¶ Paralleler Algorithmus

Parallele Programmierung

Prof. Dr. R. Loogen

10. Januar 2008

Inhaltsverzeichnis

Inhaltsverzeichnis i

1 Einführung 11.1 Programmieren von parallelen Rechnern. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1.1 Erwartungen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 Probleme: „grand challenges“ „scientific computing“. . . . . . . . . . . . . . . . . 11.1.3 Algorithmen Kernidee: „Divide et impera!“. . . . . . . . . . . . . . . . . . . . . . 11.1.4 Bewertungskriterium für parallele Systeme / Algorithmen. . . . . . . . . . . . . . 31.1.5 Parallelrechner. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.6 Gegenüberstellung und Zusammenfassung. . . . . . . . . . . . . . . . . . . . . . 5

1.2 Parallele Programmiermodelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2.1 Parallelität vs. Nebenläufigkeit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.2 Prozesse vs. Threads. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Entwurf paralleler Programme 82.1 PCAM-Methode nach Foster (1995). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1 Partitionierung (P). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Kommunikation (C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.3 Parallele Matrixmultiplikation nach Gentlement (1978). . . . . . . . . . . . . . . . 112.1.4 Agglomeration (A). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.1.5 Mapping (M) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Grundkonzepte paralleler Programme 173.1 Synchronisation von Speicherzugriffen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1.1 Synchronisationskonstrukte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.1.2 Synchronisationsformen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.1.3 Barrierensynchronisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Monitore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.1 Monitordeklaration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2.2 Signalisierungsmethoden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.3 Synchronisation und Kommunikation über Nachrichten. . . . . . . . . . . . . . . . . . . . 233.3.1 Kommunikationsmodelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.4 Verteilte Programmierung in MPD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

i

INHALTSVERZEICHNIS

INHALTSVERZEICHNIS

4 Die Bibliothek MPI 354.1 Grundkonzepte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Kommunikation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.3 Kommunikatoren, Prozessgruppen und Topologieinformationen. . . . . . . . . . . . . . . 41

4.3.1 Prozessgruppen: Konstruktion, Analyse, Manipulation. . . . . . . . . . . . . . . . 434.3.2 Kommunikatoren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.3.3 Virtuelle Topologien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.3.4 Zugriffsroutinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.3.5 Interkommunikatoren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.4 Abgeleitete Datentypen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.4.1 Spezifikation neuer Datentypen. . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5 Parallele Algorithmen 495.1 Das PRAM- Rechnermodell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2 Rechnermodelle mit verteiltem Speicher. . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.3 Paralleles Sortieren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.3.1 Ein CRCW-Verfahren mit konstantem Zeitaufwand. . . . . . . . . . . . . . . . . . 565.3.2 Sortiernetze. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.3.3 Der Algorithmus von Cole. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.4 Graphen Algorithmen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.4.1 Bestimmung der Zusammenhangskomponenten eines Graphen. . . . . . . . . . . . 67

5.4.1.1 Algorithmusvon Hirschberg(1976) . . . . . . . . . . . . . . . . . . . . 695.4.2 Kürzeste Wege. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725.4.3 Minimal spannende Bäume. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.4.3.1 Algorithmus von Prim. . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.4.3.2 Algorithmus von Sollin (1977). . . . . . . . . . . . . . . . . . . . . . . 75

6 Algorithmische Skelette 78

Literaturverzeichnis I

Abbildungsverzeichnis II

ii

1 Einführung

1.1 Programmieren von parallelen Rechnern

Problem

®¶Paralleler Algorithmus

®¶Paralleles Programm

KS

®¶

große Wechselwirkung

ssfffffffffffffffffff

kkXXXXXXXXXXXXXXXXXXoo

Parallelrechner

KS

1.1.1 Erwartungen

• mehr Rechenleistung

• besseres Preis-/ Leistungsverhältnis

• bessere Verfügbarkeit durch Redundanzen

• besser verständliche Programme durch mehr Information über die Problemstruktur

1.1.2 Probleme: „grand challenges“ „scientific computing“

• Probleme aus Naturwissenschaft und Technik, meist Simulationen technischer und natürlicher Vor-gänge.

• verteilte Datenbanksysteme

• Telekommunikationsbereiche

1.1.3 Algorithmen Kernidee: „Divide et impera!“

Divide et impera/ \

Zerlegung in paralleles lösenunabhängige Teile der Teile

1

1.1. PROGRAMMIEREN VON PARALLELEN RECHNERN

KAPITEL 1. EINFÜHRUNG

Beispiele:

Datenparallelität:

Vektoraddition „Feingranulare Parallelität“(a1, . . . , an)

+ (b1, . . . , bn)

(a1 + b1︸︷︷︸

, . . . ,an + bn)︸︷︷︸

unabhängige Teile

Kontrollparallelität:

Summation vonn Zahlenn−1∑

i=0

ai, n = 2k

sequentiell:n − 1 Additionenparallel: „rekursives Doppeln“

a0ÂÂ@

@a1 a2

yyssss

%%KKKK

a3 . . . an−2

((PPPPP

vvnnnnnan−1

www+

$$IIII +zzuuuu

. . . +

wwooooooo n/2 Additionen

+%%

+vv

n/4 Additionen

+ 1 Addition

k∑

i=1

n

2i= . . . = n − 1 Additionen ink = log n parallelen Schritten bein Ar-

beitseinheiten.

Sortieren vonn Zahlen:a =< a1, . . . , an >, n ≥ 1 paarweise verschiedeneai

Ranksort:

Definition: ranga (i) = |aj |aj < ai|Rang desi-ten Elementes vona−→ Position in der sortierten Folge.

Verfahren: Für jedes Element (Datenparallelität):

• Bestimme den Rang durch Vergleiche mit allen übrigen Elementen• Ordne Element in sortierter Folge an entsprechender Position ein

sequentiellerAufwand: n2

paralleler Aufwand: n Schritte (bein Verarbeitungseinheiten)

Beispiel: für einnicht parallelisierbares Problem

Berechnung einer großen Potenz vonx ∈ R : x2kmit k ≫ 1 sequentielles Vorgehen: sukzessi-

2

KAPITEL 1. EINFÜHRUNG1.1. PROGRAMMIEREN VON PARALLELEN RECHNERN

ves Quadrieren(1) x ∗ x = x2

(2) x2 ∗ x2 = x4

(3) x4 ∗ x4 = x8

......

(k) xk ∗ xk = xk2

1.1.4 Bewertungskriterium für parallele Systeme / Algorith men

Parameter:

• Problemgrößen ∈ N

• Anzahl der Prozessorenp ≥ 1

1. Zeitkomplexität: Tp (n) , Tp (n, A)# Zeitschritte zur Durchführung von Algorithmus A mit Eingabedaten der Größen aufp Prozessoren(Laufzeit aufp Prozessoren)Seq. Zeit:T1 (n) sequentieller Algoithmus.

2. Beschleunigung: (speedup) :Sp = T1Tp

Maß für Zeitgewinn durch Parallelverarbeitungi. Allg. gilt : 1 ≤ Sp ≤ p

• Slowdown(Sp ≤ 1)möglich wegen Zusatzaufwand für Parallelität

• Superlinearen Speedup(Sp > p)Cache-Effekte,Suchverfahren /brach-and-boundVerfahren

3. Effizienz: Ep =Sp

p

Maß für Prozessorauslastung bei identischer Anzahl von Berechnungsschritten im parallelen und se-quentiellen Fall.

4. Skalierbarkeit: Abhängigkeit eines Verfahrens von der Rechnerkonfiguration

5. Kommunikationskomplexität: Datentransferaufwand

Beispiel:

• rekursives Doppeln:T1 (n) = n − 1Tp (n) = log2 n mit p ≥ n

2

=⇒ Sp = n−1log n

∈ O(

nlog n

)

Ep ∈ O(

1log n

)

• Ranksort:T1 (n) = n2 (sequentieller Ranksort)Tn (n) = n

=⇒ Sn = n „relativer Speedup“

3

1.1. PROGRAMMIEREN VON PARALLELEN RECHNERN


relativer Speedup: Vergleich – selben Algorithmus auf1 undp Prozessoren

absoluter Speedup: Vergleich – (optimalen) sequentiellen Algorithmus mit parallelen Algorithmus aufpProzessoren

T opt1 (n) = n log n =⇒ Sopt

n = log2 n

Amdahls Gesetz1 Sp ≤ 1f

Jeder Algorithmus hat eine sequentielle Komponente die den parallelenSpeedupbremst.

Berechnung mitn Schritten undp Prozessoren

Seif , 0 ≤ f ≤ 1, der Anteil an Schritten, die sequentiell ausgeführt werden müssen.=⇒ f · n sequentielleSchritte

(1 − f) · n parallel ausführbare Schritte

T1 = n

Tp = f · n +(1 − f) · n

p

Sp =T1

Tp=

1

f + (1−f)p

≤1

f

1.1.5 Parallelrechner

MIMD: Multiple InstructionMultiple Data

• speichergekoppelte Systeme

– gemeinsamer Adressraum (logische Sicht)

– Kommunikation und Synchronisation über gemeinsame Variablen

• nachrichtengekoppelte Systeme

– prozessorlokale Adressräume

– Kommunikation und Synchronisation durch Austausch von Nachrichten

1Gene Amdahl

4

KAPITEL 1. EINFÜHRUNG1.2. PARALLELE PROGRAMMIERMODELLE

SpeicherAdressräume global physikalisch verteilt

gemeinsamSMP:

symmetrischerMultiprozessorDSM:

distributedsharedmemory

UMA:uniform memoryaccess

NUMA:NonUMA

verteilt Multicomputer, distributed memory

1.1.6 Gegenüberstellung und Zusammenfassung

Kriterien SMP DSM DMAdressraum gemeinsam gemeinsam verteiltSpeicher global verteilt verteilt

Komm. / Synch. gemeinsame Variablengemeinsame Variablen

mit internen NachrichtenNachrichten

Skalierbarkeit begrenzt leicht leichtLastverteilung leicht „leicht“ schwierig

Problememangelnde Skalierbarkeit undKonflikte beim Speicherzugriff

Cache-Kohärenz globale Synchronisation

1.2 Parallele Programmiermodelle

gemeinsamer Adressraum2 (MPD, PRAM)

Nachrichtenkopplung

• Prozess-Kanal-Modell (Ian Foster)

• Prozess-Nachrichten-Modell (MPI3, PVM4)

SPMD5

• statisches Prozesssystem

• Nachrichtenkopplung

2shared memory, logische Sicht3Message Parssing Interface4Parallel Virtual Machine5Single Program Multiple Data

5

1.2. PARALLELE PROGRAMMIERMODELLE


• Modellierung von Datenparallelität

Datenparallelität (HPF6, NESL7)

• Bereitstellung von datenparallelen Grundoperationen

– hoher Abstraktionsgrad

1.2.1 Parallelität vs. Nebenläufigkeit

Nebenläufigkeit(concurrency, multithreading)

• reaktive SystemeSystem Umgebung

←−−−−−−−→

Parallelität

• transformationelle SystemeInput−−−−→

System Output−−−−−→

1.2.2 Prozesse vs. Threads

Definition von Prozess:

• „sequenzielle“ Folge von Aktivitäten durch die eine in sich geschlossene Aufgabe bearbeitet wird

oder

• funktionelle Einheit aus

– Zeitlich invarianten Programm

– Satz von Daten

– Zeitlich variantem Zustand

Jeder Prozess besitztUmgebungundKontext

Umgebung: geschützter Adressbereich eines Prozesses, d. h.

• Codebereiche und Datenbereiche im Speicher

• geöffnete Dateien

• Ressourcenverweise

Kontext: „Registerwerte“, d. h.

• Befehlszähler

• Zeiger auf Laufzeitkeller

• Aktivierungsblock

6High Performance Fortran7A Nested Data-Parallel Language

6

KAPITEL 1. EINFÜHRUNG1.2. PARALLELE PROGRAMMIERMODELLE

• usw.

Prozesse:

• eigene Umgebung und Kontext

Threads:

• eigener Kontext

• teilen sich Umgebung mit anderen Threads

7

2 Entwurf paralleler Programme

2.1 PCAM-Methode nach Foster (1995)

PCAM: PartitioningCommunicationAgglomerationMapping

P-Partitionierung

problemabhängige Zerlegung der Berechnung und der Daten in Teile (tasks)

ohne Berücksichtigung der Zielarchitektur−→ maximale inhärente Parallelität Skalierbarkeit beachten

C-Communication

Analyse der DatenabhängigkeitFestlegung der Kommunikationsanforderungen

A-Agglomeration

Zusammenfassung stark zusammenhängender Teile zu größeren Tasks.

Ziel: Effizienzsteigerung durch Kostenminimierung

M-Mapping (Abbildung)

8

KAPITEL 2. ENTWURF PARALLELER PROGRAMME2.1. PCAM-METHODE NACH FOSTER (1995)

Abbildung der resultierenden Struktur auf konkrete Zielarchitektur

Ziel: Maximierung der Prozessorauslastung−→ statisch oder mit dynamischer Lastverteilung

2.1.1 Partitionierung (P)

Ziele:

• möglichst feinkörnige Zerlegung der Berechnung / Datenbasis• Vermeidung der Duplizierung von Daten und Berechnungen• maximal vorhandene Parallelität

Methoden:

• Bereichszerlegung (domain decomposition)• funktionale Zerlegung (functinal decomposition)

Beispiel:Matrix-Multiplikation

A = (aij)1≤i,j≤nB = (bij)1≤i,j≤n

C = (cij)1≤i,j≤nmit cij =

n∑

k=1

aikbkj

mögliche Bereichszerlegungen:

a) −→ Eingabematrizen 2n2 Tasksb) −→ Ausgabematrix n2 Tasks

Datenparallelität

funktionale Zerlegung:

c) −→ n2 · n Multiplikationenn2 (n − 1) Additionen

Kontrollparallelität

Checkliste:

• # Tasks≫ # Prozessoren?– Flexibilität

• keine redundanten Berechnungen, keine redundanten Speicheranforderungen?– Skalierbarkeit

• vergleichbare Größe der Tasks?– Lastausgleich

• alternative Partitionierung?– Flexibilität

• # Tasks skaliert mit Problemgröße? (nicht Größe der Tasks)– Skalierbarkeit

9

2.1. PCAM-METHODE NACH FOSTER (1995)

KAPITEL 2. ENTWURF PARALLELER PROGRAMME

2.1.2 Kommunikation (C)

Ziel: Identifikation der Kommunikationen, die erforderlich sind, um Tasks mit den von ihnen benö-tigten Daten zu versorgen.

Kommunikationsmuster:

• lokal vs. global

• strukturiert vs. unstrukturiert

• statisch vs. dynamisch

• synchron vs. asynchron

Checkliste:

• reguläre Struktur, d. h. Anzahl der Kommunikation in allen Tasks etwa gleich?−→ Skalierbarkeit−→ Balancierung

• möglichst lokale Kommunikation?−→ Effizienz

• Kommunikation nebenläufig (zu den Berechnungen)?−→ Effizienz

Beispiel:Matrix-Multiplikation

Zerlegung A:

aik

bkj

Jedesaik wird mit n bkj (1 ≤ j ≤ n) multipliziert

TaskAik sendet Elementaik zu denn TasksBkj (1 ≤ j ≤ n).TaskBkj erhältn Werteaik (1 ≤ i ≤ n) von TasksAik und berechnetn Produkteaikbkj (1 ≤ j ≤ n).

Die zur Berechnung voncij notwendigen Produkte befinden sich in derj-ten Spalte derB-Tasks. Verwende etwa rekursives Doppeln zum Aufsummieren dern Produkte.

Analyse:

• sehr unausgeglichene Tasks

• viele Kommunikationen

• ungünstige Datenverteilung

Zerlegung B: TaskCij benötigti-te Zeile vonA und diej-te Spalte vonB. Mit diesen Daten kann ohneweitere Kommunikationcij berechnet werden.

Problem: Die Eingangsmatrizen werdenn-mal repliziert.

Beobachtung: TaskCij kann zu jedem Zeitpunkt höchstens ein Produktaik · bkj berechnen und benötigtdazu je ein Element vonA undB

10


Idee: Rotiere Zeilen vonA und Spalten vonB so in Zeilen / Spalten vonC, dass zu jedem Zeitpunktpassende, d. h. zu multiplizierendeA/B-Werte inC-Tasks zur Verfügung stehen.

Beispiel:n = 3

Abbildung 2.1: Matrix-Multiplikation n=3

ab

33

33

ab

11

11

ab

12

12

ab

13

13

ab

21

21

ab

22

22

ab

23

23

ab

31

31

ab

32

32

ab

32

23

ab

11

11

ab

12

22

ab

13

33

ab

22

21

ab

23

32

ab

21

13

ab

33

31

ab

31

12

Rotiere die Zeilen vonA und die Spalten vonB, so dass jedeC-Task eine Multiplikation durchführen kann.

i-te Zeile vonA wird um i − 1 Positionen nach links rotiert(1 ≤ i ≤ n)j-te Spalte vonB wird um j − 1 Positionen nach oben rotiert(1 ≤ j ≤ n)

2.1.3 Parallele Matrixmultiplikation nach Gentlement (19 78)

n2 TasksCij (1 ≤ i, j ≤ n) mit Elementenaij , bij der Eingangsmatrizen, die jeweilscij be-rechnen sollen.als Kommunikationsstruktur: Torusvernetzung der Größen × n

Analyse:

• synchrones Verfahren

• Tasks gleich komplex

• Kommunikation:

– lokal

– nebenläufig zur Berechnung

– nebenläufig in Zeilen / Spalten

funktionale Zerlegung:

Ausgangspunkt:n3 Tasks, die jeweils ein Produktaik bkj berechnen sollen=⇒ 3- dimensionale Struktur (Würfeltopologie)

11



Listing 1 Parallele Matrixmultiplikation nach Gentlement

– Rotierei-te Zeile von MatrixA um i − 1 Positionen nach links

– Rotierej-te Spalte vonB um j − 1 Positionen nach oben

– Anschließend führt jeder Task folgende Anweisungen durch:

1 var a, b, c : real;2 sum := 0;3 for i=1 to n do4 sende a an linke Nachbartask5 sende b an obere Nachbartask6 sum := sum + a * b;7 empfange a von rechter Nachbartask8 empfange b von unterer Nachbartask9

10 od11 cij := sum;

C

B

Ai

jk

Broadcast vonA in DimensionjBroadcast vonB in Dimensioni=⇒ parallele ProduktberechnungAufsummieren aller Produkte in Dimensionk

2.1.4 Agglomeration (A)

Ziele:

• Zusammenfassung von stark interagierenden Teilberechnungen−→ Reduktion der Kommunikation

– Flexibilität bezüglich Skalierbarkeit– Reduktion der Software-Entwicklungskosten

Methoden:

• Dimensionsreduktion

12


Oberflächen - Volumen - Effekt↑ ↑

Kommunikation Berechnungen

Beispiel:8 × 8-Gitter

Jeder Knoten verwaltet ein Element und schickt dieses an alle Nachbarn.y 64 ∗ 4 = 256 bidirektionale Kommunikationen von ebenso vielen Datenelementen.

a) Dimensionsreduktion: Zeilenweise

y 8 Tasks, die je 8 Datenelemente verwalteny 8 ∗ 2 = 16 bidirektionale Kommunikation mit Austausch von16 ∗ 8 = 128Datenelemente.

b) Blockaufteilung in2 × 2 Grid:

y jeder Knoten verwaltet 16 Elemente und tauscht Randdaten mit allen Nachbarn.y 4 ∗ 4 = 16 bidirektionale Kommunikation mit Austausch von16 ∗ 4 = 64Datenelemente.

Methoden: (Agglomeration)

• Granularitätserhöhung durcha) Dimensionsreduktionb) Blockbildung−→ Teilblöcke in Mehrdimensionalen Gitterstrukturen

Beispiel:Gentleman Verfahren

• Granularität einzelner Tasks ist im Allgemeinen zu gering

13



– Einteilung der Matrizen inm2 Submatrizen der Dimensionnm

– Standartmatrixmultiplikation für Teilmatrizen– VerhältnisKommunikationsaufwand

Berechnungsaufwand sinkt– gute Skalierbarkeit

c) Baumstrukturen

Agglomeration der Baumstruktur für Reduktion

Beispiel: für Replikation von Berechnungen in der Agglomerationsphase.

Betrachte Reduktion mit anschließendem Broadcast des Reduktionsergebnisses=⇒ 2 log2 N Schritten beiN Prozessoren

Ã Hypercube-Topologie (Abb.2.2)

Abbildung 2.2: Hypercube

(a) k = 1 (b) k = 2 (c) k = 3

14


Abbildung 2.3: Butterfly-Vernetzung4 Prozessoren

↑ Mehrfachberechnung

Ein Hypercube der Dimensionk (Abb.2.4) enthält2k Knoten und erlaubt Reduktionen / Broad-cast ink-Schritten

Abbildung 2.4: Hypercube der Dimension k

C

B

Ai

jk

−→ Matrixmultiplikation im Hypercube1

Verteile Matrixelemente so in einem Hypercube der Dimension3q undq = ⌈log2 n⌉, so dass

• allen3 ≤ 23⌈log2 n⌉ Multiplikation gleichzeitig erfolgen können• Broadcast der Eingabematrizen inO (log2 n)

• Summation der Produkte inO (log2 n) möglich=⇒ GesamtaufwandO (log2 n)

Beispiel:n = 3y ⌈log2 n⌉ = 2 = qy Hypercube der Dimension 6 mit26 = 64 Knoten

Checkliste: (Agglomeration)

• Reduktion der Kommunikationskosten durch Verbesserung der Lokalität?• Mehraufwand durch Replikation von Daten / Berechnungen gerechtfertigt?• Skalierbarkeit?• Verhältnis Kommunikation – Berechnungen?• Balancierung der Task-Komplexität?• weitere Zusammenfassung?

1Deckel, Nassimi and Sahni 1981

15



2.1.5 Mapping (M)

(Abbildung auf Rechner)

Ziele:

• Verteilung der verbleibenden Tasks auf die Prozessoren des Zielrechners

• Platzierung von häufig kommunizierenden Tasks auf den selben Prozessor und unabhän-gige Tasks auf unterschiedlichen Rechner

Methoden:

• statische vs. dynamische Lastverteilung

• explizite Task-Verteilung−→ Master-Worker-Algorithmus

Checkliste:

• alle Alternativen berücksichtigt?

• Implementierungskosten vertretbar?

16

3 Grundkonzepte paralleler Programme

−→ MPD:1 Multithreaded,Parallel andDistributed

3.1 Synchronisation von Speicherzugriffen

Problem:

• Speicherzugriffe auf gemeinsame Variablen müssen koordiniert werden

• nicht atomare Operationen (können unterbrochen werden) erfordern exklusiven Zugriff auf globaleDaten

3.1.1 Synchronisationskonstrukte

• Semaphore2

Ein Semaphor ist ein abstrakter Datentyp mit:

– nicht negativer Integer-Variablen (Semaphorzähler)

– zwei unteilbare Operationen:

∗ P (passieren)∗ V (verlassen)

in MPD:

Semaphor-Deklaration:sem identifier[subscripts]= expression

Operationen:

P(identifier [subscripts])V(identifier [subscripts])

1Gregory R. Andrews2Edsger W. Dijkstra, 1965

17

3.1. SYNCHRONISATION VON SPEICHERZUGRIFFEN

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME

3.1.2 Synchronisationsformen

a) Wechselseitiger Ausschluss (mutual exclusion)

Beispiel:Geschützter Zugriff auf gemeinsame Ressourcen

b) einseitige SynchronisationEreignissynchronisation (events)Bedingungssynchronisation (conditions)Ein Prozess wartet auf Bedingung oder Ereignis, dass von einem anderen ausgelöst wird.

Beispiel:Erzeuger-Verbraucher mit unbeschränktem Puffer

c) BarrierensynchronisationEine Gruppe von Prozessen muss an einer sogenanntenBarrierewarten, bis alle Prozesse der Gruppedie Barriere erreicht haben.

Beispiel:Synchronisation von Schleifendurchläufen paralleler Prozesse.

Synchronisationskonstrukte

• Semaphoren (Dijkstra)Ein Semaphor S ist ein abstrakter Datentyp mit

– nicht-negativer Integer Variable (Semaphorzähler)

– zwei unteilbare OperationenP (passieren) , V (verlassen)

P(S)(atomar): WennS > 0, dannS := S − 1;sonst wird der ausführende Prozess suspendiert

V(S)(atomar): Wenn Prozesse bei Ausführung von P(S) suspendiert wurden, reaktiviere einen Prozess;sonst:S := S + 1

Beispiel:einseitige Synchronisation

Erzeuger / Verbraucher - Problem: Verbraucher kann erst konsumieren, wenn Erzeuger produ-ziert hat.Annahme: unbeschränkter Puffer

Semaphorvariablen:

sem mutex = 1

sem full = 0

18

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME3.1. SYNCHRONISATION VON SPEICHERZUGRIFFEN

Listing 2 Erzeuger Verbraucher - Problem

1 process producer()2 int item;3 while (true)4 produce(item);5 P(mutex);6 enter(item);7 V(mutex);8 V(full);9

11 process consumer()12 int item;13 while (true)14 P(full);15 P(mutex);16 remove(item);17 V(mutex);18 consume(item);19

Fallstudie: Leser- / Schreiberproblem

Mehrere Prozesse arbeiten auf gemeinsamen Speicherbereich. Gleichzeitige Lesezugriffe sind erlaubt Schreib-zugriffe müssen exklusiv erfolgen.

=⇒ CREW3

Lösungsansatz: [P. J. COURTOIS, F. HEYMANNS, D. L. PARNAS ACM 1971]

Idee: Verwalte Zählerreadcount für Leseranzahl

Listing 3 Zwei Semaphoren

sem writing = 1 −→ Sperre für exklusiven Schreibzugriffsem rcount_mutex = 1 −→ Schutz für readcount

Korrektheit:

Das Semaphorwriting schützt den Speicherbereich.

• Schreiber aktiv (in critical section)y writing ist gesetzt

– kein weiterer Schreiber kann passieren– 1. Leser beiP(writing) blockiert– weitere Leser beiP(rcount_mutex) blockiert

• Leser aktivy writing ist gesetzt durch 1. Leser

– weitere Leser passierenwriting nicht, sondern erhöhen nurreadcount– Schreiber werden beiP(writing) blockiert.

3Concurrent Read Exclusive Write

19

3.1. SYNCHRONISATION VON SPEICHERZUGRIFFEN


Problem:

Schreiber werden ausgehungert, fallsreadcount nie Null wird, weil ständig neue Leser hin-zukommen, bevor aktive Leser den kritischen Bereich verlassen.

Lösung:

Blockiere neue Leser, sobald ein Schreiber wartet.−→ Zähler für Leser und für wartende Schreiberwritecount .

neue Semaphore:

sem wcount_mutex = 1sem reading = 1 (Sperre für Leser, falls Schreiber wartet)

Wenn nicht bekannt ist, nach welcher Strategie bei ’reading ’ blockierte Prozesse reaktiviert werden,können Schreiber immer noch ausgehungert werden, falls immer wieder wartende Leser reaktiviert werden.

=⇒ Sorge dafür, dass beireading höchstens ein Schreiber und keine weiteren Leser blockiert werden.=⇒ weiteres Semaphor:sem r_protect = 1;

3.1.3 Barrierensynchronisation

Prozesse dürfen nur passieren, wenn alle Prozesse der Gruppe dieBarriere erreicht haben.

klassisches Beispiel:

Iterationsverfahren zum Lösen partieller Differentialgleichungen

Zweidimensional Temperaturverteilungsproblem

Ermittle die Temperatur in Gitterpunkten im stabilen Zustand

ϕx,y =1

4(ϕx−1,y + ϕx+1,y + ϕx,y−1 + ϕx,y+1)

−→ Iterationsverfahren (Jacobi, 1845)

ϕ0x,y-geschätzter Anfangswert

20

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME3.2. MONITORE

ϕi+1x,y =

1

4

(ϕi

x−1,y + ϕix+1,y + ϕi

x,y−1 + ϕix,y+1

)

einfache Zählbarriere hat AufwandO (n) −→ lineare Barriere

Optimierung: Turniertechnik−→ AufwandO (log n)

Die globale Barriere ist eine sehr starke und entsprechend teure Form der Synchronisation. Oft ist es mög-lich, eine globale Synchronisation durch eine lokale zu ersetzen.

Beispiel: lokale Synchronisation eines Zeilenprozesses mit beiden Nachbarzeilenprozessen

Symmetrische Barriere für zwei Prozesse mit zwei Semaphoren:sem b1=0; sem b2=0;

3.2 Monitore

abstrakte Datenstruktur mit impliziten Synchronisationseigenschaften.Zugriffsoperationen werden im wechselseitigen Ausschluss ausgeführt

−→ verborgene Implementierung der Zugriffsoperationen und der Synchronisation

21

3.2. MONITORE


3.2.1 Monitordeklaration

monitor <m_name> <variable declaration><initialization statements><procedure declaration>

Aufruf eines Monitorprozesses:<m_name> . <procedurename> (<args>)Für Synchronisation innerhalb von Monitoren (bedingte Synchronisation) ist eine Erweiterung des Basis-konzeptes erforderlich:

Bedingungsvariablen (condition variables):condvar <name>Operationen auf Bedingungsvariablen

• wait(c) „Warte auf Erfüllt sein vonc“

Der ausführende Prozess wird suspendiert und in die Warteschlangezu c eingereiht. DerMonitor wird freigegeben.

• signal(c) „Signalisiere, dassc gilt“

Der ausführende Prozess reaktiviert den „ältesten“ Prozess in derWarteschlange zuc .

Damit gegenseitiger Ausschluss gewährt bleibt, muss festgelegt werden,welcher Prozess denMonitor erhält.

3.2.2 Signalisierungsmethoden

• signal_and_exit „Concurrent Pascal“

– Signal nur am Ende von Monitorproz. erlaubt

• signal_and_continue „SR“

– signalisierender Prozess bleibt aktiv, reaktivierter Prozess muss sichneu um Monitorzugangbewerben.

• signal_and_wait „Modula“

– signalisierender Prozess muss sich neu um Monitor bewerben.

Beispiel:

22

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME3.3. SYNCHRONISATION UND KOMMUNIKATION ÜBER NACHRICHTEN

Listing 4 monitor bounded_buffer

1 monitor bounded_buffer2 typeT buf[n];3 int front = 0, rear = 0, count = 0;4 condvar not_full, not_empty;5 procedure enter (typeT data)6 while (count == n) wait(not_full);7 buf[rear] = data; count++;8 rear = (rear+1) mod n;9 signal(not_empty);

10

3.3 Synchronisation und Kommunikation über Nachrichten

• meist bei verteiltem Speicher−→ kein gemeinsamer Speicher−→ keine globalen Variablen−→ keine zu schützenden Datenbereiche

• Kommunikation über „Kanäle“ und Nachrichtenaustausch (message passing)Modell:

Sender =⇒ Empfänger

Statt schreiben / lesen gemeinsamer Variablen senden / empfangen von Nachrichten

• Synchronisation indirekt dadurch, dass Nachrichten erst nach dem Senden empfangen werden können.

• Kanäle sind Abstraktionen vorhandener Verbindungsnetzwerke

• Kommunikationsaufwand bestimmender Faktor für die Leistung von Verfahren

3.3.1 Kommunikationsmodelle

Basiskonzepte:

• Prozesse & Kanäle

• Sende- und Empfangsprimitivensende „Nachricht“ an „Empfänger“empfange „Nachricht“ (von „Sender“)

Merkmale:

(a) Bezeichnung von Quelle und Ziel der Infomationsübertragung – direkte Prozessbenennung4 vs. Kanäle5

(b) Anzahl der Kommunikationspartner / Art der Kanäle

4„implizite Kanäle zwischen jedem Paar von Prozessen“5mehrere Kommunikationswege zwischen gleichen Prozessen möglich

23

3.3. SYNCHRONISATION UND KOMMUNIKATION ÜBER NACHRICHTEN


1:1 Punkt-zu-Punkt-Kommunikation

1:n Broadcast, Multicast

m:n Briefkasten (mailbox), schwarzes Brett (black board)

m:1 Briefkasten mit einem Empfänger (ports)

(c) Synchronisation

• asynchron:Sender braucht nicht auf Empfang der Daten zu warten

– Kanalpuffer erforderlich

∗ beschränkter Puffer (evtl. Blockade durch vollem Puffer)∗ unbeschränkter Puffer

– gepuffertes Senden: Nachricht wird aus Sendepuffer in Systempuffer, bevor sie aufs Verbin-dungsnetzwerk geschrieben wird

– ungepuffertes Senden: vom Sendepuffer ins Netz

– nicht blockierendes Senden: Anstoß des Nachrichtenversandes mit direkter Weitergabe der Kon-trolle an Nachfolgeinstruktionen

– blockierendes Senden: wartet, bis Sendepuffer ausgelesen ist

• synchron: Sender und Empfänger warten auf Kommunikation, keine Pufferung, direkte Übertragung

(d) Sichtbarkeit und Direktionalität

• symmetrisch: Kommunikationspartner kennen einander in gleicher Weise−→ meist datenorientierten Nachrichtenaustausch

• asymmetrisch: Sender kennt Empfänger, aber nicht umgekehrt−→ meist aktionsorientierte Kommunikation

Beispiel:Client / Server-Systeme

C1

Cn

S

Auftrag

Server braucht

Client nicht zu

kennen

Beispielsprachen: Occam (Vorläufer CSP Hoare 1978)

• unidirektionale 1 - 1 Kanäle

• symmetrische, synchrone Kanäle

• statisches Kanalkonzept: Festlegung aller Kanäle zur Compilezeit

• selektive Kommunikationskommandos−→ gleichzeitiges Warten auf mehreren Eingabekanälen

24


ALTB1& Input_Guard_1

EXPR1...

Bn& Input_Guard_nEXPRn

in CSP: Sende- und Empfangsanw. in Guards

P1C1 // P2

C2~~||

||

P3C3

``BBBB

P2: ALTC1?X EXPR1C2!X EXPR2

Wie muss ein Protokoll aussehen, das diese Situation klärt und Verklemmungen vermeidet.

Beispiel:Puffer in Occam

• als Fließband

Listing 5 Fließband Buffer

1 PROC buffer (CHAN OF INT source, sink)2 WHILE true3 INT local;4 SEQ5 source ? local6 sink ! local7 [n+1]CHAN OF INT stream;8 PAR9 producer(stream[0])

10 PAR index = 0 FOR n11 buffer (stream[n], stream[n+1])12 consumer (stream(n+1))

• Paralleler Buffer

25



Listing 6 Paralleler Buffer

1 PROC buffer ([n] CHAN OF INT source, sink)2 WHILE true3 INT local;4 PAR index = 0 FOR n5 SEQ6 source[index] ? local7 sink[index] ! local8 "TOP-LEVEL"9 [n]CHAN OF INT in, out

10 PAR11 producer( in)12 buffer( in, out)13 consumer(out)

Ada (1980, DoD)

• synchrone Kommunikation

• Rendezvous-Konzept

• asymmetrisch

• 1:1

SR / MPD

• Modellierung verschiedener Konzepte

• Kernkonzept: Operationen

– Aufruf einer Operation

∗ asynchronsend∗ synchroncall

• Ausführung einer Operation

– mittelsproc −→ „eigener Prozess“

– mittels in −→ „bestehender Prozess“

AufrufAusführung call sendproc Prozeduraufruf (auch remote) dynamische Prozesserzeugung (fork)in synchrone Komm. (rendezvous) asynchrone Kommunikation

Beispiel:Simulation von Semaphoren

26


Listing 7 Simulation von Semaphoren

1 sem s = e , op s()send #s nur mit send aufrufen2 int n=e3 for (i = 1 to n)4 send s(); #generiere n Eintrittskarten (tickets)

6 P(s) , receive s() #empfange Eintrittskarte

8 V(s) , send s()

Deklaration von Operationen in MPD

op <name> (<params>) <invocations>sendcallsend,call

Deklaration von Prozess- und Prozedurrümpfen

proc <name> ( <params>)<body>

procedure → Operation mit call-Restriction

process → Operation mit send-Restriction

Auch Kanäle werden in MPD mit Operationen modelliert. Obige Operationsdeklaration ohne Implementie-rung wird alsm : n Kanal betrachtet. Ein Aufruf „send <name> (<params>) “ entspricht dem nichtblockierenden Senden einer Nachricht. Mittels „receive <name> (<variables>) “ können Nach-richten aus dem Kanal<name> empfangen werden.

Beispiel: (a) Mischen geordneter Folgen

Listing 8 Mischen geordneter Folgen

1 send stream1( v)2 ... (ONE)\3 send stream1(EOS) \4 \5 ------------ (MERGE) receive stream1(x1)6 / receive stream2(x2)7 send stream2( v) / while(x1<EOS) or (x2<EOS)8 ... (TWO)/ if(x1<=x2) 9 write(x1)

10 send stream2(EOS) receive stream1(x1)11 12 elsewrite(x2); receive stream2(x2);13

27



Beispiel: (b) Erzeuger- / Verbraucher

Listing 9 Erzeuger- / Verbraucher

############ |−−−−−−−−−−−| ############# p r o d u ce r #−−−−> | KANAL | −−−−> # consumer ############# |−−−−−−−−−−−| ############

| op b u f f e r ( i t e m _ t y p e ) send || |

send b u f f e r ( i tem ) r e c e i v e b u f f e r ( i tem )

Fallstudie: Auflösen von Dreiecksgleichungssystemen

Ax = b mit unterer Dreiecksmatrix

A =

a11 0 · · · · · · 0a21 a22 0 · · · 0...

......

. . ....

an1 an2 an3 . . . ann

, x =

x1...

xn

, b =

b1...

bn

Lösung:

x1 =b1

a11

x2 =(b2 − a21x1)

a22

...

xn =

(

bn −∑n−1

j=1 aijxj

)

ann

yPipeline-Algorithmus

Berechnex1 −→ Berechnex2 −→ . . . −→ Berechnexn −→ Ausgabe vonx

• elementares ’message passing’, ’goto ’ der parallelen Programmierung=⇒ Suche nach abstraktere Kommunikationskonstruktetypisches Kommunikationsmuster:

P1(Client) P2(Server)send "Auftrag" to P2

< --> receive "Auftrag" from P1> << >> << >> <-- send "Antwort" to P1

receive "Antwort" from P2

28


RPC - remote procedure call

P1 (Client)call service (input_args, result_args) (in MPD alsproc )

Aufruf einer Prozedur, die von einem anderen Prozess, der meist eigens generiert wird, ausge-führt wird.

Implizit:

• Senden der Eingabeargumente / Parameter

• Ausführen des Auftrags (durch eigenen Prozess)

• Rücksenden der Ergebnisse

• Zuweisen an Variablenparameter.

Beispiel:Stack Ressource, ggfs auf anderer virtueller / phys. Maschine:

Listing 10 Stack Ressource

1 resource Stack2 type result= enum(OK, OVERFLOW, UNDERFLOW)3 op push( val int item) returns result r4 op pop(var int item) returns result r

6 body Stack (int size)7 int store[1,...,size], int top = 08 proc push(item) returns r9 if (top<size)store[++top]=item, r=OK

10 else if (top==size)r= OVERFLOW11 12 proc pop (item) returns r13 ... item = ...14 15

17 resouce Stack_User()18 import Stack19 Stack.result x20 cap Stack s1, s221 int y22 s1 = create Stack(10);23 s2 = create Stack(20);24 [call] s1.push(25);25 s2.push(15);26 x=s1.pop(y)27 if(x != OK) ...28 ...29 end Stack_User

Beispiel:dynamische Pipeline zum sortieren durch Einfügen

29



Jeder Worker generiert nach Bedarf zunächst seinen Nachfolger, der als Ergebnis seinen Ein-gabekanal zurückliefert. Anschließend wird die Liste der zu sortierenden Werte gelesen, derkleinste erhaltene Wert wird gespeichert und größere Werte werden weitergesendet. Nach Erhaltvon i Werten sendet worker(i) den gespeicherten Wert mit der Positioni über einen globalenAntwortkanal an den sort-Prozess zurück.

Rückgabeanweisungenin MPD:

- return Ende des ProzeduraufrufsRückgabe der Resultate, Var.- par.

- reply Kontroll- und Ergebnisrückgabe an aufrufenden Prozess;Fortsetzung der Prozedurbearbeitung

Rendezvous:Bedienung des Clients durch bestehenden (Server-) Prozess; Vermeidung der Generierung ei-nes separaten Prozesses

P2 (Server):accept service (input_pars, var_params) → body (in MPD: in )

→Verallgemeinerung synchroner Kommunikation

DasRendezvous-Konzept ist flexibler als derRPC.

Beispiel:Bounded Buffer in Ada

• Task Spezifikation

– Deklaration des Namens und der Prozeduren

– für alle Prozesse sichtbar

Listing 11 Task Spezifikation

1 task buffer is2 entry Append (I: in Integer)3 entry Task (I: out Integer)4 end buffer;

30

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME3.4. VERTEILTE PROGRAMMIERUNG IN MPD

• Task ImplementierungDefinition der Prozeduren

Listing 12 Task Implementierung

1 task body buffer is2 N: constant Integer := 100;3 B: array (0...N-1) of Integer;4 anfang (ende, anzahl : Integer := 0;5 begin6 loop7 select8 when anzahl < N =>9 accept Append (I : in Integer)

10 do B[ende]:= I11 end Append12 anzahl:= anzahl +113 ende:= (ende+1) mod N14 or15 when anzahl > 0 =>16 accept Take (I : out Integer)...

Die in -Anweisung in MPD verallgemeinert dieselect -/ accept - Konstrukte von Ada.

Syntax in <op_command> [ ] . . .[ ] <op_command> nimit <op_command> der From<operation> (<formal_id_list>) return <result_id>

st <guard_expr> → <block>

Ein Prozess, der einein - Anweisung ausführt, wird suspendiert, bis eine der Operationen aufgerufen wird.Die Bedingungsausdrücke<guard_expr> dürfen Operationsparameter referenzieren.

Die receive - Anweisung ist ein Spezialfall derin -Anweisung.

receive op(v1, v2) wird impliziert durch:

in op(p1, p2) →v1=p1; v2=p2

ni

3.4 Verteilte Programmierung in MPD

Aufspaltung von Programmen in mehrere Addressräume sog. virtuelle Maschinen

• dynamische Erzeugung

31

3.4. VERTEILTE PROGRAMMIERUNG IN MPD


• Platzierung auf spez. physikalischen Maschinen

• transparente Komm.

1. Erzeugung virtueller Maschine

cap vm cc = create vm() 6 on exp 78

Ressourcen müssen explizit auf VMen erzeugt werden

create res_name(args) on c ←−Verweis auf VM

Globals werden implizit beim Importieren erzeugt. Jede VM erzeugt eigene Instanz importierter Globals.

2. Termination von VMs

destroy exprdestroy cap vm

→ Termination aller Ressourcen mitfinal code-Ausführung anschließend Terminierung aller Globals mitfinalcode.

6erzeugt Verweis auf virtuelle Maschine7optional Platzierung8phy. Maschine als String (oder Integer)

32

KAPITEL 3. GRUNDKONZEPTE PARALLELER PROGRAMME3.4. VERTEILTE PROGRAMMIERUNG IN MPD

Listing 13 Termination von VMs

1 global glob2 int x=0;3 sem mutex=1;4 body glob5 final 6 write(x);7 8 end

10 resource test(int N, int n, cap () signal)11 import glob12 process p [i=1 to N] 13 P(mutex); x+=n; V(mutex); send signal()14 15 end

17 resouce main()18 import test19 const int N = 5;20 op done()21 cap vm vmcap22 cap test t1, t2

24 t1 = create test(N, 1, done)25 vmcap = create vm() on "oran"26 t2 = create test(N, 2, done) on vmcap27 for [i=1 to 2 * N] 28 receive done()29 30 destroy t1;31 destroy t2;32 destroy vmcap;33 end

locate(n, hostname) → Assoziation von Nummer mit Rechner hostnamemymachine → liefert Nummer der eigenen Maschinemyvm → liefert Verweis auf virtuelle Maschine

33

3.4. VERTEILTE PROGRAMMIERUNG IN MPD


Listing 14 tin

1 resource main()2 import pipe3 const int n = 44 const int m = 105 const string[10] hosts[n] = ("maseru","harare","bamako" ,"bukavu")6 cap vm vmcap[m]7 int inp8 op chan[1:m+1] (int)9 op ret (int)

11 for [i=1 to n] locate(i,hosts[i]) 12 for [i=1 to m] vmcap[i] = create vm() on ((i-1) mod n)+1;13 write(hosts[((i-1) mod n)+1]," bereit")14

16 write("Bitte Werte eingeben")17 for [i=1 to m] read(inp); send chan[1](inp) 18 for [i=1 to m] create pipe(i,m,chan[i],chan[i+1],ret) on vmcap[i] 19 for [i=1 to m] receive chan[m+1](inp); writes(inp," ") 20 # for [i=1 to m] receive ret(inp); writes(inp," ") 21 write()

23 end main

Listing 15 tin2

1 resource pipe(int i, int m, cap(int) inp, cap(int) out, cap( int) result)2 int my_el3 int value

5 process test 6 receive inp(my_el)7 for [j= 1 to m-i] receive inp(value);8 if (my_el <= value) send out(value) 9 else send out(my_el); my_el = value

10

12 write("Prozess ",i," ermittelte Element ",my_el)

14 for [j = 1 to i-1] receive inp(value)15 send out(value)16 17 send out(my_el)

19 # send result(my_el)20 21 end

34

4 Die Bibliothek MPI

• MPI – MessagePassingInterface (de-factoStandard)

• MPI-Forum = ca. 40 Organisationen aus Industrie, Universitäten und Forschungslabors

– 1992 Gründung auf Supercomputing Conference

– 1994 MPI-1

– 1997 MPI-2

∗ http://www.mpi-forum.org

• Ziele:

– Quellcodeportabilität

– Kontinuität der parallelen Programmentwicklung

– Effizienz

– Flexibilität, Funktionalität ( > 128 Funktionen )

– C, C++, Fortran Anbindung

– Unterstützung heterogener Architekturen

• In Übungen: LAM-MPI

4.1 Grundkonzepte

• SPMD-Programmstruktur

• 6 Basisfunktionen

→ MPI_Init - Initialisierung→ MPI_Finalize - Terminierung→ MPI_Comm_rank - Prozess-ID abfragen→ MPI_Comm_size - #Prozesse bestimmen→ MPI_Send - Senden von Nachrichten→ MPI_Recv - Empfangen von Nachrichten

Listing 4.1: The „skeleton“ of an MPI program in C1 #include "mpi.h"

35

4.1. GRUNDKONZEPTE

KAPITEL 4. DIE BIBLIOTHEK MPI

3 main( int argc, char ** argv)4 5 int my_rank, nprocs

7 MPI_Init(&argc, &argv);8 MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);9 MPI_Comm_size(MPI_COMM_WORLD, &nprocs);

11 .12 .13 .

15 MPI_Finalize();16

int MPI_Init(int * argc, char ** argv)

︷︸︸︷

Adressen der Argumente von mainInitialisiert die MPI-Umgebung und definiert den KommunikatorMPI_COMM_WORLD. Ein Kommunikatordefiniert eine Gruppe von Prozessen und einen Kommunikationskontext.

int MPI_Comm_size( MPI_Comm comm, ← inint * size) ← out

ermittelt die Anzahl der Prozesse im Kommunikatorcomm

int MPI_Comm_rank( MPI_Comm comm, int * rank)

bestimmt Identifikation eines Prozesses innerhalb eines Kommunikators. Prozesse werden von 0 bis#Prozesse−1 nummeriert.

int MPI_Finalize()

beendet MPI

int MPI_Send(void * buf, \int count, > zu übertragendeMPI_datatype datatypes, / Datenint dest, → Rang des Empfängersint tag, → KennungMPI_Comm comm) → Kommunikator

int MPI_Recv(void * buf, \int count, > zu empfangende DatenMPI_datatype datatypes, /int source, → Rang des Empfängersint tag, → KennungMPI_Comm comm, → KommunikatorMPI_Status * status) → Quelle, Tag, Anz.

tatsächlichempfangener Daten

36

KAPITEL 4. DIE BIBLIOTHEK MPI4.2. KOMMUNIKATION

Beim Nachrichtenempfang können mittelsMPI_ANY_TAG undMPI_ANY_SOURCE Nachrichten mit be-liebigem Tag bzw. von beliebigem Sender empfangen werden.−→ VORSICHT : NichtdeterminismusIn diesem Fall kann man mit dem Status Argument die tatsächlichen Werte abfragen.

Felder:

→ status. MPI_SOURCE→ status. MPI_TAG

int MPI_Get_count( MPI_Status * status, → inMPI_DATATYPE type, → in

int * count) → out

liefert Anzahl tatsächlich empfangener Daten

Listing 4.2: MPI pairwise interactions program1 #include "mpi.h" /* Include file */

3 main( int argc, char * argv[]) /* Main program */4 int myid, np, ierr, lnbr, rnbr;5 real x[300], buff[300], forces[300];6 MPI_Status status;

8 ierr = MPI_Init(&argc, &argv); /* Initialize */9 if(ierr != MPI_SUCCESS) /* Check return code */

10 fprintf(stderr,"MPI initialization error\n");11 exit(1);12 13 MPI_Comm_size(MPI_COMM_WORLD, &np); /* Number of procs */14 MPI_Comm_rank(MPI_COMM_WORLD, &myid); /* My process id */15 lnbr = (myid+np-1)%np; /* Id of left neighbor */16 rnbr = (myid+1)%np; /* Id of right nbr */

18 initialize(x, buff, forces);

20 for (i=0; i<np-1; i++) /* Circulate messages */21 MPI_Send(buff, 300, MPI_FLOAT, rnbr, 0, MPI_COMM_WORLD);22 MPI_Recv(buff, 300, MPI_FLOAT, lnbr, 0, MPI_COMM_WORLD,23 &status);24 update_forces(x, buff, forces);25

27 print_forces(myid, forces); /* Print result */28 MPI_Finalize(); /* Shutdown */29

4.2 Kommunikation

MPI unterscheidet

(a) Punkt-zu-Punkt-Kommunikation

37

4.2. KOMMUNIKATION


(b) kollektive Kommunikation

• ad(a) Kommunikationsmodi 4 Arten von Sendefunktionen

Standard: MPI_Send (globale Operation)

gepuffert: MPI_BSend (lokale Operation)Nachricht wird gepuffert, damit das Senden unabhängig vom Empfangen abgeschlossenwerden kann.

synchron: MPI_SSend (globale Operation)Senden endet, wenn Datenempfang begonnen wurde.

ready: MPI_RSend (locale Operation)Sendender Prozess sendet sofort. Es muss gewährleistet sein, dassder Empfänger zumEmpfang bereit ist.→ Leistungssteigerung

Diese 4 Sendearten können blockierend oder nicht-blockierend sein.

nicht-blockierend:

– der Sendevorgang wird initiiert

– Überlappung von Kommunikation und Berechnungen

MPI_ISend MPI_ISSendMPI_IBSend MPI_IRSend

Es gibt nur eine EmpfangsoperationMPI_Recv , die auch nicht-blockierend sein kann (MPI_IRecv )

explizite Pufferverwaltung:

Bereitstellen:

MPI_Buffer_attach(void * buffer, int size)

Freigabe:

MPI_Buffer_detach(void * buffer, int size)

Bei nicht-blockierenden Sende-/Empfangsroutinen wird über ein zusätzliches Ausgabeargument:

MPI_Request * request

getestet werden, ob die Anweisung abgeschlossen ist:

MPI_Wait(request, status) ← warten bis abgeschlossenMPI_Test(request, flag, status) ← Kontrolle kommt zurück

• ad(b) kollektive Kommunikationsoperatoren Typen:

– globale Barrieren

– globale Datenbewegungen

– Reduktionen

38

KAPITEL 4. DIE BIBLIOTHEK MPI4.2. KOMMUNIKATION

MPI_Barrier( MPI_Comm comm)

→ globale Synchronisation aller Prozesse incomm

MPI_Bcast(void * inbuf, int count,MPI_Datatype type, int root, MPI_Comm comm)

→ Broadcast von Prozess root an alle anderen Prozesse incomm

MPI_Gather("Eingabepuffer", "Ausgabepuffer",int root, MPI_Comm comm)

MPI_Scatter("Eingabepuffer", "Ausgabepuffer",int root, MPI_Comm comm)

MPI_Reduce(void * inbuf, void * outbuf,int count, MPI_Datatypes type,MPI_Op op, int root, MPI_Comm comm)

MPI_Allreduce(void * inbuf, void * outbuf,int count, MPI_Datatypes type,MPI_Op op, MPI_Comm comm)

– Mögliche Operatoren

MPI_SUMMPI_PRODMPI_MAX, MPI_MINMPI_LOR, MPI_LAND, MPI_LXORMPI_BOR, MPI_BAND, MPI_BXOR

Synchronisierung am Ende

Beispiel:Berechnung vonπ durch Integration

∫ 1

0

4

1 + x2dx = π

Listing 4.3: Berechnung vonπ durch Integration1 #include "mpi.h"2 #include <stdio.h>3 #include <math.h>4 int main( int argc, char * argv[] )5 6 int n, myid, numprocs, i;7 double PI25DT = 3.141592653589793238462643;8 double mypi, pi, h, sum, x;

10 MPI_Init(&argc,&argv);

39

4.2. KOMMUNIKATION


11 MPI_Comm_size(MPI_COMM_WORLD,&numprocs);12 MPI_Comm_rank(MPI_COMM_WORLD,&myid);13 while (1) 14 if (myid == 0) 15 printf("Enter the number of intervals: (0 quits) ");16 scanf("%d",&n);17 18 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);19 if (n == 0)20 break;21 else 22 h = 1.0 / ( double) n;23 sum = 0.0;24 for (i = myid + 1; i <= n; i += numprocs) 25 x = h * (( double)i - 0.5);26 sum += (4.0 / (1.0 + x * x));27 28 mypi = h * sum;29 MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COM M_WORLD);30 if (myid == 0)31 printf("pi is approximately %.16f, Error is %.16f\n",32 pi, fabs(pi - PI25DT));33 34 35 MPI_Finalize();36 return 0;37

Beispiel:

• eindimensionales Temperaturproblem

• Glätten von Bilddaten

allgemeine Beschreibung:

VektorX = (X0, . . . , XN−1)BerechneX(t) mit X(0) = X

X(t+1)i =

X(t)i−1+2X

(t)i +X

(t)i+1

4 mit 0 ≤ i ≤ N − 1 0 ≤ t ≤ T − 1

→Algorithmus: Iteration mit abwechselnden Kommunikationen und Berechnungen

Listing 4.4: Outline of an MPI finite difference algorithm1 main(int argc, char * argv[]) 2 MPI_Comm com = MPI_COMM_WORLD;3 MPI_Init(&argc, &argv);4 MPI_Comm_size(com, &np);5 MPI_Comm_rank(com, &me);6 if (me == 0) 7 read_problem_size(&size);8 buff[0] = size;9

10 / * Global broadcast propagates this data to all processes * /11 MPI_Bcast(buff, 1, MPI_INT, 0, com);12 / * Extract problem size from buff; allocate space for local dat a * /13 lsize = buff[0]/np;14 local = malloc(lsize+2);15 / * Read input data at process 0; then distribute to processes * /

40

KAPITEL 4. DIE BIBLIOTHEK MPI4.3. KOMMUNIKATOREN, PROZESSGRUPPEN UND TOPOLOGIEINFORMATIONEN

16 if (me == 0) work = malloc(size); read_array(work); 17 MPI_Scatter(work, lsize, MPI_FLOAT, local+1, lsize,18 MPI_FLOAT, 0, com);19 lnbr = (me+np-1)%np; / * Determine my neighbors in ring * /20 rnbr = (me+1)%np;21 globalerr = 99999.0;22 while (globalerr > 0.1) / * Repeat until termination * /23 / * Exchange boundary values with neighborts * /24 ls = local+lsize;25 MPI_Send(local+2, 1, MPI_FLOAT, lnbr, 10, com);26 MPI_Recv(local+1, 1, MPI_FLOAT, rnbr, 10, com, &status);27 MPI_Send(ls-2, 1, MPI_FLOAT, rnbr, 20, com);28 MPI_Recv(ls-1, 1, MPI_FLOAT, lnbr, 20, com, &status);29 compute(local);30 localerr = maxerror(local); / * Determine local error * /31 / * Find maximum local error, and replicate in each process * /32 MPI_Allreduce(&localerr, &globalerr, 1, MPI_FLOAT,33 MPI_MAX, com);34 35 / * Collect results at process 0 * /36 MPI_Gather(local, lsize, MPI_FLOAT, work, size,37 MPI_FLOAT, 0, com);38 if (me == 0) write_array(work); free(work); 39 MPI_Finalize();40

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−P0 | l s i z e | l s i z e | . . . . . | l s i z e |

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−| | | | | |\ / \ / \ /

−−−−−− −−−−−− −−−−−−−−−| P0 | | P1 | | Pnp−1 |−−−−−− −−−−−− −−−−−−−−−

| | | | | |\ / \ / \ /

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−P0 | l s i z e | l s i z e | . . . . . | l s i z e |

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−( G r a f i k s t immt NICHT)

alternative Realisierung des Datenaustauschs

MPI_Irecv(ls+1, 1, MPI_FLOAT, rnbr, 10, com, &r1)MPI_Rsend(local, 1, MPI_FLOAT, lnbr, 10, com)MPI_Irecv(local, 1, MPI_FLOAT, lnbr, 20, com, &r2)MPI_Rsend(ls, 1, MPI_FLOAT, rnbr, 20, com)

MPI_Wait (r1, &status)MPI_Wait (r2, &status)

MPI_WAITALL (2, req, status︸︷︷︸

Felder

)

compute (local)

4.3 Kommunikatoren, Prozessgruppen und Topologieinformationen

in fast allen Kommunikationsbibliotheken

41

4.3. KOMMUNIKATOREN, PROZESSGRUPPEN UND TOPOLOGIEINFORMATIONEN


• Nachrichtenkennungen (tags)

• Prozessgruppen

neu in MPI:

• Kommunikatoren

– bessere Kapselung von Bibliotheksfunktionen– Erleichterung des Umgangs mit Prozessgruppen und virtuellen Topologie

Ein Kommunikator

• bestimmt eine Gruppe von Prozessen das heißt eine geordnete Menge vonProzessen mitlokalemRang ∈ 0, . . . ,#Prozesse − 1

• definiert einen Kontext für Kommunikationen

→ Einführung separater, sicherer d. h. sich nicht beeinflussender Universen zum Nachrichtenaus-tausch

Beispiel:

Was geschieht, wenn P2 verzögert wird?

DEADLOCK

42


Vordefinierte Kommunikatoren:

MPI_COMM_WORLD "Gruppe aller Prozesse"MPI_COMM_SELF "Prozess selbst"MPI_COMM_NULL "ungültiger Kommunikator"

4.3.1 Prozessgruppen: Konstruktion, Analyse, Manipulatio n

MPI_Comm_group( MPI_Comm comm, MPI_Group * group)

liefert Prozessgruppe zu Kommunikatorcomm

MPI_Group_union( MPI_Group group1,MPI_Group group2, MPI_Group * group)

MPI_Group_intersection( MPI_Group group1,MPI_Group group2, MPI_Group * group)

MPI_Group_difference( MPI_Group group1,MPI_Group group2, MPI_Group * group)

Vereinigung und Schnitt sind assoziativ, aber wegen der Prozessordnung nicht kommutativ.→ leere GruppeMPI_GROUP_EMPTY

MPI_Group_size( MPI_Group group, int * size)MPI_Group_rank( MPI_Group group, int * rank)

Falls Prozess nicht in Gruppe, ErgebnisMPI_UNDEFINED

MPI_Group_incl(group, n, ranks, ← innewgroup) ← out

MPI_Group_excl(group, n, ranks, ← innewgroup) ← out

erzeugt eine neue Gruppe mitn Prozessen, die ingroup die Rängeranks [0] . . . ranks [n − 1] haben undin newgroup die Ränge0 . . . n − 1

→ auch Umordnung von Prozessen in Gruppe möglich

Die excl-Variante streicht die durchranks angegebenen Prozesse ausgroup .

MPI_Group_free(group) deallokiert Prozessgruppe

43



4.3.2 Kommunikatoren

Neue Kommunikatoren können aus bestehenden Kommunikatoren oder Prozessgruppen gebildet werden.

MPI_Comm_dup( MPI_Comm comm, MPI_Comm * newcomm)

→ neuer Kommunikatoren mit derselben Prozessgruppe, aber neuem Kontext.

MPI_Comm_create(comm, group, ← innewcomm) ← out

group muss Teilmenge der Prozessgruppe voncommsein.

MPI_Comm_split(comm, color, key, ← innewcomm) ← out

Aufteilung der Prozessgruppe voncommin disjunkte Teilgruppen gemäßcolor , Ordnung innerhalb derTeilgruppen gemäßkey , bei identischen Schlüsseln Ordnung auscomm.

MPI_Comm_free( MPI_Comm * comm)

(A)

MPI_Comm comm, newcomm;int myid, color;MPI_Comm_rank(comm, &myid);color = myid % 3;MPI_Comm_split(comm, color, myid, &newcomm)

(B) Master-/ Worker-Schema mit separatem Kommunikator für Worker-Prozess

44


Abschlusskriterium: Genauigkeit der Approximation <ε1

→ MPI_ALLREDUCE auf Worker

P0 P1 P2l i b _ c a l l ( comm_b ) l i b _ c a l l ( comm_b ) l i b _ c a l l ( comm_b )MPI_RECV . . . <−−−−−−−− MPI_SEND . . . MPI_SEND . . .MPI_RECV . . . <−−\MPI_BARRIER \ 2 MPI_BARRIER MPI_BARRIER

l i b _ c a l l ( comm_b ) \ l i b _ c a l l ( comm_b ) l i b _ c a l l ( comm_b )MPI_RECV . . . \ MPI_SEND . . . MPI_SEND . . .MPI_RECV . . .

4.3.3 Virtuelle Topologien

Unterstützung von festen Kommunikationsstrukturen

• effizientere Abbildung auf physikalische Zielmaschine

• einfachere Benennung von Prozessen

• Verbesserung der Lesbarkeit von Programmen

zwei Arten:

• kartesische Topologien

– Gitter, Würfel, Torus, Hypercube

• Graphentopologie

feste Assoziation mit Kommunikator

Erzeugung führt zu neuem Kommunikator

MPI_Cart_create(MPI_Comm comm_old,int ndims, ←− #Dimensionen[int] dims, ←− Ausdehnung in den Dimensionen[bool] periods, ←− Boolsche Werte, die pro

Dimensionen zyklische Verbindungenerlauben oder nicht

bool reorder, ←− False verbietet die Umordung vonProzessen bzgl. der Ränge

MPI_Comm * comm_cart)

1Parameter2back-masking Problem

45



Beispiel:

dims[0] = 4 ndims = 2dims[1] = 3periods[0]= periods[1]= falsereorder = true

Dim 1−−→0↓ (0, 0)0 (0, 1)1 (0, 2)2

(1, 0)3 (1, 1)4 (1, 2)5

(2, 0)6 (2, 1)7 (2, 2)8

(3, 0)9 (3, 1)10 (3, 2)11

Die Kommunikationwird nicht aufdiese Topologieeingeschränkt

Hypercube:n−dim Torus (zyklisch) mit je genau 2 Proz. pro Dimension

4.3.4 Zugriffsroutinen

MPI_Cart_rank(comm, coords, ←− inrank) ←− out

comm - Kommunikator mit kartesischer Topologie

MPI_Cart_coords(comm, rank, maxdims, ←− incoords) ←− out

coords - Koordinaten zu Prozess mit Rang rank

MPI_Cart_shift(comm, direktion, disp, ←− inrank_source, rank_dest) ←− out

direktion - Dimension für shift

disp - #shift − pos

Beispiel:commmit zwei dimensionaler Torusstruktur und Felda, dass elementweise verteilt ist. Verschie-ben deri−ten Spalte umi Elemente (Rotieren)

MPI_Comm_rank(comm, &rank);MPI_Cart_coords(comm, rank, maxdims, &coords);MPI_Cart_shift(comm, 0, coords[1], &source, &dest);MPI_Sendrecv_replace3(a, 1, MPI_REAL, dest, 0,

source, 0, comm, &status);

Bestimmen einer balancierten Gitterstruktur zu einem Kommunikator

MPI_Dims_create(nnodes, ndims, ←− indims) ←− out

3Senden und Empfangen auf dem selben Datenbereich

46

KAPITEL 4. DIE BIBLIOTHEK MPI4.4. ABGELEITETE DATENTYPEN

Im Felddims können Felder vorbesetzt werden. Dabei mussnnodes Vielfaches von∏

i mit dims[i] 6=0

dims [i]

sein.

Beispiel:

dims vor Aufruf Aufrufparameter dims nach Aufruf(0,0) (6,2,dims) (3,2)

(7,2,dims) (7,1)(0,3,0) (6,3,dims) (2,3,1)

(7,3,dims) ERROR

4.3.5 Interkommunikatoren

bisher: Intrakommunikator−→ Kommunikator innerhalb von Prozessgruppen

Interkommunikatoren dienen der Kommunikation zwischen disjunkten Prozessgruppen.

Sie erlauben nur Punkt-zu-Punkt Kommunikation.

Erzeugung überMPI_Intercomm_create

4.4 Abgeleitete Datentypen

Nachrichten

Abbildung 4.1: Zusammenhängender Puffer

Um nicht zusammenhängende Speicherbereiche bzw. Objekte mit unterschiedlichen Teiltypenzu versenden, können eigene Datentypen definiert werden.

47

4.4. ABGELEITETE DATENTYPEN


4.4.1 Spezifikation neuer Datentypen

Eine Typabbildung (type map) ist eine Folge von Paaren der Form:

< typei, dispi |0 ≤ i < n >

wobeitypei Basistypen unddispi ganze Zahlen / relative Adressen (displacements) sind.Die Folge der Typen< typei |0 ≤ i < n > heißt Typsignatur der Typabbildung. Mit einerBasisadressebuf spezifiziert eine Typabbildung einen Komm.- Puffer mitn Einträgen. Eintragi beginnt an Adressebuf + dispi und hat Typtypei.

Beispiel:

MPI_INT hat Typabb. <(int, 0)><(int, 0), (char, 4)>

bezeichnet [0 ---------- int ------------][4-char-]

MPI_Type_Contignous(count, ←− ⇒ 0oldtype, newtype) ←− MPI_Datatype

MPI_Send(buf, count, type, . . .)MPI_Type_Contignous(count, type, newtype)MPI_Send(buf, 1, newtype, . . .)MPI_Type_vector(count, blocklength, stride,

oldtype, newtype)

Beispiel:

count=2, blocklength=3, stride=5oldtype [ //]newtype [ //][//][//][--][--][//][//][//][--][--]

1.Block 2.Block------------------

Schrittweite (Stride)

Beispiel:Sende5−te Spalte einer Zeilenweise gespeicherten Matrix.

double results [IMAX][JMAX],MPI_Datatype col,MPI_Type_vector(IMAX, 1, JMAX, MPI_DOUBLE, &col)MPI_Send(&result 4[0][4], 1, col, . . .)

45te Spalte

48

5 Parallele Algorithmen

5.1 Das PRAM- Rechnermodell

PRAM: ParallelRandomAccessMachine (FORTUNE, WYLLIE 1978)

einfach, unrealistisch, da Vernachlässigung von Interprozessorkommunikation, konstanter Zugriff aufglobalen Speicher für alle Prozessoren

→ SIMD (Single InstruktionMultiple Data) Modell

Abbildung 5.1: Aufbau einer PRAM

Arbeitsweise:

• Ein- / Ausgabe über den globalen Speicher

• Die Berechnung beginnt mit einem einzelnen aktiven PE.

• In einem Berechnungsschritt kann ein aktives PE ein anderes PE aktivieren

– eine einzelne RAM Operation: ALU-Ops, Sprünge,. . .– einen lokalen oder globalen Speicherplatz lesen oder schreiben– Alle aktiven PEs führen dieselbe Instruktion aus.

• Die Berechnung terminiert, wenn der letzte aktive Prozessor stoppt.

Kosten einer PRAM-Berechnung#Proz∗ parallele Zeitkomplexität z. B.Θ (p log p)

Speicherorganisation:

49

5.1. DAS PRAM- RECHNERMODELL

KAPITEL 5. PARALLELE ALGORITHMEN

• EREW (ExclusiveReadExclusiveWrite)keine Lese- / Schreibkonflikte erlaubt

• CREW (ConcurrentReadExclusiveWrite)gleichzeitiges Lesen erlaubt, gleichzeitiges Schreiben nicht „Default-Modell“

• CRCW (ConcurrentReadConcurrentWrite)gleichzeitiges Lesen und Schreiben erlaubt

Auflösen von Schreibkonflikten bei CRCW:

• COMMON: Alle in eine Speicherposition schreibenden Proz. schreiben den selben Wert

• ARBITRARY: zufällige Auswahl

• PRIORITY: Der Proz. mit kleinstem Index darf schreiben.

Satz 1.1:Ein p-Proz. CRCW-PRIORITY-PRAM kann durch eine p-Proz. EREW-PRAM simuliert werden.Dabei wird die Zeitkomplexität um einen Faktor(log p) erhöht.

Beispiel:PRAM mit N = 2k Prozessoren

In einem unsortierten Datenbereich mitn ≥ N Plätzen soll ein Elementx gesucht werden.sequentieller Algorithmus: lineare Suche

worst case:n Schritte

average case:n2 Schritte

EREW-PRAM: SeiPi deri-te Proz.0 ≤ i ≤ N − 1

Vorphase:Aktivierung der N Proz. und Broadcast des Wertes x (wegen ER)→ log N Schritte

Berechnungsphase:Aufteilung des Datenbereichs inN Teilbereiche der Größe(n div N) bzw.(n div N) + 1.

Jeder ProzessorPi, 0 ≤ i ≤ N − 1, durchläuft im Gleichtakt mit den anderen Prozessoren seinenTeilbereich und suchtx.

Was geschieht, wennx von einem Prozessor gefunden wird? Jeder Prozessor schreibt sein Endsignalin einen eigenen Platz im Speicher. Nach jedem Vergleichschritt wird eine globale Reduktion mitlogischer Oder-Verknüpfung der Endsignale durchgeführt. Im Schritt j, (0 ≤ j ≤ k − 1) wenden dieProzessorenPi, 0 ≤ i ≤ 2k−1−j die Verknüpfung auf ihr eigenes Endsignal und das vonPi+2k−1−j

an und schreiben das Ergebnis in die Speicherzelle vonPi

50

KAPITEL 5. PARALLELE ALGORITHMEN5.1. DAS PRAM- RECHNERMODELL

P0 P1 P7

Anschließend Broadcast des Ergebnis ink-Schritten→ worst case Zeitkomplexität

log N +⌈ n

N

⌉

∗ (1 + 2 log N)

CREW-PRAMAnfängliches Broadcast des WertesxStatt Reduktion / Broadcast der Endsignale integriertes Butterfly-Schema

XXXXXXXXXXXXXXXXXXXXXXXXXXX



XXXXXXXXXXXXXXXXXXXXXXXXXXX ...

fffffffffffffffffffffffffff




QQQQQQQQQQ

QQQQQQQQQQ

mmmmmmmmmm

mmmmmmmmmm

QQQQQQQQQQ

QQQQQQQQQQ

mmmmmmmmmm

mmmmmmmmmm

CCCC

C

CC

CCC

CC

CCC

CC

CCC

→ worst case Zeitkomplexität

1 +⌈ n

N

⌉

∗ (1 + log N)

CRCW-PRAMgemeinsames Schreiben der Endsignale in globalen Speicher.→ worst case Zeitkomplexität

1 +⌈ n

N

⌉

∗ (1 + 1)

Elementare PRAM-Algorithmen

• Broadcast / Reduktion

– → ⌈log p⌉ Schritte fürp ProzessorenReduktion vonn Werten mit assoziativen binären Operationen aufn

2 Prozessoren mitΘ (log n) Schritten

• Präfixsummen (Scans) – fürn Werte in⌈log n⌉ parallelen Schritten (n − 1 Prozessoren)

51

5.1. DAS PRAM- RECHNERMODELL


Gegeben:n Wertea0, . . . , an−1 und assoziative Operation⊕

Bestimmen Werte:

a0

a0 ⊕ a1

a0 ⊕ a1 ⊕ a2...

a0 ⊕ a1 ⊕ a2 ⊕ · · · ⊕ an−1

CREW-Verfahren:

• globale Variablen:n, A [0 . . . (n − 1)] , j

• Anfangsbedingung:A [0 . . . (n − 1)] enthält Eingabeliste

• Endbedingung:A [i] enthaltea0 ⊕ . . . ⊕ ai

1 begin2 spawn(P1, . . . , Pn−1)3 for all Pi where 1 ≤ i ≤ n − 1 do4 for j=0 to ⌈log n⌉ − 1 do

5 if``

i − 2j´

≥ 0´

then

6 A [i] ← A [i] ⊕ Aˆ

i − 2j˜

7 fi8 od9 od

10 end

Beispiel:

P1 P2 P3 P4 P5 P6

A 0 1 2 3 4 5 6

3

j=0¹¹ !!B

BBBB

BBB 1

²² ""EEEEEEEE 0

²² ""EEEEEEEE 4

²² ""EEEEEEEE 2

²² ""EEEEEEEE 6

²² ""EEEE

EEEE

5

²²Schritt 1

3

j=1¹¹ ((QQQQQQQQQQQQQQQQ 4

((RRRRRRRRRRRRRRRR 1

²² ((RRRRRRRRRRRRRRRR 4

²² ((RRRRRRRRRRRRRRR 6

²² ((RRRRRRRRRRRRRRR 8

²²

11

²²Schritt 2

3

j=2¹¹ ,,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 4

,,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 4

,,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 8 7

²²

12

²²

17

²²Schritt 3

3 4 4 8 10 16 21

Kosten:n − 1 Prozessoren,Θ (log n) Schritte

Definition: Ein paralleler Algorithmus heißt kostenoptimal, wenn seine Kosten (#Proz. * parallele Laufzeit)in derselben Komplexitätsklasse liegen wie ein optimaler sequenzieller Algorithmus.

Analyse der elementaren Verfahren

• Reduktion

– parallele Kosten:Θ (n log n) (nicht optimal!)

52

KAPITEL 5. PARALLELE ALGORITHMEN5.1. DAS PRAM- RECHNERMODELL

– optimaler sequenzieller Algorithmus:Θ(n)

– Anzahl der Operationen:par. Algorithmus:

∑log ni=1 n · 2−i =

∑log(n−1)i=0 2i = n − 1

seq. Algorithmus:n − 1

• Präfixsummen

– par. KostenΘ (n · log n) (nicht optimal)opt. seq. Alg.Θ (n)

– Anzahl der Operationenpar. Alg.:

∑⌈log n⌉−1i=0

(n − 2i

)· 1 = . . . = Θ (n log n)

seq. Alg.:n − 1

Satz 1.2 (BRENT 1974):SeiA ein paralleler Algorithmus mit Ausführungszeitt. FallsA m-Operationenausführt, so kannA mit p-Prozessoren in der Zeitt + (m−t)

pausgeführt werden.

Beweis Satz 1.2.Seisi die Anzahl der Operationen die imi-ten Schritt ausgeführt werden,1 ≤ i ≤ t.Es gilt:

∑ti=1 si = m

Mit nur p Prozessoren kann deri-te Schritt vonA in⌈

si

p

⌉

Schritten simuliert werden. Damit folgt für die

Anzahl der Schritte mitp Prozessoren:

t∑

i=1

⌈si

p

⌉

≤t∑

i=1

si + p − 1

p= t +

t∑

i=1

si − 1

p= t +

m − t

p

• Um ein kostenoptimales Verhalten zur parallelen Reduktion zu bestimmen, kann man versuchen, dieAnzahl Prozessoren zu reduzieren.

• Um n − 1 Operationen inlog n Schritten kostenoptimal auszuführen, sollten nurp = n−1log n

=

Θ(

nlog n

)

Prozessoren eingesetzt werden. Mit Brents Theorem folgt, dass sichdie parallele Laufzeit

wie folgt erhöht:

⌈log n⌉ +n − 1 − ⌈log n⌉

⌊n

log n

⌋ = Θ

(

log n + log n −log n

n−

log2 n

n

)

= Θ (log n)

=⇒ Die Komplexitätsklasse des parallelen Algorithmus wird durch die Reduktion derPro-

zessorzahl nicht verändert, d. h. die parallele Reduktion auf⌊

nlog n

⌋

Prozesse ist kosten-

optimal.

• Zur Herleitung eines kostenoptimalen Algorithmus für die Präfixsummenberechnung genügt es kaum,die Anzahl der Prozessoren zu reduzieren. Besser ist es den Berechnungen der Prozessoren auf denihnen zugeordneten Datenseqmenten das optimale sequenzielle Verfahreneinzusetzen.

• Berechnung der Präfixsummen vonn Werten mitp < n − 1 Prozessoren

53

5.2. RECHNERMODELLE MIT VERTEILTEM SPEICHER


– Aufteilung dern Werte inp Teilbereiche mit max⌈

np

⌉

Werten

– Die p Prozessoren rechnen mit dem optimalen sequenziellen Verfahren die Präfixsummen aufihren Teilbereichen−→

⌈np

⌉

− 1 Schritte

– Die erstenp−1 Prozessoren berechnen die Präfixsummen der Gesamtsummen ihrer Teilbereichemit dem parallelen Verfahren:−→ ⌈log (p − 1)⌉ Schritte.

– Die letztenp − 1 Prozessoren addieren die Gesamtsummen der niedrigeren Blöcke auf alleElemente ihrer Teilbereiche:−→

⌈np

⌉

Additionen

Gesamtaufwand:⌈

np

⌉

− 1 + ⌈log (p − 1)⌉ +⌈

np

⌉

= Θ(

np

+ log p)

Beispiel:n = 14, ⌈log n⌉ = 4, p = 4

A 2 1 4 −3 0 −2 5 1 −1 2 4 0 3 7

Schritt(iii) 2 3 7 4 0 −2 3 4 −1 1 5 5 3 104 8 94 8 13

(iv) 2 3 7 4 4 2 7 8 7 9 13 13 16 23

Gesamtzahl der Operationen:

p ·

(⌈n

p

⌉

− 1

)

+ Θ (p log p) + (p − 1) ·

⌈n

p

⌉

= Θ (n + p log p)

Sei:p = Θ(

nlog n

)

dann folgt der Gesamtaufwand:Θ(

nn

log n

+ log nlog n

)

= Θ (log n)

=⇒ Kosten:Θ(

nlog n

)

· Θ (log n) = Θ (n)

=⇒ Kostenoptimalität

Gesamtzahl der Operationen:Θ(

n + nlog n

log nlog n

)

= Θ (n)

5.2 Rechnermodelle mit verteiltem Speicher

• bestimmendes Element: Verbindungsnetzwerk

– feste Knoten-zu-Knoten-Verbindungen

• Bewertungskriterien:

– Durchmesser, längster Abstand zwischen zwei Knoten

54

KAPITEL 5. PARALLELE ALGORITHMEN5.2. RECHNERMODELLE MIT VERTEILTEM SPEICHER

– Halbierungsbreite, minimale Anzahl von Verbindungslinien, die durchtrennt werden, um dasNetzwerk in zwei etwa gleichgroße Teile zu zerlegen.

– Verbindungsgrad, Anzahl der Verbindungen pro Knoten

Beispiel:

• Gitter mit q Dim. undk Knoten pro Dim.−→ kq Knoten

Durchmesser:(k − 1) ∗ q

Halbierungsbreite:k(q−1)

Verbindungsgrad:2q

• Torus, Gitter mit zyklischen Verbindungen in allen Dimensionen

Durchmesser:q ∗⌊

k2

⌋

Halbierungsbreite:2 ∗ k(q−1)

Verbindungsgrad:2q

• Binärbaum der Tiefek → 2k+1 − 1 Knoten

Durchmesser:2k

Halbierungsbreite:1Verbindungsgrad:3

• Hypercube der Dimensionk

Durchmesser:kHalbierungsbreite:2(k−1)

Verbindungsgrad:k

• Shuffle–Exchange–Netzwerk2k Knoten mit Nummerierung von0 bis2k−1, zwei verschiedene Verbindungen:

Exchange-Verbindung:(bk−1 . . . b10)2 ↔ (bk−1 . . . b11)2Shuffle-Verbindung:(bk−1bk−2 . . . b0)2 → (bk−2 . . . b0bk−1)2

Beispiel: Shuffle–Exchange–Netzwerk

•´´

oo // • (( • oo // ++• ,,• oo //ll •kk •hh oo // •´´

000 001 010 011 100 101 110 111

000 • // • 000

001 •,,YYYYYYYYYYYYYYY • 001

010 •

))TTTTTTTTTTTTTTTT • 010

011 •

&&NNNNNNNNNNNNNNNNN • 011

100 •

88ppppppppppppppppp• 100

101 •

55jjjjjjjjjjjjjjjj• 101

110 •

22eeeeeeeeeeeeeee • 110

111 • // • 111

55

5.3. PARALLELES SORTIEREN


Shuffle-Exchange-Reduktion

000 001 010 011 100 101 110 111

• Basisidee: Reduktion von zwei Zwischenergebnissen pro Schritt−→ log viele Schritte

Zu kombinierende Werte werden in aufeinander folgende Shuffle-Exchange-Schritten zusammenge-bracht.

• allgemeine Verfahren: Parameter in #Prozessorelementenn = 2k

1 lokal val, tmp2 begin3 for j=0 to k-1 do4 for all Pi where 0 ≤ i < n do5 send val to Pi //shuffle6 receive val from Pi //shuffle7 send val to P<i> //exchange8 receive tmp from P<i> //exchange9 val := val + tmp

10 od11 od12 end

Beispiel:

6 −4 2 19 −9 0 7 56 − 9 −4 − 0

1.Schritt −3 −3 −4 −4 9 9 24 242.Schritt 6 6 6 6 20 20 20 203.Schritt 26 26 26 26 26 26 26 26

5.3 Paralleles Sortieren

im sequentiellen Fall: AufwandΩ (n log n) bei vergleichsbasierten Verfahren.

Ziel im parallelen Fall: poly. log. Aufwand mit binearer Proz.-Zahl.

5.3.1 Ein CRCW-Verfahren mit konstantem Zeitaufwand

n2 Proz. einer CRCW-PRAM könnenn Elemente in konstanter Zeit sortieren, falls

• der Aktivierungsaufwand(O (log n)) vernachlässigt werden kann und

• beim CW die Summe der Werte geschrieben wird

Ansatz: „Ranksort“

56

KAPITEL 5. PARALLELE ALGORITHMEN5.3. PARALLELES SORTIEREN

Vergleiche jedes Element mit jedem anderen und zähle die Anzahl der kleineren Elemente−→ Position in sortierter Liste

Algorithmus: Parametern = # zu sortierende Elemente

Globale Vars:a [0 . . . (n − 1)] zu sortierende Elemente

position [0 . . . (n − 1)] Position der Elemente in sortierter Listesorted [0 . . . (n − 1)]

Listing 16 „Ranksort“

1 begin2 spawn Pi,j with 0 ≤ i, j < n

3 for all Pi,j with 0 ≤ i, j < n do4 position\left[i\right]:=05 if a [i] > a [j] or ( a [i] = a [j] and i > j)6 then position\left[i\right]:=1 fi7 od8 for all Pi,0 with 0 ≤ i < n do sorted[position[i]]:=a[i]

par. ZeitO (1)par. KostenO

(n2

)

−→ nicht kostenoptimal

5.3.2 Sortiernetze

BATCHER 1968: Netze zum Sortieren in polylogarithmischer Zeithier: odd-even-merge-sort

Beispiel:klassische sequentielle Verfahren zum Mischen sortierter Listen miti bzw.j Elementen im worst ca-se:i + j − 1

Beobachtung: Welche Elemente verglichen werden, hängt von vorherigen Vergleichen ab.−→ wissenabhängige Verfahren (non-oblivious)

im folgenden: festes Vergleichsschema−→ wissensunabhängige Verfahren (oblivious)

Beispiel:Tunierschema beim Tennis

Sieger

Sieger

Ein Komparator erhält zwei Eingaben und produziert zwei Ausgaben,das Minimum und das Maximum derbeiden Eingaben:

57



+a

b

min(a, b)

max(a, b)

Im folgenden nehmen wir an, dass gleichlange Folgen der Längen = 2k zu Mischen sind.

Induktive Konstruktion eines(n, n)-Mergers(n = 2k

)

(−→ odd-even-merger)

Gegeben seien zwei sortierte Folgen:

A = (a1, . . . , an)

B = (b1, . . . , bn)

n = 1: Komparator ist(1, 1)-Merger.n = 2:

min

min

max

max

a1

a2

b1

b2

c1

c2

c3

c4

beliebigesn > 1

Voraussetzung: Es stehen(

n2 , n

2

)-Merger zur Verfügung.

Notation:x[k]

lbezeichne die Teilliste vonXi die mit demk-ten Folgenglied beginnt und jedesl-te nachfol-

gende Glied wählt< Xk+i∗l | i ≥ 0 >

A[1]

2 ,B[1]

2 Teillisten der Elemente mit ungeradem Index.

Satz 5.1.:Die ResultatfolgeC ist sortiert.

58


Beispiel: (4, 4)-Merger

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

(2,2)-Merger

(2,2)-Merger

Es werden FolgenD undE hergestellt, die so ineinander geschoben werden (interleaving), dass die resul-tierende Folge bis auf eventuelle Nachbarvertauschungen sortiert ist.

Interleaving-Schema

d1 d2

''OOOOOOOO d3

''OOOOOOOO d4

''PPPPPPPP . . . . . . dn

))TTTTTTTTTT

e1 e2 e3 . . . . . . en−1 en//

d1 d2 e1 d3 e2 d4 e3. . . . . . dn en−1 en

Satz 5.2. (0-1-Prinzip):Ein Sortieralgorithmus bestehe nur aus vorherbestimmten, d. h. eingabeunabhän-gigen Vergleichen-Austausch-Anweisungen. Dann gilt: Sortiert der Algorithmus jede Eingabefolge, die nuraus Nullen und Einsen besteht, so sortiert er jede Eingabefolge.

Beweis von Satz 5.2 durch Widerspruch:

Annahme: Die EingabefolgeX1, . . . , Xn wird von dem wissensunabhängigen Sortierverfahrennicht korrekt sortiert, d. h. nicht in die Reihenfolge

Xπ(1) ≤ Xπ(2) ≤ . . . ≤ Xπ(n)

gebracht.

59



• Seik die erste Stelle, an der sich die sortierte Folge von der Ausgabe des Algorithmus

Xσ(1), . . . , Xσ(n)

unterscheidet d. h.Xσ(k) > Xπ(k)

Definiere zuX1, . . . , Xn undk eine 0-1-Folge

yi :=

0, falls xi ≤ xπ(k)

1, falls xi > xπ(k)

Wird diese Folge dem wissensunabhängigem Sortieralgorithmus übergeben, so finden die gleichen Ver-gleichs-/ Austauschschritte statt, dennXi ≥ Xj y Yi ≥ Yj . Insbesondere steht an der k-ten Stelle derAusgabefolgeyσ(k) = 1 und irgendwo rechts daneben der Wertyπ(k) = 0. Die 0-1-Folge wird nicht richtigsortiert. (WIDERSPRUCH)

Beweis von Satz 5.1. mit dem 0-1-Prinzip.A und B seien sortierte 0-1-Folgen. Seiak die letzte Null derFolgeA undbl die letzte Null der FolgeB, d. h.

A = (0 . . . 0︸︷︷︸

k

1 . . . 1) B = (0 . . . 0︸︷︷︸

l

1 . . . 1)

Es gilt:0 ≤ k︸︷︷︸

nur Einsen

, l ≤ n︸︷︷︸

nur Nullen

Dann gilt für die Teilfolgen

A[1]

2 hat⌈

k2

⌉Nullen,

B[1]

2 entsprechend⌈

l2

⌉

A[2]

2 hat⌊

k2

⌋Nullen,

B[2]

2 entsprechend⌊

l2

⌋

Damit hat die FolgeD γ :=⌈

k2

⌉+

⌈l2

⌉Nullen

und die Folge Eδ :=⌊

k2

⌋+

⌊l2

⌋Nullen

Für die Differenz∆ := γ − δ gilt nach Definition der Gaußklammern:

∆ ∈

0︷︸︸︷

beide gerade,

1︷︸︸︷

eins gerade eins ungerade,

2︷︸︸︷

beide ungerade

Wir betrachten die Interleaving-Schemata für diese 3 Fälle:

∆ = 2D . . . 0 0 0 1 . . . . . .

\ \ \E . . . . . . . . . 0 1 1 . . .

. . . 0 0 0 0 1 1 1 . . .

60


∆ = 1D . . . 0 0 0 1 . . . . . . . . .

\ \ \E . . . . . . . . . 0 0 1 . . .

. . . 0 0 0 0 0 0 1 1 . . .

∆ = 0D . . . 0 0 0 1 1 . . . . . .

\ \ \ \E . . . . . . . . . 0 0 0 1 . . .

. . . 0 0 0 0 0 0 0 1 1 1 . . .

Aufbau eines Sortiernetzes aus(n, n)-Merger

O.B.d.A.n = 2k

Durchlaufzeit: (Zahl vertikaler Komparatorstufen)t(n) =∑k

i=0 τ(2i), wobeiτ(n) die Durchlaufzeit eines(n, n)-Mergers sei.

Komparatorzahl:N(n) =k∑

i=0

2k−i ∗ ν(2i), wobeiν(n) die Komparatoranzahl eines(n, n)-Mergers sei.

Bestimmeτ(n) undν(n) durch Analyse der(n, n)-Merger:

τ(1) = 1; ν(1) = 1τ(2n) = τ(n) + 1; ν(2n) = 2ν(n) + n − 1

Mit vollst. Induktion zeigt man leicht:τ(n) = 1 + log n; ν(n) = 1 + n · log n

Damit folgt:

t(n) =k∑

i=0

(1 + i) = (k+1)(k+2)2 ∈ O(k2) = O(log2 n)

N(n) =k∑

i=0

2k−i(1 + i ∗ 2i) = . . . = 2k+1 − 1 + 2k k(k+1)2 ∈ O(n log2 n)

=⇒ parallele Kosten:O(n log4 n)

61



5.3.3 Der Algorithmus von Cole

optimale Lösung auf CREW-PRAM, d. h.O(log n) Zeit mit O(n) Prozessoren.

„paralleler Mergesort im vollständigem Binärbaum“

Hilfsmittel: Skelette von Folgen

Definition. 5.3.: X undY seien sortierte endliche Folgen ganzer Zahlen.[X] entstehe ausX durch Hinzu-nahme der Elemente−∞ und+∞.

(a) Seiena < b undx ∈ X.x heißt zwischena undb:y a < x ≤ b

(b) X heißt Skelett vonY , in ZeichenX ∝ Y , falls für allek ≥ 2 zwischen jek Elementen von[X] höchstens2k − 1 Elemente vonY liegen.

Notation: • X gemeinsames Skelett vonY undZ

X ∝YZ

• X&Y sei die Verschmelzung.(merge) vonX undY

Beispiel: Skelette von Folgen

Y = (1, 4, 6, 9, 11, 12, 13, 16, 19, 20)

X = (5, 10, 12, 17)

Z = (2, 3, 7, 8, 10, 14, 15, 17, 18, 21)

k = 2: Zwischen je zwei Elementen vonX liegen−→ 2 ≤ 2k − 1 = 3 Elemente vonY−→ maximal 3 Elemente vonZ

k = 3: Zwischen je drei Elementen vonX liegen−→ 4 ≤ 2k − 1 = 5 Elemente vonY−→ maximal 5 Elemente vonZ

k = 4: Zwischen je zwei Elementen vonX liegen−→ 6 ≤ 2k − 1 = 7 Elemente vonY−→ maximal 6 Elemente vonZ

k = 5, 6 analogListen dürfen maximal 11 Elemente haben

=⇒ X ∝YZ

62


Haben zwei Folgen ein gemeinsames Skelett, so kann eine vereinfachte Mischung, das sog. Skelett-Merging,durchgeführt werden. Die beiden Folgen werden anhand des gemeinsamen Skelettes in Teilfolgen zerlegt,die in konstanter ZeitO(1) gemischt werden können.

Lemma 5.4:SeiX, Y, Z sortierte endliche Folgen mitX ∝YZ

SeiY (i) := (y ∈ Y : xi−1 < y ≤ xi)

Z(i) := (z ∈ Z : xi−1 < z ≤ xi)

für

1 ≤ i ≤ |x| + 1

x0 := −∞x|x|+1 := ∞

Dann gilt:Y &Z = Y (1)&Z (1) , Y (2) &Z (2) , . . . , Y (|X| + 1)&Z (|X| + 1)

Beispiel:

−∞Y (1) = 1, 4Z(1) = 2, 3

1, 2, 3, 4

5Y (2) = 6, 9Z(2) = 7, 8, 10

6, 7, 8, 9, 10

10Y (3) = 11, 12Z(3) =

11, 12

12Y (4) = 13, 16Z(4) = 14, 15, 17

13, 14, 15, 16, 17

17Y (5) = 19, 20Z(5) = 18, 21

18, 19, 20, 21

∞

X heißt Skelett vonY , in ZeichenX ∝ Y , falls für allek ≥ 2 gilt:Zwischen jek Elementen vonX liegen höchstens2k − 1 Elemente vonY .

Grundidee des Algorithmus von Cole

• Verschmelzung von Folgen mit gemeinsamen Skelett mit konstantem Aufwand.

• Zu sortierende Liste ist zu Beginn auf Blattknoten eines vollst. Binärbaums verteilt.

• die Verschmelzung von Teillisten erfolgt in mehreren Baumebenen fließbandartig gleichzeitig.

Bezeichnungen: Gegeben sei der vollständige Binärbaum mitn = 2k Blättern

63



T (v) sei der Unterbaum mit Wurzelv.

val(v) sei die momentane Folge des Knotensv.

list(v) sei die sortierte Folge, die aus den Werten der Blätter inT (v) entsteht.

Es gilt:val(v) ist stets geordnete Teilfolge vonlist(v).

Ein Knotenv heißt vollständig, fallsval(v) = list(v); sonst unvollständig(|val (v)| < |list (v)|).

Algorithmus von Cole:

Sei n = 2k die Anzahl der zu sortierenden Werte, die1 : 1 den Blättern des vollständigenBinärbaums zugeordnet werden.

Arbeitsweise eines beliebigen inneren Knotensv:Zu Beginn istval(v) leer. Der Knotenv wird aktiv, wenn vom linken Kind eine FolgeX1 derLänge1 und vom rechten Kind eine FolgeY1 der Länge1 erhält, die er zu einer Folgeval(v)der Länge2 verschmilzt. In jedem weiteren Schrittj erhält der Knoten von seinen beiden Kind-

knoten FolgenXj undYj , so dassXj−1 =Xj[1]

2 , Yj−1 =Yj[1]

2 , Xj undYj werden zuval(v)verschmolzen. In jedem Schritt wird die Länge vonval(v) verdoppelt, bislist(v) erreicht wird−→ Knotenv wird vollständig.

Ausgabevorschriften

1. Istv unvollständig undval(v) ≥ 4, so sendetv die Folgeval(v)[1]

4 = z an den Elternknoten.

2. Istv vollständig, so bleibtv noch zwei Schritte aktiv.

Im vorletzten Schritt sendetvlist(v)[1]

2 und im letzten Schrittlist(v).Danach wird der Knoten inaktiv.

Abbildung 5.2: Beispiel: 16 Zahlen

Zahlenfolge: 34, 81, 74, 92, 14, 31, 13, 97, 28, 36, 30, 80

34 81 74 92 14 31 13 97 28 36 30 80 45 25 1 71\ / \ / \ / \ / \ / \ / \ / \ /

34,81 74,92 14,31 13,97 28,36 30,80 25,45 1,71\ / \ / \ / \ /34,74 13,14 28,30 1,25

34,74,81,92 13,14,31,97 28,30,36,80 1,25,45,71\ / \ /13,34 1,28

13,31,34,81 1,28,36,4513,14,31,34,74,81,92,97 1,25,28,30,36,45,71,80

\ /1,13

1,13,36,741,13,28,31,36,71,74,92

/ \1, 13, 28, 31, 36, 71, 74, 92, 97

64


Betrachte nun einen typischen Knoten, d. h.v mit |list(v)| > 4.

Xi, Yi seien die Eingaben des Knotens imi-ten Schritt undZi sei die Ausgabe im(i + 1)-ten Schritt.

Schritt 1

X1 = (28) Y1 = (1)\ /

val1(v) = (1, 28)|∅

Schritt 2

X2 = (28, 36) Y2 = (1, 45)\ /

val2(v) = (1, 28, 36, 45)|

Z = (1)

Schritt 3

X3 = (28, 30, 36, 80) Y3 = (1, 25, 45, 71)\ /

val3(v) = (1, 25, 28, 30, 36, 45, 71, 80)|

Z2 = (1, 36)

Schritt 4vorletzter SchrittZ3 = (1, 28, 36, 71)

Schritt 5Z4 = (1, 25, 28, 30, 36, 45, 71, 80) y v wird inaktiv.

Invariante des Algorithmus von Cole

Satz 5.5.:Sei v ein Knoten mit|list(v)| ≥ 4. SeienXi+1, Yi+1 die Eingaben undZi die Ausgabefolge vonv inseinem(i + 1)-ten Schritt Dann gilt für allei ∈ N:

Xi+1 ∝ Xi+2 ∧ Yi+1 ∝ Yi+2 y Zi ∝ Zi+1

Lemma 5.6.:X ∝ X ′ ∧ Y ∝ Y ′y

X&Y4 ∝ X′&Y ′

4

Beweisgang.GelteX ∝ X ′, Y ∝ Y ′

Zeige

(a) X&Y ∝ X ′, X&Y ∝ Y ′

(b) Im allgemeinen gilt nicht:X&Y ∝ X ′&Y ′

Jedoch liegen zwischen jek aufeinander folgenden Elementen vonX&Y höchstens2k + 2Elementen. vonX ′&Y ′

Beweis von Satz 5.5.Sei|list(v)| = 2j−1 j = 3, 4, . . ., d. h. Knotenv ist nach seinem(j − 1)-ten Schritt vollständig.Mit der Ausgabevorschrift 1 erhält man mitLemma 5.6für alle i mit 1 ≤ i < j − 2:

Zi =val(v)[1]

4=

Xi+1&Yi+1

4∝

Xi+2&Yi+2

4= Zi+1

65



Sobaldv vollständig, tritt die Ausgabevorschrift (2) in Kraft und es gilt:

Zj−1 =list(v)

4∝

list(v)

2= Zj

Zj =list(v)

2∝ list(v) = Zj+1

Für die EingabefolgeXi+1 undYi+1 steht stets ein gemeinsames SkelettXi&Yi bereit.

zeitlicher Ablauf:

↓werden immer parallel geschicktXK

i+1

(Y K

i+1

)

ZKi

seien Eingabefolgen

sei Ausgabefolge

eines Knotens des LevelsK imBaum in seinem(i + 1)-ten aktivenSchritt

Abbildung 5.3: Zeitlicher Ablaufplan

Phase gesendete Folgen

1 ZBlatt1 → XA

1 /1——————————————————————————————————————–2 ZA

1 → XB1 /1

3 ZA2 → XB

2 /2——————————————————————————————————————–4 ZB

1 → XC1 /1

5 ZB2 → XC

2 /26 ZB

3 → XC3 /4 ZC

1 → XD1 /1

——————————————————————————————————————–7 ZC

2 → XD2 /2

8 ZC3 → XD

3 /4 ZD1 → XE

1 /1——————————————————————————————————————–9 ZC

4 → XD4 /8 ZD

2 → XE2 /2

Beobachtung:

• Wird Knotenv im Schritti inaktiv, so wird der Elternknoten im Schritti + 3 inaktiv y Laufzeit:

t(n) = 3 log n

= O(log n)

• Prozessoren:O(n)⇒ Kostenoptimalität:O(n log n)

66

KAPITEL 5. PARALLELE ALGORITHMEN5.4. GRAPHEN ALGORITHMEN

5.4 Graphen Algorithmen

Definition 5.7.: Ein endlicher GraphG = (V,E) besteht aus einer endlichen Menge von KnotenV (vertex) und einerendlichen Menge von KantenE (edges), E ⊆ V × V

Definition 5.8.: SeiG = (V,E) mit V = v0, . . . , vn−1. Die Einträgeaij , 0 ≤ i, j ≤ n−1 dern×n AdjazenzmatrixzuG sind definiert durch

aij =

1, falls (vi, vj) ∈ E0, sonst

Definition 5.9.:

a) Ein GraphG = (V,E) heißt ungerichtet, falls zu jedem(v, v′) ∈ E auch(v′, v) ∈ E, ansonsten gerichtet.

b) G heißt gewichtet, falls jeder Kante mittels einer Gewichtsfunktion w : E → R+ eine nicht negative

reelle Zahl zugeordnet ist.w kann zuw : V × V → R+0 ∪ ∞ ergänzt werden.

w(vi, vj) :=

w(vi, vj), falls (vi, vj) ∈ E∞, sonst

Definition 5.10.:

a) Eine Folge von Kanten(vi1 , vi2)(vi2 , vi3), . . . , (vik, vik+1

) heißt Pfad, falls alle Knotenvi1 , . . . , vik+1der

Folge voneinander verschieden sind.

b) Eine Kantenfolge(vi1 , vi2)(vi2 , vi3), . . . , (vik−1, vik

), (vik, vi1) heißt Zykel, falls alle Knotenvi1 , . . . , vik

paarweise verschieden sind.

c) Eine Kantenfolge(vi1 , vi2), . . . , (vik, vik+1

) heißt Weg, falls alle Kanten voneinander verschieden sind.Ein Graph ohne Zykel heißt azyklisch.

Definition 5.11.:Ein Graph(V ′, E′) heißt Subgraph vonG = (V,E), falls V ′ ⊆ V undE′ ⊆ E

Definition 5.12.:Ein ungerichteter Graph heißt zusammenhängend, falls zu jedem Paarvi undvj in G ein Pfad vonvi nachvj existiert.

5.4.1 Bestimmung der Zusammenhangskomponenten eines Grap hen

Zusammenhangskomponenten: minimale Menge von zusammenhängenden Subgraphen

Definition 5.13.:SeiG = (V,E) mit V = v0, . . . , vn−1 die n × n Zusammenhangsmatrix:C = (cij)0≤i,j≤n−1

wird definiert durch:

cij =

1 , falls vi undvj durcheinen Weg derLänge ≥ 0 verbunden sind

0 , sonst

67

5.4. GRAPHEN ALGORITHMEN


Abbildung 5.4: Beispiel – Zusammenhangskomponenten

0 1 2 3 4 5 6 7 8

0 1 0 0 0 0 0 0 1 11 0 1 1 0 1 1 1 0 02 0 1 1 0 1 1 1 0 03 0 0 0 1 0 0 0 0 04 0 1 1 0 1 1 1 0 05 0 1 1 0 1 1 1 0 06 0 1 1 0 1 1 1 0 07 1 0 0 0 0 0 0 1 18 1 0 0 0 0 0 0 1 1

C ergibt sich aus reflexivem, transitivem Abschluss der Adjazenzmatrix unter der boolschen Matrixmultiplikation, beider als Multiplikation „∧“ und als Addition „∨“ verwendet wird.

Stattdij =

n−1∑

k=0

aikbkj wird demnachdij =

n−1∨

k=0

(aik ∧ bkj) berechnet.

Anstelle der Adjazenzmatrix wird die auf der Diagonalen modifizierte MatrixB verwendet.

B = (bij)0≤i,j≤n−1

mit

bij =

aij , falls i 6= j1, falls i = j ←− reflexiver Abschluss

Für die Einträge vonBk gilt

bij =

1, falls es einen Weg vonvi nachvj derLänge ≤ k gibt

0, sonst

Satz 5.14.:Für die ZusammenhangsmatrixC gilt: C = Bn−1 wobein die Anzahl der Knoten bezeichnet.

68


Beweis Satz 5.14.:Falls zwei Knotenvi undvj überhaupt durch einen Weg verbunden sind, so existiert auchein Wegder Länge≤ n−1. Würde es nur Wege der Länge> n−1 geben, so würde mindestens 1 Knoten mehrfach vorkommenund der Weg enthielte einen Zyklus, der entfernt werden könnte.

Sei O.B.d.A(n − 1) Zweierpotenz

=⇒ log(n − 1) Boolsche Matrixmultiplikationen (sukzessives Quadrieren). Wird die Matrixmultiplikation auf einemHypercube mitn3 Prozessen durchgeführt, läge der Gesamtaufwand beiO(log n) parallelen Schritten.

5.4.1.1 Algorithmus von Hirschberg (1976)

Grundidee: Zusammenfassen von verbundenen Knoten zu Superknoten, bis jeder Superknoten einer Zusammen-hangskomponente entspricht.

Komplexität: O(log2 (n)

)mit O

(n2

)Prozessoren mitn = #Graphknoten

Eingabe: Adjazenzmatrix eines ungerichteten GraphenG = (V,E) mit V = 1, . . . , n

Ausgabe: VektorC der Längen, so dassC (i) = C (j) = k, falls i undj in der selben Zusammenhangskomponenteliegen undk der „kleinste“ Knoten in dieser Zusammenhangskomponente ist.

Abbildung 5.5: Beispiel

Ziel:i 1 2 3 4 5 6 7 8

C(i) 1 1 3 1 1 1 1 1

Berechnung:i 1 2 3 4 5 6 7 8

Initial C(i) 1 2 3 4 5 6 7 8T (i) 8 6 3 6 7 2 2 1

nach Phase 3:i 1 2 3 4 5 6 7 8

T (i) 1 2 3 2 2 2 2 1

Der Algorithmus arbeitet in 3 Phasen, die⌈log n⌉ mal iteriert werden.

1. Finde zu jedem Knoten den benachbarten Superknoten mit kleinstem Index.

2. Verbinde die Wurzel jedes Superknotens mit der Wurzel desbenachbarten Superknotens mit kleinstem Index.Die Wurzel eines Superknotens ist der Knoten mit der kleinsten Nummer.

3. Alle neu verbundenen Superknoten werden zu einem neuen Superknoten zusammengefasst.

Pseudocode: Initialisierung desC-Vektors:C(i) := i (1 ≤ i ≤ n) =⇒ Superknoten der Größe 1.

zu Phase 1:

69



1 for all vertices i in parallel do2 T(i):= minj C(j)|A(i,j)=1, C(j) 6=C(i)3 (falls diese Menge leer ist4 wird C(i) in T(i) gespeichert)

zu Phase 2:

1 for all vertices i in parallel do2 T(i):= minj T(j)|C(j)=i, T(j) 6=T(i)3 (wie oben)4 # "Finde aus allen benachbarten5 # Superknoten denjenigen mit6 # kleinstem Index"

Abbildung 5.6: T-Graph

zu Phase 3:

1 for all vertices i in parallel do2 B(i) ←T(i) (1 ≤ i ≤ n) # "Umspeichern in Hilfsvektor B"3 repeat log(n) times4 for all vertices i in parallel do5 T(i) ←T(T(i)) # "Setze T (i) ← T n(i)"6 for all vertices i in parallel do7 C(i) ←min(B(T(i)),T(i)

Bestimmung von Zusammenhangskomponenten

AdjazenzmatrixA Hirschberg−−−−−−−−→

VektorC mit C(i) = Index der Zusammenhangskomponenten miti V = 1, . . . , n

Index einer Zusammenhangskomponente = Nummer des „kleinsten“ enthaltenen Knotens

Algorithmus:⌈log n⌉ Iterationen der folgenden 3 Phasen

Phase 1:

1 for all vertices i in parallel do

2 T (i) :=

minjC(j)|A(i, j) = 1, C(j) 6= C(i) falls existent

C(i) sonst

Detaillierung: Sei∞ eine Zahl> n.

1 (a) for all i,j, 1 ≤ i, j ≤ n in parallel do2 if A(i, j) = 1 and C(i) 6= C(j)3 then Temp(i, j) :=C(j)4 else Temp(i, j) := ∞5 (b) for all i, 1 ≤ i ≤ n in parallel do6 Temp(i, 1) := minjTemp(i, j)7 (c) for all i, 1 ≤ i ≤ n in parallel do8 if Temp(i, j) 6= ∞9 then T (i) :=Temp(i,1)

10 else T (i) :=C(i)

70


Analyse:

(a) O(1) mitO(n2)Proz.(b) O(log n)mit O(n2)Proz.(c) O(1) mitO(n)Proz.

Phase 2:

1 for all vertices i in parallel do

2 T (i) :=

minjT (j)|C(j) = i, T (j) 6= i falls existent

C(i) sonst

„Verbinde Wurzel aller Superknoten mit Wurzel des Nachbar-Superknotens mit minimalem Index“

Detaillierung: analog zuPhase1=⇒ Aufwand wie in Phase1

Beispiel:

i 1 2 3 4 5 6 7 8

C(i) 1 2 3 4 5 6 7 8T(i) 8 6 3 6 7 2 2 1

nach Phasen 1 u. 2 der 1ten Iteration

Abbildung 5.7: T-Graph

Der T-Graph, der in Phase 2 gebildet wird, besitzt in jedem neu zu bildenden Superknoten genau eine Schleife aus 2Kanten, wobei der kleinste Knoten des neuen Superknotens einer der beiden Schleifenknoten ist. Da jeder Superknotenaus höchstensn Knoten besteht, kommt man beim Durchlaufen des T-Graphen nach n Schritten in die Schleife undist somit höchstens 1 Schritt vom Minimum entfernt.

Phase 3:

1 for all vertices i in parallel do2 B (i) := T (i)3 repeat log n times4 for all vertices i in parallel do5 T (i) := T (T (i))6 --setze T (i) := T n (i)7 for all vertices i in parallel do8 C (i) := min T (i) , B (T (i))

71



1 2 3 4 5 6 7 81 1 2 3 2 2 6 6 82 1 2 3 2 2 6 6 83 1 2 3 2 2 6 6 8

C(i) 1 2 3 2 2 2 2 1

Abbildung 5.8: C-Graph

Analyse der 3.Phase:

1. AnweisungO (1) mit O (n) Proz.2. AnweisungO (log n) mit O (n) Proz.3. AnweisungO (1) mit O (n) Proz.

y O (log n) mit O (n) Proz.

Aufwand pro Iteration (3 Phasen)O (log n)mit O(n2

)Proz.

⌈log n⌉-Iterationeny O(log2 n

)mit O

(n2

)Proz.

Mit Brents Theorem kann man zeigen, dass⌈

n2

log n

⌉

Proz. ausreichen, um mitO(log2 n

)- Schritten Zshgskomp zu

bestimmen. Es ist auch möglich mitO(

n2

log2 n

)

Prozessoren. [CHIN ET AL 81/82]

5.4.2 Kürzeste Wege

Zu G = (V,E) mit |V | = n sei die KostenmatrixW gegeben mit

wij := w (vi, vj) ∈ R+0 ∪ ∞

wii := 0

Gesucht ist die minimale KostenmatrixD, deren Einträgedij , 0 ≤ i, j ≤ n − 1 die minimalen Kosten (d. h. dieSumme der Gewichte) eines Weges vonvi zuvj sind.

Die Einträge der MatrixDk seien definiert durchdkij := minimale Kosten des Weges vonvi nachvj höchstens der

Längek

y D1 = W , Dn−1 = D Wege der Länge≥ n können nicht kürzeste Wege sein, da Kosten immer≥ 0.

O.B.d.A:n − 1 sei Zweierpotenz.

Es gilt fürk > 1

d2kij =

min

dkil + dk

lj

l

72


=⇒ modifizierte Matrix-Multiplikation

Multiplikation −→ Addition

Addition−→ Minimumbestimmung

=⇒ Dn−1 kann nachlog (n − 1) modifizierten Matrix-Multiplikation (sukzessive Quadrierung) bestimmt werden

Beispiel:aufn3 Proz.O(log2 n

)(HYPERCUBE-MATRIX -MULTIPLIKATION )

5.4.3 Minimal spannende Bäume

Definition 5.15.:Ein Baumist ein zusammenhängender, ungerichteter, azyklischer Graph.Ein spannender Baumeines GraphenG ist ein Subgraph, der alle Knoten vonG umfasst und ein Baum ist.In einem gewichteten Graphen ist einminimal spannender Baum(MST) ein spannender Baum mit der minimalenSumme von Kantengewichten.

Abbildung 5.9: minimal spannender Baum

Falls |v| = n, so hat ein MST nach Def.n − 1 Kanten. Da jede der potentiellenn(n−1)2 Kanten mindestens einmal

betrachtet werden muss, ist die untere Grenze der Laufzeit eines sequentiellen Algorithmus zur Bestimmung einesMST Ω

(n2

)

Tabelle 5.1: 3 Klassische sequentielle VerfahrenKruskal 1956 O

(n2

)

Prim-Dijkstra 1957/59 O(n2

)

Sollen 1977 O(n2 log n

)

5.4.3.1 Algorithmus von Prim

Invariante: Alle Knotenvi außerhalb des momentanen BaumesTi kennen den Knoten inTi mit minimalem Abstandzu ihnen.C (vi) :=„nächster Nachbar vonvi in Ti“

Bestimmung vonMSTs

Initialisierung: Ein Anfangsknotenv0 wird festgelegt.T0 besteht nur ausv0.

c (vi) := v0 für allevi 6= v0

for i := 1 to n − 1 do

73



(i) Suche unter den Knoten außerhalb vonTi einen Knotenv mit w (v, c (v)) minimal und fügev mit Kante(v, c (v)) zuTi hinzu.

(ii) Die Knotenvj , die außerhalb vonTi bleiben berechnec (vj) neu:

1 c (vj) := if w (vj , v) < w (vj , c (vj))2 then v else c(vj)

sequentielle Laufzeit:

T (n) = 1︸︷︷︸

v0 auswaehlen

+ O (n)︸︷︷︸

Initalisierung

+(n − 1) O (n)︸︷︷︸

Schleife

= O(n2

)

Implementierung des Verfahrens auf einer CREW-PRAM mitn Prozessoren mit 1-1-Zuordnung von Prozessoren zuGraphenknoten.

Initialisierungsaufwand:O (1)

Schleife:

Phase 1: (Minimumsbildung)O (log n)Phase 2: O (1)

y par. LaufzeitO (n log n) mit n Proz.y par. Kosten

(n2 log n

)

y nicht optimal.

Beobachtung: Prozessoren werden untätig, sobald ihre Knoten im MST sind.y Rescheduling zur Kostenoptimierung

Annahme: Es stehenN Prozessoren mit1 ≤ N ≤ n bereit. SeiN = n1−x mit 0 < x < 1.

Jeder Prozessor verwaltet jetztnN

= nx Knoten.

Laufzeitanalyse:

Initialisierungsaufwand: O (nx)

Schleife:

74


Phase 1: O (nx) für lokale Minimumbestimmung pro Prozessor+ O (log N) für globale Minimumbestimmung durch Reduktion+ O (1) für Baumerweiterung

Phase 2: O (nx) lokale Updates vonc (vj)

CREW-Aufwand:

O (nx) + O (n) (O (nx) + O (log N))= O (n) O (nx)= O

(nx+1

)auf nx−1 Prozessoren

=⇒ parallele Kosten O(n2

)

=⇒ kostenoptimal

5.4.3.2 Algorithmus von Sollin (1977)

Arbeitsweise ähnlich zu Hirschberg-Algorithmus (Bestimmung von Zusammenhangskomponenten)anstelle des Knotens mit minimalem Index innerhalb derSuperknotenwird jetzt die Kante mit minimalem Gewicht zuanderemSuperknotenbestimmt.

Initialisierung:

Wald vonn isolierten Knoten, die als Bäume betrachtet werden.

Iteration:

Für jeden Baum: bestimme die Kante mit dem kleinsten Gewicht, die diesen Baum mit einem anderenBaum verbindet. Alle diese minimalen Kanten werden hinzugefügt – dabei werden eventuell entstehendeZykel beliebig durchbrochen.

Die Anzahl der Bäume wird pro Iteration mindestens halbiert. y ⌈log (n)⌉ Iterationen genügen.

75



Abbildung 5.10: Beispiel

(a) 1.Iteration

(b) 2.Iteration

Pseudo-Code(sequentiell)

1 Parameter: n #Knoten2 Variablen: closest[ ] Abstand zu nächstem Baum3 edge[ ] Kante zu nächstem Baum4 T MST (als Kantenmenge)5 v,w Endpunkte der aktuellen Kante6 weight[ ] Kantengewichte7 Baum[ ] Wald als Knotenmenge8 begin9 for i:=1 to n do Baum[i]:= vi od

10 T := ∅11 while |T | < n − 1 do12 für jeden Baum i setze closest[i]:= ∞13 für jede Kante (v,w) tue14 if FIND(v) 6= FIND(w) then15 if weight(v,w) < closest[FIND(v)]16 then closest[FIND(v)]:= weight(v,w)17 edge [FIND(v)]:= (v,w)18 fi19 fi20 für jeden Baum i true21 (v,w):= edge[i]22 / if FIND(v) 6= FIND(w) then T:= T ∪ (v, w)23 ( * ) UNION(v,w)24 \ fi25 od26 end

FIND liefert zu einem Knoten, den Baum, in dem er enthalten ist.

76


UNION vereinigt die Bäume, in denen zwei Knotenv undw enthalten sind.

FIND und UNION effizient realisierbar.

Parallelisierung:

• Die äußerewhile -Schleife ist nicht parallelisierbar.

• 1te innere Schleife kann voll parallelisiert werden.

• 2te innere Schleife: Jeder Prozessor kann für Anteil von inneren Knoten jeweils die von diesemKnoten ausgehenden Kanten untersuchen.

• 3te innere Schleife: kritischer Bereich (*) erfordert Synchronisation.

77

6 Algorithmische Skelette

Beobachtung: Viele parallele Algorithmen arbeiten mit festenGrundmustern für parallele BerechnungundKommuni-kation. Durch algorithmische Skelette wird versucht, diese Grundmuster zu erfassen, effizient zu implementieren undzu analysieren.

Ein algorithmisches Skelett besteht aus:

1. einer funktionalen Spezifikation „abstrakte Funktionsbeschreibung“in fkt. Sprache: polymorphe Funktion höherer Ordnung (HOF)

2. parallele Implementierungen für verschiedene Zielarchitekturen

3. einem Kostenmodell zur Abschätzung der parallelen Ausführungszeit (für jede parallele Implementierung)

typische Skelette

• Divide & Conquer (Abb.6.1)

Listing 17 Divide & Conquer

dc :: (a −→Bool) −→(a −→b) −→(a −→[a]) −→([b] −→b) −→a−→bdc isAtom solve divide combine x

= if isAtom x then solve xelse combine(map dc’ (divide x))where dc’ = dc isAtom solve divide combine

Abbildung 6.1: Divide & Conquer

• Master-Worker-Schema (Abb.6.2)

78

KAPITEL 6. ALGORITHMISCHE SKELETTE

Abbildung 6.2: Master-Worker-Schema

• Pipeline (Abb.6.3)

Abbildung 6.3: Pipeline−→ ¤ −→ ¤ −→ . . . −→ ¤ −→ ¤

1. funktionale Spezifikation

pipe :: [[a] −→[a]] −→[a] −→[a]pipe [] xs = xspipe(f:fs) xs = pipe fs (f xs)

Beispiel: pipe (map map[ * 3,+5, * 2])(1:2:...)

2. parallele Implementierung...4 3 2 1−−−−−→[" * 3"] ...6 3−−→["+5"] ...11 8−−−→[" * 2"] ...22 16−−−−→3. Kostenmodell:

allgemein: Ausdruck mit Parametern, der parallele Ausführungszeit des Skelettes abschätzt.typische Parameter:

• architekturabhängig

– #Prozessoren– Kommunikationskosten

tsend „Zeit für das Senden einer Nachricht“δ „Übertragungsdauer einer Nachricht“treceive Empfangszeit

• Laufzeit systemabhängig

– Prozesserzeugungskosten– sequentielle Ausführungszeiten

• problemabhängig

– Problemgröße

Methode: Analyse eines kritischen Pfades (Abb.6.4)— kritischer Pfad: Folge notwendiger Aktionen, die aufeinander aufbauen und damit die Gesamtausführungs-zeit bestimmen.

Sehr oft: ’3’ Grundphasen

1. Hochfahren des Systems bis alle Prozessoren aktiv sind

79


Abbildung 6.4: kritischer Pfad

2. parallele Phase„längster“ Teil der Parallelausw.

3. Schlussarbeiten und Runterfahren des Systems

tpipe = tinit + tpar + tfinal

tinit = #Fct ∗ (tcreateProzess + tsend (size (Daten)) + δ)

tpar =#Fct

p∗ (tstartProcess + #Daten ∗

„

treceive (size (Daten)) +max

Fcttcomp + tsend (size (Daten))

«

tfinal = δ + treceive (size (Daten))

< < < Folien Skeletal Programming > > >

map f (xs + +ys) = (map f xs) + + (map f ys)

red ⊕ (xs + +ys) = (red ⊕ xs) ⊕ (map ⊕ ys)

falls ⊕ assoziativ

scan ⊕ (xs + +ys) = (scan ⊕ xs) + +map ((red ⊕ xs)⊕) (scan ⊕ ys)

= (scan ⊕ xs) op (scan ⊕ ys)

where

a op b = a + +map ((last a)⊕) b

scanred (⊗,⊕) (xs + +ys)

= red (⊕) scan (⊗) (xs + +ys)

= red (⊕) (scan ⊗ xs + +map ((red ⊗ xs)⊗) (scan ⊗ ys))

80


= (scanred (⊗,⊕) xs) ⊕ (red ⊕ (map ((red ⊗ xs)⊗) (scan ⊕ ys)))

scanred′ (⊗,⊕) (xs + +ys)

= ((scanred (⊗,⊕) xs) ⊕ (red ⊕ (map ((red ⊗ xs)⊗) (scan ⊕ ys))) , (red ⊗ xs) ⊗ (red ⊕ ys))

Distributivität:

a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)

map (a⊗) red⊕ = red ⊕ map (a⊗)

= ((scanred (⊗,⊕) xs) ⊕ (red ⊗ xs) ⊗ (scanred (⊗,⊕) ys) , (red ⊗ xs) ⊗ (red ⊕ ys))

= scanred′ (⊗,⊕) xs < ⊕,⊗ > scanred′ (⊗,⊕) ys

< < < Folien Alternative Concepts: Parallel Functional Programming > > >

81

Literaturverzeichnis

[1] A NDREWS, GREGORYR.: Foundations of Multithreaded, Parallel, and Distributed. Addison Wesley, 1999.

[2] FOSTER, IAN: Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering.Addison Wesley, 1995.

I

Abbildungsverzeichnis

2.1 Matrix-Multiplikation n=3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Hypercube. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Butterfly-Vernetzung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Hypercube der Dimension k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.1 Zusammenhängender Puffer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.1 Aufbau einer PRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2 Beispiel: 16 Zahlen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.3 Zeitlicher Ablaufplan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.4 Beispiel – Zusammenhangskomponenten. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.5 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.6 T-Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.7 T-Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.8 C-Graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.9 minimal spannender Baum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

5.10 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.1 Divide & Conquer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

6.2 Master-Worker-Schema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.3 Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.4 kritischer Pfad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

II

Documents

Parallele Programmierung - mathematik.uni-marburg.detseeger/Parallele_Programmierung/Blank... · 1 Einführung 1.1 Programmieren von parallelen Rechnern Problem ®¶ Paralleler Algorithmus