Schönen guten Tag, ich begrüße Sie zur weiteren Vorlesung über
effiziente Algorithmen.
Heute ist der Tag, wo Sie das erste Mal wieder Aufgaben abgeben.
Die nächsten Aufgaben werden ausgeteilt, also die nächste Folge ist
verfügbar.
Ich glaube, das machen wir nur online, nicht mehr per Papier, sehr
gut, umweltfreundlicher.
Und letztes Mal haben wir uns angeguckt, noch das Ende von den
Berechnungsmodellen.
Sie erinnern sich, dass wir dort einiges angeschaut hatten, gar nicht
mehr diese initialen Dinge.
Ich habe Ihnen letztes Mal einiges erzählt, genau, dann über die
verschiedenen Klassifikationen von Algorithmen.
Wir hatten sequenzielle Algorithmen nochmal angeschaut, was uns da
eigentlich interessiert an Aufwand.
Parallele Algorithmen, kurz diese Baum, das hatte ich Ihnen alles
schon erzählt.
Dann diese Vielfalt paralleler Berechnungen, Verbindungsstrukturen,
Hardware -Algorithmen.
Das ist das, wo wir letztes Mal angefangen haben.
Da habe ich Ihnen nochmal was erzählt über die Darstellung der Bäume.
Wir haben uns die Ripple-Carry-Adder-Matrix-Multiplikation angeschaut.
Ich habe Ihnen einiges erzählt dazu, dass man, was hier eigentlich
sehr schön zu sehen ist, obwohl das gar nicht so gedacht ist, auf
dieser Folge sind ja die ganzen Animationen überlagert.
Deswegen sieht man hier eigentlich gar nicht so richtig was.
Aber was man eigentlich sehen kann, ist, dass man anstelle dieser...
Wenn ich hier einmal kurz auf die Animationen gehe, wenn man hier ja
nur sieht, wie die hier durchwandern, dann sieht das so leer aus,
jedes dritte Feld ist gefüllt.
Wenn ich da wieder rausgehe, sieht man eben, man kann das auch ganz
dicht machen und dann eben drei Berechnungen gleichzeitig machen, was
ein bisschen ungewöhnlich ist.
Aber man kann das sehr effektiv nutzen.
Man kann das zum Beispiel auch dafür sehr effektiv nutzen, wenn Sie
sich vorstellen, Sie machen ein größeres Produkt von Matrizen und Sie
haben nur eine relativ kleine Möglichkeit zur Verfügung, das
tatsächlich durchzuführen.
Also das heißt, die Dimensionen Ihrer Hardware sind kleiner.
Dann müssen Sie eventuell ein größeres Produkt machen über eine Folge
von Matrixmultiplikationen und Additionen.
Also Sie müssen diese Skalarprodukte irgendwie aufteilen.
Und dieses Aufteilen und nacheinander Ausführen aus so einer Hardware,
das kann man dann ganz gut so machen, dass man diese Möglichkeiten der
verschränkten Ausführung, also das Pipelining, Pipelining Grad 3
immerhin, dass man den hier nutzen kann, um dann wirklich jede Zelle
des Feldes effektiv auszunutzen für eine größere Berechnung, die
überlagert ist gegenüber so einer einzelnen Matrixmultiplikation.
Also wenn das nur ein Bestandteil ist von einer größeren Menge von
Matrixmultiplikationen und es gibt eine Vielfalt solcher Szenarien, wo
man das machen könnte, wäre auch ein Thema, übrigens ein ganz gutes
Thema für die Übungen, diese Ideen, wie man solche Hardware-Bausteine
einsetzt, als Bausteine in einer größeren überlagerten Berechnung.
Das ist etwas, was man auf diesem Bild eigentlich gar nicht
beabsichtigt, aber vielleicht ganz gut sieht, dass man das auch schön
alles ganz dicht machen kann mit Daten, die dort rein und raus
strömen.
Dann habe ich Ihnen was erzählt zur Analyse des Berechnungsaufwandes,
dass man eben hier bei Parallelen insbesondere Zeitgewinn, also
Parallelitätsgrad, Zeitgewinn, Effizienz anguckt, das sind die
wesentlichen beiden Dinge, die uns bei parallelen Algorithmen
interessieren.
Dann haben wir noch kurz verteilte Algorithmen angeschaut und dann
noch das Thema Energieaufwand und das war es dann auch schon in diesem
Kapitel und wir sind dann gegangen zu dem nächsten Kapitel über
algebraische Probleme, wo ich hier erstmal noch das Bild wieder
kleiner machen muss, damit wir das auch sehen können.
Das waren die algebraischen Probleme, wo wir zunächst mal uns die
Matrix -Modifikationen vorgenommen haben, die wir schon ein paar Mal
vorher gesehen haben, jetzt nochmal intensiver, zunächst mal
Informationen darüber, wie kann ich die eigentlich als Datenstruktur
darstellen mit verschiedenen Varianten.
Dann haben wir uns angeguckt, jetzt konkret das Problem volle Matrizen
zu multiplizieren und Standardansatz hat halt diese n hoch 3
Operationen im Großen und Ganzen, also Modifikationen plus gleiche
Größenordnung Additionen.
Dann das Problem der Zugriff auf Matrixkomponenten, dessen man sich
bewusst sein muss, wenn man eben einfach ein zweidimensionales Feld
nimmt als Darstellung, dass man dann intern immer noch Additionen,
Modifikationen noch dazurechnen muss, d.h.
den Aufwand, wenn man den reduzieren möchte, muss man eine explizite
Indexkalkulation machen, indem man dann eben als Datenstruktur ein
eindimensionales Feld wählt und die halt dort entsprechend zeilenweise
oder spaltenweise ablegt und das dann ausnutzen kann bei einer
Optimierung des Algorithmus, was wir aber hier nicht im Weiteren
gemacht haben, nur als Hinweis, dass man sowas machen könnte, um noch
konkret ein bisschen konstanten Faktor Zeit zu sparen.
Dann habe ich Ihnen dieses Vinograd-Verfahren vorgestellt, wo das
Interessante war im Wesentlichen, dass man über eine völlig andere
Darstellung des Skalarproduktes auf einmal eine Möglichkeit hat, Zeit
zu sparen, obwohl es zunächst gar nicht so aussieht.
Und das Wesentliche war dabei, dass man Abhängigkeiten von den
einzelnen Indexkomponenten, also i und j, dass man da Teile der
Berechnung identifizieren konnte, die man vorziehen konnte, nur von i
abhängig, nur von j abhängig, bei einem Skalarprodukt, wo man c, i, j
berechnen möchte.
Und dadurch dann durch die nicht-naive Auswertung in der Lage war,
tatsächlich zumindest einen konstanten Faktor Multiplikation zu
sparen.
Und wenn man dann noch annimmt, ich habe eine deutlich höhere
Berechnungszeit für Multiplikation als für Addition, kommt man
tatsächlich zu Vorteilen für dieses Verfahren.
Aber das Ganze ist eben nur ein Vorteil für einen konstanten Faktor.
Kurze Randbemerkung dazu nochmal, es gibt andere Probleme.
Meinetwegen die Berechnung der Fibonacci-Folge.
Ein typisches Beispiel, wenn Sie Fibonacci-Elemente, Sie wollen das
ente Fibonacci-Element ausrechnen, dann können Sie das über eine
rekursive Darstellung definieren.
Klassische Definition einer Fibonacci-Folge.
Und über diese rekursive Darstellung, wenn Sie die einfach so
programmieren, kommen Sie auf exponentiellen Zeitaufwand, wenn Sie
sequenziell, naiv, rekursiv darstellen.
Wenn Sie dann ein bisschen mehr überlegen, kommen Sie auf linearen
Zeitaufwand, wenn Sie das nicht rekursiv, sondern iterativ machen.
Bisschen überlegen nur, Ablauf etwas verändert.
Wenn Sie noch mehr überlegen und die Formel verändern, mit der Sie die
Fibonacci -Zahlen berechnen, indem Sie einfach sich angucken, was
passiert da eigentlich, machen Sie in die Weide einen Konker-Ansatz
dafür und kommen auf einmal auf logarithmische Zeit.
Einfach nur durch Verändern der Art, wie Sie die Formel darstellen für
die Berechnung einer Fibonacci-Zahl.
Also ohne, dass Sie irgendwie Parallelrechner einsetzen, einfach nur
die Art, wie Sie die Berechnungsformel verändern, führt Sie zunächst
mal von exponentiell auf linear, und wenn Sie dann ein bisschen mehr
in die hineinstecken, sogar auf logarithmische Zeit.
Und das ist etwas, worüber man sich klar sein muss, die Art, wie ich
ein Problem formuliere, ist entscheidend dafür, wie ich tatsächlich in
der Lage bin, dieses Problem zu lösen, eine Berechnung durchzuführen.
Manchmal muss man wirklich etwas ganz anderes darstellen, um dann
tatsächlich die Berechnung effizient zu machen.
Das ist ein bisschen dann Intuition, aber auch Fähigkeit, einfach
Formeln zu manipulieren.
Da muss man einfach ein bisschen damit umgehen können, muss einfach
Ideen haben, wie man die Gesetze der Art Mething anders ausnutzen
kann.
Dafür gibt es viele Beispiele von solchen Möglichkeiten.
Hier jetzt im Zusammenhang mit der Matrix-Modifikation nur ein kleiner
Faktor, eben nur unter der Annahme, dass Modifikationen von Zahlen
etwas länger dauern.
Aber das hatte ich Ihnen ja dargestellt.
Dann kommen wir jetzt zur ersten neuen Folie, nämlich nicht hotel.de,
sondern die Weide und Conquer-Ansatz.
Wir wollen uns anschauen, habe ich denn Möglichkeiten, tatsächlich
asymptotisch einen Zeitgewinn zu erzielen, indem ich die Darstellung
meines Problems etwas verändere.
Auch wieder ein anderer Ansatz, nicht klassisch naiv die
Skalarprodukte berechnet für die einzelnen Elemente, sondern ich
schaue mir das ein bisschen genauer an.
Und die Idee, die Herr Strassen, deutscher Wissenschaftler, der in
Frankfurt Lehrstuhlern hatte, schon vor langer Zeit hatte, 69-70, die
Weide und Conquer-Ansatz zu machen.
Die Weide und Conquer ist ja etwas, was wir in der Informatik überall
einsetzen.
Ist ja ganz einfach, wir teilen ein Problem auf und lösen dann die
Teilprobleme und setzen die Lösungen anschließend wieder zusammen.
Die Idee kennen Sie, das ist ja, nur nochmal hier angedeutet, ein
großes Problem.
Den Informatikern sind große Probleme zu schwer, den Operations
-Researchleuten auch.
Und dann machen wir eine Aufteilung in Teilprobleme und machen das
Ganze rekursiv.
Und lösen dann hier unten die verschiedenen Teilprobleme und können
die entsprechend wieder zusammenbauen zu Lösungen des Ausgangsproblems
sukzessive.
Und obwohl das nachher eine komplexe Struktur aussieht, kann man auf
die Art und Weise viele Probleme recht günstig lösen.
Und das ist jetzt auch die Idee, die hier dahinter steckt.
Nur wie kann man bei einer Matrix-Multiplikation etwas mit den Weide
und Conquer machen?
Auch da kann man ganz allgemein drüber nachdenken und überlegen, was
könnte man da eigentlich alles machen.
Strassen hatte nun folgende Idee.
Der hat gesagt, er nimmt an, ich habe einen Algorithmus zur Verfügung,
den nennt er Groß-K, für K für Konstant, also konstante Größe.
Der ist in der Lage, K-Kreuz-K-Matrizen zu multiplizieren.
Ja, so meinetwegen 7x7, 17x17 oder auch 2x2-Matrizen.
Zunächst mal aber ist der Ansatz unabhängig davon, welche Größe das K
hat.
Ich nehme an, ich habe eine konstante Größe, K-Kreuz-K-Matrizen, die
kann ich mit einem bestimmten Aufwand multiplizieren.
Das ist meine Basis.
Ich nehme irgendeinen Algorithmus her.
Und das muss einmal ein Algorithmus sein, der die Kommutativität der
Multiplikation nicht ausnutzt.
Damit fallen sofort ein paar Algorithmen weg.
Leider auch, wirklich sehr sehr leider, der Algorithmus von Winograd.
Ich werde später noch sehen, warum das so schade ist, dass wir den
nicht nutzen können.
Warum kann man den nicht nehmen?
Ich zeige Ihnen das hier.
Das hier ist also der Algorithmus oder die Idee von Strassen.
Strassen sagt, ich habe eine beliebige Matrix, eine n-Kreuz-n-Matrix
oder eine, ich nehme mal an, dass das n eine Potenz von K ist.
Ich habe also diese Konstante, für die ich weiß, K-Kreuz-K-Matrizen
kann ich multiplizieren mit irgendeinem Verfahren.
Und das führe ich die Multiplikation aller anderen Matrizen darauf
zurück, auf dieses Verfahren K-Kreuz-K-Matrizen zu multiplizieren.
Indem ich einfach eine beliebige Matrix, also hier habe ich eigentlich
insgesamt n und hier habe ich auch n, die stelle ich einfach da als K
-Kreuz -K-Matrix.
Und da drin sind jetzt die einzelnen Komponenten nicht Skalare,
irgendwelche Zahlen, sondern Teilmatrizen.
So, und jetzt habe ich hier das Produkt zweier K-Kreuz-K-Matrizen, das
ich ausrechnen soll, kommt eine K-Kreuz-K-Matrix raus und die
Komponenten sind halt Teilmatrizen.
Das heißt, jetzt muss ich hier jeweils so ein C-I-K berechnen, das ist
eben ganz normal wie vorher auch, unsere Summe A-I-K mal B-K-J, K
gleich eins... nee, das passt jetzt nicht.
K passt jetzt nicht, das kann ich nicht nehmen.
Nehmen wir hier mal, statt K nehmen wir hier einfach ein L.
So, I-L, B-L-J und L gleich eins bis K.
Das ist jetzt ein einfaches Skalarprodukt und wie das gemacht wird,
das ist in dem Algorithmus Groß-K versteckt.
Der macht das irgendwie.
Jetzt sehen Sie, wenn ich jetzt diese K-Kreuz-K-Matrizen nach dem
Verfahren K multipliziere, dann muss ich mir darüber im Klaren sein,
ich multipliziere und addiere jetzt nicht mehr Zahlen, sondern ich
multipliziere und addiere Matrizen.
Und in dem Augenblick ist natürlich das wichtig zu wissen, es ist
keineswegs für Matrizen A mal B häufig ungleich B mal A.
Bei Matrizen gilt halt nicht die Kommutativität, wie sie bei Zahlen
gilt.
Und deswegen darf dieses Verfahren Groß-K die Kommutativität der
Multiplikation nicht ausnutzen.
Bei dem Vinograd-Verfahren war das so.
Diese Veränderung dieser Skalarproduktformel hat das gerade
ausgenutzt, dass man dort Multiplikationen in unterschiedlichen
Reihenfolgen machen konnte.
Das war da also wichtig, können wir hier leider nicht ausnutzen.
Warum leider, das werden Sie gleich noch sehen.
Also das ist das Verfahren von Straßen S für beliebige Matrizen, ich
mache diese Aufteilung.
Und ich multipliziere jetzt hier drin diese Teilmatrizen nach dem
Verfahren K.
Jetzt kommen da drin natürlich, das sieht man ja hier, da kommen ja
Multiplikationen von Matrizen vor.
AIL mal BLJ.
Das sind zwei Matrizen, die multipliziert werden.
Wie multipliziere ich denn zwei Matrizen, was für Matrizen sind das
denn überhaupt?
Diese Matrizen sind jetzt N durch K kreuz N durch K Matrizen.
Naja, da weiß ich zwar nicht, das kann sein, dass das größer ist als
K.
Dann mache ich das rekursiv nach meinem Verfahren, das ist genau
dieser Divide-and-Conquer-Schritt hier.
Ich habe also einmal aufgeteilt, wie teile ich hier eigentlich auf?
Ich sage, ich mache ein Produkt von K kreuz K Matrizen, da drin
tauchen Additionen auf von Matrizen, das ist ja kein Problem.
Also Matrizen addieren, da wissen wir, wie das geht, muss ich die
einzelnen Komponenten addieren, das können wir ganz einfach machen.
Matrizen multiplizieren, wissen wir nicht, da brauchen wir diesen
Divide -and-Conquer-Ansatz.
Das heißt, für jede auftretende Multiplikation in diesem K kreuz K
-Verfahren muss ich hier eine Aufteilung machen.
Nehmen wir mal an, hier steht M von K Multiplikationen in dem
Verfahren Groß K.
Das heißt, ich habe hier ein Verzweigungsgrad von M von K.
So viele Multiplikationen, wie ich ausführe, so viele Teilprobleme
bekomme ich.
Jede Multiplikation, die hier in dieser Summe auftaucht, die muss
nicht in dieser Art in dem Verfahren K vorkommen.
Wir wissen, dass man solche Skalarprodukte auch anders hinbekommen
kann.
Aber jede Multiplikation, die tatsächlich auftaucht, die muss ich
rekursiv ausführen.
Also wieder aufteilen und auch hier wieder für jede Multiplikation,
also Verzweigungsgrad ist auch da wieder M von K.
Muss ich die Multiplikationen entsprechend machen, bis ich irgendwann
auf einer Größe bin, die nicht mehr größer als K ist.
Und dann kann ich die nach irgendeinem Verfahren oder eben nach dem
Verfahren K auch machen.
Wenn ich annehme, dass N gleich K hoch R ist, dann ist am Ende
irgendwann mal das N durch K gleich K.
Und dann bin ich damit fertig.
Und dann habe ich die multipliziert und kann dann rekursiv nach oben
die ganzen Ergebnisse hochreichen.
So, das ist der ganz einfache Ansatz.
Typischer Divide-and-Conquer-Ansatz.
Das Vehikel für die Aufteilung ist dieses Verfahren Groß K.
Und ich habe also jetzt hier drin eine Reihe von Multiplikationen zu
machen in meinem Verfahren Groß K.
Das ist also hier dieses klein m von K, das ist die Anzahl der
Multiplikationen in dem Verfahren Groß K.
Die Anzahl der Additionen nenne ich klein a von K.
Und was mich am Ende interessiert, ist natürlich, wie viele
Multiplikationen werden denn in meinem großen Verfahren S hier, wie
viele Multiplikationen werden denn in dem gesamten Verfahren
ausgeführt.
Beziehungsweise wie viele Additionen.
Und natürlich wissen wir, wir sind ja interessiert an der
Ausführungszeit für unseren Algorithmus, der hier von Strassen
formuliert worden ist, für n-Kreuz-n-Matrizen.
Und wir wissen, das ist ein algebraisches Problem.
Die Rechenzeit hängt ab im Wesentlichen von den arithmetischen
Operationen.
Wir sagen, das ist in der Größenordnung von der Summe der Anzahl der
Additionen und der Anzahl der Multiplikationen.
Damit haben wir hier, das habe ich gestern Abend noch dazu gefügt,
weil ich denke, das ist sinnvoll, das richtig in schöner Schrift zu
haben, das muss ich nicht mit Handschrift reinschreiben.
Also das ist wesentlich sich klar zu machen.
Wir schauen uns jetzt die Anzahl der Multiplikationen und der
Additionen an.
Und das gibt uns dann einen Hinweis oder sagt uns dann, wie groß
asymptotisch die Anzahl der arithmetischen Operationen ist und damit
die Rechenzeit ist für dieses Verfahren.
Und das müssen wir nun genauer machen.
So, jetzt nochmal ein Versuch.
Wir waren bei der Analyse so weit gekommen, dass wir gesehen haben,
dieser Ausdruck ist richtig und jetzt versuchen wir, den abzuschätzen,
das Wachstum.
Und dazu nehmen wir folgendes an.
Wir nehmen an, dass die Anzahl der Multiplikationen, die man braucht,
größer ist als die Anzahl der Elemente, die bei der
Matrixmultiplikation berechnet werden müssen.
Also, k² Einzelelemente müssen berechnet werden, wenn Sie ein k-Kreuz
-k -Matrix-Produkt berechnen.
Wir nehmen an, dass Sie für irgendein c größer 0, also k² plus c
Multiplikationen brauchen.
Also mehr als eine Multiplikation pro Skalarprodukt.
Die Annahme ist sicherlich nicht falsch.
Wir brauchen das, weil wir ansonsten in der Analyse durch 0 dividieren
könnten an einer Stelle.
Deswegen brauche ich diese Annahme.
Also das k² ist gleich m von k minus c.
Wir werden diese Ersetzung gleich machen.
Nämlich hier haben wir die Summe, das war der Ausdruck hier oben.
Und diesen Ausdruck formen wir ein bisschen um.
Das ist m von k hoch r minus i mal m von k minus c hoch i minus 1.
Also k² ist m von k minus c.
Ich habe das praktisch einmal ersetzt.
Dann habe ich hier m von k minus c hoch i minus 1 stehen.
Das vereinfacht einige Dinge im Weiteren.
Jetzt haben wir also diesen Ausdruck.
Jetzt können wir das m von k hoch r einfach dort rausziehen.
Da steht m von k hoch r minus i.
Dann bleibt hier in der Summe übrig m von k hoch minus i mal m von k
minus c hoch i minus 1.
Das kann ich anders schreiben.
Das ist also m von k hoch r.
Jetzt dividiere ich das noch durch m von k minus c.
Hier stand hoch i minus 1.
Dann muss ich hier hoch i hinschreiben.
Das m von k hatte hoch minus i.
Also das ist m von k minus c durch m von k.
Das Ganze hoch i.
Das ist eine geometrische Reihe, wobei das Element hier kleiner als 1
ist.
Für den Wert einer geometrischen Reihe haben wir einen ganz klaren
Ausdruck.
Den können wir sofort hinschreiben.
Das ist 1 minus dieses Reihenglied hoch r plus 1 durch 1 minus m von k
minus c durch m von k.
Das ist also dieses Reihenglied.
Und das Ganze minus 1.
Das ist der Ausdruck für den Wert einer geometrischen Reihe von i
gleich 1 bis r.
Das können wir jetzt weiter umformen.
Das hier war m von k hoch r durch...
Das können wir genauso gut durch k Quadrat wieder hinschreiben.
Das ist kein Problem.
Und hier unten steht dann, wenn wir das alles ausrechnen, kommt dieser
Ausdruck raus.
Da steht jetzt m von k hoch r plus 1.
Oben stehen noch so ein paar Terme obendrauf.
Mal m von k durch c.
Und wir versuchen es nochmal.
Tut mir leid, das ist alles sehr ärgerlich heute.
Ups, da war zu viel.
Also, wir müssen diesen Ausdruck umformen.
Und mit ein bisschen Formelmassage kommen wir hier auf ein Term, wo
wir das m von k hoch r rausziehen können.
Das k Quadrat ziehen wir wieder rein in diesen Ausdruck.
Und dann nochmal etwas umformen.
Wir ziehen noch das 1 durch m von k minus k Quadrat raus.
m von k minus k Quadrat ist ja gerade 1 durch c, das ist eine
Konstante.
Hier steht 1 minus k Quadrat durch m von k.
m von k ist größer als k, das ist ein Wert, der kleiner als 1 ist.
Das heißt, der verschwindet für großes R.
Dann steht hier im Wesentlichen 1 durch c.
Und das ist eine Konstante, also m von k hoch r mal irgendeiner
Konstanten für ausreichend großes R.
Können wir klar sagen, das ist im Groß-O von m von k hoch r.
Das ist das, was wir zeigen wollten.
Der Aufwand für diesen Ausdruck wächst mit m von k hoch r.
Beziehungsweise, wenn wir uns jetzt die Anzahl der Multiplikationen
und Additionen anschauen.
Das war also m von k hoch r für die Multiplikationen plus
Größenordnung m von k hoch r für die Additionen.
Und das ist also insgesamt in O von m von k hoch r.
Also das R ist das log n zur Basis k.
n ist ja gleich k hoch r.
Jetzt haben wir hier einen Ausdruck m von k hoch log zur Basis k von
n.
Und, das haben Sie in der Übung auch angeschaut, kann ich umformen in
O von n hoch log zur Basis k von m von k.
Das ist eine leichte Umformung.
Und jetzt haben wir den Ausdruck, der uns interessiert.
Die klassische Matrixmultiplikation braucht einen Aufwand von n hoch
3.
Und hier haben wir einen Aufwand.
Die Anzahl der arithmetischen Operationen ist O von...
Ich will jetzt doch den kurz wegradieren.
Das sah nicht so schön aus.
Jetzt haben wir hier durch diese Umformung n hoch log zur Basis k von
m von k.
Und das ist die Anzahl der Multiplikationen.
Und die Konstante da drin kann man abschätzen entsprechend dem, was
wir uns vorher alles überlegt hatten.
Ist also eine nicht sehr klein, aber es ist eine vernünftige
Konstante.
Man kann versuchen, die noch möglichst klein zu machen.
Das lasse ich jetzt mal außer Acht.
Und das, was wir als Ergebnis kriegen an dieser Stelle, ist, wenn es
einen Algorithmus gibt, der ein Produkt von kleinen k kreuz k-Matrizen
mit kleinen m von k größer k-Quadratmultiplikationen berechnet, ohne
die Kommutativität der Multiplikation auszunutzen, dann können
beliebige n kreuz n-Matrizen mit o von n hoch log zur Basis k von m
von k arithmetischen Operationen multipliziert werden.
Das heißt, wenn wir ein Verfahren suchen, Groß K, das die
Arithmetische Operation für die Multiplikation von Matrizen reduziert,
brauchen wir uns nur um die Anzahl der Multiplikationen zu kümmern.
Die Anzahl der Additionen spielt für die asymptotische Größenordnung
hier keine Rolle.
Das ist der interessante Effekt, den wir hier haben.
Wir haben ja auch diesen Divide-and-Conquer-Ansatz.
Der ist ja auch nur abhängig von der Anzahl der Multiplikationen.
Das kennen wir jetzt schon, was passiert.
Jetzt bei der anderen Auflösung ein bisschen einfacher zu handhaben.
Ich muss das beenden, muss das hier beibehalten.
Und anschließend darf ich das hier nochmal wieder reingehen.
Und dann haben wir jetzt also diesen Satz.
Und jetzt ist das also das wesentliche Ergebnis.
Und jetzt kommt der Clou mit der tatsächlichen Multiplikation von 2
kreuz 2-Matrizen.
Dieser Algorithmus ist eben von Strassen entdeckt worden.
Der hat sich ausgedacht, hat rumgeknobelt, wie kann ich mit weniger
als 8 Multiplikationen 2 kreuz 2-Matrizen multiplizieren.
Sie wissen, wir brauchen 8 Multiplikationen.
2 hoch 3 sind 8 Multiplikationen für diese 4 Skalarprodukte.
In den 4 Skalarprodukten habe ich 4 Additionen zu machen.
Und hier sehen Sie, kommen viel mehr Additionen vor, das sind 18
Additionen.
Aber die Multiplikation, die Produkte, die berechnet werden, sind
aufgeführt.
Das sind genau 7 Produkte, die berechnet werden müssen.
Da ist eine Multiplikation, da ist eine, da ist eine, da ist eine, da,
da und da.
Das sind die Multiplikationen.
Und es werden multipliziert immer irgendwelche Summen von Elementen
der Matrix.
Dabei wird die Kommutativität der Multiplikation nicht ausgenutzt.
Sie können sich alles ausrechnen.
Die Terme, die hier auftreten in diesem Rechnungsschema, das sind
erstmal die Produkte, die berechnet werden.
Und dann bekommen Sie aus diesen Produkten die Skalarprodukte der 2x2
-Matrix, also C11 als P1-P3-P5-P6.
Das C12 ist P3-P4-C21-P2-P5.
Und C22, wieder ein etwas aufwendigerer Ausdruck, P1-P2-P4-P7.
Das sind insgesamt sieben Multiplikationen, 18 Additionen.
Und es ist offensichtlich, weil wir hier nur sieben Multiplikationen
brauchen, ist der Aufwand n hoch log zur Basis 2 von 7.
Und der Logarithmus von 7 zur Basis 2 ist 2.81, also asymptotisch
besser als n hoch 3.
Wir haben das im Exponenten etwas reduzieren können.
Jetzt können Sie sagen, naja, was bringt das schon, um weniger als 0,2
im Exponenten etwas reduziert.
Aber wenn Sie den Exponenten reduzieren, haben Sie tatsächlich eine
asymptotische Reduktion des Aufwandes.
Je größer das n wird, desto stärker wird der Gewinn, den Sie haben.
Wenn Sie eben nur einen konstanten Vorteil haben, wie bei dem Vinograd
-Verfahren, da hätten Sie einen Faktor 2.
Wenn Sie Glück haben.
Aber eben hier hätten Sie wesentlich größeren.
Könnten wir das Vinograd-Verfahren so umformulieren, dass dort die
Kommutativität der Multiplikation keine Rolle spielt, dann könnten wir
die Anzahl der Multiplikationen halbieren.
Das wäre natürlich fantastisch, da würden wir drastisch runtergehen.
Man kann aber zeigen, dass sieben Multiplikationen optimal sind.
Es geht nicht, Sie können 2 x 2 x 3 nicht mit weniger als sieben
Multiplikationen multiplizieren.
Achso, das kommt noch.
Im Vorgriff, 18 ist zu viel, Sie können auf 15 Multiplikationen
runterkommen.
Wir haben übrigens in einer Masterarbeit, ist bei uns gerade das
nochmal genau analysiert worden, wir haben mit evolutionären
Algorithmen alle möglichen Berechnungsschema dafür, 2 x 2 x 13
durchgespielt und dabei eine Reihe von äquivalenten Formulierungen
gefunden, auch mit sieben Multiplikationen und 15 Additionen.
Das heißt, es gibt eine ganze Reihe von solchen Schema da.
Der Strassen hat das damals, durch zufälligen Einfall, hat er dieses
Schema gefunden.
Okay.
Verbesserung, wie gesagt, ist von Vinograd gemacht worden sofort.
Der hat die 15 Additionen gefunden, also drei Additionen weniger.
Und beides ist optimal für 2 x 2 x 3.
Sie können also nicht mit weniger als 15 Additionen.
Wenn Sie also sieben Multiplikationen haben, brauchen Sie mindestens
15 Additionen.
Es geht nicht mit weniger.
Wenn Sie acht Multiplikationen haben, dann kommen Sie mit vier
Additionen aus.
Also eine weitere Multiplikation führt dazu, dass Sie wesentlich
einfacher auf einmal bezogen auf die Additionen arbeiten können.
Sie sehen, da sind interessante Trade-offs dabei.
Und dann macht man noch Dinge, ich hatte auf der vorigen Folie noch
stehen, ab R gleich 10 besser als die Schulmethode, wenn man genau das
Verfahren einsetzt von Straßen.
R gleich 10 bedeutet, Sie haben 2 hoch 10 kreuz 2 hoch 10 Matrizen.
Das sind schon ziemlich große Matrizen, 1.000 x 1.000 Matrizen.
Wenn Sie es ein bisschen effizienter machen wollen, dann machen Sie
ein gestuftes Verfahren.
Das heißt, Sie machen das Straßenverfahren bis zu einer
Rekursionstiefe R.
Also P mal 2 hoch R.
Und dann setzen Sie für P kreuz P Matrizen die Schulmethode ein.
Und da ab einer gewissen Größe Schulmethode langsamer ist als Straßen,
ist es klar, dass Sie nicht zu weit runter gehen in den P. Weil da
eben die Schulmethode besser ist als der Straßenansatz.
Deswegen machen Sie gleich die Schulmethode und machen nur für die
größeren Matrizen dann dieses Straßenverfahren.
Das ist also eine elegante Art, das zu machen.
Ist mittlerweile Werkzeug in der ganzen Reihe von Softwarepaketen für
effiziente Matrixmultiplikation, dass man solch ein Verfahren
einsetzt.
Man muss ein bisschen aufpassen.
Ein Problem ist die numerische Stabilität.
Wenn Sie reelle Zahlen hier haben, kann es sein, dass da mal gewisse
Probleme auftreten, weil dort die Berechnungsreihenfolge, die Art, wie
Sie Terme berechnen, hier etwas anders ist.
Das kann sich in bestimmten Situationen negativ auf die Genauigkeit
auswirken.
Aber mittlerweile hat man auch das weitgehend im Griff.
Und dann ist die Straßenmethode, wenn man das so gestuft macht,
bereits ab N größer 40.
Also für 40x40 Matrizen ist dieses Verfahren schon besser als die
normale Schulmethode.
Und das ist durchaus eine Größenordnung, die in der Praxis häufig
auftreten wird.
Und das Prinzip ist halt, dass ich das Problem, wie wir schon sagten,
in kleinere Aufteile, typischer divide-and-conquer-Ansatz.
Wir wollen alle kleineren Probleme rekursiv lösen und die Lösung des
großen Problems aus den Lösungen der kleineren Probleme dann ableiten.
Also, jetzt ist es so, das Prinzip ist klar, habe ich Ihnen sehr
deutlich gemacht.
Verzweigungsgrad ist halt, wie ich das deutlich gesagt habe, die
Anzahl der Multiplikationen in der kxk-Methode.
Also in diesem Fall haben Sie Verzweigungsgrad von 7 bei dem divide
-and -conquer.
Sie teilen in 7 Teilprobleme auf, für jede Multiplikation einen
extrarekursiven Abstieg.
Und jetzt ist die Frage, was heißt das eigentlich?
Jetzt kann ich Multiplikationen schnell machen.
Das Interessante ist, dass die Anzahl der arithmetischen Operationen
für die Matrixmultiplikation in der gleichen Größenordnung liegt, wie
die Anzahl der arithmetischen Operationen für die Inversion von
Matrizen.
Und auch der Aufwand, um Determinanten zu berechnen.
Und wenn Sie das beides in der gleichen Größenordnung, was die Anzahl
der arithmetischen Operationen angeht, bearbeiten können, dann heißt
das, Sie können lineare Gleichungssysteme auch mit der gleichen Anzahl
arithmetischer Operationen lösen.
Und das ist also dann der wesentliche Punkt gewesen.
Mittlerweile ist es so, dass nach diesem Ergebnis von Strassen haben
sich viele Leute begonnen zu interessieren dafür, wie man die
Berechnung noch effizienter machen kann.
Man hat völlig andere Ansätze gewählt.
Also bei 3x3-Matrizen hat man das noch nicht geschafft, wirklich
runterzukommen unter dieses 2.81.
Also man hat kein Verfahren gefunden, bei dem man signifikant weniger
Multiplikationen braucht, um da noch weiter runterzukommen.
Mit völlig anderen Ansätzen ist man aber mittlerweile bei N hoch 2.37.
Mittlerweile, also das ist jetzt auch schon 30 Jahre her.
Das Interessante ist, die untere Schranke für die Matrixmultiplikation
ist N².
Wir haben keine Erkenntnisse drüber oder keine guten Möglichkeiten,
die untere Schranke nach oben zu drücken, ist noch keinem gelungen.
Zu sagen, man braucht mehr als eine Addition und eine Multiplikation
pro Skalarprodukt, also das nach oben zu drücken, ist noch keinem
gelungen.
Das heißt, da ist immer noch eine Lücke zwischen N² und N hoch 2.37.
Aber das ist schon verdammt weit runtergegangen.
Allerdings ist hier die Konstante in einem Bereich, der nicht
angemessen ist.
Das ist ja erstaunlich.
Jetzt ist das gleich wieder da.
Das ist also unsere untere Schranke, Omega von N².
Und dieses N hoch 2.37 ist ein theoretisches Ergebnis, hat eigentlich
kaum Praxisrelevanz.
Obwohl Leute immer noch da dran sind, das weiter zu verbessern.
Weil es eben Auswirkungen hat auf so viele Operationen.
Technisch-wissenschaftliche Berechnungen haben ganz viel mit
Linangleichungssystemen zu tun.
Also wenn Sie die Matrixmultiplikation schneller hinkriegen, dann geht
der ganze Rest eben auch wesentlich besser.
Jetzt schauen wir uns die Matrixinversion nochmal genauer an.
Ich gebe Ihnen jetzt ein explizites Verfahren, ohne zu beweisen, dass
es das genau tut.
Auch hier wieder partitionieren wir die N-Kreuz-N-Matrizen in 2-Kreuz
-2 -Matrizen und machen ein Verfahren, bei dem wir folgende
Operationen machen.
Sie sehen, hier kommt eine Inversion vor.
Das wäre also dann ein rekursiver Abstieg für die Inversion.
Das wäre eine Inversion einer N½ x N½-Matrix.
Dann haben Sie hier eine Reihe Multiplikationen von Matrizen.
Sie haben hier eine Subtraktion von Matrizen und dann noch eine
Inversion der resultierenden Matrix P5.
Dann haben Sie hier die Ergebnisse.
Ah, das ist jetzt falsch animiert.
Dann kommen hier die Ergebnisse raus für die Inverse.
Sie sehen, das sind also eine ganze Reihe von Matrix-Multiplikationen.
Jeweils von N½-Kreuz-N½-Matrizen und dann noch so ein paar Additionen,
zwei Inversionen dabei.
Das ist das Schema, mit dem man invertieren kann.
Also ein explizites Schema.
Jetzt gibt es sicherlich noch andere Ansätze.
Man kann also allgemein zeigen, wenn die Matrix-Multiplikation in
einer Zeit N½ geht, für Alpha größer gleich 2, dann kann ich die
Matrix -Inversion in der gleichen asymptotischen Größenordnung machen.
Das muss man genau beweisen.
Dann kann man über dieses Schema hinbekommen, dass das dann in der
gleichen Größenordnung liegen muss.
Das habe ich jetzt aber nicht genauer ausgeführt.
Also, da ist ein neuer Beamer drin.
Das kann der Grund sein für die Probleme, die ich habe.
Da müssen wir mal gucken.
Ich hatte vorher in diesem Raum keine Probleme mit dem Beamer.
Und letztes Mal wurde uns hier ein extra Beamer hingestellt, das hieß,
der wird ausgetauscht.
Herr Mauser, vielleicht können Sie mal mit Herrn Toussaint Kontakt
aufnehmen und fragen, was das sein kann.
Denn das sind Probleme in der Kommunikation zwischen dem Laptop und
dem Beamer da oben.
Okay.
Die Umkehrung ist ganz einfach.
Also stellen Sie sich vor, Sie haben ein effizientes Verfahren oder
irgendein Verfahren für die Matrix-Inversion.
Jetzt können Sie darüber auch ein Verfahren für die Multiplikation
gewinnen.
Jetzt haben wir noch einen schönen Effekt, das PowerPoint aufgehört
hat.
Heute ist wirklich das besonders interessant.
Machen wir gleich weiter.
Matrix-Inversion.
Also, nehmen Sie an, Sie haben ein effizientes Verfahren für die
Inversion.
Sie wollen jetzt Matrizen multiplizieren.
Dann bauen Sie sich eine Matrix.
Sie wollen n kreuz n Matrizen multiplizieren.
Sie bauen sich eine 3n kreuz 3n Matrix, bei der Sie die Matrizen A und
B in die obere Hälfte reinschreiben.
Die anderen Bereiche füllen Sie mit der Identitätsmatrix, die hier als
I angegeben ist.
Und ganz oben steht eine Nullmatrix.
Diese Matrix invertieren Sie.
Und wenn Sie die invertieren, dann können Sie die Inverse sofort
hinschreiben.
Die Inverse ist die Matrix, bei der hier steht, minus A minus B.
Und da oben steht A mal B.
Also, wenn Sie die Matrix invertieren können, brauchen Sie
anschließend, um das Produkt zu bekommen, nur ganz einfach hier oben
das A mal B dort rauszulesen.
Das heißt, durch die Inversion bekommen Sie implizit das Produkt der
beiden Matrizen A und B berechnet.
Also, wenn Sie ein Verfahren für die Inversion haben, könnte ja sein,
dass man Inversion ganz schnell hinkriegen kann.
Was hier oben drüber steht, ist, wenn ich Multiplikation machen kann
in der Zeit N hoch Alpha, dann geht die Matrixinversion auch in der
Zeit N hoch Alpha.
Und jetzt zeigen wir, wenn wir irgendein Verfahren für die Inversion
haben, dann kann ich daraus ein Verfahren in der gleichen
Größenordnung bekommen für die Multiplikation.
Und damit sieht man, dass die wirklich genau in der gleichen
Größenordnung Bedarf haben an arithmetischen Operationen.
Also, die hängen sehr eng miteinander zusammen.
Der Originaltitel der Arbeit von Strassen war, die Gauss'sche
Elimination ist nicht optimal.
Und das, wenn Sie sich davor Lehrbücher angeschaut haben über Numerik,
wurde immer gesagt, Gauss'sche Elimination ist ein optimales Verfahren
für die Lösung linearer Gleichungssysteme.
Das ist halt nicht wahr.
Aber darauf kommt man erst, wenn man sich wirklich intensiver damit
beschäftigt, welche Berechnungen eigentlich gemacht werden.
Und wenn man das einfache Entwurfsprinzip, das die Weidenkonker
anwendet in dem Bereich, ob man weiter runterkommen kann, ist bis
heute offen.
Wenn Sie nette Ideen haben, dürfen Sie sich gerne damit beschäftigen.
Und wenn einer Ideen hat, wie man die Kommunikation zwischen Rechner
und Beamer besser hinkriegen kann, wäre ich auch sehr dankbar.
Also, beenden wir das mal wieder.
Beibehalten.
Und hier auf die nächste Folie gehen.
Und jetzt ist uns das nicht schnell genug.
Wir wollen gerne Moet-Matrizen noch schneller multiplizieren.
Und der nächste Einsatz dafür ist, die Multiplikation zu
parallelisieren.
Das war unser erstes Beispiel.
Und jetzt gehen wir hier auf die Parallelisierung.
Wir hatten Parallelisierung ganz zu Anfang schon gemacht.
Das war dieses Bild gewesen mit dem... die völlig parallele Version.
Sie erinnern sich, O von Log N Schritte.
Da hatten wir dieses Dreieck gemacht, hier oben die vielen
Multiplikationen.
Und dann die Aufsummierung.
Aufwand Log N mit N hoch 3 durch Log N Prozessoren.
Hatte ich Ihnen gezeigt.
In der naiven Version erstmal N hoch 3 Prozessoren in der Zeit Log N.
Dann die Anzahl der Prozessoren etwas reduziert um den Faktor Log N.
Und immer noch Zeit O von Log N.
Deswegen macht es keinen Sinn, N hoch 3 Prozessoren zu nehmen, sondern
N hoch 3 durch Log N.
Und das ist natürlich optimal im Vergleich mit O von N hoch 3
Operation.
Jetzt erinnern Sie sich, bei dem Speedup, bei dem Zeitgewinn, den wir
berechnen für parallele Algorithmen, sagte ich, wir müssen vergleichen
mit dem besten sequenziellen Algorithmus.
Jetzt hat der beste sequenzielle Algorithmus, den wir kennen, einen
Aufwand von O von N hoch 2.37.
Der hat aber eine Konstante da drin, der das Verfahren erst besser
macht als die Schulmethode für sehr, sehr, sehr, sehr große Matrizen.
Und für die Matrizen, die hier eine Rolle spielen, die Größenordnung,
ist N hoch 3 das beste sequenzielle Verfahren.
Deswegen sage ich, für die Parallelisierung, wenn wir von N hoch 3
Prozessoren reden, Sie werden nicht für 1.000 x 1.000 Matrizen 1.000
hoch 3 Prozessoren verwenden.
Das sind echt interessante Effekte hier.
Und das heißt, wir vergleichen das mit N hoch 3.
Deswegen, wir vergleichen tatsächlich mit N hoch 3.
Und jetzt schauen wir uns an, zweidimensionale Prozessorfelder.
Also nicht beliebig parallel, sondern...
Was hat er jetzt wieder vor?
Und jetzt haben wir hier ein zweidimensionales Prozessorfeld.
Und die Matrizen, sie erinnern sich an das eine Beispiel von Kuhn und
Leiserson mit dem hexagonalen Feld.
Hier haben wir ein anderes verbundenes Feld, ein zweidimensionales,
gitterverbundenes Feld.
Und Sie sehen die beiden Matrizen, die hier reingeschoben werden.
Die Matrix A von links nach rechts, Matrix B von oben nach unten.
Und Sie sehen hier vor diesem ersten Feld, links oben, stehen A14 und
B41.
Jetzt werden die im ersten Schritt addiert... Quatsch, multipliziert.
Und anschließend stehen dort A13 und B31 bereit.
Das heißt, an der gleichen Stelle addieren wir anschließend die
beiden, das Produkt von A13 und B31 und haben dann schon mal einen
Teil berechnet.
Und in der Zelle daneben wurden A14 und B42 berechnet.
Und das heißt, wenn wir das jetzt der Reihe nach hier so durchlaufen
lassen, dann haben wir nach einer gewissen Anzahl von Schritten alle
Elemente berechnet.
Insgesamt sind das 3n-2 Schritte, also wir mussten das erste Element
hier oben reinschieben.
Dann müssen dort die anderen drei Produkte auch noch drauf addiert
werden.
Das sind also insgesamt n Takte, bis das erste berechnet ist.
Dann müssen Sie noch weiter hier durchlaufen und hier bei uns runter.
Das sind noch mal 2 mal n-1 oben drauf.
Das heißt insgesamt 3n-2, damit insgesamt in all diesen Zellen, also
jetzt hier drin steht C11, hier C12 und so weiter.
Dann sind die alle dort berechnet.
Wir können also jetzt diese Matrix, das Matrixprodukt berechnen in 3n
-2 Takten.
Und dann stehen die Produkte in diesen Zellen drin.
Wenn Sie die noch auslesen wollen anschließend, dann müssten Sie noch
mal dort n Takte für spendieren, um die ganze Matrix auszulesen mit n
Elementen pro Takt.
Dann würden Sie die nach rechts oder nach unten oder wohin auch immer
einfach rausschieben.
Wie sieht das aus mit dem Zeitgewinn S von n?
Im Vergleich mit n hoch 3 ist der Zeitgewinn n Quadrat, weil wir von n
hoch 3 auf n kommen.
Das heißt die Effizienz ist optimal, ist 1.
Wir haben n hoch 3 reduziert auf Laufzeit n, besser geht es nicht.
Also ein optimales Verfahren auf zweidimensionalen Feldern.
Und nur noch als Erinnerung, was ich schon mal sagte, in der Realität
werden Sie keine riesen Felder, also zweidimensionale Felder bauen, um
Matrizen zu multiplizieren, sondern Sie werden vielleicht 5x5 oder 6x6
oder 8x8 Felder haben und dann partitionieren Sie Ihre Matrix in
entsprechend 8x8 Matrizen und Sie werden in diesen einzelnen
Prozessoren jeweils Matrixprodukte berechnen.
Und werden die durch so ein Feld hindurchschieben, dann sind das dicke
Prozessoren, die jeweils etwas dickere Skalarprodukte berechnen oder
Matrixmultiplikationsfunktionen ausführen.
Okay, das war ein Verfahren.
Ich zeige Ihnen noch eins.
Jetzt haben Sie also schon zwei kennengelernt auf zweidimensionalen
Feldern, hier kommt noch ein Verfahren.
Das ist jetzt von Kramer und van Leeuwen, zwei Holländer.
Die Zelle macht immer das Gleiche, diese elementare
Skalarproduktoperation.
Und in diesem Fall laufen die wieder etwas anders.
Hier läuft das A von oben nach unten, das B von unten nach oben.
Und jetzt bewegt sich, wie bei dem Anfangsbeispiel mit dem hexagonalen
Feld, auch die Matrix C.
Und ich fahre in diesem Fall von links nach rechts.
Zu Anfang sind die Elemente alle auf Null gesetzt.
Und dann laufen die hier durch.
Sie sehen, die müssen erstmal eine Weile dort reinlaufen.
Im nächsten Takt werden hier A11 und B11 zusammenkommen.
Und auf C11, was anfangs Null ist, addiert.
Das ist dieser Takt.
Und dann läuft das entsprechend weiter durch.
Und Sie sehen, in diesem Fall ist das Feld in jedem Takt genau zur
Hälfte ausgelastet.
Wir haben also jetzt hier, läuft aus der Reihe nach durch.
Und dann entsprechend nach einer gewissen Zeit ist die gesamte Matrix
berechnet.
Die Gesamtzeit hier ist 4N-2.
Also im Prinzip genauso lange wie bei dem Verfahren auf der vorigen
Folie.
Weil ich dort ja sagte, das war 3N-2 plus N, wenn Sie die Elemente
auslesen wollen.
Hier sind sie ausgelesen.
Und wir haben also wieder einen Zeitgewinn von N², eine optimale
Effizienz.
Was Sie bei beiden Verfahren machen können ist, wenn Sie dann das
berechnet haben, was ich Ihnen auch schon erzählt habe bei dem anderen
Verfahren mit dem hexagonalen Feld, Sie können natürlich das hier
wieder dort reinschieben.
Und könnten so auf einem Feld begrenzter Größe, das wäre dann ein
lokal -parallel-global-sequenzielles Verfahren, könnten Sie ein
größeres Matrixprodukt berechnen und dort dieses Feld nutzen, wenn Sie
das als kleines Extrafeld tatsächlich realisieren mit Elementen, die
nur diese Operation ausführen, könnten Sie so ein lokal-paralleles
-global -sequenzielles Verfahren machen.
Oder wie ich Ihnen vorgesagt hatte mit der Partitionierung, dann
würden Sie das als lokal-sequenziell-global-paralleles Verfahren
machen.
Das sind alles so Varianten der parallelen Ausführung, je nachdem, ob
Sie hier kleine, dedizierte Prozessoren haben, die nur diese eine
Operation machen, oder ob Sie dort dicke Prozessoren haben, die im
Prinzip auch diese Operation ausführen, da sind aber diese A, B und C
dann dickere Matrizen.
Okay, haben wir noch ein Verfahren kennengelernt.
Jetzt könnte ich Ihnen noch eine ganze Reihe weiterer Verfahren
vorstellen, wo die Matrizen wieder irgendwie anders durch so
zweidimensionale Felder durchlaufen.
Und die Frage ist, wie kommt man eigentlich auf sowas?
Und das Interessante ist, dass man ausgehend von solchen Algorithmen
einen systematischen Algorithmus entwickelt hat, einen systematischen
Ansatz entwickelt hat, wie man solche Art von Algorithmen systematisch
auf zweidimensionale Prozessorfelder abbilden kann.
Und das ist, also zunächst mal denkt man, ich habe Intuition, die
Ersten haben das mit Intuition gemacht, die Nächsten haben gesehen,
oh, ich habe ja noch eine andere Idee.
Und dann ist die Überlegung, kann man das nicht systematisch machen?
Und die Idee ist eben, dass man parallele Algorithmen für die
Matrixmultiplikation durch ganz systematische und weitgehend
automatisierbare schrittweise Transformationen erzeugt.
Das heißt, ich kann dann Algorithmen systematisch erzeugen und gehe
aus von einer mathematischen Formulierung des Problems.
Na?
Es spielt noch ein bisschen rum hier.
Jetzt ist er wieder in Ordnung.
Man muss ein bisschen Geduld haben.
Siehe nächste Folien.
Na ja, jetzt hat er sich hier beruhigt, aber leider in einem falschen
Gleichgewicht.
Das ist wirklich extrem ärgerlich.
So, wieder dort.
Wir wollten also hier auf den nächsten Folien, wo wir jetzt das
systematisch angehen.
Wir wollen parallele Algorithmen durch eine systematische und
weitgehend automatisierbare schrittweise Transformation erzeugen.
Und wie machen wir das?
Wir haben eine Problemdefinition.
Eine Problemdefinition ist, soweit wir das bisher kennen, ein
iterativer Algorithmus.
Die dreifach geschachtelten Schleifen.
Das ist der Kern der Matrixmultiplikation bei dem naiven Verfahren,
bei der Schulmethode.
Ich kann das, was dort steht, das ist ja im Kern steht ja dieses c
gleich c plus a mal b.
Iterativ kann ich das auch rekursiv aufschreiben.
Ich habe ein System von Rekurrenzgleichungen, so nennt man das.
Und aus diesen Rekurrenzgleichungen kann man einen sogenannten
Datenabhängigkeitsgraf erzeugen.
Das werden wir gleich sehen, wie das geht.
Ich habe gewisse Abhängigkeiten.
Ich habe hier schon etwas berechnet.
Und dort kommen Werte, die mir zur Verfügung gestellt werden, um auf
die Zwischenergebnisse neue Werte drauf zu addieren.
Und dann bekomme ich neuen Wert.
Das hier ist gemacht worden im Schritt k-1, das soll im Schritt k
gemacht werden.
Und diese Matrizen hier, die stehen im Prinzip auch aus dem k-1 und k
-1 zur Verfügung.
Also, in der Art und Weise wird das gleich aussehen.
Und dann habe ich einen Graphen, der die Datenabhängigkeiten angibt.
Und in diesem Graphen stehen die einzelnen Berechnungen drin, also
eine einzelne Berechnung mit irgendwelchen Angaben, wo diese drei
Komponenten herkommen, die hier berechnet werden sollen, um ein
Ergebnis weiterzuliefern für die nächste Berechnung.
Dann habe ich für jede Berechnung, die gemacht werden, für jeden
Berechnungsschritt, für jedes solche kleine Produkt dort, einen
Berechnungsknoten in dem Graphen.
Und jetzt muss ich nur diesen Graphen abbilden auf ein
zweidimensionales Feld.
Das heißt, ich muss jedem Knoten, jeder Berechnung einen Ort zuweisen
und einen Zeitpunkt, sodass das ganze Verfahren korrekt durchgeführt
wird.
Und das ist genau das, was man hier macht.
Transformation, Projektion, Retiming, Zuordnung von Ort und Zeit zu
jeder einzelnen Berechnung.
Und dann bekomme ich Prozessorfelder völlig unterschiedlicher
Struktur.
Das ist ein sogenannter Mapping-Ansatz.
Da gibt es verschiedene Begriffe für.
Neulich sagte mir jemand, er hätte das Unterbegriff Mapping-Ansatz
nicht gefunden.
Ich habe in der Anfangsliteraturliste Ihnen das Buch von Zehntner
empfohlen.
Da stehen diese Verfahren sehr ausführlich dargestellt drin, mit allen
möglichen Varianten, wie man systematisch solche Verfahren auf
zweidimensionalen Feldern entwerfen kann.
Das nennt sich Entwurf systemischer Systeme.
Und das ist im Prinzip dieser Abbildungsansatz, um Algorithmen zu
erzeugen.
Und das werde ich Ihnen jetzt an dem Matrix-Modifikationsbeispiel noch
einmal vorführen.
Also, unsere Problemdefinition lautet so, das kennen Sie nun wirklich
schon in- und auswendig.
Cij gleich Summe k gleich 1 bis n aik bkj.
Eine Summendarstellung dieser Skalarprodukte.
Und iterativ können wir das so hinschreiben wie hier.
Das haben Sie alles kennengelernt.
Eine dreifach geschachtelte Schleife.
Also, ich habe hier zwei Indizes in der oberen Schleife drin für ij
gleich 1 bis n.
Ich hätte schreiben können für i gleich 1 bis n, für j gleich 1 bis n.
Und dann haben wir hier drin noch mal für k gleich 1 bis n.
Sie wissen, warum wir in unserer Formulierung die Cij hier nicht
hingeschrieben haben, sondern da eine hilfsvariable Summe verwendet
haben.
Wenn Sie dort Cij reinschreiben würden in Ihrem Programm, hätten Sie
entsprechend noch mal für jedes Cij eine Multiplikation und zwei
Additionen extra.
Das heißt, Sie würden das Verfahren deutlich verlangsamen wegen dieser
zusätzlichen arithmetischen Operationen, um diese Variable Cij jeweils
zu finden.
Das heißt, deswegen ist es so wichtig, dass man dort diese
hilfsvariable Summe normalerweise verwendet.
Das spielt jetzt keine Rolle.
Wir wissen, wie wir das im Programm normalerweise machen.
Hier schreiben wir es jetzt nur wegen der Beziehungen zwischen den
Indizes so noch mal hin.
Und jetzt verwandeln wir diese Darstellung in eine sogenannte Single
Assignment Form.
Single Assignment Form heißt, jeder Variablen in meinem Programm wird
nur einmal einen Wert zugewiesen.
Hier sehen Sie, da war das nicht der Fall.
Cij wird hier k mal einen Wert zugewiesen.
Oder k plus eins mal in dem Fall sogar.
Zuerst null und dann die anderen Werte.
Das ist nicht Single Assignment.
Single Assignment ist, wenn wir das gleich wieder sehen dürfen, das
wäre diese Form.
Ich habe Variablen Cijk, k gleich eins bis n.
Und mein Cij null wäre null.
Und entsprechend würde ich dann die Werte hier drauf addieren.
Dann habe ich hier Aik und Bkj.
Das sind natürlich Werte, die werden gar nicht verändert.
Die haben einmal ihren Wert.
Jetzt habe ich hier ein Problem.
Ich habe die Variablen Cijk und ich habe Variablen Aik und Bkj.
Ich möchte gerne alle Variablen jetzt mit drei Indizes versehen.
Das heißt, das A hat nur zwei Indizes, da füge ich noch ein J dazu.
Und das B hat nur zwei Indizes, da füge ich noch ein I dazu.
Dann habe ich die Formulierung, die Sie hier sehen.
Ich habe jetzt meinen Schleifenrumpf umformuliert in diese
Darstellung, die Sie hier sehen.
Wir müssen für jedes Ik und J, also so ein Cijk hier berechnen.
Und das ist gleich Cik-1j plus A von Ikj-1 und Bi-1kj.
Jetzt haben wir also hier die extra Indizes dazugefügt.
Wir haben noch einen extra Index I und hier J, der vorher nicht
auftauchte.
Das heißt, wir müssen jetzt festlegen, wo bekommen diese Groß-A- und
Groß -B-Variablen ihre Werte her.
Also Groß-A-Ikj ist gleich A-Ikj-1, das wird einfach nur
durchgereicht.
Das B wird auch einfach nur durchgereicht.
Da wird das durchreichen über die erste Komponente, über den ersten
Index.
Und die Anfangsinitialisierung ist, dass das A-Ik0 auf A-Ik gesetzt
wird.
Das B0kj auf das Bkj.
Und das Ci0j auf 0.
Und jetzt wird das alles für alle I, K und J genauso definiert.
Und dann kann ich also hier mit dieser Formulierung genau diesen
Algorithmus ausführen, aber jetzt formuliert über ein System von
Rekurrenzgleichungen.
Das Wesentliche ist hier die Single Assignment Form.
Jetzt habe ich nämlich für jede einzelne Berechnung ein Trippel von
Indizes I, K und J.
Das heißt, ich habe N hoch 3 Operationen auszuführen für jedes I, K
und J.
Hier steht dieses N in Klammern hoch 3.
Und ich sehe für jede Zeile Datenabhängigkeiten.
Ich sehe, dass hier der Wert an der Stelle I, K und J abhängt von
einem Wert, der an der Stelle I, K-1, J berechnet wurde, bzw.
an der Stelle I, K, J-1 oder I-1, K, J.
Und jetzt schreibe ich mir gleich das alles dreidimensional auf oder
zeichne das auf und dann sehe ich die Abhängigkeiten.
Man nennt ein solches Rekurrenzgleichungssystem Uniform, weil ich
überall die gleichen Datenabhängigkeiten habe.
Ich habe überall die Abhängigkeiten hier, das geht um minus 1 jeweils
zurück.
Für alle I, K, J habe ich die gleichen Abhängigkeiten.
Die sind nicht unterschiedlich, je nachdem, welche Berechnung ich
gerade mache.
Und das heißt, ich habe jetzt für jedes I, K, J genau diese
Abhängigkeiten, dass das B kommen muss von einem Knoten an der
Position I-1, K, J, das A muss kommen von einem Knoten an der Position
I, K, J-1 und das C muss kommen von einem Knoten hier an der Position
I, K-1, J.
Und dann, wenn ich diese Werte bekomme, kann ich den Wert an der
Position I, K und J berechnen.
Und das sind Datenabhängigkeiten, die ich durch Vektoren darstellen
kann.
Bei dem C muss ich den Wert abziehen, um an den Ort zu kommen, wo der
Vorgängerwert herkam, bei A entsprechend andere Vektoren.
Das sind meine Datenabhängigkeitsvektoren, die ich aus diesem
Rekurrenzschema herausziehen kann.
Und sowas können Sie für alle Berechnungen machen, bei denen Sie
solche iterativen Algorithmen haben und wenn Sie ein bisschen
Programmiererfahrung haben in numerischen Anwendungen, werden Sie
feststellen, sowas tritt verdammt häufig auf.
Sie können also alle solche Arten von iterativen Algorithmen, wie wir
das hier oben sehen, können Sie auf die Art und Weise überführen in
Rekurrenzgleichungssystemen mit Single Assignment Form Variablen.
Und dann wollen wir das ausnutzen, um daraus systematisch parallele
Algorithmen zu erzeugen.
Das ist ja nur die Problemformulierung.
Und jetzt wollen wir parallele Algorithmen machen.
Ich habe also einen Datenabhängigkeitsgraf, den sieht man hier.
Hier für 3x3 Matrizen angegeben.
Ich habe jetzt die einzelnen Operationen, also jeder Knoten hier ist
eine Berechnung, die ausgeführt werden muss.
Sie sehen also hier, das hier ist der Knoten, wo die letzte Berechnung
ausgeführt werden wird.
Das ist die 3-3-3-Berechnung.
Da wird dann das C-3-3 berechnet am Ende.
Das sind die einzelnen Berechnungen.
Und die muss ich jetzt abbilden, diesen dreidimensionalen Graphen,
abbilden auf ein zweidimensionales Feld, sodass ich für jede
Berechnung sage, wo wird die ausgeführt, zu welchem Zeitpunkt.
Das heißt, ich brauche eine lineare Transformation, die jedem Index
ikj eine Zeit t und einen Ort xy zuordnet.
Das heißt, ich habe jetzt eine solche Zuordnung.
Ich multipliziere praktisch jedes ikj mit einer Matrix, zum Beispiel
mit der Matrix T.
Wenn ich genau diese Transformationsmatrix hier nehme, die dort steht,
dann kommt eine Abbildung raus, die diesem Prozessorfeld entspricht.
Und das müsste Ihnen bekannt vorkommen.
Hier läuft jetzt die Matrix A von unten nach oben, die Matrix B von
oben nach unten und die Matrix C von links nach rechts.
Wir hatten vorher das Kramer-von-Löwen-Verfahren gesehen.
Da liefen A und B gerade andersherum durch, aber im Prinzip ist es das
gleiche wie das Kramer-von-Löwen-Verfahren.
Das bekommen wir durch einfach die Transformation dieses
Datenabhängigkeitsgraphen mit dieser Transformationsmatrix.
Jetzt können Sie mit der Transformationsmatrix beliebig rumspielen.
Natürlich müssen Sie darauf achten, dass die Datenabhängigkeiten
erhalten bleiben.
Sie können die nicht beliebig anordnen.
Sie müssen entsprechend den Datenabhängigkeiten die Berechnungen
richtig machen.
Und das heißt, das muss eine injektive Abbildung sein auf dem
Indexbereich.
Sie können nicht zwei Berechnungen zur gleichen Zeit am gleichen Ort
machen.
Der Schedule, den Sie dort machen, darf den Datenabhängigkeiten nicht
widersprechen.
Das kann man dadurch ausdrücken, dass für jeden
Datenabhängigkeitsvektor das Produkt der Transformationsmatrix mit dem
Datenabhängigkeitsvektor größer gleich null sein muss.
Andernfalls, wenn das negativ wäre, hätten Sie negative
Abhängigkeiten.
Das heißt, Sie würden Dinge verlangen, die in der Zukunft berechnet
werden.
Das geht ja nicht.
Und insofern ist das eine einfache algebraische Anforderung.
Und jetzt kann man damit rumspielen.
Sie können damit auch rumspielen.
Sofern Sie es schaffen, das Applet, das gleich auf der nächsten Folie
Ihnen angegeben wird.
Das steht also hier ganz unten drin.
Wenn Sie das auf Ihrem Rechner zum Laufen kriegen.
Ich habe das gestern Abend mal kurz versucht auszuführen und stellte
fest, mir fehlt wieder irgendein Plugin auf dem neuen Rechner.
Es ist in meinem Browser ein bestimmtes Plugin nicht vorhanden.
Wir hatten das schon mal, das Problem.
Wir wissen, wie dann das löst, Herr Braun, Herr Mauser.
Sie können sich das kurz angucken, wie man das Problem löst, wenn man
das Applet zum Laufen bringt.
Und dann können Sie das vor dieses Arbeitsbereich schreiben als
Hinweis.
Bitte?
Da steht es schon drin.
Ja, ja, genau.
Muss man nur aufpassen.
Ich habe das gestern Abend nicht mehr gemacht.
Aber das ist ein Applet, wo Sie mit genau diesen
Transformationsmatrizen rumspielen können und dann immer sehen, was
für Prozessorfeldstrukturen dabei entstehen.
Und das ist gemacht für Matrix-Multiplikationen, für Sortierverfahren
und für Matrix-Vektor-Multiplikationen.
Also Sie können auch Sortierverfahren auf die Art und Weise
systematisch abbilden.
Und insofern sehr breit anwendbar.
Und wie gesagt, das Buch von Zehntner ist dafür eine Fundgrube für
solche Verfahren.
Noch wesentlich vielseitiger als das, was ich Ihnen hier als sehr
einfachen Ansatz dargestellt habe.
Was sind die Vorteile dieses Ansatzes?
Sie haben korrektheitserhaltende Transformationen.
Sie können das also so einsetzen, dass Ihnen tatsächlich ein Programm
für einen Parallelrechner daraus erzeugt wird.
Und es gibt solche Softwarepakete, die genau das machen.
Und sie können eben insbesondere eine Vielfalt verschiedener
Algorithmen erzeugen.
Allerdings basieren die alle auf dem gleichen Berechnungsschema.
Das heißt, besser als lineare Zeit wird das niemals.
Das Wesentliche ist ja diese Operation.
C gleich C plus A mal B.
Und damit haben Sie eine inhärente Sequenzialität bei diesen
Berechnungen drin.
Das heißt, das einzelne Skalarprodukt kann nicht in weniger als N
Takten berechnet werden.
So etwas wie das, was ich Ihnen bei dem PRAM-Ansatz gezeigt habe, dass
man das parallelisiert und das baumförmig addiert.
Das ist hier nicht abgebildet.
Dazu brauchen Sie eine andere rekursive Formulierung.
Und wenn Sie das anders formulieren, dann haben Sie nicht mehr
uniforme Abhängigkeiten, sondern dann sind die Abhängigkeiten davon
abhängig, auf welcher Stufe der Rekursion Sie sich gerade befinden.
Und damit läuft das Ganze nicht mehr.
Also hier ist es wirklich davon abhängig, dass Sie diese uniforme
Abhängigkeit haben, immer gerade um einen Schritt weiterlaufen.
Nachteil, wie gesagt, das linearisierte Berechnungsschema.
Deswegen sind die Möglichkeiten der Parallelverarbeitung in
gewissermaßen nur eingeschränkt nutzbar.
Aber mit N²-Prozessoren in linearer Zeit das Produkt zu berechnen, ist
ja schon optimal.
Insofern, das reicht für dieses Ziel.
Mit N²-Prozessoren Matrizen bestmöglich zu modifizieren.
Das geht mit genau diesem Ansatz.
Und es ist eben nur anwendbar auf homogene Berechnungen, bei denen die
gleiche Teilberechnung oft wiederholt wird.
Wenn Sie sich Ihre Programme anschauen, ist alles Mögliche...
Sie haben ein langes Programmstück und darin haben Sie irgendwo so
einen Teil, der iterativer Algorithmus ist.
Wir können den Teil parallelisieren, automatisch.
Die Sachen drumherum vielleicht nicht so gut, nicht so systematisch,
nicht so automatisiert.
Aber man kann eben Teile der Algorithmen damit sehr schnell machen.
Und das ist also ein wichtiger Ansatz, wie gesagt, um parallel etwas
zu tun.
Auch auf Multicore-Rechnern kann man genau solche Dinge anwenden.
Da muss man dafür sorgen, dass die Leute, die heutzutage Multicore
machen, überhaupt noch wissen, dass eine solche Technologie, ein
solcher Ansatz existiert, der eben nicht der Standardansatz ist, wenn
Sie effiziente Algorithmen ansonsten hören.
Das ist ein systematischer Ansatz und darauf kommt es mir an, Ihnen
Verfahren zu präsentieren, bei denen Sie lernen, wie man systematisch
Algorithmen entwickelt.
Und das geht hier ganz klassisch mit diesem Ansatz der linearen
Transformationen, sodass Sie auf unterschiedliche Art und Weise Ihre
Matrizen durch ein zweidimensionales Feld durchlaufen lassen können.
Sie können die Matrix A wandern lassen, die Matrix B wandern lassen
oder C oder irgendeine von den Konstanten im Feld drin lassen.
All das können Sie einstellen durch die Art der Transformation.
Sehr flexibel.
Okay, das ist die Matrixmultiplikation und als nächstes kommen wir zur
Auswertung von Polynomen.
Lassen Sie mich diese eine Folie noch heute machen.
Polynome auswerten ist auch ein Standardansatz bei numerisch
-wissenschaftlichen Berechnungen.
Sie müssen irgendeinen Polynomen berechnen, Polynomen enden gratis,
haben wir auch ganz zu Anfang schon als Beispiel gehabt mit dem Horner
-Schema.
Jetzt schauen wir uns das Allgemeine an.
Die sind beschrieben, solche Polynome durch die Koeffizienten A0 bis
An und die Variable x, natürlich auch der Grad, der ist ja durch die
Anzahl der Koeffizienten gegeben, das sind die Eingaben für die
Polynomauswertung.
Und wie kann man sowas darstellen?
Naja, als Datenstruktur haben Sie ein eindimensionales Feld für die
Koeffizienten und für die Variable x.
Und das ist Ihre Datenstruktur.
Und da müssen Sie damit sehen, wie Sie den Algorithmus ausführen.
Also das ist hier kein Problem, Datenstruktur ist trivial.
Und die Frage ist, wie viele arithmetische Operationen ich brauche, um
p von x zu berechnen.
Und Sie kennen das Horner-Schema, da habe ich n Multiplikationen, n
Additionen, ich hatte schon gesagt, das ist optimal, wir werden
beweisen, dass es optimal ist.
Wenn Sie allerdings spezielle Polynome betrachten, zum Beispiel, wir
hatten vorhin eine geometrische Reihe, Summe i gleich 0 bis n x hoch
i.
Da haben wir eine Formel für, haben wir vorhin auch angewendet, das
ist x hoch n plus 1 minus 1 durch x minus 1.
Das heißt, ich muss gar nicht n Multiplikationen, n Additionen machen,
ich muss das x hoch n plus 1 berechnen.
Das geht mit log n Multiplikationen, werden Sie später sehen.
Das ist einfach sukzessives Quadrieren.
Und dann muss ich zweimal eine 1 subtrahieren und einmal dividieren.
Das heißt, für ein spezielles Polynom kann ich wesentlich anders den
Wert berechnen, als für ein allgemeines Polynom.
Also hier habe ich zwei einfache Additionen, Subtraktionen, eine
Potenzierung, eine Division.
Und vorher bei dem Horner Schema, bei dem ich sagte, das ist optimal,
hatten wir n Additionen, n Multiplikationen, also das geht hier
deutlich einfacher.
Aber das ist auch kein allgemeines Polynom, da kenne ich vorher die
Koeffizienten und weiß, ich muss genau dieses Polynom häufig ausführen
und dann mache ich das bestmöglich.
Wenn ich aber vorher nicht weiß, welches Polynom tatsächlich zu
verwenden ist, sondern ich bekomme diese Koeffizienten als Eingabe
geliefert, dann muss ich sehen, wie ich damit zurechtkomme.
Und dann ist das Horner Schema ein sehr gutes Verfahren.
Und das schauen wir uns dann nächstes Mal genauer an.
Tut mir leid, dass es heute so ein bisschen gestört war.
Der neue Beamer hat mich hier empfindlich gestört.
Ich hoffe, dass wir daraus noch einigermaßen eine vernünftige
Aufzeichnung hinbekommen.
Vielen Dank für die Aufmerksamkeit.