Also, ich begrüße Sie zur Fortsetzung der Forschung effizienter
Algorithmen.
Wir hatten ja eine Woche Pause, machen dafür nächste Woche dann einen
Sondertermin.
Da kommt noch ein Mitarbeiter.
Hallo, Herr Brotmann.
Sie haben den Aufgabenzettel?
Das ist ich.
Sehr gut.
Neue Aufgaben.
Also, letztes Mal haben wir uns mit den Rechnungsmodellen noch
beschäftigt gehabt.
Ich hatte Ihnen ja einiges da vorgestellt.
Wir hatten verschiedene Varianten angeschaut dieser
Berechnungsmodelle.
Ich hatte Ihnen ein Beispiel gegeben für ein Programm auf der Random
Access Machine.
Das ist ja so das Standardmodell als Basis für die Bewertung von
Algorithmen.
Da ist nochmal eine Aufgabe auf dem Aufgabenzettel, dass Sie da
nochmal ein Programm schreiben sollen.
Einfach um nochmal zu sehen, wie man halt dafür, wie man dort auch
dann Laufzeiten abschätzt und so.
Ich denke, das ist eine relativ einfache Geschichte, eine sehr
einfache Aufgabe, Maximumsberechnung.
Ich hatte dann gezeigt, insbesondere die Unterschiede zwischen den
verschiedenen Kostenmodellen.
Wir waren dann weitergegangen, hatten uns angeschaut, wie man etwas
vereinfachen kann, hatten die geradlinigen Programme angeschaut,
hatten die Entscheidungsbäume angesehen und anschließend haben wir
unterschiedliche Klassifikationen von Algorithmen vorgenommen.
Insbesondere haben wir geguckt, wie kann man eigentlich sequenzielle
Algorithmen jetzt besonders charakterisieren.
Ein Beispiel war die Matrix-Multiplikation.
Dann haben wir uns die parallelen Algorithmen hergenommen, auch dort
die Matrix-Multiplikation als Beispiel genommen, wo man hier sehr
schön sehen kann, dass man Dinge parallelisieren kann, also die
unabhängigen Operationen, dass es aber eben häufig auch Abhängigkeiten
gibt, wie hier dieses Fan-In bei der Berechnung der Summe, die man
eben durchaus auch parallelisieren kann.
Aber da habe ich halt durch diesen Additionsraum eine Tiefe von Log N
Schichten.
Und wo auch ich Sie auch hingewiesen hatte, waren natürlich die, wenn
man sich anguckt, wie viel Informationen fließen eigentlich dort
zwischen den verschiedenen Prozessoren hin und her, das sind im
Prinzip zwei N hoch drei Nachrichten, die verschickt werden müssen
zwischen den einzelnen Berechnungseinheiten, was man natürlich auch
als Aufwand zählen kann.
Also es ist klar, dass der Gesamtaufwand nicht kleiner ist, als wenn
ich einen sequentiellen Algorithmus habe, vielleicht sogar insgesamt
etwas größer, weil ich Kommunikation noch stärker machen muss, aber
die Anzahl der Schritte sind halt deutlich reduziert und das ist das
Wichtige bei den parallelen Algorithmen.
Dann haben wir uns noch angeschaut, wo waren wir dann, bei den
verschiedenen Modellen für Parallelrechner, die PRAM mit
Speichermodellen, also verteilter Speicher, gemeinsamer Speicher,
verschiedene Zugriffsmodelle, exklusiven Zugriff auf den Speicher oder
gemeinsamen Zugriff auf den Speicher, was für das Lesen kein Problem
ist, für das Schreiben Konfliktlösungen bedeutet und wir hatten
gesehen, es gibt natürlich für die Verbindung zwischen einzelnen
Prozessoren sehr unterschiedliche Möglichkeiten, verschiedene
Verbindungsstrukturen wie Brustring oder Baum oder Gitter oder Torus
oder Crossbar oder Fairtree oder ähnliches, also eine Vielfalt
verschiedener Verbindungsstrukturen, die selbstverständlich alle ihre
Auswirkungen haben auf die Leistungsfähigkeit der verschiedenen
Rechner und die man natürlich bei der Entwicklung von Algorithmen auch
berücksichtigen muss.
Und das heißt, ich muss dann beim Entwurf von Algorithmen eigentlich
wissen, wo werden die voraussichtlich ausgeführt, weil ich dann
eventuell etwas optimieren kann bezüglich solcher
Verbindungsstrukturen.
Eigentlich etwas, was man gar nicht möchte.
Ich möchte eigentlich ein Problem lösen, also irgendeine Lösung
überlegen und wie das dann am besten auf einer bestehenden
Hardwarestruktur ausgeführt wird.
Das sollte eigentlich irgendwie automatisiert sein.
Das ist das, was wir eigentlich so im Kopf haben.
Deswegen muss man sehen, wie kann man sowas systematisch machen.
Damit werden wir uns beschäftigen.
Und wie gesagt, eigentlich ist es so, dass ich mich als Anwender
möglichst wenig um die parallelen Strukturen kümmern möchte.
Ich möchte eigentlich meine Lösungen möglichst allgemein hinschreiben
und der Rest muss dann irgendwie erledigt werden.
Und wenn der Rest irgendwie erledigt werden muss, muss ich dafür auch
Werkzeuge haben und die schreiben natürlich Informatiker.
Und da sind wir wieder dabei.
Also müssen wir, wenn wir uns mit Informatik beschäftigen, auch
wissen, wie man sowas macht, wie man solche Strukturen ausnutzt.
Und wenn man einen speziellen Rechner zur Verfügung hat, macht es eben
auch Sinn, sich anzugucken, wie kann ich diesen speziellen Rechner
jetzt möglichst sinnvoll ausnutzen.
Es gibt am Rechenzentrum hier sehr schöne Parallelrechner.
Sie werden zukünftig in Ihren Laptops vielleicht irgendwelche
Multicore -Prozessoren haben.
Und deswegen macht es durchaus Sinn, sich solche Dinge anzugucken.
Aber es ist so ein bisschen so ein Zwiespalt zwischen einer zu starken
Orientierung auf eine spezielle Hardware-Struktur und einer etwas
allgemeineren, generischeren Art, ein Problem zu lösen.
Das nächste, was wir dann angucken werden heute, sind die Hardware
-Algorithmen.
Da kommen wir jetzt zum nächsten neuen Folie für heute.
Also Hardware-Algorithmen.
Da geht es im Prinzip auch um Parallelität.
Also wir haben hier durchaus auch etwas mit Parallelität zu tun.
Aber darüber hinaus geht es eben auch um ein Prinzip, das wir schon
lange kennen.
Das habe ich Ihnen in den Grundlagen der Informatik 2 sehr
nachdrücklich vorgestellt.
Oder wenn Sie eine andere Vorlesung gehört haben, dann haben Sie es
dort wahrscheinlich gehört, wenn es um Hardware ging.
Das ist halt das Problem des Pipelining oder der
Fließbandverarbeitung.
Das heißt, wenn ich mehrere Berechnungen ausführen möchte, kann ich
sie so nacheinander ausführen.
Ich kann sie aber genauso gut im Pipelining-Verfahren ausführen,
sofern ich genügend redundante Hardware zur Verfügung habe.
Wenn ich eben mehrere solcher Berechnungen überlappend machen kann.
Und das Interessante ist eben, dass ich bei einer wiederholten Lösung
eines Problems mit unterschiedlichen Daten dann die einzelnen
Bearbeitungen für diese unterschiedlichen Datensätze sehr fein
getaktet anfangen kann.
Das heißt, ich habe dann hier im Prinzip sehr kleine Zeiteinheiten
aufeinander folgend.
Ein Beginn von neuen Berechnungen.
Und so etwas brauche ich zum Beispiel in der Signalverarbeitung, wenn
Sie irgendwelche Signale verarbeiten, wie zum Beispiel Fernsehbilder
oder sonst irgendwelche Satellitenbilder oder ähnliche
Satellitendaten.
Da müssen Sie eine bestimmte Bearbeitungsfrequenz aufrechterhalten,
also einen bestimmten Durchsatz garantieren.
Und wie lang dann tatsächlich die einzelne Berechnung dauert, ist dann
gar nicht mehr so relevant.
Eine gewisse Verzögerung insgesamt kann man tolerieren, aber nicht
einen Abfall in der Bearbeitungsrate, in der Anzahl der Berechnungen
pro Zeiteinheit.
Und das ist halt da der wesentliche Punkt.
Also eine Kombination von Pipelining und Parallelität.
Und Parallelität führt dann halt zur Verkürzung der Laufzeit der
einzelnen Berechnung.
Das Pipelining erhöht den Durchsatz.
Und ich gebe Ihnen hierzu ein paar Beispiele.
Wir werden zu denen dann wieder zurückkommen in späterer Stelle.
Ich werde Ihnen gleich Adderer und Modifizierer vorstellen oder
Matrixmodifizierer.
Und was das Berechnungsmodell angeht, habe ich hier folgendes.
Ich habe im Prinzip einen Rechnergraphen, der die Struktur angibt.
Den Platz frei, den brauche ich jetzt auch.
Also ich habe einen Rechnergraph, der gibt eine Struktur an.
Nehmen wir mal an, wir haben einen Baumrechner.
Also kein Problem.
Wir können ja problemlos einen Baumrechner aufmalen.
Das wäre so ein Rechnergraph für einen.
Und Sie können natürlich noch beliebig weiter Knoten hier vorstellen.
Das ist jetzt die Struktur.
Der Graph, der nur sagt, welche Rechnungsknoten habe ich und wie sind
die verbunden.
Dann brauche ich aber auch ein Layout.
Und wenn Sie sich das Layout angucken für einen Baum, dann ist das gar
nicht so einfach.
Gar nicht so naheliegend, wie man das macht.
Ich habe Ihnen jetzt hier einfach einen hingemalt.
Das ist schon ein Layout.
Aber wenn Sie das jetzt auf dem Rechner tatsächlich machen oder auf
dem Chip tatsächlich anordnen wollen, ist die Frage, wie man das
macht.
Also ich hatte hier 1, 2, 3, 4, 5, 6, 7, 8 Knoten.
Also 1, 2, 3, 4, 5, 6, 7, 8.
Ich nehme mal an, dass ich dort Dinge ausgeben will.
Die ordne ich mal so einfach nebeneinander an.
Das waren jetzt meine Blätter meines Baumes.
Jetzt sind die jeweils verbunden mit einem anderen Knoten.
Das könnte ich natürlich einfach so machen, dass ich hier jeweils so
die nächste Ebene anordne.
Nicht nah, wenn Sie das in Mikroelektronik machen, sind Leiterbahnen
normalerweise rechtwinklig oder wenig diagonal.
Vielleicht mal diagonal, aber in der Regel macht man das rechtwinklig.
Jetzt habe ich ja wieder die nächste Ebene, muss ich wieder irgendwie
verbinden.
Naja, kann ich ganz systematisch weitermachen.
Dann habe ich hier die nächsten...
Ups, der hat sich automatisch verbunden, den wollte ich gar nicht
verbinden.
Jetzt hat er hier irgendwas gemacht.
Okay, das hat nochmal gut gegangen.
Jetzt habe ich also den so weit und jetzt muss ich halt nochmal das
hier fertigstellen.
Was Sie jetzt sehen, bei diesem Layout, was ich Ihnen hier gemalt
habe, das ist genau das Layout eines Baumes, den ich hier oben drüber
hatte.
Sehr systematisch.
Und wie sieht das mit der Fläche aus, die ich dafür brauche.
Offensichtlich habe ich hier, gerade wenn ich also N Blätter habe, Log
N Schichten.
Das heißt, ich habe hier eine Höhe von Log N.
Und ich habe hier meine N Blätter.
Also habe ich hier N mal Log N als Fläche.
Ein weiterer Punkt ist, ich habe zum Teil sehr kurze Leitungen.
Also diese Leitung hier ist relativ kurz.
Diese Leitung hier, die ist lang.
Und zwar die Länge von N halbe.
Leitungslängen spielen bei Zeitverhalten von Schaltkreisen eine ganz
wichtige Rolle.
Gerade wenn man immer stärker miniaturisiert, über lange Leitungen
können Sie Signale nur deutlich langsamer transportieren als über
kurze Leitungen.
Insbesondere, wenn man das richtig anschaut, wenn man es ganz genau
physikalisch modelliert, ist es so, dass die Signallaufzeit
quadratisch mit der Länge wächst.
Wenn man das ein bisschen geschickt modelliert, kommt man auf lineare
Laufzeit.
Mit gewissen Annahmen geht man manchmal auch davon aus, dass man sogar
Log Länge Laufzeit hinkriegen kann.
Aber das realistische Modell ist eigentlich, dass man sagt, ich habe
lineare Laufzeit auf den Leitungen.
Und das heißt, wenn ich eine lange Verbindungsleitung habe, bestimmt
die Zeit für den Transport der Informationen über diese lange Leitung
über meine Taktfrequenz.
In meiner Berechnungsstruktur.
Und selbst wenn ich hier nur Log N Schritte mache, für eine
Berechnung, jeder einzelne Schritt dauert Zeit N.
Größenordnung N, weil die Leitungslänge N ist, hätte ich auf einmal N
Log N als Zeit.
Ganz schlimm.
Aber das zeigt nur, die Leitungslänge spielt eine Rolle, das Layout
spielt eine Rolle bei der Fläche und auch beim Zeitverhalten.
Deswegen muss man sich das halt genauer angucken.
Es kann ja sein, es geht ja noch viel besser, so einen Baum zu malen.
Ich kann ja z.B.
den so malen.
Ich ordne hier die
an.
Das ist ein Baum mit vier Knoten.
Quatsch, mit vier Blättern.
Jetzt mache ich hier noch den Baum.
Malte mir hier eine Funktion, die so nicht gewünscht ist.
Der geht einfach weiter.
Also, ich kann hier noch einen solchen Baum daneben malen.
Jetzt kann ich im Prinzip das gleiche hier unten noch malen.
Jetzt kann ich leider das hier unten nicht so richtig fortführen, aber
ich mache das gleiche hier unten noch malen.
Stellen Sie sich vor, Sie haben da den gleichen Baum noch mal unten
drunter gespiegelt.
Dann hätten wir schon vier Bäume mit jeweils vier Blättern, also 16
Blätter insgesamt.
Und jetzt kann ich die einfach verbinden, die jeweils.
Was ich dann bekomme, ist eine Struktur, die sieht so aus.
Ich habe hier
solche Bäume und habe die so verbunden.
Das kann ich natürlich darunter noch mal bauen.
Und entsprechend könnte ich das daneben noch mal bauen.
Ich male das jetzt einfach mal hin.
Also, Problem offensichtlich mit Office 2007.
Diese zwei Pfeile darin sollten eigentlich nicht da sein.
Kann ich jetzt aber hier mit einbauen.
Sie sehen, ich habe hier viele Haars ineinander gewirbelt.
Warum mache ich das?
Wie groß ist denn jetzt die Fläche?
Wenn ich N Blätter habe, die sind quadratisch angeordnet, also die
Fläche meines ganzen Layouts dieses Baumes hier.
Die Fläche ist jetzt N, Größenordnung N.
Das heißt, diese Länge hier, die Seitenlänge, ist Wurzel N.
Ich habe also jetzt eine Gesamtfläche von N, Größenordnung N.
Und die Leitungslänge, die größte Leitungslänge habe ich hier, das ist
Größenordnung Wurzel N.
Also deutlich reduziert.
Das zeigt nur, ich kann Bäume sehr unterschiedlich anordnen und
bekomme dadurch unterschiedliche Flächen, unterschiedliche
Randbedingungen für das Zeitverhalten.
Deswegen ist also Layout ein ganz wichtiges Thema.
Muss man sich angucken.
Und hat also bei Hardware-Algorithmen einigen Einfluss auf das
Leistungsverhalten eines Algorithmus.
Dann haben wir als drittes das IOO-Schema.
Was ist ein IOO-Schema?
Das gucken wir uns jetzt am Beispiel an.
Die Ripple-Carry-Adder kennen Sie im Prinzip, wenn Sie meine Vorlesung
Grundlagen -Informatik 2 gehört haben.
Einfaches Beispiel, wir wollen zwei Zahlen addieren und machen das
halt mit einem Ripple-Carry-Adder.
Ich habe also einen Algorithmus, wo der Graph besteht aus diesen
kleinen Input, das sind die Input-Knoten.
Hier habe ich Output-Knoten, also diese kleinen Kringelchen.
Und ich habe auch noch logische Knoten.
Das sind jeweils diese Quadrate, jeweils Funktionen, Volladdierer und
das Ganze soll schön getaktet sein.
Die Verbindungsstruktur, die Verbindung zwischen den Knoten ist
eindeutig trivial.
Also der Graph ist trivial, ganz einfach.
Das Layout auch, kann man so machen.
Man kann auch andere Anordnungen wählen, wenn man möchte, aber das ist
ein naheliegendes Layout, einfaches und lineares Layout.
Das I.O.-Schema dafür, wie sieht das aus?
Ich möchte ja Zahlen addieren, also irgendwie A und B addieren, die
jeweils hier in diesem Beispiel 4 Bit haben.
Und jetzt gebe ich die halt der Reihe nach ein.
Und weil die Strukturen gleichartig sind, habe ich hier noch eine
Eingabe für einen gewissen Übertrag.
Der kann, der ist normalerweise 0.
Also die niedrigwertigen Bits werden halt mit dem Übertrag 0 addiert.
Und dann habe ich halt hier meine ersten beiden, im ersten Takt die
ersten beiden da reingenommen.
Die ersten beiden Bits, die werden addiert.
Ich habe die zweiten Bit der schwarzen Addition im zweiten
Volladdierer.
Die ersten Bits der blauen Addition im ersten Volladdierer.
Und so weiter läuft das hier durch.
Dann habe ich irgendwann alle vier Volladdierer aktiviert.
Die jeweils auf verschiedenen Bit-Positionen von vier Additionen
arbeiten.
Und habe dann also irgendwann diese verschiedenen Additionen alle
ausgeführt.
In einem Pipelining-Verfahren.
So, das ist jetzt nochmal insgesamt angedeutet das IRO-Schema.
Ich habe halt zeitversetzt die Eingaben für die einzelnen, also die
einzelnen Bits für die einzelnen Additionen.
Eine schwarze Addition, eine blaue, eine rote, eine grüne hier so
angedeutet.
Und ich kann im Pipelining-Verfahren jeden Takt eine Berechnung
beginnen.
Bekomme also in jedem Takt ein Ergebnis geliefert.
Allerdings die einzelne vollständige Addition dauert halt so viele
Takte wie ich Bits in meinen Zahlen habe.
Also lineare Laufzeit für die Addition, aber hohen Durchsatz, weil ich
eine sogenannte konstante Periode habe.
Also konstanten Abstand zwischen aufeinanderfolgenden Berechnungen.
Ich kann das sogar noch flexibler einsetzen.
Ich könnte hier diese Bits noch anders setzen.
Ich könnte dort den Endübertrag einer Berechnung von der Ausgabeseite
hernehmen.
Und könnte dadurch auch längere Zahlen als 4-Bit-Zahlen mit so einem 4
-Bit -Addierer addieren, indem ich einfach den Endübertrag vorne
wieder reinspiele und dann die nächsten 4 Bits einer Zahl dort
einbaue.
Und könnte dann entsprechend so einen 4-Bit-Addierer auch verwenden
für die Addition von längeren Zahlen.
Geht also problemlos.
Aufwand, wie gesagt.
Die Zeit für eine einzelne Berechnung ist halt die Zeit von Beginn der
Berechnung bis zum Ende der Berechnung.
Das ist natürlich Größenordnung n.
Die Fläche ist auch Größenordnung n.
Der Abstand zwischen zwei aufeinanderfolgenden Berechnungen, die
Periode, ist konstant, ein Takt.
Und der Durchsatz ist halt groß.
Der Durchsatz ist n.
Ich habe n Berechnungen gleichzeitig im Prinzip in Arbeit.
Gut.
Nächstes Beispiel.
Matrix-Modifikation.
Das kennen Sie noch nicht, das Beispiel.
Das ist das Standardbeispiel eines sogenannten systolischen
Algorithmus.
Und ein systolischer Algorithmus heißt dann, wie beide hier oben
genannten Autoren so ausgedacht haben, 1979, 30 Jahre her immerhin
schon, ein Algorithmus, bei dem im Prinzip Daten durch ein Netzwerk
von Prozessoren oder von Recheneinheiten gepumpt werden.
Und weil das ein bisschen Ähnlichkeit hat, sehr abstrakt gedacht, mit
einem Blutkreislauf, wo Blut durch Adern gepumpt wird, haben die
gesagt, das ist ein systolischer Algorithmus.
Das steht eben dafür, dass man Daten durch ein Netzwerk von
Recheneinheiten pumpt.
Es geht hier um die Multiplikation von Matrizen, das Beispiel kennt,
die Matrix-Modifikation kennen Sie inzwischen.
Und in diesem Fall geht es um die Multiplikation von Bandmatrizen.
Was sind Bandmatrizen?
Da sehen beide Matrizen so aus, dass sie nur ein relativ schmales Band
von Nicht-Nullwerten haben.
Und das heißt, ich habe dann eigentlich nur in diesem Bereich, der
jetzt hier schraffiert angedeutet ist, nur da stehen die relevanten
Zahlen.
Und die Breite dieses Feldes, das hier angedeutet ist, ist gerade so,
dass die Bandbreite der Matrizen hier berücksichtigt ist.
Da können alle notwendigen Operationen darauf gemacht werden.
Und was wird dort konkret gemacht, in diesem Feld von sechseckigen
Prozessoren?
Der einzelne Prozessor sieht so aus, wie hier angedeutet ist.
Der soll genau diese Basis-Operation eines Skalarprodukts berechnen.
Das Skalarprodukt, das berechnet wird, ist ja a i k mal b k j.
k gleich 1 bis n.
Also jedes c i j wird ja so berechnet.
Und das heißt, ich muss im Prinzip immer solche a's und b's
multiplizieren.
Man kann das eben sequenziell machen, indem ich der Reihe nach die so
aufaddiere.
Das ist immer eine Berechnung und dann aufaddieren.
Und meine kleinen Zellen sehen so aus, dass die jetzt hier von links
oben das a bekommen, von rechts oben das b, von unten das c, den alten
Zwischenwert, und wird also auf das c das Produkt von a und b
draufaddiert.
Und jede Zelle dort drin hat genau diese Funktion.
Und wie läuft das Ganze jetzt?
Wir haben hier unsere Matrizen, die eingegeben werden.
Hier habe ich jetzt sogar keine Bandmatrizen, sondern volle Matrizen
drin.
Also in diesem Fall sind das 8x8 Matrizen.
Sieht so aus.
Nein, Quatsch, das sind doch Bandmatrizen.
Das sind Bandmatrizen, die Bandbreite ist...
...entsprechend sind das hier...
...Bandbreite ist 4 und ich habe dann bei dem Produkt der beiden ist
die Bandbreite größer.
Die wird größer bei dem Produkt der beiden Matrizen, an der Bildung
des Skalarprodukts.
Was habe ich hier angedeutet?
Ich habe die Situation, dass von hier kommt die Matrix A, von dort
kommt die Matrix B, von unten die Matrix C.
Und so ist das Element A11 hier schon in die Mitte gewandert.
Von links, von rechts oben, das Element B ist auch dort in die Mitte
gewandert.
Also über diesen Weg hier im Prinzip.
Über den Weg und über diesen Weg sind die Elemente A, B und C dadurch
gewandert.
Vorher waren die Zellen alle leer.
Da sind also nur Nullen drin.
Und jetzt ist der erste Zeitpunkt, wo hier A11 und B11 modifiziert
werden.
Und im nächsten Takt soll nun auf das A11 mal B11, natürlich A12 mal
B21 drauf addiert werden.
Die beiden, sehen Sie, stehen aber schon dort bereit.
Und im nächsten Takt wandern die also jeweils eine Zelle weiter, genau
in die Zelle zwischen diesen drei, die dort steht.
Das heißt, dann berechne ich A11 mal B11 plus A12 mal B21.
Im nächsten Takt habe ich hier drin A13 und B31.
Die kommen wieder auf die Zwischensumme drauf.
Und danach kommen hier A14 und B41.
Die werden wieder drauf addiert.
Und dann habe ich im Prinzip mein C11 fertig berechnet.
Und so habe ich dann hier das erste Ergebnis.
Und so läuft das Ganze weiter.
Und damit kann ich dann sukzessive meine Berechnungen durchlaufen
lassen.
Das ist wieder der Anfangszustand jetzt, nochmal angedeutet.
Und ich habe also einen Algorithmus, bei dem ich etwas parallel mache.
Also diese Zellen arbeiten alle parallel, wobei man sieht, dass immer
nur ein Drittel der Zellen konkret etwas zu tun haben.
Die anderen machen keine sinnvollen Berechnungen.
Und dann könnte man natürlich noch etwas dazwischen schieben.
Ich könnte noch weitere Berechnungen da reinschieben.
Das habe ich jetzt aber nicht mit drin.
Ich könnte aber problemlos hier drin noch eine weitere Matrix
einschieben.
Und noch eine weitere Matrix.
Da ist Platz für zwei weitere Berechnungen, die ich versetzt jeweils
hier durchlaufen lassen kann.
Die laufen dann alle schön aneinander vorbei.
Ich könnte im Prinzip drei Berechnungen leicht überlappt ausführen.
Das heißt, das würde dann so aussehen, dass ich hier eine lange
Berechnung habe, noch eine lange Berechnung, noch eine lange
Berechnung.
Dann ist Schluss, dann ist mein Feld voll.
Und dann kann ich irgendwann hier wieder so weitermachen, die nächsten
drei Berechnungen.
Auch eine Art Pipelining, aber eben ein beschränktes Pipelining.
Ich kann drei Berechnungen überlappend ausführen.
Das reduziert dann den mittleren Abstand zwischen aufeinanderfolgenden
Berechnungen.
Ich hätte also zweimal den Abstand 1 und dann wieder den Abstand
Größenordnung n zwischen den Berechnungen.
Also hier den etwas größeren Abstand und hier hätte ich also drei
Berechnungen sehr kurz nacheinander.
Die Fläche für diesen Algorithmus wäre quadratisch.
Wie gesagt, Periodeabstand zwischen aufeinanderfolgenden Berechnungen
wäre n.
Die Zeit, auch Größenordnung n.
Es dauert, ich muss ja nicht nur einmal so durchschieben, das Band
muss einmal durch und dann bin ich im Prinzip fertig.
Also das ist ein klassischer Hardware-Algorithmus für Matrix
-Multiplikation.
Diese Bandmatrizen tauchen in technischen Anwendungen häufig auf.
Deswegen ist es etwas, was in technischen Anwendungen auch tatsächlich
in Schaltkreisen so eingesetzt wird.
So, jetzt habe ich Ihnen gezeigt diese Vielfalt von verschiedenen
Berechnungsmodellen, die alle sich auswirken auf die Art, wie ich
Algorithmen entwerfe.
Da muss ich natürlich den Berechnungsaufwand charakterisieren.
Das hatten wir uns schon mal überlegt.
Bei sequenziellen Algorithmen ist es klar, da ist es einfach nur Zeit
und Platz.
Bei parallelen Algorithmen kann ich ein bisschen mehr angucken.
Selbstverständlich auch wieder Zeit und Platz.
Aber Zeit bei parallelen Algorithmen ist in dem Fall dann eben die
Anzahl der Schritte oder Anzahl der Takte, die ich ausführen muss.
Und ich kann eben in jedem Schritt oder Takt eventuell mehrere
Operationen gleichzeitig machen.
Der Platz könnte sein Anzahl der Speicherzellen pro Prozessor.
Dann brauchen wir dazu natürlich etwas, was auch noch mit Platz zu tun
hat, nämlich die Anzahl der Prozessoren.
Das geht ja auch in die Fläche, also wäre Platz und Parallelitätsgrad
etwas.
Wobei der Parallelitätsgrad die Anzahl gleichzeitig aktiver
Prozessoren ist.
Jetzt überlegen Sie nochmal kurz hier unser Beispiel mit der
Berechnung eines Skalarprodukts oder so einer Summe.
Da hatte ich zu Beginn mehrere parallel ausführbare Multiplikationen.
Bei der Matrixmultiplikation konnten bis zu N hoch 3 Multiplikationen
gleichzeitig gemacht werden, weil sie unabhängig voneinander sind.
In jedem weiteren Schritt sank aber die Anzahl der gleichzeitig
ausführbaren Operationen.
Das heißt, wenn ich über Parallelitätsgrad rede, dann kann ich reden
über den Maximalparallelitätsgrad, der auftritt in einer Berechnung.
Das deutet nämlich an, wie viele Prozessoren ich zur Verfügung stellen
muss.
Es kann aber sein, dass ich irgendwann eine Berechnung habe, wo nur
noch ein Prozessor aktiv ist.
Da sind die anderen halt unbeschäftigt.
Und deswegen muss man sich anschauen, was gewinne ich eigentlich
dadurch, dass ich mehrere Prozessoren einsetze.
Und wie kann ich das ausdrücken?
Ich schaue mir einen Algorithmus an mit einem Prozessor oder mit zehn
Prozessoren.
Der Zeitgewinn, wenn ich Glück habe, ganz naiv, spontan gesagt, wäre
doch sicherlich mal okay.
Zeit muss um ein Zehntel runter.
Was Sie sich hier schon überlegen können ist, das wird so nicht wahr
sein.
Das funktioniert nicht.
Das geht nur, wenn die Berechnungen alle unabhängig sind.
Was ich mir also anschauen muss, ist die Zeit mit einem Prozessor.
Das wäre hier dieses T1.
Und die Zeit mit P-Prozessoren.
Ist aber auch nicht ganz so einfach.
Wenn Sie Literatur schauen, sehen Sie manchmal solche Abschätzungen.
Ich nehme einen Algorithmus, führe den mit einem Prozessor aus oder
mit 100 Prozessoren.
Ich stelle fest, ich habe einen Zeitgewinn.
Ich muss aber vergleichen, die optimale sequenzielle Zeit mit der Zeit
meines parallelen Algorithmus der P-Prozessoren verwendet.
Denn es könnte sein, dass die Algorithmen völlig anders strukturiert
sind.
Es könnte sein, dass der optimale sequenzielle Algorithmus eine völlig
andere Struktur hat, als ein guter Paralleler mit P-Prozessoren.
Das heißt, ich muss also wirklich die optimale sequenzielle Zeit
nehmen.
Ich kann nicht, wenn ich Bubble Sort parallelisieren möchte...
Bubble Sort hat eine Zeit von n².
Mit n Prozessoren kann ich das auf lineare Zeit runterdrücken.
Zeitgewinn von n, ganz fantastisch.
Stimmt aber nicht.
Der Zeitgewinn ist nicht n, sondern ich muss vergleichen die Zeit für
die parallele Ausführung von Bubble Sort mit der optimalen
sequenziellen Zeit und die ist n log n.
Und das heißt, ich habe dann n log n durch n zu dividieren.
Das heißt, der Zeitgewinn ist nur noch log n und nicht n.
Und entsprechend kann ich mir die Effizienz anschauen.
Die Effizienz sagt jetzt, wie gut ich eigentlich die Ressourcen
ausgenutzt habe bei der Erzielung dieses Zeitgewinns.
Also, der Zeitgewinn war das sp.
s steht übrigens für Speed Up.
Deswegen s.
Und dieser Zeitgewinn wird anteilig gesehen pro Prozessor.
Mein Parallelitätsgrad p.
Und das heißt, ich habe hier im Prinzip meine optimale sequenzielle
Zeit im Verhältnis zu p mal parallele Zeit.
Und p mal parallele Zeit wird nicht kleiner sein als die optimale
sequenzielle Zeit.
Deswegen ist der Zeitgewinn, also immer kleiner gleich p, bzw.
die Effizienz kleiner gleich 1.
Sie finden allerdings manchmal etwas, das nennt sich dann Superlinear
Speed Up.
Also dieser von selbst entstehende senkrechte Strich ist wirklich
ärgerlich.
Ich erspare es mir jetzt, ihn wegzulöschen, weil ansonsten das schon
wieder hier an der Folie weiterspringt.
Superlinear Speed Up gibt es manchmal auch, z.B.
bei Branch-and-Bound-Verfahren, wenn man die parallelisiert, redet man
häufig von Superlinear Speed Up, weil ich eventuell einfach früher
abbrechen kann und nicht alles das, was ich bei einem sequenziellen
Algorithmus, beim sequenziellen Branch-and-Bound machen muss, gar
nicht ausführen muss, weil ich schon früher den Punkt finde, an dem
ich abschneiden kann.
Deswegen findet man dort manchmal einen Superlinear Speed Up.
Das sind Sonderfälle.
Normalerweise gelten diese Grenzen.
Der Zeitgewinn kann nicht größer sein als P und die Effizienz ist
höchstens 1.
Ich kann also jeden Prozessor höchstens vollständig eingesetzt haben
für die Erzielung dieser Parallelität oder dieser kürzeren Zeit.
Und das Wesentliche ist eben, dass man auch immer guckt, vergleiche
ich wirklich mit der optimalen sequenziellen Zeit.
In Aussagen über Superlinear Speed Up wird eben manchmal dann auch
nicht mit der optimalen sequenziellen Zeit verglichen, sondern mit der
Zeit, die der gleiche Algorithmus mit einem Prozessor brauchte.
Und das kann eben dann dazu führen, dass man sagt, ich habe einen
Superlinear Speed Up manchmal.
Okay.
Das Letzte, was ich hier noch aufführe, ist die Skalierbarkeit und das
ist auch ein ganz wichtiges Thema.
Ich habe einen Algorithmus ausgeführt mit 16 Prozessoren.
Jetzt habe ich mehr Geld und schaffe mir 32 Prozessoren an oder 128
oder was immer.
Größere Zahl.
Und ich erwarte natürlich, dass die Laufzeit weiter runter geht.
Nur deswegen mache ich es ja.
Aber nicht jeder Algorithmus ist so gestrickt, dass er tatsächlich
skalierbar ist, in dem Sinne, dass sich das Verhalten auch verbessert,
wenn ich mehr Prozessoren nehme.
Damit das passiert, müssen die Algorithmen entsprechend gebaut sein.
Und genauso ist es so, dass wenn ich jetzt größere Problemgrößen
nehme, soll natürlich das Ganze auch entsprechend skalieren.
Und das ist nicht notwendigerweise der Fall.
Es gibt manchmal Algorithmen, die nur für spezielle Problemgrößen ein
gewisses Zeitverhalten haben und bei anderen halt, wenn ich einfach
Sprünge habe, dann im Zeitverhalten.
Da muss man aufpassen.
Also Skalierbarkeit hat was damit zu tun, inwieweit ich die
Randbedingungen meiner Rechnerstruktur verändern kann oder auch meiner
Problemstellung und trotzdem noch ein gleichartiges Verhalten habe.
Das heißt, ich kann Erkenntnisse für eine spezielle Problemgröße oder
einen speziellen Parallelitätsgrad übertragen auf andere, also
verallgemeiner.
Und dann haben wir noch bei Hardware-Algorithmen, hatte ich Ihnen
deutlich gesagt, zusätzlich den Flächenbedarf und den Pipelining-Grad.
Das werden wir aber nicht so sehr intensiv noch weiter angucken.
Ich kann nicht alles in dieser Vorlesung machen, aber ich muss darauf
hinweisen, dass bei Berechnungsaufwand man genau gucken muss, wo führe
ich eigentlich den Algorithmus aus, auf welchem Berechnungsmodell.
Das gibt mir dann eigentlich alles das, was ich mir tatsächlich
angucken muss, wenn es um die Kosten geht.
Jetzt haben wir noch eine Art von Algorithmen, die ich Ihnen bisher
nicht angesprochen habe.
Das sind die verteilten Algorithmen, bei denen ich jetzt eine Menge
sequenzieller Prozesse ausführe, die unabhängig voneinander arbeiten
und die kommunizieren.
Also es kann sein, dass sie nicht ganz unabhängig voneinander arbeiten
können, dass sie gewisse Informationen austauschen müssen.
Und das müssen sie durch Kommunikation machen.
Und das macht man normalerweise eben auf einem verteilten System, z.B.
allen Rechnern hier in der Uni oder im Internet.
Grid Computing, Cloud Computing sind so typische Ideen dafür.
Sie haben verteilte Rechner, haben leistungsfähige Prozessoren und sie
verteilen ihre Berechnung auf diese leistungsfähigen Prozessoren.
Stellen Sie sich vor, Sie haben also hier irgendwelche schönen Rechner
und der eine hat sogar so eine schöne Spitze noch dran.
Und jetzt wollen die irgendwelche Berechnungen ausführen.
Sie wollen eine Matrix-Multiplikation machen.
Wenn Sie das so machen würden, wie ich Ihnen das vorher vorgestellt
habe, indem Sie jetzt meinetwegen hier die einzelnen Zahlen zwischen
den verschiedenen Prozessoren jetzt hier hin- und herschieben, wie
immer die auch verbunden sein mögen, Sie hätten sehr viel
Kommunikation.
Und wenn Sie mal gemessen haben, wie lange ein Ping dauert zwischen
zwei Rechnern, das kann man ja einfach machen, indem man über die
Command -Seile bei Windows einfach mal einen Ping macht, dann sieht
man, wie viele Millisekunden das dauert.
Das sind halt Millisekunden.
Die Taktfrequenz des Rechners liegt aber im Nanosekundenbereich, die
einzelnen Takte.
Das heißt, Sie können Hunderttausende von Operationen machen in der
Zeit, in der Sie zwischen zwei Prozessoren Informationen austauschen.
Und das zeigt sofort, wenn Sie Kommunikation machen müssen zwischen
Prozessoren in einem verteilten System, dann kostet das sehr viel
Geld, sehr viel Zeit.
Es ist besser, Dinge lokal zu machen.
Das sind auch heterogene Netze, also heterogene Prozessoren, und
deswegen sagt man, die Aufwandsbewertung bei solchen verteilten
Algorithmen bezieht sich eigentlich nur auf die Anzahl der
Nachrichten.
Auf dem einzelnen Prozessor kann ich eigentlich ziemlich viel rechnen,
in der gleichen zeitlichen Größenordnung wie für Kommunikation.
Jetzt sage ich trotzdem, ich möchte gerne den Kommunikationsaufwand
hinter Berechnungen verstecken.
Das nennt man Communication Hide.
Also, das kann ich natürlich nur machen, wenn ich eine Situation habe,
bei der ich lange Berechnungen habe, dann habe ich hier meinetwegen,
das sind meine Prozessoren, auf einem Prozessor, der zweite Prozessor,
der braucht vielleicht irgendeine Nachricht, das dauert eine Weile,
die zu verschicken.
Ich sage, das dauert lange, also eigentlich ist es so, wenn der
Prozessor jetzt irgendjemandem was schickt, das dauert sehr lange, bis
da eine Nachricht ankommt.
Und man möchte gerne in der Zeit, in der kommuniziert wird, trotzdem
etwas Sinnvolles tun.
Und deswegen braucht man dafür besondere Mechanismen, bei denen man
ein Ausgabetrend von Berechnungen und versucht, also Nachrichten
rauszuschicken und auf Antworten will man möglichst nicht warten,
sondern will in der Zeit etwas Wichtiges tun.
Und dann kann man auf die Art und Weise den Kommunikationsaufwand
verstecken.
Das ist dann für die konkreten Entwürfe von verteilten oder von
Algorithmen auf verteilten Systemen die Herausforderung, den
berechtigten Kommunikationsaufwand zu verstecken.
Wenn ich allerdings mir Probleme auf verteilten Systemen anschaue, die
speziell sind, speziell auch dort auftreten, wie zum Beispiel, Sie
möchten gerne einen Anführer für ein Rechnernetz haben, einen
Leitprozessor wählen.
Das ist ein Problem, das hängt von der Anzahl der Prozessoren dran,
die daran teilnehmen.
Dafür müssen Sie eine gewisse Anzahl von Nachrichten austauschen.
Das ist also ein inhärenter Aufwand, um ein gewisses Problem mit
verteilten Algorithmen zu lösen.
Und da kann man nur die Anzahl der Nachrichten nehmen, da ist nichts
mehr zu verstecken.
Also das ist ein weiteres Thema, das man sich sehr intensiv angucken
kann, verteilte Algorithmen.
Hat größere Relevanz jetzt noch im Zusammenhang mit Grid Computing und
Cloud Computing.
Und ich hoffe, Ihnen ist der Begriff Cloud Computing schon mal über
den Weg gelaufen, habe ich glaube ich zu Beginn auch schon kurz
erwähnt.
Und es ist klar, konkrete Beispiele für verteilte Systeme gibt es halt
genügend in der Universität oder im KIT halt auf verschiedenen Ebenen.
Und ist klar, im Internet haben wir im Prinzip ein großes Netz von
verteilten Rechnern.
Darauf kann man viele interessante Algorithmen entwerfen und
überlegen, wie viel Zeit die brauchen.
Und das will ich aber jetzt hier nicht machen, sondern wir müssen uns
jetzt mit konkreten Problemen beschäftigen.
Das war jetzt nur mal so der Überblick, was haben wir eigentlich für
eine Vielfalt an Berechnungsmodellen, Aufwandsabschätzung und so
weiter.
Wir werden von jetzt an keine Random Access Machines uns mehr
angucken, sondern wir wissen, wie wir davon abstrahieren können.
Sondern wir werden uns jetzt mit den konkreten Problemen beschäftigen
und dann natürlich durchaus unterschiedliche Rechnerstrukturen
zugrunde legen.
Aber wir machen das auf einer relativ abstrakten Ebene.
Gut.
Wir fangen also jetzt an mit den algebraischen Problemen.
Das ist also etwas anders als in so klassischen Vorlesungen über
effiziente Algorithmen, wo man häufig mit Suchverkehrsverfahren
anfängt.
Ich mache es halt so und man kann sich daran sehr schön so wichtige
Eigenschaften angucken.
Und das, was ich mir jetzt angucken muss bei algebraischen Problemen,
ist im Prinzip die Anzahl der arithmetischen Operationen.
Der Begriff Algebra ist Ihnen ja hoffentlich noch bekannt aus der
Mathematik, obwohl Algebra eigentlich in dem Sinne nicht gemacht wird.
Sie machen lineare Algebra, aber der Begriff von Gruppen, Halbgruppen,
Gruppen, Ringen, Körpern und so weiter wird leider nicht so intensiv
gemacht.
In der Matheausbildung ist das einfach nicht die Zeit dafür.
Wenn ich von algebraischen Problemen rede, dann rede ich von
Problemen, die ich mit solchen Operationen machen kann, wie Addition,
Multiplikation und den inversen Operationen, Subtraktion und Division.
Und die brauche ich natürlich bei der Matrixmultiplikation.
Das ist ein klassisches Beispiel.
Wenn Sie sich anschauen, wie ich die Leistungsfähigkeit von Rechnern
messe.
Eines der typischen Benchmarkprobleme für Hochleistungsrechner ist
Matrixmultiplikation.
Weil das ein klassisches Problem ist, das auftritt in ganz vielen
technisch -wissenschaftlichen Anwendungen, wo Sie Matrixvektor oder
Matrixmatrixmultiplikation machen müssen, weil lösen
Lineargleichungssysteme, haben sie das mit Matrixmultiplikation,
Matrixinversion zu tun.
Klassisches Benchmarkproblem.
Was ist das Problem?
Haben wir schon mehrfach angeguckt.
Wissen wir, n x n Matrizen.
Ups, ich muss hier erstmal den Stift wieder einstellen.
Also, wir haben n x n Matrizen.
Wir nehmen mal an, dass die Elemente ganze Zahlen sind.
In technisch-wissenschaftlichen Anwendungen werden sie häufig reelle
Zahlen haben oder sogar komplexe Zahlen.
Wenn sie komplexe Zahlen haben, sind die einzelnen Operationen etwas
komplizierter, als wenn sie reelle oder ganze Zahlen haben.
Lieber zu vereinfachen an, wir haben ganze Zahlen, ist aber für den
Algorithmus eigentlich jetzt nicht relevant.
Insbesondere heißt das, die Größe der einzelnen Elemente in den
Matrizen interessiert uns eigentlich nicht, sondern es interessiert
uns nur die Anzahl der Elemente, die Größe der Matrix.
Problemgröße sagen wir ist n, obwohl wir n² Elemente sind.
Zwei n².
Trotzdem sagen wir Problemgröße ist n, das sind halt n x n Matrizen.
Das ist einfach eine Definitionssache.
Ich sage hier Problemgröße ist n, obwohl die Anzahl der Bits, die ich
brauche, um eine Instanz zu beschreiben, in der Größenordnung n² ist.
Dann die Datenskulptur.
Wie mache ich das, wie stelle ich denn meine Matrix da?
Nun gut, naiv, Sie wissen, wenn Sie in Java sowas programmieren, dann
würden Sie das vermutlich so machen, wie das hier steht.
Wir haben ein Feld deklariert mit zwei Dimensionen und können dann
entsprechend ein Feld deklarieren mit diesen zwei Dimensionen.
Übrigens ist hier eine Schreibweise jetzt drin.
Ich habe hier oben bei der Definitionsseite Matrix A gleich Aij, wobei
IJ aus einer Menge sind oder einem Konstrukt n in eckigen Klammern.
Das ist eine abkürzende Schreibweise für die Menge 1 bis n.
Verwende ich an vielen Stellen.
Einfach abkürzend.
Ist nicht nur meine Idee, sondern ist eine Standardnotation in
Bereichen, wo man sehr viel mit Indizes umzugehen hat.
So, jetzt sage ich also, meine Matrix, mein Matrix-Element Aij wird
dann abgespeichert.
Nun, wenn wir das in Java machen, wissen wir, die Indizes beginnen mit
0.
Also ist das Aij in Ai-1J-1 abgespeichert.
Der Speicherplatzbedarf ist groß in Ordnung n², das ist klar.
Ich muss jedes Element abspeichern.
Und nun ist die Frage, wie greife ich eigentlich auf die Komponenten
zu?
Wie mache ich das denn?
Im Speicher sieht das doch so aus, dass ich eine lange Liste von
Speicherelementen habe.
Und ich sage, irgendwo habe ich hier meinen Start.
Und in Register S-plus-1 liegt jetzt das erste Element, da liegt jetzt
A -1-1.
Entsprechend liegt hier vielleicht die erste Zeile.
Dann kommt die nächste Zeile.
Ein sehr unterstützendes System, das mir immer einen horizontalen
Strich produziert, automatisch.
Also habe ich hier schon die nächste Zeile und so weiter.
Das heißt aber, das i-te Element liegt in i-1 mal n plus j.
Ich überlege gerade, das habe ich einen Fehler...
Einen Fehler ist hier drin.
Für die Komponente...
Hier sollte ich schreiben die Komponente aij.
Also, das ist hier das Element S-plus-1.
Das ist S-plus-n².
Die Komponente a, eigentlich muss ich hier schreiben i-1j
-1.
Also, warum?
Das aij hier ist so nicht richtig.
Klein aij, das Element, das interessiert mich.
Klein a-1-1 steht im Element an der ersten Position, bei S-plus-1.
Warum steht das an S-plus-1?
Weil 1-1 mal n ist 0 mal n.
Plus 1.
S-plus-1.
Zweite Element an der zweiten S-plus-2 und so weiter und so weiter.
Das Element a-2-1 steht an der Position S-plus-n.
Das sind hier diese hier.
Und hier steht S-plus-n-plus-1.
Entsprechend, wenn sie irgendwo hier unten sind.
Wenn das hier die nächste, die i-te Zeile ist, steht hier also S-plus
-i -minus-1 mal n-plus-j.
J in dem Fall 1, wenn das das erste Element ist.
Oder in dem Fall wäre das das entsprechende Element.
Also, das Relevante hier ist eigentlich nur, um diese Position
auszurechnen, muss ich eine Addition machen.
Eine Multiplikation.
Das i-1 kann man vergessen.
Das ist keine extra Operation.
Das wird einfach anders initialisiert.
Und noch eine Addition.
Ich habe zwei Additionen, eine Multiplikation zu machen.
Und das heißt, der Zugriff auf eine Komponente einer Matrix kostet
Rechenzeit.
Das ist nicht einfach nur ein Zugriff auf den Speicher.
Sondern ich muss erst mal die Adresse ausrechnen, aus dem, was ich in
meiner Datenstruktur zweidimensionales State angegeben habe.
Und entsprechend könnte es natürlich noch sein, dass ich auch noch
eventuell mehrere Register brauche pro Komponente.
Stellen Sie sich vor, Sie haben eine komplexe Zahl.
Da brauchen Sie zwei reelle Zahlen, um eine komplexe Zahl
darzustellen.
Eine reelle Zahl mit doppelter Genauigkeit wären 64 Bit jeweils.
Hätten Sie also viermal...
Quatsch, Sie hätten zweimal 64 Bit pro Komponente.
Und entsprechend hätten Sie dann eventuell noch eine weitere
Multiplikation, weil Sie das noch mal dieser Anzahl Register nehmen
müssen.
Also bei komplexeren Datenstrukturen wird das noch aufwendiger.
Warum sage ich das?
Weil man sich einfach angucken muss, wo treten überall Kosten auf für
meine Ausführung eines Algorithmus.
Jetzt kann ich die anders darstellen, ich kann sie als
eindimensionales Feld darstellen.
Dann habe ich den Aufwand ja nicht mehr.
Dann sind die ja schon so linear angeordnet.
Aber trotzdem muss ich dann natürlich, selbst wenn ich daraus ein
eindimensionales Feld mache, muss ich natürlich auf ein Element aij
zugreifen können und habe dann natürlich in der Indexangabe genau das
wieder reinzuschreiben.
Da wird einfach nur die Operation explizit gemacht.
Wenn ich allerdings nacheinander durch die ganzen Elemente einer
Matrix durchlaufe, dann brauche ich nichts zu modifizieren, dann muss
ich nur addieren.
Immer nur eins drauf addieren.
Das heißt, da spare ich mir die Multiplikation.
Das heißt, die Zugriffskosten hier sind natürlich, wenn ich eine
Komponente a von k habe, und ich möchte auf Register s plus k
zugreifen, ist eine Addition.
Ich muss, wenn hier oben eine Startadresse ist, nur dann wieder drauf
addieren.
Dann kann ich das Ganze noch anders machen.
Ich habe meinetwegen eine Matrix, die ist sehr dünn besetzt.
Wenn die sehr dünn besetzt ist, ist es Unsinn, n² Elemente oder n²
Speicherplatz zu verwenden für eine Matrix, die vielleicht
Größenordnung o von n Nicht-Null-Elemente hat.
Dann macht es Sinn, nur Speicherplatz für die Anzahl der Nicht-Null
-Elemente zu nehmen.
In dem Fall macht man das über eine Folge von Listen, wo jeweils nur
die Nicht-Null-Elemente pro Zeile aufgeführt sind.
Das ist sehr vorteilhaft, wenn Sie Bandmatrizen haben, das ist klar.
Also wie gesagt, wenn Sie diese Struktur hier haben.
Oder bei dünn besetzten Matrizen habe ich hier sogar, genau, hier sage
ich zu malen brauchen.
Da sind die beiden Beispiele angedeutet.
Also das sind die typischen Matrizen, bei denen Sie eine dünne
Besetzung haben, also nur linear viele Elemente.
Und dafür macht es Sinn, auch eine Datenstruktur zu nehmen, die genau
das ausnutzt.
Das Problem ist nur, wenn Sie dann... ich habe Zugriffskosten, die
sind relativ klein.
Ich habe also einen kleinen Speicherplatz.
Allerdings, wenn ich jetzt auf ein spezielles Element aij zugreifen
will, muss ich natürlich erstmal in die entsprechende Zeile gehen.
Und dort das entsprechende Element finden.
Dazu muss ich aber wissen, an welcher Position das jeweils gestanden
hat.
Das heißt, ich muss da schon ein bisschen was reinschreiben.
Und je nachdem, welche Datenstruktur ich an den Zeilen habe, kann das
durchaus wieder etwas länger dauern.
Also die Zugriffskosten hängen dann auch wieder sehr stark davon ab,
wie die Datenstruktur für die Zeilen ist.
Aber man kann schon deutlich effizient das gestalten.
Sie können sich aber vorstellen, wenn Sie dann eine Matrix
-Multiplikation machen wollen, mit so einer effizienten Datenstruktur,
dann werden die Zugriffe so kompliziert auf die einzelnen Elemente,
dass Sie auf einmal Schwierigkeiten haben, die Vorteile zum Beispiel
von dünnbesetzten Matrizen dann wirklich noch rauszuholen.
Kann man aber hinkriegen, erfordert aber etwas intelligentes
Programmieren.
Kommen wir jetzt also zur Matrix-Multiplikation.
Haben wir uns schon wirklich mehrfach angeschaut, was wir da machen
wollen?
Wir wollen zwei Matrizen multiplizieren.
Wir haben uns bisher immer die Schulmethode angeschaut.
Das heißt, wir berechnen die Cij, so wie es mathematisch definiert
ist, als Skalarprodukt von Zeilen und Spalten.
Also irgendeine Zeile wird mit irgendeiner Spalte multipliziert, gibt
dann das entsprechende Element in der Produktmatrix.
Standardansatz ist Ihnen bekannt.
Habe ich Ihnen schon mehrfach aufgelegt.
Dreifachgeschachtelte Schleife.
Wir wissen, wie man das macht.
Auch schön hier mit der Hilfsvariablen, damit ich nicht unnötige
Zugriffe auf Matrixkomponenten bekomme.
Und die Analyse ist Ihnen zu uns zwischen auch bekannt.
Zwei n hoch drei minus n² arithmetische Operation.
Und Zugriffe auf Matrixkomponenten müssen wir nochmal genauer
angucken.
Da wissen wir jetzt, was der einzelne Zugriff kostet.
Und wenn wir das Ganze als zweidimensionales Feld haben, die Matrix,
wissen wir, wir haben zwei Additionen und eine Multiplikation pro
Zugriff.
Das ist die Anzahl der Zugriffe.
Wenn Sie sich das hier durchzählen, kriegen Sie sofort raus, wir haben
zwei n hoch drei plus n² Zugriffe.
Jetzt haben wir zwei Additionen und eine Multiplikation pro Zugriff.
Das sind also drei Operationen pro Zugriff.
Vier n hoch drei plus zwei n² Additionen und zwei n hoch drei plus n²
Multiplikationen nur für Zugriffe.
Wir hatten aber nur n hoch drei Multiplikationen für die eigentliche
Matrixmultiplikation und n hoch drei minus n² Additionen.
Das heißt, die arithmetischen Operationen, die wir nur für die
Zugriffe brauchen, sind deutlich höher als die eigentlich uns
interessierenden arithmetischen Operationen.
Also, Sie haben mehr als dreimal so viele arithmetische Operationen
für Adressberechnungen wie für die eigentliche Matrixmultiplikation.
Man kann gucken, kann man das nicht irgendwie effizienter machen.
Wenn Sie also tatsächlich auf Zeit programmieren müssen, dann werden
Sie versuchen, den Aufwand für Zugriffsberechnungen möglichst stark zu
reduzieren.
Matrix ist ein eindimensionales Feld.
Wenn Sie es geschickt machen, können Sie alle Multiplikationen
rausstreichen.
Wenn Sie aber angucken müssen, in welcher Reihenfolge Sie zugreifen
müssen auf die Elemente der Matrix, da brauchen Sie nur immer drauf zu
addieren.
Sie brauchen nicht zu multiplizieren.
Und dann dürfte das schon mal ein bisschen schneller gehen.
Wenn Sie eine dünn besetzende Matrix haben, ist das Ganze etwas
komplizierter wegen der Art der Abspeicherung in irgendwie linearen
Listen.
Und dann haben Sie halt da ein bisschen zu kämpfen.
Aber man kann es auch effizient hinbekommen.
Man könnte es in den Übungen machen, ist aber, glaube ich, keine
Aufgabe auf dem aktuellen Zettel.
Jetzt kann man natürlich auch daran gehen, zu überlegen, kann ich bei
der Anzahl der eigentlichen arithmetischen Operationen was machen.
Wir haben doch das ganz normale, klassische Skalarprodukt gemacht.
Und jetzt gibt es eine Annahme, Multiplikation dauert länger als
Addition.
Wenn Sie das mal testen in Ihrem Rechner, probieren Sie einfach mal
aus, Sie wollen Zahlen addieren und Zahlen modifizieren.
Wie lange dauert es, Zahlen zu modifizieren, wie lange dauert es,
Zahlen zu addieren, ist etwa die gleiche Größenordnung heutzutage.
Wenn Sie Gleitpunkt, Addition, Gleitpunkt, wenn Sie reelle Zahlen
haben, Sie machen Multiplikation reeller Zahlen und Addition reeller
Zahlen, dann werden Sie feststellen, die Multiplikation ist etwas
schneller als die Addition.
Hängt einfach damit zusammen, Sie erinnern sich, wie Gleitpunkt,
Multiplikation und Addition laufen.
Wir müssen bei der Gleitpunkt, Addition ja noch
Mantissenverschiebungen machen und all solche Dinge, also den
Mantissenangleich und Skalierung usw.
Da sind eine Reihe von Einzelschritten zu machen.
Wenn Sie allerdings einen guten Gleitpunktprozessor daneben haben,
dann geht das auch sehr schnell.
Wenn Sie allerdings komplexe Operationen oder komplexe Zahlen haben,
dann dauert die Multiplikation deutlich länger, weil Sie dann mehrere
Operationen da drin machen müssen.
Und es gibt halt, wenn Sie also sehr einfache Rechner haben, was in
der Prozessdatenverarbeitung noch manchmal der Fall sein kann, da
dauert tatsächlich die Multiplikation länger als die Addition, weil
die in einfachen Rechnern nicht hardwaremäßig realisiert ist, sondern
softwaremäßig.
Wenn Sie es softwaremäßig machen, wird die auf Addition zurückgeführt
und dann haben Sie eine deutlich längere Ausführungszeit als für
Addition.
Winograd hat 1970 jedenfalls einen Algorithmus entwickelt, der davon
ausging, ich muss Multiplikationen einsparen.
Und ich stelle Ihnen das vor, weil ich Ihnen daran darstellen möchte,
was man alles machen kann, wenn man einen Algorithmus versucht,
schnell zu machen, wenn man ein Problem auf eine neue Art und Weise
bearbeiten möchte.
Was der macht, ist nämlich etwas unerwartet.
Der hat sich nämlich folgende Sache angeguckt.
Eigentlich soll ja etwas berechnet werden, wie unsere schöne Summe a,
i, k, b, k, j.
Ignorieren Sie diesen langen Strich da oben.
Nicht j, sondern k gleich 1 bis n.
Jetzt berechnet der hier folgendes.
Also eigentlich möchte ich so Sachen berechnen, wie das, was hier
steht.
Das ist so eine Teiladdition, die vorkommt.
Hier steht also a, i, 3 mal b, 3, j plus a, i, 4 mal b, 4, j.
So etwas brauche ich in meiner Summe.
Das steht genau da oben entsprechend drin.
Und jetzt hat er sich hier das angeguckt.
Und da steht jetzt a, i, 3 plus b, 4, j mal a, i, 4 plus b, 3, j minus
a, i, 3, a, i, 4 plus b, 3, j mal b, 4, j.
Das ist genau diese Summe, die dort rechts steht.
Können Sie sich einfach überlegen, wenn Sie das hier, diesen Teil
auspolitizieren, müssen Sie halt gerade diese kombinierten, also diese
a -Produkte und b-Produkte wieder abziehen.
Das Interessante sind diese beiden Terme, die Sie hier haben.
Da haben Sie einen Term, in dem nur ein Index i auftaucht.
Sie haben einen Term, wo nur der Index j auftaucht.
Und das ist die wesentliche Idee.
Wenn Sie das jetzt naiv analysieren, oder zunächst mal naiv aufbauen,
ist also der Vorschlag von Vinograd.
Ich mache meine Summe so auf diese Art und Weise.
Ich fasse immer so zwei solche Produkte zusammen.
Und schreibe meine Summe im Prinzip so auf, mein Skalarprodukt.
Und da setze ich jeweils so zwei benachbarte Produkte durch diese
linke Seite.
Und dann habe ich diesen sehr kompliziert aussehenden Ausdruck in
einer Summe, in der nur noch in halbe solche Paare aufsummiert werden
müssen.
So, jetzt analysiere ich das, was dort steht.
Ich stelle Test für jedes ij.
Muss ich jetzt, naja, eine Summe von in halbe Elementen machen.
Das sind, tun wir mal, in halbe minus eins Additionen.
Dann habe ich da eine Addition, da eine und da eine.
Das sind also eins, zwei, drei Additionen.
Und in halbe...
Wieso komme ich hier auf einmal ins Schleuder?
Das kann doch gar nicht sein.
Bitte?
Ich habe doch hier nur eins, zwei, drei...
Natürlich, ich habe vier Additionen hier drin.
Also drei Additionen, eine Subtraktion.
Und das Ganze wird ja auch summiert.
Also habe ich diese vier Additionen plus in halbe minus eins.
Also vier mal in halbe Additionen.
Plus noch die Additionen, um die alle aufzusummieren.
Dann habe ich diese fünf in halbe minus eins.
Und ich habe eine Reihe Produkte zu machen.
Für jeden diesen Termen habe ich dort eine Modifikation, dort eine und
dort eine.
Das sind drei in halbe Modifikationen.
Und wenn ich das für jedes IJ mache, habe ich also insgesamt 1,5 n³
Modifikationen und 2,5 n³ minus n².
Und das ist deutlich mehr bei Additionen und Modifikationen.
Also ist das völliger Quatsch.
Interessant ist eben, dass das nicht ist.
Das ist also nicht alles Unsinn, obwohl es auf den ersten Blick so
aussieht.
Sondern jetzt muss ich das ausnutzen, was ich hier oben sagte.
Interessanterweise habe ich hier Terme drin, die nur von I und nur von
J abhängen.
Und das nutze ich jetzt aus.
Also, das ist mein Ausdruck.
Und hier habe ich diese... das war mein Ausdruck.
Und in dem zweiten Teil hier, da taucht diese Summe auf und diese
Summe von Produkten.
Und jetzt gehe ich ganz anders vor.
Jetzt sage ich, ich habe hier einen Term, der hängt nur von I ab.
Ich habe dort einen Term, der hängt nur von J ab.
Jetzt kann ich doch einfach für jedes I diesen Term berechnen.
Und für jedes J kann ich den B-Term berechnen.
Und dann habe ich diese vorberechneten Werte und brauche die nur noch
für jedes IJ abzuziehen von der Summe dieser Produkte, die da vorne
stehen.
Das heißt, ich habe da nur den Aufwand für diese Summe hier vorne.
Und dann werden noch zwei Additionen dazugefügt.
Und ich habe den Aufwand, um vorher diese Dinge zu berechnen.
Also die geschickte Anordnung der Berechnung sieht dann so aus, dass
ich erstmal diese kleinen dI berechne, die kleinen ej mit den B
-Produkten.
Anschließend berechne ich alle cij, dadurch, dass ich halt diese Summe
der beiden Klammerausdrücke dort mache, von den halben solchen
Klammerprodukten.
Und noch das dI abziehe und das ej abziehe.
Wenn ich das jetzt analysiere vom Aufwand hier, dann stelle ich fest,
um das dI zu berechnen, brauche ich in halbe, also pro dI, in halbe
Multiplikationen und in halbe Minus 1 Additionen pro ej genauso.
Und für jedes IJ muss ich für das cij dann noch einmal den Aufwand
hier für diese Summe berücksichtigen.
Das sind gerade diese zwei Additionen noch dazu.
Dann komme ich insgesamt auf in halbe mal eine Multiplikation plus
zwei Additionen und noch einmal in halbe plus eins Additionen dazu.
In halbe Minus 1 Additionen plus zwei.
Das sind hier diese zwei.
Wenn ich das alles aufaddiere, habe ich insgesamt n hoch 3 halbe plus
n Quadrat Multiplikationen und eine gewisse Zahl von Additionen.
Insgesamt also mehr als bei der Schulmethode für die Vates
Multiplikationen, aber ich habe die Anzahl der Multiplikationen fast
um die Hälfte reduziert.
Nur noch n hoch 3 halbe.
Und wenn jetzt die Zeit für eine Multiplikation ein gewisses
Vielfaches ist, der Zeit für eine Addition, habe ich hier einen
deutlichen Vorteil.
Und das war also die wesentliche Idee von Vinograd.
Also wenn sie etwa zehnmal so lange dauert, die Multiplikation, dann
ist das ein deutlicher Vorteil.
Ich will jetzt nicht Ihnen vorschlagen, dass Sie Vates
Multiplikationen auf diese Art und Weise machen, weil auf heutigen
Rechnern die Multiplikationen und die Additionen, zumindest wenn Sie
also ganze Zahlen nehmen oder auch wenn Sie normale reelle Zahlen
nehmen, dauern die etwa gleich lange.
Was ich Ihnen zeigen wollte, ist einfach nur, manchmal muss man eine
Berechnung völlig anders anordnen und bekommt auf einmal
Möglichkeiten, eine Berechnung insgesamt zu beschleunigen.
Wir konnten auf einmal hier Multiplikationen eintauschen gegen so ein
paar mehr Additionen.
Und der Weg, wie das gemacht wurde, war halt eine Ausnutzung von
diesen algebraischen Eigenschaften, dass ich halt einfach da zwei
Klammerprodukte oder zwei Klammerausdrücke multipliziert habe, was
abgezogen habe und dann kam etwas raus, was ich tatsächlich brauche.
Und darüber konnte ich eine Berechnung ganz anders strukturieren.
Ich mache also zunächst mal einen komplexeren Ausdruck, kann den aber
effizienter berechnen und bekomme insgesamt einen Vorteil.
Und das wollte ich Ihnen hiermit einfach darstellen, das ist manchmal,
ich nenne das mal so eine Art massieren oder so Problemmassage.
Wie kann ich eigentlich mein Problem irgendwie anders betrachten, um
neue Zugänge zu finden für eine effiziente Berechnung?
Das ist das, was ich hier bei dem Beispiel vermitteln wollte.
Und es ist völlig klar, asymptotisch habe ich nichts erreicht.
Größenordnung n hoch 3.
Und der Stil, wenn Sie das programmieren, ist nicht sehr schön.
Insbesondere, damit das wirklich was bringt, müssen Sie auch noch die
Anzahl der Multiplikationen und Additionen bei den Zugriffen
reduzieren.
Das machen Sie also mit eindimensionalen Arrays und der sehr
geschickten Art der Indexberechnung.
Und wenn Sie das Programm jemandem zeigen, dann hat er große
Schwierigkeiten zu erkennen, dass das eine ganz normale
Matrixmultiplikation ist.
Ist eigentlich nicht das, was wir machen wollen.
Aber manchmal braucht man sowas, wenn man wirklich sehr stark darauf
achten muss, dass die Laufzeit innerhalb bestimmter Grenzen liegt.
Dann kann sowas ein ganz entscheidender Punkt sein, wie man die
Berechnung befreundet.
Gerade so in Signalverarbeitungssachen, in Prozessdatenverarbeitung,
wenn Sie gewisse Randbedingungen für die Berechnung haben, kann sowas
sehr sinnvoll sein.
Also was Sie lernen sollten, war diese geschickte Berechnungsmassage,
das Durchkneten einer Berechnung, um irgendwie neue Zugänge zu
schaffen.
Jetzt wollen wir das Ganze noch ein bisschen anders angucken, mit
einem Standardansatz, um Berechnungen oder Probleme ein bisschen
durchzukneten, anders zu strukturieren.
Und das ist der Divide-and-Conquer-Ansatz, den Sie auch kennen, aus
Grundlageninformatik 1, oder auch noch mal Essens-Research.
Standardansatz, um große Probleme zu bearbeiten.
Sie haben ein großes Problem und der typische Informatiker sagt, das
ist mir viel zu kompliziert.
Ich teile das erstmal auf in eine Menge von kleineren Problemen und
löse die.
Und wenn ich dann meine vielen Lösungen habe, dann kombiniere ich die
wieder zu meiner Endlösung.
Und das Ganze rekursiv.
Ich versuche immer, ein Problem möglichst einfach zu machen, auch ein
klassischer mathematischer Ansatz.
Da geht es im Wesentlichen darum, dass man Dinge versucht, möglichst
einfach zu machen.
Und wenn ich eine einfache Struktur habe, kann ich die einfach lösen.
Und ansonsten muss ich nur Lösungen zusammenbauen, das kann ja einen
Vorteil bringen.
Und die Idee, die man hier jetzt, oder die Strassen verwendet hat,
gleiche Jahreszahl wie Wienograd, übrigens Volker Strassen, der hier
in Frankfurt einen Lehrstuhl hatte, der sagt Folgendes.
Er nimmt an, es gibt ein Algorithmus, den wir mal groß K nennen, zur
Multiplikation von klein-K-kreuz-K-Matrizen, der die Kommutativität
der Multiplikation nicht ausnutzt.
Wieso kann Multiplikation eventuell nicht kommutativ sein?
Denken Sie nur mal an die Multiplikation von Matrizen.
Die ist in der Regel nicht kommutativ.
Die Werte a mal b und b mal a sind sehr unterschiedlich.
Jetzt nimmt er an, es gibt ein Algorithmus, der kann also bestimmte
Matrizen einer festen Größe K-Kreuz-K multiplizieren.
Ohne die Kommutativität der Multiplikation dabei auszunutzen.
Bei dem Beispiel von Wienograd, was wir vorher hatten, wenn Sie sich
das anschauen, was da gemacht wird, da haben wir die Kommutativität
der Multiplikation ausgenutzt.
Schauen Sie sich diesen Ausdruck an, da stellen Sie sich fest, das ist
da gerade ausgenutzt.
Semiring bezieht sich auf die entsprechende algebraische Struktur.
Wenn ich eine Struktur habe mit Addition und Multiplikation, bei der
die Multiplikation nicht kommutativ ist, und außerdem nicht
notwendigerweise inverse Multiplikation, also Division existiert, wenn
ich also keine Kommutativität der Multiplikation habe, nennt man das
ein Semiring.
Normalerweise Addition und Multiplikation, Kommutativ und Addition
auch noch eine Gruppe, das heißt ich habe dort ein inverses Element,
bei der Multiplikation nicht unbedingt, das ist nur ein Ring.
Insbesondere also K-ungleich Wienograds Algorithmus, weil wir bei
Wienograds Algorithmus die Kommutativität ausnutzen.
Und jetzt nehmen wir an, wir haben eine Matrix, deren Dimension eine
Potenz von K ist.
Neben K wird das 2, wenn ich also eine 4x4-Matrix oder eine 32x32
-Matrix oder eine 1024x1024-Matrix oder ähnliches.
Und die Idee des Verfahrens von Strassen ist jetzt folgendes, ich
zerlege mein Problem.
Jetzt kommt ein Punkt, wo Studenten häufig irritiert werden und etwas
missverstehen.
Die Aufteilung, die ich hier angedeutet habe, da oben in die
verschiedenen Teilprobleme, ist ein bisschen was anderes als die
Aufteilung, die ich Ihnen jetzt hier zeige.
Ich teile zunächst mal meine Matrizen auf.
Also, Matrizen A und B sind hier angegeben.
Jetzt schaue ich mir also meine Matrix A an.
Ich sage, dass N ist eine Potenz von K.
Zum Beispiel K2 wäre meinetwegen eine 16x16-Matrix.
Dann teile ich das ein in eine KxK-Matrix.
Also, wenn das K2 wäre, würde ich das einteilen in eine, einfach
halbieren, hätte ich eine 2x2-Matrix von NxKxNxK-Matrizen.
Für N gleich 16 und K gleich 2, also hätte ich eine 2x2-Matrix von 8x8
-Matrizen.
Das B genauso und das C genauso.
Und jetzt habe ich also im Prinzip, nehmen wir mal an, K gleich 2.
Dann hätte ich also jetzt hier eine solche Matrix, eine solche Matrix
und das ergibt natürlich dann eine solche Matrix.
Die einzelnen Komponenten, die hier drin stehen, sind aber, also
nehmen wir mal an, wir hätten N gleich 16.
Dann wären die Komponenten da drin 8x8-Matrizen.
So, jetzt modifiziere ich diese jetzt als KxK-Matrizen aufgepassten
Matrizen nach dem Verfahren Groß-K, das ich ja vorausgesetzt habe.
Dabei treten natürlich Produkte von Komponenten auf.
Ich muss ja zum Beispiel hier die erste Zeile mit der ersten Spalte
modifizieren.
Da muss ich jetzt Matrizen modifizieren.
Aha, jetzt modifiziere ich auf einmal zwei 8x8-Matrizen miteinander.
Da weiß ich gar nicht, wie das geht.
Nehme ich doch hier den gleichen Ansatz.
Ich teile die auf in 2x2-Matrizen, von in dem Fall dann 4x4-Matrizen
und kann ja die Modifikation rekursiv so machen.
Das heißt, für jedes auftretende Produkt von N durch K, Kreuz N durch
K -Matrizen, also für jedes Produkt 1, das erste Produkt, das zweite
Produkt usw.
bis zu irgendeinem, sage ich mal, das R-Produkt.
Das sind die ganzen Produkte, die auftauchen.
Das ist meine Aufteilung meines Problems.
Bei der Multiplikation dieser K-Kreuz-K-Matrizen treten eine gewisse
Anzahl von Multiplikationen von Komponenten auf.
Das ist jeweils ein Teilproblem, das ich weiter reduzieren kann, oder
rekursiv weiter bearbeiten kann.
Die Additionen, die auftreten da drin, sind Additionen von
irgendwelchen Matrizen, die kann ich problemlos ausführen.
Die einzelnen Komponenten weiß ich genau, wie ich die agieren muss.
Das geht also einfach.
Also, ich modifiziere oder ich führe alle dabei auftretenden Produkte
rekursiv nach diesem Verfahren S aus, falls ich noch größere Matrizen
habe.
Wir waren jetzt gekommen bis zu einer 2-Kreuz-2-Matrix von 4-Kreuz-4
-Matrizen.
Wenn ich dann jeweils mit 4-Kreuz-4-Matrizen multipliziere, würde ich
ja schon aufteilen und hätte 2-Kreuz-2-Matrizen von 2-Kreuz-2
-Matrizen.
Da hätte ich einen Punkt, wo ich dann ein dann auftretendes Produkt
von 2-Kreuz-2-Matrizen natürlich nach dem Verfahren K mache.
Das heißt, da endet die Rekursion.
Jetzt habe ich also aus einem uns allen bekannten Problem, wie ich
nach Schulmethode Matrizen multipliziere, einen Divide-and-Conquer
-Ansatz gemacht, bei dem ich jede Multiplikation nach einem so etwas
interessanten Verfahren ausführe.
Und die Idee war eben, ich fasse meine Matrizen nicht als n-Kreuz-n
-Matrizen auf, sondern als K-Kreuz-K.
Das ist der ganze Ansatz.
Jetzt schaut man sich an, was da von der Rechenzeit rauskommt.
Das sieht ja zunächst mal wahnsinnig kompliziert aus.
Und dazu muss ich das analysieren.
Und dazu schaue ich mir an, m von K seien die Anzahl der
Multiplikationen in K.
Das, was ich hier oben gerade als r bezeichnet habe.
Das ist also jetzt m, klein m von K.
Das kleine a von K seien die Anzahl der Additionen in K.
Das m von n, die Anzahl der Multiplikationen in dem gesamten
Verfahren.
Das m von n, die Anzahl der Additionen in dem gesamten Verfahren.
Also das klein m, klein a sind die Multiplikationen in den konstanten
Verfahren für das K.
Und das andere sind die Groß m von n und Groß a von n.
Und jetzt muss ich das Ganze analysieren.
Also, die Anzahl der Multiplikationen für K hoch r Kreuz K hoch r
Matrizen.
Das war ungünstig, dass ich das r hier genommen hatte.
Das r war eigentlich schon vergeben, weil es die Potenz von K war.
Also n ist K hoch r.
Vergessen Sie also, dass ich da r gesagt hatte.
Das war nur ein kleines m von K.
Wenn ich jetzt mir anschaue, die Anzahl der Multiplikationen für n
Kreuz n Matrizen oder K hoch r Kreuz K hoch r Matrizen, da treten doch
bei diesem Verfahren klein m von K viele Multiplikationen auf von
genau um den Faktor K kleineren Matrizen.
Das kann man sofort auflösen.
Das ist also ganz einfach.
Das sehen Sie also sofort.
Das ist natürlich m von K hoch r.
Das Ganze.
Das ist sehr einfach auszurechnen.
Die Anzahl der Additionen.
Wie sieht die aus?
Ich habe eine gewisse Anzahl von Additionen zu machen bei der
Multiplikation von K Kreuz K Matrizen.
Und die Größe der Matrizen da drin ist jeweils K hoch r minus 1, also
n durch K Quadrat.
Das sind ja n durch K Kreuz n durch K Matrizen.
Jede dieser Komponenten muss addiert werden, also habe ich so viele
Additionen zu machen plus die Anzahl der Additionen, die bei diesen
rekursiven Ausführungen der Matrixmultiplikationen noch auftauchen.
Ich habe ja diese kleinen m von K vielen Matrixmultiplikationen zu
machen.
Auch da drin treten Additionen auf.
Und zwar sind das aber eben die Anzahl der Additionen bei den
Matrixmultiplikationen, wo ich jetzt eine n durch K Kreuz n durch K
oder K hoch r minus 1 Kreuz K hoch r minus 1 Matrix habe.
Das sind die Rekursionsformeln für die Abschätzung des Aufwandes
dieses Strassenverfahrens.
Und das wird jetzt in einem Lemma hier kurz dargestellt.
Die Multiplikation sieht man sofort, das ist m von K hoch r.
Und das ist also wirklich sehr einfach.
Das ist ganz klar, man kann das durch Induktion beweisen, normal muss
man das so machen, aber es ist wirklich schon naiv sofort zu sehen.
Das Interessante ist, was passiert eigentlich mit der Anzahl der
Additionen?
Und da habe ich hier einfach nochmal hingeschrieben, das ist die
Anzahl der Additionen.
Dieses m von K mal a von K hoch r.
Jetzt kann ich Induktionsannahme einsetzen und für das a von K hoch r
den Ausdruck hier oben schonmal dafür einsetzen.
Dann kommt das dorthin.
Und jetzt muss ich hier nur ein bisschen umformen und ich mach das
jetzt einfach mal.
Wie kommt man da hin?
Ich habe einfach das m von K hier reingezogen.
Wenn ich das m von K da reinziehe, wird hier aus m von K hoch r minus
i, wird m von K hoch r plus 1 minus i.
Und das a von K bleibt davor.
Jetzt habe ich also hier a von K mal K hoch 2r plus das, was da vorne
steht, Summe.
Und wenn ich mir die genau angucke, wenn ich die jetzt bis r plus 1
laufen lasse, die Summe dort, dann würde ich noch dazu kriegen,
entsprechend m von K hoch r plus 1 minus r plus 1, das ist 0, mal K
hoch 2r plus 1 minus 1.
Das ist gerade 2r, das ist genau der Term, der da links daneben steht.
Das heißt, diese Summe, wobei ich einfach jetzt den Laufbereich bis r
plus 1 erhöht habe, ist genau das, was ich induktiv beweisen musste.
Und damit habe ich die Gültigkeit dieser Formel da oben.
Induktionsanfang war trivial in dem Fall.
Und die Induktion ist sehr einfach.
Sie brauchen keine Angst zu haben, ich werde nicht alle Beweise, die
möglich sind, per Induktion machen.
Ich mache das an ganz wenigen Stellen, einfach um auch mal was zu
beweisen.
Aber ich will Sie nicht quälen mit unnötigen Dingen.
Aber eigentlich ist ein Beweis auch kein Quälen, sondern ein Beweis
ist eine Hilfestellung zum Verständnis von gewissen Zusammenhängen.
Und ich werde Ihnen später auch noch zeigen, dass man solche
Abschätzungen auch über einen Standardsatz ableiten kann, bei dem man
sich Rekursionsgleichungen anguckt, dieser Art, wie sie hier oben
stehen.
Wir werden später noch sehen, wie man die ganz systematisch lösen
kann.
Und dann braucht man nicht mehr jeder Einzelne sich genau zu
überlegen, sondern kann das einfach allgemein ableiten, welche
geschlossene Form für so eine Rekursionsgleichung dann entsteht.
Was Sie jetzt wissen ist, dass m von K auf R ist m von K hoch R, der
erste Term.
Und das zweite ist dieser Ausdruck für die Addition, der ist aber noch
nicht sehr viel weiter.
Diese Summe ist noch sehr komplex, sehr umständlich.
Die wollen wir gerne noch ein bisschen vereinfachen.
Und vereinfachen, naja, durch diese Abschätzung.
Der Vorteil der asymptotischen Abschätzung, die wollen wir ausnutzen.
Ich möchte zeigen, diese Summe ist nach oben beschränkt durch eine
Konstante mal m von K hoch R.
Das haben wir schon mal gesehen, das m von K hoch R.
Das war nämlich die Anzahl der Modifikationen.
Und da ist der entscheidende Punkt.
Was ich zeigen möchte ist, dass im Prinzip die Anzahl der Additionen
in der gleichen Größenordnung liegt, wie die Anzahl der
Multiplikationen bei diesem Verfahren.
Und genau das wird hier durch dieses Lemma gezeigt.
Diese Abschätzung fängt also mit einer gewissen Annahme an.
Ich nehme einmal an, dass die Anzahl der Multiplikationen größer ist
als K².
Das heißt, ich brauche mindestens eine Operation mehr, als ich
Elemente in meiner Matrix habe.
Diese Annahme ist sicherlich gerechtfertigt.
Also pro Cij brauche ich sicherlich mindestens eine Multiplikation.
Ich habe ja K kreuz K-Matrizen.
Da muss ich so ein Kalabprodukt jeweils berechnen.
Dass ich da etwas mehr als eine Multiplikation brauche, kann man
durchaus annehmen.
Ich brauche das, weil ich nämlich ansonsten in meiner Abschätzung hier
durch 0 dividieren würde.
Deswegen nehme ich mal an, ich brauche mindestens eine mehr als dieses
C.
Das heißt, ich kann jetzt also entweder M von K als K² plus C
hinstellen oder K² als dieses M von K minus C.
Das M von K minus C ist dann größer als 0, also K² kleiner als M von
K.
Jetzt schreibe ich mir einfach diese Formel nochmal hin.
Diesen Ausdruck von da oben.
Und kann jetzt das K² ersetzen durch M von K minus C.
Da habe ich das gemacht.
Was hilft mir das?
Ich möchte ja gerne hier oben auf irgendein Produkt oder eine Potenz
von M von K hinaus.
Deswegen bin ich so sehr daran interessiert, das K², was hier
auftaucht, oder da steht so noch eine höhere Potenz von K, das
rauszuwerfen.
Und zu ersetzen durch etwas, was nur von M von K abhängt.
Das habe ich jetzt hier schon gemacht.
Und das kann ich jetzt weiter verändern.
Ich kann also das M von K hoch R hier rausziehen.
Da steht ja M von K hoch R minus I.
Da ziehe ich also M von K hoch R raus, dann bleibt M von K hoch minus
I übrig.
Mal diesen anderen Term, M von K minus C hoch I minus 1.
M von K hoch minus I heißt aber, ich dividiere durch M von K hoch I.
Dann kann ich aber genauso gut hier hinschreiben, M von K minus C
durch M von K.
Da ist dieser Bruch hoch I.
Jetzt habe ich M von K minus C hoch I genommen.
Und hier oben stand aber hoch I minus 1.
Deswegen muss ich das hier unten nochmal in den Nenner reinschreiben.
Und ich habe da immer noch stehen, mein M von K hoch R.
Und das Ganze kann ich jetzt...
Diese Summe, die hier steht, ist eine Summe, ist also eine Reihe.
Ich habe hier die Terme, dieses M von K minus C durch M von K ist ein
Wert kleiner 1.
Da weiß ich, der Grenzwert ist dadurch abschätzbar.
Das ist einfach Standardmathematik.
Der Grenzwert einer Reihe.
Die Summe einer solchen Reihe.
So, das ist jetzt mein Grenzwert, der Wert dieser Summe.
Und jetzt weiß ich, das M von K minus C, das war das K-Quadrat.
K-Quadrat ist ja eine Konstante.
Und hier rechts steht etwas.
M von K hoch R plus 1 minus dieses M von K minus C hoch R plus 1.
Das kommt von hier oben, da.
Durch M von K hoch R plus 1.
Und da steht hier noch, das wird ja durch das, was hier unten steht,
dividiert.
Sie können das leicht ausrechnen.
Da kommt dann also dieser Ausdruck raus.
Und den kann man noch wieder etwas umformen.
Und dann kommen wir am Ende.
Wenn wir das ein bisschen hin und her umformen, ich will jetzt die
Einzelheiten gar nicht machen, kommen wir auf einen Ausdruck.
Das sind wirklich einfache Umformungen von diesen Brüchen.
Kommen wir auf einen Ausdruck, wo M von K hoch R steht.
Mal 1 minus dieses K-Quadrat durch M von K hoch R.
K-Quadrat durch M von K ist aber ein Wert.
K-Quadrat durch M von K ist kleiner als 1.
Das hoch R.
Das ist ein kleiner Wert.
Mal 1 durch M von K minus K-Quadrat.
Auch ein kleiner Wert.
Das kann ich durch eine Konstante abschätzen.
Überhaupt kein Problem.
Also das ist kleiner gleich eine Konstante mal M von K hoch R.
Und das heißt, ich habe gezeigt, dass das Ganze aus O von M von K hoch
R ist.
So, jetzt habe ich das schöne Ergebnis.
Entschuldigung, die Zeit ist abgelaufen.
Aber ich habe das schöne Ergebnis, das muss ich Ihnen noch ganz kurz
zeigen, das dann in diesem Satz zusammengefasst wird.
Ich weiß im Prinzip, die Multiplikation und Addition, die Anzahlen
liegen in der gleichen Größenordnung.
Und jetzt muss ich mir noch anschauen, das war das M von K hoch R.
Das M von K hoch R.
Naja, das R war log zur Basis K von N.
Jetzt macht man einen kurzen Trick.
Wirbelt das also einmal rum.
M von K hoch log zur Basis K von N ist gleich N hoch log zur Basis K
von M von K.
Und ich habe damit einen Algorithmus, der die Matrizen modifizieren
kann mit N hoch log zur Basis K von M von K arithmetischen
Operationen.
Wenn Sie jetzt 2 einsetzen für K, dann steht dort log zur Basis 2 von
M von K.
Standardmäßig haben Sie 8 Multiplikationen, wenn Sie 2 kreuz 2
Matrizen modifizieren.
Logarithmus zur Basis 2 von 8 ist 3.
Dann hätten Sie O von N hoch 3 Operationen.
Das kennen wir irgendwie.
Wenn es Ihnen aber gelingt, 2 kreuz 2 Matrizen zu modifizieren mit
weniger als 8 Multiplikationen, haben Sie einen Gewinn.
Der Strassen hat es geschafft, die 2 kreuz 2 Matrizen mit 7
Multiplikationen zu modifizieren.
Jetzt haben wir also N hoch log zur Basis 2 von 7 und das ist 2.81.
Sie haben reduziert von N hoch 3 auf N hoch 2.81, was eine
asymptotische Verbesserung ist.
Für große Matrizen eine drastische Verbesserung.
Das ist das Wesentliche.
Der Konkeransatz liefert also hier eine wirklich deutliche
Verbesserung in der Komplexität für die Wartungsmodifikation.
Das war es für heute.
Vielen Dank.