WEBVTT 00:00.660 --> 00:03.820 Ich begrüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen. 00:03.960 --> 00:06.640 Bisschen verzögert durch technische Schwierigkeiten mit dem Rechner, 00:06.900 --> 00:08.020 aber das haben wir jetzt ja hingekriegt. 00:08.120 --> 00:09.800 Irgendwas ist hier im Hintergrund immer noch nicht in Ordnung. 00:09.900 --> 00:13.100 Er ist immer noch am Arbeiten auf irgendwas im Hintergrund. 00:13.280 --> 00:14.380 Keine Ahnung, was da passiert. 00:15.560 --> 00:19.980 Letztes Mal haben wir uns beschäftigt mit Grundlagen, um überhaupt 00:19.980 --> 00:26.740 Aussagen machen zu können, über das, was ein Algorithmus an Kosten 00:26.740 --> 00:27.300 verursacht. 00:27.300 --> 00:29.160 Wir hatten Berechnungsmodelle angeschaut. 00:29.280 --> 00:34.680 Ich hatte Ihnen im Wesentlichen gezeigt, ein einfaches 00:34.680 --> 00:36.660 Berechnungsmodell, der Random Access Machine. 00:36.800 --> 00:39.300 Wir haben uns angeschaut, die Berechnungsmodelle. 00:40.400 --> 00:42.320 Das eine hier waren, na, wo habe ich die? 00:42.740 --> 00:44.350 Da hatte ich die beiden Definitionen. 00:45.980 --> 00:49.420 Die Kostenmaße, das uniforme Kostenmaß, das logarithmische Kostenmaß, 00:49.500 --> 00:54.240 wo der wesentliche Punkt ist, dass man sich überlegt, spielt die Größe 00:54.240 --> 00:57.680 der Zahlen, die bearbeitet werden, eine Rolle für die Laufzeit des 00:57.680 --> 00:58.260 Programms? 00:58.520 --> 01:01.220 Und wenn das nicht der Fall ist, ist das uniforme Kostenmaß sinnvoll. 01:01.800 --> 01:06.900 Wenn die Größe der beteiligten Zahlen eine Rolle spielt, dann muss man 01:06.900 --> 01:10.440 sehen, dass man dann das logarithmische Kostenmaß nimmt. 01:10.700 --> 01:12.440 Und das hatten wir uns am Beispiel angeschaut. 01:13.120 --> 01:16.980 Und dann haben wir eben nochmal so ein paar andere Modelle kurz 01:16.980 --> 01:20.740 betrachtet und sahen dann, dass wir uns im Wesentlichen zurückziehen 01:20.740 --> 01:25.980 können, zumindest wenn es darum geht, dass die Größe der Zahlen keine 01:25.980 --> 01:26.620 Rolle spielt. 01:26.720 --> 01:32.700 Dann können wir bei einigen Problemen uns beschränken auf zum Beispiel 01:32.700 --> 01:35.100 einfach die geradlinigen Programme. 01:35.220 --> 01:37.100 Da spielen dann nur die arithmetischen Anweisungen eine Rolle. 01:38.080 --> 01:42.260 Oder bei, ups, da ist wieder eins zu... 01:42.260 --> 01:45.500 Und das andere waren die Entscheidungsbäume, bei denen nur die 01:45.500 --> 01:46.700 Vergleiche eine Rolle spielen. 01:46.700 --> 01:49.320 Bei einer ganzen anderen Klasse von Problemen, nämlich Such- und 01:49.320 --> 01:51.500 Sortierverfahren, da guckt man sich das an. 01:52.100 --> 01:55.200 Und ich hatte dann angefangen, Algorithmen zu klassifizieren, 01:55.320 --> 01:56.420 sequenzielle Algorithmen. 01:56.480 --> 01:58.840 Da hatten wir uns angeguckt, die Matrix-Multiplikation als ein 01:58.840 --> 01:59.820 typisches Beispiel. 02:00.320 --> 02:03.280 Naiver Ansatz, einfacher Ansatz mit dieser dreifach geschachtelten 02:03.280 --> 02:03.760 Schleife. 02:04.440 --> 02:06.800 Und ich hatte schon darauf hingewiesen, dass man aufpassen muss, wie 02:06.800 --> 02:11.360 das, was eigentlich mit den Zugriffen auf Speicherelemente, auf Matrix 02:11.360 --> 02:15.440 -Elemente passiert, dass dort auch noch arithmetische Operationen im 02:15.440 --> 02:16.140 Hintergrund laufen. 02:16.640 --> 02:18.040 Da gingen wir heute nochmal genauer darauf ein. 02:18.120 --> 02:20.140 Da hatten wir parallele Algorithmen angeschaut. 02:21.380 --> 02:25.260 Ganz kurz, dass das eben darum geht, ein Problem auf vielen Rechnern 02:25.260 --> 02:26.680 zu lösen in möglichst kurzer Zeit. 02:27.380 --> 02:31.800 Da hatte ich eben Ihnen gezeigt, diese Möglichkeit, das Skalarprodukt 02:31.800 --> 02:35.020 von zwei Vektoren als wesentliche Operation in der Matrix 02:35.020 --> 02:38.920 -Multiplikation mit einem Baum der Tiefe log n zu bearbeiten. 02:38.920 --> 02:42.820 Und wir hatten uns dann ganz kurz überlegt, dass es vielfältige 02:42.820 --> 02:46.160 parallele Berechnungsstrukturen gibt, die eine Rolle spielen beim 02:46.160 --> 02:47.880 Entwurf von Algorithmen. 02:48.580 --> 02:52.260 Und waren dabei auch eingegangen auf die Schreibkonflikte, die es 02:52.260 --> 02:55.560 geben kann, wenn ich also gleichzeitiges Schreiben ermöglichen möchte. 02:55.660 --> 02:58.560 Ich hatte dann die Verbindungsstrukturen angesprochen zwischen 02:58.560 --> 03:00.000 Parallelrechnern. 03:00.320 --> 03:04.420 Und da waren hier diese Reihe von Verbindungsstrukturen, die meisten 03:04.420 --> 03:05.680 von denen kannten Sie schon. 03:05.680 --> 03:08.480 Fairtree kannten Sie noch nicht, den habe ich kurz skizziert. 03:08.780 --> 03:13.140 Und dieses Reconfigurable Mesh habe ich auch ganz kurz angesprochen, 03:13.200 --> 03:15.940 dass man dort eben Verbindungen in einem zweidimensionalen Netz im 03:15.940 --> 03:20.420 Prinzip als Busstrukturen in jedem Takt schalten kann und dadurch dann 03:20.420 --> 03:25.400 in der Lage ist, komplexe Verbindungen in Programmen einzubinden. 03:25.640 --> 03:29.160 Und auch das führt dann zu interessanten neuen Algorithmen, auf die 03:29.160 --> 03:31.060 wir aber hier nicht weiter eingehen können. 03:31.060 --> 03:36.160 Ich wollte nur ansprechen, dass es solche Dinge halt als 03:36.160 --> 03:37.260 Berechnungsmodelle gibt. 03:37.960 --> 03:40.160 Und das ist die erste neue Folie von heute. 03:40.800 --> 03:43.600 Hardwarealgorithmen, eine andere Klasse von Algorithmen, bei denen ich 03:43.600 --> 03:45.100 wieder einen anderen Aspekt betrachte. 03:45.660 --> 03:49.980 Nämlich, ich möchte ein Problem wiederholt bearbeiten auf 03:49.980 --> 03:53.100 anwendungsspezifischer Hardware, speziell gebaut für die Lösung dieses 03:53.100 --> 03:53.760 Problems. 03:53.760 --> 03:57.140 Und dabei nutze ich natürlich bestmöglich die Ressourcen, die mir zur 03:57.140 --> 04:01.320 Verfügung stehen, für die Bearbeitung eines Problems. 04:01.380 --> 04:02.480 Also ich nutze Parallelität. 04:03.040 --> 04:06.280 Das heißt, ich möchte die Rechenzeit für eine Probleminstanz 04:06.280 --> 04:06.920 reduzieren. 04:07.320 --> 04:10.640 Und das andere, was ich eben machen kann, wenn ich die Verarbeitung in 04:10.640 --> 04:12.900 Hardware betrachte, ist, dass ich Pipelining nutzen kann. 04:13.960 --> 04:17.260 Und das ist etwas, was Sie auch kennen zum Teil schon, was ich hier 04:17.260 --> 04:20.580 aber nochmal mit einigen Beispielen belegen möchte. 04:20.580 --> 04:23.320 Ich möchte Ihnen zwei Beispiele angeben. 04:23.420 --> 04:26.140 Einmal ein Addierer, kennen Sie im Prinzip aus der 04:26.140 --> 04:26.580 Grundlagenvorlesung. 04:27.420 --> 04:31.780 Und dann ein Matrix-Multiplizierer, der eben auch sehr stark sowohl 04:31.780 --> 04:34.000 Parallelität als auch Pipelining einsetzt. 04:34.860 --> 04:36.460 Was ist da das Berechnungsmodell? 04:37.180 --> 04:40.680 Das Berechnungsmodell in dem Fall ist ein VLSI-Algorithmus. 04:42.920 --> 04:44.500 VLSI für Very Large Scale Integration. 04:44.580 --> 04:46.080 Man könnte auch sagen Hardware-Algorithmus. 04:46.660 --> 04:49.980 Das soll also andeuten, dass wir die Berechnungsstruktur in Hardware 04:49.980 --> 04:50.980 direkt modellieren müssen. 04:51.360 --> 04:53.460 Da haben wir einerseits den Rechnergraphen. 04:53.780 --> 04:57.220 Da hatte ich schon mal angedeutet, ein Rechnergraf könnte zum Beispiel 04:57.220 --> 04:58.160 ein Baum sein. 04:58.680 --> 05:02.760 Und wenn ein Rechnergraf ein irgendein Baum ist, dann muss ich mir 05:02.760 --> 05:05.300 überlegen, wie er dargestellt werden kann. 05:05.300 --> 05:09.680 Also in der Ebene als Hardware-Algorithmus muss ich ihn irgendwie 05:09.680 --> 05:10.620 zweidimensional darstellen. 05:10.980 --> 05:12.420 Dann spielt das Layout eine Rolle. 05:13.120 --> 05:16.040 Und da hatte ich auch schon neulich kurz darauf hingewiesen, dass man 05:16.040 --> 05:23.240 eventuell, wenn man einen Baum darstellen möchte, den halt so 05:23.240 --> 05:34.220 darstellen kann, dass man die Blätter an den Rand eines Chips legt und 05:34.220 --> 05:40.900 dann die benachbarten Knoten jeweils verbindet. 05:41.100 --> 05:43.900 Und dann würde man bei einem solchen Baum eben auf eine Fläche kommen 05:43.900 --> 05:47.480 von O von N mal Log N. 05:47.720 --> 05:52.120 N Blätter am Rand und dann tiefe Log N für diese einzelnen Schichten. 05:52.120 --> 05:57.420 Und die Alternative war halt dafür, dann einen Haarbaum zu nehmen, zum 05:57.420 --> 06:05.120 Beispiel so etwas, wo man die Blätter in Zweidimensionen anordnet und 06:05.120 --> 06:08.160 dadurch die nicht mehr am Rand hat, aber gleichmäßig über die Fläche 06:08.160 --> 06:08.740 verteilt. 06:08.880 --> 06:11.840 Deswegen eine Fläche, in dem Fall von O von N. 06:12.520 --> 06:17.000 Faktor N kleiner und auch eben eine andere Anordnung. 06:17.000 --> 06:20.080 Aber das zeigt einfach, welche Rolle das Layout spielt für die 06:20.080 --> 06:23.020 Flächenbedarf eines Algorithmus. 06:23.600 --> 06:27.780 Weniger als N geht natürlich nicht mit N Knoten und insofern, oder 06:27.780 --> 06:29.980 wenn ich N Blätter habe, 2 N-1 Knoten. 06:30.620 --> 06:33.460 Und das heißt, das wäre eine optimale Fläche, die ich da mit dem 06:33.460 --> 06:35.020 Haarbaum -Layout haben kann. 06:35.100 --> 06:38.200 Das hatte ich Ihnen schon mal kurz angedeutet, wie man so einen 06:38.200 --> 06:39.620 Haarbaum baut. 06:40.460 --> 06:42.780 Und das letzte ist dann das I.O.-Schema. 06:42.920 --> 06:45.760 Für ein Algorithmus, was das I.O.-Schema ist, ich muss sagen, zu 06:45.760 --> 06:50.480 welchen Takten während des Laufs eines Algorithmus muss ich welche 06:50.480 --> 06:53.720 Daten an den Eingängen meiner Hardware anlegen. 06:53.860 --> 06:57.100 Also zum Beispiel bei einem Baum, was kommt hier an den Blättern 06:57.100 --> 07:02.060 jeweils zu welchen Takten rein und wann kann ich irgendwo Ausgaben 07:02.060 --> 07:04.680 beobachten, dort irgendwelche Ergebnisse aus dem Algorithmus 07:04.680 --> 07:05.340 herausbekommen. 07:05.340 --> 07:09.620 Ein einfaches Beispiel, was Sie aus der Grundlagenvorlesung, für 07:09.620 --> 07:14.200 diejenigen, die die gehört haben, kennen, ist der Ripple-Carrier 07:14.200 --> 07:16.840 -Adder, der Adder mit durchlaufendem Übertrag. 07:17.400 --> 07:19.220 Sehr einfaches Verfahren. 07:20.460 --> 07:24.660 Sie wollen zwei Zahlen addieren und machen deshalb Bit parallel. 07:27.160 --> 07:30.880 Sie können im Prinzip die alle parallel addieren, die einzelnen Bit 07:30.880 --> 07:33.980 -Paare, aber natürlich müssen Sie den Übertrag durchlaufen lassen. 07:34.140 --> 07:36.200 Das ist hier angedeutet über diese Kästen. 07:36.660 --> 07:39.660 Sie haben jeweils zwei Eingänge für die einzelnen Bits. 07:39.760 --> 07:43.400 Wenn Sie zwei N-Bit-Zahlen haben, haben Sie also zwei N-Eingänge für 07:43.400 --> 07:46.620 die jeweils N-Bits und ich habe hier noch einen weiteren Eingang. 07:46.820 --> 07:50.700 Das ist der Eingang Nummer 1 hier für den Anfangsübertrag, der in der 07:50.700 --> 07:51.420 Regel 0 ist. 07:52.820 --> 07:58.400 Aber wenn man ihn auf 1 setzt, könnte man damit auch noch andere Dinge 07:58.400 --> 07:58.680 machen. 07:58.680 --> 08:02.680 Man könnte zum Beispiel auch diesen Ausgang Nummer 5, den Übertrag, 08:02.780 --> 08:08.220 der am Ende rauskommt, wieder hier auf der rechten Seite eingeben und 08:08.220 --> 08:11.180 hätte dann die Möglichkeit, mehrere Blöcke von Zahlen nacheinander zu 08:11.180 --> 08:11.520 addieren. 08:11.880 --> 08:15.940 Das sind so Dinge, die werde ich gleich nochmal etwas vertiefen. 08:16.700 --> 08:19.520 Also wir haben einen Grechner Graphen, der in dem Fall sehr einfach 08:19.520 --> 08:19.800 ist. 08:19.920 --> 08:24.700 Ein lineares Array von Knoten, von logischen Knoten. 08:25.500 --> 08:29.200 Das sind gerade Volladdierer, die jeweils getaktet arbeiten. 08:30.220 --> 08:33.800 Und Kantenmenge ist hier klar, Layout ist klar, das ist nicht weiter 08:33.800 --> 08:34.560 schwierig. 08:35.120 --> 08:37.640 Und das IO-Schema, wie sieht das aus? 08:37.740 --> 08:40.200 Das ist im Prinzip das Eingabeschema hier angedeutet. 08:40.760 --> 08:43.960 Hier ist angedeutet eine Folge von Berechnungen, die gemacht werden 08:43.960 --> 08:44.280 sollen. 08:44.420 --> 08:48.800 Das sind getaktete Volladdierer, das heißt im ersten Takt kann ich mit 08:48.800 --> 08:52.620 dem ersten Bit-Paar von einer hier in Schwarz angedeuteten Addition 08:52.620 --> 08:53.640 anfangen. 08:53.900 --> 08:57.960 Zwei Werte A0, B0, die werden addiert im Volladdierer. 08:58.500 --> 09:03.400 Und das wäre also praktisch der erste Takt, in dem zwei Werte dort 09:03.400 --> 09:04.200 addiert werden. 09:05.020 --> 09:07.380 Und es kommen hier rechts nur Nullen rein. 09:07.900 --> 09:10.320 In diesen, vielleicht nochmal kurz zurück, diese vier verschiedenen 09:10.320 --> 09:11.420 Farben sollen andeuten. 09:11.500 --> 09:14.300 Ich mache vier Additionen nacheinander. 09:14.300 --> 09:18.080 Und ich kann eben nach der ersten Addition der beiden 09:18.080 --> 09:22.500 niedrigsignifikanten Bits der schwarzen Addition gleich weitermachen. 09:22.540 --> 09:26.040 Ich bekomme das erste Ergebnis-Bit raus, kann in dem zweiten 09:26.040 --> 09:30.660 Volladdierer daneben schon dann die zweiten Bits addieren und den 09:30.660 --> 09:35.140 Übertrag aus dem A0, B0 und so geht das dann weiter. 09:35.300 --> 09:41.040 Und in diesem Takt habe ich dann im Prinzip vier gleichzeitig aktive 09:41.040 --> 09:41.800 Additionen. 09:41.800 --> 09:46.600 Die schwarze Addition ist im Prinzip dann fast beendet, weil ich dort 09:46.600 --> 09:49.920 A3, B3 drin habe, wenn ich vier bezahlen und addieren möchte. 09:50.400 --> 09:53.900 Die blaue ist halt einen Schritt weiter zurück, die rote noch ein 09:53.900 --> 09:56.060 weiter und die grüne Addition hat gerade angefangen. 09:56.180 --> 10:00.320 In dem Fall werden aber alle vier Volladdierer aktiv und ich habe also 10:00.320 --> 10:03.980 eine Hardware-Struktur, die ist voll ausgelastet. 10:03.980 --> 10:16.380 Die produziert in jedem Takt vier Bits von vier Additionen, aber eben 10:16.380 --> 10:17.140 zeitversetzt. 10:17.440 --> 10:24.760 Und alle Bits dieser schwarzen Addition, hier ist nochmal das ganze 10:24.760 --> 10:27.760 Schema zu sehen, die kommen eben zeitversetzt hier irgendwann raus. 10:28.500 --> 10:30.940 Jetzt könnte ich das noch, wenn ich möchte, könnte ich noch 10:30.940 --> 10:34.300 irgendwelche Verzögerungszellen dazu bauen, könnte dafür sorgen, dass 10:34.300 --> 10:40.540 diese S0, S1, S2 jeweils verzögert werden und dann würden tatsächlich 10:40.540 --> 10:41.860 alle Bits parallel rauskommen. 10:41.940 --> 10:44.840 Sofern das erforderlich wäre, dass man die parallel ablesen möchte. 10:45.020 --> 10:47.460 Nur dann müsste ich halt entsprechend noch mehr Hardware dazu bauen, 10:48.020 --> 10:49.980 auf die ich hier zunächst mal verzichte. 10:50.460 --> 10:51.800 Also, was sieht man? 10:51.880 --> 10:55.140 Wir haben ein Eingabeschema hier oben angedeutet. 10:55.140 --> 10:58.060 Wir haben ein Ausgabeschema, aus diesem Knoten kommen irgendwann die 10:58.060 --> 10:58.880 Summen -Bits raus. 10:59.660 --> 11:02.680 Und was ich eben auch machen kann, ich kann, sagt ich, wenn hier aus 11:02.680 --> 11:09.360 dem Ausgabeknoten Nummer 5 etwas rauskommt, ein Übertrag erzeugt wird, 11:09.780 --> 11:15.480 könnte ich den hier wieder eingeben und dann könnte ich im Prinzip 11:15.480 --> 11:20.600 hier nach, da könnte ich also weitermachen mit A4, jetzt nicht in Rot, 11:20.680 --> 11:22.140 sondern müsste ich in Schwarz weitermachen. 11:23.840 --> 11:27.720 Vollständigkeit halber kann ich das ja mal entsprechend so machen. 11:27.880 --> 11:36.280 Hier könnte ich also jetzt im Prinzip mit A4, B4 könnte ich hier 11:36.280 --> 11:36.880 weitermachen. 11:37.800 --> 11:42.840 Und entsprechend dann würde dort A5, B5 stehen und so weiter. 11:42.980 --> 11:45.680 Danach würde eine blaue Addition kommen, die könnte ich weiterführen. 11:45.680 --> 11:49.420 Ich könnte also im Prinzip hier beliebig lange Zahlen addieren mit 11:49.420 --> 11:55.740 diesem 4-Bit-Addierer, jeweils blockweise 4 Bits so im Pipelining 11:55.740 --> 11:56.220 -Verfahren. 11:56.600 --> 12:02.980 Könnte also dann, wenn ich eine lange Addition habe, eine Weile diesen 12:02.980 --> 12:11.080 4 -Bit-Addierer nutzen und hätte dann um den Faktor 4 eine kürzere 12:11.080 --> 12:13.600 Periode im Prinzip. 12:13.600 --> 12:18.140 Also das ist eine Möglichkeit, wie man dann solchen Rechner nutzen 12:18.140 --> 12:18.420 kann. 12:18.520 --> 12:22.820 Ich kann also Pipelining nutzen, ich nutze hier eigentlich keine 12:22.820 --> 12:27.800 Parallelität, weil die einzelne Rechenoperation, wenn ich mir das 12:27.800 --> 12:32.740 anschaue, die Addition von den 4 Zahlen, dauert natürlich 4 Takte. 12:33.800 --> 12:39.360 Wenn ich mir die Gesamtzeit anschaue, dann habe ich hier natürlich 12:39.360 --> 12:44.260 meine 4 Takte, aber ich kann eben in jedem Takt eine neue Addition im 12:44.260 --> 12:44.880 Prinzip beginnen. 12:45.140 --> 12:49.240 Und dadurch habe ich einen Durchsatz von einer Addition pro 12:49.240 --> 12:50.400 Zeiteinheit. 12:50.520 --> 12:55.300 Ich habe im Prinzip etwas, was ich Periode nenne, eine konstante 12:55.300 --> 12:55.820 Periode. 12:55.900 --> 12:58.280 Ich kann in jedem Takt eine neue Berechnung beginnen. 12:58.500 --> 13:04.980 Ich gehe meine Farbe wieder auf meine Standardfarbe Rot für den Stift. 13:05.640 --> 13:08.400 Und was habe ich ansonsten noch an Komplexität oder an Aufwand zu 13:08.400 --> 13:08.800 betrachten? 13:08.800 --> 13:12.200 Ich habe eine Zeit für die einzelne Berechnung, die ist linear in der 13:12.200 --> 13:16.540 Anzahl der Bits, also in der Anzahl der Bits der beiden Zahlen. 13:17.260 --> 13:20.640 Und die Fläche ist natürlich linear, der Durchsatz ist auch linear. 13:23.680 --> 13:30.140 Es sind pro Takt 4 Berechnungen gleichzeitig aktiv. 13:31.380 --> 13:39.420 Also, das ist insofern ein sehr interessanter Algorithmus, der zwar 13:39.420 --> 13:43.320 für die einzelne Berechnung viel Zeit braucht, aber durch die niedrige 13:43.320 --> 13:48.660 Periode in der Lage ist, mit einem sehr hohen Durchsatz zu arbeiten. 13:49.160 --> 13:52.280 Durchsatz-OVNN stimmt ja eigentlich nicht, sondern ich habe natürlich, 13:52.480 --> 13:55.620 wenn ich rechne, wie viele Berechnungen werden pro Zeiteinheit fertig, 13:55.620 --> 14:00.560 im Schnitt ist das eine Berechnung pro Zeiteinheit, die fertig wird. 14:01.620 --> 14:06.580 Und wenn ich halt N-Takte betrachte, werden dann N-Berechnungen in der 14:06.580 --> 14:08.800 Zeit im Prinzip fertig. 14:09.260 --> 14:10.600 Also Durchsatz ist OVN1. 14:11.200 --> 14:16.560 Ich habe aber der Parallelitätsgrad in dem Fall, der wäre 4, weil ich 14:16.560 --> 14:20.620 hier 4 Berechnungen gleichzeitig laufen lasse. 14:22.220 --> 14:27.740 Der Parallelitätsgrad der einzelnen Berechnung wäre auch wieder 1, 14:27.920 --> 14:28.940 weil die sequenziell ist. 14:29.440 --> 14:32.340 Aber der Pipelininggrad, den kann ich auch noch betrachten, also wie 14:32.340 --> 14:35.780 viele Berechnungen werden gleichzeitig aktiv. 14:36.260 --> 14:40.620 Das wäre also hier praktisch ein Schnitt durch dieses Zeitdiagramm. 14:41.320 --> 14:43.920 Da habe ich 4 Berechnungen, die gleichzeitig aktiv sein können. 14:44.020 --> 14:45.180 Das wäre der Pipelininggrad. 14:45.180 --> 14:50.340 Und damit habe ich auf jeden Fall diese Hardware sehr sinnvoll 14:50.340 --> 14:50.980 genutzt. 14:51.080 --> 14:54.440 Also das ist nur ein Beispiel für einen Hardware-Algorithmus-Ripple 14:54.440 --> 14:55.120 -Carrier -Dealer. 14:55.460 --> 14:59.700 Ein anderes Beispiel, Matrix-Multiplikation, da kommt jetzt wieder 14:59.700 --> 15:01.620 dieses Thema auf uns zurück. 15:02.100 --> 15:08.540 Matrix-Multiplikation ist ein Standardthema für algebraische Probleme. 15:09.080 --> 15:16.000 Also ein aufwendiges Problem, bei dem man halt mit dem 15:16.000 --> 15:19.680 Standardverfahren n hoch 3 Operationen ausführen muss. 15:19.860 --> 15:21.220 Und deswegen braucht das sehr viel Zeit. 15:22.040 --> 15:25.060 Und wenn wir jetzt versuchen, das parallel zu machen, da hatte ich 15:25.060 --> 15:26.980 schon darauf hingewiesen neulich bei dem Beispiel für 15:26.980 --> 15:31.420 Parallelalgorithmen, dass man im Prinzip mit n hoch 3 Prozessoren bei 15:31.420 --> 15:34.820 n -Kurz-n-Matrizen in logarithmischer Zeit das Matrix-Produkt 15:34.820 --> 15:35.660 berechnen kann. 15:35.660 --> 15:41.280 Wenn ich jetzt das in Hardware realisieren möchte, dann bekommen wir 15:41.280 --> 15:43.620 so etwas wie einen systolischen Algorithmus. 15:44.440 --> 15:48.180 Ein systolischer Algorithmus ist also einfach ein Algorithmus, der ein 15:48.180 --> 15:53.400 solches Netz von Hardware-Bausteinen sehr effizient ausnutzt, dadurch, 15:53.740 --> 15:58.340 dass Daten durch ein solches Netz von Recheneinheiten 15:58.340 --> 15:59.400 hindurchgeschickt werden. 15:59.400 --> 16:05.780 In diesem Fall sieht das so aus, dass wir 3 Matrizen durch dieses Netz 16:05.780 --> 16:07.100 von Zellen hindurchschieben. 16:08.040 --> 16:12.600 Und wie sieht das jetzt genau aus, was wird hier gemacht? 16:12.680 --> 16:16.900 Wir wollen also 2 Matrizen multiplizieren, eine rote Matrix A mit 16:16.900 --> 16:21.560 einer blauen Matrix B multiplizieren, dann kommt eine grüne Matrix C 16:21.560 --> 16:22.020 raus. 16:22.780 --> 16:25.340 Die einzelnen Zellen in diesem Fall, was machen die? 16:25.340 --> 16:28.080 Die hier so hexagonal verbunden sind. 16:28.580 --> 16:33.660 Jede einzelne Zelle bekommt von unten eine Eingabe, von links oben 16:33.660 --> 16:36.300 eine Eingabe und von rechts oben eine Eingabe. 16:36.560 --> 16:40.560 Die beiden Eingaben sind gerade die Elemente A und B einer Matrix. 16:41.340 --> 16:44.900 Das C ist also das, was bisher schon berechnet wurde. 16:45.120 --> 16:47.420 Ich rechne also C plus A mal B aus. 16:47.420 --> 16:53.720 Das ist im Prinzip der Ausdruck, der bei der naiven Berechnung eines 16:53.720 --> 16:56.420 Skalarproduktes in der inneren Schleife steht. 16:57.080 --> 17:11.540 Wir wollen ja berechnen, die Summe A, I, K, B, K, J, K gleich 1 bis N. 17:12.300 --> 17:16.740 Damit wir das machen können, machen wir das aufgelöst in eine 17:16.740 --> 17:18.260 sequenzielle Berechnung dieser Summe. 17:18.700 --> 17:22.040 Jeweils zwei Elemente werden multipliziert und dann addiert auf die 17:22.040 --> 17:22.580 Zwischensumme. 17:22.740 --> 17:28.760 Das ist so ein Skalarprodukt-Berechnungselement, das hier so hexagonal 17:28.760 --> 17:29.920 verschaltet ist. 17:30.620 --> 17:35.320 Was hier angedeutet ist mit diesen ganzen Zahlen ist, jede Zahl deutet 17:35.320 --> 17:39.360 an, dass es jeweils ein, wenn hier steht 4,3, dann ist das das Element 17:39.360 --> 17:40.320 B4,3. 17:40.920 --> 17:45.960 Die rote 4,3 ist eben das Element A4,3 und hier unten auch eine 4,3. 17:46.100 --> 17:52.080 Das ist also die grüne 4,3, das C-Element in das, mit dem wir also die 17:52.080 --> 17:54.400 ganzen Produkte aufsammeln wollen. 17:55.140 --> 17:59.900 Zu Anfang werden die grünen Werte alle auf 0 gesetzt und werden hier 17:59.900 --> 18:00.520 durchgeschoben. 18:00.520 --> 18:04.540 Jetzt ist die Situation dargestellt, also das Ganze fängt natürlich 18:04.540 --> 18:07.620 erstmal an, da kommen von außen irgendwann die Daten rein. 18:08.160 --> 18:11.880 Der erste relevante Augenblick ist der, wo sich hier in der mittleren 18:11.880 --> 18:18.240 Zelle die Elemente A11, B11 und C11 treffen. 18:19.660 --> 18:25.140 A11 kommt hier links oben an, B11 und C11 von unten, das ist zu Anfang 18:25.140 --> 18:25.480 0. 18:25.480 --> 18:31.320 Die beiden werden addiert und im nächsten Takt, es läuft das hier also 18:31.320 --> 18:35.240 immer so schön von unten nach oben, das läuft in der Richtung, das 18:35.240 --> 18:36.140 läuft in der Richtung. 18:36.440 --> 18:42.260 Im nächsten Takt wandert also dieses C11 in dies Feld da oben rein und 18:42.260 --> 18:51.720 gleichzeitig werden sich treffen welche Elemente A11, B12 und C12. 18:51.720 --> 18:57.560 Es werden also dann A11 modifiziert mit B12 und es wird addiert auf 18:57.560 --> 19:00.020 das C12, was zu Anfang 0 ist. 19:00.200 --> 19:10.200 Naja, das ist also das erste Produkt für das Produkt von C12. 19:11.060 --> 19:14.640 Das schauen wir uns an, dann sind also diese drei Zellen anschließend 19:14.640 --> 19:15.120 aktiv. 19:15.120 --> 19:21.200 Da werden also jetzt jeweils die dort eingegangenen A- und B-Elemente 19:21.200 --> 19:25.020 modifiziert und addiert auf das, was von unten mit der Matrix C 19:25.020 --> 19:25.700 gekommen ist. 19:26.080 --> 19:31.580 Außerdem wurde hier oben drüber, hier wurde ja C11 berechnet, also das 19:31.580 --> 19:33.760 erste Produkt A11 mal B11. 19:33.760 --> 19:40.420 Und dann wird im nächsten Takt werden also hier A12 und B21 addiert 19:40.420 --> 19:42.760 auf A11 mal B11. 19:43.680 --> 19:47.420 Und deswegen wird hier also die nächste Komponente von dem 19:47.420 --> 19:51.860 Skalarprodukt C11 dadurch entstehen und so geht das weiter. 19:52.920 --> 19:56.980 Der Bereich der aktiven Elemente, wo tatsächlich etwas Signifikantes 19:56.980 --> 19:58.300 passiert, wird immer größer. 19:58.300 --> 20:03.900 Und dann nach vier Takten, also ausgehend von dem Zeitpunkt, wo wir 20:03.900 --> 20:08.420 hier das erste Mal eine sinnvolle Berechnung hatten, kommt hier oben 20:08.420 --> 20:17.380 die Summe der vier Skalarprodukte A1K mal BK1 raus. 20:17.960 --> 20:19.100 Für K gleich 1 bis 4. 20:19.500 --> 20:24.100 Und gleichzeitig wird in den anderen Zellen hier weiter gerechnet. 20:24.100 --> 20:28.040 Das heißt, was man sieht ist, dass immer nur ein Drittel der Zellen 20:28.040 --> 20:29.320 gerade aktiv ist. 20:30.020 --> 20:33.500 Und was man eben auch sieht hier, das ändert sich von Takt zu Takt. 20:34.040 --> 20:37.080 Die dazwischenliegenden Zellen sind halt gerade dann nicht aktiv, da 20:37.080 --> 20:42.500 sind keine aktiven Elemente, die dort reingebracht werden. 20:42.920 --> 20:44.300 Das ist also das ganze Schema. 20:44.840 --> 20:50.080 Wir haben also diese A und B, die hier von oben nach unten oder so 20:50.080 --> 20:51.340 schräg diagonal da durchlaufen. 20:51.340 --> 20:52.780 Das C von unten. 20:52.920 --> 20:56.840 Und auf diese Art und Weise werden also Daten im Prinzip durch ein 20:56.840 --> 20:58.780 Netz von Zellen hindurch gepumpt. 20:58.860 --> 21:01.740 In jedem Takt passiert eine Berechnung. 21:02.540 --> 21:07.520 Und da das so eine gewisse Ähnlichkeit hat mit dem Fließen von Blut 21:07.520 --> 21:13.960 durch unsere Blutgefäße, deswegen haben das damals Kung und Leiserson 21:13.960 --> 21:16.160 einen systolischen Algorithmus genannt. 21:16.160 --> 21:18.920 Man hätte es auch nennen können einen iterativen Algorithmus. 21:19.300 --> 21:21.780 Die sind längst bekannt gewesen, iterative Algorithmen. 21:21.880 --> 21:24.880 Systolischer Algorithmus ist etwas ganz Tolles, etwas Neues, hat mehr 21:24.880 --> 21:25.160 Aufmerksamkeit. 21:25.900 --> 21:30.340 Man muss immer sehen, wie man seine Ideen bezeichnet. 21:31.020 --> 21:34.860 Und dies hat dazu geführt, dass man viele systolische Algorithmen 21:34.860 --> 21:37.960 entwickelt hat, bei denen genau dieses Prinzip verfolgt wird. 21:38.060 --> 21:41.220 Ich habe ein Netz von aktiven Zellen, die irgendwelche Berechnungen 21:41.220 --> 21:46.740 ausführen können und ich pumpe Daten dorthin durch mit einem gewissen 21:46.740 --> 21:48.760 Berechnungsschema im Kopf. 21:49.320 --> 21:52.340 Und das, was dann am Ende ausgegeben wird, sind gerade die Werte, die 21:52.340 --> 21:53.500 berechnet werden sollten. 21:53.600 --> 21:58.680 In diesem Fall die einzelnen Elemente der Produktmatrix C. 21:59.800 --> 22:03.980 Also, was habe ich hier für Kosten zu berücksichtigen? 22:04.400 --> 22:08.440 Eine Zeit, die ist in dem Fall linear, Groß O von N. 22:08.440 --> 22:13.200 Ich habe eine Konstante mal die Dimension meiner Matrix. 22:13.780 --> 22:15.660 Also, wie lange dauert das, bis ich hier durchlaufe? 22:15.940 --> 22:22.900 Das kann man hier an der Matrix C sehen. 22:23.280 --> 22:24.440 Ich schiebe hier diese... 22:25.560 --> 22:28.080 das ist erstmal hier unten rein, das muss erstmal bis hier hin laufen. 22:28.580 --> 22:32.560 Und dann habe ich hier nochmal diese N-Takte, bis das Ergebnis draußen 22:32.560 --> 22:32.880 ist. 22:33.300 --> 22:36.500 Das heißt, ich habe hier von der ersten Eingabe bis dahinten hin, das 22:36.500 --> 22:41.100 ist für das erste Element, eine Zeit von 2N-1. 22:41.960 --> 22:45.900 Danach kommen die weiteren Elemente, jeweils mit einem Abstand 2 22:45.900 --> 22:46.400 Takte. 22:46.820 --> 22:49.880 Das heißt, das dauert schon eine gewisse Zeit, bis die ganze Matrix, 22:50.020 --> 22:52.760 also das letzte Element, bis das hier reingelaufen ist unten und dann 22:52.760 --> 22:55.100 da oben fertig berechnet rauskommt. 22:55.340 --> 22:56.760 Aber es ist auf jeden Fall linear. 22:58.100 --> 22:59.900 Es steht hier eine Periode von O von N. 23:00.180 --> 23:01.680 Also, wie sieht das mit der Periode aus? 23:01.900 --> 23:04.060 Das heißt, wir haben eine gewisse Berechnung hier angefangen. 23:04.060 --> 23:07.620 Die dauert eine gewisse Anzahl von Takten. 23:09.220 --> 23:13.060 Also, wenn wir uns nochmal das hier anschauen, alle 3 Takte kommt ein 23:13.060 --> 23:13.760 neues Element. 23:14.640 --> 23:17.440 Wir haben also nach 3... wie ist denn das? 23:17.500 --> 23:19.040 Wenn wir eine genaue Zeit hier mal ausrechnen wollen. 23:19.520 --> 23:25.060 Wir haben 3 mal N-1 plus... 23:25.060 --> 23:28.480 Dann müsste nochmal... 23:28.480 --> 23:32.060 Nach der Zeit habe ich hier die alle... 23:32.980 --> 23:38.520 Hier habe ich ja die 1-1, 2-2-2 und so weiter bis C-N-N da drin. 23:41.320 --> 23:44.940 Und in dem Fall habe ich übrigens eine Bandbreite... 23:44.940 --> 23:46.560 Genau, hier habe ich noch eine gewisse Bandbreite drin. 23:47.700 --> 23:50.560 Hier gehe ich bis auf... 23:55.120 --> 24:00.740 In dem Fall habe ich hier als C eine... 24:01.320 --> 24:02.560 Das sind keine N-Kreuz... 24:02.560 --> 24:05.580 Genau, die Bandbreite in dem Fall wäre 4. 24:05.760 --> 24:09.560 Die Dimension meiner Matrix ist 8. 24:10.240 --> 24:11.140 Die Bandbreite 4. 24:11.240 --> 24:12.460 Deswegen habe ich hier diese Größe. 24:12.980 --> 24:14.560 Ich habe hier 3 mal N-1. 24:14.560 --> 24:17.520 N in dem Fall wäre... 24:17.520 --> 24:19.920 Also, lassen Sie mich das nochmal darstellen. 24:20.540 --> 24:22.280 Das ist das, was rauskommen soll. 24:22.360 --> 24:28.040 Ich habe hier 2 Bandmatrizen, die modifiziert werden. 24:28.180 --> 24:30.460 Und dann kommt eine Matrix raus. 24:30.520 --> 24:32.840 Die hat halt hier ein etwas größeres Band. 24:35.240 --> 24:42.400 Und in dem Fall habe ich also eine N-Kreuz-N-Matrix. 24:42.400 --> 24:45.700 Das ist die Bandbreite W. 24:46.140 --> 24:53.900 Das, was ich sagen wollte, war, dass wir hier plus 2 W minus 1 als 24:53.900 --> 24:57.800 Takte brauchen, um hier ganz durchzulaufen. 24:58.800 --> 25:02.600 Das ist also die Laufzeit für das letzte Element. 25:02.840 --> 25:08.480 Das heißt, wir haben 3 mal N-1, damit das letzte Element hier unten 25:08.480 --> 25:09.080 reingeht. 25:09.080 --> 25:17.620 Und die Länge hier ist genau 2 mal die Bandbreite minus 1. 25:17.920 --> 25:19.940 So, das ist... 25:19.940 --> 25:24.240 Und wenn das letzte Element reingelaufen ist, bin ich fertig. 25:26.960 --> 25:28.920 Und das wäre die Zeit. 25:29.240 --> 25:30.140 Was ist mit der Periode? 25:31.160 --> 25:31.980 Wieso Periode? 25:32.100 --> 25:33.260 Ich habe doch hier... 25:33.260 --> 25:36.600 Wieso kann ich hier irgendwie etwas im Pipelining-System machen? 25:36.600 --> 25:41.520 Das, was wir hier beobachtet haben, ist doch, dass in jedem Takt, hier 25:41.520 --> 25:45.460 mal kurz zurück, in jedem Takt nur ein Drittel der Elemente aktiv ist. 25:46.480 --> 25:49.800 Und ich könnte ja die anderen zwei Drittel auch ausnutzen. 25:50.440 --> 25:53.600 Indem ich einfach dieses Schema etwas verändere. 25:54.880 --> 25:57.600 Und hier bei diesem Schema dazwischen... 25:58.640 --> 26:02.520 Ich könnte ja hier das 4-1 nochmal hinschreiben. 26:02.760 --> 26:03.600 Oder die 4-1. 26:03.840 --> 26:05.440 So, könnte ich da nochmal hinschreiben. 26:05.440 --> 26:09.640 Und ich könnte jetzt irgendeine andere Farbe nehmen. 26:12.040 --> 26:15.980 Ich will keine andere Farbe nehmen. 26:16.320 --> 26:17.740 Ich sage hier, das ist 4-1-Strich. 26:18.180 --> 26:19.440 4-1-Strich. 26:19.640 --> 26:21.920 Und hier unten drunter noch 4-1-2-Strich. 26:23.180 --> 26:28.700 Und ich würde praktisch die Lücken jeweils füllen mit Elementen von 26:28.700 --> 26:30.500 weiteren Matrix-Multiplikationen. 26:30.500 --> 26:32.620 Ich würde also gerne noch berechnen. 26:33.080 --> 26:36.880 Eine Matrix-Multiplikation A-Strich mal B-Strich gleich C-Strich. 26:37.080 --> 26:40.820 Und A2-Strich mal B2-Strich gleich C2-Strich. 26:41.540 --> 26:48.960 So, dann hätte ich drei Matrix-Multiplikationen, die hier genau in 26:48.960 --> 26:51.840 einem Takt Abstand loslaufen könnten. 26:52.900 --> 26:56.640 Dann wäre in jedem Takt jede Zelle hier aktiv. 26:57.620 --> 27:00.780 Die Berechnungen würden sich überhaupt nicht stören gegenseitig. 27:00.860 --> 27:02.840 Die laufen ja hier durch die einzelnen Zellen durch. 27:05.240 --> 27:08.660 Und es treffen genau die richtigen Elemente jeweils aufeinander. 27:09.240 --> 27:13.060 Es wird ja nichts gespeichert in diesen Skalarproduktzellen, sondern 27:13.060 --> 27:15.160 es wird nur eine Funktion berechnet. 27:15.360 --> 27:19.880 Das, was reinkommt, links oben und rechts oben, wird multipliziert und 27:19.880 --> 27:22.880 addiert auf das, was von unten kam und nach oben wieder ausgegeben. 27:22.880 --> 27:30.580 Also da gibt es keine Rückwirkungen der verschiedenen Berechnungen. 27:30.700 --> 27:33.100 Ich könnte also drei Berechnungen parallel machen. 27:34.000 --> 27:37.200 Und das Ganze würde dann entsprechend eine gewisse Zeit dauern. 27:37.280 --> 27:39.820 Sie sehen hier, da steht ein Faktor 3 vor. 27:40.660 --> 27:43.920 Das heißt, insgesamt hätte ich dann tatsächlich eine Periode von N. 27:44.620 --> 27:45.960 Mit einer Konstante 1. 27:47.080 --> 27:52.220 Wenn ich drei Berechnungen habe, könnte ich im Schnitt alle N-Takte 27:52.220 --> 27:54.980 eine neue Matrixmultiplikation anfangen. 27:55.400 --> 27:58.860 Aufgeteilt ist es so, dass ich hier in drei aufeinanderfolgenden 27:58.860 --> 28:02.820 Takten etwas eingeben kann, dann eine Weile warten muss und dann 28:02.820 --> 28:06.060 könnte ich wieder drei neue Berechnungen loslaufen lassen. 28:06.640 --> 28:09.640 Und so könnte ich wieder dieses ganze Feld hier oben ausnutzen, 28:10.320 --> 28:14.640 vollständig nutzen, um aufeinanderfolgende Berechnungen auszuführen, 28:15.620 --> 28:17.780 wobei jeweils drei Berechnungen sich überlappen. 28:19.020 --> 28:23.020 Also das ist der Vorteil eines Hardware-Algorithmus, dass ich 28:23.020 --> 28:26.200 Berechnungen überlappend ausführen kann. 28:26.320 --> 28:31.200 Ich habe natürlich dann redundante Hardware zur Verfügung und muss 28:31.200 --> 28:36.860 jetzt sehen, dass ein Ausgabeschema für meine Berechnungen sinnvoll 28:36.860 --> 28:37.860 gestaltet wird. 28:37.940 --> 28:39.940 Ich muss wissen, wann ich welche Werte eingeben muss. 28:40.380 --> 28:42.960 Und das muss natürlich meine Rechnerumgebung entsprechend 28:42.960 --> 28:43.460 unterstützen. 28:44.180 --> 28:47.940 Auf die Art und Weise kann ich also von der Zeit, die ich vorher 28:47.940 --> 28:51.260 hatte, nämlich wir hatten n hoch 3 bei der sequentiellen 28:51.260 --> 28:57.840 Matrixmultiplikation, kann ich jetzt mit n Quadraten, ich könnte das 28:57.840 --> 29:02.200 Ganze auch mit einer vollen Bandbreite machen, dann hätte ich Fläche n 29:02.200 --> 29:08.640 Quadrat und hätte als Zeit und Periode linearen Aufwand. 29:08.640 --> 29:12.160 Das heißt, ich hätte eigentlich einen bestmöglichen Zeitgewinn 29:12.160 --> 29:16.000 verglichen mit dem Algorithmus, der Zeit n hoch 3 braucht im 29:16.000 --> 29:16.880 sequentiellen Fall. 29:18.060 --> 29:22.000 Also das ist eine recht gute Möglichkeit, die Matrixmultiplikation zu 29:22.000 --> 29:22.600 beschleunigen. 29:23.060 --> 29:24.740 Jetzt könnte man sich überlegen, geht das noch anders? 29:25.360 --> 29:29.680 Natürlich geht es noch anders, da gehen wir aber etwas später drauf 29:29.680 --> 29:30.000 ein. 29:31.740 --> 29:37.080 Das war jetzt nur ein Beispiel für solche Hardware-Algorithmen. 29:37.640 --> 29:42.280 Systolische Algorithmen sind ein interessanter Ansatz, um spezielle 29:42.280 --> 29:46.440 Funktionen sehr schnell ausführen zu lassen, so dass wir einen hohen 29:46.440 --> 29:47.560 Durchsatz ermöglichen können. 29:47.660 --> 29:50.080 Und es gibt eine Reihe von Anwendungen, wo man so etwas braucht. 29:50.560 --> 29:52.560 Da hatte ich schon zu Anfang darauf hingewiesen, zum Beispiel 29:52.560 --> 29:56.640 Signalverarbeitung, wo Sie mit hohem Durchsatz arbeiten müssen und 29:56.640 --> 29:59.240 dafür sorgen müssen, dass Sie eben die, meinetwegen bei 29:59.240 --> 30:03.040 Bildverarbeitung, typisches Beispiel Fernsehbilder, in der Lage sind, 30:03.320 --> 30:07.580 die Bildwiederholfrequenz tatsächlich einzuhalten, selbst wenn Sie 30:07.580 --> 30:12.460 eine gewisse Verzögerung haben bei der Darstellung der einzelnen 30:12.460 --> 30:14.520 Frames. 30:15.280 --> 30:23.360 So, das zu dem, was so Hardware-Algorithmen angeht, oder diese 30:23.360 --> 30:24.980 verschiedenen Klassen von Algorithmen angeht. 30:25.040 --> 30:29.120 Wenn ich jetzt daran gehe, den Berechnungsaufwand abzuschätzen, dann 30:29.120 --> 30:31.200 muss ich mir überlegen, was sind die relevanten Kriterien? 30:31.200 --> 30:37.020 Das eine sind Kosten, Qualität natürlich auch. 30:37.620 --> 30:40.120 Das hat etwas mit Entwurfskosten zu tun. 30:40.260 --> 30:41.880 Mit Entwurfskosten hängt das zusammen. 30:41.960 --> 30:46.320 Wir gucken uns im Wesentlichen an, bei sequenziellen Algorithmen, die 30:46.320 --> 30:47.500 Zeit, die wir brauchen. 30:47.740 --> 30:50.780 Und das ist eben die CPU-Zeit oder die Anzahl der Operationen, haben 30:50.780 --> 30:54.060 wir uns mit beschäftigt, wie man die zählen kann. 30:54.520 --> 30:57.140 Das andere war der Platz, die Anzahl Speicherzellen. 30:57.900 --> 30:59.760 Das ist auch alles bei sequenziellen Algorithmen. 30:59.760 --> 31:02.580 Bei Parallel-Algorithmen, was schauen wir uns da an? 31:02.800 --> 31:06.340 Wir müssen sehen, wenn es um effiziente Algorithmen geht, geht es 31:06.340 --> 31:10.500 darum, nutze ich die Rechner-Infrastruktur, die mir zur Verfügung 31:10.500 --> 31:14.480 steht, eigentlich bestmöglich aus oder wie gut nutze ich die aus. 31:14.980 --> 31:17.540 Bei Parallel-Algorithmen geht es natürlich auch um die Zeit. 31:18.200 --> 31:19.600 Wie viele Schritte brauche ich? 31:20.120 --> 31:24.180 Jeder Schritt entspricht jetzt einer Reihe von Operationen, die auf 31:24.180 --> 31:26.600 parallel arbeitenden Komponenten ausgeführt werden. 31:26.600 --> 31:29.000 Oder wie viele Takte brauche ich? 31:29.120 --> 31:30.820 Das ist die Zeit für die einzelne Berechnung. 31:31.400 --> 31:32.820 Der Platz spielt ja auch eine Rolle. 31:33.900 --> 31:37.100 Anzahl Speicherzellen pro Prozessor kann eine Rolle spielen. 31:37.180 --> 31:38.820 Wie ist mein ganzer Speicheraufwand dabei? 31:39.600 --> 31:42.720 Ich habe aber dann auch noch, hat eigentlich auch was mit Platz zu 31:42.720 --> 31:46.300 tun, nämlich die Anzahl der Prozessoren, die gleichzeitig aktiv sind. 31:46.480 --> 31:52.180 Wenn wir uns hier nochmal unser Beispiel hernehmen von der Matrix 31:52.180 --> 31:56.680 -Multiplikation oder Skalarprodukt-Berechnung, da brauchen Sie halt 31:56.680 --> 32:01.700 hier in der obersten Schicht die ganzen Multiplikationen. 32:02.560 --> 32:04.200 Die werden gleichzeitig ausgeführt. 32:04.280 --> 32:06.900 Wenn Sie ein ganzes Matrix-Produkt machen wollen in Zeitlog N, 32:07.240 --> 32:10.100 brauchen Sie dafür N hoch 3 oder N hoch 3 durch Log N in der 32:10.100 --> 32:13.780 optimierten Variante Prozessoren, die gleichzeitig arbeiten. 32:15.460 --> 32:20.440 Das ist der Parallelitätsgrad, der maximal zur Verfügung stehen muss, 32:20.500 --> 32:22.320 um dieses Verfahren durchführen zu können. 32:22.320 --> 32:25.380 Das ist die Anzahl der gleichzeitig aktiven Prozessoren. 32:26.540 --> 32:28.520 Das kann sich ändern im Laufe der Berechnung. 32:28.620 --> 32:32.680 Wenn Sie am Ende dann hier alles zusammengefügt haben, kommen Sie hier 32:32.680 --> 32:35.840 darauf, dass Sie nur noch einen Prozessor brauchen am Ende. 32:36.380 --> 32:38.300 Es reduziert sich halt in jedem Takt um die Hälfte. 32:39.220 --> 32:44.280 Aber Sie hatten einen Zeitpunkt, wo Sie diese N hoch 3 durch Log N 32:44.280 --> 32:46.040 Prozessoren tatsächlich benötigten. 32:46.160 --> 32:47.560 Das ist dann der Parallelitätsgrad. 32:47.560 --> 32:51.780 So viele Rechner müssen Sie bereitstellen, um Ihren Algorithmus 32:51.780 --> 32:52.780 ausführen zu können. 32:53.520 --> 32:57.860 Dann schaut man sich an, was ist eigentlich der Vorteil, den ich 32:57.860 --> 33:01.640 erziele durch Einsatz von parallel arbeitenden Prozessoren. 33:02.520 --> 33:10.960 Wenn ich ein Verfahren habe, bei dem ich 100 Berechnungen machen muss 33:10.960 --> 33:15.600 und ich mache das Ganze jetzt parallel mit 5 Prozessoren, dann gehe 33:15.600 --> 33:18.360 ich davon aus, dass ich nur noch 20 Schritte brauche, weil ich ja 5 33:18.360 --> 33:19.600 jeweils parallel machen kann. 33:20.520 --> 33:22.620 Das ist nicht unbedingt immer der Fall. 33:23.220 --> 33:24.740 Vor allen Dingen muss man sich eines überlegen. 33:25.400 --> 33:28.560 Ich könnte mir irgendeinen sequentiellen Algorithmus hernehmen, der 33:28.560 --> 33:31.820 vielleicht gar nicht so intelligent gemacht ist, und jetzt mache ich 33:31.820 --> 33:36.820 den parallel und kann da einen ziemlichen Vorteil herausfinden. 33:37.700 --> 33:40.040 Ich sollte mir aber vielleicht auch überlegen, wie ich meinen 33:40.040 --> 33:43.380 Algorithmus bestmöglich sequentiell erst mal machen kann. 33:45.320 --> 33:48.300 Und das wäre meine Zeit T1. 33:48.600 --> 33:55.920 Was ist das bestmögliche Verfahren, um sequentiell ein Problem zu 33:55.920 --> 33:56.260 lösen? 33:57.760 --> 34:02.720 Und dann schaue ich mir an, wie viel Zeit ich brauche mit meinem 34:02.720 --> 34:03.880 parallelen Algorithmus. 34:04.400 --> 34:07.800 Denn dann kann ich etwas darüber sagen, wie groß der Zeitgewinn ist, 34:07.980 --> 34:09.780 durch Einsatz von Parallelität. 34:11.040 --> 34:14.920 Ich kann natürlich immer sagen, für einen speziellen Algorithmus habe 34:14.920 --> 34:17.860 ich durch Parallelität einen gewissen Zeitgewinn erzielt. 34:18.520 --> 34:21.500 Es könnte aber sein, dass ich den gleichen Zeitgewinn durch einen 34:21.500 --> 34:24.660 intelligenteren Einsatz meines einen Prozessors schon hinbekommen 34:24.660 --> 34:24.920 hätte. 34:25.920 --> 34:27.200 Und da gibt es viele Beispiele. 34:28.020 --> 34:34.920 Also beim Sortieren wissen Sie noch, dass es da Verfahren gibt, die in 34:34.920 --> 34:36.100 quadratischer Zeit laufen. 34:39.060 --> 34:42.780 Also ich kann natürlich das Verfahren, das in Zeit n² läuft, 34:42.920 --> 34:46.740 parallelisieren und kriege vielleicht eine Zeit von n raus oder 34:46.740 --> 34:47.660 vielleicht auch noch weniger. 34:48.540 --> 34:52.900 Aber es könnte ja sein, dass ich, und ich weiß ja, ich könnte allein 34:52.900 --> 34:58.560 durch bessere Organisation meiner sequentiellen Berechnung von n² auf 34:58.560 --> 34:59.340 n log n kommen. 34:59.540 --> 35:02.060 Hätte also allein dadurch schon einen Zeitgewinn. 35:02.060 --> 35:07.560 Deswegen optimale sequentielle Zeit durch die parallele Zeit mit p 35:07.560 --> 35:08.240 -Prozessoren. 35:09.320 --> 35:14.060 Und das ist mein Zeitgewinn, den ich erzielen kann, der natürlich 35:14.060 --> 35:16.580 immer kleiner gleich p ist. 35:18.100 --> 35:24.860 Das Interessante ist, Sie finden Artikel über einen superlinearen 35:24.860 --> 35:25.480 Speedup. 35:26.920 --> 35:29.580 Superlineare Speedup würde bedeuten, Sie haben einen höheren 35:29.580 --> 35:31.960 Zeitgewinn als p mit p-Prozessoren. 35:33.700 --> 35:39.380 Das kann tatsächlich passieren, wenn Sie bestimmte Algorithmen sich 35:39.380 --> 35:47.320 anschauen, bei denen Sie auf einmal, bei denen Sie meinetwegen eine 35:47.320 --> 35:51.380 Struktur haben, Sie haben irgendeinen Baum und Sie wissen, es gibt 35:51.380 --> 35:57.500 hier irgendwelche Berechnungen, die laufen sehr lange und Sie müssen 35:57.500 --> 36:00.580 also meinetwegen einen Branch-and-Bound-Baum abarbeiten. 36:01.460 --> 36:04.880 Und da gibt es einige Pfade, einige Wege, die dauern sehr lange und 36:04.880 --> 36:06.140 einige, die gehen kürzer. 36:08.240 --> 36:11.880 Und wenn Sie sich jetzt anschauen, den sequentiellen Aufwand, die 36:11.880 --> 36:15.560 sequentielle Zeit, um Branch-and-Bound-Verfahren zu machen, dann 36:15.560 --> 36:18.320 laufen Sie dann eine Zeit lang durch diesen Baum durch und schneiden 36:18.320 --> 36:19.480 immer irgendetwas ab. 36:19.480 --> 36:22.520 Und irgendwann kommen Sie auf die optimale Lösung. 36:23.280 --> 36:27.080 Wenn Sie das Ganze parallel machen, können Sie parallel in diesem Baum 36:27.080 --> 36:30.820 arbeiten und können vielleicht viel früher auf den günstigen Abschnitt 36:30.820 --> 36:34.740 kommen, wo Sie schon vorzeitig auf eine optimale Lösung gekommen sind. 36:36.000 --> 36:43.340 Und dann kann es passieren, dass Sie mit p-Prozessoren oder eben der 36:43.340 --> 36:46.380 Anzahl der Prozessoren, die Sie parallel arbeiten lassen, tatsächlich 36:46.380 --> 36:50.660 im Vergleich zu dem durchschnittlichen sequentiellen Aufwand einen 36:50.660 --> 36:54.100 Vorteil haben, der höher ist als die Anzahl der Prozessoren. 36:54.360 --> 36:56.040 Das gibt es in gewissen Situationen. 36:56.600 --> 37:00.560 So etwas kommt bei den Algorithmen, die wir hier betrachten, aber 37:00.560 --> 37:01.680 nicht vor. 37:03.000 --> 37:07.200 Also normalerweise haben wir eine Anzahl von Operationen, die 37:07.200 --> 37:10.540 normalerweise beim sequentiellen Algorithmus auftauchen. 37:10.540 --> 37:15.540 Und wenn die alle ausgeführt werden müssen, alle diese Operationen, 37:16.260 --> 37:20.800 dann kann ich durch Parallelität maximal den Zeitgewinn p haben. 37:21.720 --> 37:25.040 Wenn ich aber weiß, ich muss nicht unbedingt alle diese Operationen 37:25.040 --> 37:28.380 ausführen, sondern es könnte sein, dass ich durch gewisse Erkenntnisse 37:28.380 --> 37:31.420 während meiner Berechnung einige Sachen schon abschneiden kann, dann 37:31.420 --> 37:33.400 könnte der Zeitgewinn sogar mal höher sein. 37:36.160 --> 37:38.620 Normalerweise wird der Zeitgewinn kleiner sein als p. 37:38.620 --> 37:42.740 Also zum Beispiel bei dem Skalarprodukt hatten wir gesehen, wir haben 37:42.740 --> 37:45.420 gewisse Abhängigkeiten, logische Abhängigkeiten zwischen den 37:45.420 --> 37:50.780 Berechnungen, sodass wir gar nicht wirklich alle Operationen 37:50.780 --> 37:54.280 gleichzeitig ausführen können oder gleichmäßig verteilen können auf 37:54.280 --> 37:55.200 die p-Prozessoren. 37:55.640 --> 37:57.380 Und dann dauert es halt doch etwas länger. 37:59.200 --> 38:02.400 Und das heißt, logische Abhängigkeiten führen dazu, dass wir eben 38:02.400 --> 38:04.240 nicht alles gleichzeitig machen können. 38:04.380 --> 38:07.540 Gleichzeitig geht nur das, was logisch voneinander unabhängig ist. 38:07.540 --> 38:11.060 Und das muss man jetzt bestmöglich so strukturieren, damit man einen 38:11.060 --> 38:12.940 möglichst hohen Zeitgewinn bekommt. 38:13.580 --> 38:18.680 Also mit N3-Prozessoren bei der Matrix-Multiplikation kann ich keinen 38:18.680 --> 38:22.600 optimalen Zeitgewinn bekommen, sondern nur einen Zeitgewinn von N3 38:22.600 --> 38:23.520 durch Log N. 38:24.100 --> 38:27.380 Wenn ich N3 durch Log N Prozessoren verwende, bei der Matrix 38:27.380 --> 38:30.640 -Multiplikation hatten wir gesehen, kann ich tatsächlich einen 38:30.640 --> 38:35.720 asymptotisch optimalen Zeitgewinn bekommen von N3 durch Log N. 38:37.180 --> 38:39.360 Aber nicht ganz genau. 38:39.560 --> 38:44.840 Also ich habe dann eben Faktor 2 noch länger als das Bestmögliche. 38:45.520 --> 38:48.480 Der nächste Punkt ist die Effizienz. 38:49.220 --> 38:51.480 Was ist jetzt die Effizienz einer Berechnung? 38:52.080 --> 38:55.360 Hier gucke ich auf die Effizienz, mit der ich eine 38:55.360 --> 38:57.340 Berechnungsressource ausnutze. 38:58.780 --> 39:04.620 Meine einzelnen Prozessoren führen jetzt hier so ein Skalarprodukt, 39:04.620 --> 39:06.180 das ich angedeutet habe, aus. 39:07.360 --> 39:11.460 Und die sind einmal sehr aktiv, dann müssen sie eine Zeit lang 39:11.460 --> 39:12.400 vielleicht gar nichts machen. 39:12.920 --> 39:18.600 Das heißt, der einzelne Prozessor trägt nicht 100% zu dem Zeitgewinn 39:18.600 --> 39:18.960 bei. 39:19.660 --> 39:23.140 Und das wird genau dadurch ausgedrückt, dass ich den Zeitgewinn, den 39:23.140 --> 39:26.940 ich erzielt habe, dividiere durch die Anzahl der Prozessoren. 39:27.960 --> 39:31.580 Was ist der Anteil des einzelnen Prozessors an diesem Zeitgewinn? 39:31.980 --> 39:39.040 Wenn ich einen optimalen Zeitgewinn habe von P, dann wäre die 39:39.040 --> 39:40.280 Effizienz 1. 39:40.940 --> 39:47.900 Wenn ich weniger Zeitgewinn habe, dann ist die Effizienz kleiner 39:47.900 --> 39:48.480 gleich 1. 39:48.480 --> 39:52.000 Das heißt, das gibt mir im Prinzip an, zu wie viel Prozent ist der 39:52.000 --> 39:56.140 einzelne Prozessor ausgelastet, um einen gewissen Zeitgewinn zu 39:56.140 --> 39:56.520 erzielen. 39:56.800 --> 40:00.100 Und das ist eben wichtig für die Effizienz, mit der ich meine Rechner 40:00.100 --> 40:00.460 nutze. 40:01.280 --> 40:05.000 Wir hatten gesehen zum Beispiel, wenn ich die Matrix-Modifikation auf 40:05.000 --> 40:09.140 diesem hexagonal verbundenen Feld mache, wenn ich das ohne Pipelining 40:09.140 --> 40:14.520 benutze, da ist jeder Prozessor nur zu einem Drittel ausgenutzt, weil 40:14.520 --> 40:16.240 er nur in jedem dritten Takt aktiv ist. 40:16.960 --> 40:20.880 Aber wenn ich Pipelining mache, kann ich ihn vollständig nutzen. 40:21.000 --> 40:24.400 Dann hätte ich also eine bestmögliche Effizienz, eine bestmögliche 40:24.400 --> 40:25.540 Auslastung meiner Ressourcen. 40:26.300 --> 40:28.880 Und das ist ja auch etwas, was man betrachten muss, wie gut werden 40:28.880 --> 40:32.980 meine Ressourcen genutzt, um ein Berechnungsergebnis zu bekommen. 40:34.380 --> 40:36.200 Und dann gibt es noch die Skalierbarkeit. 40:36.460 --> 40:38.600 Sie sehen, bei Parallelalgorithmen gibt es sehr viele verschiedene 40:38.600 --> 40:39.500 Dinge, die man sich anguckt. 40:39.780 --> 40:40.900 Skalierbarkeit ist auch wichtig. 40:40.900 --> 40:47.200 Wenn ich die Problemgröße variiere, habe ich dann mit einem doppelt so 40:47.200 --> 40:50.660 großen Parallelitätsgrad auch eine halb so große Zeit. 40:50.980 --> 40:54.220 Es ist klar, dass das nicht immer funktionieren wird, weil die 40:54.220 --> 40:58.520 logischen Abhängigkeiten vielleicht stärker zuschlagen. 41:00.440 --> 41:03.620 Bei variierendem Parallelitätsgrad größere Anzahl Prozessoren, 41:03.780 --> 41:05.000 variierende Problemgröße. 41:05.000 --> 41:09.380 Sie haben Problemgröße, beliebig große Matrizen. 41:09.500 --> 41:12.960 Sie erhöhen die Größe der Matrix, können Sie immer noch den gleichen 41:12.960 --> 41:13.960 Zeitgewinn bekommen. 41:15.800 --> 41:19.400 Bekommen Sie also, egal wie groß das Problem ist, immer den gleichen 41:19.400 --> 41:21.720 Zeitgewinn für Ihren Algorithmus. 41:22.320 --> 41:25.380 Das sind Dinge, die man sich auch anguckt, werden wir aber nicht 41:25.380 --> 41:26.180 genauer angucken. 41:26.320 --> 41:29.480 Das wäre in einer Vorlesung, wo wir nur Parallelalgorithmen 41:29.480 --> 41:30.780 betrachten, dann sinnvoll. 41:30.880 --> 41:33.040 Aber hier führt mich das ein bisschen zu weit. 41:34.180 --> 41:38.040 Und wenn wir dann uns anschauen, was noch dazu kommt bei VLSI 41:38.040 --> 41:40.400 -Algorithmen, dann haben wir natürlich zusätzlich noch den 41:40.400 --> 41:41.260 Flächenbedarf. 41:43.180 --> 41:46.600 Flächenbedarf ist also, hatte ich darauf hingewiesen, Fläche des 41:46.600 --> 41:47.140 Layouts. 41:47.280 --> 41:49.800 Und bei dem Flächenbedarf habe ich natürlich die ganzen 41:49.800 --> 41:52.280 Berechnungselemente mit zu berücksichtigen, die müssen irgendwo 41:52.280 --> 41:53.140 angeordnet werden. 41:53.580 --> 41:57.540 Aber dann habe ich auch den Platz für die Verschaltung, für die 41:57.540 --> 42:01.680 Verbindungen, die ja als Leiterbahnen auf der Fläche angeordnet werden 42:01.680 --> 42:01.940 müssen. 42:01.940 --> 42:05.180 Und da hatten wir schon Beispiele gesehen, dass das durchaus 42:05.180 --> 42:08.340 signifikante Flächenbedarf bewirken kann. 42:10.980 --> 42:14.940 Und deswegen ist das wichtig, hier nicht nur die Anzahl der aktiven 42:14.940 --> 42:18.300 Zellen anzugucken, sondern den gesamten Flächenbedarf für meinen 42:18.300 --> 42:18.940 Schaltkreis. 42:19.660 --> 42:24.520 Und dann das Weitere noch, der Pipelining-Grad, also wie viele 42:24.520 --> 42:26.360 Berechnungen sind gleichzeitig aktiv. 42:26.360 --> 42:34.680 Bei dem Beispiel mit dem Addierer, da waren eben bei Addition von n 42:34.680 --> 42:39.320 Bezahlen halt n Berechnungen gleichzeitig aktiv maximal. 42:39.840 --> 42:42.840 Bei der Matrix-Modifikation waren das drei, die gleichzeitig aktiv 42:42.840 --> 42:43.440 werden konnten. 42:44.680 --> 42:47.240 Und entsprechend kann ich dann sehen, wie gut kann ich mit einem 42:47.240 --> 42:51.540 gewissen Pipelining-Grad meinen Durchsatz entsprechend erhöhen. 42:51.540 --> 42:55.260 Wobei Pipelining-Grad und Durchsatz sind ja gerade inverse zueinander. 42:56.720 --> 43:01.800 So, das war alles jetzt zu sequentiellen, parallelen und Hardware 43:01.800 --> 43:02.360 -Algorithmen. 43:02.520 --> 43:03.980 Das sind die Dinge, die man da anschauen kann. 43:04.300 --> 43:05.680 Im Wesentlichen werden wir usw. 43:05.980 --> 43:09.560 betrachten Zeit bei den sequentiellen Algorithmen. 43:09.640 --> 43:14.660 Bei den parallelen Algorithmen Zeit, Parallelitätsgrad, Zeitgewinn und 43:14.660 --> 43:15.460 Effizienz. 43:15.460 --> 43:18.480 Und Hardware-Algorithmen betrachten wir praktisch nicht. 43:18.620 --> 43:21.700 Beziehungsweise die, die ich Ihnen vorstelle, die haben alle einen 43:21.700 --> 43:29.280 trivialen Flächenbedarf, weil da der Platz für die Verbindungen in der 43:29.280 --> 43:33.940 gleichen Größenordnung ist wie die Anzahl der Schaltelemente. 43:33.940 --> 43:37.900 Als letztes noch kurz ein Hinweis auf die verteilten Algorithmen. 43:37.900 --> 43:41.620 Das ist auch eine Klasse von Algorithmen, die relevant sind, die wir 43:41.620 --> 43:43.040 heute immer mehr ausführen. 43:43.180 --> 43:47.300 Auf einer Reihe von Rechnern, die irgendwo bereitstehen. 43:47.600 --> 43:53.440 Da ist die Motivation, ich möchte eine Menge sequentieller Prozesse 43:53.440 --> 43:56.520 ausführen, die unabhängig voneinander arbeiten. 43:57.880 --> 44:02.160 Das ist was anderes als vorher ein Problem parallel ausführen. 44:02.160 --> 44:08.000 Da will ich für eine Berechnung möglichst viele Knoten nutzen. 44:08.900 --> 44:13.340 Ich könnte so einen parallelen Algorithmus auch auf einem verteilten 44:13.340 --> 44:14.360 System ausführen. 44:14.920 --> 44:19.260 Aber zunächst mal habe ich hier eine Menge sequentieller Prozesse, die 44:19.260 --> 44:24.180 unabhängig voneinander arbeiten können, aber durchaus hin und wieder 44:24.180 --> 44:27.320 durch Kommunikation ihre Aktivitäten koordinieren. 44:29.100 --> 44:32.740 Und in der Regel natürlich auf einem verteilten System. 44:33.360 --> 44:36.800 Das heißt, wir haben in der Regel ein räumlich verteiltes Netz. 44:37.620 --> 44:41.600 Unabhängige Prozessoren, die irgendwie kommunizieren können. 44:42.720 --> 44:47.580 Das können homogene Netze sein, in der Regel sind es aber heterogene 44:47.580 --> 44:48.020 Netze. 44:48.140 --> 44:51.160 Das heißt, wir haben viele verschiedene Arten von Rechnern, die 44:51.160 --> 44:54.600 miteinander kommunizieren können und Aufgaben bearbeiten können. 44:54.600 --> 44:59.740 Und das, was wir hier als Aufwandsbewertung uns anschauen, das ist die 44:59.740 --> 45:00.960 Anzahl der Nachrichten. 45:02.140 --> 45:03.780 Und die Rechenzeit wird ignoriert. 45:04.800 --> 45:08.280 Mit folgender Begründung, bei verteilten Algorithmen, wenn ich die 45:08.280 --> 45:11.440 bewerten will, interessiert mich vor allen Dingen, was ist eigentlich 45:11.440 --> 45:16.160 der Aufwand für das Verteilen dieser Menge von sequentiellen 45:16.160 --> 45:18.740 Prozessen, die durchaus miteinander kooperieren. 45:18.740 --> 45:24.780 Und das, was die eigentlich berechnen müssen, das ist in der Regel 45:24.780 --> 45:27.340 problemlos zu machen. 45:27.900 --> 45:32.000 Wenn man sich anschaut, eine Nachricht zu verschicken, brauche ich 45:32.000 --> 45:34.640 Zeit im Bereich von Millisekunden. 45:34.840 --> 45:37.300 Wenn ich eine Rechenoperation ausführe, bin ich im 45:37.300 --> 45:38.300 Nanosekundenbereich. 45:38.860 --> 45:42.980 Das heißt, ich kann sehr viele Operationen machen, während ich eine 45:42.980 --> 45:43.780 Nachricht verschicke. 45:43.780 --> 45:49.240 Also offensichtlich kann man dann sagen, das ist in der gleichen 45:49.240 --> 45:51.360 Größenordnung, ich kann die Rechenzeit ignorieren. 45:52.720 --> 45:56.920 In der Praxis werde ich natürlich versuchen, Algorithmen so zu 45:56.920 --> 46:01.160 entwerfen, dass die Kommunikation gar keine Rolle spielt. 46:01.440 --> 46:06.360 Das heißt, da werde ich sequentielle Prozesse verteilen, die relativ 46:06.360 --> 46:08.000 rechenaufwendig sind. 46:08.000 --> 46:14.660 Und während ich auf den einzelnen Knoten in meinem System hier rechne 46:14.660 --> 46:19.180 und die irgendwie verbunden sind, miteinander Nachrichten austauschen 46:19.180 --> 46:22.800 können, während ich hier rechne, werden meine Nachrichten hier 46:22.800 --> 46:28.000 geschickt und ich kann diese Kommunikationszeit im Prinzip verstecken 46:28.000 --> 46:29.460 hinter der Rechenzeit. 46:29.460 --> 46:32.900 Das heißt, dann würde ich nicht so etwas machen, dass ich etwas 46:32.900 --> 46:37.180 berechne, dann warte, kommuniziere und dann irgendwann weiter 46:37.180 --> 46:45.060 berechne, sondern ich kommuniziere meinetwegen mit irgendeinem 46:45.060 --> 46:49.460 anderen, wenn das hier die Anzahl der Prozesse ist. 46:50.560 --> 46:54.720 Ich würde Nachrichten hin und her schicken von einem Prozess zu einem 46:54.720 --> 46:56.680 anderen Prozess, das dauert eine gewisse Zeit. 46:58.880 --> 47:03.420 Ich würde diese Zeiten, die ich für Kommunikation brauche, möglichst 47:03.420 --> 47:04.740 verstecken hinter Berechnungen. 47:04.940 --> 47:09.140 Das heißt, in der Realität werde ich Rechenzeit nicht ignorieren, 47:09.220 --> 47:13.560 sondern werde nur solche Prozesse verteilen, die tatsächlich viel Zeit 47:13.560 --> 47:18.300 brauchen, sodass der Aufwand für die Nachrichten vernachlässigt werden 47:18.300 --> 47:18.620 kann. 47:18.620 --> 47:23.640 Wenn ich aber verteilte Algorithmen betrachte und sehe, welchen 47:23.640 --> 47:29.840 Aufwand bringt mir eigentlich dieses Verteilen einer Berechnung über 47:29.840 --> 47:33.420 verschiedene Prozesse, dann muss ich mir anschauen, wie viele 47:33.420 --> 47:35.360 Nachrichten muss ich dort tatsächlich verschicken. 47:36.320 --> 47:41.220 Und das ist dann der Aufwand für das Verteilen meiner Menge von 47:41.220 --> 47:44.060 sequentiellen Prozessen, die irgendetwas gemeinsam tun sollen. 47:46.560 --> 47:49.640 Problem der Praxis habe ich gerade darauf hingewiesen. 47:50.800 --> 47:53.060 Kommunikationsaufwand hinter Berechnungen verstecken ist da das 47:53.060 --> 47:53.720 Wesentliche. 47:54.400 --> 47:57.200 Ich brauche da natürlich einen extra Prozessor, der in der Lage ist, 47:57.220 --> 48:00.220 die Kommunikation abzuwickeln, aber das ist ja in der Regel der Fall. 48:02.380 --> 48:06.360 Wir gehen in dieser Vorlesung auf verteilte Algorithmen ganz am Ende. 48:06.440 --> 48:08.360 Da haben wir nochmal einen Abschnitt, wo wir auf verteilte Algorithmen 48:08.360 --> 48:09.860 ein bisschen eingehen, wo wir das betrachten. 48:12.420 --> 48:15.660 Insofern kommt das auch vor, aber bis dahin werden wir uns nur 48:15.660 --> 48:19.640 sequentielle und parallele Algorithmen, zum Teil auch systolische 48:19.640 --> 48:20.840 Algorithmen anschauen. 48:23.000 --> 48:25.900 Ein paar konkrete Beispiele für verteilte Systeme ist klar. 48:26.020 --> 48:28.660 Alle Rechner, die irgendwie miteinander kommunizieren können, in einem 48:28.660 --> 48:33.280 Institut, in der Fakultät, im Rechenzentrum, da haben wir große 48:33.280 --> 48:39.440 Rechencluster, die über Nachrichten kommunizieren. 48:40.080 --> 48:42.920 Und wir wissen, wir können auch alle Rechner im Netz ansprechen. 48:43.480 --> 48:54.760 Wir haben ein System, das nennt sich Josh Car Job Scheduling. 48:55.680 --> 49:01.320 Das ist ein System, mit dem wir unabhängige Prozesse verteilen können 49:01.320 --> 49:02.000 auf Rechner. 49:02.840 --> 49:06.460 Und wenn Sie zum Beispiel eine Auswertung machen wollen, wie ein 49:06.460 --> 49:11.780 bestimmter evolutionärer Algorithmus ein schönes Problem löst, dann 49:11.780 --> 49:13.880 wollen Sie das ausprobieren für viele Probleminstanzen. 49:14.740 --> 49:18.700 Sie müssen Berechnungen mehrfach wiederholen, über eine Anzahl von 49:18.700 --> 49:21.740 Wiederholungen, weil das randomisierte Algorithmen sind, zu sehen, wie 49:21.740 --> 49:26.760 ist so die mittlere Zeit, um irgendeine bestimmte Lösungsqualität zu 49:26.760 --> 49:27.240 erzielen. 49:27.620 --> 49:31.060 Dann haben Sie ganz viele Berechnungen zu machen, die mit vielen 49:31.060 --> 49:33.500 verschiedenen Parametersätzen laufen müssen. 49:34.000 --> 49:37.280 Das können Sie über ein Skript definieren und dann wollen Sie diese 49:37.280 --> 49:40.140 viele Berechnungen irgendwo auf einem Pool von Rechnern ausführen. 49:40.600 --> 49:44.000 Das wird über Josh Car hier bei uns gemacht, über allen möglichen 49:44.000 --> 49:46.180 Rechnern im KIT. 49:46.180 --> 49:50.340 Zum Beispiel unten die Rechner im Pool, hier im Zippool, die sind da 49:50.340 --> 49:51.120 alle mit angeschlossen. 49:51.580 --> 49:54.440 Und da laufen also im Hintergrund solche Berechnungen. 49:55.060 --> 50:02.820 Ähnliche Ideen gibt es, da Sie kennen vielleicht SETI oder Sie kennen 50:02.820 --> 50:04.700 vielleicht BOINC. 50:05.860 --> 50:07.880 Wer hat von SETI oder BOINC schon mal gehört? 50:09.020 --> 50:09.980 Keiner von Ihnen. 50:09.980 --> 50:17.760 SETI ist eine Initiative, mit der man, obwohl es glaube ich ohne das H 50:17.760 --> 50:23.900 geschrieben wird, Search for Extraterrestrial Intelligence, da geht es 50:23.900 --> 50:28.600 darum, dass man Signale aus dem All aufsammelt. 50:28.760 --> 50:35.840 Es werden ständig Signale aus dem All aufgezeichnet und man will dann 50:35.840 --> 50:38.620 sehen, inwieweit sind das irgendwelche intelligente Nachrichten. 50:38.620 --> 50:43.580 Dazu muss man halt irgendwie diese Daten, diese Zeitreihen 50:43.580 --> 50:44.260 analysieren. 50:45.000 --> 50:49.380 Und da gibt es eben einen Ansatz, alle verfügbare Rechenkapazität auf 50:49.380 --> 50:52.800 der Welt dafür zu nutzen, wenn diese Rechner nicht für andere Zecken 50:52.800 --> 50:53.620 gebraucht werden. 50:54.400 --> 50:56.740 Wann wird ein Rechner nicht für andere Zecken gebraucht? 50:56.840 --> 50:58.300 Wenn der Bildschirmschoner angeht. 50:59.120 --> 51:00.960 Also auf vielen Workstations. 51:01.260 --> 51:03.860 Wenn der Bildschirmschoner angeht, wird gerade nichts Vernünftiges 51:03.860 --> 51:04.760 ansonsten gemacht. 51:04.760 --> 51:07.900 Dann wird praktisch statt des Bildschirmschoners eine Routine 51:07.900 --> 51:11.880 angeworfen, die ein solches Datenpaket, das ist also gerade so eine 51:11.880 --> 51:17.340 Signalreihe, die man empfangen hat, die wird dann analysiert in der 51:17.340 --> 51:17.680 Zeit. 51:18.180 --> 51:22.700 Und auf die Art und Weise sind also sehr sehr viele Rechner in der 51:22.700 --> 51:26.480 Lage, eine solche Aufgabe zu bearbeiten, die eben aufgeteilt werden 51:26.480 --> 51:30.100 kann auf das Analysieren von jeweils irgendwelchen Abschnitten solcher 51:30.100 --> 51:35.060 Zeitreihen auf in irgendeiner Form intelligente Muster. 51:36.040 --> 51:37.860 Und das ist also das SETI-Projekt. 51:38.340 --> 51:42.640 Boing ist etwas ähnliches, wo man Rechner, die irgendwie Leerlauf 51:42.640 --> 51:44.860 haben, einsetzt für andere Zwecke. 51:45.020 --> 51:48.500 Und Joschka ist eine etwas intelligentere Version davon, die bei uns 51:48.500 --> 51:51.160 am Lehrstuhl entstanden ist und hier im KIT auch eingesetzt wird. 51:51.980 --> 51:56.500 Gut, das ist das, was wir hier genau zu verteilten Angriffen haben. 51:56.500 --> 52:00.360 Dann ein Aspekt, den ich gar nicht berücksichtigt habe, der aber eine 52:00.360 --> 52:03.400 Rolle spielt, immer mehr heutzutage, das ist der Energieaufwand. 52:04.320 --> 52:07.140 Auch darüber könnte man eine ganze Zeit erzählen, was ist eigentlich 52:07.140 --> 52:08.840 mit dem Energieaufwand für Berechnungen. 52:09.360 --> 52:12.520 Das ist ja mit Kosten verbunden, Energieeinsatz. 52:13.340 --> 52:16.360 Und die Frage ist, wie viel Energie wird benötigt zur Ausführung eines 52:16.360 --> 52:16.920 Programms. 52:17.000 --> 52:20.500 Das sind mittlerweile mehrere Prozent des weltweiten 52:20.500 --> 52:23.340 Energieverbrauchs, die auf Informationsverarbeitung zurückgehen. 52:24.560 --> 52:27.240 Und natürlich hängt das von vielen verschiedenen Dingen ab. 52:27.360 --> 52:28.600 Was für einen Prozessor habe ich? 52:28.700 --> 52:30.000 Mit welcher Technologie arbeitet der? 52:30.540 --> 52:31.780 Wie ist dessen Taktfrequenz? 52:31.900 --> 52:37.440 Je schneller die arbeiten, desto größer ist der Energieverbrauch. 52:37.440 --> 52:39.180 Der Energieverbrauch wird natürlich höher. 52:39.280 --> 52:42.580 Auf einigen Prozessoren könnten Sie ein Spiegelei braten, weil da so 52:42.580 --> 52:45.740 viel Energie oder so viel Wärme frei wird. 52:47.140 --> 52:51.240 Also da muss man schauen, was für einen Prozessor habe ich? 52:51.360 --> 52:53.320 Ist der einfach, parallel, superskalar? 52:54.280 --> 52:59.220 Wie viele gleichzeitig arbeitende Einheiten habe ich auf einem solchen 52:59.220 --> 53:00.120 Prozessor? 53:00.980 --> 53:02.140 Taktfrequenz spielt eine Rolle. 53:02.820 --> 53:04.280 Die Art der Datenzugriffe. 53:05.100 --> 53:06.720 Greife ich auf den Hauptspeicher zu? 53:06.820 --> 53:10.680 Greife ich auf die Festplatte zu oder Solid-State-Disk oder was immer? 53:10.840 --> 53:12.080 Greife ich auf andere Rechner zu? 53:12.080 --> 53:14.740 Was für Daten verarbeite ich? 53:15.000 --> 53:17.100 Sie wissen, dass man z.B. 53:17.240 --> 53:22.580 in der Lage ist, anhand der Leistungsaufnahme, also wie der 53:22.580 --> 53:25.800 Stromverbrauch ist, während eines Algorithmus, Sie schauen sich das 53:25.800 --> 53:29.460 an, irgendein Stromverbrauchsprofil während eines Algorithmus, Sie 53:29.460 --> 53:33.120 können aus dem Profil ablesen, welche Daten verarbeitet wurden. 53:33.640 --> 53:33.920 Warum? 53:34.440 --> 53:39.240 Weil ein Wechsel von 0 auf 1, von 1 auf 0, bei einer CMOS-Technologie 53:39.240 --> 53:43.620 dazu führt, dass zwischendurch kurz ein bisschen Strom fließt. 53:43.900 --> 53:46.640 Und wenn Sie eben keinen Wechsel haben, fließt kein Strom. 53:47.320 --> 53:52.500 Das heißt, der Stromverbrauch während einer Berechnung hat zu tun mit 53:52.500 --> 53:55.720 den Werten, die tatsächlich verarbeitet werden, welche Schaltvorgänge 53:55.720 --> 53:56.660 im Rechner ablaufen. 53:57.340 --> 53:59.680 Das ist genutzt worden, um z.B. 54:00.400 --> 54:06.700 bei irgendwelchen Smartcards rauszufinden, welche geheimen Schlüssel 54:06.700 --> 54:07.260 die verwenden. 54:08.100 --> 54:11.540 Auf die Art und Weise konnte man das rausfinden, konnten also einzelne 54:11.540 --> 54:13.820 Bits raten des geheimen Schlüssels. 54:15.200 --> 54:18.240 Sogenannter Seitenkanalangriff auf sichere Systeme, bei dem man in der 54:18.240 --> 54:22.520 Lage ist, völlig andere Aspekte einer Berechnung anzuschauen und 54:22.520 --> 54:25.360 daraus Rückschlüsse zu ziehen, auf das, was in einem Algorithmus 54:25.360 --> 54:25.740 passiert. 54:26.880 --> 54:29.640 Also, die verarbeiteten Daten spielen auch eine Rolle. 54:30.340 --> 54:33.840 Wenn man das nicht auf Smartcards anwendet, sondern auf ein Datacenter 54:33.840 --> 54:40.900 z.B., da könnte man sich überlegen, je nachdem, wie teuer gerade der 54:40.900 --> 54:45.240 Strom ist, wann lasse ich welche Berechnungen laufen, also wann 54:45.240 --> 54:49.160 verbrauche ich viel Strom, wann verbrauche ich weniger Strom und das 54:49.160 --> 54:52.840 kann ich über ein Scheduling meiner Anwendungen anpassen. 54:52.840 --> 54:56.040 Das heißt nicht, dass ich den Rechner nicht mehr nutze, aber es gibt 54:56.040 --> 54:59.180 bestimmte Anwendungen, die haben weniger Energieverbrauch als andere 54:59.180 --> 55:04.420 und das wäre ein aktives Scheduling eines Rechenzentrums unter den 55:04.420 --> 55:09.680 Gesichtspunkten, wie ich meinen Energieaufwand anpassen kann an die 55:09.680 --> 55:12.180 aktuell zur Verfügung stehende Energie. 55:12.920 --> 55:19.160 Das wird auch aktiv gemacht, so etwas tatsächlich anzupassen, wobei 55:19.160 --> 55:20.760 das in den Anfängen steckt. 55:20.760 --> 55:24.360 Dann spielt die Temperatur des Rechners auch eine Rolle, wie viel 55:24.360 --> 55:25.620 Energieaufwand ich habe. 55:25.840 --> 55:29.420 Deswegen werden heutzutage irgendwelche großen Web-Server oder Cloud 55:29.420 --> 55:36.460 -Computing -Server, die werden in kalte Regionen der Erde lieber 55:36.460 --> 55:41.540 platziert als in wärmere Regionen, weil die dort halt besser arbeiten 55:41.540 --> 55:41.920 können. 55:42.900 --> 55:46.680 Ich werde auf diese Themen nicht explizit eingehen, würde mich 55:46.680 --> 55:49.900 eigentlich wahnsinnig interessieren, das mal genauer anzugucken, aber 55:49.900 --> 55:52.480 es geht über das hinaus, was ich Ihnen hier in dieser Vorlesung 55:52.480 --> 55:53.280 erzählen kann. 55:53.860 --> 55:56.780 Es gibt beim Helmholtz, in der Helmholtz-Gesellschaft gibt es ein 55:56.780 --> 56:00.640 neues Forschungsprogramm, Future Information Technology, da wird das 56:00.640 --> 56:04.620 sehr grundlagenorientiert, sehr fundamental angeschaut, inwieweit wir 56:04.620 --> 56:10.340 hier sehr energiesparsame Informationsverarbeitung zukünftig machen 56:10.340 --> 56:10.660 können. 56:10.660 --> 56:15.540 Also das Thema Low-Power-Technologien, also Informationsverarbeitung 56:15.540 --> 56:20.940 mit wenig Energieaufwand, das wird in Prozessorarchitekturen, in 56:20.940 --> 56:22.540 Rechnerarchitekturen durchaus behandelt. 56:23.040 --> 56:26.460 Die einfachen Ansätze sind, dass man die Bereiche, die gerade nicht 56:26.460 --> 56:30.640 gebraucht werden, abschaltet, die nicht mit taktet, das Takten braucht 56:30.640 --> 56:35.040 natürlich auch Strom und dadurch kann man schon mal Energie einsparen. 56:35.560 --> 56:38.300 Also das ist etwas, was durchaus in der Informationsverarbeitung 56:38.300 --> 56:42.540 heutzutage gemacht wird, aber man könnte da noch wesentlich mehr tun 56:42.540 --> 56:45.760 und insofern ist es auch ein interessantes Thema, das eine Rolle 56:45.760 --> 56:50.340 spielt bei der Betrachtung, wie effizient setze ich Ressourcen für 56:50.340 --> 56:53.540 Algorithmen ein, aber ich werde das hier also nicht vertiefen. 56:54.300 --> 57:01.080 Und damit sind wir am Ende dieses Kapitels über Berechnungsmodelle und 57:01.080 --> 57:06.440 ich kann kommen zu dem nächsten Kapitel, mit dem es erst richtig 57:06.440 --> 57:12.080 losgeht, sodass wir uns mit Algorithmen beschäftigen für bestimmte 57:12.080 --> 57:12.520 Probleme. 57:13.660 --> 57:17.060 Und wie ich schon zu Anfang gesagt habe, ich fange an mit 57:17.060 --> 57:19.680 algebraischen Problemen, die habe ich schon mit meinen Beispielen 57:19.680 --> 57:21.160 vorher vorbereitet. 57:21.660 --> 57:27.800 Wir wollen also sehen, wie können wir so typische algebraische 57:27.800 --> 57:30.240 Probleme behandeln, was sind algebraische Probleme? 57:30.680 --> 57:35.060 Probleme, bei denen wir arithmetische Operationen ausführen müssen, 57:35.180 --> 57:38.660 wobei das der wesentliche Kostenfaktor ist. 57:38.740 --> 57:42.140 Die Anzahl arithmetischer Operationen, Länge der geradlinigen 57:42.140 --> 57:47.020 Programme oder Anzahl paralleler Schritte, das spielt hier die 57:47.020 --> 57:47.600 wesentliche Rolle. 57:47.840 --> 57:50.020 Und das, was wir uns zuerst anschauen, ist das, was ich vorher schon 57:50.020 --> 57:52.740 ein paar Mal gehabt habe, das kennen Sie jetzt schon, die Matrix 57:52.740 --> 57:53.480 -Modifikation. 57:53.940 --> 57:56.600 Wie kann ich Matrizen sinnvoll modifizieren? 57:58.360 --> 58:00.780 Und dazu muss ich mir erst mal anschauen, womit habe ich es eigentlich 58:00.780 --> 58:01.220 zu tun. 58:01.680 --> 58:04.440 Nochmal ein bisschen genauer, wir gehen jetzt davon aus, wir haben n 58:04.440 --> 58:11.980 -Kreuz -n-Matrizen, in der Regel über den Raum der ganzen Zahlen. 58:12.920 --> 58:15.880 Ich könnte natürlich auch L-wertige betrachten oder komplexwertige 58:15.880 --> 58:18.420 Matrizen, das spielt aber jetzt keine Rolle. 58:19.040 --> 58:22.400 Ich brauche nur irgendwelche Zahlen, die ich hier in den Matrizen drin 58:22.400 --> 58:23.760 habe, die ich modifizieren kann. 58:25.680 --> 58:29.920 Dann sage ich, das ist die Problemgröße n, obwohl ja eigentlich ist es 58:29.920 --> 58:33.420 so, wenn ich n-Kreuz-n-Matrizen habe und ich schaue mir an, wie groß 58:33.420 --> 58:38.900 ist der Platz, den ich brauche, um eine Probleminstanz, Multiplikation 58:38.900 --> 58:42.480 zweier Matrizen zu beschreiben, dann ist der Aufwand natürlich bei n 58:42.480 --> 58:44.920 -Kreuz -n-Matrizen quadratisch, also n². 58:46.340 --> 58:49.980 Ja, weil ich ja n² Platz brauche, um das allein hinzuschreiben. 58:51.100 --> 58:54.260 Deswegen muss man eigentlich sagen, n² ist aber Standard, dass man 58:54.260 --> 58:58.320 sagt, Problemgröße bei der Matrixmultiplikation ist n und ich weiß, 58:58.420 --> 59:00.400 ich muss hier n-Kreuz-n-Matrizen multiplizieren. 59:01.240 --> 59:04.160 Ich habe also Platz, natürlich n² in dem Fall. 59:04.340 --> 59:07.020 Aber so natürlich ist es gar nicht, hängt davon ab, wie tatsächlich 59:07.020 --> 59:09.060 die Matrix oder wie die gefüllt ist. 59:10.100 --> 59:14.100 Die Datenstruktur, das ist jetzt ein Punkt, den man sich auch angucken 59:14.100 --> 59:14.300 muss. 59:14.360 --> 59:17.000 Was brauche ich für eine Datenstruktur, um Matrizen darzustellen? 59:17.000 --> 59:27.820 Ich habe eine Matrix von A11 bis A1n, hier unten Ann und hier unten 59:27.820 --> 59:31.140 An1 und das ist alles schön ausgefüllt. 59:31.720 --> 59:37.880 Das ist meine Matrix, IJ aus, hier sehen Sie n in eckigen Klammern. 59:38.240 --> 59:41.960 Dieses n in eckigen Klammern, das bedeutet immer das, was hier steht. 59:41.960 --> 59:45.980 Das ist eine Definition jetzt, die ich im Weiteren nicht wiederhole, 59:46.120 --> 59:47.200 sondern immer so einsetze. 59:47.320 --> 59:52.300 Zur Abkürzung schreibe ich das n in eckigen Klammern, wenn ich die 59:52.300 --> 59:54.440 Menge der Zahlen 1 bis n meine. 59:55.300 --> 01:00:00.800 So, das ist Standardmutation, die mal irgendwo eingeführt wurde, die 01:00:00.800 --> 01:00:01.840 ich übernommen habe. 01:00:02.800 --> 01:00:06.360 Jetzt kann ich diese Matrix darstellen als zweidimensionales Feld. 01:00:07.100 --> 01:00:08.760 Die naive Art, das zu machen. 01:00:09.200 --> 01:00:14.300 Ich habe also irgendein zweidimensionales Feld und kann also das 01:00:14.300 --> 01:00:23.300 Element Aij zum Beispiel so darstellen, dass ich hier Aij-1, J-1 das 01:00:23.300 --> 01:00:25.600 Element als Aij bezeichne. 01:00:25.740 --> 01:00:27.020 Warum mache ich das so? 01:00:27.260 --> 01:00:31.260 Wenn wir uns das in Java anschauen, da wird immer von 0 an indiziert. 01:00:31.260 --> 01:00:37.620 Von 0 bis n-1 habe ich dort die Indizes laufen und eben nicht von 1 01:00:37.620 --> 01:00:43.860 bis n, wie bei der Darstellung jetzt hier bei der Probleminstanz 01:00:43.860 --> 01:00:48.440 intern, nummeriert von 0 bis n-1, wenn ich eigentlich bei den 01:00:48.440 --> 01:00:51.580 Elementen von 1 bis n das aufschreibe. 01:00:52.340 --> 01:00:55.620 Dann hätte ich also einen Speicherplatzbedarf von natürlich n², das 01:00:55.620 --> 01:00:56.060 ist klar. 01:00:56.060 --> 01:00:59.720 Wenn ich zugreifen will auf die einzelne Komponente, was muss ich 01:00:59.720 --> 01:01:00.060 machen? 01:01:01.240 --> 01:01:05.880 Da hatte ich schon mal kurz darauf hingewiesen, der Zugriff auf eine 01:01:05.880 --> 01:01:10.680 Matrix, hier ist meine Matrix, da ist meine zweidimensionale Matrix, 01:01:10.780 --> 01:01:12.360 das möchte ich hier natürlich darstellen. 01:01:13.060 --> 01:01:16.600 Irgendwie muss die im Rechner abgelegt werden, entweder spaltenbasiert 01:01:16.600 --> 01:01:25.500 oder zeilenbasiert, sodass ich hier die erste Zeile habe, dann hier 01:01:25.500 --> 01:01:27.200 die zweite Zeile usw. 01:01:27.780 --> 01:01:32.180 und hier unten irgendwann die Endezeile. 01:01:33.240 --> 01:01:35.240 So, das sind meine einzelnen Elemente hier drin. 01:01:36.240 --> 01:01:43.780 Und wenn ich jetzt auf irgendein Element zugreifen möchte, dann liegen 01:01:43.780 --> 01:01:50.540 vor einem solchen Element, hier an irgendeiner Position, liegen i-1 01:01:50.540 --> 01:02:01.020 andere Zeilen und von dieser Zeile liegen j, jetzt schreibe ich hier 01:02:01.020 --> 01:02:11.360 plus j, also i-1 mal n gibt genau die letzte Position hier, plus j ist 01:02:11.360 --> 01:02:17.880 genau das letzte Element hier und dann muss ich hier entsprechend bis 01:02:17.880 --> 01:02:26.980 zur Position j laufen, dann habe ich das Element i-1 mal n plus j und 01:02:26.980 --> 01:02:32.700 das s ist im Prinzip mein Startregister, da geht das Ganze los, die 01:02:32.700 --> 01:02:34.300 Startadresse für diese Datenstruktur. 01:02:35.620 --> 01:02:40.980 s plus 1 ist das Element a11 und s plus n² ist dann das Element hier 01:02:40.980 --> 01:02:44.960 ganz unten und entsprechend kann ich auf diese Art und Weise 01:02:44.960 --> 01:02:45.520 zugreifen. 01:02:46.280 --> 01:02:52.960 Das heißt, um zuzugreifen auf das Element aij, muss ich eine 01:02:52.960 --> 01:02:57.940 Multiplikation ausführen, i-1 mal n rechnen und ich muss zwei 01:02:57.940 --> 01:03:02.540 Additionen ausführen, einmal muss ich auf dieses Indexregister s etwas 01:03:02.540 --> 01:03:05.940 drauf addieren und das was ich drauf addiere, da muss ich hier intern 01:03:05.940 --> 01:03:09.520 auch nochmal das i-1 mal n plus j rechnen. 01:03:09.520 --> 01:03:11.600 Zwei Additionen, eine Multiplikation. 01:03:12.000 --> 01:03:15.860 Wir sagten, wir müssen gucken, wie viele Operationen werden im Rechner 01:03:15.860 --> 01:03:20.480 tatsächlich ausgeführt und das heißt, ich muss auch die arithmetischen 01:03:20.480 --> 01:03:24.940 Operationen zählen, die ich brauche, um auf eine Matrixkomponente 01:03:24.940 --> 01:03:25.840 zuzugreifen. 01:03:26.180 --> 01:03:27.400 So, das müssen wir im Kopf haben. 01:03:27.980 --> 01:03:31.680 Wenn ich jetzt in einer einzelnen Komponente nicht nur eine ganze Zahl 01:03:31.680 --> 01:03:36.100 habe, sondern vielleicht mehrere Register brauche, meinetwegen für 01:03:36.100 --> 01:03:39.500 komplexe Zahlen oder ähnliches, stellen Sie sich vor, Sie haben eine 01:03:39.500 --> 01:03:43.880 doppelt lange Darstellung Ihrer reellen Zahlen, das Ganze noch 01:03:43.880 --> 01:03:50.280 komplex, dann hätten Sie vier Wörter, die Sie brauchen, um Ihre Zahlen 01:03:50.280 --> 01:03:51.600 darzustellen. 01:03:52.120 --> 01:03:55.900 Dann hätten Sie entsprechend, und das noch als weiteren Faktor, das g, 01:03:56.060 --> 01:04:00.880 die Anzahl der Speicherzellen, die Sie für die Darstellung eines 01:04:00.880 --> 01:04:02.260 Elementes tatsächlich brauchen. 01:04:04.220 --> 01:04:07.440 Gut, zeigt also, man muss sich das genauer angucken. 01:04:08.400 --> 01:04:10.020 Welche anderen Möglichkeiten hätte ich? 01:04:10.040 --> 01:04:13.400 Ich könnte das Ganze ja vermeiden, indem ich von vornherein sage, ich 01:04:13.400 --> 01:04:16.600 stelle meine Matrix einfach als eindimensionales Array dar. 01:04:17.440 --> 01:04:23.160 Ich schreibe also, nehme hier ein einfaches Feld, der Länge n², und an 01:04:23.160 --> 01:04:29.400 der Position i-1 mal n plus j-1 schreibe ich das Element aij rein. 01:04:31.740 --> 01:04:35.320 Dann habe ich natürlich auch die Operation zu machen, aber jetzt 01:04:35.320 --> 01:04:39.060 explizit als Indexoperation für mein Feld. 01:04:41.740 --> 01:04:45.560 Und wenn ich jetzt also auf ein Element zugreifen möchte, also dieses 01:04:45.560 --> 01:04:50.380 Element a, wenn ich irgendeinen Index k habe, will ich sehen, welches 01:04:50.380 --> 01:04:54.600 Element ij steckt denn da drin, das ist dann gerade das k plus 1 durch 01:04:54.600 --> 01:04:56.960 n, nächstgrößere Zahl, bzw. 01:04:57.400 --> 01:04:59.700 das j ist k mod n plus 1. 01:05:00.660 --> 01:05:06.420 Dann habe ich genau das i und j wieder zu dem tatsächlichen Ort in 01:05:06.420 --> 01:05:10.640 meinem eindimensionalen Feld zugeordnet. 01:05:11.500 --> 01:05:16.840 Ich kann aber, wenn ich das so gemacht habe, Operationen in einem 01:05:16.840 --> 01:05:21.180 Algorithmus, in dem ich auf Elemente der Matrix zugreifen muss, so 01:05:21.180 --> 01:05:25.240 gestalten, dass ich diese Multiplikationen und Additionen vielleicht 01:05:25.240 --> 01:05:26.260 so gar nicht machen muss. 01:05:26.740 --> 01:05:28.880 Ich könnte ja sequenziell da durchlaufen. 01:05:30.240 --> 01:05:31.600 Dann brauche ich nur mal eins zu addieren. 01:05:31.760 --> 01:05:34.140 Ich brauche für keinen Zugriff dann unbedingt eine Multiplikation zu 01:05:34.140 --> 01:05:34.560 machen. 01:05:35.360 --> 01:05:40.780 Und insofern kann ich dadurch, dass ich geschickter mit meinen 01:05:40.780 --> 01:05:45.600 Positionen in der Matrix arbeite, kann ich arithmetische Operationen 01:05:45.600 --> 01:05:46.020 sparen. 01:05:46.900 --> 01:05:50.940 Das wäre also ein datenstrukturorientiertes Verbessern der Laufzeit 01:05:50.940 --> 01:05:51.880 eines Algorithmus. 01:05:54.100 --> 01:06:00.820 Auch da ist natürlich Speicherplatzbedarf quadratisch und die 01:06:00.820 --> 01:06:03.220 Komponente a von k steckt in Register s plus k. 01:06:03.220 --> 01:06:04.580 Also eine Operation muss ich machen. 01:06:04.720 --> 01:06:11.340 Wenn ich Indexadressierung mache, einmal die Operation Indexregister 01:06:11.340 --> 01:06:14.420 plus Position innerhalb der Datenstruktur. 01:06:15.400 --> 01:06:17.060 Ich kann das Ganze noch anders machen. 01:06:17.300 --> 01:06:20.720 Ich kann das Ganze darstellen als Folge von Zeilen. 01:06:20.840 --> 01:06:26.620 Wenn Sie eine Matrix haben, bei der Sie nur wenige, die habe ich hier 01:06:26.620 --> 01:06:29.720 auch dargestellt, solche Elemente wären das. 01:06:29.720 --> 01:06:35.540 Wenn Sie eine Bandmatrix haben oder Sie haben eine dünn besetzte 01:06:35.540 --> 01:06:41.920 Matrix mit nur einer linearen Anzahl von Elementen ungleich null, dann 01:06:41.920 --> 01:06:46.380 würden Sie genau diese Elemente ungleich null speichern in einer 01:06:46.380 --> 01:06:47.760 systematischen Art und Weise. 01:06:48.820 --> 01:06:52.900 Und Sie würden zum Beispiel nur in jeder Zeile die Nicht-Null-Elemente 01:06:52.900 --> 01:06:53.360 speichern. 01:06:54.200 --> 01:06:58.160 Das wäre bei einer Bandmatrix sogar sehr einfach, sehr systematisch 01:06:58.160 --> 01:07:01.060 möglich, jeweils die Zeilen darzustellen. 01:07:01.200 --> 01:07:05.180 Bei einer dünn besetzten Matrix ist die Position der einzelnen 01:07:05.180 --> 01:07:07.560 Elemente vielleicht etwas schwierig zu bestimmen. 01:07:07.720 --> 01:07:10.860 Da müssen Sie jeweils noch den Index merken, an welcher Position 01:07:10.860 --> 01:07:12.900 tatsächlich dieses Nicht-Null-Element steht. 01:07:14.200 --> 01:07:18.580 Aber hier hätten Sie eben einen Speicherplatz, der nur bedingt wird 01:07:18.580 --> 01:07:21.340 durch die Anzahl der Komponenten ungleich null. 01:07:21.340 --> 01:07:27.520 Und bei dünn besetzten Matrixen, wenn Sie maximal linear viele Nicht 01:07:27.520 --> 01:07:30.960 -Null -Elemente haben, dann sparen Sie eben deutlich Speicherplatz. 01:07:32.060 --> 01:07:36.060 Was es wieder schwieriger macht, wenn Sie vor Sie wollen zwei dünn 01:07:36.060 --> 01:07:41.080 besetzte Matrixen multiplizieren, dann müssen Sie auf einmal sehen, 01:07:41.200 --> 01:07:44.860 welche Elemente eigentlich jetzt miteinander multipliziert werden 01:07:44.860 --> 01:07:45.160 müssen. 01:07:45.160 --> 01:07:49.020 Da müssen Sie also auf der Datenstruktur einige Operationen machen, um 01:07:49.020 --> 01:07:53.960 tatsächlich jetzt die relevanten Operationen für die Matrix 01:07:53.960 --> 01:07:55.180 -Multiplikation hinzubekommen. 01:07:55.740 --> 01:07:59.260 Das kann man auch versuchen bestmöglich auszuführen. 01:08:00.220 --> 01:08:02.920 Das wird eventuell in den Übungen gemacht. 01:08:03.120 --> 01:08:06.780 Da kann man sich überlegen, wie man dünn besetzte Matrixen bestmöglich 01:08:06.780 --> 01:08:07.920 modifizieren kann. 01:08:07.920 --> 01:08:14.460 Unter Ausnutzung dieser Tatsache, dass ich ja dabei viele Operationen 01:08:14.460 --> 01:08:17.480 gar nicht ausführen muss, weil die Elemente gleich null sind. 01:08:17.780 --> 01:08:22.120 Wenn ich weiß, ich habe Elemente, die null sind, die Operation kann 01:08:22.120 --> 01:08:22.740 ich mir sparen. 01:08:22.860 --> 01:08:24.920 Da brauche ich nicht zu modifizieren, da kommt wieder null raus. 01:08:25.340 --> 01:08:26.660 Brauche ich auch nicht zu addieren. 01:08:27.660 --> 01:08:33.160 Also insofern kann man dabei Berechnungen deutlich verbessern. 01:08:35.420 --> 01:08:39.060 Deutlich über das hinaus, was man für vollbesetzte Matrizen machen 01:08:39.060 --> 01:08:39.400 könnte. 01:08:40.520 --> 01:08:42.140 Das waren die Datenstrukturen. 01:08:42.820 --> 01:08:47.180 Ich wollte darstellen, wie viele verschiedene Möglichkeiten ich habe, 01:08:47.680 --> 01:08:50.380 so eine Matrix tatsächlich im Rechner abzulegen. 01:08:51.060 --> 01:08:53.740 Und das beeinflusst dann die Art, wie wir tatsächlich Algorithmen 01:08:53.740 --> 01:08:54.540 entwickeln können. 01:08:55.440 --> 01:09:00.720 Ich werde jetzt annehmen, dass wir Standard Datenstruktur haben, 01:09:00.960 --> 01:09:02.800 zweidimensionales Feld meinetwegen. 01:09:03.320 --> 01:09:07.620 Und wir gucken uns nur noch an, wie wir die beiden Matrizen, so 01:09:07.620 --> 01:09:09.520 vollbesetzte Matrizen modifizieren können. 01:09:10.260 --> 01:09:12.180 Wir wissen schon im Prinzip, wie das geht. 01:09:12.860 --> 01:09:14.580 Schulmethode hatte ich Ihnen schon vorgestellt. 01:09:14.580 --> 01:09:19.720 Dreifach geschachtelte Schleife, selbstverständlich so, dass wir hier 01:09:19.720 --> 01:09:25.560 eine Hilfsvariable verwenden, um zu vermeiden, dass wir unnötige 01:09:25.560 --> 01:09:28.940 Zugriffe auf Matrixkomponenten hier drin haben. 01:09:29.100 --> 01:09:32.960 Das Cij wird nur einmal dort verwendet. 01:09:34.240 --> 01:09:37.600 Das ist also der Standardansatz, die Schulmethode, naive Art und 01:09:37.600 --> 01:09:38.740 Weise, wie ich Matrizen modifiziere. 01:09:39.900 --> 01:09:42.800 Und die Analyse hatten wir auch schon gemacht. 01:09:42.980 --> 01:09:44.740 N hoch 3 Multiplikationen. 01:09:45.480 --> 01:09:49.720 Im Prinzip hier diese in der Schleife nach I und J. 01:09:49.980 --> 01:09:54.500 Und hier noch die Multiplikation innerhalb der innersten Schleife. 01:09:55.340 --> 01:09:57.740 Und dann die N hoch 3 minus N² Additionen. 01:09:58.520 --> 01:10:02.160 Insgesamt zwei N hoch 3 minus N² Arithmetische Operationen. 01:10:03.960 --> 01:10:06.780 Gibt O von N hoch 3 Operationen N² Platzbedarf. 01:10:06.780 --> 01:10:10.240 Die Frage ist, wie sieht das mit dem Zugriff auf die Matrixkomponenten 01:10:10.240 --> 01:10:10.560 aus. 01:10:10.800 --> 01:10:14.880 Und es ist dann eben, wenn wir das anschauen, für die verschiedenen 01:10:14.880 --> 01:10:17.820 Möglichkeiten, Matrix als zweidimensionales Feld. 01:10:18.220 --> 01:10:21.340 Da hatten wir gesehen, wir haben zwei Additionen, eine Multiplikation 01:10:21.340 --> 01:10:22.100 pro Zugriff. 01:10:23.740 --> 01:10:27.320 Insgesamt kommen in diesem Algorithmus, den wir auf der vorigen Folie 01:10:27.320 --> 01:10:30.880 gerade hatten, folgende Anzahl von Zugriffen vor. 01:10:30.880 --> 01:10:38.860 3N² plus 2N² mal N-1 Zugriffe auf Matrixkomponenten. 01:10:39.200 --> 01:10:46.420 Das sind insgesamt 2N hoch 3 plus N² Zugriffe auf Matrixkomponenten. 01:10:47.540 --> 01:10:54.740 Das heißt, wir haben allein 4N hoch 3 plus 2N² Additionen und 2N hoch 01:10:54.740 --> 01:10:58.640 3 plus N² Multiplikationen nur für die Zugriffe. 01:11:00.420 --> 01:11:04.300 Insgesamt also dreimal so viele arithmetische Operationen für 01:11:04.300 --> 01:11:08.280 Adressberechnungen als für die eigentliche Matrixmultiplikation, die 01:11:08.280 --> 01:11:10.780 wir uns auf der vorigen Folie überlegt hatten. 01:11:10.880 --> 01:11:14.240 Das waren diese 2N hoch 3 minus N². 01:11:15.180 --> 01:11:17.700 Das ist ja eigentlich das, was wir uns anschauen im Algorithmus. 01:11:18.200 --> 01:11:20.940 Im Hintergrund werden aber noch so und so viele weitere Operationen 01:11:20.940 --> 01:11:21.900 ausgeführt im Rechner. 01:11:22.760 --> 01:11:24.680 Und das sind also dreimal so viele. 01:11:24.680 --> 01:11:28.160 Das heißt, wenn ich das anders mache, wenn ich auf diese Operation 01:11:28.160 --> 01:11:31.980 verzichten könnte, hätte ich schon ein Zeitgewinn um den Faktor, wenn 01:11:31.980 --> 01:11:34.460 ich Glück habe, 3, vielleicht 2 oder sowas. 01:11:35.100 --> 01:11:41.620 Also wenn ich eine eindimensionale Matrix als Datenstruktur habe, dann 01:11:41.620 --> 01:11:45.460 kann ich den Algorithmus so aufbauen, genau den gleichen dreifach 01:11:45.460 --> 01:11:50.140 geschachtelten naiven Algorithmus, sodass ich keine einzige 01:11:50.140 --> 01:11:51.680 Multiplikation brauche. 01:11:51.680 --> 01:11:54.440 Sondern ich gehe praktisch immer nur einen Schritt weiter. 01:11:54.960 --> 01:11:58.880 Also wenn ich von Zeile zu Zeile gehe, kann ich das einfach ein 01:11:58.880 --> 01:12:02.320 bisschen anders anordnen und kann auf die Multiplikationen in 01:12:02.320 --> 01:12:05.180 Adressberechnungen damit verzichten. 01:12:06.500 --> 01:12:09.060 Ist eine Sache, die Sie sich in den Übungen gerne anschauen können, 01:12:09.140 --> 01:12:10.540 wie man das dann formulieren würde. 01:12:11.520 --> 01:12:15.640 Auf jeden Fall ist also hier der Punkt, den ich da vermitteln möchte. 01:12:16.780 --> 01:12:20.780 Sie kamen abhängig von der Datenstruktur, zweidimensionales Feld oder 01:12:20.780 --> 01:12:23.960 eindimensionales Feld, hier einen deutlichen Unterschied in der Anzahl 01:12:23.960 --> 01:12:28.800 der Operationen und insofern Vorteil bei eindimensionalem Feld. 01:12:28.980 --> 01:12:32.560 Allerdings natürlich eine nicht so naheliegende Datenstruktur. 01:12:33.680 --> 01:12:37.640 Wenn Sie eine dünnbesetzte Matrix mitnehmen, ist das wiederum sehr 01:12:37.640 --> 01:12:39.980 abhängig davon, wie Sie das dann organisieren. 01:12:40.520 --> 01:12:41.980 Das können Sie sich in den Übungen angucken. 01:12:41.980 --> 01:12:44.880 Da kann man auch Aufwand reduzieren. 01:12:45.560 --> 01:12:48.180 Stellen Sie sich vor, Sie hätten eine dünnbesetzte Matrix und Sie 01:12:48.180 --> 01:12:53.060 haben hier die Folge der Zeilen, in denen jetzt jeweils die Nicht-Null 01:12:53.060 --> 01:12:56.960 -Elemente drinstehen und zwar an den jeweiligen Positionen. 01:12:57.040 --> 01:12:59.500 Da müssten Sie ja eventuell linear hier durchlaufen durch so eine 01:12:59.500 --> 01:13:01.080 Liste, um auf das Element zu kommen. 01:13:01.500 --> 01:13:03.720 Das heißt, die Datenstruktur spielt da schon eine ganz große Rolle, 01:13:04.340 --> 01:13:07.520 wie Sie mit dünnbesetzten Matrizen umgehen können. 01:13:08.520 --> 01:13:12.060 Das steht ja nicht so sehr im Vordergrund. 01:13:12.840 --> 01:13:17.300 Und jetzt haben wir also analysiert klassische Standard-Matrix 01:13:17.300 --> 01:13:18.040 -Multiplikation. 01:13:18.560 --> 01:13:21.860 Jetzt will ich Ihnen vorstellen, eine andere Art, Matrizen zu 01:13:21.860 --> 01:13:28.740 multiplizieren, die sich dadurch unterscheidet, dass man einfach diese 01:13:28.740 --> 01:13:39.040 Aufgabe verändert und die Annahme, die Winograd vor 45 Jahren gemacht 01:13:39.040 --> 01:13:43.540 hat, war, dass die Multiplikation länger dauert als eine Addition. 01:13:43.740 --> 01:13:48.360 Das war keine so unwahrscheinliche oder unsinnige Annahme. 01:13:49.080 --> 01:13:52.900 Zu damaliger Zeit war es so, dass tatsächlich im Rechner die 01:13:52.900 --> 01:13:55.740 Multiplikationen deutlich länger dauerten als die Additionen. 01:13:56.740 --> 01:14:00.720 Sie können das heute noch mal messen, wie lange auf Ihrem Rechner die 01:14:00.720 --> 01:14:03.100 verschiedenen arithmetischen Operationen dauern. 01:14:03.700 --> 01:14:05.660 Die sind durchaus unterschiedlich. 01:14:06.780 --> 01:14:11.320 Bei ganzen Zahlen dauert normalerweise die Multiplikation etwas länger 01:14:11.320 --> 01:14:12.140 als die Addition. 01:14:12.720 --> 01:14:15.920 Bei reellen Zahlen dauert meistens die Addition länger als die 01:14:15.920 --> 01:14:19.300 Multiplikation, weil das Gleitpunkt-Operationen sind. 01:14:19.300 --> 01:14:21.760 Sie haben bei Gleitpunkt-Operationen eine Reihe weiterer Sachen zu 01:14:21.760 --> 01:14:25.740 machen, wie Angleichen von Exponenten und Mantissen. 01:14:27.200 --> 01:14:30.200 Also Anpassung der Mantissen und dann Normalisierung und ähnliche 01:14:30.200 --> 01:14:30.480 Dinge. 01:14:30.940 --> 01:14:34.340 Deswegen ist die Addition dort im Prinzip eine komplexere Aufgabe als 01:14:34.340 --> 01:14:35.480 eine Multiplikation. 01:14:36.460 --> 01:14:39.440 Bei komplexen Zahlen haben Sie einen deutlichen Unterschied. 01:14:39.760 --> 01:14:43.620 Da ist die Multiplikation deutlich länger als die Addition, weil Sie 01:14:43.620 --> 01:14:50.860 dort den reellen und imaginären Teil jeweils noch mit einbeziehen 01:14:50.860 --> 01:14:51.100 müssen. 01:14:51.240 --> 01:14:54.340 Da ist eine Multiplikation eine deutlich aufwendigere Operation als 01:14:54.340 --> 01:14:54.880 eine Addition. 01:14:55.540 --> 01:14:59.040 Also das hängt davon ab, auf welchen Zahlenbereichen ich agiere. 01:14:59.660 --> 01:15:03.180 Nehmen wir mal an, die Multiplikation dauert länger als die Addition. 01:15:03.820 --> 01:15:07.640 Und das Ziel wäre dann, die Anzahl der Multiplikationen zu verringern. 01:15:09.040 --> 01:15:10.360 Wie kann ich das hinbekommen? 01:15:10.360 --> 01:15:23.200 Also, was ich berechnen möchte, ist meine Summe a i k b k j k gleich 1 01:15:23.200 --> 01:15:24.320 bis n. 01:15:24.600 --> 01:15:26.260 Das möchte ich gerne berechnen. 01:15:27.200 --> 01:15:33.480 Jetzt ist die Beobachtung von Vinograd, dass zum Beispiel hier a i 3 b 01:15:33.480 --> 01:15:40.660 3 j plus a i 4 b 4 j auch ausgedrückt werden können durch das Produkt 01:15:40.660 --> 01:15:49.880 von a i 3 plus b 4 j mal a i 4 plus b 3 j minus diesem Term. 01:15:51.420 --> 01:15:54.660 Jetzt werden Sie sich fragen, was soll denn diese Darstellung? 01:15:54.880 --> 01:15:57.900 Jetzt müssen Sie ein bisschen Geduld haben, bevor Sie tatsächlich den 01:15:57.900 --> 01:15:59.140 Vorteil sehen werden. 01:15:59.140 --> 01:16:05.140 Auf jeden Fall sieht man, dass ich hier also diese Summe von zwei 01:16:05.140 --> 01:16:09.440 Multiplikationen solcher Elemente, die in diesem Skalarprodukt 01:16:09.440 --> 01:16:13.500 auftauchen, kann ich durch einen anderen Ausdruck darstellen. 01:16:17.660 --> 01:16:26.280 Das heißt also, ich könnte für gerades n die Summe, also dieses c i j, 01:16:26.460 --> 01:16:31.580 das ist meine Summe hier oben, auch darstellen als Summe solcher 01:16:31.580 --> 01:16:34.500 Ausdrücke, die dort eingerahmt sind. 01:16:35.460 --> 01:16:41.560 Für k gleich 1 bis n halbe könnte ich also, dass es hier a i 2 k minus 01:16:41.560 --> 01:16:48.300 1, ein ungerader Wert, plus b 2 k j, das ist der genau 1 größere Wert 01:16:48.300 --> 01:16:55.300 dort, mal diesem a i 2 k, da habe ich das 2 k, und dann hier 2 k minus 01:16:55.300 --> 01:17:01.220 1 j, das ist also 4 und 3, da hatte ich 3 und 4, minus Produkt dieser 01:17:01.220 --> 01:17:06.840 a, dieses a i 2 k minus 1 von a i 2 k und so weiter, das ist praktisch 01:17:06.840 --> 01:17:11.380 nur dieser eingerahmte Ausdruck allgemeiner hingeschrieben für ein 01:17:11.380 --> 01:17:13.500 beliebiges k zwischen 1 und n halbe. 01:17:14.060 --> 01:17:19.460 Jetzt habe ich nur noch n halbe Elemente, also n halbe Ausdrücke, die 01:17:19.460 --> 01:17:22.400 addiert werden, allerdings sieht das da drin ziemlich kompliziert aus. 01:17:22.400 --> 01:17:25.440 Wenn ich das auswerten würde, was würde dabei rauskommen? 01:17:26.060 --> 01:17:34.940 Für jedes i und j hätte ich jetzt, was zu berechnen, ich hätte 1, 2, 3 01:17:34.940 --> 01:17:46.340 Operationen, das ganze n halbe mal, ich hätte 1, 2, 3, 4 Additionen, 01:17:46.560 --> 01:17:52.700 also 4 Additionen, das n halbe mal, aber ich habe ja auch noch die 01:17:52.700 --> 01:17:56.760 Summe von k gleich 1 bis n halbe, also noch n halbe minus 1 obendrauf, 01:17:57.280 --> 01:18:00.260 dann haben wir diese 5 mal n halbe minus 1 Additionen. 01:18:00.260 --> 01:18:04.040 Wenn man das insgesamt anschaut, haben wir 1,5 n hoch 3 01:18:04.040 --> 01:18:08.460 Multiplikationen, 2,5 n hoch 3 minus n Quadrat Additionen. 01:18:09.020 --> 01:18:12.400 Deutlich mehr sowohl bei Multiplikationen als auch bei Additionen. 01:18:12.720 --> 01:18:17.460 Und dann fragt man sich, was das Ganze soll, dass man diese Berechnung 01:18:17.460 --> 01:18:18.740 so anders darstellt. 01:18:19.540 --> 01:18:22.360 Also man fragt sich, ob das Ganze unsinnig ist. 01:18:23.240 --> 01:18:26.420 Natürlich ist es nicht unsinnig, denn jetzt fängt man an, darüber 01:18:26.420 --> 01:18:28.160 nachzudenken, was da eigentlich steht. 01:18:29.240 --> 01:18:33.520 Und hier steht, also wenn wir nochmal auf die vorige Folie schauen, 01:18:34.640 --> 01:18:40.360 hier steht etwas drin, das ist ein Produkt von zwei Werten, a i 3 plus 01:18:40.360 --> 01:18:42.980 b 4j mal a i 4 plus b 3j. 01:18:43.580 --> 01:18:48.060 Und hier wird etwas abgezogen, und hier steht ein Term, da steht eine 01:18:48.060 --> 01:18:53.560 Multiplikation von zwei Elementen der Matrix A. 01:18:54.820 --> 01:18:56.980 Da steht also nur eine Abhängigkeit von i. 01:18:57.820 --> 01:19:01.460 Und hier steht ein Produkt von zwei Elementen der Matrix B. 01:19:02.340 --> 01:19:04.280 Da ist nur eine Abhängigkeit von j drin. 01:19:05.920 --> 01:19:11.580 Das heißt, ich habe hier eine, das ist diese Summe, die wir gerade auf 01:19:11.580 --> 01:19:12.980 der vorigen Folie gesehen haben. 01:19:13.600 --> 01:19:18.320 Da ist ein Ausdruck, also eine Summe, ein Summenteil, das war dieses 01:19:18.320 --> 01:19:19.860 Produkt von den beiden Klammern. 01:19:20.140 --> 01:19:22.240 Da traten in jeder Klamme i und j auf. 01:19:24.080 --> 01:19:30.260 Und dann habe ich hier eine Summe, da steht nur das i drin, und eine 01:19:30.260 --> 01:19:34.420 Summe, und natürlich k gleich 1 bis in halbe, und hier steht drin nur 01:19:34.420 --> 01:19:36.740 das j, auch k gleich 1 bis in halbe. 01:19:37.920 --> 01:19:41.240 Und das heißt, ich kann meine Berechnung ganz anders organisieren. 01:19:42.240 --> 01:19:47.180 Ich berechne zunächst mal alle diese Produkte, die nur von i abhängen. 01:19:47.920 --> 01:19:50.720 Dann habe ich ein di, für jedes i ein di. 01:19:51.960 --> 01:19:57.280 Das sind genau diese Produkte, diese Elemente ai2k-1 mal ai2k. 01:19:58.180 --> 01:20:02.520 Ich berechne alle anderen Ausdrücke. 01:20:03.260 --> 01:20:06.840 Dann habe ich ein ej, für jedes j einen solchen Ausdruck. 01:20:07.600 --> 01:20:11.240 Und jetzt muss ich noch diesen Teil hier berechnen. 01:20:11.320 --> 01:20:12.840 Das muss ich natürlich für jedes ij machen. 01:20:12.840 --> 01:20:19.900 cij ist dann diese Summe minus di minus ej. 01:20:20.240 --> 01:20:22.720 Das sind genau diese beiden Teile da oben. 01:20:23.880 --> 01:20:24.600 Die ziehe ich ab. 01:20:24.740 --> 01:20:26.740 Die di und ej habe ich vorher berechnet. 01:20:27.360 --> 01:20:28.780 Welchen Aufwand habe ich dafür? 01:20:29.900 --> 01:20:34.480 Ich habe für den ersten Schritt eine Berechnung k gleich 1 bis in 01:20:34.480 --> 01:20:35.540 halbe dieser Produkte. 01:20:35.540 --> 01:20:40.560 Ich habe jeweils eine Multiplikation, also n halbe Multiplikationen 01:20:40.560 --> 01:20:43.120 plus n halbe minus 1 Additionen. 01:20:43.620 --> 01:20:45.800 Und das Ganze für jedes i, also n mal. 01:20:47.820 --> 01:20:52.360 Analog für j, auch n mal n halbe Multiplikationen plus n halbe minus 1 01:20:52.360 --> 01:20:53.100 Additionen. 01:20:53.560 --> 01:20:59.900 Und im dritten Schritt muss ich n² mal für jedes i und j, muss ich wie 01:20:59.900 --> 01:21:01.080 viele Multiplikationen machen? 01:21:01.080 --> 01:21:04.880 Dann eine Multiplikation, das ist dieser erste Teil. 01:21:05.640 --> 01:21:10.260 Das Ganze n halbe mal, also n halbe Multiplikationen. 01:21:10.580 --> 01:21:15.080 Aber ich habe dann auch noch dazu dieses minus di und minus... 01:21:15.640 --> 01:21:17.140 Nein, Entschuldigung. 01:21:17.240 --> 01:21:19.400 Diese zwei Additionen hier beziehen sich darauf, dass ich in jeder 01:21:19.400 --> 01:21:20.820 Klammer eine Addition mache. 01:21:21.720 --> 01:21:24.580 Das sind also meine n halbe mal, das bezieht sich darauf. 01:21:25.200 --> 01:21:27.360 Eine Multiplikation und zwei Additionen. 01:21:27.420 --> 01:21:30.000 Zwei Additionen, das sind in den beiden Klammern hier. 01:21:30.000 --> 01:21:33.260 Und dann eine Multiplikation der beiden Summen. 01:21:33.680 --> 01:21:42.700 Und dann muss ich noch das di abziehen und das ej abziehen. 01:21:42.840 --> 01:21:46.080 Das sind nochmal zwei weitere Additionen. 01:21:46.280 --> 01:21:51.760 Also insgesamt komme ich hier auf diese Anzahl der Operationen. 01:21:52.420 --> 01:21:56.600 Und wenn ich das alles aufaddiere, dann habe ich insgesamt n hoch 3 01:21:56.600 --> 01:21:59.060 halbe plus n² Multiplikationen. 01:21:59.060 --> 01:22:04.380 Und ich habe 3n hoch 3 halbe plus 2n² minus 2n Additionen. 01:22:04.620 --> 01:22:07.520 Können Sie nachschauen, das kommt genau so hin. 01:22:08.420 --> 01:22:13.300 Insgesamt 2n hoch 3 plus 3n² minus 2n Automatische Operationen. 01:22:13.340 --> 01:22:16.660 Das ist mehr als vorher bei der naiven Methode. 01:22:17.020 --> 01:22:24.020 Aber ich habe n hoch 3 halbe minus n² weniger Multiplikationen. 01:22:24.640 --> 01:22:27.500 Und ich habe gehörig mehr Additionen. 01:22:27.500 --> 01:22:31.300 Wenn jetzt aber die Multiplikationen deutlich länger dauern als die 01:22:31.300 --> 01:22:35.400 Additionen, kann es ja sein, dass diese Einsparung der 01:22:35.400 --> 01:22:39.660 Multiplikationen deutlich mehr Zeitgewinn bringt, oder Zeitvorteil 01:22:39.660 --> 01:22:43.080 bringt, als der Aufwand für die Additionen. 01:22:43.560 --> 01:22:45.980 Und das ist tatsächlich der Fall. 01:22:46.700 --> 01:22:48.700 Man kann das ausrechnen. 01:22:49.400 --> 01:22:55.120 Ab etwa Faktor 10 Unterschied zwischen Aufwand für Multiplikationen im 01:22:55.120 --> 01:23:00.740 Vergleich zur Addition hat man spürbare Verbesserung, sofern man auch 01:23:00.740 --> 01:23:03.880 noch sparsam mit Adressberechnungen umgeht. 01:23:04.160 --> 01:23:05.700 Das muss man natürlich auch im Hinterkopf haben. 01:23:06.140 --> 01:23:11.680 Also man kann einen Algorithmus schreiben, der mit einem 01:23:11.680 --> 01:23:18.680 eindimensionalen Feld die Matrizen abspeichert und dann die Operation 01:23:18.680 --> 01:23:22.420 so anders anordnet, wie ich das hier dargestellt habe. 01:23:22.420 --> 01:23:28.380 Dann hat man einen Zeitgewinn gegenüber dem naiven Ansatz oder der 01:23:28.380 --> 01:23:29.200 Schulmethode. 01:23:30.060 --> 01:23:33.040 Die Zeit ist natürlich immer noch n hoch 3, das heißt ich habe nur 01:23:33.040 --> 01:23:34.460 konstanten Faktor hier bekommen. 01:23:35.040 --> 01:23:39.680 Der Stil des Algorithmus, wenn Sie sich den anschauen, der sieht nicht 01:23:39.680 --> 01:23:42.300 so aus, dass Sie sofort erkennen, das ist eine Matrixmultiplikation. 01:23:42.720 --> 01:23:44.840 Also eigentlich ist das nicht das, was wir machen wollen, wenn wir 01:23:44.840 --> 01:23:46.800 einen schönen Entwurfsstil haben wollen. 01:23:47.400 --> 01:23:50.060 Das, was ich Ihnen hier nur darstellen wollte, war folgendes. 01:23:50.060 --> 01:23:54.860 Manchmal bekomme ich einfach dadurch, dass ich eine Berechnung völlig 01:23:54.860 --> 01:24:00.220 anders formuliere, durch Ausnutzung von irgendwelchen Gesetzen der 01:24:00.220 --> 01:24:06.300 Arithmetik, bekomme ich eine völlig andere Art, wie ich meine 01:24:06.300 --> 01:24:11.880 Berechnung organisieren kann und auf einmal kann ich Operationen 01:24:11.880 --> 01:24:14.460 einsparen, einfach dadurch, dass ich, wie in diesem Fall, 01:24:15.240 --> 01:24:19.200 Abhängigkeiten zwischen diesen verschiedenen Indizes I und J in einem 01:24:19.200 --> 01:24:24.280 solchen Term ausgemerzt habe und dadurch, eigentlich durch zusätzliche 01:24:24.280 --> 01:24:31.040 Berechnungen insgesamt, aber eine bessere Darstellung bekommen habe, 01:24:31.100 --> 01:24:34.080 weil ich etwas schieben konnte von Multiplikation auf Addition. 01:24:35.120 --> 01:24:40.320 Also geschickte Berechnungsmassage, nenne ich das mal, kann deutliche 01:24:40.320 --> 01:24:41.460 Kostenreduktion bringen. 01:24:41.460 --> 01:24:44.260 Bringt nur einen konstanten Faktor, können Sie sagen, was bringt das 01:24:44.260 --> 01:24:44.560 schon? 01:24:45.000 --> 01:24:46.580 Nenne ich einen Rechner, der ein bisschen schneller ist, dann habe ich 01:24:46.580 --> 01:24:47.120 das doch auch. 01:24:47.540 --> 01:24:51.560 Aber ich wollte einfach mal darstellen, man sollte nicht immer nur 01:24:51.560 --> 01:24:55.020 schauen auf eine einfache Formulierung eines Problems, sondern 01:24:55.020 --> 01:24:58.480 manchmal muss man sich überlegen, wie könnte ich dieses Problem auch 01:24:58.480 --> 01:25:02.960 irgendwie anders formulieren und es kann sein, dass ich dadurch einen 01:25:02.960 --> 01:25:06.160 neuen Zugang bekomme für die Organisation meiner Berechnung. 01:25:06.760 --> 01:25:11.000 Und nächstes Mal schauen wir uns dann einen anderen Ansatz an, bei dem 01:25:11.000 --> 01:25:17.720 wir tatsächlich auch diese O von N hoch 3 reduzieren können mit einem 01:25:17.720 --> 01:25:19.900 klassischen Divide-and-Conquer-Ansatz. 01:25:20.240 --> 01:25:22.020 Vielen Dank für die Aufmerksamkeit, das war es für heute.