Date post: | 06-Apr-2015 |
Category: |
Documents |
Upload: | ilse-gerhardt |
View: | 111 times |
Download: | 2 times |
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Parallele Algorithmen IBasistechniken
Prof. Dr. Walter F. TichyDr. Victor PankratiusDavid MederAli Jannesari
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 2Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Parallel Random Access Machine (PRAM)
• Abstraktes Maschinenmodell, in dem sich parallele Algorithmen sehr gut spezifizieren lassen.
• Entspricht einer synchronen MIMD-Maschine mit gemeinsamem Adressraum.
• Speicherzugriffsvarianten• EREW: Exclusive Read, Exclusive Write• ERCW: Exclusive Read, Concurrent Write• CREW: Concurrent Read, Exclusive Write• CRCW: Concurrent Read, Concurrent Write
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 3Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Probleme des PRAM-Modells
• Es gibt keine echte, synchrone MIMD-Maschine mit gemeinsamem Adressraum.
• Alle Speicherzugriffsvarianten außer EREW sind unrealistisch.
• Die implizite Annahme, dass Kommunikations-operationen eine Zeiteinheit dauern, ist ebenfalls unrealistisch.
• ABER: Ist man sich der Unzulänglichkeiten bewusst, dann ist die PRAM ein sehr elegantes Modell zur Spezifikation paralleler Algorithmen.
• Diese können einfach für Cluster konvertiert werden.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 4Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
PRAM Sprachkonstrukte (1)
• Imperative Programmiersprache mit Erweiterungen, um Parallelität zu spezifizieren.
• Asynchrones FORALL:
FORALL i : P IN PARALLEL Anweisung1(i) … Anweisungn(i)END
• P ist eine Menge; für jedes Element in P wird ein Prozessor eingesetzt, wobei jeder Prozessor ein unterschiedliches Element i der Menge P bekommt.
• Jeder Prozessor führt die Anweisungsfolge 1 .. n asynchron aus.• Die FORALL-Anweisung endet, wenn jeder Prozessor die Anweisungs-
reihenfolge abgearbeitet hat. Zwischendurch erfolgt keine Synchronisation.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 5Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
PRAM Sprachkonstrukte (2)
• synchrone Form des FORALL:
FORALL i : P IN SYNC Anweisung1(i) … Anweisungn(i)END
• Wie vorher, nur dass jetzt alle Prozessoren die Anweisungsfolge synchron („im Gleichschritt“) ausführen.
• Die synchrone Ausführung gleicher Anweisungen vermeidet viele Laufzeitprobleme, da unterschiedliche Ausführungs-geschwindigkeiten der Prozessoren nicht beachtet werden müssen.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 6Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Synchrone Zuweisung
Synchrone Abarbeitung der Zuweisung: L := R
1) Alle n Prozessoren werten L synchron aus und erhalten eine Adresse.
2) Alle n Prozessoren werten R synchron aus und erhalten einen Wert.
3) Alle n Prozessoren speichern ihren Wert an ihrer Adresse (EW oder CW).
4) (1) & (2) können im Prinzip auch gleichzeitig ausgeführt werden. Seiteneffekte sind möglich, aber die Reihenfolge der Auswertungen ist undefiniert.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 7Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Synchrones IF-THEN-ELSE (1)
Synchrone Abarbeitung der bedingten Anweisung:IF B THEN S1 ELSE S2
1) Alle n Prozessoren werten B synchron aus.
2) Die Menge der Prozessoren partitioniert sich in die Mengen MT
(für B=T) und MF (für B=F) in Abhängigkeit des Ergebnisses
von B.
3) Die Menge MT führt S1 synchron aus.
4) Die Menge MF führt S2 synchron aus.
5) Die Untermengen MT und M
F können (müssen aber nicht)
parallel abgearbeitet werden. Keine Aussage über die „relativen Geschwindigkeiten“ zueinander.
6) Ausführung endet, wenn die Mengen MT und M
F beide fertig
sind.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Synchrones IF-THEN-ELSE (2)
8Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
IF (Answer == 42)
THEN print(„Woohoo!“);
ELSE print(„Doh!“);
ENDIF
Prozessoren MT mit Answer == 42
Alle Prozessoren
Prozessoren MF mit Answer != 42
Answer = 21 * (processorId % 3);
Alle Prozessoren
Answer = 21 * (processorId % 3);IF (Answer == 42)THEN print(„Woohoo!“);ELSE print(„Doh!“);ENDIF
Alle Prozessoren werten die Bedingung synchron aus.
Ende, sobald beide Prozessorgruppen MT und MF fertig sind.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Synchrones IF-THEN-ELSE (3)
9Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
IF (Answer == 42)
THEN print(„Woohoo!“);
ELSE print(„Doh!“);
ENDIF
Prozessoren MT mit Answer == 42
Alle Prozessoren
Prozessoren MF mit Answer != 42
Answer = 21 * (processorId % 3);
Alle Prozessoren
Answer = 21 * (processorId % 3);IF (Answer == 42)THEN print(„Woohoo!“);ELSE print(„Doh!“);ENDIF
Alle Prozessoren werten die Bedingung synchron aus.
Ende, sobald beide Prozessorgruppen MT und MF fertig sind.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 10Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
• Addition eines n-elementigen Vektors
FORALL i : [0 .. n-1] IN SYNC C[i] := A[i] + B[i];END
• Bsp.: für n = 8
FORALL i : [0 .. n-1] IN PARALLELwäre ebenfalls möglich, da die Anweisungen voneinander unabhängig sind.
FORALL (1)
00 11 22 33 44 55 66 77
00 11 22 33 44 55 66 77
00 22 44 66 88 1010 1212 1414
A
B
C
+
=
0 1 2 3 4 5 6 7Prozessor
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
1) Alle n Prozessoren Werten C[i] synchron aus und erhalten eine Adresse.
2) Alle n Prozessoren Werten A[i] + B[i] synchron aus und erhalten einen Wert.
3) Alle n Prozessoren speichern ihren Wert an der in (1) ermittelten Adresse.
4) Haben alle n Prozessoren die FORALL-Schleife abgearbeitet, wird gemeinsam mit der Bearbeitung der danach folgenden Codezeilen fortgefahren.
FORALL (2)
11Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
FORALL i : [0 .. n-1] IN SYNC ;ENDC[i] := A[i] + B[i]
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 12Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
FORALL (3)
• Rotieren eines n-elementigen Vektors
FORALL i : [0 .. n-1] IN SYNC A[i] := A[(i+1)mod n];END
• Bsp.: für n = 8
FORALL i : [0 .. n-1] IN PARALLELwäre nicht möglich, da dann unter Umständen falsche Werte weitergegeben werden.
00 11 22 33 44 55 66 77
11 22 33 44 55 66 77 00
A
0 1 2 3 4 5 6 7Prozessor
A
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
FORALL (4)
• Beispiel für fehlerhafte Ausführung mit IN PARALLEL
13Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
00 11 22 33 44A
0 1 2 3 4 5 6 7Prozessor
A
55 66 77
1) Prozessoren 0 bis 3, sowie 5 bis 7 führen Anweisung gleichzeitig aus.
2) Prozessor 4 liest Wert aus A[5] erst, nachdem dieser von Prozessor 5 geschrieben wurde ( asynchrone Ausführung!).
11 22 33 44 66 66 77 00
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 14Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Reduktion (1)
• Eine Reduktion, d.h. das Zusammenfassen mehrerer Datenelemente zu einem Ergebnis, gehört zu den Basistechniken der parallelen Algorithmen. (MPI_Reduce, MPI_Allreduce)
• Bsp: Die parallele Summenbildung
• Summenberechnung sequentiell: O(N)• Frage: Wie geht's parallel schneller?
00 11 22 33 44 55 66 77A
0 1 2 3 4 5 6 7Prozessor
Sum 2828
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 15Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Reduktion (2)
• Baumartiges Reduktionsverfahren:Fasse jeweils zwei (im Abstand 2k, 0 ≤ k < log
2(N)) benachbarte
Elemente zusammen:
Sum(0,7)Sum(0,7)
Sum(0,3)Sum(0,3)
Sum(0,1)Sum(0,1) Sum(2,3)Sum(2,3) Sum(4,5)Sum(4,5) Sum(6,7)Sum(6,7)
Sum(4,7)Sum(4,7)
0 3 42 5 6 71
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 16Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Reduktion (3)
PRAM Programm einer parallelen SummeCONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGER
Spanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
CONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGER
Spanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
parallele Laufzeit: O(log2(N)), Modell: CREW
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Reduktion (4)
N = 4
Schritt 1
Spanne = 1 < 4, 2 * Spanne = 2
17Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
0 1 2 3Valt
i mod 2
Spanne + i
0 1 0 1
1 2 3 4
Vneu
N = 4
Schritt 2
Spanne = 2 < 4, 2 * Spanne = 4
0 1 2 3Valt
i mod 4
Spanne + i
0 1 2 1
2 3 4 5
Vneu
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Reduktion (5)
18Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
• Frage: Funktioniert das Verfahren auch, wenn N keine Potenz von 2 ist?
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Reduktion (6)
N = 6
Schritt 1
Spanne = 1 < 6, 2 * Spanne = 2
19Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
0 1 2 3Valt
i mod 2
Spanne + i
Vneu
4 5
0 1 0 1 0 1
1 2 3 4 5 6
N = 6
Schritt 2
Spanne = 2 < 6, 2 * Spanne = 4
0 1 2 3Valt
i mod 4
Spanne + i
Vneu
4 5
0 1 2 3 0 1
2 3 4 5 6 7
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Reduktion (7)
N = 6
Schritt 3
Spanne = 4 < 6, 2 * Spanne = 8
20Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
CONST N = 4V : ARRAY [0 .. N-1] OF INTEGERSpanne : INTEGERSpanne := 1;WHILE (Spanne < N) DO FORALL i : [0 .. N-1] IN SYNC IF (i MOD (2*Spanne)) = 0 AND Spanne+i < N V[i] := V[i] + V[i + Spanne]; END END Spanne := Spanne * 2;END
0 1 2 3Valt
i mod 8
Spanne + i
Vneu
4 5
0 1 2 3 4 5
4 5 6 7 8 9
• Funktioniert auch, wenn N keine Potenz von 2 ist.
• Übriges Element (im Beispiel Element 4) wird dann in einem separaten Schritt verrechnet.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 21Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Präfix & Postfix (1)
Berechnung aller Partialsummen (MPI_Scan):
Sum(0,1)Sum(0,1)
Sum(0,3)Sum(0,3)
Sum(1,2)Sum(1,2) Sum(2,3)Sum(2,3) Sum(3,4)Sum(3,4) Sum(4,5)Sum(4,5) Sum(5,6)Sum(5,6) Sum(6,7)Sum(6,7) Sum(7,7)Sum(7,7)
Sum(1,4)Sum(1,4) Sum(2,5)Sum(2,5) Sum(3,6)Sum(3,6) Sum(4,7)Sum(4,7) Sum(5,7)Sum(5,7)
Sum(1,7)Sum(1,7) Sum(2,7)Sum(2,7) Sum(3,7)Sum(3,7)Sum(0,7)Sum(0,7)
0 3 42 5 6 71
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 22Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Präfix & Postfix (2)
• Präfixoperation(j) berücksichtigt alle Elemente i mit 0 ≤ i ≤ j.
• Postfixoperation(j) berücksichtigt alle Elemente i mit N-1 ≥ i ≥ j.
• Beispiel: Prä- und Postfixsummen.
11A 11 11 11 11 11 11 11
11 22 33 44 55 66 77Präfix 88
88Postfix 77 66 55 44 33 22 11
0 1 2 3 4 5 6 7Prozessor
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Präfix & Postfix (3)
• Berechnung der Präfixsumme:
23Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
1 2 4 8 16 32 48 96
1 2 4 8 16 32 48 96
1 3 6 12 24 48 80 144
1 3 7 15 30 60 104 192
1 3 7 15 31 63 111 207
A
B+B[i-1]
+B[i-2]
+B[i-4]
log2(8) = 3 Schritte zur Berechnung der Präfixsummen.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 24Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Broadcast (1)
Verteilen von Elementen (nützlich z.B. für MPI_Bcast):
aa ??
0 1 2 3 4 5 6 7Prozessor
?? ?? ?? ?? ?? ??
aaaa aaaa aaaa aaaa
?
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 25Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Broadcast (2)
Verteilen von Elementen (nützlich z.B. für MPI_Bcast):
• Sei Verknüpfungsoperator mit Eigenschaft a x = a
• Speichere a in T[0]
• Wende dann Präfixoperation an
aa
?? ??
?? ?? ?? ??
??
0 1 2 3 4 5 6 7Prozessor
?? ?? ?? ?? ?? ??
aaaa aaaa
aaaa ?? ?? ?? ??
aaaa aaaa
aaaa aaaa
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 26Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Broadcast (3)
PRAM Programm zur DatenverteilungCONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : ARRAY [0 .. N-1] INTEGER
V[0] := a;FORALL i : [0 .. N-1] IN SYNC Spanne[i] := 1; WHILE (Spanne[i] < N) DO IF i >= Spanne[i] V[i] := V[i - Spanne[i]]; END Spanne[i] := Spanne[i] * 2; ENDEND
CONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : ARRAY [0 .. N-1] INTEGER
V[0] := a;FORALL i : [0 .. N-1] IN SYNC Spanne[i] := 1; WHILE (Spanne[i] < N) DO IF i >= Spanne[i] V[i] := V[i - Spanne[i]]; END Spanne[i] := Spanne[i] * 2; ENDEND
parallele Laufzeit: O(log2(N)), Modell: EREW.
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Broadcast (4)
N = 4
Schritt 1
27Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
a0 1 2 3
Valt
Spanne[i] 1 1 1 1
a aVneu
CONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : ARRAY [0 .. N-1] INTEGER
V[0] := a;FORALL i : [0 .. N-1] IN SYNC Spanne[i] := 1; WHILE (Spanne[i] < N) DO IF i >= Spanne[i] V[i] := V[i - Spanne[i]]; END Spanne[i] := Spanne[i] * 2; ENDEND
CONST N = ...V : ARRAY [0 .. N-1] OF INTEGERSpanne : ARRAY [0 .. N-1] INTEGER
V[0] := a;FORALL i : [0 .. N-1] IN SYNC Spanne[i] := 1; WHILE (Spanne[i] < N) DO IF i >= Spanne[i] V[i] := V[i - Spanne[i]]; END Spanne[i] := Spanne[i] * 2; ENDEND
i>=Spanne[i] 1 1 1
Spanne[i]neu 2 2 2 2
a a0 1 2 3
Valt
Spanne[i] 2 2 2 2
a a a aVneu
i>=Spanne[i] 1 1
Spanne[i]neu 4 4 4 4
N = 4
Schritt 2
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 28Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Anwendungen (1)
FORALL i:[0 .. N-1] IN PARALLEL T[i] := test_condition(i);END
Präfix(T,+);
• Ergebnis in T
Präfix
T 00 11 11 00 11 00 11 11
0 1 2 3 4 5 6 7Prozessor
0 1 2 3 4 5 6 7
T 00 11 22 22 33 33 44 55
• Abzählen von Elementen mit einer bestimmten Eigenschaft:
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 29Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Anwendungen (2)
• Kompaktifizierung einer Liste
• Laufzeit:O(log(N))
aa bb cc dd
aa bb cc dd
aa bb cc
aa bb cc dd
11 11 22 33
ddL
if isChar(L[i]) then T[i] := 1; else T[i] := 0;
T: 11 00 11 11
Präfix(T,+)
if (T[i] == 1) then L'[T' [i]-1] := L[i]
L'
00 00 00 11
33 33 33 44T‘:
0 1 2 3 4 5 6 7
Lehrstuhl für Programmiersysteme
Fakultät für Informatik
Anwendungen (3)Rekurrenzen – Zur Erinnerung
• Zur Erinnerung• Beispiel: Finde
geschlossene Form fürlineare Rekurrenz
• g(n) = g(n-1) + 2n -1 • g(0) = 0
• Lösung: f(n)=n²• Möglicher Lösungsansatz:
„Ausrollen“
g(n) = g(n-1) + 2n - 1 = [g(n-2) + 2(n-1) - 1] + 2n - 1 weil g(n-1) = g(n-2) + 2(n-1) -1 = g(n-2) + 2(n-1) + 2n - 2 = [g(n-3) + 2(n-2) -1] + 2(n-1) + 2n - 2 weil g(n-2) = g(n-3) + 2(n-2) -1 = g(n-3) + 2(n-2) + 2(n-1) + 2n - 3 ... = g(n-i) + 2(n-i+1) +...+ 2n - i ... = g(n-n) + 2(n-n+1) +...+ 2n - n = 0 + 2 + 4 +...+ 2n – n weil g(0) = 0 = 2 + 4 +...+ 2n - n = 2*n*(n+1)/2 - n weil 1+...+n = n(n+1)/2 = n^2
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 31Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Anwendungen (3)Rekurrenzen
• Lösen von Rekurrenzen (1. Ordnung):
Xi = X
i-1 ○ a
i, mit ○ binärer Operator.
Beispiel: Präfixsumme als Rekurrenz:
Sumi = Sum
i-1 + a
i mit
Sum
0 = a
0
• Lösen von Rekurrenzen höherer Ordnung auch möglich:
• Xi = ai-1 ○ Xi-1 ○ … ○ ai-m ○ Xi-m ○ bi
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 32Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
• Parallele Polynomauswertung:f(x) = a
0 + a
1x + a
2x2+ a
3x3+ a
4x4+ a
5x5+ a
6x6+ a
7x7
• Laufzeit:O(3*log(N))= O(log(N))
Anwendungen (4)
X
11
0 1 2 3 4 5 6 7Prozessor
xx xx xx xx xx xx xx
xx
Broadcast X
Präfix(X,*) 11 xx x2x2 x3x3 x4x4 x5x5 x6x6 x7x7
A
T = A * X
L_Reduce(T,+) f(x)f(x)
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 33Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Aufgabe (1)
• Gegeben sei ein N-elementiger Zahlenvektor v[0…n-1].
• Schreiben Sie ein paralleles Programm, welches D = max{ v[i] − v[j] }, 0 ≤ i , j < n berechnet.
• Was ist die asymptotische Laufzeit?
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 34Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Aufgabe (2)
• Schreiben Sie ein paralleles Programm, welches zwei Zeichenreihen der Länge N lexikographisch vergleicht.
• Was ist die asymptotische Laufzeit?
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 35Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Aufgabe (3)
• Gegeben sei ein N-elementiger Zahlenvektor v[0… n-1].
• Schreiben Sie ein paralleles Programm, welches den Wert des maximalen Untervektors bestimmt:
U=max{ ∑ v[i] ; 0 ≤ p < q < n}
• Was ist die asymptotische Laufzeit?
i=p
q
Lehrstuhl für Programmiersysteme
Fakultät für Informatik 36Prof. W. F. Tichy, Dr. V. Pankratius, D. Meder, A. Jannesari
Aufgabe (4)
• Schreiben Sie ein paralleles Programm, welches die ersten N Fibonacci-Zahlen berechnet.
• fi = f
i-1 + f
i-2, f
0 = f
1 = 1