WEBVTT 00:10.430 --> 00:12.330 Ja, schönen guten Morgen. 00:12.890 --> 00:14.810 Herzlich Willkommen zu Algorithmen 2. 00:18.250 --> 00:23.310 Als erstes schließen wir heute das Kapitel über Online-Algorithmen ab. 00:26.470 --> 00:29.990 Und danach fangen wir dann noch langsam an mit parallelen Algorithmen. 00:32.450 --> 00:34.190 So, Online-Algorithmen. 00:37.400 --> 00:39.680 Da habe ich jetzt noch einen letzten Punkt. 00:45.000 --> 00:50.860 Da geht es darum, man bekommt Vorschläge von Experten, in 00:50.860 --> 00:51.840 Anführungszeichen. 00:53.880 --> 00:58.800 Und soll sich dann dafür entscheiden, dem einen oder dem anderen 00:58.800 --> 00:59.880 Vorschlag zu folgen. 01:02.220 --> 01:05.140 Das Problem ist, Experten liegen nicht immer richtig. 01:07.820 --> 01:13.740 Und jetzt erstmal im einfachen Fall stellen wir uns vor, es geht 01:13.740 --> 01:18.040 darum, einfach eine Entscheidung Ja oder Nein zu fällen. 01:19.960 --> 01:24.100 Also meinetwegen Aktien kaufen oder nicht. 01:27.180 --> 01:31.880 Da gibt es also die Anzahl K-Experten. 01:32.180 --> 01:33.540 Da sagt jeder was. 01:34.340 --> 01:36.820 Und dann müssen sie sich selber für Ja oder Nein entscheiden. 01:37.520 --> 01:38.240 Und das ist es dann. 01:39.900 --> 01:43.500 Und dann merkt man noch, war diese Entscheidung jetzt richtig oder 01:43.500 --> 01:43.800 nicht. 01:43.940 --> 01:46.300 Die eigene und die Entscheidung der Experten. 01:47.820 --> 01:49.740 Ja, und das passiert immer wieder. 01:51.780 --> 01:53.900 In jeder Runde immer wieder das gleiche. 01:54.000 --> 01:55.800 K-Empfehlungen, eine eigene Entscheidung. 01:57.700 --> 02:00.580 Und es stellt sich dann heraus, die Entscheidung war richtig oder 02:00.580 --> 02:01.080 falsch. 02:02.220 --> 02:06.040 Und damit das nach wie vor so in diesem Rahmen, wir wollen irgendetwas 02:06.040 --> 02:10.780 minimieren, passt, stellen wir uns vor, eine richtige Entscheidung 02:10.780 --> 02:14.960 kostet nichts, aber eine falsche Entscheidung ist irgendwie eine 02:14.960 --> 02:15.860 Einheit kosten. 02:17.030 --> 02:18.620 Und man möchte die Kosten minimieren. 02:24.560 --> 02:28.180 Problem, man weiß nicht, was in der Zukunft die richtigen 02:28.180 --> 02:29.280 Entscheidungen sein werden. 02:29.620 --> 02:34.660 Und man weiß auch nicht, ob die Experten in irgendeinem Sinne oft oder 02:34.660 --> 02:36.160 irgendetwas gut liegen werden. 02:37.820 --> 02:41.200 Keinerlei, auch keine probabilistischen Aussagen, wahrscheinlich 02:41.200 --> 02:42.100 irgendetwas. 02:43.060 --> 02:47.960 Und das Ziel ist aber dann trotzdem, die eigenen Kosten zu minimieren 02:47.960 --> 02:56.280 und sagen wir mal, also jedenfalls mehr oder weniger, nahe am besten, 02:56.800 --> 03:00.180 so im Nachhinein gesehen, bis auf einen konstanten Faktor, nicht viel 03:00.180 --> 03:03.400 mehr Fehlentscheidungen gemacht zu haben als der beste Experte. 03:03.880 --> 03:07.660 Wer der im Nachhinein, wenn man zurückschaut, sagt, ah, das war einer 03:07.660 --> 03:10.680 von den besten, der hat die wenigsten Fehlentscheidungen, die 03:10.680 --> 03:12.540 wenigsten falschen Empfehlungen gegeben. 03:13.220 --> 03:14.220 Das ist der Plan. 03:22.930 --> 03:31.430 Wenn Sie jetzt in dieser Situation wären und Sie müssten jetzt 03:31.430 --> 03:38.990 irgendetwas plausibel Erscheinendes tun, wozu würden Sie neigen? 03:45.250 --> 03:50.130 Man führt für ein Buch, welcher Experte lag wie oft richtig, wie 03:50.130 --> 03:55.930 selten falsch und dann bei der nächsten Entscheidung, man folgt der 03:55.930 --> 03:59.930 Entscheidung einem von den bisher besten Experten. 04:01.430 --> 04:04.250 Ja, das ist das naheliegende, das kommt mir auch gleich in den Sinn 04:04.250 --> 04:06.210 als erstes, aber leider ist es gar nicht gut. 04:10.890 --> 04:13.390 Das sehen Sie ja morgen in der großen Übung. 04:13.890 --> 04:20.710 Also da können Sie immer K-Experten konstruieren, sodass Sie mit 04:20.710 --> 04:25.010 dieser Strategie, man entscheidet sich immer für die Empfehlung eines 04:25.010 --> 04:30.410 Experten, der bisher am besten war, dass man da selber immer verkehrt 04:30.410 --> 04:36.570 liegt, aber jeder dieser Experten nur in einem Kartel aller Fälle. 04:37.730 --> 04:42.030 Das heißt, Sie haben, also wenn Sie T-Runden haben, Sie selber haben T 04:42.030 --> 04:45.350 -Fehlentscheidungen, aber der beste Experte und tatsächlich jeder 04:45.350 --> 04:48.630 Experte hat nur so über den Daumen T durch K. 04:48.630 --> 04:50.590 Also Sie sind um den Faktor K schlechter. 04:52.270 --> 04:54.870 Ja gut, kann natürlich sein, dass es gar nicht besser geht, also 04:54.870 --> 04:58.650 könnte sein, aber es zeigt sich, ja doch, es geht besser. 04:59.830 --> 05:00.330 So. 05:02.830 --> 05:03.970 Und wie geht das? 05:05.070 --> 05:06.750 Naja, wir haben es schon gesehen. 05:07.630 --> 05:11.470 Das ist jetzt erstmal ein deterministischer Algorithmus, ja. 05:13.710 --> 05:17.330 Also die Idee mit dem Zurückgucken, wer hat am seltensten falsch 05:17.330 --> 05:20.650 gelegen, das ist ja so ein bisschen so... 05:22.030 --> 05:24.590 Wen halten wir für besser, wen für schlechter oder so. 05:25.410 --> 05:28.750 Und sowas ähnliches, etwas, was vordergründig so ähnlich aussieht, 05:28.890 --> 05:31.830 passiert hier auch, aber Sie sind aufgefordert, zu Hause nochmal 05:31.830 --> 05:34.210 darüber nachzudenken, warum das etwas anderes ist. 05:37.010 --> 05:40.270 Und die Idee ist, also jeder Experte kriegt so ein Gewicht, 05:40.830 --> 05:43.570 Wichtigkeit, Bedeutung, ich weiß nicht, wie Sie das interpretieren 05:43.570 --> 05:47.730 wollen, und initial alle eins. 05:51.750 --> 05:54.210 Und die geben also Empfehlungen ab. 05:55.750 --> 06:00.950 Und wenn Sie dann diese Empfehlungen haben, dann entscheiden Sie sich 06:00.950 --> 06:06.470 für Ja oder für Nein, je nachdem, ob das Gewicht der Experten, die für 06:06.470 --> 06:10.490 Ja sind, größer ist als das restliche Gewicht, oder als das Gewicht 06:10.490 --> 06:13.550 der Experten, die für Nein sind, oder ob das Gewicht für Nein 06:13.550 --> 06:14.190 überwiegt. 06:15.090 --> 06:16.770 So entscheiden Sie sich. 06:18.990 --> 06:22.230 Und dann kriegen Sie mitgeteilt, was wäre die richtige Entscheidung 06:22.230 --> 06:22.630 gewesen. 06:23.010 --> 06:26.270 Und jetzt können Sie auch gucken, welche Experten lagen richtig, 06:26.370 --> 06:27.810 welche Experten lagen falsch. 06:29.790 --> 06:34.150 Und Experten, die falsch lagen, kriegen ihr Gewicht halbiert. 06:34.910 --> 06:35.950 Und die anderen behalten es. 06:36.530 --> 06:39.190 Also in der ersten Runde, am Anfang alle haben Gewicht 1. 06:40.070 --> 06:44.050 Nach der ersten Runde, die, die falsch lagen, haben nur noch Gewicht 1 06:44.050 --> 06:44.250 ,5. 06:44.850 --> 06:46.570 Die, die richtig lagen, haben noch 1. 06:47.230 --> 06:52.430 In der zweiten Runde, die, die richtig lagen, behalten ihr Gewicht 1 06:52.430 --> 06:55.110 oder vielleicht nur noch 1,5, weil sie in der ersten Runde falsch 06:55.110 --> 06:55.550 lagen. 06:56.150 --> 06:57.630 Und die, die falsch lagen, kriegen es halbiert. 06:57.770 --> 06:59.290 Sie sind ja nur noch bei 1,5 oder 1,25. 06:59.670 --> 07:00.370 Und so weiter. 07:02.770 --> 07:05.910 Und ansonsten aber das Kriterium für die eigene Entscheidung immer das 07:05.910 --> 07:06.730 gleiche. 07:07.630 --> 07:10.550 Was ist insgesamt das Gewicht der Experten, die für Ja sind? 07:10.650 --> 07:13.090 Was ist insgesamt das Gewicht der Experten, die für Nein sind? 07:13.930 --> 07:17.130 Die Empfehlung mit dem größeren Gewicht, die nehmen wir. 07:18.570 --> 07:19.450 So. 07:20.770 --> 07:28.750 Behauptung, wenn man das so macht, ganz egal, was diese Experten da so 07:28.750 --> 07:36.910 veranstalten, im Nachhinein, die eigene Anzahl Fehlentscheidungen ist 07:36.910 --> 07:42.350 jetzt nicht mehr so absurd weit weg von der Anzahl Fehlentscheidungen 07:42.350 --> 07:43.790 der besten Experten. 07:43.790 --> 07:46.750 Also im Vergleich zu dieser, wir nehmen immer den, der bisher am 07:46.750 --> 07:47.270 besten war. 07:48.150 --> 07:56.550 Nämlich, dieser Algorithmus ist 1 durch Logarithmus zur Basis 2 von 4 07:56.550 --> 07:56.910 Drittel. 07:57.230 --> 07:59.470 Das ist ungefähr 2,4 oder so. 08:01.890 --> 08:03.090 Kompetitiv. 08:03.210 --> 08:10.970 Also die eigene Anzahl Fehlentscheidungen ist kleiner oder gleich 2,4 08:10.970 --> 08:22.430 mal die minimale Anzahl Fehlentscheidungen, die die besten Experten 08:22.430 --> 08:24.070 nur gegeben haben. 08:24.070 --> 08:30.370 Plus, ja also die optimale Anzahl Fehlentscheidungen plus Logarithmus 08:30.370 --> 08:30.970 von K. 08:31.770 --> 08:33.970 Logarithmus von Anzahl der Experten. 08:36.190 --> 08:42.190 Das ist eine Konstante, die hängt irgendwie nicht von der Folge von 08:42.190 --> 08:44.050 diesen Runden ab, was da passiert. 08:44.190 --> 08:45.310 Ja, das ist eine feste Zahl. 08:46.690 --> 08:49.750 Das eine, was man hier sieht, hier ist es augenscheinlich nützlich, 08:50.030 --> 08:53.750 jetzt mal nicht von strikter Kompetitivität auszugehen, sondern eben 08:53.750 --> 08:55.850 so einen zusätzlichen Summanden dazu erlauben. 08:58.170 --> 09:03.470 Und so ein bisschen Händewedeln könnten sie das interpretieren als, ja 09:03.470 --> 09:07.130 so in den ersten Runden, da muss sich der Algorithmus erstmal so ein 09:07.130 --> 09:10.310 bisschen warmlaufen, dass die Gewichte so ein bisschen passen. 09:11.930 --> 09:13.470 Logarithmus von K reicht halt. 09:14.670 --> 09:19.350 Und danach, in Anführungszeichen, geht es so im Mittel halbwegs gut. 09:22.180 --> 09:29.500 Ja, das wollen wir jetzt mal beweisen, ja, mit diesem Faktor 1 durch 09:29.500 --> 09:30.680 Logarithmus von K³. 09:34.000 --> 09:38.740 Dazu guckt man sich erstmal eine einzelne Runde an, ja, also am Anfang 09:38.740 --> 09:42.680 die Experten, nicht unbedingt die erste, am Anfang jeder Experte hat 09:42.680 --> 09:43.600 irgendein Gewicht Wi. 09:47.400 --> 09:52.980 Und wenn man die Gewichte alle aufsummiert, das zu Beginn der Runde 09:52.980 --> 09:58.980 Nummer T, das heißt Groß Wt, ja, das ist die Summe der Gewichte zu 09:58.980 --> 10:00.020 Beginn der Runde T. 10:01.060 --> 10:04.660 Also initial zu Beginn der ersten Runde ist das N, ach jetzt steht da 10:04.660 --> 10:08.480 noch N, das soll K heißen, irgendwann habe ich die Variable umbenannt. 10:08.480 --> 10:12.540 Also Anzahl der Experten, ja, jeder hat am Anfang Gewicht 1. 10:15.180 --> 10:15.740 So. 10:17.600 --> 10:23.720 Und ja, das teilt sich dann also auf und dann entscheidet man sich 10:23.720 --> 10:27.000 selber und dann kommt das richtige Ergebnis und dann ist also ein Teil 10:27.000 --> 10:28.480 der Empfehlungen verkehrt. 10:29.380 --> 10:35.500 Also jetzt nicht aufaddieren, Empfehlung ja, Empfehlung nein, sondern 10:35.500 --> 10:40.480 stellen wir uns das so vor, also ein paar lagen halt richtig und das R 10:40.480 --> 10:45.100 von Rt, das sei das Gewicht, die Summe der Gewichte der Experten, die 10:45.100 --> 10:49.580 die richtige Antwort empfohlen haben und das Ft sei die Summe der 10:49.580 --> 10:52.700 Gewichte der Experten, die die falsche Antwort empfohlen haben. 10:53.800 --> 10:58.320 Also Rt plus Ft ist insgesamt das Wt, ja, jeder hat ja das Richtige 10:58.320 --> 10:59.400 oder das Falsche empfohlen. 11:00.760 --> 11:01.240 So. 11:02.240 --> 11:05.460 Und jetzt, die, die das Falsche empfohlen haben, die kriegen ihr 11:05.460 --> 11:06.100 Gewicht halbiert. 11:07.380 --> 11:14.980 Das heißt, für die nächste Runde, das Wt plus 1, da hat man dann bei 11:14.980 --> 11:17.440 denen, die falsch lagen, nur noch das halbe Gewicht, das ist also nur 11:17.440 --> 11:22.560 noch die Hälfte von Ft plus, die anderen behalten ihr Gewicht, Rt. 11:30.150 --> 11:33.190 Jetzt, wenn sie die falsche Entscheidung getroffen haben, dann war 11:33.190 --> 11:35.950 also das Gewicht für die falsche Entscheidung größer als das Gewicht 11:35.950 --> 11:36.950 für die richtige Entscheidung. 11:42.850 --> 11:47.230 Also Rt war kleiner als Ft oder anders gesagt Rt war kleiner als Wt 11:47.230 --> 11:47.610 halbe. 11:49.630 --> 11:54.330 Das heißt, der Teil Ft, den sie jetzt halbieren, machte mehr als die 11:54.330 --> 11:55.750 Hälfte vom Ganzen aus. 11:56.570 --> 11:59.650 Also mehr als die Hälfte von dem ganzen Gewicht halbieren sie jetzt. 12:00.370 --> 12:03.470 Da fällt also mindestens ein Viertel weg vom Gesamtgewicht, das vorher 12:03.470 --> 12:04.030 da war, ja. 12:04.850 --> 12:09.570 Oder wenn sie das irgendwie mit Formeln hinschreiben, ja das Rt ist Rt 12:09.570 --> 12:16.710 halbe plus Rt halbe und Ft halbe plus Rt halbe ist Wt halbe und Rt 12:16.710 --> 12:24.070 halbe ist kleiner als Wt Viertel, weil ja Rt weniger als Wt halbe ist, 12:24.170 --> 12:29.850 dann sind sie also bei höchstens 3 Viertel Wt in Runde Wt plus 1. 12:29.850 --> 12:33.550 Das ist immer so, wenn wir uns für das Falsche entscheiden. 12:33.690 --> 12:39.870 Also wenn die Empfehlungen, die das größere Gewicht hatte, die falsche 12:39.870 --> 12:40.330 waren. 12:41.390 --> 12:43.990 Also immer wenn wir einen Fehler machen, weil die Empfehlung Mist war, 12:45.210 --> 12:49.170 das Gesamtgewicht schrumpft um mindestens ein Viertel. 12:50.110 --> 12:54.690 Ja, bei jedem Fehler, den wir machen, weil die Empfehlungen so 12:54.690 --> 12:55.190 schlecht waren. 13:00.310 --> 13:03.870 Gut, also es geht los mit W1 gleich K. 13:04.170 --> 13:05.750 Ich hoffe, irgendwo steht dann wieder K, ja. 13:06.370 --> 13:10.970 Und bei jeder falschen Entscheidung schrumpft das mit dem Faktor 3 13:10.970 --> 13:11.350 Viertel. 13:12.010 --> 13:16.650 Das heißt, wenn man F mal einen Fehler gemacht hat, weil F mal die 13:16.650 --> 13:23.270 Empfehlung überwiegend schlecht, die verkehrte war, dann ist also Wt 13:23.270 --> 13:28.550 kleiner gleich 3 Viertel hoch F mal W1, also 3 Viertel hoch F mal K. 13:37.380 --> 13:43.060 Andererseits, wenn der beste Experte nur, oder die besten Experten 13:43.060 --> 13:47.280 können ja auch mehrere gleich gut sein, nur Ft mal verkehrt gelegen 13:47.280 --> 13:53.400 haben, dann ist ihr initiales Gewicht 1 nur Ft mal halbiert worden. 13:54.100 --> 13:57.920 Das heißt, die haben dann immer noch in der Runde T Gewicht ein 13:57.920 --> 13:59.180 Halbhoch Fobt. 14:00.900 --> 14:04.520 Und das ist ja offensichtlich einsummand von Groß Wt. 14:05.820 --> 14:08.960 Also Groß Wt ist dann mindestens noch ein Halbhoch Fobt. 14:10.180 --> 14:13.000 Ja, und wenn Sie diese beiden Ungleichungen zusammensetzen, dann ist 14:13.000 --> 14:16.440 also ein Halbhoch Fobt kleiner gleich 3 Viertel hoch F mal K. 14:17.180 --> 14:22.600 Und wenn Sie das nach F auflösen, steht da eben da, F kleiner gleich 1 14:22.600 --> 14:28.840 durch Logarithmus von 4 Drittel mal Fobt plus Logarithmus von K. 14:28.840 --> 14:33.420 Und diese Konstante ist wie gesagt so 1, 2,4. 14:35.440 --> 14:41.400 Also ein konstanter Faktor 2,4 und nicht dieses, man ist, wenn man 14:41.400 --> 14:47.380 Pech hat, K mal schlechter, wenn man immer dem bisher besten Experten 14:47.380 --> 14:47.900 folgt. 14:48.960 --> 14:52.200 Nicht ein Faktor K schlechter, sondern nur ein Faktor 2,4. 14:52.880 --> 14:54.000 Das klingt besser, ja? 14:56.820 --> 15:00.740 Und übrigens, das ist also etwas so oder vielleicht noch ein bisschen 15:00.740 --> 15:02.700 allgemeiner, wie wir uns das gleich angucken. 15:04.660 --> 15:08.120 Das können Sie nicht unbedingt vielleicht nicht nur verwenden, wenn 15:08.120 --> 15:11.320 Sie Aktien kaufen wollen, sondern Sie können sich auch vorstellen, 15:11.440 --> 15:13.840 diese Experten in Anführungszeichen, das sind irgendwelche 15:13.840 --> 15:16.900 Heuristiken, die Sie haben für ein Problem, das Sie exakt vielleicht 15:16.900 --> 15:20.120 nicht lösen können, bearbeiten können. 15:20.120 --> 15:22.680 Dann benutzen Sie halt Heuristik und dann fragen Sie sich immer, haben 15:22.680 --> 15:26.160 Sie Ihre Heuristiken, die irgendetwas sagen und dann müssen Sie sich 15:26.160 --> 15:27.340 für etwas entscheiden. 15:28.320 --> 15:33.280 Und wenn Sie das eben so machen, nur um einen Faktor 2,4, ist das 15:33.280 --> 15:35.400 abgesprochen schlechter als die beste Heuristik. 15:36.440 --> 15:37.980 So ein bisschen Händewedel, ja? 15:38.080 --> 15:40.360 Ohne jetzt genau zu sagen, was die Heuristiken tun und so. 15:41.880 --> 15:45.020 So, 2,4, schon mal nicht schlecht. 15:52.860 --> 15:56.260 Jetzt wenn man sich das so anguckt, kann man sich natürlich fragen, 15:56.400 --> 15:59.360 woher kommt dieser Faktor 2,4 und kann man den vielleicht irgendwie 15:59.360 --> 16:00.200 kleiner machen? 16:05.420 --> 16:08.600 Ja, wie könnte man diesen Faktor noch besser kriegen? 16:09.600 --> 16:14.600 Ich weiß nicht, sehen Sie da eine Idee irgendwo angedeutet? 16:17.100 --> 16:22.260 Naja, also ein Aspekt ist ja irgendwie, da steht eben Logarithmus zur 16:22.260 --> 16:24.960 Basis 2 von irgendetwas. 16:26.300 --> 16:30.340 Und die 2 kommt daher, dass da ein Halb hoch Fob steht. 16:32.120 --> 16:38.000 Und wenn Sie da jetzt nicht eine Halb nehmen, sondern was Größeres 16:38.000 --> 16:40.340 oder so, dann wird das vielleicht besser. 16:41.740 --> 16:45.260 Dann wird der Logarithmus zu einer kleineren Basis und ich weiß nicht. 16:45.760 --> 16:49.420 So, und das ist dann auch das, was man in der allgemeineren Variante, 16:49.440 --> 16:51.780 die wir uns jetzt noch angucken wollen, veranstaltet. 16:53.480 --> 16:59.960 Da sind es jetzt nicht mehr unbedingt irgendwelche Ja-Nein 16:59.960 --> 17:05.880 -Empfehlungen, sondern es gibt halt K-Experten und jeder sagt 17:05.880 --> 17:07.740 irgendetwas, x1, x2, x3. 17:08.780 --> 17:14.240 Dann entscheidet man sich selber für etwas und kriegt man was gesagt, 17:14.320 --> 17:15.040 wie das so war. 17:15.040 --> 17:22.360 Und dann können Sie den Empfehlungen x1 bis xk irgendwelche Noten 17:22.360 --> 17:26.420 geben, Noten in Anführungszeichen, also 0 ist die beste Note und 1 ist 17:26.420 --> 17:27.060 die schlechteste. 17:28.100 --> 17:29.680 Also irgendwas zwischen 0 und 1, ja. 17:33.040 --> 17:39.480 Und die Kosten, die Ihnen entstehen sozusagen, das ist die Note, die 17:39.480 --> 17:43.620 die Empfehlung kriegt, der Sie jetzt dann glücklicher oder dummerweise 17:43.620 --> 17:44.340 gefolgt sind. 17:46.280 --> 17:49.800 Also, im schlechtesten Fall haben Sie Kosten 1 pro Runde, im besten 17:49.800 --> 17:50.800 Fall Kosten 0. 17:53.600 --> 17:54.580 Das ist alles. 17:56.960 --> 17:59.980 Und Sie können ja vielleicht mal kurz überlegen, also offensichtlich 17:59.980 --> 18:03.020 das, was wir gerade betrachtet haben, war ein Spezialfall davon. 18:05.200 --> 18:10.800 Gerade konnten die Noten immer nur 0 oder 1 sein, jetzt kann es aber 18:10.800 --> 18:11.800 auch was dazwischen sein. 18:14.680 --> 18:15.180 So. 18:16.920 --> 18:18.280 Und was macht man jetzt? 18:18.420 --> 18:22.340 Man wählt sich noch ein Epsilon aus, das können Sie sich frei 18:22.340 --> 18:26.420 aussuchen im Bereich sinnvollerweise echt größer 0 und echt kleiner 18:26.420 --> 18:27.320 als ein Halb. 18:29.740 --> 18:33.960 Und wir geben Experten ein Gewicht, das ist auch am Anfang wieder für 18:33.960 --> 18:34.620 jeden 1. 18:36.760 --> 18:41.900 Und jetzt machen Sie nicht irgendwie Mehrheitsentscheidungen oder so, 18:42.060 --> 18:44.820 wie gesagt, die Empfehlungen können ja auch ganz unterschiedlich sein, 18:44.900 --> 18:45.740 nicht nur ja, nein. 18:46.620 --> 18:52.320 Sondern Sie sagen, ja, ok, je größer das Gewicht eines Experten, desto 18:52.320 --> 18:54.700 eher bin ich geneigt, ihm zu folgen. 18:54.700 --> 18:58.980 Und das machen wir dann randomisiert, indem wir sagen, ja, ok, also 18:58.980 --> 19:02.140 die Wahrscheinlichkeit, sich für einen gewissen Experten i zu 19:02.140 --> 19:04.900 entscheiden, ist proportional zu seinem Gewicht. 19:06.700 --> 19:13.320 Also, jeder Experte hat ein Gewicht wie i, dann haben Sie noch in 19:13.320 --> 19:15.200 jeder Runde die Summe aller Gewichte. 19:15.760 --> 19:19.540 Und wenn Sie dann eben das Gewicht durch die Summe aller dividieren, 19:20.020 --> 19:22.680 dann haben Sie Wahrscheinlichkeiten, die aufsummiert 1 geben, also Sie 19:22.680 --> 19:24.900 entscheiden sich mit Wahrscheinlichkeit 1 für einen von denen. 19:26.180 --> 19:29.940 Also das sind die Wahrscheinlichkeiten, ja, Pi ist klein wie i durch 19:29.940 --> 19:31.400 die Summe aller dieser Gewichte. 19:35.000 --> 19:40.100 Und, ja, das gibt dann eben einen Experten und Sie machen das, was der 19:40.100 --> 19:40.340 vorschlägt. 19:41.860 --> 19:46.740 Und dann stellt sich jetzt heraus, irgendwie, ja, diese Empfehlungen 19:46.740 --> 19:48.320 waren mehr oder weniger gut. 19:48.600 --> 19:51.920 Jede Empfehlung kriegt irgendeine Note zwischen 0 und 1. 19:52.720 --> 19:58.020 Also in Runde T, Experte i kriegt Note c, unten i, oben t. 20:01.220 --> 20:05.700 Und dann machen Sie die Gewichte der Experten kleiner. 20:07.680 --> 20:18.240 Wenn die Note 0 ist, dann lassen Sie das Gewicht gleich, da ändert 20:18.240 --> 20:18.720 sich nichts. 20:19.440 --> 20:25.760 Wenn die Note nicht 0 war, irgendwas zwischen 0 und 1, dann 20:25.760 --> 20:29.740 erniedrigen Sie das Gewicht und zwar multiplizieren Sie es mit 1 minus 20:29.740 --> 20:31.980 Epsilon mal Note. 20:32.620 --> 20:38.300 Das ist also, da ziehen Sie also von 1 irgendwas zwischen 0 und 20:38.300 --> 20:39.160 Epsilon ab. 20:40.140 --> 20:44.720 Nicht mehr unbedingt ein Halb, also dieses 1 minus Epsilon ct ist 20:44.720 --> 20:45.840 nicht mehr unbedingt ein Halb. 20:46.660 --> 20:51.180 Wenn die Note ziemlich gut ist, 0,1 oder irgendwie und wenn das 20:51.180 --> 20:55.060 Epsilon womöglich auch noch ganz klein ist, dann ziehen Sie da halt 20:55.060 --> 20:56.640 weniger als ein Viertel ab von der 1. 21:01.520 --> 21:05.020 Dann haben Sie neue Gewichte für alle Experten, jeder kriegt eine Note 21:05.020 --> 21:07.240 und dann in der nächsten Runde das gleiche von vorne. 21:11.200 --> 21:15.640 Und wenn man das macht, stellt sich heraus, also wenn Sie k Experten 21:15.640 --> 21:22.420 haben und sich ein Epsilon zwischen 0 und 1,5 gewählt haben, dann, und 21:22.420 --> 21:28.400 Sie machen das eine beliebige Anzahl Runden, dann erwartet Ihre 21:28.400 --> 21:31.200 Gesamtkosten, wenn Sie immer eben mit der entsprechenden 21:31.200 --> 21:35.320 Wahrscheinlichkeit einem Experten folgen, die erwarteten Gesamtkosten 21:35.320 --> 21:45.000 unterscheiden sich von den Gesamtkosten des oder der im Nachhinein als 21:45.000 --> 21:49.620 optimal erscheinenden Experten um einen Faktor nur noch 1 plus 21:49.620 --> 21:50.120 Epsilon. 21:50.960 --> 21:55.480 Also man ist dann 1 plus Epsilon kompetitiv, hat aber dahinten auch 21:55.480 --> 21:59.080 wieder noch so einen summanden Logarithmus N durch Epsilon. 22:01.440 --> 22:07.900 Und was Sie da sehen, also das Epsilon können Sie sich aussuchen, und 22:07.900 --> 22:11.400 wenn Sie das Epsilon klein wählen, weil Sie gerne sehr kompetitiv sein 22:11.400 --> 22:16.660 wollen, ja sehr nah dran an dem, was der beste Experte so macht, dann 22:16.660 --> 22:20.460 können Sie das tun, dann haben Sie halt 1 plus nur ein kleines 22:20.460 --> 22:26.340 bisschen kleines Epsilon mal optimales K, aber dafür wird halt dieser 22:26.340 --> 22:29.040 Summand Log N durch Epsilon, der wird halt groß. 22:30.200 --> 22:33.440 Also wenn Sie nah dran sein wollen, am besten Experten sehr sehr sehr 22:33.440 --> 22:37.820 nah, dann haben Sie sozusagen eine längere Zeit, wo Sie das erstmal so 22:37.820 --> 22:42.560 ein bisschen spielen müssen, bis das sozusagen in Schwung kommt und 22:42.560 --> 22:44.860 die Gewichte irgendwie plausibel sind oder so. 22:45.080 --> 22:48.980 Das ist jetzt händewedelnd, ja, aber also je kleiner Sie das Epsilon 22:48.980 --> 22:51.480 wählen, umso größer ist die additive Konstante. 22:52.460 --> 22:54.360 Da muss man sich dann halt entscheiden, was man will. 22:56.480 --> 22:56.820 So. 22:58.160 --> 23:01.240 Ja, das muss man jetzt noch nachrechnen und das ist aber im Grunde 23:01.240 --> 23:04.320 jetzt auch wieder ähnlich zu dem, was wir gerade gemacht haben, es ist 23:04.320 --> 23:06.480 halt ein bisschen komplizierter zu rechnen. 23:08.780 --> 23:09.980 Also wieder... 23:11.280 --> 23:15.840 Summe der Gewichte zu Beginn von Runde T, bezeichnen wir die mal mit 23:15.840 --> 23:16.860 Wi oben T. 23:18.900 --> 23:23.480 Und Groß-Wt soll die Summe der Gewichte sein, da sollte also 23:23.480 --> 23:27.480 eigentlich Summe der, nicht der Wi, sondern der Wi oben T stehen. 23:27.920 --> 23:31.500 Also das ist das Gesamtgewicht zu Beginn von Runde T. 23:32.220 --> 23:40.120 Und wir entscheiden uns mit Wahrscheinlichkeit klein Wi oben T durch 23:40.120 --> 23:42.560 Groß -Wt für Experte I. 23:44.480 --> 23:48.400 Und am Ende stellt sich raus, ja, Experte I in Runde T hat halt 23:48.400 --> 23:49.900 irgendwelche Kosten C, I, T. 23:50.500 --> 23:55.500 Das heißt, wenn Sie das aufaddieren, Wahrscheinlichkeit sich für 23:55.500 --> 23:59.760 Experte I zu entscheiden, mal Kosten, die dann entstehen, das ist halt 23:59.760 --> 24:03.520 der Erwartungswert für die eigenen Kosten, die Sie haben in Runde T. 24:03.680 --> 24:04.840 Das ist dieses Groß-Kt. 24:04.840 --> 24:05.760 So. 24:08.870 --> 24:12.430 Und jetzt guckt man sich wieder an, na, wie ist das denn dann eine 24:12.430 --> 24:13.130 Runde später? 24:13.270 --> 24:15.350 Was ist Groß-Wt plus 1? 24:17.790 --> 24:19.550 Ja, was passiert mit den Gewichten? 24:19.970 --> 24:24.090 Jedes Gewicht von Runde T wird multipliziert mit 1 minus Epsilon mal 24:24.090 --> 24:24.850 C, I, T. 24:26.790 --> 24:31.530 Also Groß-Wt plus 1 ist Summe dieser kleinen Wi mal 1 minus Epsilon C, 24:31.570 --> 24:31.870 I, T. 24:32.550 --> 24:34.350 Das ziehen Sie einfach auseinander. 24:34.470 --> 24:37.490 Da haben Sie vorne die Summe der W, I, T stehen. 24:39.230 --> 24:42.850 Das ist also das Gesamtgewicht vor Runde T, das ist das Wt. 24:43.830 --> 24:50.470 Und hinten haben Sie minus Epsilon mal Summe der W, I, T mal C, I, T. 24:51.350 --> 24:52.850 Das Epsilon ist eine Konstante. 24:55.410 --> 25:04.790 Und wenn Sie jetzt nochmal da oben zur Definition von Groß-Kt gucken, 25:06.010 --> 25:09.850 dann können Sie das natürlich mit Groß-Wt durchmultiplizieren. 25:09.930 --> 25:15.090 Dann sehen Sie Groß-Kt mal Groß-Wt ist Summe der W, I, T mal C, I, T. 25:16.030 --> 25:20.290 Das ist das, was hier gerade noch jetzt beim Ausrechnen von Wt plus 1 25:20.290 --> 25:21.130 da hinten steht. 25:22.190 --> 25:26.850 Also da ergibt sich dann Wt minus Epsilon mal Kt mal Wt. 25:26.990 --> 25:30.170 Das ist also Wt mal 1 minus Epsilon Kt. 25:33.220 --> 25:35.420 Und das können Sie jetzt auch wieder iterieren. 25:37.400 --> 25:43.020 Vorhin hatten wir da irgendwie so einen Faktor ein Dreiviertel. 25:43.320 --> 25:44.790 Das ist halt jetzt ein bisschen was Komplizierteres. 25:46.300 --> 25:49.560 Aber das können Sie natürlich auch induktiv hochziehen und Wt plus 1 25:49.560 --> 25:50.740 ist dann W1. 25:52.560 --> 25:55.240 Das ist so K, sorry, da steht jetzt wieder N. 25:56.560 --> 26:02.600 Und dann Produkt aller 1 minus Epsilon mal eigene Kosten zum Zeitpunkt 26:02.600 --> 26:05.120 Tau für Tau gleich 1 bis T. 26:07.970 --> 26:10.130 So, und das logaritmiert man dann. 26:11.350 --> 26:15.190 Dann steht da also Logarithmus von Wt plus 1 ist kleiner gleich 26:15.190 --> 26:17.310 Logarithmus von W1. 26:17.450 --> 26:20.270 Das ist ln N oder wenn man es richtig schreibt ln K. 26:24.930 --> 26:31.190 Und dann kommt plus Logarithmus vom Produkt dieser Faktoren. 26:31.830 --> 26:35.770 Das ist also plus die Summe der Logarithmen der einzelnen Faktoren. 26:36.470 --> 26:41.530 Also da stünde jetzt eigentlich plus Summe der Log von 1 minus Epsilon 26:41.530 --> 26:42.070 Kt. 26:43.270 --> 26:54.940 Und Logarithmus von 1 minus X ist aber kleiner gleich minus X in einem 26:54.940 --> 26:56.720 Bereich, der hier relevant ist. 26:58.200 --> 27:03.120 Und dann können Sie statt Logarithmus 1 minus Epsilon Kt, können Sie 27:03.120 --> 27:06.660 einfach minus Epsilon Kt schreiben. 27:07.360 --> 27:10.560 Und dann können Sie das Epsilon noch vor das Summenzeichen ziehen und 27:10.560 --> 27:15.840 übrig bleibt Summe der eigenen Kosten zu den ganzen Runden aufaddiert. 27:16.540 --> 27:17.760 Also das ist unser Groß K. 27:19.840 --> 27:26.000 Also hier steht erstmal Logarithmus von Wt plus 1 ist kleiner gleich 27:26.000 --> 27:28.580 Log K minus Epsilon mal Groß K. 27:28.720 --> 27:31.000 Unsere erwarteten eigenen Kosten insgesamt. 27:34.100 --> 27:40.340 Andererseits, das ist jetzt der andere Teil analog zu dem von vorhin. 27:42.880 --> 27:51.720 Für jeden Experten gilt, dass in jeder Runde eben sein Gewicht in 27:51.720 --> 27:55.760 Anführungszeichen nur um so einen Faktor 1 minus Epsilon C Itau 27:55.760 --> 27:56.300 schrumpft. 27:57.680 --> 28:04.560 Und deswegen Wt plus 1, also klein Wt plus 1 ist dann das Produkt 28:04.560 --> 28:08.000 dieser Dinger, weil es Initial 1 ist, das Gewicht aller Experten. 28:10.940 --> 28:15.580 Das gilt für alle, insbesondere auch für den optimalen Experten oder 28:15.580 --> 28:16.880 die optimalen Experten. 28:19.260 --> 28:20.880 Und da können Sie jetzt auch logarithmieren. 28:22.520 --> 28:25.520 Also da steht jetzt für das Groß Wt plus 1 ein größer Gleich, eine 28:25.520 --> 28:27.320 Abschätzung nach unten durch dieses Produkt. 28:28.000 --> 28:30.600 Da können Sie jetzt auch logarithmieren und für den Logarithmus eine 28:30.600 --> 28:33.380 andere Abschätzung, diesmal eben auch nach unten einsetzen. 28:36.360 --> 28:39.340 Also die erste war Ihnen vielleicht noch geläufig, ich weiß nicht wie 28:39.340 --> 28:42.240 oft Sie die zweite schon gesehen haben, aber das gilt halt auch. 28:43.740 --> 28:48.540 Und das heißt, Sie können dieses Logarithmus von Produkt der 1 minus 28:48.540 --> 28:50.620 Epsilon C Itau abschätzen nach unten. 28:50.760 --> 28:56.340 Summe der Logarithmus 1 minus Epsilon C Itau und das nach unten minus 28:56.340 --> 29:02.340 Summe der Epsilon C Itau plus Epsilon C Itau zum Quadrat. 29:02.340 --> 29:06.420 Und diese Noten sind ja zwischen 0 und 1. 29:09.320 --> 29:13.100 Und eine Zahl zwischen 0 und 1 Quadrat ist kleiner als das Original. 29:16.380 --> 29:19.200 Deswegen können Sie das noch weiter nach unten abschätzen, indem Sie 29:19.200 --> 29:24.300 da dieses C Itau zum Quadrat abschätzen durch C Itau. 29:25.080 --> 29:30.060 Und dann können Sie das, das ist hier in dem dritten Punkt jetzt in 29:30.060 --> 29:33.160 der Formel, und dann können Sie das Epsilon plus Epsilon Quadrat 29:33.160 --> 29:38.200 vorziehen und hinten besteht noch Summe der Noten und das ist die 29:38.200 --> 29:43.080 Gesamtkosten, die Gesamtnote, wie man es sehen will, von Experte I. 29:44.120 --> 29:47.140 Und das gilt für alle Experten, also auch für den optimalen. 29:48.140 --> 29:52.540 Und das heißt eben minus Epsilon plus Epsilon Quadrat mal optimale 29:52.540 --> 29:57.580 Kosten ist kleiner gleich Logarithmus von Groß Wt plus 1 und das haben 29:57.580 --> 30:02.420 wir auf der Folie abgeschätzt nach oben durch lnk mal Epsilon Groß K. 30:03.460 --> 30:08.160 Ja und dann löst man nach Groß K auf und es kommt das raus, was 30:08.160 --> 30:08.860 behauptet wurde. 30:12.360 --> 30:12.820 Fertig. 30:15.120 --> 30:19.800 Also, wenn Sie in der Lage sind, das so zu machen mit den Noten, dann 30:19.800 --> 30:24.100 können Sie beliebig nah an das Optimum rankommen, wenn Sie bereit 30:24.100 --> 30:27.660 sind, einen hinreichend großen additiven Term zu spendieren. 30:28.520 --> 30:30.860 Der steht da, das lnk durch Epsilon. 30:31.660 --> 30:33.200 Wenn Epsilon klein ist, ist das groß. 30:35.360 --> 30:38.460 Und das wird man dann halt in der Praxis irgendwie abwägen müssen, was 30:38.460 --> 30:38.980 man macht. 30:39.820 --> 30:43.920 Und das ist aber durchaus etwas, also dieses Vorgehen hier, was in der 30:43.920 --> 30:47.200 Praxis bei Lernalgorithmen oder wo auch immer benutzt wird. 30:47.300 --> 30:48.360 Ja, also so ist es nicht. 30:49.680 --> 30:50.080 Gut. 30:50.080 --> 30:56.200 Also hier jetzt dann auch wieder nochmal, na erstens, also online und 30:56.200 --> 31:00.820 man hat einen Konst, hier jetzt, man hatte konstante, immerhin 31:00.820 --> 31:04.120 konstante Kompetitivität, 2,409 irgendwas. 31:04.880 --> 31:09.100 Und mit Randomisierung kriegt es den Faktor noch ein bisschen kleiner. 31:09.840 --> 31:12.740 Um einen gewissen Preis, so einen additiven Term. 31:16.310 --> 31:16.830 Jo. 31:19.610 --> 31:24.490 Damit sind wir am Ende des Kapitels zu Online-Algorithmen. 31:26.430 --> 31:28.210 Vergleichen Sie vielleicht nochmal zu Hause. 31:28.350 --> 31:33.730 Also es gibt da natürlich offensichtlich irgendwelche Verbindungen zu 31:33.730 --> 31:34.350 Approximationsalgorithmen. 31:35.430 --> 31:37.690 Gucken Sie sich das nochmal an, aber machen Sie auch klar, wo die 31:37.690 --> 31:38.570 Unterschiede sind. 31:42.500 --> 31:45.840 Und dann kommt jetzt sozusagen ein Bruch. 31:47.080 --> 31:48.360 Und wir gehen zum nächsten Kapitel. 31:49.280 --> 31:52.580 Und da soll es jetzt wirklich um etwas ganz anderes gehen, nämlich 31:52.580 --> 31:53.880 parallele Algorithmen. 31:56.940 --> 31:58.180 Oh, da haben Sie recht. 31:58.960 --> 32:01.200 Damit habe ich überhaupt nichts zu tun. 32:01.340 --> 32:07.320 Ich weiß nicht, es kann, also es gibt viele Möglichkeiten, nur das 32:07.320 --> 32:10.340 Lämpchen ist kaputt oder die Aufnahme läuft nicht. 32:11.500 --> 32:12.960 Ich habe keine Ahnung, sorry. 32:15.300 --> 32:16.380 Aber Sie haben recht. 32:18.640 --> 32:21.100 Ja, ich werde dann gleich mal nachfragen, ob das geklappt hat oder 32:21.100 --> 32:21.280 nicht. 32:21.360 --> 32:22.400 Ändern kann ich es dann auch nicht mehr. 32:32.850 --> 32:36.270 Ist die schon die ganze Zeit aus, die Lampe, oder ist die gerade erst 32:36.270 --> 32:36.850 ausgegangen? 32:37.170 --> 32:39.350 Die ganze Zeit, soweit Sie das beobachtet haben. 32:43.040 --> 32:47.700 Also man hat mir auch am Anfang des Semesters gesagt, da gab es auch 32:47.700 --> 32:49.760 irgendwie technische Probleme mit der Aufnahme. 32:49.980 --> 32:52.800 Deswegen gab es auch von einer Veranstaltung nur die Hälfte als 32:52.800 --> 32:54.200 Aufzeichnung oder so etwas. 33:00.600 --> 33:01.560 So, Parallelverarbeitung. 33:02.100 --> 33:03.060 Also was soll das heißen? 33:03.880 --> 33:10.140 Na, Sie sehen, also als ich so alt war wie Sie oder noch ein bisschen 33:10.140 --> 33:15.280 jünger, da gab es auch schon die Tagesschau und auch schon die 33:15.280 --> 33:16.280 Wettervorhersage. 33:18.040 --> 33:23.780 Aber da gab es Wettervorhersage für morgen und nur für morgen. 33:25.760 --> 33:29.280 Nicht die nächsten drei Tage und in einer Woche und irgendetwas. 33:31.720 --> 33:35.560 Heute kriegt man das für mehr Tage und heute die Vorhersage für die 33:35.560 --> 33:39.560 nächsten drei oder vier Tage ist so zuverlässig wie vor, was weiß ich, 33:39.600 --> 33:42.620 50 Jahren, die Vorhersage für morgen. 33:43.900 --> 33:45.540 Da hat sich irgendwas verbessert. 33:50.530 --> 33:55.350 Unter anderem, also man hat wahrscheinlich bessere Modelle dafür, wie 33:55.350 --> 33:56.410 entwickelt sich Wetter. 33:56.890 --> 33:58.650 Also was heißt ein Modell für Wetterentwicklung? 33:59.570 --> 34:03.890 Ich habe mal vor etliche Jahre her einen Vortrag gesehen, das ist 34:03.890 --> 34:05.710 schon länger her, das waren noch Plastikfolien. 34:05.990 --> 34:08.410 Da hat jemand gesagt, jetzt zeige ich Ihnen mal, wie Wettervorhersage 34:08.410 --> 34:08.670 geht. 34:08.750 --> 34:12.150 Dann hat er da drei Folien, die von oben bis unten voll waren, mit 34:12.150 --> 34:14.950 partiellen Differenzialgleichungen hingelegt und hat gesagt, so, das 34:14.950 --> 34:15.330 ist es. 34:15.990 --> 34:17.490 Damit muss man umgehen. 34:18.150 --> 34:24.250 Und dann muss man, also das ist wahrscheinlich besser geworden, aber 34:24.250 --> 34:28.750 was man da macht, man muss da irgendwie so Nährungslösungen für so ein 34:28.750 --> 34:30.670 partielles Differenzialgleichungssystem ausrechnen. 34:32.570 --> 34:38.570 Und das macht man, indem man dann sozusagen die Erde diskretisiert und 34:38.570 --> 34:43.850 die Luft oben drüber, so in Quader, irgendwie ein paar Kilometer lang 34:43.850 --> 34:46.210 und breit und ein paar hundert Meter hoch oder was auch immer. 34:46.890 --> 34:49.110 Und dann für jeden Quader etwas rechnet. 34:53.850 --> 34:58.010 Und innerhalb eines Quaders nimmt man an, alles ist konstant. 34:58.090 --> 35:01.990 Im ganzen Quader überall gleiche Temperatur, gleiche Luftfeuchtigkeit, 35:02.250 --> 35:05.730 gleiche Windgeschwindigkeit, gleiche Höhe über dem Meeresspiegel, 35:05.790 --> 35:06.330 alles gleich. 35:08.110 --> 35:12.330 Da muss man, also macht man offensichtlich Fehler und tendenziell hat 35:12.330 --> 35:15.930 man das Gefühl, man macht weniger Fehler, wenn man das in kleinere 35:15.930 --> 35:16.470 Teile unterteilt. 35:17.410 --> 35:18.270 Das ist auch so. 35:18.890 --> 35:21.350 Aber wenn man das in kleinere Teile unterteilt, muss man bei der 35:21.350 --> 35:22.690 Wettervorhersage viel mehr rechnen. 35:26.190 --> 35:31.290 Und das ist so viel, das kann man nicht mehr eine CPU machen lassen, 35:31.370 --> 35:32.370 dann wird es nur noch eine Wetternachhersage. 35:34.730 --> 35:38.030 Also man muss irgendwie diese vielen Rechnungen aufteilen auf mehrere 35:38.030 --> 35:38.750 Prozessoren. 35:38.990 --> 35:42.770 Und zwar heutzutage schon auch ziemlich viele Prozessoren. 35:43.910 --> 35:46.790 Sie können sich ja mal angucken, was für Rechner, ich weiß nicht, beim 35:46.790 --> 35:49.870 Deutschen Wetterdienst oder in England bei dem Zentrum für 35:49.870 --> 35:52.030 mittelfristige Wettervorhersage so umstehen. 35:52.650 --> 35:55.190 Das sind nicht die allergrößten, die es so gibt auf der Welt, aber 35:55.190 --> 35:57.090 auch immerhin schon ganz ordentliche Dinge. 35:59.010 --> 36:02.710 So, und man hat also einen Haufen Berechnungen und ist in der 36:02.710 --> 36:06.770 glücklichen Lage, das so auf ein paar Arbeiter, auf ein paar 36:06.770 --> 36:08.370 Prozessoren verteilen zu können. 36:08.870 --> 36:12.050 Die können natürlich nicht unabhängig voneinander vor sich hin 36:12.050 --> 36:12.350 rechnen. 36:13.310 --> 36:17.290 Also wenn man so viel 2-Quader was simuliert, dann wird man vielleicht 36:17.290 --> 36:21.910 auch feststellen, ah, jetzt Regen, das Regengebiet, die Wolken ziehen 36:21.910 --> 36:24.010 jetzt von einem Quader in den nächsten, da muss man da irgendwie 36:24.010 --> 36:26.010 Informationsaustausch offensichtlich haben. 36:28.630 --> 36:32.830 Aber anscheinend ist das so wenig irgendwie, dass man dann also viele 36:32.830 --> 36:36.890 Prozessoren sinnvoll beschäftigen kann und selbst mit dem zwischendrin 36:36.890 --> 36:40.130 müssen wir Nachrichten von hier nach da schicken, ist es am Ende immer 36:40.130 --> 36:42.210 noch deutlich schneller als ein Prozessor. 36:46.290 --> 36:49.010 Also das ist im Prinzip Parallelverarbeitung. 36:49.230 --> 36:53.430 Viele Prozessoren arbeiten gemeinsam daran, irgendetwas auszurechnen, 36:53.470 --> 36:55.250 was einen als ein Ergebnis interessiert. 36:56.450 --> 36:59.950 Und, gut, eine Begründung habe ich gerade schon gesagt, naja, man 36:59.950 --> 37:02.570 möchte halt, dass es vielleicht schneller wird als mit einem 37:02.570 --> 37:03.170 Prozessor. 37:06.650 --> 37:09.410 Habe ich das richtig in Erinnerung mit meinen Folien? 37:09.510 --> 37:09.570 Ja. 37:10.730 --> 37:13.890 Aber wie gesagt, also sofern das nicht was völlig stumpfsinniges ist, 37:13.970 --> 37:16.930 wo jeder unabhängig voneinander von allen anderen einfach vor sich hin 37:16.930 --> 37:20.590 rechnen kann, Sie haben da wahrscheinlich Nachrichtenaustausch, müssen 37:20.590 --> 37:22.990 da irgendwas koordinieren, da müssen wir schon aufpassen, dass das 37:22.990 --> 37:24.690 nicht zu teuer wird, das Ganze außenrum. 37:28.230 --> 37:28.670 Ähm... 37:28.670 --> 37:32.110 So, können Sie sich noch andere Gründe vorstellen, dafür, dass man 37:32.110 --> 37:34.490 vielleicht lieber mehrere Prozessoren benutzt als einen? 37:35.710 --> 37:35.990 Ja? 37:38.330 --> 37:38.770 Ja? 37:39.350 --> 37:39.750 Richtig? 37:41.950 --> 37:42.390 Noch was? 37:43.350 --> 37:44.950 Also steht gleich auf dem Rest der Folie. 37:45.710 --> 37:46.790 Fällt Ihnen noch was ein? 37:46.890 --> 37:46.930 Ja? 37:49.050 --> 37:49.490 Okay. 37:50.810 --> 37:53.130 Das steht nicht auf der Folie, aber ist auch eine schöne Idee, ja? 37:55.250 --> 37:58.710 Und sowas in der Art macht man auch an einigen Stellen. 37:59.330 --> 38:00.050 Noch was? 38:03.390 --> 38:03.550 Ja. 38:07.070 --> 38:08.110 Ganz plump. 38:09.210 --> 38:12.550 Viele Prozessoren haben mehr Speicher und mehr Cache als wenige 38:12.550 --> 38:13.170 Prozessoren. 38:13.750 --> 38:14.830 Das hilft manchmal auch. 38:16.770 --> 38:19.570 Also tatsächlich, man kann unter Umständen Energie sparen. 38:19.570 --> 38:23.890 Ich habe abgeschrieben von den Folien vom letzten Jahr, zwei 38:23.890 --> 38:27.290 Prozessoren mit halber Taktfrequenz brauchen weniger als ein Prozessor 38:27.290 --> 38:28.410 mit voller Taktfrequenz. 38:28.990 --> 38:34.970 Also weniger Energie braucht weniger Energie als ein vollgetakteter. 38:36.010 --> 38:40.130 Ich habe auf Anhieb nicht offensichtlich eine Stelle gefunden, wo das 38:40.130 --> 38:42.150 explizit so steht, aber glauben wir das mal. 38:44.990 --> 38:49.790 Speicher, wie gesagt, wenn sie viele Prozessoren haben, haben sie zum 38:49.790 --> 38:51.050 Beispiel viel mehr Cache. 38:52.390 --> 38:56.970 Und wenn sie Glück haben, diese Effekte gibt es tatsächlich, wenn sie 38:56.970 --> 39:01.110 eine große Probleminstanz haben, so eine Matrix mit 10.000 Zeilen und 39:01.110 --> 39:03.970 10.000 Spalten dicht besetzt oder irgendwie sowas, ja? 39:06.870 --> 39:10.990 Dann, wenn das Problem hinreichend nett ist, sind sie tatsächlich da 39:10.990 --> 39:14.750 schneller, weil einfach mehr im Cache liegt und die Mittel, so die 39:14.750 --> 39:17.190 Zugriffszeiten einfach viel besser sind. 39:17.690 --> 39:20.110 Oder sie kriegen es ja überhaupt zum ersten Mal da in den 39:20.110 --> 39:23.350 Hauptspeicher rein, der da neben den Prozessoren steckt auf den 39:23.350 --> 39:23.930 Mainboards. 39:25.750 --> 39:29.470 Und stellen Sie sich im Zweifelsfall ruhig immer auch mal einen... 39:29.470 --> 39:31.990 haben Sie schon mal jedenfalls ein Foto von einem großen 39:31.990 --> 39:33.150 Parallelrechner gesehen? 39:34.570 --> 39:40.730 Also, Sie haben dann ein Mainboard, da stecken vielleicht schon 2 oder 39:40.730 --> 39:44.150 4 CPUs drauf und jeder hat, ich weiß nicht wie viele Cores. 39:45.130 --> 39:49.930 Und dann haben sie vielleicht irgendwie, ich weiß nicht wie viele 39:49.930 --> 39:54.390 Dutzend Mainboards in einem Schrank stecken und dann haben sie 39:54.390 --> 39:58.790 vielleicht 100 Schränke, also 5 Reihen mit 20 Schränken, alles 39:58.790 --> 40:00.350 vollgestopft mit CPUs. 40:00.570 --> 40:02.590 Und dann noch irgendwie Netzwerk außenrum und so. 40:04.010 --> 40:07.870 Also, das kann dann unter Umständen schon richtig viel Hauptspeicher 40:07.870 --> 40:08.170 sein. 40:08.930 --> 40:09.710 Richtig viel. 40:11.650 --> 40:14.450 Haben Sie mal was von der Top 500 Liste gehört? 40:15.450 --> 40:15.870 Wer hat? 40:17.290 --> 40:19.850 Okay, die anderen, also wie heißt die Seite? 40:20.030 --> 40:25.990 www.top500, also top500.org oder so. 40:27.250 --> 40:32.750 Da wird so alle halben Jahre die Rangliste der schnellsten bekannten 40:32.750 --> 40:36.090 Installationen von Parallelrechnern aufgelistet. 40:36.770 --> 40:38.910 Wer schafft die meisten Petaflops? 40:40.570 --> 40:42.970 Können Sie sich mal angucken, was das für große Kisten sind. 40:45.290 --> 40:49.230 Ja, und manchmal, das trifft jetzt auf solche Hochleistungsrechner 40:49.230 --> 40:53.250 nicht unbedingt zu, aber manchmal ist es halt auch so, dass die Daten, 40:53.330 --> 40:57.670 die sie verarbeiten müssen, vielleicht sogar so irgendwie verteilt 40:57.670 --> 40:58.670 irgendwie anfallen. 41:00.710 --> 41:03.290 Und dann können sie vielleicht auch schon verteilt anfangen, so ein 41:03.290 --> 41:06.010 bisschen zu rechnen, bevor sie dann anfangen, was zusammenzuführen. 41:07.010 --> 41:10.010 Also tatsächlich sparen sie sich vielleicht Kommunikation. 41:15.590 --> 41:20.590 Typisches, also so in die Richtung geht zum Beispiel LHC. 41:23.290 --> 41:26.130 Wem sagt Large Hadron Collider was? 41:28.310 --> 41:29.250 Am CERN. 41:29.670 --> 41:34.210 Also so ein großes Physikexperiment, ein Ring, fast 30 Kilometer 41:34.210 --> 41:38.670 Umfang, wo sie in beiden Richtungen Protonen strahlen. 41:39.490 --> 41:42.810 Auf fast Lichtgeschwindigkeit beschleunigen und sich das dann, die 41:42.810 --> 41:45.130 Protonen kollidieren zu lassen. 41:46.510 --> 41:51.530 Das, was dann direkt nach den Kollisionen passiert, die Daten, die 41:51.530 --> 41:57.150 werden schon direkt da am Experiment mit Spezialhardware eingedampft, 41:57.230 --> 42:00.290 damit man noch überhaupt irgendeine Chance hat, so ein bisschen was 42:00.290 --> 42:03.270 wegzukriegen und das dann so nach und nach zu verteilen. 42:03.270 --> 42:07.870 Zu, ich weiß nicht wie viele Dutzend Rechenzentren, die dann anfangen 42:07.870 --> 42:08.590 daraus zu rechnen. 42:08.710 --> 42:13.430 Aber, also gleich lokal, da sind da viele Detektoren, viele Hardware, 42:13.670 --> 42:14.990 die gleich schon mal so ein bisschen rechnen. 42:17.230 --> 42:17.670 Gut. 42:19.130 --> 42:24.050 Ja, und jetzt, also natürlich in der Vorlesung so ein bisschen von der 42:24.050 --> 42:25.910 Realität muss man irgendwie abstrahieren. 42:26.730 --> 42:29.150 Modelle für Parallelverarbeitung gibt es ganz viele. 42:31.830 --> 42:34.070 Die sehen zum Teil ganz unterschiedlich aus. 42:34.170 --> 42:36.450 Bei manchen sieht man noch gar nicht mal auf den ersten Blick, dass 42:36.450 --> 42:39.930 hier in irgendeinem Sinne so etwas wie Parallelverarbeitung passiert. 42:41.290 --> 42:43.990 Ich meine, wenn man dann drauf gestoßen wird, mit der Nase gesagt 42:43.990 --> 42:46.610 wird, hier, guck mal genau hin, dann kann man sich natürlich schon was 42:46.610 --> 42:47.030 überlegen. 42:47.230 --> 42:49.690 Aber manchmal ist es gar nicht so offensichtlich, ja. 42:51.710 --> 42:56.090 Und, also von den vielen Modellen, die es so gibt, wir beschränken uns 42:56.090 --> 43:01.090 aber auf zwei, wo das mit dem Parallelismus ganz offensichtlich ist. 43:02.170 --> 43:07.230 Das eine sind so, wie soll ich sagen, ja, so ein Netzwerk von 43:07.230 --> 43:12.850 Prozessoren, die halt über die Daten miteinander austauschen können, 43:12.850 --> 43:15.830 indem sie halt sagen, ja, ich habe hier ein Kilobyte, das ist sehr 43:15.830 --> 43:17.770 schön, bitte schick es an Prozessor 23. 43:18.990 --> 43:21.110 Und er muss es halt dann empfangen und kann was damit machen. 43:22.490 --> 43:25.150 Und das andere sind parallele Registermaschinen. 43:27.050 --> 43:33.150 Da spart man sich dieses explizite Sprechen über, wir schicken 43:33.150 --> 43:34.710 Nachrichten von A nach B. 43:36.090 --> 43:40.190 Das macht manches ein bisschen einfacher, hat aber auf der anderen 43:40.190 --> 43:44.790 Seite auch so ein paar kleine Haken, da kommen wir gleich noch dazu. 43:45.690 --> 43:49.530 Also das, was wir uns zunächst mal angucken wollen, sind so, wie soll 43:49.530 --> 43:52.150 man sagen, Nachrichten-gekoppelte Parallelrechner. 43:52.490 --> 43:55.410 Und also in der Praxis finden Sie dann natürlich auch alle möglichen 43:55.410 --> 43:56.330 Mischformen, ja. 43:59.730 --> 44:03.850 Zum Beispiel, also hier so das, was wir uns jetzt erstmal vorstellen, 44:04.410 --> 44:08.690 wir haben irgendwie P-Prozessoren und so ein Prozessor, das ist was 44:08.690 --> 44:12.790 ganz normales, ja, so eine CPU mit Hauptspeicher und stellen Sie sich 44:12.790 --> 44:14.810 ruhig Cache auch noch meinetwegen dabei vor. 44:19.770 --> 44:25.010 Und so ein Speicher ist aber fest an einer CPU dran und nur diese eine 44:25.010 --> 44:27.690 CPU kann direkt auf diesen Speicher zugreifen, ja. 44:29.170 --> 44:32.690 Prozessor 0 kann nur auf seinen Speicher 0 zugreifen, Prozessor 1 nur 44:32.690 --> 44:33.910 auf seinen Speicher und so. 44:37.490 --> 44:46.230 So und wenn jetzt irgendwie Daten transportiert werden müssen, dann 44:46.230 --> 44:49.010 muss eben ein Prozessor sagen, ich möchte, dass die wegtransportiert 44:49.010 --> 44:50.650 werden und sagt halt auch wohin. 44:51.290 --> 44:54.190 Und auf der anderen Seite der Empfänger muss sagen, oh ja, jetzt 44:54.190 --> 44:58.950 möchte ich auch gerne Nachricht empfangen und dann kriegt er die auch. 45:00.210 --> 45:03.470 Da taucht natürlich dann gleich das Problem auf, was ist, wenn mehrere 45:03.470 --> 45:07.110 an einen schicken, der Empfänger, wie kann der unterscheiden, was er 45:07.110 --> 45:08.150 jetzt kriegt und solche Dinge. 45:09.250 --> 45:11.870 Unsere Beispielalgorithmen sind alle so harmlos, da müssen wir uns um 45:11.870 --> 45:12.770 sowas nicht kümmern. 45:15.750 --> 45:20.310 Aber in der Praxis ist das dann natürlich immer noch mal ein bisschen 45:20.310 --> 45:21.110 komplizierter. 45:22.690 --> 45:26.310 So das ist also so grob das Ding, was wir uns zuerst angucken wollen. 45:27.030 --> 45:35.790 Für diese andere Richtung, Richtung parallele Registermaschine oder 45:35.790 --> 45:41.490 so, da können sich tendenziell etwas, so ein Bildchen vorstellen, muss 45:41.490 --> 45:42.690 man nicht, kann man. 45:43.930 --> 45:50.830 Also wieder, man hat Prozessoren, so CPUs, meinetwegen mit einem 45:50.830 --> 45:53.350 Akkumulator oder konstant vielen Registern. 45:53.350 --> 45:57.950 Aber, und natürlich gibt es noch irgendwo Hauptspeicher, aber es ist 45:57.950 --> 46:02.410 nicht irgendwie so, dass jeder Hauptspeicher, jedes Hauptspeichermodul 46:02.410 --> 46:04.990 einem bestimmten Prozessor gehört und nur der kann darauf zugreifen, 46:05.090 --> 46:05.890 sondern es gibt Speicher. 46:06.310 --> 46:08.810 Ich habe jetzt der Bequemlichkeit halber da wieder verschiedene Module 46:08.810 --> 46:10.830 hingemalt, kann man auch als eins hinmalen. 46:11.450 --> 46:14.830 Und jeder Prozessor kann auf jede Stelle im globalen Speicher 46:14.830 --> 46:15.450 zugreifen. 46:16.270 --> 46:19.570 Und kann ohne Zutun von anderen, es ist nicht so, dass Speicher immer 46:19.570 --> 46:23.410 irgendwem gehört oder so, jeder kann irgendwo was hinschreiben und 46:23.410 --> 46:25.550 jemand anders kann da lesen und dann hat er das eben. 46:27.030 --> 46:32.350 Und Daten übertragen heißt dann einfach nur, ja der Sender schreibt es 46:32.350 --> 46:35.230 halt an eine vielleicht irgendwie vereinbarte Stelle in den Speicher 46:35.230 --> 46:35.930 und gut ist. 46:36.550 --> 46:39.350 Und zu dem Zeitpunkt, wo er das tut, da muss nicht der Empfänger auch 46:39.350 --> 46:40.350 schon irgendetwas tun. 46:41.050 --> 46:42.210 Kann er irgendwie später machen. 46:48.760 --> 46:50.960 Das gucken wir uns als zweites an. 46:52.480 --> 46:54.820 Hat alles so seine Vor- und Nachteile. 46:57.220 --> 47:00.940 Je nachdem, auf welchem Standpunkt man so steht und in welcher 47:00.940 --> 47:05.400 Situation man ist, liegen dann halt auch die Nachteile des einen oder 47:05.400 --> 47:07.160 des anderen Modells schwerer. 47:08.620 --> 47:14.820 Wenn Sie Nachrichtenkopplung haben, wenn der Sender was wegschickt, 47:15.060 --> 47:20.380 womöglich ist es so, müssen Sie sich vorstellen, ja der Sender, der 47:20.380 --> 47:23.040 kann erst weitermachen, wenn tatsächlich der Empfänger bereit ist und 47:23.040 --> 47:25.340 gesagt hat, ja jetzt hier, ich empfange das auch. 47:26.120 --> 47:27.800 Und erst dann wird es übertragen. 47:27.960 --> 47:30.520 Das wird man vielleicht nicht so für kleine Nachrichten machen, aber 47:30.520 --> 47:33.840 wenn ein Prozessor ein Gigabyte hat, das er an einen anderen schicken 47:33.840 --> 47:36.920 will, das wird man nicht zwischendurch im System irgendwie groß 47:36.920 --> 47:38.240 zwischenspeichern wollen oder so. 47:38.380 --> 47:42.320 Also manchmal ist es schon plausibel zu erwarten, der Empfänger muss 47:42.320 --> 47:45.760 auch zum richtigen Zeitpunkt aktiv was tun, vorher geht es auch für 47:45.760 --> 47:46.700 den Sender nicht weiter. 47:49.660 --> 47:52.900 Und deswegen muss man dann halt gucken, dass man dann so Programme so 47:52.900 --> 47:57.120 baut, dass die potenziellen Empfänger oft genug sozusagen in ihren 47:57.120 --> 47:58.340 Briefkasten gucken oder so. 48:00.280 --> 48:07.640 Und das ist aber vielleicht manchmal gar nicht so angenehm, weil das 48:07.640 --> 48:10.200 halt nicht so schön in den Programmfluss passt beim Empfänger 48:10.200 --> 48:11.040 möglicherweise. 48:15.210 --> 48:16.770 So, das ist das eine. 48:17.450 --> 48:22.090 Und das andere ist, also offensichtlich, man sagt immer ganz explizit, 48:22.170 --> 48:23.910 wer überträgt welche Daten wohin. 48:25.010 --> 48:26.270 Und vielleicht noch ein bisschen mehr. 48:29.090 --> 48:34.890 Also im Prinzip, das ist so, wie Sie das von MPI kennen. 48:36.290 --> 48:37.830 Wie ist das Programmierparadigmen? 48:37.950 --> 48:38.770 Wer hat das gehört? 48:39.310 --> 48:39.530 Schon. 48:41.330 --> 48:42.230 Wer nicht? 48:44.030 --> 48:44.550 Okay. 48:45.390 --> 48:45.590 Gut. 48:46.650 --> 48:49.950 Also, wer hat noch nie etwas von MPI gehört? 48:51.010 --> 48:52.590 Das sind dann ähnliche Mengen. 48:52.670 --> 48:53.130 Ja, okay. 48:55.510 --> 49:01.030 Also, da gibt es etwas, das heißt MPI und das unterstützt so eine Art 49:01.030 --> 49:01.750 zu programmieren. 49:02.730 --> 49:03.330 Gut. 49:07.540 --> 49:13.820 Ja, also Nachrichtenkopplung, alles von Hand machen, hat halt den 49:13.820 --> 49:16.800 Nachteil, man muss es von Hand machen und das ist unter Umständen 49:16.800 --> 49:19.320 Arbeit und vielleicht mehr, als einem lieb ist. 49:19.900 --> 49:23.440 Auf der anderen Seite kann man dann halt an vielen Stellen Einfluss 49:23.440 --> 49:26.720 nehmen und gucken, dass das möglichst effizient abläuft. 49:30.640 --> 49:34.440 Speicherkopplung hat aber auch so gewisse Probleme, also wenn Sie 49:34.440 --> 49:37.700 wirklich an große Maschinen denken und wie gesagt, große Maschinen 49:37.700 --> 49:41.100 heutzutage haben eine Million Cores oder so was. 49:42.480 --> 49:45.140 Oder vielleicht zehn, ich weiß nicht gerade, ich weiß nicht, was 49:45.140 --> 49:45.980 gerade so aktuell ist. 49:46.320 --> 49:47.880 Also, die sind schon richtig groß. 49:50.500 --> 49:57.000 Es ist schwierig, einen Speicher zu bauen, auf den eine Million Cores 49:57.000 --> 50:00.000 gleichzeitig irgendwie zugreifen können und irgendwie unabhängig 50:00.000 --> 50:01.580 voneinander etwas veranstalten können. 50:02.340 --> 50:05.280 Selbst wenn Sie nur, sagen wir mal, disjunkte Speicherbereiche lesen 50:05.280 --> 50:05.560 wollen. 50:06.580 --> 50:09.840 Ganz zu schweigen davon, was passiert ist, wenn die Speicherbereiche 50:09.840 --> 50:14.160 schreiben wollen und womöglich verschiedene Prozessoren an die gleiche 50:14.160 --> 50:15.040 Stelle schreiben wollen. 50:15.040 --> 50:16.400 Was dann? 50:17.620 --> 50:19.040 Muss man irgendetwas tun? 50:22.590 --> 50:25.050 Das kann man natürlich versuchen in den Griff zu kriegen, aber das 50:25.050 --> 50:28.910 kostet Hardware und zwar unter Umständen relativ viel. 50:29.490 --> 50:33.870 Deswegen, also so ganz ganz große Kisten, die haben einfach keinen 50:33.870 --> 50:34.810 globalen Speicher. 50:35.670 --> 50:38.150 Also, ich kenne überhaupt nichts in der Richtung. 50:38.930 --> 50:40.470 Der Speicher ist verteilt. 50:41.670 --> 50:45.830 Das ist vielleicht nicht so strikt, dass jeder Speicher nur von einer 50:45.830 --> 50:47.590 CPU zugegriffen werden kann. 50:49.170 --> 50:52.710 Aber es geht eher in diese Richtung, Zugriff von wenigen. 50:56.330 --> 50:57.470 So. 50:58.870 --> 51:05.130 Und deswegen, also wenn es einem wirklich darauf ankommt, dass das 51:05.130 --> 51:13.390 hinterher sehr effizient ist oder auf womöglich sehr unterschiedlichen 51:13.390 --> 51:18.570 Architekturen läuft, wozu man neigt, ist zu sagen, okay, wir entwerfen 51:18.570 --> 51:22.710 jetzt unseren Algorithmus erstmal so, dass wir wirklich explizit 51:22.710 --> 51:25.290 hinschreiben, wer mit wem wann kommuniziert. 51:26.790 --> 51:30.810 Dann hat man erstens einen großen Bereich abgedeckt und zweitens, 51:31.270 --> 51:35.970 naja, wenn es dann irgendwo mal an einer Stelle eine Situation gibt, 51:36.130 --> 51:41.090 wo das gar nicht so schlimm ist, also es sind dann nur auf einem 51:41.090 --> 51:46.030 Mainboard vier CPUs, jeder hat acht Cores und da stecken halt 16 51:46.030 --> 51:49.450 Speicherregel und jeder Core kann auf jeden Speicherregel zugreifen, 51:51.090 --> 51:54.650 dann guckt man halt da bei der Implementierung nochmal so ein bisschen 51:54.650 --> 51:59.250 genauer oder man hat eine Bibliothek, sowas wie MPI, die einem da 51:59.250 --> 52:00.450 vielleicht schon viel abgenommen hat. 52:00.450 --> 52:05.870 Und dann haben sie zwar in ihrem Programm irgendwie explizite 52:05.870 --> 52:10.350 Kommunikation hingeschrieben, aber es unten drunter wird schon 52:10.350 --> 52:13.770 ausgenutzt, dass mehrere auf den gleichen Speicher zugreifen können. 52:17.450 --> 52:22.170 Deswegen gucken wir uns jetzt auch erstmal Nachrichtengekoppelte 52:22.170 --> 52:23.170 Parallelrechner an. 52:24.570 --> 52:32.310 Und also was wir angucken werden, sind so einfache Algorithmen, somit 52:32.310 --> 52:35.570 das Komplizierteste, da kann man sich dann auch schon, werden Sie 52:35.570 --> 52:38.110 sehen, hinreichend viele Gedanken machen, ist sortieren. 52:38.950 --> 52:43.210 Und was wir aber dann für die Sortieralgorithmen zum Teil brauchen, so 52:43.210 --> 52:49.990 als Werkzeuge, sind so einfache Ritikel, vielleicht einfach nur so ein 52:49.990 --> 52:54.070 paar Daten verteilen oder so etwas, was Präfixsummen heißt, 52:54.170 --> 52:56.050 ausrechnen, solche Dinge. 52:56.770 --> 52:59.150 Und mit sowas wollen wir dann auch anfangen. 53:02.210 --> 53:02.690 Gut. 53:03.910 --> 53:07.170 Also Nachrichtengekoppelte Parallelrechner und dann will man natürlich 53:07.170 --> 53:10.150 sich auch immer angucken, wenn ich jetzt so einen Algorithmus habe für 53:10.150 --> 53:15.590 so einen Parallelrechner, also für so ein Modell entworfen habe, was 53:15.590 --> 53:17.730 erwarte ich denn so, wie schnell das so ist. 53:19.170 --> 53:20.970 Und wie viel schneller bin ich denn jetzt? 53:21.750 --> 53:25.750 Also irgendwie so Zeitersparnis steht schon oft im Vordergrund, ist 53:25.750 --> 53:27.290 aber nicht unbedingt das Einzige. 53:29.930 --> 53:34.010 Auch Energiesparen durchaus und ich weiß nicht, also bei Peter Sanders 53:34.010 --> 53:41.490 am Lehrstuhl, die machen ja auch viel Parallelverarbeitung und wenn 53:41.490 --> 53:44.810 ich das richtig im Kopf habe, also es gibt auch große Benchmarks und 53:44.810 --> 53:51.890 sozusagen Weltrekorde für Sortieren, aber auch verschiedene Kategorien 53:51.890 --> 53:54.430 von Sortieren, unter anderem Energiesparen sortieren. 53:55.510 --> 54:00.270 Und da haben die glaube ich, also zumindest waren sie glaube ich mal 54:00.270 --> 54:01.790 Weltmeister, vielleicht sind sie es immer noch. 54:02.770 --> 54:03.370 So. 54:04.370 --> 54:04.970 Also. 54:06.610 --> 54:08.890 Was stellen wir uns jetzt so ein bisschen genauer vor? 54:09.030 --> 54:13.630 Also wir haben Prozessoren, die irgendwie miteinander verbunden sind 54:13.630 --> 54:19.010 und das ist irgendwie schön gemacht, das ist eine Blackbox dieses 54:19.010 --> 54:20.770 Netzwerk, das gucken wir uns nicht genauer an. 54:20.770 --> 54:27.270 Jeder kann an jeden etwas schicken, kann einfach sagen, das soll jetzt 54:27.270 --> 54:30.190 zu jedem Prozessor geschickt werden und muss sich keine Gedanken 54:30.190 --> 54:32.910 darüber machen, auf welchem Weg ist das denn jetzt gerade möglich und 54:32.910 --> 54:34.270 was ist schnell und irgendetwas. 54:35.050 --> 54:39.750 Also jeder kann mit jedem kommunizieren und ich bin mir nicht ganz 54:39.750 --> 54:42.950 sicher, ob wir das bei einem Algorithmus vielleicht dann irgendwann 54:42.950 --> 54:43.550 mal brauchen. 54:45.130 --> 54:48.630 Stellen wir uns mal auf den Standpunkt, wenn Prozessor A an Prozessor 54:48.630 --> 54:52.210 B zwei Nachrichten schickt, dann die, die er zuerst abschickt, kommt 54:52.210 --> 54:52.970 auch zuerst an. 54:54.270 --> 54:59.010 Das ist keine absurde Forderung, das ist in der Praxis auch meistens 54:59.010 --> 55:03.050 sowieso so und so Bibliotheken wie MPI versprechen Ihnen das dann 55:03.050 --> 55:03.270 auch. 55:04.270 --> 55:07.350 Da müssen Sie ein bisschen genauer lesen, was genau versprochen wird, 55:07.530 --> 55:12.090 dann kommen da noch mehr dazu, aber das ist eine plausible Annahme. 55:12.610 --> 55:17.070 Und wir stellen uns mal auf den Standpunkt, dieses Netzwerk ist so und 55:17.070 --> 55:21.910 die Netzwerkanschlüsse und die CPU, jeder Prozessor kann immer 55:21.910 --> 55:27.330 gleichzeitig, also kann etwas schicken, kann etwas empfangen und kann 55:27.330 --> 55:30.250 auch das gleichzeitig eins wegschicken und eins empfangen. 55:31.030 --> 55:33.850 Einmal senden, einmal empfangen gleichzeitig, das soll auch gehen. 55:35.090 --> 55:38.050 Das ist manchmal ein bisschen bequemer hinzuschreiben, ansonsten 55:38.050 --> 55:39.690 kostet es halt auch nur einen Faktor zwei. 55:43.630 --> 55:49.170 Also gehen wir davon aus, dass wir so Funktionen haben wie send und 55:49.170 --> 55:51.970 mit zwei Parametern, was wollen wir wegschicken und an wen? 55:52.650 --> 55:57.310 Und receive, da ist ein Parameter zu viel. 55:59.930 --> 56:03.590 Receive soll nur einen Parameter haben, von wem wollen wir empfangen, 56:03.710 --> 56:07.390 also das soll man sagen können, ich möchte jetzt vom Prozessor 17 was 56:07.390 --> 56:09.830 empfangen und da kommt da eben die Antwort raus. 56:10.130 --> 56:13.790 Und diesen ersten Parameter, der da noch steht, hinter dem Receive, 56:13.890 --> 56:16.950 den stellen Sie sich bitte gelöscht vor. 56:19.290 --> 56:23.090 Oder eben beides gleichzeitig und damit man dann nicht im Programm das 56:23.090 --> 56:26.190 doch sequenziell in der einen oder in der anderen Reihenfolge 56:26.190 --> 56:33.450 hinschreibt, was vielleicht schlecht ist, wollen wir uns vorstellen, 56:33.530 --> 56:37.010 man hat noch eine Funktion, da kann man sagen, also hier, ich habe 56:37.010 --> 56:40.710 eine Nachricht, die soll gesendet werden und das ist der Empfänger und 56:40.710 --> 56:43.310 ich möchte auch gleichzeitig noch etwas empfangen und das ist der 56:43.310 --> 56:46.930 Sender und raus plumpst die Nachricht, die man empfangen hat. 56:50.480 --> 56:53.160 Und im Wesentlichen darauf möchte ich mich hier beschränken. 56:53.260 --> 56:55.820 Ich weiß nicht, die, die MPI kennen werden, wissen, na da kann man 56:55.820 --> 57:01.260 noch viel mehr nachdenken, zum Beispiel, wenn ein Prozess Send 57:01.260 --> 57:06.920 aufruft, ja was ist denn, wenn da keiner ist, also wenn der Empfänger 57:06.920 --> 57:12.640 gerade nichts tut, was anderes tut, nichts empfängt, das Send, ist das 57:12.640 --> 57:17.360 nach endlicher Zeit zu Ende oder hängt man da jetzt, bis der Empfänger 57:17.360 --> 57:20.080 geneigt ist, die Nachricht entgegenzunehmen? 57:23.080 --> 57:27.380 In MPI typischerweise ist es so, kleine Nachrichten, ist egal, was der 57:27.380 --> 57:30.040 Empfänger gerade macht, werden halt im Zweifelsfall 57:30.040 --> 57:34.040 zwischengespeichert irgendwo, große Nachrichten halt nicht. 57:35.520 --> 57:38.440 Und bei einer großen Nachricht hängen sie dann, es sei denn, sie 57:38.440 --> 57:43.440 benutzen eine Variante von Send, wo explizit ein Buffer dahinterhängt, 57:43.520 --> 57:45.300 wo das erstmal hingkopiert wird oder so, ja. 57:52.300 --> 57:55.960 Aber unsere Algorithmen sind alle so harmlos, da muss man sich darüber 57:55.960 --> 57:56.960 keine Gedanken machen. 57:58.760 --> 58:02.280 Da ist es im Zweifelsfall auch so, wenn einer sendet, also das kann 58:02.280 --> 58:04.740 man dann so hinschreiben, dass dann auch irgendwie klar ist, ah da ist 58:04.740 --> 58:07.500 auch ein Empfänger, der das im Zweifelsfall gleich abnehmen würde. 58:10.040 --> 58:10.480 Gut. 58:14.180 --> 58:17.860 Ja und dann ist die Frage, wie lange dauert das denn jetzt, irgendwie 58:17.860 --> 58:18.980 Daten zu übertragen? 58:20.800 --> 58:25.900 Und eine nützliche Näherung ist die, die hier steht. 58:26.900 --> 58:31.300 Senden oder Empfangen von L-Bytes dauert eine Zeit, die setzt sich 58:31.300 --> 58:35.200 zusammen aus einem konstanten additiven Term, der heißt hier T-Start, 58:36.420 --> 58:39.800 plus einer Zeit, die ist proportional zur Anzahl Bytes, die man 58:39.800 --> 58:45.280 verschicken will, also L mal eine Standardzeit, Einheitszeit T-Byte, 58:45.340 --> 58:48.260 die man halt warten muss, um einen Byte zu verschicken. 58:49.620 --> 58:52.560 Und wenn Sie das in der Praxis irgendwie mal so ein bisschen 58:52.560 --> 58:55.660 rummessen, dann stellen Sie fest, ja das ist typischerweise so. 58:58.880 --> 59:02.460 In der Praxis ist auch typischerweise die Zeit, um einen Byte zu 59:02.460 --> 59:08.300 verschicken, deutlich kleiner, viel kleiner als diese Startup-Zeit, wo 59:08.300 --> 59:12.600 so Dinge drin sind, wie, also wenn Sie das jetzt wirklich real machen, 59:12.820 --> 59:16.640 Sie rufen MPI Send auf, ja da rufen Sie eine Funktion auf, die guckt, 59:16.780 --> 59:19.620 ob irgendwelche Parameter, irgendwelche legalen Werte haben, in 59:19.620 --> 59:21.220 irgendwelchen Bereichen oder was weiß ich. 59:21.780 --> 59:24.460 Und da passiert dieses und jenes, das dauert halt alles ein bisschen. 59:25.980 --> 59:28.740 Und diesen konstanten Overhead, den sehen Sie halt immer. 59:29.440 --> 59:35.460 Was bei dieser Formel hier ignoriert wird, ist sozusagen sowas wie, 59:35.560 --> 59:38.360 wie weit sind Sender und Empfänger voneinander entfernt. 59:40.380 --> 59:47.700 Und wenn Sie so Messungen machen, ja, für 1, 2, 4, 8, 16 Byte bis 4 59:47.700 --> 59:52.020 Gigabyte in der Praxis, dann merken Sie schon, oh, wenn Sender und 59:52.020 --> 59:55.240 Empfänger zwei Cores auf der gleichen CPU auf dem gleichen Mainboard 59:55.240 --> 01:00:00.980 sind, dann geht das viel schneller, als wenn das zwei Cores auf zwei 01:00:00.980 --> 01:00:03.340 verschiedenen CPUs auf dem gleichen Mainboard sind. 01:00:04.100 --> 01:00:08.080 Und noch langsamer wird es, wenn das zwei Cores in zwei CPUs auf 01:00:08.080 --> 01:00:10.340 verschiedenen Mainboards sind, womöglich in verschiedenen Schränken. 01:00:10.960 --> 01:00:17.600 Also, in jedem Fall, man sieht so ein Verhalten, aber, also, grob 01:00:17.600 --> 01:00:20.960 gesagt, T-Byte jedenfalls variiert schon. 01:00:22.760 --> 01:00:26.500 Bleiben Sie innerhalb der CPU oder bleiben Sie wenigstens auf dem 01:00:26.500 --> 01:00:30.120 Mainboard oder wenigstens im Schaltschrank oder wo geht das hin, ja. 01:00:31.140 --> 01:00:32.740 Davon ignorieren wir mal. 01:00:34.520 --> 01:00:35.800 Ist die Frage, warum. 01:00:36.560 --> 01:00:38.500 Also, erstens macht es natürlich die Sachen bequemer. 01:00:39.580 --> 01:00:46.060 Und zweitens, also, wenn man im Kopf hat, große Anzahlen von 01:00:46.060 --> 01:00:50.320 Prozessoren, dann ist eben das wenigste on Chip oder auf dem gleichen 01:00:50.320 --> 01:00:55.220 Mainboard und dann, in den meisten Fällen, also dann dominiert halt 01:00:55.220 --> 01:00:58.000 das größere T-Byte, ne. 01:01:01.740 --> 01:01:05.320 Also, wann immer wir irgendwann anfangen darüber nachzudenken, was 01:01:05.320 --> 01:01:09.280 kostet es, irgendwie eine Anzahl Bytes von A nach B zu transportieren, 01:01:10.280 --> 01:01:11.580 stellen sich sowas vor. 01:01:13.820 --> 01:01:14.220 So. 01:01:15.180 --> 01:01:18.600 Und dann ist jetzt die Frage noch, ja, wie programmiert man so ein 01:01:18.600 --> 01:01:18.800 Ding. 01:01:21.940 --> 01:01:25.980 Und was sich als ganz praktisch erwiesen hat, ist dieses Konzept 01:01:25.980 --> 01:01:27.760 Single Program Multiple Data. 01:01:27.980 --> 01:01:36.500 Das heißt, man schreibt ein Programm, übersetzt das und, ja, wenn man 01:01:36.500 --> 01:01:40.640 es sich erlauben kann, halt interaktiv sagt dann, ja, dieses Programm 01:01:40.640 --> 01:01:44.420 jetzt bitte starten auf 32 CPUs oder man gibt es halt ein Batch 01:01:44.420 --> 01:01:45.080 System, ne. 01:01:45.080 --> 01:01:49.300 Also, wenn man 1.000 CPUs will, die stehen wahrscheinlich nicht gerade 01:01:49.300 --> 01:01:50.180 so online zur Verfügung. 01:01:54.750 --> 01:01:58.930 Wenn Sie auf Rechnern wie im Rechenzentrum, auf Parallelrechnern 01:01:58.930 --> 01:02:03.270 arbeiten, typischerweise eben also so für moderate Zahlen zum Testen, 01:02:03.330 --> 01:02:05.530 können Sie das einfach direkt online machen, allerdings müssen Sie 01:02:05.530 --> 01:02:06.670 auch im Clan drüber sein. 01:02:06.670 --> 01:02:10.350 Die CPUs, die Sie dann kriegen, die haben Sie nicht exklusiv für sich, 01:02:10.730 --> 01:02:12.950 sondern da sind halt alle am rumturnen. 01:02:13.810 --> 01:02:17.030 Wenn Sie einen Job ins Batch System geben und das läuft dann irgendwie 01:02:17.030 --> 01:02:20.850 nachts um drei los, dann kriegen Sie halt 32 CPUs und die haben Sie 01:02:20.850 --> 01:02:21.650 dann nur für sich. 01:02:22.510 --> 01:02:23.970 Das sind keine anderen Benutzer. 01:02:24.790 --> 01:02:25.970 Das Betriebssystem schon noch. 01:02:27.230 --> 01:02:31.370 Und das Betriebssystem kann übrigens auch vereinzelt Ärger bereiten, 01:02:31.990 --> 01:02:33.150 aber gut. 01:02:34.170 --> 01:02:35.350 Lassen wir mal weg. 01:02:37.110 --> 01:02:40.770 So, also man schreibt ein Programm und das gleiche Programm wird von 01:02:40.770 --> 01:02:44.550 allen abgearbeitet und dann braucht man als allererstes ein 01:02:44.550 --> 01:02:49.110 Hilfsmittel, um sicherstellen zu können, dass nicht garantiert alle 01:02:49.110 --> 01:02:51.750 Prozessoren exakt das gleiche von vorne bis hinten berechnen. 01:02:51.830 --> 01:02:53.110 Damit kann man sich sparen, ja. 01:02:53.110 --> 01:02:56.510 Also die müssen sich dann schon irgendwie unterscheiden können und 01:02:56.510 --> 01:03:01.290 stellen sich vor, es gibt da also irgendwie Funktionen, meinetwegen 01:03:01.290 --> 01:03:04.950 eine, um nachzufragen, wie viele sind wir denn jetzt gerade? 01:03:05.090 --> 01:03:07.910 Also im Idealfall, Sie schreiben Ihr Programm so. 01:03:09.250 --> 01:03:14.810 Das funktioniert immer, egal ob Sie es auf 2 oder auf 16 oder auf 2 01:03:14.810 --> 01:03:18.370 hoch 16 Prozessoren laufen lassen und es funktioniert hoffentlich 01:03:18.370 --> 01:03:21.210 sogar, wenn Sie es nur auf einem Prozessor laufen lassen. 01:03:21.330 --> 01:03:25.010 Das ist dann nicht sehr parallel, aber im schönen Fall funktioniert 01:03:25.010 --> 01:03:25.750 auch das noch. 01:03:27.230 --> 01:03:31.190 Da muss man dann manchmal ein bisschen aufpassen, denn wenn da in 01:03:31.190 --> 01:03:34.810 seinem Programm sowas wie Nachrichten schicken und empfangen steht, 01:03:35.210 --> 01:03:38.030 dann kann man ja, wenn man alleine ist, nur an sich selbst schicken 01:03:38.030 --> 01:03:41.350 und dann muss man gucken, dass das auch wirklich funktioniert. 01:03:41.350 --> 01:03:44.030 Dass man nicht sagt, ich möchte was wegschicken und der Empfänger 01:03:44.030 --> 01:03:48.490 empfängt aber nicht, weil er der Sender ist und immer noch darauf 01:03:48.490 --> 01:03:50.410 wartet, dass der Empfänger es abnimmt. 01:03:51.430 --> 01:03:55.090 Also da kann man leicht einen kleinen Fehler machen. 01:03:56.530 --> 01:03:57.050 Gut. 01:03:58.170 --> 01:04:02.390 Also, ohne dass wir das jetzt immer noch explizit hinschreiben, also 01:04:02.390 --> 01:04:06.830 stellen wir uns vor, ein Programm kann nachfragen, auf wie vielen 01:04:06.830 --> 01:04:10.870 Prozessoren laufe ich denn und jeder Prozess kann nachfragen, okay, 01:04:11.310 --> 01:04:14.470 wir sind insgesamt p Stück, der wievielte bin ich denn? 01:04:15.230 --> 01:04:19.930 Und dann gibt es eben so eine Funktion, also in MPI heißt das dann der 01:04:19.930 --> 01:04:22.690 Rang in irgendeinem sogenannten Kommunikator, ist egal. 01:04:24.230 --> 01:04:29.270 Und wenn das eben alle ausführen, so einen Aufruf von der wievielte 01:04:29.270 --> 01:04:33.110 bin ich denn, dann kriegen eben die verschiedenen Prozesse, die da 01:04:33.110 --> 01:04:34.930 gleichzeitig laufen, verschiedene Zahlen zurück. 01:04:34.930 --> 01:04:39.570 Einer kriegt gesagt, du bist 0, 1, 2, 3, p-1. 01:04:40.210 --> 01:04:42.970 Und dann sind die verschieden und dann können sie, wenn sie wollen, 01:04:43.010 --> 01:04:46.390 ein großes if machen und wenn 0, dann mache ich Wettervorhersage, wenn 01:04:46.390 --> 01:04:48.930 1, spiele ich Lotto, keine Ahnung. 01:04:52.730 --> 01:04:56.790 Also so triviales Hello World, dann jeder sagt, ja ich bin Nummer 01:04:56.790 --> 01:05:00.730 sowieso von insgesamt so und so vielen, das ist so das Standard Hello 01:05:00.730 --> 01:05:03.170 World Programm, das man auch als erstes bei MPI macht. 01:05:05.190 --> 01:05:09.230 Und was man da dann gleich lernt ist, natürlich die Ausgaben kommen in 01:05:09.230 --> 01:05:13.310 irgendeiner Reihenfolge, wenn es gut läuft, also vorausgesetzt alle 01:05:13.310 --> 01:05:16.970 können Ausgabe machen, und wenn es gut läuft, kommen immer 01:05:16.970 --> 01:05:20.390 vollständige Zeilen nur von einer CPU, von einem Prozess. 01:05:22.490 --> 01:05:26.770 Und nicht so ein paar Byte von einem, dann dazwischen ein paar Byte 01:05:26.770 --> 01:05:29.550 von einem anderen und so in einem Ausgabestrom, das ist natürlich 01:05:29.550 --> 01:05:30.330 hässlich sowas. 01:05:31.310 --> 01:05:34.090 Gut, also das ist die Idee. 01:05:34.890 --> 01:05:39.410 Ein Programm schreiben und stellen sich jetzt immer vor, am Anfang, 01:05:39.490 --> 01:05:43.510 jeder kann nachfragen, im Zweifelsfalle, der wievielte bin ich von wie 01:05:43.510 --> 01:05:47.370 vielen, also jeder weiß dann, ich bin Nummer i und insgesamt gibt es p 01:05:47.370 --> 01:05:50.650 und stellen wir uns vor, die Nummern gehen von 0 bis p-1. 01:05:50.650 --> 01:05:57.050 So, und dann fangen wir jetzt mal langsam an, was auszurechnen. 01:06:02.090 --> 01:06:06.390 Stellen Sie sich vor, Sie haben eine binäre, assoziative Operation auf 01:06:06.390 --> 01:06:06.850 einer Menge. 01:06:08.050 --> 01:06:11.330 Also binär ist klar, man hat halt zwei Operanten. 01:06:12.290 --> 01:06:15.350 Assoziativ heißt, Sie können klammern wie Sie wollen, es kommt immer 01:06:15.350 --> 01:06:19.730 das gleiche raus, wenn Sie größere Ausdrücke haben. 01:06:22.170 --> 01:06:27.090 Also, das kann sowas sein, wie zwei Zahlen addieren oder das Minimum 01:06:27.090 --> 01:06:28.470 von zwei Werten ausrechnen. 01:06:28.990 --> 01:06:31.370 Das kann aber auch sowas sein, das sieht jetzt ein bisschen albern 01:06:31.370 --> 01:06:37.330 aus, x verknüpft mit y ist x oder x verknüpft mit y ist y. 01:06:40.110 --> 01:06:43.990 Warum das vielleicht so nebenbei auch ganz interessant ist, sehen Sie 01:06:43.990 --> 01:06:44.690 hinterher. 01:06:45.990 --> 01:06:50.970 So, und was man dann gerne möchte, wenn man eine Liste von n Werten 01:06:50.970 --> 01:06:56.830 hat, x0 bis xp-1 und wir machen es uns jetzt am Anfang ganz einfach, 01:06:56.990 --> 01:06:59.710 wir stellen uns vor, wir sind ganz reich für jedes Element, wir haben 01:06:59.710 --> 01:07:00.790 einen eigenen Prozessor. 01:07:01.990 --> 01:07:05.110 Das ist insbesondere, wenn Sie Gigabytes sortieren wollen, 01:07:05.210 --> 01:07:08.870 typischerweise nicht der Fall, aber tun wir erst mal so. 01:07:10.150 --> 01:07:15.770 Was Sie dann gerne möchten ist, alle diese Werte miteinander 01:07:15.770 --> 01:07:19.110 verknüpft, diesen Ausdruck ausgewertet. 01:07:24.240 --> 01:07:36.860 Und also wir haben hier ein x0 und ein x1, x2, x3 und dann die alle 01:07:36.860 --> 01:07:38.400 miteinander verknüpft. 01:07:43.410 --> 01:07:47.730 Und weil die Operation ja assoziativ ist, muss ich keine Klammern 01:07:47.730 --> 01:07:50.030 hinmalen, egal wie ich die Klammern mache, es kommt ja immer das 01:07:50.030 --> 01:07:50.610 gleiche raus. 01:07:50.610 --> 01:07:50.770 So. 01:07:53.310 --> 01:07:54.150 Gut. 01:07:56.170 --> 01:08:02.770 Und das jetzt, jetzt haben wir aber diese Werte jetzt verteilt auf 6 01:08:02.770 --> 01:08:04.350 CPUs, 6 Prozessoren. 01:08:06.470 --> 01:08:09.650 Und wollen da möglichst schnell zum Ziel kommen. 01:08:11.730 --> 01:08:16.890 Haben Sie einen Vorschlag, was man da tun könnte, tendenziell? 01:08:20.530 --> 01:08:24.030 Also ich sag Ihnen mal eine langsame Methode, jeder schickt seinen 01:08:24.030 --> 01:08:27.550 Wert an Prozessor 0 und der addiert die alle auf, eins nach dem 01:08:27.550 --> 01:08:27.870 anderen. 01:08:29.730 --> 01:08:31.230 Haben Sie was schnelleres? 01:08:33.170 --> 01:08:35.110 Oder ist das zu banal, weiß ich nicht. 01:08:37.250 --> 01:08:40.770 Wer hat denn eigentlich schon mal irgendwann irgendetwas, irgendein 01:08:40.770 --> 01:08:43.550 Programm geschrieben, wo dann irgendwas parallel verarbeitet wurde? 01:08:45.750 --> 01:08:46.830 Ah ja, doch einige. 01:08:47.010 --> 01:08:49.370 Okay, dann für die ist es wahrscheinlich ein bisschen zu albern. 01:08:51.890 --> 01:08:54.610 Also wie kann man schneller werden, indem man halt möglichst viele von 01:08:54.610 --> 01:08:56.950 diesen Operationen gleichzeitig ausführt, ne? 01:08:59.090 --> 01:09:03.610 Und dann könnte man zum Beispiel sagen, na gut, X0 und X1 verknüpfen, 01:09:05.350 --> 01:09:08.170 X2 und X3 verknüpfen, X4 und X5. 01:09:08.750 --> 01:09:11.350 Da hat ja das eine mit dem anderen nichts zu tun, das kann man 01:09:11.350 --> 01:09:12.710 versuchen gleichzeitig hinzukriegen. 01:09:16.760 --> 01:09:21.060 Und dann noch, ja, hier vorne die beiden. 01:09:21.720 --> 01:09:26.260 Und es könnte ja sein, dass man hier auch noch X6 und X7 hat. 01:09:26.760 --> 01:09:27.760 Dann könnte man die noch. 01:09:28.440 --> 01:09:33.260 Und dann zu guter Letzt hier den einen Operator in der Mitte 01:09:33.260 --> 01:09:34.140 auswerten, ne? 01:09:37.540 --> 01:09:41.840 Ja, das ist jetzt hier nochmal so ein bisschen hingeschrieben. 01:09:47.460 --> 01:09:51.740 Der Einfachheit halber stellen wir uns vor, die Anzahl der Elemente 01:09:51.740 --> 01:09:55.000 der Prozesse ist eine Zweierprotenz, ja? 01:09:56.100 --> 01:10:00.640 Dann also wäre die Idee, die Verknüpfung von allen P-Elementen 01:10:00.640 --> 01:10:02.440 auszuwerten, ist rekursiv. 01:10:03.200 --> 01:10:05.820 Man macht das für die erste Hälfte und für die zweite Hälfte hat man 01:10:05.820 --> 01:10:08.220 noch zwei Werte und die verknüpft man dann noch. 01:10:08.800 --> 01:10:11.460 Und da ist wieder ein kleiner Tippfehler, also hier dieses Plus, das 01:10:11.460 --> 01:10:15.820 soll natürlich dieses Operationssymbol sein, ne? 01:10:18.900 --> 01:10:22.840 Und das führt dann genau zu dem, was wir da gerade gesehen haben. 01:10:24.020 --> 01:10:29.500 Also erstmal, die beiden werden verknüpft, die beiden werden zu einem 01:10:29.500 --> 01:10:33.140 Wert verknüpft, die beiden und die beiden. 01:10:36.130 --> 01:10:41.390 Und was man dann kriegt, wie man sieht, ist ein Baum, ja? 01:10:41.810 --> 01:10:44.370 Und da kommt dann hier der Wert raus, den man haben will. 01:10:50.270 --> 01:10:50.330 So. 01:10:55.130 --> 01:10:59.150 Naja und wenn Sie da, also im schönen Fall, die Anzahl Elemente ist 01:10:59.150 --> 01:11:00.730 eine Zweierprotenz jedenfalls. 01:11:02.350 --> 01:11:05.570 Das ist ein balancierter binärer Baum. 01:11:06.930 --> 01:11:13.450 Da haben Sie so viele Ebenen mit Operationssymbolen wie Logarithmus 01:11:13.450 --> 01:11:16.530 von Anzahl Elemente. 01:11:19.510 --> 01:11:23.630 Und das ist das, was hier auch behauptet wird, also wenn Sie die P 01:11:23.630 --> 01:11:27.030 -Elemente schön verteilt haben auf P-Prozessoren, dann können Sie das 01:11:27.030 --> 01:11:30.250 in logarithmischer Zeit ausrechnen und den Wert zum Beispiel auf 01:11:30.250 --> 01:11:31.890 Prozessor 0 haben. 01:11:36.910 --> 01:11:43.950 Und das ist jetzt nochmal das Bild so etwas verändert als Programm 01:11:43.950 --> 01:11:44.690 hingeschrieben. 01:11:50.130 --> 01:11:53.130 Und zwar, na da müssen wir doch nochmal das Bild angucken. 01:11:58.160 --> 01:12:02.480 Also meinetwegen hier dieses x0, ich sag mal einfach plus x1, das muss 01:12:02.480 --> 01:12:04.120 ja irgendwo ausgerechnet werden. 01:12:04.860 --> 01:12:11.360 Und stellen wir uns mal vor, das würde bei Prozess 0 ablaufen sollen. 01:12:11.800 --> 01:12:15.140 Dann wird also hier x1 zu 0 geschickt werden sollen. 01:12:15.140 --> 01:12:16.280 Hier das macht 0. 01:12:17.480 --> 01:12:19.600 Und hier das macht 2. 01:12:19.780 --> 01:12:23.020 Da muss also der 3 das an 2 schicken. 01:12:24.060 --> 01:12:26.400 Und 5 muss das an 4 schicken. 01:12:28.320 --> 01:12:30.600 Und sie muss das an 6 schicken. 01:12:32.020 --> 01:12:37.960 Und danach sind 1, 3, 5, 7 arbeitslos. 01:12:38.080 --> 01:12:39.000 Die haben nichts mehr zu tun. 01:12:39.580 --> 01:12:42.180 Der Rest wird von den anderen erledigt. 01:12:42.660 --> 01:12:45.480 Da kommt also hier irgendwas raus, x2 plus x3. 01:12:45.560 --> 01:12:48.120 Und da stellen wir uns vor, das wird zu 0 geschickt. 01:12:48.720 --> 01:12:52.880 Und hier kommt irgendwas raus, das wird zu 4 geschickt. 01:12:53.880 --> 01:12:57.820 Und dann kommt hier was raus und das wird zu 0 geschickt. 01:12:58.220 --> 01:13:00.380 Und dann haben wir auf 0 hier das Ergebnis. 01:13:02.760 --> 01:13:07.780 Also die mit den Nummern 1, 3, 5, 7, die das niedrigste Bit 1 haben, 01:13:07.820 --> 01:13:11.920 wenn sich die Nummern dual dargestellt vorstellen, die schicken das an 01:13:11.920 --> 01:13:15.540 ihr Pendant, die hinten als letztes Bit eine 0 haben und dann sind sie 01:13:15.540 --> 01:13:16.080 fertig. 01:13:17.220 --> 01:13:24.540 Dann sind nur noch 4 aktiv, von denen 2 und 6, jetzt das Ganze 01:13:24.540 --> 01:13:26.860 sozusagen das nächste Bit angeguckt von hinten. 01:13:27.600 --> 01:13:32.980 Beim vorletzten Bit, die, die da eine 1 haben, 2 und 6, schicken das 01:13:32.980 --> 01:13:36.560 an den, der da eine 0 hat, 4 und 0. 01:13:37.240 --> 01:13:38.920 Und dann sind die fertig. 01:13:40.060 --> 01:13:44.300 Aktiv sind dann nur noch die, die die letzten 2 Bits 0 haben. 01:13:45.100 --> 01:13:49.160 Es sind immer weniger aktiv, nur noch die mit Nummern, die hinten 01:13:49.160 --> 01:13:50.140 immer mehr Bits 0. 01:13:51.820 --> 01:13:54.020 Und irgendwann ist halt nur noch einer aktiv. 01:13:55.440 --> 01:13:57.380 Und das ist das, was Sie hier auch in dem Code sehen. 01:13:57.380 --> 01:14:01.780 Also da steht jetzt explizit mal noch dieses Aktiv-Bit, am Anfang 01:14:01.780 --> 01:14:02.080 alle. 01:14:04.980 --> 01:14:09.260 Und man summiert irgendwie auf und initialisiert für alle. 01:14:09.680 --> 01:14:11.080 Das ist ein Programm, das machen alle. 01:14:12.320 --> 01:14:14.300 Initialisiert mit dem eigenen Wert xi. 01:14:16.220 --> 01:14:20.880 Und dann geht man eben, macht man den Baum sozusagen durch, von 0 bis 01:14:20.880 --> 01:14:24.220 Log p abgerundet reicht. 01:14:26.340 --> 01:14:30.240 Muss man sich einfach so die Grenzfälle, Beispiel 7, 8, 9 mal 01:14:30.240 --> 01:14:33.660 angucken, ob man da noch p aufrunden, abrunden, wieviel man da machen 01:14:33.660 --> 01:14:33.900 muss. 01:14:35.000 --> 01:14:39.700 So, die noch aktiv sind, gucken, was ist jetzt das Karte-Bit von 01:14:39.700 --> 01:14:40.100 hinten. 01:14:41.200 --> 01:14:42.560 Ist das eine 0 oder eine 1? 01:14:43.120 --> 01:14:48.160 Und wenn es eine 1 ist, dann schicken sie das, was sie bisher als 01:14:48.160 --> 01:14:53.440 Summe hatten, an den Prozess, dessen Nummer an der Stelle nicht eine 01:14:53.440 --> 01:14:54.680 1, sondern eine 0 hat. 01:14:54.780 --> 01:14:57.940 Also dann nehmen sie die eigene Nummer i und ziehen 2 hoch k ab. 01:14:58.500 --> 01:15:02.060 Das ist das Pardon mit der Nummer 0 als Karte-Bit. 01:15:03.480 --> 01:15:06.020 Und dann sagen wir, okay, ich bin fertig mit der Arbeit. 01:15:06.700 --> 01:15:08.280 Ich habe weggeschickt. 01:15:08.500 --> 01:15:09.360 Ich muss nichts mehr tun. 01:15:09.360 --> 01:15:11.440 Dann setzen sie das Aktiv-Bit auf 0. 01:15:12.800 --> 01:15:17.360 So, und die anderen, die also da als Gratis-Bit eine 0 haben, gucken, 01:15:18.320 --> 01:15:20.940 und das ist jetzt hier so formuliert, damit das auch für Nicht 01:15:20.940 --> 01:15:27.380 -Zweierpotenzen schön funktioniert, der, der an der Kartenstelle eine 01:15:27.380 --> 01:15:30.360 1 hat, ist das eine Nummer, die auch noch mitspielt? 01:15:30.540 --> 01:15:34.220 Und wenn ja, dann empfange ich von dem den Wert, den er mir schickt. 01:15:35.480 --> 01:15:38.700 Und die beiden addiere ich, und das ist mein neuer Summenwert. 01:15:40.280 --> 01:15:41.980 Ja, und dann eben weiter mit dem nächsten Bit. 01:15:43.440 --> 01:15:49.000 Und in jeder Runde, alle die, die an der Kartenstelle von hinten noch 01:15:49.000 --> 01:15:52.880 ein 1-Bit haben in ihrer Adresse, schicken noch was weg und sind dann 01:15:52.880 --> 01:15:53.260 raus. 01:15:53.920 --> 01:15:58.020 Das heißt, also die Anzahl Aktiver wird immer weniger, und am Ende 01:15:58.020 --> 01:16:01.660 haben sie wirklich nur noch einen übrig, der das Ergebnis liefert. 01:16:03.220 --> 01:16:08.320 Und wie Sie hier sehen, kann man auch nochmal überlegen, zu jedem 01:16:08.320 --> 01:16:13.600 Cent, es gibt ein Receive, und es ist auch irgendwie klar. 01:16:14.500 --> 01:16:20.600 Also, und stellen Sie sich vor, dass das irgendwie, genau, also das 01:16:20.600 --> 01:16:22.020 müssen Sie sich natürlich vorstellen. 01:16:23.340 --> 01:16:26.940 Nehmen wir mal an, man hat keine Garantien, wie schnell die CPUs sind, 01:16:27.020 --> 01:16:29.140 vielleicht sind verschiedene CPUs unterschiedlich schnell. 01:16:29.140 --> 01:16:36.020 Also, dieses Receive, das sollte also warten, bis was kommt, und dann 01:16:36.020 --> 01:16:39.380 eben den Wert hier reinschreiben und nicht sagen, Receive, hier ist 01:16:39.380 --> 01:16:42.480 aber noch nichts, Summstrich ist 0 oder sowas. 01:16:43.120 --> 01:16:50.020 Das ist nicht die Vorstellung, sondern, wie bei MPI, Receive wartet, 01:16:50.200 --> 01:16:50.920 bis was da ist. 01:16:51.000 --> 01:16:54.200 Und es ist auch klar, dass dann nur von einem was kommen kann, da kann 01:16:54.200 --> 01:16:55.360 nichts durcheinander gehen. 01:16:56.680 --> 01:16:58.220 Alles ist gut, ja? 01:16:58.880 --> 01:17:00.220 Nachrichten überholen sich nicht. 01:17:00.980 --> 01:17:02.980 Jeder kriegt immer das Richtige geliefert. 01:17:04.140 --> 01:17:07.060 Und am Ende haben Sie bei Prozess 0 alles da. 01:17:12.120 --> 01:17:15.980 Und wenn diese binäre Operation zum Beispiel Minimum ist, dann haben 01:17:15.980 --> 01:17:19.320 Sie eben am Ende das Minimum von allen bei Prozess 0. 01:17:20.640 --> 01:17:27.100 Und wenn die Operation, die Ihnen als Ergebnis das erste Argument 01:17:27.100 --> 01:17:30.440 liefert, naja gut, dann haben Sie am Ende auch das Argument von 01:17:30.440 --> 01:17:32.020 Prozessor 0 bei Prozessor 0. 01:17:32.740 --> 01:17:36.360 Wenn Sie die Operation haben, die das zweite Argument liefert, dann 01:17:36.360 --> 01:17:40.920 haben Sie am Ende bei 0 das, was am Anfang Prozessor P-1 hatte. 01:17:41.560 --> 01:17:43.860 Das klingt jetzt alles noch nicht so aufregend, ja? 01:17:45.500 --> 01:17:48.920 Aber wir werden das gleich benutzen in etwas komplizierterem. 01:17:51.000 --> 01:17:51.420 Gut. 01:17:52.840 --> 01:17:56.660 Bevor wir das tun, vielleicht noch kurz so eine Überlegung, ja, was 01:17:56.660 --> 01:17:57.600 haben wir denn jetzt gewonnen? 01:17:58.180 --> 01:18:03.860 Also wenn wir n Elemente auf, ich sag mal einfach aufaddieren wollen. 01:18:05.140 --> 01:18:07.660 Und wir haben für jedes Element einen Prozessor. 01:18:08.760 --> 01:18:11.340 Ach so, nee, erst mal, wenn wir nur einen Prozessor haben, wenn Sie es 01:18:11.340 --> 01:18:15.760 auf einen machen, n Elemente addieren, dann sagen wir mal ja auch 01:18:15.760 --> 01:18:19.440 offensichtlich, es gibt nichts besseres als halt n-1 von diesen 01:18:19.440 --> 01:18:20.820 Operationen auszuführen. 01:18:22.600 --> 01:18:26.780 Macht also Laufzeit größenordnungsmäßig Theta von n. 01:18:31.160 --> 01:18:34.360 Jetzt hier in unserem Beispiel mit den Bäumen. 01:18:35.940 --> 01:18:40.240 Behauptung, also wenn Sie tatsächlich n Elemente, n Prozessoren haben 01:18:40.240 --> 01:18:42.960 für die n Elemente, die Laufzeit ist log n. 01:18:45.180 --> 01:18:53.700 Naja, also es sieht so aus, als wäre 0 der, der das meiste zu tun hat. 01:18:54.480 --> 01:18:56.600 Das kann man sich natürlich auch ein bisschen ordentlicher überlegen, 01:18:56.800 --> 01:18:58.040 aber gucken wir mal auf den. 01:18:59.720 --> 01:19:05.500 Dann hat er also offensichtlich log p, log n viele von diesen 01:19:05.500 --> 01:19:06.700 elementaren Operationen. 01:19:09.700 --> 01:19:13.840 Und er empfängt log n mal eine Nachricht. 01:19:14.320 --> 01:19:17.500 Die Nachricht ist jedes Mal konstant groß, also wir stellen uns vor, 01:19:17.580 --> 01:19:22.520 die Elemente, die hier verarbeitet werden, das passt in konstant viele 01:19:22.520 --> 01:19:23.500 Bytes oder so etwas. 01:19:27.840 --> 01:19:34.840 Und dann haben Sie ja hier noch log n mal die Zeit, um konstant viele 01:19:34.840 --> 01:19:35.880 Daten zu empfangen. 01:19:36.020 --> 01:19:38.860 Das ist also konstant oft diese Start-Up-Zeit. 01:19:39.400 --> 01:19:44.080 Und dann mal plus konstant viele Bytes mal Zeit für ein Byte, also es 01:19:44.080 --> 01:19:45.080 sind lauter Konstanten. 01:19:45.080 --> 01:19:51.520 Also das Empfangen dauert jedes Mal konstant lange, die Operation 01:19:51.520 --> 01:19:55.820 dauert jedes Mal konstant lange und beides passiert log n mal. 01:19:56.460 --> 01:19:59.440 Also das wird größenordnungsmäßig logarithmische Arbeit sein. 01:20:01.360 --> 01:20:01.800 Gut. 01:20:05.340 --> 01:20:08.240 Deswegen haben wir da wohl Laufzeit log n und dann kann man sich 01:20:08.240 --> 01:20:14.160 angucken, wie viel mal schneller ist man denn dann. 01:20:14.280 --> 01:20:17.540 Naja, das ist dann größenordnungsmäßig n durch log n. 01:20:17.680 --> 01:20:24.780 Dieser Faktor sequenzielle Zeit geteilt durch log n. 01:20:26.100 --> 01:20:30.180 Jetzt im Allgemeinen so ein bisschen Hände wedelnd. 01:20:30.820 --> 01:20:32.040 Ja, worauf kann man hoffen? 01:20:32.240 --> 01:20:35.780 Ja, mit P-Prozessoren, man könnte hoffen, P mal schneller zu sein. 01:20:38.000 --> 01:20:43.840 Viel mehr wird schwierig, denn wenn Sie was haben aus P-Prozessoren, 01:20:43.900 --> 01:20:46.540 das können Sie ja mit einem Prozessor simulieren, immer so Reihe um, 01:20:46.820 --> 01:20:51.300 jeden für einen Schritt oder so, dann sind Sie, bis auf einen 01:20:51.300 --> 01:20:54.700 konstanten Faktor, mit dem Faktor P nur langsamer. 01:20:56.940 --> 01:21:01.540 Und hier, also die Beschleunigung ist nicht Anzahl Prozessoren n, 01:21:01.700 --> 01:21:04.260 sondern ist nur in Anführungszeichen n durch log n. 01:21:05.620 --> 01:21:08.160 Das ist die Frage, kann man das noch irgendwie verbessern? 01:21:12.080 --> 01:21:15.100 Naja, also man kann es nicht verbessern, indem man da noch mehr 01:21:15.100 --> 01:21:16.440 Prozessoren investiert. 01:21:17.120 --> 01:21:21.000 Oder ich erinnere mich an die Formulierung von einem Professor, bei 01:21:21.000 --> 01:21:22.580 dem ich das mal gehört habe, solche Sachen. 01:21:23.280 --> 01:21:29.420 Er meinte, wenn ein Gärtner für das Pflanzen eines Baumes eine Stunde 01:21:29.420 --> 01:21:33.100 braucht, dann ist nicht die Frage, wie lange brauchen tausend Gärtner 01:21:33.100 --> 01:21:36.600 für das Pflanzen eines Baumes, sondern wie lange brauchen tausend 01:21:36.600 --> 01:21:38.860 Gärtner für tausend Bäume oder so etwas. 01:21:39.540 --> 01:21:40.760 Oder fünftausend Bäume. 01:21:44.420 --> 01:21:49.020 Und da können Sie tatsächlich noch ein bisschen was, also wenn Sie 01:21:49.020 --> 01:21:54.040 einen schönen Beschleunigungsfaktor wollen, wenn das Ihr Ziel ist, 01:21:54.700 --> 01:21:58.640 dann können Sie was gewinnen, indem Sie weniger Prozessoren einsetzen. 01:21:59.420 --> 01:22:01.640 Ups, wie kommt das? 01:22:01.740 --> 01:22:05.120 Also stellen Sie sich vor, wir haben insgesamt n Datenelemente, aber 01:22:05.120 --> 01:22:08.340 wir haben nicht P gleich n Prozessoren, sondern weniger. 01:22:09.520 --> 01:22:12.200 Und die Daten sind gleichmäßig aufgeteilt. 01:22:12.300 --> 01:22:14.500 Wir gehen mal davon aus, die Division geht schon auf. 01:22:14.900 --> 01:22:17.720 Jeder Prozessor hat n durch p Elemente. 01:22:19.540 --> 01:22:20.840 Was kann man dann machen? 01:22:21.080 --> 01:22:24.700 Naja, jeder macht erstmal nacheinander sequenziell, addiert die n 01:22:24.700 --> 01:22:25.840 durch p Elemente auf. 01:22:26.500 --> 01:22:27.560 Das machen alle gleichzeitig. 01:22:28.200 --> 01:22:30.240 Das dauert Zeit, n durch p. 01:22:31.800 --> 01:22:33.580 Dann hat jeder so eine Teilsumme. 01:22:33.580 --> 01:22:37.320 Dann haben Sie noch p Teilsummen und die addieren Sie so, wie wir das 01:22:37.320 --> 01:22:38.800 gerade gemacht haben in so einem Baum. 01:22:39.820 --> 01:22:44.540 Das dauert dann größenordnungsmäßig Logarithmus von p viel Zeit. 01:22:45.800 --> 01:22:51.280 Also die Gesamtlaufzeit ist dann größenordnungsmäßig Theta von n durch 01:22:51.280 --> 01:22:57.640 p für die sequenziellen Teilsummen, plus Theta von Log p für den Baum, 01:22:57.760 --> 01:22:59.820 um die Teilsummen aufzuaddieren. 01:23:01.660 --> 01:23:05.060 Und was ist dann die Beschleunigung im Vergleich zu, wir machen alles 01:23:05.060 --> 01:23:06.700 mit einem Theta von n. 01:23:06.760 --> 01:23:10.000 Das ist halt Theta von n durch Theta von n durch p plus Log p. 01:23:12.340 --> 01:23:16.380 Und wenn Sie jetzt spaßhalber mal für p Anzahlprozessoren nicht n 01:23:16.380 --> 01:23:19.000 einsetzen, sondern nur sowas wie n durch Log n. 01:23:21.760 --> 01:23:26.140 Also hierfür dann unten im Nenner der erste Summand, da steht dann 01:23:26.140 --> 01:23:28.340 also n durch Log n. 01:23:28.760 --> 01:23:29.880 Das ist also sowas wie Log n. 01:23:31.960 --> 01:23:36.540 Und hinten steht das Log p, das ist auch kleiner als Log n. 01:23:37.280 --> 01:23:40.760 Also im Nenner steht dann noch sowas wie größenordnungsmäßig Log n. 01:23:43.770 --> 01:23:48.630 Und dann haben Sie Beschleunigung immer noch sowas größenordnungsmäßig 01:23:48.630 --> 01:23:49.550 n durch Log n. 01:23:51.210 --> 01:23:54.110 Aber die Anzahl Prozessoren ist auch so klein. 01:23:54.710 --> 01:23:57.710 Also Sie kriegen auch mit weniger Prozessoren die gleiche 01:23:57.710 --> 01:23:58.470 Beschleunigung hin. 01:23:58.570 --> 01:24:00.530 In dem Fall jetzt hier so. 01:24:02.890 --> 01:24:03.370 Gut. 01:24:06.290 --> 01:24:10.330 Und das heißt dann manchmal das Prinzip von Herrn Brent. 01:24:12.390 --> 01:24:15.290 Das ist jetzt hier noch ein bisschen vage formuliert, das werden wir 01:24:15.290 --> 01:24:17.050 das nächste Mal dann ein bisschen präziser machen. 01:24:19.890 --> 01:24:24.410 Sie können mit der Beschleunigung in die Nähe der Prozessorzahl 01:24:24.410 --> 01:24:27.230 kommen, manchmal indem Sie die Prozessorzahl kleiner machen. 01:24:28.190 --> 01:24:28.850 Nicht zu viel. 01:24:29.870 --> 01:24:32.730 Und das andere was wir hier jetzt schon mal gesehen haben, also Bäume 01:24:32.730 --> 01:24:36.930 waren jetzt in einem Fall nützlich und die werden in vielen anderen 01:24:36.930 --> 01:24:38.210 Fällen auch noch nützlich sein. 01:24:39.370 --> 01:24:45.550 Das gucken wir uns dann weiter an in der nächsten Vorlesung und das 01:24:45.550 --> 01:24:47.730 dann morgen Nachmittag im ersten Teil. 01:24:48.390 --> 01:24:48.930 Dankeschön.