Herzlich Willkommen zu Algorithmen 2.
Genau, Evaluierung.
Es scheinen irgendwie die meisten zufrieden zu sein, bis auf ein paar
Ausnahmen.
Eine Sache, dieses Ding hier, diese Projektorleinwand, es gab einer
kommentiert, ja, die ist so selten unten oder sowas.
Persönlich würde ich dann eine E-Mail schreiben und das nicht in die
Evaluierung machen, wenn es dann fast am Ende ist.
Aber danke für den Hinweis, das Ding kommt jetzt halt immer runter.
Wie gesagt, das sind generell so Sachen, wenn die halt stören oder
irgendwas unverständlich machen, schreibt man eine E-Mail und dann ist
das erledigt.
Dann kommen die Sachen in der Vorlesung.
Okay, aber trotzdem danke für die durchaus positive Evaluierung.
Genau, dann wollte ich nochmal ankündigen, wir am Institut haben einen
Haufen Bachelor- und Masterarbeiten zu vergeben und irgendwann im
Laufe der Vorlesung werden wahrscheinlich auch noch Kollegen kommen
und ein paar Topics ankündigen.
Behaltet das einfach mal im Hinterkopf, wir machen normalerweise
ziemlich spannendes Zeug.
Genau, und das Letzte, auch nochmal ein bisschen Werbung.
Ich hatte ja schon ein paar Mal erwähnt, dass ich eigentlich ab Januar
weg bin, aber nicht ganz, sondern nur 75% meiner Zeit weg, 25% hier.
Und das heißt, dass es im Sommersemester bei mir auch eine Vorlesung
geben wird, über Graphpartitionierung, das, was ich im Prinzip die
letzten Jahre am meisten gemacht habe.
Und das Ding wird dann als Blog-Veranstaltung stattfinden.
Das heißt, es ist wahrscheinlich relativ easy, da schnell eine
Vorlesung im Master abzulegen.
Je nachdem, wo ihr da seid.
Genau, also soviel zur Werbung.
Dann machen wir im Prinzip weiter mit Wiederholungen.
Also was haben wir letzte Woche gemacht?
Wir haben erstmal mit pseudopolynomialen Algorithmen angefangen.
Und haben gesagt, ein Algorithmus A ist pseudopolynomial.
Pseudopolynomial, falls die Zeit von dem Algorithmus polynomial in N
ist.
Wobei jetzt hier N die Anzahl Eingabe-Bits ist.
Wenn alle Zahlen unnäher kodiert werden.
Das heißt im Wesentlichen, wenn ich eine Zahl k habe, dann kodiere ich
die mit k einzeln.
Und dementsprechend habe ich dann so viele Bits, um diese Zahl zu
kodieren.
Also die Zahl k braucht k Bits, um unnäher entsprechend kodiert zu
werden.
So, dann haben wir uns angeschaut, das Rucksackproblem.
Und haben gesagt, okay, das Rucksackproblem hat im Wesentlichen N
Gegenstände.
Gewichte W, I und N.
Und jedes dieser Gewichte hat einen Profit, PI.
Und wir haben insgesamt eine Schranke W, was eine natürliche Zahl ist.
Dann haben wir gesagt, okay, ohne Beschränkung der Allgemeinheit, gibt
es für alle Gegenstände, dass diese Gewichte der Gegenstände kleiner
gleich W ist.
Weil die Idee hinter diesem Rucksackproblem ist, wir haben einen
Rucksack, in den passt insgesamt Kapazität W rein, Gewicht W rein.
Und wenn die Gewichte eine Kapazität größer als W haben, dann passen
sie erst gar nicht in den Rucksack und deswegen kann ich sie einfach
rausschmeißen, weil sie sowieso nicht zu irgendeiner Lösung gehören.
Okay, das Ziel von dem Rucksackproblem war dann, wähle eine Teilmenge
X von Gegenständen.
Und zwar Summe I in X, WI kleiner gleich W.
Das ist genau das, was ich eben gesagt habe.
In den Rucksack passt maximal Gewicht W rein, also habe ich dieses
Constraint, dass die Summe der Objekte, die ich in den Rucksack packe,
vom Gewicht her kleiner gleich W sein muss.
Und die Zielfunktion, Objective, war Summe I in X, PI maximal.
Genau, also das Ziel ist, den Profit zu maximieren.
So, dann haben wir gesehen, Dynamic Programming für das Problem.
Und haben gesagt, okay, C von IP ist die kleinste Kapazität für
Gegenstände I bis I.
Die Profitgröße gleich P ergeben.
So, und dann haben wir uns auch überlegt, bzw.
ich habe halt kurz argumentiert, dass sich I von P berechnen lässt als
Minimum von C von I-1P und C von I-1P-PI plus WI.
Okay, genau, also das ist die dynamische Programmierformel hier und
dann kann man halt Stück für Stück über I induktiv diese Kosten
berechnen.
Man sieht vor allem in erster Iteration schon mal, man braucht immer
nur die vorherige Zeile in dieser Matrix hier und braucht damit Platz,
der linear ist in P. Und haben dann gleichzeitig gesehen, okay,
insgesamt kann man das machen in Zeit U von N mal P-Dach
Pseudopolynomial.
So, dann haben
wir uns angeschaut, was ist ein PITAS und was ist ein FPITAS und haben
gesagt, okay, das sind Algorithmen, mit denen möchte man optimale
Lösungen approximieren.
Und zwar so, dass sie zu einem gewissen Maß polynomiell sind.
So, jetzt gibt es zwei Parameter, einmal den Approximationsgrad, den
ich gerne erreichen möchte und zum anderen die Instanzgröße.
So, das PITAS hat jetzt das Constraint, dass die Zeit polynomiell in
der Instanzgröße sein muss, aber nicht in 1 durch Y.
Also, wenn Y klein ist, bin ich nah dran an der Lösung und das heißt
im Wesentlichen, dass 1 durch Y groß ist.
Also, kleine Y heißt 1 durch Y ist groß und damit kann ich aber immer
noch exponentiell, mit meinem PITAS kann ich immer noch exponentiell
in 1 durch Y sein.
Und das FPITAS, Fully Polynomial Time Approximation Scheme, muss halt
polynomial sein in der Instanzgröße und in 1 durch Y.
Da haben wir Beispiele gesehen, links PITAS, wo offensichtlich noch
exponentielle Teile in 1 durch Y existieren und auf der rechten Seite
eben beides polynomiell sowohl in Instanzgröße als auch in 1 durch Y
ist.
Und wenn man sich das anschaut, dann lässt man, um zu schauen, ob es
eben polynomiell in N oder in 1 durch Y ist, lässt man eben einmal N
konstant und schaut, was passiert für 1 durch Y und andererseits lässt
man 1 durch Y konstant und man sagt, okay, was passiert für N.
Also das ist der wesentliche Unterschied.
Dann haben wir nicht umsonst gerade diese Definition von FPITAS
eingeführt und haben dann gesehen, ein FPITAS für Knapsack, also das
Rucksackproblem.
So, wie ging das?
Wir haben gesagt, okay, P ist der maximale Profit, den ich habe, K ist
ein Skalierungsfaktor, Y mal P durch N, PI' das sind die skalierten
Profite, das ist PI durch K und dann löst man eben das modifizierte
Knapsackproblem hier mit Dynamic Programming.
Und zwar mit P', den alten Gewichten und der Kapazität C, die ich da
habe.
So, und das ist jetzt, sieht man das noch?
Das ist unser FPITAS und jetzt haben wir zwei Sachen gezeigt in der
Vorlesung, die relativ technisch waren.
Zum einen haben wir gezeigt, okay, die Zielfunktion P mal X' ist 1
minus Y mal OPT, wobei das hier, dieses P mal X' nichts anderes ist
als Summe I in X' PI.
Ja, also das ist nichts anderes als ein Skalarprodukt und jetzt ist
man ein bisschen kreativ und dann sieht man, dass dieser X-Vektor im
Prinzip Einsen hat an den Stellen, wo man die Gegenstände haben
möchte, Nullen an den anderen Stellen und dann ist das hier genau
dieses Skalarprodukt und das ist dieses P mal X'.
Ja, und das ist ja im Prinzip genau der Profit, den wir da maximieren
möchten.
Und dann haben wir gleichzeitig gezeigt, die Laufzeit von dem
Algorithmus ist O von N hoch 3 durch Y.
Ja, also polynomiell in N, in Distanzgröße und polynomiell in 1 durch
Y, also in FPITAS.
Ja, das sind die Eigenschaften, wie man nachher nachrechnen möchte.
Okay, Fragen zur Wiederholung?
Keine, hervorragend.
So, dann haben wir uns als nächstes letzte Woche Fix-Parameter
-Algorithmen angeschaut.
Und ich hatte versucht anzudeuten, dass es manchmal Probleme gibt, bei
denen ein Parameter existiert, sodass die Algorithmen nur exponentiell
in den Instanzparameter sind, aber nicht in der Instanzgröße selber.
Ja, das heißt, ich kann nachher einen Algorithmus entwickeln, der
polynomiell in N ist, modifiziert mit irgendwas, was exponentiell von
dem Parameter abhängt, der eben spezifisch für die Instanz ist.
Das heißt, es gibt irgendwie in einer Instanz einen Problemkern, der
im Prinzip die Schwierigkeit enthält, die Kombinatorik.
Genau.
So, dann hatten wir uns als Beispiel angeschaut, Vertex-Cover.
Vertex-Cover war also eine Teilmenge der Knotenmenge, sodass jede
Kante zumindest einem Knoten im Vertex-Cover-Inzidenz ist.
Mit anderen Worten, wenn ich mir angucke, Knoten überdecken Kanten,
überdecken die inzidenten Kanten, dann heißt das, dass alle Kanten
überdeckt sind.
Vertex-Cover.
Knotenüberdeckung.
Jetzt haben wir hier einen Parameter K und der Parameter sagt, es
existiert ein Vertex-Cover der Größe K.
Das ist das, was hier steht.
Das ist unser Entscheidungsproblem und für dieses Entscheidungsproblem
haben wir dann im Prinzip einen Algorithmus entworfen.
Die einfachste Variante hatten wir gesagt, nimm halt alle Teilmengen
und probiere aus, ist es gerade ein Vertex-Cover der Größe K.
Also nimm Teilmengen der Größe K, probiere aus, ist es ein Vertex
-Cover der Größe K.
Und dann kriegt man einen Brute-Force-Algorithmus, der eben O von N
hoch K plus 1 Laufzeit hat.
Jetzt haben wir hier nochmal konkret definiert, was ein Fix-Parameter
-Tractable -Algorithmus ist, bzw.
wann eine formale Sprache L Fix-Parameter-Tractable ist bezüglich
einem Parameter K.
Und hier steht jetzt, eine Sprache L ist Fix-Parameter-Tractable, wenn
ein Algorithmus existiert, der das Problem löst.
Der Laufzeit hat F von K mal P von N.
So ein P von N, P wie immer steht hier für Polynom, das ist
Polynomial.
Und F von K kann jetzt beliebig sein.
Also irgendeine berechenbare Funktion, die nicht von N abhängt.
Und dann sehen wir unten Beispiele hier.
2 hoch K mal N² ist offensichtlich der erste Teil hier.
Dieses F von K ist dann 2 hoch K.
Das ist exponentiell, aber nicht Polynomial.
Völlig egal, was da steht.
Aber der zweite Teil, P von N ist hier N², ist Polynomial in N und
damit ist das Ding insgesamt dann...
Also wenn wir einen Algorithmus haben, der so eine Laufzeit hat, dann
ist es dann insgesamt Fix-Parameter-Tractable.
Genau, so jetzt hatten wir uns überlegt, dass wir einen Algorithmus
haben möchten für Vertex-Cover, der Fix-Parameter-Tractable ist
bezüglich der Parameter-Ausgabe-Komplexität.
Ausgabe-Komplexität ist hier im Prinzip die Größe des Vertex-Cover.
Da haben wir zwei Entwurfstechniken uns überlegt.
Einmal Kernbildung und zum anderen systematische Suche mit
beschränkter Tiefe.
Wie geht im Prinzip naive, tiefenbeschränkte Suche?
Da haben wir gesagt, wenn wir keine Kanten haben, dann haben wir
offensichtlich ein Cover, weil überhaupt keine Kanten abzudecken sind.
Wenn K gleich 0 ist, dann können wir offensichtlich kein Cover haben,
also geben wir entsprechend ein False zurück.
Und ansonsten macht der Algorithmus nichts anderes, als zu sagen, nimm
irgendeine zufällige Kante und probiere aus einem der beiden Endpunkte
ins Vertex-Cover zu packen, weil es reicht immer einer der beiden
Endpunkte, um die entsprechende Kante abzudecken.
Und dann macht eine Rekursion einmal auf den einen Fall und danach auf
den anderen Fall.
Und das muss natürlich mit oder verknüpft werden und dementsprechend
kann man das dann entscheiden.
Und dann haben wir uns überlegt, wie teuer ist das?
Ein einfaches Argument sagt uns, das kostet uns 2k mal n plus m.
Der wesentliche Teil kommt durch die Rekursion, also durch das
Aufbauen von dem Graphen, was uns im schlimmsten Fall o von n plus m
kostet.
Und dann habe ich entweder hier diese Rekursion, die dadurch entsteht,
die ich auflösen kann und komme auf die Laufzeit, oder ich überlege
mir eben, die Rekursionstiefe ist k und auf jedem Level habe ich zwei
Rekursive Aufrufe, also komme ich insgesamt auf 2k Rekursive Aufrufe,
insgesamt also 2k mal n plus m.
So, dann hatten wir versucht, einen Kern zu bilden.
Und hatten hier schon mal die erste Beobachtung, wenn ein Knoten Grad
größer k hat, dann muss der Knoten in der Lösung sein.
Also wir wollen entscheiden, ob der Graphen einen Vertex-Cover der
Größe k hat und wenn der Knotengrad größer als k hat, dann muss er in
der Lösung sein.
Sonst müsste ich alle Nachbarn in die Lösung hineinpacken und das
wären offensichtlich mehr als k und damit wäre das Problem nicht mehr
lösbar.
Also entweder der Knoten ist in der Lösung oder das Problem ist
unlösbar.
So, mit der Beobachtung kommt man eben zu dem Algorithmus hier, der im
Prinzip so lange Knoten findet, also der hier in dieser Waldschleife
die Bedingung hat, solange ein Knoten existiert, der Knotengrad größer
k hat, füge ich ihn in die Lösung ein und reduziere k um 1.
Das heißt, ich habe ja schon einen Knoten in der Lösung, also muss ich
k um 1 reduzieren, weil ich dann bloß noch einen Vertex-Cover der
Größe k minus 1 suche.
Und solange ich eben so Knoten habe, kann ich sie einfach zur Lösung
hinzufügen.
Wenn im Laufe des Prozesses k gleich 0 wird, dann muss ich eben falsch
zurückgeben und ansonsten habe ich hier als Nachbedingung, es
existiert kein Knoten mit Knotengrad größer als k.
Gleichzeitig könnte es passieren, dass isolierte Knoten da sind.
Und diese isolierten Knoten haben keine ausgehenden Kanten, das heißt,
die brauche ich auch nicht mehr in dem Rest des Algorithmus zu
betrachten, also kann ich sie einfach entfernen.
Und dann hat man es auch noch eine Eigenschaft angeschaut, wenn dieser
reduzierte Graph hier mehr als k Quadratkanten hat, dann kann der auch
nicht mehr gecovered werden.
Der reduzierte Graph hat höchstens k Knoten, jeder dieser Knoten hat
höchstens k Nachbarn, damit können wir hier keinen Vertex-Cover mehr
finden.
Und wenn wir jetzt den reduzierten Graph haben, dann rufen wir unsere
alte Funktion auf, Vertex-Cover g und k.
So haben wir analysiert und dann kriegen wir einen Algorithmus, der
insgesamt Laufzeit hat O von n mal k plus 2k mal k Quadrat mit der
Analyse, die wir vorher schon gemacht haben.
Und das ist offensichtlich Fixparameter-Tractable in k, weil das Ding
ist Polynomial in n und hat zusätzlich noch einen exponentiellen
Anteil in k, also 2 auf k ist offensichtlich exponentiell.
Und damit haben wir insgesamt gezeigt, das ist Fixparameter-Tractable.
Dann haben wir uns ein Beispiel angeschaut, wo wir im Prinzip immer
entsprechend Knoten entfernen.
Das sehen wir hier, wir haben Stück für Stück Knoten entfernt.
Hier haben alle Knoten einen Knotengrad kleiner gleich 3, das heißt da
können wir nichts mehr tun.
Auf dem Ding lösen wir dann die Instanz und sind dann fertig.
Also die Frage war, wie kriegt man es hin, Knoten der Größe k zu
finden, ohne dass man sich alle Knoten nochmal anschaut.
Ja, lass mal überlegen.
Also erstens, was in der Zeile hier steht, also O von n plus m, ja das
ist nicht ganz richtig, da steht sowieso schon O von n plus m, das
heißt das stört mich nicht, wenn ich jedes Mal Knotengrad neu
berechne.
Auf der anderen Seite kannst du auch hergehen und sagen, also je
nachdem was man hier macht, das ist sehr sehr high-level, du kannst
aber auch hergehen und eine dynamische Grafdatenstruktur verwenden, wo
du Knoten rauslöscht und inzidente Kanten in konstanter Zeit, sowas
gibt es auch.
Da kannst du dir ganz einfach überlegen, dass du Folgendes machst,
also du speicherst dir für jeden Knoten den Knotengrad und wenn du
einen Knoten entfernst, dann weißt du, dass die Nachbarknoten einen
Knotengrad haben, der um 1 reduziert ist.
Und wenn das der Fall ist, dann haben sie halt irgendwann entweder
einen Grad kleiner als K oder halt nicht und dann muss man halt ein
bisschen weiter gucken, was man da macht.
Aber du kannst auf jeden Fall irgendwie was lazy machen und Sachen
updaten, vielleicht eine Bucket Priority oder sowas, müsste klappen.
Okay, sonst noch Fragen?
Sweet.
Okay, also jetzt machen wir noch ein bisschen weiter, jetzt erweitern
wir den Algorithmus.
Die Reduktionsregeln, die wir eben gesehen haben, sind im Prinzip
nicht die einzigen.
Also für das Problem gibt es jetzt allerhand Reduktionsregeln, die den
Kern, den wir da finden, nachher kleiner machen.
Also weitere Reduktionsregeln sind offensichtlich, ja gut, wenn der
Knotengrad 0 ist, dann brauche ich ihn auch nicht im Cover zu haben.
Wenn der Knotengrad 1 ist, also hier Knotengrad 1 ist dieser Fall,
dann kann ich den Knoten entfernen und sagen, okay, der Nachbar muss
dann einfach im Cover sein.
Also ich könnte dann daraus auch eine Lösung... ja, also nee, ich
entferne diesen Knoten und packe diesen Knoten hier ins Cover.
Für Knoten mit Grad gleich 2 gibt es kompliziertere Strukturen.
Zum Beispiel, wenn man eben so eine Menge von Knoten, so einen Kreis
hier von Knoten mit Grad gleich 2 findet, dann kann man hergehen und
das Ding optimal lösen und dann auch dementsprechend aus der Lösung
entfernen.
Also für so einen Kreis weiß ich, dass jeder zweite Knoten im Cover
sein muss.
Und dann die letzte Regel, die haben wir sowieso schon gesehen, ja,
wenn der Knotengrad größer als K ist, dann muss das Ding ins Cover.
So, und dann kommt man zu einem komplizierteren Algorithmus, der im
Wesentlichen folgendes macht, die Regeln, die wir gerade gesehen
haben, wendet er hier Stück für Stück an.
Also hier die erste Regel, hier die anderen Regeln, ja, gehe ich im
Detail jetzt nicht so genau drauf ein.
Und am Ende kommt man eben zu einem Algorithmus, der diese Laufzeit
hier hat, ja, also im Prinzip noch bessere Laufzeiten.
Genau, und dann gibt es eben noch weitere Verbesserungen, die man sich
anschauen kann.
Oder detailliertere Fallunterscheidungen, man kommt zu noch besseren
Algorithmen, hier mit Laufzeit 1.2738 hoch K plus K mal N.
Im Prinzip, also ich kenne das Papier selber nicht, ja, wenn ihr
reinschauen wollt, XenCanXIA2006.
Genau, so was wir jetzt machen, also was wir jetzt im Prinzip gesehen
haben, ist folgendes.
Ja, wir haben gesagt, okay, wir haben dieses Vertex-Cover-Problem und
wir berechnen den Kern und berechnen exakte Lösungen.
So, jetzt gibt es ein verwandtes Problem, nämlich das Independent-Set
-Problem.
Und wer hier kennt das Independent-Set-Problem?
So, ich kenne es natürlich.
Independent heißt, übersetzt ja unabhängig, das heißt, wir suchen
eigentlich eine unabhängige Menge.
So, unabhängige Menge heißt, wir suchen eine Menge S, die Teilmenge
der Knoten ist, sodass jeweils zwei Paare von Knoten nicht inzident
sind.
Ja, sind unabhängig, das heißt, da ist irgendwie Platz dazwischen.
Und jetzt sieht man hier schon in diesem Bild, ja, dass das Komplement
von einem Independent-Set ein Vertex-Cover ist.
Das heißt, da ist die Verbindung zwischen Vertex-Cover und Independent
-Set.
Und um nochmal auf den Anfang jetzt zurückzukommen, es ist so, vorher
haben wir jetzt für Vertex-Cover einen exakten Algorithmus gehabt,
also so einen Fix-Parameter-Tractable-Algorithmus gehabt.
Das gab es im Prinzip auch für Independent-Sets, wir haben ja gerade
gesehen, die Sachen sind äquivalent.
Also für das Maximum-Independent-Set-Problem.
Was dann halt immer noch das Problem ist, dass wenn der Kern zu groß
ist, kann ich das Problem immer noch nicht lösen.
Also wenn ich einen Kern habe, der Größe 1000 in meinem Graphen, dann
komme ich immer noch zu keiner Lösung des Problems.
Das heißt, was ich jetzt eigentlich machen möchte ist, anstatt den
Kern exakt zu lösen, nehme ich Heuristiken und haue mit den
Heuristiken auf den Kern drauf und komme dann zu Lösungen.
Zu Lösungen, die, wie die Experimente nachher zeigen, nicht zu weit
weg sind von den optimalen Lösungen.
Das machen wir jetzt erstmal nicht.
Die Idee von dem Algorithmus, den wir hier sehen, einfach nur um auch
nochmal diese Kernalization ein bisschen zu verinnerlichen ist, Nimm
ein großes Netzwerk, berechne mit Hilfe von einfachen
Kernalisierungstechniken einen kleinen Graphen und anstatt den hier
exakt zu lösen, nehme ich irgendeine Heuristik für das Problem und
benutze die Heuristiken, um das Problem zu lösen.
Die Heuristiken habe ich jetzt hier weggelassen, ist jetzt auch nicht
zu spannend für das Verständnis von euch.
Und wie gesagt, die Heuristiken sind im Prinzip genau die gleichen,
die wir gerade eben auch für das Vertex-Cover gesehen haben.
Gehe ich jetzt im Detail auch nicht mehr so drauf ein.
Was man tatsächlich auch machen kann, ist jetzt folgendes.
Das ist noch ein Schritt weiter.
Anstelle jetzt zu sagen, ok, sobald ich den Kern habe, wende ich die
Heuristiken auf diesen Problemkern an und bin halt mit der Laufzeit
von dem Algorithmus zufrieden, mache ich jetzt folgendes.
Ich wähle ein paar Knoten aus, zum Beispiel Knoten, die jetzt hier
einen kleinen Knoten gerade haben.
Zum Beispiel hier Knoten, die eben einen kleinen Knoten gerade haben.
Und packe sie in die Lösung rein, entferne sie aus dem Graphen und
öffne damit wieder den Raum für die Reduktion und kann den Graphen
noch kleiner machen.
Und dann suche ich immer weiter kleinere Lösungen, verliere damit
allerdings die Eigenschaft, dass die Lösung, die ich finde, nachher
optimal ist.
Weil ich mich ja für irgendwelche Knoten entschieden habe.
Und dann kriege ich eben so eine Sequenz von immer kleiner werdenden
Graphen, wo ich hier unten auf diesem Minigraphen hier im Prinzip
nachher keine Laufzeit mehr verschwende.
Das geht dann nachher super schnell.
Okay.
Also nur um hier, wie gesagt, nochmal einen Ausblick zu geben.
Es ist dann so, dass dieser Algorithmus, den ich da gerade so ganz
oberflächlich skizziert habe, die Laufzeit insgesamt deutlich
verbessert.
Also wir sehen hier Instanzen, wo der exakte Algorithmus 13 Stunden
braucht und die Heuristik nachher 5 Minuten oder statt 8 Stunden
irgendwie 2,4 Sekunden, statt 2 Stunden 28 Sekunden.
Und dann gab es im Prinzip nachher ein interessantes Ergebnis, was
sagt, okay, immer wenn der exakte Algorithmus die Instanz lösen kann,
findet unser Algorithmus tatsächlich auch die optimale Lösung.
Das heißt, man kann auf den Instanzen, die wir da haben, auf den
Graphen, die Lösung vergleichen.
Und immer wenn der exakte Algorithmus eine Lösung gibt, das heißt,
wenn er in einem bestimmten Zeitraum eben fertig wird, dann findet
unser Algorithmus da auch die gleichen Independent Sets, die gleichen
Maximum Independent Sets.
Auf der anderen Seite sieht man hier in diesen Plots, jetzt muss ich
kurz diese Plots erklären, hier im Prinzip Laufzeit des Algorithmus,
der verschiedenen Algorithmen.
ARW ist eine lokale Suche, der Evolutionäre, also Evomis ist im
Prinzip ein Evolutionärer Maximum Independent Set Algorithmus, das ist
im Prinzip die Heuristik, die man nachher auf dem verkleinerten
Graphen drauf loslässt.
Und wenn man diese beiden, und Redomis macht jetzt nichts anderes als
berechnet den kleineren Graphen, lasst den Evolutionären Algorithmus
drauf los, macht ihn noch kleiner und noch kleiner und noch kleiner.
Und jetzt sieht man hier ganz deutlich, dass wenn wir diesen Evomis,
diese rote Kurve, mit dieser Technik verbinden, die eben diese
Reduktion macht, dann kriegt man eine deutliche Beschleunigung des
Algorithmus.
Also hier sieht man die Lösungsgröße auf der y-Achse, hier wie gesagt
die Zeit, das ist eine logarithmische Skala, das heißt hier sehen wir
irgendwie zwei Größenordnungen Beschleunigung einfach nur dadurch,
dass man eben diese Reduktion anwendet.
Aber das wie gesagt nur als Ausblick, man muss diese Reduktion, wenn
man ein Problem hat, nicht unbedingt dafür anwenden, um nachher exakte
Lösungen zu finden, sondern man kann es auch dafür anwenden, um
tatsächlich in der Praxis schnell Lösungen zu finden.
Und hier ist es wie gesagt eben so, dass man sehr sehr große
Independent Sets findet, verglichen mit dem exakten Algorithmus.
Fragen dazu erstmal?
Genau, dann ist das Kapitel, was wir jetzt machen im Prinzip auch als
Schnupper -Kapitel zu verstehen für parallele Algorithmen, die der
Professor Sanders in der Regel hält, um genau zu sein, genau jetzt und
dann dementsprechend halt im nächsten Wintersemester.
Genau, also was möchten wir im Prinzip machen?
Was wir haben normalerweise sind nicht nur ein Computer, sondern P
-Computer.
Und jetzt haben wir ein großes Problem und möchten mithilfe dieser P
-Computer tatsächlich ein bestimmtes Problem schneller lösen.
Und zwar im Idealfall P mal so schnell, wenn an diesem Problem P
Computer arbeiten.
Und dann ist es normalerweise so, und das steht ja hier so lax auf den
Folien, zu viele Köche verderben den Brei.
Das heißt im Wesentlichen, ab und zu müssen diese Prozessoren, die man
da hat, miteinander kommunizieren.
Also es sei denn, man hat irgendwie eine triviale Parallelisierung.
Und wenn die Algorithmen nicht besonders skalierbar sind, und was das
heißt, erkläre ich gleich noch im Detail, dann führt das dazu, dass
man immer mehr Prozessoren investiert.
Also immer mehr versucht, immer schneller zu werden, aber nachher wird
man gar nicht mehr schneller, weil zu viel kommuniziert werden muss.
Genau, dann auch ein wichtiger Punkt für Parallelverarbeitung ist
Speicherbeschränkung.
Also wir haben ja schon externe Algorithmen gesehen und semi-externe
Algorithmen, mit denen man im Prinzip Probleme lösen kann, die nicht
mehr in den Hauptspeicher von einem Laptop oder einer Maschine passen.
Was man allerdings machen kann, ist zu sagen, wenn das Problem nicht
in die Kiste hier vorne passt, dann nehme ich halt P-Maschinen und
zwar so viele, bis das Problem insgesamt verteilt in den Speicher
passt.
Also wir haben einmal gesehen externe Algorithmen, mit denen man dann
Probleme lösen kann auf einer einzelnen Maschine, das wird allerdings
nachher ziemlich langsam.
Oder jetzt werden wir sehen, mit parallelen Algorithmen geht es
nachher noch schneller.
Und der letzte Punkt hier auf dieser Folie Kommunikationserspartnis,
wenn Dateien verteilt anfallen, kann man sie auch verteilt
vorverarbeiten.
Das heißt im Prinzip, wenn ich zum Beispiel ein verteiltes Dateisystem
habe, dann kann jeder Prozess nachher die Datei auch verteilt lesen
und dann genau die Daten lesen, die er auch braucht und die Daten
dementsprechend auch verteilt vorverarbeiten.
So, jetzt Übersichtsfolie, Parallelverarbeitung am ATI.
Wir machen tatsächlich relativ viel Parallelverarbeitung.
Wir haben zum Beispiel Multicore-Basis-Algorithmen, das heißt zum
Beispiel Shared-Memory-Parallel-Sorting oder Shared-Memory-Parallel
-Selection -Probleme oder was auch immer.
Und das Zeug ist tatsächlich integriert in die GNU-Prozessor-Library.
Also es gibt bei GNU den Flag, was man anschalten kann, benutze Shared
-Memory -Parallelismus und dann werden tatsächlich die Algorithmen,
die hier von dem Johannes Signler damals entwickelt wurden, werden
dann tatsächlich ausgeführt.
Und wenn ihr tatsächlich irgendwann mal diese Option benutzt, dann
könnt ihr im Hinterkopf haben, ah ja, hier bei Professor Sanders wurde
der Kram entwickelt.
Dann gab es bei uns den Vitaly Osipov, der hat GPU-Algorithmen
gemacht.
Wer weiß, was eine GPU ist?
Ja, alle.
Und da will man im Prinzip auch parallele Algorithmen haben.
Und was der dann gemacht hat, ist, er hat den schnellsten
vergleichbaren Sortierer entwickelt.
Was wir auch gemacht haben, sind parallele externe Algorithmen, wie
zum Beispiel Sortier-Algorithmen auch.
Und da geht es im Prinzip darum, dass man jetzt nicht nur parallel
hat, sondern parallel extern.
Das heißt, jeder von diesen parallelen Rechnern hat ein externes
Medium und die Daten können eben nur so verarbeitet werden oder können
eben schnell verarbeitet werden, indem ich einen parallelen
Algorithmus habe, der zusätzlich noch extern ist.
Das wird immer komplizierter.
Dann gibt es Graph-Partitionierung.
Da haben wir tatsächlich auch eine Menge parallel gemacht.
Wie gesagt, das gibt es dann tatsächlich auch in meiner Vorlesung im
Sommer.
Was wir da gemacht haben, ist im Wesentlichen parallele Graph
-Partitionierung für soziale Netzwerke oder eben auch für Graphen, die
aus Scientific Computing kommen.
Und was der Jochen Speck sich angeschaut hat, ist im Wesentlichen
Lastbalancierungs -Algorithmen für eben Parallelverarbeitung.
Wovon reden wir jetzt hier im Prinzip?
Welches Modell gucken wir uns hier im Prinzip an?
Das Modell, das wir haben, ist im Prinzip P-Prozessoren.
Das sind die Dinger hier oben und wir haben ein Netzwerk.
Jeder dieser Prozessoren hat seine eigene ALU, hat seinen eigenen
Register und hat seinen eigenen Speicher.
Und wenn ich auf Daten zugreifen möchte, die auf einem anderen
Prozessor liegen, dann heißt das, dass Nachrichten durch die Gegend
geschickt werden müssen.
Und gleichzeitig ist es so, dass diese Prozessoren hier nicht synchron
arbeiten.
Das heißt, sie haben alle ihren eigenen Prozessor, sind nicht
synchronisiert und können im Prinzip beliebig arbeiten.
Und dann hatte ich eben ja auch schon gesagt, das ist der dritte Punkt
hier, Interaktion durch Nachrichtenaustausch.
Das heißt, wenn wie gesagt Daten von einem anderen Prozessor nötig
werden, dann heißt das, dass eine Nachricht durch das Netzwerk
geschickt werden muss und dementsprechend muss dann irgendein anderer
Prozessor diese Nachricht empfangen und dann können eben diese
Nachrichten da ausgetauscht werden.
So, dann brauchen wir ein Kostenmodell für Nachrichtenaustausch.
Unser Kostenmodell sagt jetzt im Wesentlichen, jeder Prozessor kann
maximal eine Nachricht senden und empfangen.
Jetzt gibt es andere Kostenmodelle, wo das tatsächlich dann anders
ist, wo man mehrere Nachrichten gleichzeitig senden und empfangen
kann.
Es wird alles beliebig kompliziert, aber das machen wir nicht hier,
sondern in der Spezialvorlesung Parallelalgorithmen.
So, und jetzt brauchen wir noch ein Modell für die Kommunikation.
Das heißt normalerweise, wenn ein Prozessor eine Nachricht zu einem
anderen Prozessor schickt, dann ist es so, dass ich erstens ein
Startup -Overhead habe, wie zum Beispiel das initiale Aufbauen der
Verbindung zwischen zwei Prozessoren, und dann, je nach
Nachrichtenlänge, eine Zeit, die es braucht, diese Nachrichterlänge L
zu übertragen.
Und das heißt, ich komme insgesamt zu einer Zeit, T Kommunikation von
L ist T Start plus L mal T Byte.
Also für jedes Byte habe ich im Prinzip eine Zeit, die es dauert, das
zu übertragen, und dann komme ich eben auf dieses Modell hier.
Genau, dann die weiteren Annahmen, die wir hier haben, sind Voll
-Duplex -Punkt-zu-Punkt-Vollständige-Verknüpfung.
Das heißt, dass ein Prozessor sowohl Empfangen als auch Senden
gleichzeitig kann, das Voll-Duplex.
Punkt-zu-Punkt heißt, dass wirklich nur zwei Prozessoren miteinander
kommunizieren.
Und vollständige Verknüpfung heißt, dass ich mich nicht um das
Netzwerk, um das Routing unten drunter kümmern muss, sondern dass
wirklich jeder Prozessor einfach jedem anderen Prozessor nachrichtigen
kann.
Und dann ist es normalerweise so, deswegen kann man das hier nämlich
nicht auch vernachlässigen, dass die Startups-Overhead, die Zeit für
den Startup, üblicherweise viel größer sind als T Byte.
Das heißt, wenn ich jetzt kleine Nachrichten durch die Gegend schieben
möchte, und zwar viele davon, dann ist es eventuell sinnvoller, zuerst
diese ganzen kleinen Nachrichten in ein großes Array zu packen, eben
diese Berechnung vorher durchzuführen und dann das ganze Array durchs
Netzwerk zu schicken.
Das ist tatsächlich etwas, was man in der Praxis eigentlich immer so
macht.
Das ist das erste, was man gesagt bekommt, wenn man mit Professor
Sanders an parallelen Algorithmen arbeitet.
Nachrichten werden zusammengepackt, wenn man sie hat, und dann werden
sie durchs Netz geschickt, komplett als Stück.
Jetzt ist die Frage, warum haben wir kein Shared-Memory-Multicore
-Modell?
Na gut, also dieses Shared-Memory-Multicore-Modell wäre jetzt im
Prinzip diese Erweiterung, dass wir hier noch zusätzliche
Speichermodule haben und dass die Prozessoren selber keinen Speicher
haben.
Dann ist aber allerdings nicht klar, wie erreicht man überhaupt
skalierbaren Parallelismus.
Es ist auch nicht direkt klar, was man bei Speicherzugriffskonflikten
macht, was man da für ein Kostenmaß hat.
Das kann zum Beispiel sein, dass ein Prozessor an eine bestimmte
Speicherstelle schreiben möchte, der andere möchte sie lesen, dann
gibt es irgendwie einen Konflikt, oder beide möchten schreiben, dann
gibt es einen Konflikt, dann ist die Frage, was steht am Ende an der
Speicherstelle und dann muss man sich über ein Kostenmaß Gedanken
machen und das ist aber nicht klar, wie das geht.
Was wir generell machen, wenn wir über so Algorithmen nachdenken, dann
denken wir eigentlich verteilt, also wir entwerfen die Algorithmen
verteilt, das heißt in dem Modell, was wir vorher gesehen haben, an
diesem Modell
und implementieren sie dann tatsächlich vereint, für diese Shared
-Memory -Parallelen-Sachen.
Fragen zu dem Modell?
Wenn wir so Algorithmen formulieren, dann machen wir es eigentlich
immer so als Single Program Multiple Data.
Das heißt, wir schreiben im Prinzip ein Programm und benutzen die IDs
von dem Prozessor, um Symmetrie zu brechen.
Ich habe ein Programm, in dem kann ich mir die ID von dem Prozessor
holen, die ich gerade habe und je nach ID des Prozessors mache ich
bestimmte Dinge.
Der Code, den ich dafür schreibe, ist allerdings insgesamt genau ein
Code.
Im einfachsten Fall schreibe ich eine Datei, wo ich mir die ID von dem
Prozessor hole und je nachdem, welche ID ich gerade habe, tue ich halt
bestimmte Dinge.
Häufig kann es zum Beispiel sein, dass ein Prozessor, der mit der ID 0
eine bestimmte Information hat und die muss nachher an alle
Prozessoren gesendet werden und dann hat man in dem Programmcode eine
If -Formulierung, die einem sagt, wenn meine ID 0 ist, wenn ich der
Root -Prozessor bin, dann schicke ich die Nachricht an alle anderen
Prozessoren und wenn ich das nicht bin, also der Else-Fall, dann warte
ich eben auf die Nachricht von Prozessor 0.
Also als ganz triviales Beispiel.
Und hier auf den Folien ein kleines Hello-World-Programm.
Also Write-Line-Atomic-Hello-I-am-Processor-IPROC-out-of-P-Processing
-Elements.
So IPROC ist hier die ID von dem Prozessor und P ist die Gesamtzahl
der Prozessoren.
Und dann gibt uns dieses Programm eben diese drei Teilen hier aus.
Zugegebenermaßen ist das, was hier auf dieser Folie steht, ziemlich
abstrakt.
Was man normalerweise hat, wenn man so Algorithmen implementiert, ist
MPI -Programme.
MPI steht für Message-Parting-Interface.
Und dann gibt es Libraries, die nennen sich zum Beispiel OpenMPI oder
eben andere.
Also es gibt auch welche von IBM oder noch weitere.
Und die implementieren eben dieses Message-Parting-Interface, die uns
im Prinzip Kommunikationsprimitive zur Verfügung stellen.
Wie eben Sendeoperationen, Empfangsoperationen, gibt mir die Größe von
einem Kommunikator.
Oder gibt mir die eigene ID von dem Prozessor und so weiter.
Und dann implementiert man eben diese Programme mit diesem Interface.
Und die Libraries implementieren dieses Interface, man muss sich um
nichts mehr kümmern.
Und dann ist es im Prinzip ein bisschen weniger abstrakt.
Also kleiner Tipp, um hier ein bisschen besser einzusteigen, wenn euch
das interessiert, googelt mal nach OpenMPI.
Und dann sucht euch da ein heller World-Programm und übersetzt das
mal.
Und dann hat man nachher im Prinzip ein viel besseres Bild für die
parallelen Algorithmen als das, was ich jetzt hier gerade erzähle.
So, der nächste Schritt ist jetzt die Frage danach, ja gut, wie
analysiert man überhaupt parallele Algorithmen?
So, und im Prinzip ist es jetzt so, dass wir eigentlich nur einen
zusätzlichen Parameter haben, p.
Und dann gehen wir eben die Instanz, die Ausführungszeit in
Abhängigkeit von der Instanz und dem Parameter p an.
So, jetzt haben wir ein paar Maßzahlen für diese parallelen
Algorithmen, also zum einen die Gesamtarbeit, die verrichtet wurde,
das ist p mal t von p.
Genau, dann müssen wir uns Gedanken machen darüber, was nennen wir
Speedup.
Und normalerweise sagen wir, wir nehmen den sequentiellen Algorithmus,
nehmen die Laufzeit von dem sequentiellen Algorithmus und teilen den
durch die Laufzeit von dem parallelen Algorithmus.
Und wenn ich das habe, dann weiß ich, wie viel schneller bin ich und
habe dann den Speedup berechnet.
Jetzt muss man hier auch wieder ein bisschen vorsichtig sein.
Man nimmt jetzt nicht einfach den parallelen Algorithmus und lässt ihn
auf einem Prozessor laufen und vergleicht ihn mit der Ausführungszeit
von p-Prozessoren, sondern man vergleicht den hier mit dem besten
bekannten sequentiellen Algorithmus.
Es kann nämlich sein, dass der beste bekannte sequentielle Algorithmus
sich nicht parallelisieren lässt und es dann aber einen anderen
Algorithmus gibt, der sich parallelisieren lässt.
Und dann muss man tatsächlich nachher diese beiden Algorithmen
vergleichen, um zu sehen, wie viel schneller man ist.
Dann sagt der Satz darunter, die relative Beschleunigung, nämlich die
Laufzeit von dem parallelen Algorithmus mit einem Prozessor geteilt
durch die Laufzeit von dem parallelen Algorithmus mit p-Prozessoren,
ist im Allgemeinen etwas anderes als der absolute Speedup, den wir
hier angeben.
Die letzte Maßzahl hier ist im Prinzip die Effizienz und das ist
nichts anderes als der Speedup geteilt durch die Anzahl Prozessoren.
Das Ziel, was wir jetzt normalerweise haben, ist, dass der Speedup im
Prinzip nah an der Anzahl Prozessoren ist.
Das heißt,
im Idealfall wollen wir eben haben, dass S gleich p ist für p
-Prozessoren und damit ist das Ziel hier für die Effizienz, dass wir
irgendwie nah an 1 sind.
Oder zumindest mal so etwas wie konstant, also dieses Theta von 1
hier.
Dann ist die Frage, ist das überhaupt sinnvoll?
Und zwar in der folgenden Art und Weise.
Ist es möglich, dass die Effizienz größer als 1 ist?
Wer ist dafür, dass das möglich ist?
Wer ist dagegen?
Wer hat sich gerade gemeldet für dafür?
Ja, warum?
Wer will es kurz sagen, warum könnte es gehen?
Ja genau, also die Antwort war mit Cache-Effekten.
Also wenn ich eine Instanz habe, sodass die Teilprobleme auf einmal in
den Cache der Maschine passen, dann geht es natürlich okay, dass es
super lineare Speedups gibt.
Ja, das war im Prinzip auch schon die Antwort dieser Frage.
Okay, so dann machen wir im Prinzip jetzt ein Beispiel, was ich noch
hier drauf erklären kann.
Okay, also den Erbsenparallelalgorithmus, den wir uns anschauen, das
ist jetzt eine Reduktionsoperation.
Was wir für so eine Reduktionsoperation brauchen, ist erstmal ein
assoziativer Operator, Plus, das ist genau dieses Teil hier, der in
konstanter Zeit berechnet werden kann.
Und jetzt sagt diese Reduktionsoperation, ich möchte über alle, also
jeder Prozessor hat im Prinzip eins dieser Elemente XI in seinem
lokalen Speicher liegen.
Und ich möchte jetzt mithilfe dieser Reduktionsoperation alle Elemente
reduzieren.
Also ich stelle mir zum Beispiel...
Was heißt überhaupt Assoziativ?
Machen wir das nochmal.
Also Assoziativ heißt nichts anderes als A plus B plus C.
Das ist das gleiche wie A plus B plus C.
Und zwar hier so.
Also wirklich gar nichts Neues.
Und Beispiele sind nichts anderes als Max, Min, Plus, Mal und so
weiter.
Okay, so und diese Reduktionsoperation möchte ich jetzt nichts anderes
als im Prinzip über alle Elemente, die über die Prozessoren verteilt
sind, diese Operation Plus hier ausführen.
Also wenn ich mir überlege, dieser Plus-Operator hier ist genau dieses
Plus, dann möchte ich am Ende alle Elemente aufsummieren, die ich über
die Prozessoren verteilt habe und möchte das auf irgendeinem Prozessor
speichern.
Also der Satz, den wir da eben schon gesehen haben, sei Plus
-Assoziativer Operator, der in konstanter Zeit berechnet werden kann.
Dann lässt sich dieses Ding hier nichts anderes als X0 plus X1 plus X2
plus XP minus 1 in Zeit O von Log P berechnen.
Okay, das heißt, ich habe P Prozessoren, jeder hat sein eigenes
Datenelement, ich möchte diese Reduktionsoperation berechnen und die
Aussage von dem Satz ist, ich brauche Log P Zeit, um das zu machen.
Dann gucken wir uns an, wie geht es im Detail.
Beweisskizze.
Also ohne Beschränkung der Allgemeinheit nehmen wir an, dass P gleich
zwei auch K ist und machen im Prinzip jetzt nichts anderes als
Induktion über K.
Also für K gleich 0, klar, da gibt es gar nichts zu berechnen, da
haben wir einen Prozessor und dann ist klar, dass es auch
dementsprechend in dieser Zeit geht.
K nach K plus 1.
Das heißt, wir wollen gucken, wie sieht das aus hier für diesen
Operator.
Und der Hut, der lässt sich hinschreiben als 2 hoch K XI plus I
kleiner 2 hoch K XI plus 2 hoch K.
So, genau, und jetzt kommt nämlich der Haupttrick.
Ich habe jetzt hier 2 hoch K PEs für den linken Teil, für den rechten
Teil habe ich 2 hoch K PEs.
Und mit der Induktionsannahme weiß ich, dass ich parallel beide Seiten
in Zeit K berechnen kann.
Das heißt, das weiß ich, kann ich in K Zeit berechnen, das kann ich in
Zeit K berechnen und dadurch, dass diese beiden Berechnungen
gleichzeitig laufen, kann ich es insgesamt in Zeit K berechnen.
Jetzt habe ich hier noch einen zusätzlichen Schritt, den ich ausführen
muss.
Das heißt, insgesamt muss ich hier noch einen Zeitschritt addieren,
plus einen Zeitschritt.
Das heißt, ich komme insgesamt auf K plus 1.
Oder malen wir auch nochmal ein Bild hin.
Also hier Tiefe K und hier auch nochmal ein Plus, das ist dann K plus
1.
Also nochmal, Reaktionsoperation heißt zum Beispiel, summiere alle
Elemente auf, die ich auf dem Prozessor verteilt habe und die Aussage
ist, es geht in Loch P Zeit und der Beweis geht im Wesentlichen
induktiv.
Wenn ich den Induktionsschritt hier mache, dann teile ich die
Berechnung auf eben in diese linke Seite und rechte Seite.
Die linke Seite kann ich in Zeit K ausführen, die rechte Seite kann
ich in Zeit K ausführen.
Beides läuft gleichzeitig ab.
Dann brauche ich noch den Schritt, der diese beiden Ergebnisse hier
vereint.
Und dann komme ich auf Zeit K plus 1.
Wie sieht das aus, wenn man das implementiert?
Also wir haben jetzt Prozessoren in die CSI in 0 bis P minus 1.
Und am Anfang sagen wir, alle Prozessoren sind aktiv.
Gleichzeitig haben wir ein Zwischenergebnis, das ist am Anfang XI.
Also über die Prozessoren, die hier unten stehen, hat jeder erstmal
sein eigenes Element.
Und jetzt machen wir im Prinzip Loch P Runden und in jeder Runde
kommunizieren im Prinzip zwei Prozessoren miteinander.
Das heißt in der ersten Runde schickt Prozessor 1 sein Element an
Prozessor 0, der macht dann die Vereinigung und dann sind wir auf der
nächsten Ebene.
Prozessor 3 schickt sein Element an Prozessor 2, der macht die
Vereinigung mit dieser assoziativen Operation hier und wir sind in der
nächsten Runde.
Und genau so geht das weiter mit den anderen Prozessoren hier, die
kommunizieren alle im Prinzip mit ihrem direkten Vorgänger.
Nach dieser Runde sind die Prozessoren, die hier die indices 1, 3, 5,
7 usw.
haben, die sind danach alle nicht mehr aktiv.
Die müssen alle nichts mehr tun, sondern nur noch die Prozessoren, die
im Prinzip vorher auch die Berechnung durchgeführt haben.
Das heißt 0, 2, 4, 6 usw.
sind dann aktiv.
Das sind im Prinzip genau die Prozessoren, über denen hier diese
Pluszeichen das erste Mal stehen.
In der nächsten Runde machen wir im Prinzip jetzt wieder genau das
gleiche.
Wir formen wieder Paare der Größe 2.
Nämlich die beiden Paare hier, die beiden, die beiden und die beiden.
Und jetzt sendet der rechte jeweils sein Datenelement an den linken.
Der macht wieder die Vereinigung und hat damit schon die Operation
berechnet von 0 bis 3.
Und dieser Prozessor hier hat dann schon die Operation berechnet von 4
bis 7 usw.
Und dann geht das eben präkursiv weiter und am Ende hat man auf
Prozessor 0 die komplette Reduktion berechnet.
Also im Pseudocode nochmal, wenn der Prozessor tatsächlich aktiv ist
und das Bit entsprechend gesetzt ist, dann sendet der Prozessor seine
Nachricht zu dem entsprechenden Nachbarprozessor in dieser Runde und
macht sich danach inaktiv.
Und wenn das nicht der Fall ist, also wenn der Prozessor entsprechend
Nachrichten empfangen soll, dann wird das Element empfangen und die
beiden Teilobjekte werden im Prinzip vereinigt.
Das heißt, dieser Algorithmus, den wir hier sehen, funktioniert im
Prinzip genau entlang des Beweises, den wir vorher gesehen haben.
Gibt es Fragen zu dem Pseudocode hier?
Ok, dann schauen wir uns mal an, wie die tatsächlichen Maßzahlen hier
aussehen.
Also wir haben N Prozessoren, wir brauchen Log N Zeit.
Sequentiell, also wenn ich einen Prozessor habe, was machen wir?
Wir iterieren einfach über alle Elemente hier durch, berechnen die
Summe, das heißt sequentiell brauche ich lineare Zeit.
Parallel brauche ich irgendwie Log N Zeit, das heißt der Speedup, den
ich da habe, ist irgendwie N Log N und die Effizienz von dem
Algorithmus ist damit 1 durch Log N.
So, jetzt haben wir vorher schon gesagt, eigentlich hätten wir gerne
einen Algorithmus, der eine ziemlich hohe Effizienz hat, also eine
Effizienz, die nahe bei 1 ist.
Wir sehen jetzt hier in dem Fall für den Algorithmus, dass die
Effizienz für N gegen und endlich gegen 0 geht.
Das heißt, es kann erstmal nicht skalieren, was da steht.
So, und dann gibt es in der Parallelverarbeitung ein klassisches
Prinzip.
Ich glaube, es heißt Brenns Prinzip, um ehrlich zu sein, das steht
hier nicht auf der Folie drauf.
Häufig ist es nämlich so, dass ich für einen Prozessor tatsächlich
nicht nur ein Element habe, sondern viele Elemente, N durch P
Elemente.
So, dann kann jeder Prozessor selber erstmal die sequentielle Arbeit
hier durchführen für seine lokalen Elemente und danach gehen wir erst
in den Parallelalgorithmus rein.
Das heißt, hier steht es nochmal, jeder Prozessor addiert N durch P
Elemente sequentiell und danach die parallele Summe für P Teilsummen.
Das heißt nochmal, wir haben jetzt N Elemente und P Prozessoren und
machen jetzt im Prinzip mehr Arbeit sequentiell und kriegen damit
nachher einen besseren Algorithmus.
Also, wir kriegen erstmal sequentielle Laufzeit von N durch P plus
Theta von Log P. Das heißt insbesondere für die Effizienz gilt dann,
dass das, wie halt eben definiert, die sequentielle Laufzeit durch P
mal die parallele Laufzeit und dann rechnet man hier jetzt ein
bisschen rum und dann kommen wir zu 1 minus Theta von P Log P durch N.
So, und das ist offensichtlich viel besser als das, was wir vorher
hatten.
So, genau.
Dann nochmal zusammenfassend.
Ja, wir haben jetzt im Prinzip gesehen, dass der Binärbogen, den wir
haben, zu einer logarithmischen Ausführungszeit führt, was in der
Regel nützlich ist auf den meisten Modellen.
Ja, und wir haben mal in Brenns Prinzip reingeschnuppert, mit dem man
im Prinzip ineffiziente Algorithmen durch Verringerung der
Prozessorenzahl effizienter machen kann.
So, genau.
Gibt es Fragen dazu?
So, die zweite Operation, die wir uns jetzt anschauen, sind Präfixum.
Das wird noch ein bisschen komplizierter, aber da kommt tatsächlich
noch ein Beispiel dazu.
Also, Präfixum.
Also, was wir brauchen, gesucht.
Und ich erkläre die Notation gleich noch.
Ich habe sie mir nicht selber ausgedacht.
add i
Also, dieses add i, was ich hier hinschreibe, das heißt nichts anderes
als auf Prozessor i.
So, das heißt, was hier steht, und wie gesagt, es sieht irgendwie
kompliziert aus.
Nach dem Beispiel, was ich gleich hinschreibe, ist es irgendwie nicht
mehr so kompliziert.
Wir suchen ein Element auf Prozessor i, das definiert ist als
irgendwelche Nachrichten m, die auf Prozessor i' liegen.
Und zwar dann kombiniert mit dieser assoziativen Kombination über alle
i' kleiner gleich i.
So, machen wir mal ein Beispiel.
Und dieses m kann übrigens ein Vektor sein.
Also, m kann Vektor von n Bytes sein.
Also, machen wir ein einfaches Beispiel.
Jetzt sagen wir, diese assoziative Operation ist nichts anderes als
die Summe bzw.
Plus.
Und haben jetzt 5 Prozessoren, 5 PIs.
Und die Nachrichtenlänge hier ist n gleich 1, 3, 4, 5.
Und die Elemente, die wir haben, sind jetzt 0, 3, 1, 5 und 7.
So, das Resultat in dem Fall sieht dann folgendermaßen aus.
Also, hier steht 0, hier steht 3.
Wenn ich an der Stelle hier bin, möchte ich im Prinzip für diesen
Operator Summe alle Elemente aufaddieren, die kleiner gleich der
eigenen Prozessor addiert sind.
Das heißt, für den Punkt hier steht eine 0, für diesen Punkt hier
steht eine 3, weil 3 plus 0 ist 3.
Für den Punkt hier steht 1 plus 3 plus 0 ist 4.
Für den Punkt hier steht 5 plus 1 plus 3 plus 0 ist 9.
Und dann 7 plus 5 plus 1 plus 3 plus 0 ist 16.
Also eigentlich ganz einfach, super kompliziert hingeschrieben.
Aber wie gesagt, ich habe mir die Notation nicht ausgedacht.
Jetzt machen wir noch ein anderes Beispiel.
Nehmen wir Max.
Wie sieht dann das Resultat aus?
Also, Maximum 0, 3, 3, 5, 7.
Das Maximum über alle Elemente, die bis hier gehen, ist offensichtlich
3.
Das Maximum über alle Elemente, die hier stehen, ist 5.
Und das Maximum über alle Elemente ist 7.
Das ist also eine Präfixsumme.
Präfix, weil ich immer den Präfix über diese Prozessoren habe und dann
die Operation, die man entsprechend ausführen möchte, über alle.
Okay?
Irgendjemand nicht verstanden?
Alle glücklich?
Prima.
So, jetzt ist die Frage innerensequenziell.
Fragezeichen.
Antwort ist Nein.
Weil das, was ich da hingeschrieben habe und auch wie ich es getan
habe, sieht erst mal innerensequenziell aus.
Das heißt, so wie ich es beschrieben habe, guckt ihr immer alle
Elemente davor an.
Das heißt, man hat hier eine Abhängigkeit zu den Elementen davor und
man weiß nicht genau, was man eigentlich machen möchte.
Die Antwort ist, es ist nicht innerensequenziell.
Und in der Vorlesung Parallele Algorithmen ist es so, dass man
verschiedene Algorithmen jetzt kennenlernt, um dieses Problem zu
lösen.
Insbesondere auf den Folien für Algorithmen 2 steht auch noch ein
Algorithmus drauf.
Der nennt sich Hyperwürfelalgorithmus.
Ziemlich kompliziert, ich lasse ihn einfach weg.
Wenn es euch interessiert, schaut ihn euch an.
Insbesondere mit der Notation, die da steht, wird es ziemlich
kompliziert.
Es gibt einfache Algorithmen, die sind nicht so toll wie der
Hyperwürfelalgorithmus.
Wir benutzen das gleich als Blackbox, weil wir uns eigentlich noch
darum kümmern möchten, wie man auf einem Paralleles Rechner sortiert.
Das Wichtige für euch ist hier, die Operation einmal verstanden zu
haben und zu wissen, was man mit der Operation am Ende machen kann.
Jetzt Paralleles Sortieren.
Nebenbei gemerkt, der Michael Axmann ist ein Experte auf dem Gebiet.
Eigentlich müsste er jetzt den Teil hier halten, kann er heute leider
nicht, weil er nicht da ist.
Aber morgen in der Übung erzählt er euch noch ein Prinzip, was man
machen muss, um diese Großrechner tatsächlich zum effizienten
Sortieren zu bringen.
Da geht es dann darum mit 64.000 Kernzahlen zu sortieren und zwar
schnell, so schnell wie möglich.
Normalerweise ist es so, dass wenn man das noch nie gemacht hat, auf
so einem Großrechner zu arbeiten und man das erste Mal 32.000
Prozessoren haben möchte, dass man da ziemlich schwitzt.
Weil man da Angst hat, dass man zu viele Ressourcen verbraucht oder
was auch immer.
Paralleles Sortieren.
Also was wir jetzt machen ist, wir gucken uns an Paralleles Quicksort
und Paralleles Merge Sort.
Und wie gesagt, der Michael erzählt euch morgen noch
fortgeschrittenere Sachen.
So, jetzt gucken wir uns nochmal den Quicksort an.
Sequentiell, vereinfacht.
Was machen wir da?
Na gut,
wähle erstmal ein Pivot.
Dann ordnen wir die Elemente neu, sodass links Elemente stehen, die
kleiner gleich V sind.
Rechts Elemente, die größer gleich V sind.
Und dann sortieren wir die linke Seite.
Und dann sortieren wir die rechte Seite.
Und dann haben wir Quicksort.
Wenn ich das jetzt trivial mache, als Anfänger sozusagen, dann komme
ich im schlimmsten Fall auf eine Rekursionstiefe von N.
Das heißt, die parallele Ausführungszeit ist offensichtlich dann auch
durch N beschränkt.
Und das ist offensichtlich auch schlecht für verteilten Speicher.
Jetzt kommen wir mal zu einer Theoretiker-Parallelisierung.
Das funktioniert folgendermaßen.
Nämlich hier möchten wir auch die Aufteilung parallelisieren.
Das heißt, am Anfang stellt ein Prozessor einen Pivot, zufällig,
irgendeiner von den Prozessoren, die ich habe.
Dieses Pivot wird dann gebroadcasted.
Was ich mit Broadcast meine, ist, dass ein Prozessor die Nachricht an
alle anderen Prozessoren schickt.
Das heißt, jeder Prozessor kennt am Ende das Pivot nach diesem
Broadcast.
Nach dieser Broadcast-Operation.
Als nächstes vergleicht jeder Prozessor lokal sein Element mit dem
Pivot und weiß dann, ist es kleiner oder größer gleich.
Und je nachdem, wie dieser Vergleich ausgeht, haben wir eben eine Zahl
0 oder 1.
In dem vierten Schritt nummerieren wir dann die kleinen Elemente
durch, mithilfe der Präfixsumme.
Das heißt, diese 0 oder 1, über die bilden wir dann eine Präfixsumme.
Und dann wissen wir, wie viele Elemente sind kleiner gleich dem Pivot,
wie viele Elemente sind größer gleich dem Pivot.
Dann werden die Daten nun verteilt, die Prozessoren werden
aufgespaltet.
Und dann arbeitet der eine Teil der Prozessoren auf der linken Seite,
der andere Teil der Prozessoren auf der rechten Seite.
Also das ist erstmal High-Level.
Jetzt hier als Pseudocode nochmal ganz detailliert.
Also am Anfang wählen wir ein zufälliges Element in 0 bis p-1.
Das heißt, damit wählen wir im Prinzip den Prozessor aus, der das
Pivot nachher erstellen möchte.
Dann sagen wir, v ist das Pivot auf Prozessor r.
Also das Element auf Prozessor r, das ist unser Pivot.
Und das wird gebroadcasted.
Dann kommt hier mit f der lokale Vergleich.
Also f ist 1, wenn d links ist und 0 sonst.
Jetzt hier die Präfixsumme über diese Elemente f, die wir uns da
gerade überlegt haben, auf Prozessor k.
Und damit zählen wir die Elemente auf der linken Seite und auf der
rechten Seite.
Und dann haben wir hier noch einen Randfall.
Achso, genau.
Der Randfall passiert genau dann, wenn nachher alle Elemente kleiner
sind.
Also wenn ich im Prinzip nur eine Rekussion durchführen muss und nicht
auf beiden Seiten der Rekussion durchführen muss.
Und was dann in den nächsten Zeilen hier steht, ist nichts anderes als
die entsprechende Umverteilung mithilfe dieser Präfixsumme.
D.h.
über diese Präfixsumme finde ich raus, an welchen Prozessor ich die
Elemente entsprechend schicken muss.
Und am Ende von dem Pseudocode hier sehen wir dann, im Prinzip werden
hier dann die Prozessoren aufgespalten.
Und je nachdem, wo ich mich befinde, arbeite ich entweder auf der
linken Seite oder auf der rechten Seite.
Fragen dazu?
Hier ist mal ein Beispiel.
Wir haben als Pivot die 44.
Und dann zählen wir im Prinzip die Anzahl der Elemente, die kleiner
gleich dem Pivot sind.
Und hier unten sind das die Anzahl der Elemente, die größer dem Pivot
sind.
D.h.
hier haben wir 0, da 0, hier kleiner gleich Pivot ist 1, weil das Ding
hier kleiner gleich dem Pivot ist.
Hier steht auch 1 größer als Pivot.
Achso, genau.
Hier steht die 1 wegen der 44.
Hier steht die 0 wegen der 77.
Und da steht die 1 wegen der 77.
Und dann geht das eben hier durch und zählt im Prinzip die Anzahl der
Elemente, die kleiner gleich dem Pivot sind und größer dem Pivot.
Und dann passiert hier dementsprechend die Umverteilung und mithilfe
dieser Nummern hier oben komme ich eben auf die entsprechenden
Prozessoren -IDs, wo ich diese Elemente nachher umverteile.
Insbesondere sieht man hier, dass mithilfe von dem Algorithmus die
Elemente, die größer von dem Pivot sind, als das Pivot sind, auf der
rechten Seite hier stehen und die anderen entsprechend kleiner gleich
auf der linken Seite.
Jetzt gibt es hier einen Haufen Code.
Auch da gehe ich jetzt nicht so genau darauf ein.
Was hier im Prinzip steht, ist nichts anderes als das, was ich vorhin
schon angeläutet habe.
Die Primitive, die man verwendet, um so einen Algorithmus zu
implementieren, sind Primitive, die aus MPI kommen, aus dem Message
Parsing Interface.
Das heißt, man hat hier Operationen, die einem zum Beispiel sagen, wie
ist der Rang, den ich habe, wie ist meine ID, wie viele Prozessoren
gibt es insgesamt.
Je nachdem, was hier steht, bricht man die Symmetrie entsprechend.
Wie gesagt, ich erkläre das nicht so genau, das ist ziemlich
technisch, ist für das Verständnis von dem Algorithmus auch nicht so
relevant.
Dann gucken wir uns an, wie analysiert man das.
Na gut, pro Rekursionsebene haben wir zwei Broadcasts und eine
Präfixsumme.
Beide kann man in logarithmisch p-Zeit mal t-Startup implementieren,
weil wir immer nur ein Element haben für die Operation.
Die erwartete Rekursionstiefe log p, das heißt insgesamt kommen wir
auf t-Start mal log-Quadrat p-Zeit.
Jetzt hatten wir vorhin ja schon Brenns Prinzip gesehen, jetzt ist die
Frage, geht das tatsächlich auch nach Schema F.
Das Hauptproblem, was man hat, ist im Wesentlichen, dass jeder
Prozessor nachher große und kleine Elemente hat.
Die können also beliebig verteilt sein über die Prozessoren und das
führt dazu, dass die Aufteilung nachher nicht genau aufgeht.
Was meine ich mit Aufteilung?
Na gut, am Anfang hat jeder Prozessor n durch p Elemente und danach
geht das eben nicht genau auf.
Ich möchte danach eigentlich wieder n durch p Elemente pro Prozessor
haben, aber mit dem Algorithmus, den wir gerade eben gesehen haben,
geht das irgendwie nicht genau auf.
Und dann kann man zeigen, dass man am Ende auf eine Zeit kommt, die
hier n log n durch p plus log-Quadrat p möglich ist.
Und was steht da im Prinzip?
Na gut, da steht im Prinzip sowas wie, ich muss lokal sortieren, das
machen alle Prozessoren gleichzeitig, plus log-Quadrat p.
Und dann kommt hier eine Beobachtung, bei verteiltem Speicher stört,
dass jedes Element log-p mal transportiert werden muss.
Warum ist das so?
Na gut, in jeder Rekursionsebene sende ich das Element im Prinzip ja
durch die Gegend.
Und das heißt, dass jedes Element log-p mal transportiert werden muss.
Und dann gibt es dazu eine Alternative.
Wie macht man das tatsächlich besser?
Und oh Wunder, mehr Wege mischen.
Wir haben das schon bei externen Algorithmen gesehen, dass uns das
geholfen hat.
Und genau das gleiche kann man hier auch machen.
Man sagt einfach, wir haben p Prozessoren, jeder Prozessor sortiert n
durch p Elemente lokal.
Dann findet man eben pivots, also mehrere pivots, sodass jeweils n
durch p Elemente zwischen zwei benachbarten pivots liegen.
Das heißt, ich weiß am Ende, wo die Elemente, die ich da habe,
tatsächlich hingehören.
Und dann macht jeder Prozessor in dem Schritt hier nichts anderes als
mehr Wege mischen.
Das heißt, insgesamt habe ich die Anzahl Phasen reduziert und damit
auch die Anzahl der Kommunikationsoperationen kleiner gemacht.
Das heißt, jedes Element muss weniger oft durch die Gegend
kommuniziert werden.
Aber mehr dazu gibt es dann tatsächlich in parallelen Algorithmen,
beziehungsweise der Michael, wie gesagt, erzählt euch dann morgen noch
zu was.
Genau, also was wir hier nochmal sehen, sind im Prinzip Laufzeiten mit
8 Kern und 128 Bit Elementen, wenn man das mit nem parallelen Shared
Memory parallelen Algorithmus macht.
Und dann sieht man eben, je nachdem wie groß die Anzahl der Elemente
werden, desto größer werden hier tatsächlich nachher die Speedups.
Das heißt, für kleine Anzahlen ist es normalerweise so, dass ein
paralleler Algorithmus auch nicht besonders effizient ist.
Das heißt, ich brauche schon große Eingaben, um tatsächlich zu einer
effizienten Parallelisierung zu kommen.
Ja, und dann gibt es eben noch ziemlich viel Zeug, was man da machen
kann.
Ja, genau.
Also es gibt eben, wie gesagt, ziemlich viel Zeug, was man da noch
machen kann.
Gibt es im Detail eben in der Vorlesung paralleler Algorithmen.
So, jetzt ist die Frage, was gibt es noch für parallele Algorithmen?
Wir haben einen Kollegen, der arbeitet an Shared Memory parallelen
Hashtables.
Die gibt es tatsächlich auch im verteilten Speicher.
Also im verteilten Speicher sollte man sie tatsächlich vermeiden,
Shared Memory parallel irgendwie nicht.
Dann gibt es im verteilten Speicher Prioritätslisten, Suchbäume,
Breitensuche, Tiefensuche, kürzeste Wege, maximale Spannbäume.
Eigentlich alles, was man sich so vorstellen kann.
Parallele Graph Partitioning haben wir ja schon gesehen.
Also großes offenes Feld kann man einiges machen.
Und dann auch nochmal hier als Wiederholung diese kollektiven
Operationen, die wir da gerade gesehen haben.
Was man im Prinzip hat nachher ist eine bestimmte Menge an
Basisalgorithmen, die man effizient machen möchte.
Eben diese Reduktions- und Präfixsummen.
Und auch da ist es so, dass man eben ganz viele verschiedene
Algorithmen hat, die unter bestimmten Umständen besser sind als andere
Algorithmen.
Zum Beispiel in Abhängigkeit davon, wie groß tatsächlich
Nachrichtenlängen sind.
Und dann muss man eben sehen, dass man zu jeder Stelle den richtigen
Algorithmus auswählt.