Tja, so sieht es also aus, wenn Fußball und schönes Wetter
zusammenkommen.
Meistens sind wir eher doppelt so viele, aber... Nun gut.
Ja, ich möchte nochmal kurz auf ein paar Dinge eingehen, die wir
letztes Mal hatten, bevor ich weitermache mit dem Thema von heute.
Nur so als Erinnerung.
Wir hatten uns letztes Mal angeguckt, wie wir Parallelrechner
klassifizieren können.
Eine Art der Klassifikation richtet sich danach, wie viele
verschiedene Programme und wie viele verschiedene Datenmengen.
Je nachdem, ob alle Rechner dasselbe Programm haben oder jeder sein
eigenes, sprechen wir von Single Instruction oder Multiple
Instruction.
Und je nachdem, ob jeder Prozessor auf denselben Daten rechnet oder
auf seinen eigenen von Single Data oder Multiple Data.
Und diese beiden Sachen lassen sich kombinieren, sodass es vier
verschiedene Möglichkeiten gibt.
Ein Single Instruction, Single Data, das ist wie ein
Einprozessorrechner.
Ein Multiple Instruction, Multiple Data ist das mächtigste.
Und relativ häufig findet man auch noch Single Instruction, Multiple
Data Rechner, die alle das gleiche Programm ausführen, aber jeder auf
anderen Daten.
Eine andere Art der Einteilung richtet sich nach der Architektur.
Da hat man zum Beispiel Schaltkreise oder Automaten, zelluläre
Automaten oder systolische Automaten mit vielen kleinen Einzelteilen
gesehen.
Die gucken wir uns auch noch genauer an später.
Dann überhaupt mehrere Rechner zusammengeschaltet, kann man als einen
Parallelrechner sehen.
Und die vermutlich am häufigsten bzw.
am meisten studierte Architektur ist die von Parallel Random Access
Machines oder PRAMs, bei denen mehrere Prozessoren alle einen
gemeinsamen Speicher haben, auf den sie beliebig zugreifen können.
Für diese Fälle haben wir da nochmal Unterschieden zwischen
Architekturen, in denen jeweils nur einer lesen oder schreiben kann,
oder alle gleichzeitig.
Wenn nur einer lesen oder schreiben kann, dann nennen wir das
Exclusive, Read oder Write.
Und wenn mehrere gleichzeitig können, dann eben Concurrent.
Und für den Fall des Concurrents haben wir gedacht, müssen wir uns
noch etwas überlegen, was passiert, wenn mehrere gleichzeitig
schreiben wollen.
Und da haben wir auch gemerkt, dass es verschiedene Möglichkeiten
gibt.
Und durchaus nicht ungewöhnlich ist die Lösung, dass man, wenn mehrere
gleichzeitig schreiben wollen, zufällig auswählt, wer dann die
Speicherzelle beschreiben darf.
Dann haben wir uns angeguckt, wie man parallel addieren kann, obwohl
es auf den ersten Eindruck so aussah, als würde es nicht gehen, weil
zum Addieren des Iden-Bits man den Übertrag vom vorherigen Bit
braucht, geht aber trotzdem.
Und das letzte Beispiel, das wir uns angeguckt haben, war die
parallele Maximumsuche.
Da haben wir festgestellt, wenn wir die Maximumsuche einfach so nach
der ersten Idee durchführen, sozusagen baumartig, jeweils zwei
zusammenfassend zu einem Maximum, dann vier, dann acht, bis zum
Schluss alle Elemente maximiert werden, dann sind die Prozessoren sehr
schlecht ausgelastet.
Und die Effizienz war eins durch Logarithmus n, was ziemlich schlecht
ist eigentlich.
Und dann haben wir uns den Satz von Brent angeguckt, der uns sagt,
dass man die Auslastung der Prozessoren unter Umständen verbessern
kann.
Hier nochmal, er sagt nämlich, wenn es einen statischen Algorithmus
gibt für eine EREW-Maschine, also ein Algorithmus, bei dem man von
vornherein weiß, welcher Prozessor wann für welche Aufgabe benötigt
wird, und dieser Algorithmus benötigt die Zeit O von T, läuft auf P
Prozessoren und rechnet dabei insgesamt S Schritte, dann muss es auch
eine Möglichkeit geben, das Problem in derselben Zeit, O-Kalkülmäßig
selben Zeit zu lösen und dabei allerdings nur S durch T Prozessoren zu
verwenden.
Ja, das haben wir dann angewendet für die parallele Maximumsuche und
haben festgestellt, ja, das geht tatsächlich.
Und eine Lösung, wie man mit weniger Prozessoren auskommt, haben wir
uns dann auch angeguckt, indem wir am Anfang, bevor wir in diesen Baum
einsteigen, nicht jeweils nur zwei Feldelemente einem Prozessor geben
zum Maximieren, sondern Log n.
Ja, und heute wollen wir uns angucken, wie man ausnutzen kann, dass
eine CRCW-Maschine tatsächlich mächtiger ist.
Also CRCW, das steht für Concurrent Read, Concurrent Write.
Das ist also dann so etwas, wo mehrere Prozessoren gleichzeitig auf
einen Speicher zugreifen können, sowohl lesend als auch schreibend.
Und das ist ja eigentlich mehr, als man bei einer Exclusive Read,
Exclusive Write machen kann.
Da würden solche Algorithmen unter Umständen abstürzen.
Hier können wir uns jetzt aber überlegen, wie man das Maximieren in O
von 1 hinkriegt.
Nämlich folgendermaßen, wir wollen das Maximum von n Zahlen berechnen,
also A1 bis AN.
Jeder Prozessor, wir nehmen also auch n Prozessoren dazu, jeder
Prozessor kriegt auch eine Speicherzelle, VI zugeordnet im ersten
Schritt, in die er eine 1 reinschreibt.
Also jeder Prozessor weiß seine eigene Nummer.
Ich bin Prozessor I, also was muss ich als erstes tun?
In VI eine 1 reinschreiben.
Da gibt es noch keine Kollisionen, jeder schreibt in verschiedene
Speicherbereiche.
Das würde auch noch mit einer EREW gehen.
Als nächster Schritt nehmen wir nur noch n-1 mal n halbe Prozessoren.
Was heißt nur noch, das sind jetzt mehr, aber im nächsten Schritt
nehmen wir n halbe mal n-1 Prozessoren.
Also für jedes Paar von AI und AJ einen.
Und jeder von diesen Prozessoren vergleicht AI und AJ.
Und wenn AI kleiner AJ ist, dann wird die Speicherzelle VI mit 0
beschrieben.
Und wenn AJ kleiner AI ist, dann wird halt VJ mit 0 beschrieben.
An dieser Stelle hier kann jetzt eine Gleichzeitigkeit passieren.
Es kann sehr wohl sein, dass der eine Prozessor A1 mit A7 vergleicht,
der andere A1 mit A8.
Jedes Mal ist A1 kleiner und jetzt versuchen beide gleichzeitig V1 zu
beschreiben, eine 0 reinzuschreiben.
Aber egal was wir machen, als Strategie ist ja kein Problem.
Wenn wir es zufällig auswählen, kommt auf jeden Fall eine 0 raus.
Wenn wir Prioritäten machen, ist auch egal, kommt eine 0 rein.
Also brauchen wir uns überhaupt gar keine Gedanken darüber zu machen,
wie ein gleichzeitiges Schreiben gehandelt wird bei diesem System.
Wenn beide sowieso das gleiche schreiben wollen, ist kein Problem.
Da das alles parallel passiert, also diese n-1 mal n halbe Prozessoren
machen das alle gleichzeitig, werden also quasi alle Paare
gleichzeitig miteinander verglichen.
Und überall wird eine 0 reingeschrieben, wo es eine größere Zahl dazu
gibt in dem Feld.
Nur in eine einzige Speicherzelle wird nicht 0 reingeschrieben,
nämlich in die, zu der die größte Zahl aus dem Feld gehört.
Und dann kommt der nächste große Schritt, die Prozessoren, also wieder
nur die ersten i, gucken, was in vi drinsteht.
In fast allen steht nämlich eine 0 drin, nur in einem einzigen steht
eine 1 drin.
Und der Prozessor, in dem die 1 drinsteht, der meldet sich und sagt,
ich bin's, i oder ai ist das Maximum.
Und auf diese Art haben wir jeweils hier in O von 1, in O von 1 und
nochmal O von 1 das Maximum von n Zahlen berechnet.
Geht ganz gut.
Und hier haben wir ausgenutzt, dass mehrere gleichzeitig schreiben
können.
Wenn Sie sich mal dafür interessieren, was man noch alles in O von 1
machen kann, probieren Sie mal, n Zahlen zu sortieren in O von 1.
Es geht tatsächlich.
Man kann also n Zahlen in O von 1 sortieren, aus einem Feld in ein
anderes sortiert, übertragen in konstanter Zeit, in O von 1.
Ist ein bisschen komplizierter als das Maximumsuchen, aber das
Maximumsuchen ist da ein Teil davon, von diesem Sortierverfahren.
Ja, ok.
Gucken wir uns mal die Effizienz von dieser Version an.
Die Effizienz war ja 1 durch Log n bei der Version, die wir uns vorher
für die ER-EW-Maschine überlegt hatten.
Und jetzt haben wir also n halbe mal n minus 1 Prozessoren.
Also haben wir unten im Nenner n halbe mal n minus 1 und dann hier
oben den Aufwand für einen Prozessor und unten den Aufwand für n halbe
mal n minus 1 Prozessoren, wenn wir das einsetzen.
O von 1, hatten wir gesagt, war der Aufwand mit n halbe mal n minus 1
Prozessoren.
Wenn wir nur einen hätten, müsste er n minus 1 Vergleiche durchführen.
Ja, oder O von n ungefähr.
Ja, wenn wir das jetzt ausrechnen, dann haben wir das kann sich
rauskürzen ungefähr und dann bleibt noch O von 1 mal n halbe im
Nenner.
Also etwa O von 1 durch n.
Ich schreibe es nochmal dazu, schlampige Schreibweise.
Also Sie müssen sich halt bei diesen Fällen halt dazu denken, dass
damit gemeint ist, wir reden hier von Funktionen, die diese
Eigenschaften haben und so weiter und nicht eigentlich von den Mengen,
die laut O-Kalküldefinitionen dastehen.
Okay, vorhin hatten wir 1 durch Log n, jetzt haben wir 1 durch n.
1 durch n ist ja eigentlich sogar noch schlimmer als 1 durch Log n.
Geht ja noch, fällt ja noch steiler runter.
Ist also nicht besonders gut.
Können wir uns hier auch nochmal fragen, ob wir das nicht effizienter
gestalten können?
Also nochmal die gleiche Idee, wie wir vorhin hatten bei der ERE
-Maschine.
Wenn wir sagen, dass wir jetzt auch hier wieder nicht nur 2
miteinander vergleichen und davon das Maximum berechnen, sondern wenn
wir hier auch wieder gleich Gruppen nehmen.
Vorhin hatten wir ja auch gesagt, wir nehmen nicht nur 2, sondern eine
Gruppe in einer bestimmten Größe.
Probieren wir das mal auch aus.
Auch hier müssten wir dann wieder in der Zeit mehrere Runden drehen.
Wobei in der ersten Runde wird halt jeder Prozessor das Maximum von
einer Gruppe der Größe g berechnen müssen.
Und diese Gruppengrößen, die würden sich ja dann mit der Zeit ändern.
Wir haben ja immer weniger Maxima, die wir berechnen müssen und immer
mehr Prozessoren im Verhältnis zu den Maxima, die wir berechnen
müssen.
Also bietet es sich doch an, diese Gruppengröße auch zu ändern.
Sodass wir also Gruppengröße 1, Gruppengröße 2 haben und so weiter.
Am Anfang hätten wir halt n Eingaben.
Wenn wir die in Gruppen der Größe g1 einteilen, dann haben wir halt
bei der nächsten Runde nur noch n durch g1 Werte, von denen wir das
Maximum brauchen.
Wenn wir dann bei der nächsten Runde dann die Gruppen in der Größe g2
einteilen, dann haben wir nur noch n durch g1 durch g2 Werte, von
denen wir das Maximum brauchen.
Ja, das können wir tatsächlich machen.
Das sieht ungefähr so aus.
Also Gruppe soll die Größe g haben als erstes.
Und das heißt, wir haben insgesamt n durch g Gruppen, von n Werten das
Maximum berechnen, jeweils g in einer Gruppe.
Also n durch g Gruppen.
Wie viele Prozessoren brauchen wir dafür?
Naja, wir brauchen einmal für die Maximumberechnung der Größe g, g
minus 1 mal g halbe Prozessoren.
So wie wir es eben gesehen haben, um das in O von 1 zu berechnen.
Und das für jede von den Gruppen, also n durch g Gruppen, also nochmal
mal n durch g davor.
Ja, jetzt nehmen wir einfach mal an, wir hätten n Prozessoren gegeben.
Vorhin hatten wir ja gesagt, n minus 1 mal n halbe.
Jetzt nehmen wir einfach mal an, wir hätten weniger.
Sagen wir einfach mal n und gucken, was lässt sich damit erreichen.
Oder wie wählen wir jetzt die Gruppengrößen g1 und g2 und so weiter.
Am einfachsten ist es, wenn wir von oben anfangen.
Was wäre, wenn wir als erste Gruppengröße 2 nehmen?
Das hieße, wir brauchen tatsächlich nur einen Prozessor für jede der
Gruppen zunächst mal.
Was die liefern, wären dann n halbe Maxima.
Wir haben dann die Hälfte der Zahlen rausgeschmissen, die kommen dann
nicht mehr infrage.
So, jetzt haben wir n halbe Maxima, aber n Prozessoren, die jetzt noch
weitermachen können.
Das heißt, wir könnten jetzt Gruppen der Größe 4 bilden.
Und wenn wir Gruppen der Größe 4 bilden und dann kommen hinterher nur
noch die Hälfte, also nur noch n Achtel Maxima insgesamt raus, also n
halbe und dann nochmal durch 4, also n Achtel insgesamt.
Jetzt haben wir nur noch ein Achtel, so viele Werte, wie wir
ursprünglich hatten, aber immer noch n Prozessoren.
Also können wir wieder das Doppelte davon, nämlich 16.
Also hier sehen wir das Doppelte hier.
Können wir also 16er Gruppen bilden.
Dann haben wir insgesamt also n halbe, Viertel, Sechzehntel, also 1128
Werte, die dabei rauskommen.
Und das können wir weitermachen.
Und wenn Sie sich das angucken, wie groß werden die Gruppen mit jeder
Runde, dann stellen Sie fest, dass sie quadratisch wachsen.
Also wir haben hier sowas wie 2 mal 2 ist 4, mal 4 ist 16, mal 16 ist
256 und so weiter.
Und ganz allgemein ist halt in der ithen Runde die Gruppengröße 2 hoch
i minus 1.
Und das, was hier hinten also rauskommt, ist dann eben dieser kleine
Anteil hier oben, und das ist der Logarithmus des Logarithmus von n.
Die Zahl der Werte, die eben in dieser Runde dann rauskommen für die
nächste Runde.
Gucken wir uns vielleicht an konkreten Zahlen mal an, damit wir so
grob den Eindruck haben, wie das abläuft.
Also angenommen, wir haben 32.000 Zahlen, das ist 2 hoch 15, genauso
viele Prozessoren.
Und dann legen wir mal los, das ist halt so die erste Runde, zweite,
dritte, vierte und so weiter, dann geht die Zeit runter.
Als erstes haben wir ja 32.768 Maxima, also jede Zahl ist für sich ein
Maximum.
Von all denen brauchen wir ein gemeinsames Maximum.
Also ist der erste Schritt, wir nehmen 16.000 Gruppen zu jeweils 2,
vielleicht sollte man das, die Gruppengröße ist hier.
Und die Gruppen ist das andere.
Also fangen wir mal an mit 16.000 Gruppen zu jeweils 2 Elementen, dazu
brauchen wir 16.000 Prozessoren.
Um von 2 Elementen ein Maximum zu berechnen, also da reicht einer für
eins von diesen Maxima.
Insgesamt also 16.384 Prozessoren, die Hälfte aller Prozessoren
beteiligt sich im ersten Durchgang, um insgesamt hinterher 16.384 noch
Maxima zu berechnen.
So, der nächste Schritt, da haben wir gesagt, jetzt können wir die
Gruppengröße verquadrieren.
Also nehmen wir jetzt als Gruppengröße 4.
Wie viele Prozessoren braucht man, um von 4 Werte ein Maximum zu
berechnen in Ofen 1?
Das sind diese 4 mal 3 halbe, also n mal n-1 halbe.
Und insgesamt haben wir 4.096 Gruppen, da kommt irgendwas um die 24
.000 raus.
Und als Ergebnis nach dieser Runde haben wir noch 4.096 Werte, von
denen wir ein Maximum brauchen.
Nächster Schritt, wir quadrieren wieder die Gruppengröße, jetzt ist
sie 16.
Und das heißt, wenn die Gruppengröße 16 ist und insgesamt 4.096 Werte
vorhanden sind, dann brauchen wir 256 Gruppen.
Um für eine Gruppe ein Maximum zu berechnen, brauchen wir also n-1 mal
n halbe, also 16 mal 15 halbe.
Bei 256 Gruppen, also nochmal 256, dann kommen 30.000 raus.
Und zum Schluss haben wir dann nur noch eine einzige Gruppe mit 256
Werten.
Und für die brauchen wir dann eben, um das in Ofen 1 zu berechnen, 256
mal 255 halbe.
Das ist so fast schon 32.768, nicht ganz.
Das ist jetzt aber auch ein Fall, der nahezu optimal gewählt ist.
Also diese Zweierpotenz, die sich dann auch so super runterquadrieren
lässt oder wo sich die Größen so runterquadrieren lassen oder
hochquadrieren lassen, dass es genau aufgeht.
Typischerweise würde man bei irgendwelchen beliebigen Ends da gegen
Ende nicht mehr solche schönen glatten Werte haben und dann auch nicht
alle 32.000 Prozessoren brauchen, sondern vielleicht nur noch ein
paar.
Aber was man sieht, ist, dass die Auslastung immer größer wird.
Sie nimmt von Runde zu Runde zu.
Erst haben wir nur die Hälfte der Prozessoren und gegen Ende werden es
immer mehr bis zu irgendwann fast alle dann eingesetzt werden.
Das heißt, die Effizienz ist irgendwo zwischen der Hälfte der
Prozessoren und fast alle irgendwo dazwischen.
Können wir auch mal ausrechnen.
Wir haben N Prozessoren, deswegen hier dieses N.
Problemgröße N.
Der Aufwand mit einem Prozessor wäre wieder N-1, wie bisher die ganze
Zeit angenommen.
Der Aufwand jetzt mit N Prozessoren ist ja sozusagen doppelt
logarithmisch, also nicht nur doppelt logarithmisch, sondern
logarithmisch -logarithmisch.
Wenn wir nur immer halbieren würden die Größen, dann wäre es
logarithmisch, aber da wir uns quadrieren sogar, ist es logarithmisch
-logarithmisch.
Also die Tiefe des Baumes, die wir da aufbauen, oder wenn man es als
Baum überhaupt sieht, also die Anzahl der Ebenen, die wir hier
runterlaufen, ist also Logarithmus von Logarithmus N.
Und wenn wir das so grob abschätzen, ist es auch wieder schlampig,
dann kommt eine Funktion raus, die ungefähr O von 1 durch N ist.
Allerdings können wir jetzt nicht mehr in O von 1 fertig werden.
Wir haben zwar nur noch N Prozessoren, aber wir werden nicht in O von
1 fertig.
Denn wir brauchen ja eben Log N Ebenen, Log N Runden, die wir drehen
müssen.
Aber wenn Sie sich überlegen, was ist schon Log N, so viel ist es ja
gar nicht.
Wenn wir vier Zahlen hätten, dann ist Log Log N 1 und selbst bei 65
.000 ist Log Log N 4.
Und wenn wir hier weitermachen, dann kommt da auch irgend so etwas wie
2 mal 10 hoch 19 raus, wo dann der Log Log N davon 6 ist.
Also das sind halt schon solche riesigen Zahlen hier, die Probleme der
Größenordnung erlebt man fast gar nicht.
Also wenn man sagen würde, der Aufwand ist höchstens 6 Schritte, das
ist immer noch fast konstant.
Okay, so viel noch zu diesem Problem der Maximumsuche.
Gucken wir uns jetzt mal ein anderes Problem an, das auch wieder
typisch geeignet ist, um parallelisiert zu werden.
Das ist nämlich das sogenannte parallele Prefix Problem.
Ist gar nicht so umständlich diese Definition, die sagt einfach,
angenommen wir haben die Zahlen X1 bis XN und wir möchten X1 haben, X1
mal X2, X1 mal X2 mal X3 und so weiter, für jedes K eben das Produkt
der ersten K-Werte.
Wobei das jetzt nicht unbedingt ein Produkt sein muss, das kann auch
die Summe sein, das kann auch irgendwas, was Assoziativität erfüllt
sein.
Stellen wir uns einfach mal das Produkt vor.
Ja, wie könnte man da vorgehen?
Erste Idee wäre, wir versuchen mal wieder mit Teile und Hashe, nennen
die Prozedur PP für Parallel Prefix und rufen die auf mit einem
Bereich, von wo bis wo der Parallel Prefix berechnet werden soll.
Wir würden natürlich anfangen mit 1 und N, also der Aufruf wäre PP von
1,N, damit würde es losgehen.
Und dann sagt der Algorithmus, ok, sollten wir in dieser Rekursion,
die wir durch diese Teile und Hashe machen, irgendwann mal so weit
gekommen sein, dass das bis der unmittelbare Nachfolger von von ist,
also nur 1 weiter ist, dann können wir einfach dieses x von von und
das x von bis aufmultiplizieren und das Ergebnis abspeichern, zum
Beispiel in dem selben Feld in x von bis, da können wir es
reinschreiben.
Dann steht eben in x von bis das Produkt von x von von und von x von
bis, also einfach das Produkt von zwei von diesen.
Wenn es nicht so weit runtergekommen ist, wenn wir also den Parallel
Prefix haben wollen für mehr als nur zwei Werte, dann müssen wir halt
irgendwie die Mitte von dem Bereich auswählen, also von und bis
zusammen addiert, minus 1 und die Hälfte, die minus 1 brauchen wir,
wenn wir mit 1 anfangen zu zählen, wenn wir mit 0 anfangen würden zu
zählen, dann bräuchten wir dieses minus 1 nicht.
Also definieren wir jetzt einfach die Mitte von dem Teilstück und
rufen dann entsprechend Teile und Hashe den Parallel Prefix einmal für
die erste Hälfte, einmal für die zweite Hälfte auf, also einmal von
von bis Mitte und einmal von Mitte plus 1 bis bis.
Und was wir jetzt noch machen müssen, um das zu reparieren, wenn wir
hier eben das Parallel Prefix von Mitte plus 1 bis bis berechnen, dann
haben wir ja eigentlich, also wir haben ja hier mehrere Zahlen und
wenn wir für diese hier das Produkt aller Vorgänger bis dahin haben
wollen und es halbiert haben, dann fehlt uns ja noch dieses gesamte
Produkt bis hierhin, wenn wir nur diesen kleinen Ausschnitt hier
berechnet hätten, so wie es in diesem von Mitte bis bis läuft.
Also was wir noch tun müssen ist, dass wir in diese Werte ab der
Mitte, also das was in dem zweiten Aufruf berechnet wurde, für diese
Werte ab der Mitte noch dazu multiplizieren, was alles in der ersten
Hälfte aufmultipliziert worden wäre.
Also X von Mitte ist das letzte aus der ersten Hälfte.
Da steht ja drin, laut Induktionsannahme, das Produkt aller X von 1
bis X von Mitte und den müssen wir halt eben noch das X von I drauf
multiplizieren und dann steht hinterher, wenn der Algorithmus
durchgelaufen ist, in jedem X von I das Produkt der X von 1 bis I.
Also von X1 bis XI.
Ja und wenn wir schon von Parallelität reden, wo ist hier die
Parallelität?
Einmal haben wir sie hier beim Aufruf.
Ein Teil der Prozessoren berechnet die erste Hälfte von dem Bereich,
ein anderer Teil der Prozessoren berechnet die zweite Hälfte und zum
Schluss sind nochmal die Hälfte der Prozessoren damit beschäftigt,
ihre Werte zu reparieren, also diese vordere Hälfte noch dran zu
multiplizieren, wobei das alle wiederum gleichzeitig machen können.
Wenn wir also die Rekurrenzrelation hätten, dann wäre das nicht T von
N ist 2 mal T von N halbe, sondern T von N ist T von N halbe plus O
von N.
Ja, hier steht der Algorithmus nochmal da und hier ist ein Beispiel,
wie er ablaufen würde.
Naja, diese Lambda sind wieder Pünktchen.
Zum Beispiel, wenn wir ein Fels der Größe 8 haben, ja dann, was als
erstes passiert, wir rufen es also auf mit PP von 1 bis 8.
Der Vergleich, ob wir schon irgendwo angekommen sind, wo das bis 1
größer ist als das von, der greift noch nicht, also halbieren wir das.
1 plus 8 minus 1 halbe ist 4, also ist 4 die Hälfte.
Dann wird der PP von 1 bis 4 berechnet und der von 5 bis 8, also
rekursiver Abstieg.
Okay, dann kommt irgendwann der von 1 bis 4, wieder halbieren, 2,
rekursiver Abstieg und jetzt greift hier, wir brauchen den PP von 1
bis 2.
Also wird in X von 2 reingeschrieben das Produkt X1 und X2.
Das ist das, was hier dargestellt ist.
Das ist zum ersten Mal, wo überhaupt etwas berechnet wird, ist an
dieser Stelle.
Ja, dann steigen wir zurück auf aus der Rekursion.
Das nächste Mal, wo wir etwas berechnen müssen, ist an der Stelle, wo
die andere Hälfte berechnet wird, also X3 und X4.
Da wird hier X3 mal X4 berechnet.
Diese Pünktchen sind ja eigentlich hier unnötig, weil es sind sowieso
nur zwei Werte, aber es ist halt eben das Produkt von X3 bis X4 und so
weiter.
Entsprechend wird hier das Produkt von X5 bis X6 und hier das Produkt
von X7 bis X8 berechnet.
Dann ist diese komplette Rekursionsebene abgearbeitet und wir kommen 1
höher.
Und jetzt kommt zum ersten Mal zum Tragen, also diese Rekursionsebene
ist hier abgearbeitet.
Und jetzt kommt zum ersten Mal zum Tragen, dass wir die Werte
reparieren müssen.
Hier, das stimmt ja noch.
Also in diesem Feld steht das Produkt von X1 bis X2.
In diesem Feld hätten wir aber gern das Produkt von X1 bis X4.
Wir haben aber X3 bis X4.
Also was wir tun müssen ist, dieses X3 bis X4 multiplizieren mit dem
schon berechneten X1 bis X2.
Das ist dieser Pfeil hier.
Wenn wir diese Multiplikation durchführen, dann haben wir eben hier
drin stehen tatsächlich das Produkt von X1 bis X4.
Das gleiche gilt natürlich auch für diesen Wert hier.
Hier wollen wir nicht X3 drin stehen, sondern das Produkt von X1 bis
X3.
Also müssen wir auch hier wieder diesen Wert, den wir hier berechnet
haben, verwenden, um die Werte an den Stellen 3 und 4 zu
aktualisieren.
Das gleiche passiert in dieser anderen Hälfte.
Wenn wir hier nicht X7 mal X8 haben wollen, sondern zunächst mal X5
mal X6 mal X7 mal X8, dann müssen wir auch hier dieses
Zwischenergebnis X5 mal X6 dran multiplizieren und haben dann eben die
Multiplikation von 5 bis 8 alle hier drin stehen.
Und dann kommt wieder der nächste Aufstieg zurück.
Und jetzt muss für diese ganze zweite Hälfte hier diese Reparatur
gemacht werden.
Wir haben hier drin stehen das Produkt ursprünglich X5, hier 5 bis 6,
hier 5 bis 7, hier 5 bis 8.
Und wenn wir an alle noch das 1 bis 4 dran multiplizieren, dann sind
diese Pfeile alle da.
Dann haben wir hier überall drin stehen X1 bis 5, X1 bis 6, X1 bis 7
und X1 bis 8.
Und jetzt ist die Sache erledigt.
Es ist alles fertig.
So funktioniert also zum Beispiel so ein Parallel Prefix.
Analysieren wir auch den Algorithmus mal.
Zunächst mal, was für ein Rechnermodell brauchen wir?
Wenn wir hier zum Beispiel sehen, dass diese Werte hier alle
gleichzeitig berechnet werden sollen, dann müssen alle diese vier
Prozessoren gleichzeitig auf dieses Ergebnis zurückgreifen.
Das Produkt von X1 bis X4, das muss alles gleichzeitig hier zur
Verfügung stehen für alle von diesen.
Das heißt, wir brauchen eine Maschine, wo es möglich ist, dass mehrere
Prozessoren gleichzeitig herauslesen.
Also zumindest eine Concurrent Read brauchen wir.
Zum Schreiben, ein Schreiben ist niemals so vorgekommen, dass zwei
gleichzeitig auf eine Speicherzelle schreiben.
Also würde hier eine Exclusive Write genügen.
Ja, dann brauchen wir noch N Prozessoren.
Okay, aber das ist mal keine nennenswerte Einschränkung.
Aber so würde es gehen.
Ja, weiter in der Analyse.
Welchen Aufwand hat diese Vorgehensweise?
Wir machen Standardteile und Herrscher.
Das heißt, wir haben logarithmische Rekursionstiefe, logären
Rekursionsebenen, die wir abarbeiten müssen.
In jeder Ebene haben wir in halbe Multiplikationen durchzuführen, die
wir aber alle gleichzeitig machen können.
Das heißt, der zeitliche Aufwand pro Rekursionsebene ist konstant, O
von 1.
Und wir haben logären Rekursionsebenen, also ist die Gesamtlaufzeit O
von logarithmisch N.
Und die Effizienz dazu?
Aufwand mit einem Prozessor.
Wie viel Aufwand bräuchten wir, wenn wir einen Prozessor hätten?
Na ja, x1 mal x2 mal x3 müssten alle aufmultipliziert werden, also N
Stück.
Mit anderen Worten etwa O von N.
Der Aufwand mit N Prozessoren haben wir eben berechnet, ist log N.
Unten im Nenner noch N dran multiplizieren für die Effizienz.
Was hier rauskommt, ist etwa O von 1 durch log N.
Auch hier wieder schlampig, aber Sie wissen, was gemeint ist.
Ja, ist die gut oder nicht gut?
Na ja, könnte besser sein.
Das war jetzt ein CREW-Algorithmus.
Und der Satz von Brent ist eigentlich nicht definiert für CREW
-Maschinen, sondern nur für Exclusive Read, Exclusive Write-Maschinen.
Trotzdem gucken wir uns mal an, was denn der Satz von Brent dazu sagt.
Also in dem Fall haben wir gesagt, zeitlicher Aufwand O von log N.
Die Schritte, die insgesamt gerechnet werden, sind O von N pro Ebene
mal log N, also O von N, log N Schritte.
Wenn wir das in den Satz von Brent einsetzen, dann sagt uns der, wir
können in der gleichen Zeit fertig werden, indem wir S durch T
Prozessoren benutzen.
Also N log N durch log N, das ist N.
Also sagt uns der Satz von Brent, wenn es ein CREW-Algorithmus wäre,
hätte man nichts davon.
Wir haben zwar mit N Prozessoren einen Algorithmus, aber wir können
genauso gut mit N Prozessoren auskommen, das ist uns nichts Neues.
Also keine Verbesserung.
Aber wie gesagt, eigentlich greift er ja hier nicht.
Deswegen die Frage, könnten wir vielleicht einen EREW-Algorithmus für
dieses Parallel Prefix konstruieren?
Vielleicht wäre das ja eine ganz nette Version.
Ja, gucken wir uns das mal an.
Wie könnte man da vorangehen?
Vielleicht erinnern Sie sich noch an die schnelle Fourier
-Transformation.
Da war auch eine Teile-und-Häsche-Geschichte dabei.
Allerdings auch hier wieder nicht nur die Unterteilung in erste
Hälfte, zweite Hälfte, sondern die Unterteilung in gerade und
ungerade.
Vielleicht hilft uns das ja hier auch und bringt uns weiter.
Angenommen, wir hätten diese Produkte von X1 bis XK für alle geraden
Ks.
Wenn wir die irgendwo schon mal berechnet hätten, was müsste man dann
noch tun, um die ungeraden Ks zu berechnen?
Da bräuchten wir einfach nur für jedes von diesen ungeraden XK plus 1
noch eine Multiplikation dran machen.
Um also das Produkt von X1 bis XK plus 1 zu berechnen, wird es
vollkommen ausreichen, wenn wir einfach das schon vorhandene X1 bis XK
haben und dazu noch das XK plus 1 dran multiplizieren.
Also mit insgesamt n halben Schritten könnten wir dann auch alle
Ungeraden berechnen.
Probieren wir mal dieses so quasi verzahnte, gerade ungerade verzahnte
Teile - und Hashesystem hier mal zu implementieren.
Dann läuft es auf einen Algorithmus hinaus, der ungefähr so aussieht.
Auch hier wieder nennen wir es PP für Parallel Prefix.
Und jetzt machen wir ja nicht vordere Hälfte, hintere Hälfte, sondern
wir machen erstmal die Geraden und dann ähnlich wie bei der Fourier
-Transformation von den Geraden nochmal die Geraden bzw.
die Ungeraden und dann nochmal von den Geraden der Geraden, also von
den durch 4 teilbaren jeweils die Geraden.
Das wären dann die durch 8 teilbaren.
Mit anderen Worten, der Algorithmus ist nicht über die Hälfte,
Viertel, Achtel des Gesamten.
Feld ist definiert, sondern über einen, nennen wir es Inkrement, also
das Ink für Inkrement.
Wobei wir dann eben davon ausgehen, dass das Inkrement erstmal 1, dann
2, dann 4 und so weiter, dann 8 und so weiter ist.
Okay, dann werden wir also erstmal gucken.
Wenn das Inkrement 1 ist, dann hieße das, wir betrachten uns jetzt nur
diese Geraden, das heißt, wir machen es in eine Schleife laufen von 1
bis 1,5, wenn das Inkrement 1 ist und berechnen also für alle 2i, das
heißt für alle Geradenwerte, diese Produkte, diese Parallel Prefix.
Sie sehen, wenn Ink 1 ist, dann haben wir hier for i gleich 1 bis n,
halbe und k ist 2 mal i, das sind genau die Geraden.
Dann käme als nächstes der rekursive Aufruf, wobei wir jetzt
allerdings wiederum nur die Geraden der Geraden, also mit einem
doppelten Inkrement unsere Prozedur aufrufen.
Das heißt, wir rufen immer das PP von Ink nochmal auf mit PP von 2
Ink.
Und was dann, wenn davon die Ergebnisse fertig vorliegen, was dann
noch zu tun ist, ist diese oben genannte Multiplikation für die
Ungeraden.
Das heißt, wir lassen dann wieder eine Schleife laufen von 1 bis n,
halbe mal Ink, also n durch 2 Ink.
Wenn Ink 1 ist, dann halt eben 1 bis n, halbe.
Und k geht dann durch alle Geraden durch, also k gleich 2i plus 1, wo
wir oben k gleich 2i hatten.
Und diese Berechnung für die Ungeraden ist dann halt eben genau dieses
eine dran multiplizieren.
Das sieht jetzt vielleicht anhand dieses Algorithmuses nicht ganz so
anschaulich aus.
Man muss ja wirklich zwei, dreimal drüber lesen, bis man erkennt, was
abläuft.
Achso, ja, vielleicht sieht es ein bisschen anschaulicher aus, wenn
man diese Grafik sich ansieht.
Also angenommen, das wäre nun dieses Feld von x1 bis x, was weiß ich,
32, 64, irgend sowas.
Und dann haben wir gesagt, als erstes sagen wir, Inkrement ist 1.
Das heißt, wir berechnen von allen Geraden den Parallel Prefix.
Also das wäre der erste Schritt, der passiert.
Das heißt, das ist das x2, x4, x6 und so weiter.
Und x2 beinhaltet nach dieser Operation den Wert x1 mal x2.
x4 beinhaltet den Wert 3 mal 4, x6 den 5 mal 6 und so weiter.
So sah es ja vorhin fast genauso aus.
Da war ja kein nennenswerter Unterschied.
Ja, aber jetzt geht es weiter.
Jetzt kommt nochmal der Aufruf, und zwar jetzt wieder von den Geraden,
von diesen Geraden.
Das heißt, hier haben wir jetzt das x4, dann das x8, dann das x12,
also alle durch 4 teilbaren.
Und was wir hier drin stehen haben, in jedem von diesen, ist eben das
Parallel Prefix von diesem entsprechenden 4er-Block dazu.
Hier drin steht das Parallel Prefix von dem dazugehörigen 4er-Block.
Also in dem x12 zum Beispiel steht halt dann eben x9 mal x10 mal x11
mal x12.
Das schreiben wir jetzt hier rein.
Ja, jetzt geht es weiter.
Jetzt werden wieder diese nochmal, davon die Geraden genommen, also
alle durch 8 teilbaren.
Dann haben wir hier zum Beispiel in x16 haben wir drin stehen, in x16
steht dann halt dieser komplette 8er-Block drin.
Also x9 mal x10 mal x11 mal x12 bis mal x16.
Und hinten in x32 steht dann halt der 8er-Block ab hier.
Jetzt geht es weiter.
Wir haben noch nicht fertig halbiert.
Davon gibt es auch wieder die Geraden.
Das sind dann halt eben diese x16 und x32.
Jetzt haben wir nur noch zwei Werte, nämlich in x16 steht der Parallel
Prefix der ersten 16 drin.
Und in x32 steht der Parallel Prefix der zweiten 16 drin.
Jetzt können wir noch einmal halbieren, dann ist Schluss.
Jetzt steht in x32 der Parallel Prefix von allen drin.
Das ist aber der von allen.
Wir haben aber gesagt, Parallel Prefix ist nicht nur x1 bis x32,
sondern das ist x1 und x1 mal x2.
Außerdem wollen wir haben x1 mal x2 mal x3 und x2 mal x4.
Wir wollen sie alle haben.
Und wo steht x1 mal x2 mal x3?
Das steht noch gar nicht da.
Das sind ja diese ungeraden Teile, die müssen wir jetzt reparieren.
Also, Aufstieg.
Wieder zurück in diese Ebene.
Hier hatten wir ja quasi vier Werte, nämlich 1, 2, 3, 4.
Wo zwei davon gerade waren und zwei ungerade.
Den ersten ungeraden brauchen wir nicht, den haben wir schon hier oben
berechnet.
Bleibt nur noch dieser zweite ungerade, der uns interessiert.
Das ist also ungerade aus der Sicht von dieser Ebene her.
Das ist immer noch in den Geraden, aber aus der Sicht dieser Ebene ist
es der dritte.
Ja, was ist also, das ist so wie x16, 17, 18, 19, 20, 21, 22, x24 ist
das.
Um x24 zu berechnen, brauchen wir also den Parallel Prefix bis x16.
Das ist also alles, was alles bis 16 aufmultipliziert.
Und hier oben haben wir schon berechnet, alles von 17 bis 24.
Also lautet eben in diesem Schritt, das ist dieser ungerade Anteil.
Multipliziere alles bis zu dem x16er, also bis zu 4 mal 4.
Ne, bis zu 16, das ist 2 mal 8.
Alles bis zu 2 mal 8 und addiere dazu den 3 mal 8.
Das ist der 1 mal 8, 2 mal 8, 3 mal 8, 4 mal 8.
Das wäre also beim Increment 8 wäre das der Faktor 3.
Der gerade mit Faktor 2, den haben wir.
Dazu noch drauf multiplizieren den an der Stelle 3 und schon ist x24
fertig.
Wieder weiter aufwärts in diese Ebene.
Ja, jetzt sind wir halt hier in dieser Ebene da.
Hier hatten wir 8 Zahlen mit Increment 4.
Also die 4, die 8, die 16, 12, 16, 20, 24, 28, 32.
Und die Ungeraden aus dieser Sicht, aus diesem Level, das sind eben
genau die, die hier grün gekennzeichnet sind.
Also um zum Beispiel von x12 das Produkt zu berechnen, von x1 bis x12,
nehmen wir das von x1 bis x8 und das von x9 bis x12.
Also das von 2 mal 4 und das bis zu 3 mal 4.
Entsprechend hier das von 4 mal 4 und das bis zu 5 mal 4 noch dazu.
Und hier das von 6 mal 4 bis zu dem 7 mal 4 dazu.
Und so weiter.
Jetzt können wir nochmal aufsteigen.
Dann kommen die Ungeraden aus dieser Sicht.
Und dann nochmal als letztes die Ungeraden aus dieser obersten
Schicht.
Also die tatsächlich echt alle Ungeraden.
Und dann sehen wir hier, dass zum Beispiel eben x3 jetzt den Wert
enthält, x1 mal x2, was hier drin stand, mal x3.
Und wenn wir jetzt fertig sind, dann haben wir in jeder Zelle den
Parallel Prefix bis zu dahin stehen, also das Produkt von x1 bis x9.
Wenn wir uns das jetzt angucken, dann stellen wir zum Beispiel fest,
gleichzeitig schreiben ist auch hier gar nicht nötig, aber hier ist
nicht mal gleichzeitig lesen nötig.
Machen wir wieder alles weg, vielleicht sieht es dann hübscher aus.
Es kommt nicht mal mehr irgendwo vor, dass zu einem Zeitpunkt
gleichzeitig zwei Prozessoren aus derselben Speicherzelle lesen.
Das ist gar nicht nötig.
Das liegt daran an dieser gerade-ungeraden Aufteilung.
Das heißt, das hier funktioniert auf einer EREW-Maschine.
Vielleicht auch hier ein kleines konkretes Beispiel dazu.
Der Algorithmus steht nochmal hier, so wie wir ihn vorhin
hingeschrieben hatten.
Aufruf mit Inkrement, zunächst mal mit 1, dann 2, 4, 8 und so weiter.
Wenn das Inkrement bis zur Hälfte der Größe des Feldes gekommen ist,
dann sind wir fertig.
Das ist jetzt willkürlich, ob wir hier bis zur Hälfte des Feldes gehen
oder bis n gehen.
Also auf jeden Fall, wenn wir bis zur Hälfte gehen, dann können wir
sagen, in xn schreiben wir hinein, was das Parallel Prefix bis n
halber war und multiplizieren das, was dann eben bis xn drin stand.
Also quasi die beiden Hälften zusammen machen, das entspricht dann in
diesem Bild, diesem Schritt hier.
Wir könnten auch die Rekursion noch weitermachen, meinetwegen bis
Inkrement gleich n ist und fahren dann so zurück.
Ist eigentlich gehupft wie gesprungen.
So, wenn wir jetzt aber nicht am Ende sind, sondern irgendwo
dazwischen, der Inkrement ist also irgendwas zwischen 1, 2 und so
weiter, aber noch nicht in halbe.
Dann haben wir den geraden Anteil, den ungeraden Anteil und das
Absteigen.
Der gerade Anteil, das ist das, was wir da vorhin mit den schwarzen
Strichen gesehen hatten.
Der sagt immer, dass wir eben in diese Stelle 2 Inkrement mal i einen
neuen Wert reinschreiben, nämlich den, den wir da bisher drin haben, 2
Inkrement mal i und das multipliziert mit dem nicht besonders
anschaulichen 2 Inkrement i minus den Inkrement davor.
Also das ist das, was ich vorhin meinte, 8 mal 4 plus 9 mal 4 oder 3
mal 4 plus 4 mal 4, das ist dann halt eben hier nochmal der eine
weniger.
Das wird da drauf multipliziert.
Hier unten in dem Teil ist, wenn wir zurückkommen aus der Rekursion,
kommen noch die ungeraden dazu, wobei ungerade bedeutet halt eben
nochmal einen Inkrement mehr.
Man könnte auch das Inkrement hier ausklammern und hätte dann ein i
plus 1 dastehen, dann würde es vielleicht eher einleuchten, warum das
die ungeraden sind.
Also das ist ja Inkrement mal 2 i plus 1, daran sehen Sie, was
ungerade ist.
Und dazwischen ist eben der Abstieg, das gleiche nochmal aufrufen mit
dem doppelten Inkrement.
Wenn wir uns das hier an diesem kleinen Feld ansehen, dann sieht es so
aus, erstes Inkrement 1.
Wir gehen also in die Schleife, die Wendbedingung ist nicht erfüllt.
Wir gehen also in die Schleife von 1 bis n halber, also n durch 2 mal
Inkrement, also von 1 bis n halber.
Wenn, so wie hier dargestellt, n gleich 8 ist, heißt das n halber ist
4.
Also läuft die Schleife von 1 bis 4.
Was zu tun ist, ist zunächst mal der Geradeanteil.
Schreibe in 2 i den Wert von 2 i minus 1 mal den Wert von 2 i rein.
Das sind diese vier Operationen.
x von 2 ist x von 2 mal x von 1.
x von 4 ist x von 3 mal x von 4.
x von 6 ist x von 5 mal x von 6.
Und x von 8 ist x von 7 mal x von 8.
Das hier kann alles parallel passieren.
Dann Abstieg, Inkrement verdoppeln.
Inkrement ist jetzt 2.
Die Schleife läuft jetzt nicht mehr bis n halber, sondern nur noch bis
n viertel.
Und wir haben hier nicht mehr x von 2 i, sondern x von 4 i an den
entsprechenden Stellen stehen.
Das heißt, das sind bei uns diese zwei Pferde, wo das greift.
Also für i gleich 1 haben wir x von 4 ist x von 4 mal x von 2.
Und für i gleich 2 haben wir x von 8 ist x von 8 mal x von 6.
Das gleiche nochmal absteigen mit dem Inkrement 4.
Dann läuft die Schleife nur von 1 bis 1.
An der Stelle könnte man jetzt auch diese Wendbedingungen abfangen.
Oder wir rechnen es durch.
Dann kommt eben eine Operation, die durchgeführt werden muss, nämlich
x von 8 ist das Produkt von x von 8 und x von 4.
So, jetzt kommen wir wieder raus.
Deswegen sind wir jetzt wieder in dem Kästchen oben drüber.
In dem Kästchen, wo das Inkrement 2 ist.
Jetzt kommen die ungeraden Teile.
Also die Schleife läuft jetzt von 1 bis 1 weniger als n Viertel.
Also von 1 bis 3.
Ne, 1 bis 1.
Ja, also genau, nur von 1 bis 1.
1 bis 3 ist hier unten.
Also läuft von 1 bis 1.
n Viertel ist 2, minus 1 ist 1.
Die einzige Rechnung, die hier...
Das Einzige, was ungerade ist, aus der Sicht dieser Ebene, ist x von
6.
Und dann wird eben x von 6 mal x von 4 in x von 6 reingeschrieben.
Und zum Schluss noch die vollständig ungeraden, also die auch
bezüglich Inkrement 1 ungeraden.
Da gibt es dann drei Fälle, wo was passiert.
Einmal für x von 3, einmal für x von 5 und einmal für x von 7.
Das sieht man dann wieder leichter, wenn man hier für i die Werte 1,
2, 3 einsetzt.
Auch hier ist wieder zu erkennen, es wird nie gleichzeitig von zwei
Prozessoren aus dem selben Speicher heraus gelesen.
Also, das funktioniert für einen ER-EW-Rechner.
Naja, wenn das für den ER-EW geht, dann können wir jetzt vielleicht in
Richtung Satz von Brent mal gucken, ob sich jetzt was machen lässt.
Also ER-EW-Bedingung für Satz von Brent ist gegeben.
Aufwand ist der gleiche wie beim ersten.
Auch hier haben wir wieder Log-N-Rekursionsebenen.
Das sind halt nur andere Dinge, die in den verschiedenen Ebenen
multipliziert werden.
Auch hier können wir wieder in einer Ebene alles auf einmal machen.
Geht in O von 1.
Also gilt auch diesmal, der Gesamtaufwand ist O von Log-N.
Die Anzahl der Schritte, die wir rechnen müssen,
können wir per Rekurrenzrelation machen.
Die Anzahl der Schritte für Ebene N ist die Anzahl der Schritte für
die N-Halbe.
Und dazu kommen noch N-1 dazu.
In der ersten haben wir also eine, und es kommt raus, wir haben
insgesamt O von N Schritte in etwa.
Das heißt, in die Effizienzformel eingesetzt, kommt als Ergebnis raus,
Effizienz 1 durch Log-N.
Okay, jetzt mal gucken, was sagt der Satz von Brent dazu?
Hier steht er nochmal.
Wir haben also einen Algorithmus, der in der Zeit O von T fertig wird,
wobei das T Log-N ist.
Und er läuft mit P Prozessoren, wobei das P auch N ist.
Und der Satz von Brent sagt, dann lässt sich das auch mit S durch T
Prozessoren erledigen.
S war auch etwas mit O von N.
Also sagt Brent, wir kommen aus mit O von N durch Log-N Prozessoren.
Und N durch Log-N, das ist durchaus weniger als O von N.
Das heißt, es ist im Prinzip möglich,
mit N durch Log-N Prozessoren eine Effizienz zu erreichen, die, wenn
wir es hier einsetzen, ergibt Aufwand mit einem Prozessor.
Parallel Prefix ist O von N.
Und mit N durch Log-N Prozessoren müssen wir hier unten eben
einsetzen.
Die Anzahl der Prozessoren ist N durch Log-N.
Die Laufzeit wäre wie bisher O von Log-N.
Das, schlampig ausgerechnet, ergibt O von 1.
Das heißt, wir könnten im Prinzip diesen Algorithmus auch in O von 1
hinkriegen.
Wir müssen nur wieder entsprechend die Werte in Gruppen zusammenfassen
und dann in Gruppen abarbeiten lassen.
Aber das gucken wir uns nicht mehr an.
Das sieht nur noch ein bisschen hässlich aus.
Es reicht, wenn wir wissen, im Prinzip wäre es möglich, die Effizienz
zu steigern, und zwar deutlich zu steigern.
Ja, okay, soviel zu diesem Parallel Prefix.
Und als letztes Teilthema von heute gucken wir uns noch an, wie man
etwas, was eigentlich gar nicht so nach Parallelität aussieht, nämlich
Listen und Bäume, wie man damit auch parallel zurechtkommt.
Im Prinzip ist es ja schön, wenn man mit Arrays arbeitet oder Vektoren
oder so.
Da hat man ja immer gleich alles schön indiziert, weiß genau, wo
welches Element im Speicher liegt.
Für jedes ist ein Prozessor zuständig oder so.
Man kann sehr schön und ganz einfach Daten zu Prozessoren zuordnen.
Das sieht gar nicht mehr so einfach aus, wenn es um Listen geht.
Und Listen haben ja nun mal auch sehr schöne Eigenschaften, wie zum
Beispiel, dass man Sachen einfügen kann oder dranhängen kann, was viel
schneller geht als mit Arrays.
Oder Listen hintereinanderhängen, konkatenieren, geht auch wesentlich
schneller als Arrays.
Auch irgendein Element herausnehmen, das bedeutet ja einfach in der
Regel nur, einen Zeiger zu verbiegen.
Deswegen werden gerne solche Listen eben als irgendwelche verzeigerten
Objekte im Speicher angelegt.
Jedes Listen-Element ist irgendwo ein Objekt und ein Feld dieses
Objektes, ein Attribut ist ein Zeiger auf das nächste Objekt.
Und so haben wir halt diese Liste im Speicher stehen.
Wenn wir jetzt also zum Beispiel auf dieses Listen-Element hier
zugreifen wollen und wir haben hier irgendwo meinetwegen so einen
Anfangszeiger in das Erste hinein,
dann wie sollte man dann da hinkommen?
Es geht doch eigentlich nur, indem wir diese Verzeigerung verfolgen.
Das deutet eigentlich darauf hin, dass solche Listenverarbeitung gar
nicht richtig parallelisierbar ist.
Also es sieht aus, als wäre es sowas wie echt inhärent sequenziell,
man kann da nichts parallelisieren.
Um vom Ersten zum Letzten zu kommen, muss man durch N Verzeigerungen
durch.
Tja, ist es wirklich so?
Naja, also zunächst mal, bevor wir uns da ein paar Algorithmen dazu
überlegen, überlegen wir uns, wie wir das im Speicher anordnen.
Wenn es so ist, dass diese Elemente wirklich wild, willkürlich im
Speicher herumliegen und niemand weiß, wo sie tatsächlich sind, dann
ist es tatsächlich so, dass es irgendwie inhärent sequenziell ist, da
den Weg durch diese Dinger zu finden.
Aber es ist ja nicht nötig, dass wir die so willkürlich im Speicher
herumliegen lassen.
Was uns genügen würde, um einigermaßen gut parallel damit zurecht zu
kommen, ist, wenn wir wenigstens ein Feld haben, in dem die Zeiger auf
all diese Elemente drin stehen und dann dieses Feld quasi verzeigern.
Also statt, dass es so im Speicher wild herumliegt, haben wir ein
Feld, in dem ein Zeiger auf diese Pampa vorhanden ist, die irgendwo
sein kann, aber dieses Feld ist wenigstens in einem indizierbaren
Speicherbereich, wo wir sagen können, wir können das dritte
Feldelement, das vierte, das fünfte einfach ziemlich schnell sofort
finden und können das jeweils dem Prozessor, dem ersten, dem zweiten,
dem dritten usw.
zuordnen.
Und dann könnte jeder Prozessor gleichzeitig auf einen Speicherbereich
aus diesem Feld zugreifen und wo die eigentlichen Daten liegen, da
müsste man dann schon hinfahren, aber wenn man das eventuell gar nicht
braucht, diese eigentlichen Daten, sondern nur irgendwelche Reihen
folgen oder sowas, dann genügt uns das Feld.
Und in diesem Feld ist auch die Verzeigerung drin enthalten, also
diese Verzeigerung hier, was ist der Nachfolger von wem, das steht
auch hier drin.
Mit dieser Datenstruktur können wir jetzt tatsächlich loslegen und
parallele Sachen tun.
Was zum Beispiel gebraucht werden könnte, ist der sogenannte Rang
eines Listen-Elements.
Wobei Rang definiert ist in dem Fall, als wie weit vom Schwanz der
Liste ist es weg.
Das heißt, das letzte Stückchen von der Liste, das was hier mit 1
bezeichnet ist, das hätte den Rang 1.
Na gut, ob man jetzt hier mit 1 oder 0 anfängt zu zählen, ist wohl
auch Nebensache, aber so wie es halt hier steht, fangen wir mit 1 an
zu zählen, das heißt, es ist das erste oder letzte, je nachdem aus
welcher Richtung man zieht, es hat den Rang 1.
Dieses hier hat den Rang 2, das heißt, bis hier hin hängen 2 Listen
-Elemente dran, bis wir beim Null-Pointer angekommen sind und so
weiter, Rang 3, Rang 4, Rang 5.
Wenn wir wüssten, welches Listen-Element welchen Rang hat, dann
könnten wir sehr schnell auf das ITE-Element zugreifen, das ist ja
dann der Rang.
So etwas hätten wir manchmal gerne, die Liste ist dann trotzdem eine
Liste, aber um auf das 5.
oder 6.
zuzugreifen, müssen wir wissen, welcher ist das 5.
oder 6.
Also wäre der erste Schritt dazu, erstmal alle Ränge berechnen, für
jedes Element den Rang berechnen.
Natürlich hilft es nichts, wenn wir den Rang so berechnen würden,
parallel wie man es sequentiell machen würde, dass wir hier hinten
anfangen und dann zählen, dass wir sagen, der hier hat einen Null
-Pointer, also kriegt er Rang 1, dann fahren wir zurück, irgendwie
diese Verzeigerung rückwärts verfolgen, der kriegt den Rang 2, der
kriegt den Rang 3.
Erstens, was ist, wenn gar keine Rückwärtsverzeigerung da ist?
Und zweitens, selbst wenn sie da ist, dann müssen wir halt trotzdem
alles durchlaufen, also sparsam wäre das auch nicht.
Naja, wie könnte man loslegen?
Naja, eine Idee wäre,
dass wir versuchen, einen sequentiellen Algorithmus zu
parallelisieren, wobei der sequentielle dann so aussehen würde, wir
fahren an den Start der Liste, an den Anfang, und angenommen wir
wissen, dass die Liste N Elemente hat, dann setzen wir den Rang da auf
N und dann zählen wir einfach in einer Schleife den Rang runter, bis
er irgendwann unten angekommen ist, bei 1, und setzen auf dieses
aktuelle Listenelement, für den Rang des aktuellen Listenelements
diesen Wert R.
Verfolgen dann den Zeiger zum nächsten und so weiter, bis eben der
Zeiger auf 0 zeigt, also das ist dann dieser 0 hier.
Das ist natürlich sequentiell und geht in O von N, aber wo soll sich
da was parallelisieren lassen?
Lässt sich dieser Schritt hier, diese Schleife, das wäre das Einzige,
wo man sagen könnte, da lässt sich was parallelisieren, lässt sich das
irgendwie gleichzeitig machen für alle Listenelemente?
Naja, wohl nicht.
Wenn wir das nämlich einfach stupide übersetzen würden in einen
parallelen Algorithmus, dann würde das vielleicht so aussehen.
Wir haben hier nochmal so eine Liste mit Verzeigerung, das hier ist
also das letzte Element in der Liste, weil hier der Zeiger 0 ist, das
ist das vorletzte, und das Feld wäre dann zum Beispiel so
abgespeichert, dass wir sagen würden, in der ersten Zelle steht 4
drin, das heißt, der Nachfolger von Zelle 1 ist 4.
Das können wir hier sehen, wenn wir diesem Pfeil nachfahren, der
landet dann an der Stelle 4, A von 2 ist 1, das heißt, der Nachfolger
der zweiten Zelle ist die erste, das ist, wenn wir hier zurückfahren
würden, und A von 3 ist 7, geht also bis ganz nach hinten, A von 7 ist
dann 6, geht also 1 zurück.
Also sagen wir mal, wir haben so eine Liste, so wie hier mit 7
Elementen, die sind so in einem Feld abgespeichert, in dem Feld A von
1 steht 4 drin, in A von 2 steht 1 drin und so weiter.
Und gehen wir wieder davon aus, dass wir eine PRAM verwenden, also
dass zunächst mal einfach jeder Prozessor einen Speicherplatz
zugeordnet kriegt, der erste Prozessor kriegt A1 zugeordnet, der
andere A2 und so weiter.
Diesen Algorithmus, den wir vorhin hatten, wenn wir den jetzt für so
viele Prozessoren laufen lassen würden, würde der ungefähr so
aussehen, dass wir sagen, zunächst mal sind alle, oder zunächst mal,
es steht jetzt hier nicht drin, aber wir würden wohl so anfangen, dass
ein einziger Prozessor weiß, dass er Rang 1 hat, nämlich dann, wenn
sein Zeiger 0 ist.
Also jeder Prozessor guckt, ist mein Zeiger 0, falls A von I 0 ist und
es trifft nur für einen zu, nämlich in dem Fall hier für diesen
Prozessor Nr.
6, dann setze ich den Rang auf 1.
Der weiß, ich bin der Letzte, ich habe keinen Nachfolger, ich setze
meinen Rang auf 1.
Und dann lassen wir eine Schleife drehen.
Jeder Prozessor denkt sich nun,
also ich habe nichts zu tun, solange ich nicht weiß, was der Rang
meines Nachfolgers ist, also A von I wäre ja der Nachfolger des
Prozessors I, solange der auf 0 ist, also noch im initialisierten
Zustand ist, das ist das, was hier nicht stand, aber zunächst mal sind
die alle auf 0 initialisiert.
Also solange mein Nachfolger immer noch 0 drinstehen hat, weiß ich
nicht, was dem sein Rang ist, also kann ich meinen auch nicht
berechnen.
Dann drehen wir die Daumen solange.
Und irgendwann, wenn doch der Nachfolger A von I einen Rang hat, also
R von A von I was anderes als 0 wird, dann können wir sagen, oha,
jetzt kann ich meinen Rang auch berechnen, nämlich ich berechne meinen
Rang als 1 mehr als den Rang meines Nachfolgers.
Und das läuft natürlich auch O von N-Zeit.
Als erstes setzt der Prozessor 6 seinen Rang auf 1, die anderen haben
so lange gewartet, dann kommt plötzlich der Prozessor 7 zum Zug, oh,
mein Nachfolger hat einen Wert ungleich 0, also setze ich meinen auf
1.
Dann kommt Prozessor 3 zum Zug, der stellt nämlich fest, mein
Nachfolger Nummer 7 hat jetzt einen Rang 1, also kann ich meinen auf 2
setzen und so weiter.
Trotz Parallelität, die Prozessoren tun nichts und der Aufwand ist O
von N.
So also nicht.
Geht es vielleicht nicht doch irgendwie.
Was wäre denn, wenn wir nicht nur wüssten, was der Rang unseres
Nachbarn ist, sondern irgendwas anderes, von irgendeinem weit
Entfernten, von dem wir wissen, wie weit er ist.
Wäre das nicht hilfreich?
Also hier ist nochmal dieses gleiche Feld und jetzt die Frage, was
wäre, wenn wir außerdem noch die Information N von I hätten, jeder
Prozessor speichert sich N von I ab und in diesem N von I steht drin,
irgendein weit entfernter Nachfolger, von dem er weiß, wie weit er
entfernt ist, meine Dringen.
Also nicht der unmittelbare Nachfolger, sondern ein weiter weg
entfernt liegender.
Wenn wir jetzt, das sehen Sie gleich vielleicht auf den ersten Blick,
statt nichts zu tun, also Daumen zu drehen und zu warten, bis der
Nachfolger einen bestimmten Wert in seinem Rang drin stehen hat, wenn
wir stattdessen gucken, wie weit können wir denn noch in unsere
Zukunft gucken, wir sind ja Parallel Random Access Machines, also
können wir gucken, wenn ich bisher als entferntesten Nachfolger N von
I habe, dann gucke ich, was ist dessen entferntester Nachfolger, und
dann habe ich ja noch einen entfernteren Nachfolger.
Also im ersten Fall wäre vielleicht N von I nur der unmittelbare
Nachfolger, eine Iteration später würde in N von I der Nach-Nachfolger
stehen, also der mit zwei Entfernungen und noch eine Iteration später
der mit vier und dann der mit acht, also wir könnten in wenigen
Iterationen gleich ziemlich weite Entfernungen überbrücken.
Wie würde das aussehen, zum Beispiel so?
Das ist wieder das gleiche Beispiel.
Wir haben hier wieder das Feld A von I, zusätzlich legen wir das Feld
N von I an, also jeder Prozessor hat jetzt, das ist auch zuständig
wieder für ein N.
Ja, und dann geht es eben los.
Im ersten Schritt würden wir sagen, jeder hat seinen unmittelbaren
Nachfolger, also das A von I merkt er sich in N von I, da ist nichts
besonderes dabei, also es ist einfach nur übertragen.
Das wäre also Abstand 1.
Jeder merkt sich, wie weit kann ich in einem Schritt kommen.
Dann käme der nächste Schritt, wie weit kann ich weit kommen, wenn ich
mir angucke, wo mein Nachbar hinkommt.
Bei dem sechsten Prozessor, der kommt überhaupt nicht weiter, weil der
hat gar keinen Nachfolger, also ist für den Schluss.
Sein entferntester Nachfolger ist immer noch der Nullpointer, da geht
es nicht weiter.
Aber bei den anderen, zum Beispiel hier bei dem ersten, der Prozessor
1 sagt sich, mein bisher entferntester Nachfolger ist Nummer 4,
also guckt er nach, was ist N von 4, und N von 4 ist 3, das heißt
Prozessor 4 weiß, sein entferntester Nachfolger ist der Nummer 3.
Also merken wir uns hier, in Abstand 2 kann ich von 1 aus den Nummer 3
erreichen.
Also haben wir hier den Abstand 2 in dieser ganzen Ebene.
Entsprechend wird in N von 2 der Nachfolger des Nachfolgers von 2
reingeschrieben, also der Nachfolger von 1, der war 4.
Das ist jetzt nicht dieser hier, nicht diese 3, sondern das ist diese
4, die hier rüberkommt.
Also nicht das, sondern diese 4.
Bedenken Sie, dass das alles parallel abläuft, also alles was hier
passiert in einer Zeile geschieht parallel, das heißt der Prozessor 2
guckt sich nach, was steht in dem N von 1 drin, weil das sein
unmittelbarer Nachfolger ist, da steht 4 drin, also nimmt er sich die
4.
Sie können jetzt zwar sagen, da könnten ja Race Conditions entstehen,
was ist, wenn der erste Prozessor sein wird, aktualisiert hat, bevor
der zweite ihn gelesen hat.
Gut, dann nehmen wir eben für diesen Fall ein N und ein N' und dann
wird halt immer aus dem N gelesen und das N' reingeschrieben und
hinterher dann aktualisiert.
Das geht alles in O von 1, das macht die Sache nicht komplizierter.
Okay, was passiert zum Beispiel noch in dieser Ebene?
Hier zum Beispiel merkt sich dann der Prozessor 7, sein unmittelbarer
Nachfolger war Prozessor 6, dessen Nachfolger war der Nullpointer,
also weiß der Prozessor 7, in zwei Schritten bin ich beim Nullpointer
angekommen.
Da geht es nicht weiter, also geht es hier auch für 7 nicht mehr
weiter.
Und jetzt geht es weiter, jetzt merkt man, dass es plötzlich
interessant wird.
Zum Beispiel hier vorne hat sich dieser erste Prozessor gemerkt, mein
entferntester Nachbar war der Nummer 3, in Abstand 2.
Also gucken wir nach, bei 3, was ist N von 3?
Der hat sich gemerkt, sein entferntester Nachbar ist der Nummer 6,
auch im Abstand 2.
Also können wir in vier Schritten von 1 nach 6 kommen.
Das heißt, wir haben hier einen Abstand von 4.
Und der Prozessor 1 merkt sich, in vier Schritten komme ich zur 6, der
Prozessor 2 merkt sich analog, in vier Schritten komme ich zur 7.
Und die 3 und 4, die sind dann ja auch schon inzwischen beim
Nullpointer angekommen.
Und noch einen Schritt weiter, das wäre dann Abstand 8, so weit geht
es sowieso nicht bei dieser kleinen Liste, sind sowieso alle beim
Nullpointer angekommen.
Das heißt, wir müssen nur drei solche Rechenschritte durchführen, drei
Iterationen, bis jedes Listenelement bis zum Nullpointer durchgeguckt
hat.
Und das ist wesentlich weniger, als wenn wir hier jedes Einzelne
abarbeiten müssten.
Und zwar deswegen, weil sich der Abstand in jedem Schritt verdoppelt.
Diese Vorgehensweise heißt deswegen auch Verdopplungsmethode.
Und wenn wir die einsetzen, dann können wir plötzlich solche Sachen
wie einen Rang auch parallel schnell berechnen.
Gucken wir uns das mal an.
Hier ist nochmal das gleiche Feld, wie bisher auch.
Hier ist auch nochmal die Entwicklung dieses N, wie wir es bisher
hatten.
Genau das gleiche, das ist N von 1, N von 2, N von 3.
Und das ist wieder die Zeit.
Hier ist die Initialisierung.
Da wird zunächst mal der Rang überall auf Null gesetzt und das N wird
auf den unmittelbaren Nachfolger gesetzt.
Also das wird direkt einfach runterkopiert.
Die 6 kommt hier hin, die 0 kommt runter, die 2 kommt runter.
Das ist die Initialisierung, da wird noch gar nichts großartig
gerechnet.
Jetzt kommt der erste Schritt.
Wo kann ich mit Abstand...
Achso, ja genau, da wird das zunächst mal geändert.
Wenn ich hier jetzt weiß, wo ich mit Abstand 1 hinkomme, können wir
jetzt auch den Rang berechnen.
Also hier schon gleich nach der Initialisierung können wir den Rang
von Nummer 6 berechnen.
Der weiß nämlich, mein Nachfolger ist 0, also bin ich der Letzte, ich
kriege Rang 1.
Jetzt haben wir, nachdem wir den Abstand 1 hier in der Initialisierung
berechnet haben, kommt, meldet sich der Prozessor 7.
Der sagt sich, mein unmittelbarer Nachfolger ist 6.
Der hat als Rang schon eine 1 drinstehen.
Der kennt also seinen Rang schon.
Weil das mein Nachfolger mit Abstand 1 ist, brauche ich also nur 1
plus 2 berechnen.
Also ich nehme dessen Rang, addiere 1 und habe meinen Rang.
Dann kommt die nächste Ebene.
Hier vorne passiert zum Beispiel für den ersten Prozessor nicht viel.
Das ist wie vorhin, wie wir festgestellt haben, der kann seinen Rang
immer noch nicht setzen, da steht immer noch 0 drin.
Er hat inzwischen den entferntesten Nachfolger des entferntesten
Nachfolgers von der 3 festgestellt, das ist die 6.
Schreibt sich da die 6 rein, weiß nur, im Abstand 4 kann ich die 6
erreichen.
Mit 4 Schritten komme ich bis zur 6.
Aber hier zum Beispiel passiert was, bei dem A von 3.
Der sagt sich, in einem Schritt kann ich die 7 erreichen, in zwei
Schritten kann ich die 6 erreichen.
Und die 6 hat schon jetzt einen Rang drinstehen, nämlich die 1.
Zu dem Zeitpunkt hatte die 7 auch noch keinen Rang drinstehen, da war
auch noch eine 0 drin.
Deswegen konnte der dritte Prozessor seinen Wert auch nicht berechnen.
Aber jetzt, nachdem die Abstände für 2 berechnet wurden, weiß er, der
Prozessor Nummer 6 hat einen Rang festgestellt, nämlich 1.
Im Abstand 2 kann ich da hinkommen, also ist mein Rang 3.
An dieser Stelle, der Prozessor 4 macht es ähnlich, der stellt auch
fest, ich komme in zwei Schritten zu 7.
Da steht schon ein Rang drin, nämlich 2, also kann ich meinen Rang auf
2 plus 2 setzen, nämlich die 4.
Und in der nächsten Iteration werden dann halt die bekannten Ränge,
nicht plus 1, nicht plus 2, sondern plus 4 genommen, um dann diese
neuen Ränge zu berechnen.
Jetzt kommt zum Beispiel auch der erste Prozessor zum Zug.
Er stellt fest, mit Abstand 4 komme ich zu Nummer 6, der hat schon
Rang 1 drinstehen, also 1 plus 4 ist 5.
Der zweite Prozessor sagt sich, mit Abstand 4 komme ich zu 7, der hat
schon 2 drinstehen, also ist meins Nummer 6.
Und der letzte, der Nummer 5 sagt sich, mit Abstand 4 komme ich zu
Nummer 3, also 3 plus 4.
Der Rang ist hier bei 3 schon als 3 festgestellt, 3 plus 4 ist 7.
Ganz allgemein, so wie das Beispiel hier mit vielen Zahlen aussieht,
kann man es formulieren.
Der Abstand verdoppelt sich ja mit jeder Iteration D.
Das heißt, wenn wir D Runden drehen, dann ist der Abstand 2 hoch D.
Wenn der Abstand also irgendwann 2 hoch D ist und ein Element ist im
Abstand 2 hoch D zu erreichen, bei dem der Rang schon drinsteht und
der Rang dort ist R, dann kann sich der Prozessor sagen, dann ist mein
Rang eben 2 hoch D plus R.
Und wie lange dauert das?
Naja, das ist offensichtlich wesentlich schneller.
Da müssen wir nicht O von N machen, sondern, weil sich die Abstände ja
immer verdoppeln, maximal O von Log N tiefen.
Ja, gucken wir auch hier mal an, wie das mit Aufwand und Effizienz
aussieht, in dieser Verdopplungsmethode.
Also die Zeit ist O von Log N, weil der Abstand immer verdoppelt wird.
Effizienz, wir haben N Prozessoren, das steht hier unten drin.
Der Aufwand mit einem Prozessor ist einfach durch die ganze Liste
durchlaufen, also O von N.
Hier unten Log N, der Aufwand für N Prozessoren, das Ganze wieder
schlampig ausgewertet, kommt raus als Effizienz 1 durch Log N.
Scheint gar nicht mal so eine untypische Effizienz zu sein für
Parallelalgorithmen, haben wir jetzt schon öfters gesehen.
Ja, dann gucken wir mal, ob der Satz von Brent was hilft.
Als erstes die Anzahl der Schritte ausrechnen.
Wir haben Log N Ebenen, in jeder sind bis zu O von N Prozessoren
aktiv.
Zum Schluss nur noch wenige, viele scheiden schon am Anfang aus,
vielleicht im Schnitt N halbe, aber immer noch im O-Kalkül O von N Log
N.
So viele Schritte werden also durchgerechnet.
Wenn wir das in den Satz von Brent einsetzen, kriegen wir raus,
S ist N Log N, T ist Log N.
Also sagt der Satz von Brent, wir können auch in der Zeit Log N
auskommen und brauchen dazu nur N Prozessoren.
Dann sagen wir, wir haben sowieso nur N, also bringt es nicht.
Wir können also mit Hilfe dieses Satzes von Brent nicht sagen, ob es
einen schnelleren gibt.
Vielleicht ist auch noch festzuhalten, der Satz von Brent sagt nicht,
es gibt keinen schnelleren.
Der Satz von Brent sagt nur, wenn es einen Algorithmus gibt, wie oben,
der in Log N Zeit fertig wird mit N Prozessoren, dann gibt es auch
einen, der in der selben Zeit, also auch in Log N fertig wird, aber
nur S durch T Prozessoren braucht.
Er sagt nicht, dass es keinen anderen schnelleren gibt.
Das sagt er nicht.
Das ist eine ganz andere Geschichte.
Zumindest gibt er uns keinen Hinweis dafür, ob es sich nicht lohnt,
danach zu suchen, nach etwas Besserem.
Ja, und das Rechnermodell ist hier ein Exclusive Read, Exclusive
Write.
Es wird nie gleichzeitig gelesen oder geschrieben.
Von daher, ja, das ist eine relativ einfache Architektur.
So, somit können wir den nächsten Rang berechnen.
Eigentlich ist es jetzt klar, gut, Listen in Arrays umwandeln ist ja
schon mal okay.
Jetzt setzen wir noch einen drauf und gucken uns an, was ist mit
Bäumen?
Dass wir eine Liste als ein Array irgendwie ansehen können, das ist ja
noch vorstellbar.
Aber ein Baum, das ist ja schon gar nicht mehr Array-mäßig.
Das ist ja schon was ganz Kompliziertes.
Lässt sich da auch parallel sinnvoll arbeiten.
Also was wir zum Beispiel gerne hätten, ist, dass man in diesem Baum
auch, ähnlich wie bei einer Liste, einen Rang berechnet.
Wobei halt hier Rang, naja, was anderes wäre.
Aber sagen wir einfach mal, was wir gerne hätten, ist eben eine
Indizierung der Knoten.
Sowas wie 1, 2, 3, 4, 5.
Wie sie zum Beispiel eben so ein Tiefensuche-Algorithmus finden würde.
Da gibt es natürlich andere Möglichkeiten.
Es könnte natürlich auch sein, dass er was anderes findet wie 1, 2, 3,
4, 5.
Auch das wäre natürlich möglich.
Also irgend so eine Tiefensuchennummerierung, die hätten wir gerne.
Ja, okay.
Einen Baum können wir schlecht als eine Liste, als ein Array im
Speicher ablegen.
Aber was wir machen könnten, ist, so eine Adjacenzliste mit
Verzeigerungen anlegen.
Also mehrere Listen quasi.
Dann ließe sich vielleicht hier auch parallel ganz gut zurecht kommen.
Gut, nehmen wir mal diesen Baum, den wir eben hatten.
Das ist dieser Baum 1.
Und wir haben hier auch wieder diese Kanten drin.
Nur haben wir jetzt jede Kante in beide Richtungen reingeschrieben.
Statt eine, so wie sie hier vorhin war, ohne irgendwelche Richtungen,
haben wir jetzt halt statt ungerichtete Kanten zwei gerichtete, eine
vorwärts, eine rückwärts gerichtet.
Die rückwärts gerichteten sind mit Strich bezeichnet und die vorwärts
gerichteten ohne Strich bezeichnet.
Also wir gehen mal davon aus, dass wir die Wurzel des Baumes kennen.
Dann würde zum Beispiel so eine Adjacenzliste im Speicher so aussehen.
Von Knoten 1 aus kommt man über die Kante 1,2, das ist die Kante A,
weg.
Außerdem kommt man von dem Knoten 1 über die Kante 1,5 weg, das ist
die Kante B.
Also das hier ist einfach die Beschreibung des Knotens 1.
Dann kommt die Beschreibung des Knotens 2 drunter.
Da steht drin, wir haben die Kante 2,3, die geht von 2 weg, das ist
die Kante C.
Dann haben wir die Kante 2,1, das ist die Kante A Strich.
Und die Kante 2,4, das ist die, die mit D bezeichnet ist.
Also mit anderen Worten, hier haben wir eine verzeigerte Liste, die
uns sagt, also wir haben für den Knoten 2,3 Kanten, die davon abgehen,
die Kante C, A Strich und D, nämlich zum Knoten 3, zum Knoten 1 und
zum Knoten 4.
Damit der Algorithmus hinterher keine Schwierigkeiten hat, können wir
uns außerdem noch merken, welche Kanten die Rückwärtskanten einer
anderen sind.
Wir wissen zwar jetzt hier noch nicht, was vorwärts und was rückwärts
ist, aber wir wissen, dass 1,2 das andere ist von 2,1 und deswegen
könnte man hier also diese beiden da noch verbinden mit einem Zeiger,
sodass man, wenn man weiß, wo die Kante A Strich ist, dass man schnell
auf die Kante A zugreifen kann.
So viel aber nur jetzt vorneweg, damit man hinterher nicht unnötig im
Speicher rumsuchen muss.
So, nehmen wir an, der Baum liegt so im Speicher, ist ja ein Graph,
also ist so im Speicher abgelegt, können wir jetzt eine Nummerierung
der Knoten parallel schnell berechnen.
Also zum Beispiel wäre eine Lösung, die uns der Algorithmus liefern
soll, eine Folge der Zahlen 1,2,4,3,5.
So könnte ein Tiefensuchalgorithmus, also Depth First Search, die
Knoten finden.
1, dann 2, dann 4, dann die 3 und dann die 5.
Also so ungefähr, wie es hier grob angedeutet ist.
Ja, wie könnte man so ein Ding jetzt finden?
Erste Möglichkeit ist, wir ordnen alle Kanten in Form eines eulischen
Pfades an.
Dadurch, dass wir jetzt diese Kanten alle jeweils mit einmal vorwärts,
einmal rückwärts gemacht haben, können wir garantieren, dass hier ein
eulischer Pfade existiert.
Also können wir ganz einfach von der Wurzel aus losmarschieren.
Dann zum Beispiel eben die Kante A runterlaufen, dann die Kante D
runterlaufen, D-strich, C, C-strich, A-strich, B, B-strich.
Das würde dann ungefähr so ablaufen, wie es hier auch dargestellt ist.
Das wäre ein eulischer Pfade.
Was natürlich die Frage ist, wie finden wir jetzt so einen eulischen
Pfade?
Also zum Beispiel wollen wir ja nicht erstmal A runterlaufen und dann
von hier aus könnte man ja auch gleich wieder A-strich wählen, wieder
hochgehen.
Wenn wir das tun würden, dann würden wir keinen eulischen Pfade
finden.
Wie können wir also garantieren, dass einer rauskommt?
Hier steht nochmal nichts Neues da, das ist der gleiche Baum, die
gleiche Kantenreihenfolge.
Wir können das ganz einfach so garantieren, indem wir beim
Wurzelknoten anfangen.
Und jetzt immer uns dann halt fragen, da können wir ja mit irgendeiner
Kante loslegen, mit einer Kante IJ.
Und wenn wir eine Kante IJ abgelaufen haben, also die erste sei zum
Beispiel A, dann müssen wir uns immer fragen, welche nehmen wir als
nächstes.
Und um sicherzustellen, dass die nächste nicht die Rückwärtskante ist,
wieder zurück, sagen wir einfach, die nächste Kante, nachdem wir IJ
gemacht haben, ist einfach das, was in dieser Adjacenzliste, also
nachfolgerbezüglich Adjacenzliste,
was ist in dieser Adjacenzliste hinter JI, also hinter diesem
Rückwärtszeiger.
Wenn wir irgendwo von I nach J gehen, dann gibt es ja dort auch einen
JI, rückwärts, das gibt es ja auch, das ist immer drin.
Und dann nehmen wir einfach den Nachfolger in der Adjacenzliste,
sodass wir garantiert nicht den Rückwärtsweg verfolgen.
Falls es keinen Nachfolger gibt, dann nehmen wir halt eben diese erste
Kante, die von J abgeht, dann haben wir auch eine, die nicht der
Rückwärtszeiger ist, oder wenn es die einzige ist, die davon abgeht,
dann halt eben den Rückwärtszeiger.
Dann gehen wir wieder zurück.
Mit dieser Idee können wir also tatsächlich so einen Eulerschen Pfad
erzeugen, der sieht dann so aus.
Wir fangen bei Knoten A an.
Die Knoten haben jetzt auch Namen, nicht bei Knoten A, sondern bei
Knoten 1.
Das sind jetzt die Namen der Knoten, nicht unbedingt die Reihenfolge.
Also wir fangen bei dem Knoten A 1 an, gehen über die Kante A, dann
nehmen wir dort, was in Knoten 2 als Nachfolgekante von A' drin steht,
da steht halt zufällig D drin, also geht es weiter nach D, über D nach
4, da gibt es nichts mehr außer D', also wieder zurück über D' nach 2,
von dort aus bleibt noch C nach 3, dann wieder zurück nach 2, dann
kommt jetzt endgültig der A' dran und so weiter, bis wir zurück
angekommen sind bei dem Knoten 1.
Das gibt dann diesen Eulerschen Pfad, der über alle Kanten drüber
läuft.
Jetzt haben wir keinen Baum mehr, sondern jetzt haben wir eine Liste.
Und jetzt können wir das, was wir vorhin mit Listen gemacht haben,
nämlich den Rang berechnen, können wir jetzt auf dieser Liste machen.
Also wir haben den Baum quasi in eine Liste umgewandelt und gucken
jetzt, wie wir damit auf dieser Liste den Rang berechnen.
Rang berechnen haben wir ja schon kennengelernt.
Wir fangen also mit dem Wurzelknoten an und was dann eben als Rang
herauskommt, der Knoten 5 hat hier den Rang 1, 2, 3, 4, 5, 6, 7, 8,
bis zum Schluss eben der Rang 8 herauskommt in dieser Liste.
Da stehen nochmal die Kanten dran, so wie sie im Eulerschen Pfad
gefunden wurden.
Und so wie wir den konstruiert haben, diesen Eulerschen Pfad, haben
wir ja garantiert, dass immer die Rückwärtskante als letztes verfolgt
wird.
Das heißt, der Rang einer Vorwärtskante ist immer größer als der der
zugehörigen Rückwärtskante.
Und jetzt können wir damit also auch ganz einfach erkennen, welche ist
eine Vorwärts- und welche ist eine Rückwärtskante.
Wenn wir also hier irgendwo von 1 nach 2 haben und von 2 nach 1, also
das da, dann wissen wir, dieses hier muss die Vorwärts gewesen sein
und das muss die Rückwärts gewesen sein, weil die Vorwärts ja einen
größeren Rang haben muss.
Jetzt fehlt noch diese Indizierung, ist nicht weiter aufwendig.
Alles was wir wissen wollen für die Indizierung ist ja, wie viel
würden wir noch absteigen, wenn wir den Depth-First-Search machen.
Das heißt, wie viele Vorwärtskanten würden wir noch verfolgen.
Nennen wir also F von IJ einfach die Funktion, die angibt, wie viele
Vorwärtskanten gibt es nach der Kante IJ.
Also zum Beispiel für die Kante A, die selbst eine Vorwärtskante ist.
Danach gibt es noch eine, diese hier, noch eine hier und noch eine
hier.
Also noch drei Vorwärtskanten, deswegen ist F von A 3.
Und die Indizierung von so einem Knoten ist jetzt einfach quasi das
Inverse der Anzahl der Vorwärtskanten, die noch fehlen.
Also N-Knoten haben wir insgesamt, also an irgendeiner Stelle,
irgendeiner von denen hat 0 Vorwärtskanten, die noch kommen.
Für den kommt dann als Nummerierung 5 raus, als Indizierung.
Einer hat noch 5 Nachfolger, für den kommt halt 0 raus.
Naja, 4 Nachfolger, für den kommt halt 1 raus.
Das sehen wir, wenn wir hier unten tatsächlich welche einsetzen.
Zum Beispiel eben, was ist die Indizierung vom Knoten 2?
Also gucken wir uns den Knoten 2 hier an.
Wie viele Knoten, wie viele Vorwärtskanten gehen noch ab?
Ne, hier 2.
Wie viele Knoten gehen noch ab nach der Kante IJ, also nach der Kante
A?
F von A ist 3, also 5 minus F von A ergibt 2.
Entsprechend hinten vielleicht noch, als ein Beispiel noch diesen
Fünfer.
Das wäre hier, den erreichen wir über B.
Wie viele Vorwärtskanten kommen noch nach B?
Keine mehr, also von hier aus geht es nicht mehr vorwärts weiter.
Das heißt, F von B ist 0 und 5 minus F von B, 5 minus 0 ist 5.
Das heißt, dieser Knoten kriegt den Rang 5.
Wir können genauso wie den Rang auch dieses F mithilfe der
Verdopplungsmethode berechnen, also in logarithmischer Zeit.
Und haben auf die Art jetzt also die Indizes für jeden Knoten in
diesem Baum berechnet.
Das ist das, was rauskommt.
Vielleicht nur noch so eine kleine Bemerkung, was nebenbei außerdem
noch mit diesem F interessant ist.
Wenn man F von IJ einer Kante, also wie viele nachfolgende
Vorwärtskanten gibt es noch, wenn man da von F von JI abzieht, dann
gibt es genau die Anzahl der Knoten, die da drunter hängen.
Also wenn wir z.B.
für den Wert 2 gucken, wie viele Vorwärtskanten kommen danach, minus
wie viele Vorwärtskanten waren oben drüber und wie viele da drunter.
Wenn man davon den Unterschied berechnet, dann gibt es genau die
Anzahl der Knoten, die da unten dranhängen.
Also K von 2 ist F von A, die 3, minus F von A Strich.
Und dann auch z.B.
vor allem mit der Verdopplungsmethode Indizes für die einzelnen
Elemente generiert und dann damit weiterrechnet.
Nächste Woche machen wir nochmal weiter mit der Parallelität.
Nachher ist Vorlesung und der Mayer wird auch noch etwas zur Klausur
sagen mit Anmeldung usw.
Bis Montag dann.