Grundlagen der Programmierung 2 Parallele Verarbeitungprg2/SS2006/folien/kap7-par-fol.pdf · Grundlagen der Programmierung 2 - 7 - Themen: Nebenläufigkeit, Parallelität, Ressourcenverbrauch

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


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


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


n

n-1

n

n-1

n-1n

1

2

3

Beispiel: Turme von Hanoi (2)


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)


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


Themen: Nebenlaufigkeit,Parallelitat,RessourcenverbrauchParallelisierung von AlgorithmenAmdahl-GesetzGustafson-Barsis GesetzBeispielalgorithmen in Haskell

Nebenlaufigkeit und Parallelitat


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


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


• PRAM: parallel random access machine

• Verteilte Berechnung, lose Kopplung

• massiv parallel, enge Kopplung

• Grid-Computing

• Vektorrechner, Feldrechner

• Pipelining

PRAM: parallel random access machine


• 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


• 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


• 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


• Viele Workstations/ PCs rechnen gemeinsam an einer Aufgabe

• verschiedene Hardware / Betriebssystem ist moglich

• I.a. : Rechner haben das gleiche Programm, aber verschiedene Daten

Vektorrechner


• Ein Programm steuert parallele Berechnungen auf HW-Arrays:

• Gleiche Prozedur, verschiedene Datenelemente

• Sinnvoller Einsatz: Wettersimulationen, numerische Berechnungen

• SIMD (single instruction, multiple data)

Pipelining


• 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


Modell auf der Programmiersprachenebene:

Auswertung durch einzelne Reduktionsschritte (z.B. Haskell)

• sequentieller Einzelschritt

• paralleler Einzelschritt = mehrere unabhangige, gleichzeitigeEinzelschritte

Maße fur den parallelen Ressourcenverbrauch


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


Skalarproduktberechnung:

(a1, . . . , an) ∗ (b1, . . . , bn) = a1 ∗ b1 + . . . + an ∗ bn

1. Schritt: Werte die Produkte parallel aus2. Schritt: Addiere die Ergebnisse

Parallele Reduktion; konservativ / spekulativ


• 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


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


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


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


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


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


τ(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


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


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)


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


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


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


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


quadratsumme 3 4 −→ (3*3)+(4*4) −→ 9+16 −→ 25.

2 Prozessoren; 3 Zeiteinheiten werden benotigt

Beispiel: Fakultat


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


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


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


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:


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


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


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


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


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


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


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


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


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.

Beispiel: nicht in NC


Ein Problem nicht in NC: (Vermutlich)

D.h. nicht effizient parallelisierbar

Gegeben ein Schaltnetz

(UND/ ODER / NICHT-Knoten, Gerichteter Graph)

Boolesche Werte an den Eingangen

Berechne die Wert an den Ausgangen

Documents

Grundlagen der Programmierung 2 Parallele Verarbeitungprg2/SS2006/folien/kap7-par-fol.pdf · Grundlagen der Programmierung 2 - 7 - Themen: Nebenläufigkeit, Parallelität, Ressourcenverbrauch