Grundlagen der Programmierung 2
Parallele Verarbeitung
Prof. Dr. Manfred Schmidt-Schauÿ
Künstliche Intelligenz und Softwaretechnologie
31. Mai 2006
Teile und Herrsche (Divide and Conquer)
Grundlagen der Programmierung 2 - 1 -
Entwurfsmethode fur Algorithmen
1. Teile das Problem in kleinere Unterprobleme (Divide)2. Lose rekursiv die entstehenden Unterprobleme (Conquer)3. Setze die Losungen zusammen.
Instanzen :
• Mergesort• Quicksort• Intervallhalbierung (kein Zusammensetzen)• schnelle Berechnung ganzzahliger Potenzen
Divide-and-Conquer: Laufzeiten
Grundlagen der Programmierung 2 - 2 -
Bei sequentiellen Programmen kann man oft erreichen, dass
ein O(n) Laufzeitanteil verbesserbar ist zu O(log(n))
Notwendig dazu:
Summe der Großen der Teilprobleme ≤ Große des Problems
Beispiel: Turme von Hanoi
Grundlagen der Programmierung 2 - 3 -
Gegeben Stapel von verschieden großen Scheibenvon oben nach unten großer werdend
Aufgabe: Umstapeln auf einen anderen Stapel.Erlaubt ist ein weiterer HilfsstapelBedingung: Es darf niemals eine Scheibe auf einer kleineren
liegen
Losung: mittels Teile-und-Herrsche:
Beispiel: Turme von Hanoi (2)
Grundlagen der Programmierung 2 - 5 -
Notwendige Bewegungen fur n:
1. n− 1 Scheiben von 1 nach 3 mit 2 als Hilfsstapel
2. Scheibe n von 1 nach 2
3. n− 1 Scheiben von 3 nach 2 mit 1 als Hilfsstapel
Beispiel: Turme von Hanoi (2)
Grundlagen der Programmierung 2 - 6 -
Haskell-Algorithmus zum Ermitteln der Bewegungen.
Die Nr. der Stapel wird als Argument mitubergeben.
-- hanoi: Stapel, Stapelnr, Zielstapelnr Hilfstapelnr:
hanoi xs a b c = hanoiw (reverse xs) a b c
hanoiw [] _ _ _ = []
hanoiw xa a b c =
(hanoiw (tail xa) a c b)
++
((head xa ,(a,b))
:
(hanoiw (tail xa) c b a))
Parallele Algorithmen und deren Ressourcenbe-darf
Grundlagen der Programmierung 2 - 7 -
Themen: Nebenlaufigkeit,Parallelitat,RessourcenverbrauchParallelisierung von AlgorithmenAmdahl-GesetzGustafson-Barsis GesetzBeispielalgorithmen in Haskell
Nebenlaufigkeit und Parallelitat
Grundlagen der Programmierung 2 - 8 -
Prozesse und Kommunikation
Prozess: eigenstandig ablaufende Rechnung mit eigenem Speicher
wie Rechner; kann interne Berechnungenund Ein-Ausgabe durchfuhren
P,Q nebenlaufig
(concurrent)
wenn diese unabhangig voneinander ausgefuhrt
werden konnen.
P,Q parallel, wenn sie nebenlaufig sind und gleichzeitig ablaufen.
Klassifikation der parallelen Rechnerarchitektu-ren nach Flynn
Grundlagen der Programmierung 2 - 9 -
Bezuglich paralleler Instruktionssequenzen und Parallelitat der Verar-
beitung von Daten:
• SISD: Single instruction, single data stream (SISD): Sequentieller
Rechner ohne Parallelitat.• MISD:Multiple instruction, single data stream: kommt so gut wie
nicht vor: Man konnte redundante (Doppel-) Verarbeitung hier
einordnen.• SIMD: Single instruction, multiple data streams: Gleiche Verar-
beitung. viele gleichartige Daten: z.B. Vektorprozessor.• MIMD:Multiple instruction, multiple data streams: Mehrere Pro-
zessoren lassen verschiedene Programme auf verschiedenen Da-
ten ablaufen: Verteilte Systeme.
Parallele und verteilte Berechnungen
Grundlagen der Programmierung 2 - 10 -
• PRAM: parallel random access machine
• Verteilte Berechnung, lose Kopplung
• massiv parallel, enge Kopplung
• Grid-Computing
• Vektorrechner, Feldrechner
• Pipelining
PRAM: parallel random access machine
Grundlagen der Programmierung 2 - 11 -
• Mehrere Prozesse (Prozessoren),gemeinsamer Hauptspeicher,
• unabhangiges Lesen und Schreiben
• Unterscheidung verschiedener Modelle:Lesen- und/oder Schreiben; exklusiv oder konkurrierend(EREW, CRCW, CREW).
Verteilte Berechnungen, lose Kopplung
Grundlagen der Programmierung 2 - 12 -
• Mehrere unabhangige Rechner kommunizieren uber ein Netzwerk• arbeiten gemeinsam an einer Berechnung• Programme / Programmteile konnen vollig verschieden sein.• Weitere Unterscheidung:
Gleichberechtigte Rechner; oderhierarchisch (Master/ Slave) bzw. (Client / Server).
• Z.B. PVM: Parallel Virtual Machine
massiv parallel, enge Kopplung
Grundlagen der Programmierung 2 - 13 -
• Viele unabhangige, gleiche Prozessoren• Kopplung uber ein schnelles Netzwerk• arbeiten gemeinsam an einer Berechnung.• I.a: Gleiches Programm, verschiedene Daten.• Oft feste Topologie:
Hyperwurfel, ahnliche Netzwerke,Z.B. Hardware fur kunstliche neuronale Netze.
Grid-Computing
Grundlagen der Programmierung 2 - 14 -
• Viele Workstations/ PCs rechnen gemeinsam an einer Aufgabe
• verschiedene Hardware / Betriebssystem ist moglich
• I.a. : Rechner haben das gleiche Programm, aber verschiedene Daten
Vektorrechner
Grundlagen der Programmierung 2 - 15 -
• Ein Programm steuert parallele Berechnungen auf HW-Arrays:
• Gleiche Prozedur, verschiedene Datenelemente
• Sinnvoller Einsatz: Wettersimulationen, numerische Berechnungen
• SIMD (single instruction, multiple data)
Pipelining
Grundlagen der Programmierung 2 - 16 -
• I.a. parallele Ausfuhrung von Maschinenkodeauf der Hardware eines Prozessor
• Befehlsbearbeitung wird in kleinere Einheiten zerlegt,• die dann nacheinander, versetzt abgearbeitet werden.• Weitere Beschleunigung durch
Mehrfachauslegung von internen Einheiten
Maße fur den parallelen Ressourcenverbrauch
Grundlagen der Programmierung 2 - 17 -
Modell auf der Programmiersprachenebene:
Auswertung durch einzelne Reduktionsschritte (z.B. Haskell)
• sequentieller Einzelschritt
• paralleler Einzelschritt = mehrere unabhangige, gleichzeitigeEinzelschritte
Maße fur den parallelen Ressourcenverbrauch
Grundlagen der Programmierung 2 - 18 -
Basis ist das PRAM-Modell:• mehrere, nicht unterscheidbare Prozessoren• gemeinsamer Hauptspeicher• Befehlsabarbeitung ist synchron getaktet.• pro Einzelschritt einer parallelen Auswertung• ist ein Prozessor notwendig
#parallele Reduktionsschritte = #paralleler Schritte bis zum Ergebnis
#notwendige Prozessoren = maximale Anzahl gleichzeitigersequentieller Einzelschrittein einem parallelen Schritt
Beispiel: Parallele Auswertung
Grundlagen der Programmierung 2 - 19 -
Skalarproduktberechnung:
(a1, . . . , an) ∗ (b1, . . . , bn) = a1 ∗ b1 + . . . + an ∗ bn
1. Schritt: Werte die Produkte parallel aus2. Schritt: Addiere die Ergebnisse
Parallele Reduktion; konservativ / spekulativ
Grundlagen der Programmierung 2 - 20 -
• Die Parallelisierung ist konservativ, wenn nur Auswertungen durch-
gefuhrt werden, die fur das Erreichen des Resultats notwendig sind.
• Die Parallelisierung ist spekulativ, wenn auch Reduktionen durch-
gefuhrt werden konnen, von denen zum Zeitpunkt der Ausfuhrung
nicht bekannt ist, ob diese fur das Berechnen des Resultats not-
wendig sind.
Parallele Reduktion: Beispiel
Grundlagen der Programmierung 2 - 21 -
spekulativ:
Die parallele Reduktion von s und t in
if cond then s else t
konservativ:
Die parallele Reduktion von s und t in
s * t
Parallele Reduktion: Maßzahlen
Grundlagen der Programmierung 2 - 22 -
Algorithmus sei gegeben, sei E die Eingabe, und p die Anzahl der
erlaubten Prozessoren.
τ(E, p) minimale Anzahl der parallelen Reduktionsschritte bis
zum Ergebnis, wenn man p unabhangige Reduktions-
schritte gleichzeitig pro Schritt machen darfτ(E,1) ist die Anzahl der Einzel-Reduktionsschritte bei sequen-
tieller Auswertung.τ(E,∞) entspricht dann der Anzahl der parallelen Reduktions-
schritte bis zum Ergebnis, wenn es keine obere Schranke
fur die Anzahl gleichzeitiger Reduktionen
(#Prozessoren) gibt.
Optimistische Erwartung: τ(E, p) ≈τ(E,1)
p.
Parallele Reduktion: Beschleunigung
Grundlagen der Programmierung 2 - 23 -
Vereinfachende Annahme im folgenden:
die Kennzahlen hangen nur vom Algorithmus ab;
proportional zur Eingabegroße E;
D.h., fur alle p: τ(E, p) = |E| ∗ τ(p);
meist kann |E| gekurzt werden.
(relative) parallele Beschleunigung :=τ(1)
τ(p)
Die parallele Beschleunigung ist eine Zahl zwischen 1 und p
≥ 1, da man sequentiell reduzieren kann,≤ p, da maximal p Prozessoren und man eine parallele
Reduktion zu einem Ergebnis sequentiell nachvollziehen kann.
Parallele Reduktion: Beschleunigung
Grundlagen der Programmierung 2 - 24 -
maximale parallele Beschleunigung
q :=τ(1)
τ(∞)= lim
p→∞τ(1)
τ(p).
parallele Beschleunigung bei unbeschrankter Anzahl von Prozessoren.
sequentieller Zeit-Anteil des Algorithmus := 1/q.
Parallele Reduktion: Effizienz
Grundlagen der Programmierung 2 - 25 -
parallele Effizienz :=τ(1)
p ∗ τ(p)
= Anteil der fur den Algorithmus nutzbaren gesamten Leistungaller Prozessoren
Beispielhafte Zahlen:
τ(1) τ(3) τ(4)Zeit 1000 500 400Beschleunigung 1 2 2,5Effizienz 1 66,6% 62,5%
Parallele Effizienz
Grundlagen der Programmierung 2 - 26 -
τ(1)
p ∗ τ(p)ist eine Zahl zwischen 1 und 1/p.
1 optimal: alle Prozessoren tragen zur zur Berechnung bei
1/p schlecht: Berechnung ist im wesentlichen sequentiell
Weitere Maßzahlen
Grundlagen der Programmierung 2 - 27 -
w(p) die verrichtete ArbeitGesamt-Anzahl von Einzelschritten
Es gilt stets: w(p) ≥ τ(1)
w(p)
τ(p)mittlere Anzahl beschaftigter Prozessoren
w(p)
p ∗ τ(p)mittlere Auslastung
Amdahls Gesetz
Grundlagen der Programmierung 2 - 28 -
Begrenzung der parallelen Beschleunigung
Amdahl-Annahmen zur Problemstruktur (≈ fur alle Eingaben)
T = Tpar + Tseq
Gesamtzeit T hat parallelen und sequentiellen Anteil
VerhaltnisTpar
Tseqist konstant.
Beispiel
map f xs
Sequentieller Anteil: mindestens ein Listendurchlauf
Amdahls Gesetz (2)
Grundlagen der Programmierung 2 - 29 -
Beschleunigung durch p Prozessoren:
Tpar + Tseq
(1/p) ∗ Tpar + Tseq
Bei unendlich vielen Prozessoren:
Beschleunigung ≤Tpar + Tseq
Tseq
Beispiel
Wenn sequentieller Anteil = 5%,
dann ist Beschleunigung maximal 20
Gustafson-Barsis Gesetz
Grundlagen der Programmierung 2 - 30 -
Gustafson-Barsis-Annahme: T = Tseq + p ∗ Tp
T Zeit fur einen ProzessorTseq fester sequentiellen Anteil, z.B. Initialisierungp ∗ Tp auf p Prozessoren verteilbare Berechnungszeit
Mit α =Tseq
Tpergibt sich:
Beschleunigung =Tseq + p ∗ Tp
Tseq + Tp=
α + p
α + 1
Gustafson-Barsis Gesetz: Beispiel
Grundlagen der Programmierung 2 - 31 -
Anwendung von f auf alle Elemente eines Arrays der Lange n
a[1], . . . , a[n] → f a[1], . . . , f a[n]
Tseq InitialisierungszeitTp Zeit zum Berechnen von f x.
Wenn Tseq = Tp,
dann Beschleunigung mit n Prozessoren =1 + n
2
Beispiele: Algorithmen und Parallelisierung inHaskell
Grundlagen der Programmierung 2 - 32 -
vereinfachtes Modell in Haskell:
unabhangige Transformationen konnen parallel durchgefuhrt werden.
Annahme: beliebig viele Prozessoren
verzogerte Reduktion und gerichteter Graph bzw. let-Darstellung.
Jede Transformation benotigt eine Zeiteinheit.
#parallel mogliche Transformationen = #Prozessoren
Beispiele
Grundlagen der Programmierung 2 - 33 -
quadratsumme 3 4 −→ (3*3)+(4*4) −→ 9+16 −→ 25.
2 Prozessoren; 3 Zeiteinheiten werden benotigt
Beispiel: Fakultat
Grundlagen der Programmierung 2 - 34 -
fakt 3
−→ if 3 == 1 then 1 else 3*(fakt (3-1))
−→ if False then 1 else 3*(if 2 == 1 then 1 else 2*(fakt (2-1) )
−→ 3*(if False then 1 else 2*(if 1 == 1 then 1 else 1*(fakt (1-1)))
−→ 3*(2*(if True then 1 else 1*(if 0 == 1 then 1 else 1*(fakt0)))
−→ 3*(2*(1))
−→ 3*(2)
−→ 6
7 parallele Auswertungsschritte bei 4 Prozessoren.
Die parallele Zeit ist O(n).
Mehr Prozessoren helfen nicht.
Beispiel: Fakultat
Grundlagen der Programmierung 2 - 35 -
Man kann (fakt n) in paralleler Zeit O(log(n)) berechnen:
Idee: Benutze Divide-and-Conquer:1 ∗ 2 ∗ 3... ∗ n
=(1 ∗ 2 ∗ . . . ∗ (n/2)
)∗
((n/2 + 1) ∗ . . . ∗ n
)usw.
Beispiel
Grundlagen der Programmierung 2 - 36 -
map quadrat [1..n].
Auswertungssequenz:
map quadrat [1..n]
1: map quadrat [2..n]
1: 4: (map quadrat [3..n])
Benotigt O(n) parallele Schritte.
Summation von n Zahlen in einer Liste
Grundlagen der Programmierung 2 - 37 -
Zwei Algorithmen fur Summe im Vergleich:
sum [] = 0
sum (x:xs) = x+ (sum xs)
Benotigt O(n) parallele Reduktionsschritte.
Summation von n Zahlen in einem balanciertenbinaren Baum:
Grundlagen der Programmierung 2 - 38 -
data BBaum a = BBlatt a | Bknoten (BBaum a) (BBaum a)
sumbt (Bblatt x) = x
sumbt (Bknoten bl br) = (sumbt bl) + (sumbt br)
Bei Tiefe h:
2 ∗ (h + 1) parallele Schritte, d.h., log2(n) + 1 .
sehr gut fur parallele Verarbeitung geeignet
Summation von n Zahlen in einem balanciertenbinaren Baum mittels schnellem foldbt
Grundlagen der Programmierung 2 - 39 -
foldbt (+) 0 "(((1,2),3),(4 ,5))"
--> foldbt (+) (foldbt (+) 0 "(4 ,5)") "((1,2),3)"
--> foldbt (+) (foldbt (+) (foldbt (+) (foldbt (+) 0 "5") "4") "3") "(1,2)"
.................
--> 1+ (2+ (3+ (4+ 5))))
Die Problematik ist:
Obwohl sich die foldbt exponentiell ausbreiten:
Die Summe 1+ (2+ (3+ (4+ 5))) ist sequentiell
D.h., man braucht mindestens O(n) parallele Schritte
foldbt nicht geeignet zur Parallelisierung
Paralleles Sortieren von (verschiedenen) Zahlen
Grundlagen der Programmierung 2 - 40 -
Nachweis: Parallelisierung kann Sortieren beschleunigen.
Merge-Sort: die zerlegten Listen sind parallel sortierbar.
Aber: Mischen ist sequentiell, Zerlegen ebenfalls
Man benotigt an parallelen Reduktionen
2 ∗ n + 2 ∗ (n/2) + 2 ∗ (n/4) + . . . = 4 ∗ n D.h. O(n).
Eine Parallelisierung des Bubble-Sort
Grundlagen der Programmierung 2 - 41 -
Gegeben: Array der Lange n
odd-even transposition sort:
Vergleiche benachbarte Elemente und vertausche, falls notig
Notwendig sind (n + 1) ‘div‘ 2 Prozessoren.
Im ersten Schritt
vergleiche Werte mit Indizes (1,2), (3,4), (5,6) . . . ,
im zweiten Schritt (2,3), (4,5), (6,7), (8,9),. . . .
Man kann nachweisen, dass nach n Schritten das Feld sortiert ist.
Man erhalt:• parallele Laufzeit: O(n)• parallele Beschleunigung: ∼ log(n))• parallele Effizienz: ∼ log(n)/n• Gesamtanzahl an Operationen: ∼ n ∗ n
Paralleles Sortieren
Grundlagen der Programmierung 2 - 42 -
Es gibt Parallelisierungen, die in O((log(n))2) laufen.
Es gibt komplizierte Parallelisierungen, die laut Experten sogar
nur O(log(n)) Zeit benotigen.
Parallele Sortieralgorithmen: Sortiernetzwerke
Parallelisierung: Bemerkungen
Grundlagen der Programmierung 2 - 43 -
Teile-und Herrsche kann sehr gut parallelisierbare Algorithmen ergeben
Aber nicht immer: z.B. hanoi
Sequentielle optimierte Algorithmen (Scan)
ergeben i.a. schlecht parallelisierbare Algorithmen
Hand-Parallelisierung auf der Programmiersprachenebene:
nur Anwendungsnische
Stete Beschleunigung der sequentiellen CPUs holt den Vorteil
paralleler Architekturen immer wieder ein
Parallelisierung: Bemerkungen
Grundlagen der Programmierung 2 - 44 -
Wo ist Parallelisierung aktuell lohnend?• auf Prozessorebene• implizit durch den Compiler• Number Crunching: wie z.B. Wettervorhersage• Grid Computing: viele gleichartige Daten, gleiches Programm
Supercomputer sind Parallelrechner mit (aktuell) bis zu 131.072 Pro-
zessoren.
Ein Ausflug in die Komplexitatstheorie
Grundlagen der Programmierung 2 - 45 -
Theoretische Klassifikation von Problemklassen:
Effizient Parallelisierbare Probleme: NC (”Nick’s Class“) (Nikolaus
Pippenger)
Definition: Eine Problemklasse is in NC,
wenn die Probleme in polylogarithmischer Zeit, O(logc(n)) fur ein c > 0
mit polynomiell vielen Prozessoren bearbeiten werden konnen.
Es gilt NC ⊆ PTime. d.h. NC-Probleme haben einen Polynomial-Zeit-
Algorithmus
Vermutung: NC ⊂ PTime.
Dadurch ist es manchmal moglich, nachzuweisen, dass man eine Pro-
blemklasse nicht auf diese gunstige Weise parallelisieren kann.
Beispiel: NC
Grundlagen der Programmierung 2 - 46 -
NC-Probleme (d.h. gutartig parallelisierbar):
Sortieren von Zahlen.
Summation von n Zahlen in einem balancierten Baum.
Zeitschatzung:• n Prozessoren• in Zeit O(log(n)) die Blatter ermitteln• die Ergebnisse in Zeit log(n) (parallel) addieren.