WEBVTT 00:10.070 --> 00:14.610 Dann begrüße ich Sie recht herzlich zur letzten Vorlesung Paralleler 00:14.610 --> 00:15.790 Algorithmen in diesem Jahr. 00:16.670 --> 00:21.730 Der Michael hatte beim letzten Mal über Datenaustausch all-to-all 00:21.730 --> 00:22.290 geredet. 00:22.930 --> 00:27.310 Der allgemeinste Fall dabei ist unregelmäßige Nachrichtenlängen. 00:27.790 --> 00:30.310 Eigentlich braucht man dann den Begriff all-to-all auch nicht mehr. 00:30.470 --> 00:34.830 Jeder Prozessor hat Daten, also Nachrichten, für andere Prozessoren. 00:34.890 --> 00:36.370 Die können unterschiedlich lang sein. 00:36.730 --> 00:38.870 Insbesondere kann die Nachrichtenlänge auch null sein. 00:38.870 --> 00:40.850 Dann will man das vielleicht auch mit nutzen. 00:43.430 --> 00:47.190 Er hat dann einen Algorithmus vorgestellt, der das zurückführt auf das 00:47.190 --> 00:52.130 regelmäßige all-to-all Problem, wo man sozusagen in vorauseilendem 00:52.130 --> 00:58.870 Gehorsam alle Daten irgendwie auf zufälligen Umwegen leitet. 00:58.990 --> 01:03.950 Und zwar auf allen möglichen Umwegrouten mit zwei Hops sozusagen. 01:05.690 --> 01:11.070 Und das ist irgendwie schön, aber es verschenkt sozusagen Faktor 2 an 01:11.070 --> 01:11.750 Bandbreite. 01:12.410 --> 01:15.870 Und wenn man den Fall hat, dass man eigentlich nur ganz wenige 01:15.870 --> 01:20.090 Nachrichten hat, die nicht null sind, verschenkt man auch sehr viel an 01:20.090 --> 01:21.010 Startup -Overheads. 01:22.930 --> 01:27.290 Also eigentlich ist das immer noch ein offenes Problem, wie man 01:27.290 --> 01:30.270 überhaupt Nachrichten vernünftig ausliefert in so einem Netzwerk. 01:30.270 --> 01:33.970 Selbst in unserem ganz simplen Fall, wo wir annehmen, dass das eine 01:33.970 --> 01:36.070 vollständig symmetrische Situation ist. 01:36.270 --> 01:40.350 Also wo alle Prozessoren gleich schnell sind und jeder mit jedem 01:40.350 --> 01:42.890 gleich schnell kommunizieren kann, egal wo das ist. 01:42.990 --> 01:45.590 Was auch meistens eine Vereinfachung des Systems ist. 01:46.290 --> 01:49.570 Deshalb denke ich, es ist schon sinnvoll, dass wir da auch mal ein 01:49.570 --> 01:51.070 bisschen genauer drüber reden. 01:51.530 --> 01:55.310 Vor allem, weil es da auch ein paar recht fundamentale Einsichten 01:55.310 --> 01:57.950 gibt, wie ich finde, über die ich heute ein bisschen sprechen will. 01:59.150 --> 01:59.830 Okay. 02:05.440 --> 02:08.800 Genau, hattest du Vogel-Strauß-Algorithmus erzählt? 02:08.980 --> 02:14.040 Das ist die Implementierung, die MPI wählt, also das Message-Parsing 02:14.040 --> 02:15.380 -Interface, soviel ich weiß. 02:17.900 --> 02:23.540 Man verlagert das Problem auf eine weiter unterliegende Schicht in der 02:23.540 --> 02:23.900 Software. 02:23.900 --> 02:28.980 Man sagt halt, jeder Prozessor macht asynchrone Sende-Operationen, 02:29.020 --> 02:32.460 also man kann eine Send-Operation aufrufen, die sofort zurückkehrt. 02:33.440 --> 02:37.980 Es gibt dann aber eben so eine Wait-Operation, die dann so lange 02:37.980 --> 02:40.060 wartet, bis das tatsächlich erfolgreich war. 02:40.840 --> 02:43.780 Genauso gut kann man dann so Receive-Operationen aufrufen, wir sammeln 02:43.780 --> 02:44.860 mal alles ein, was kommt. 02:44.860 --> 02:48.940 Und wenn dann alle diese Wait-Operationen fertig sind, weiß man, es 02:48.940 --> 02:49.400 ist fertig. 02:54.380 --> 02:57.460 Aber was dann da unten passiert, da muss dann ja auch irgendein 02:57.460 --> 02:59.180 Scheduling -Algorithmus ablaufen. 02:59.280 --> 03:00.880 Da hat man dann keine Kontrolle mehr drüber. 03:01.380 --> 03:04.120 Und die Erfahrungen, die wir gemacht haben, ist, dass dann alles 03:04.120 --> 03:05.440 mögliche passieren kann. 03:05.800 --> 03:08.520 Vor allem, wenn Sie dann auf wirklich große Parallelrechner gehen, 03:09.020 --> 03:12.560 passieren haarsträubende Dinge, bis zum Absturz des Systems. 03:12.560 --> 03:16.380 Oder was der Michael, glaube ich, gerade hat, ist, dass dann beim 03:16.380 --> 03:20.120 ersten Mal dauert es irgendwie 2000 Mal länger oder 8000 Mal länger, 03:20.300 --> 03:20.880 als es sollte. 03:21.420 --> 03:23.040 Und beim zweiten Mal ist es dann schnell. 03:24.020 --> 03:27.460 Aber in bestimmten Situationen nützt einem das auch nichts, weil man 03:27.460 --> 03:29.900 das nicht beliebig oft wiederholt, sondern nur einmal macht. 03:32.700 --> 03:34.600 Zu diesem Vogel-Strauß-Modell... 03:35.520 --> 03:39.900 Vielleicht mache ich auch mal ein bisschen weniger Festbeleuchtung. 03:40.760 --> 03:41.800 Kann man vielleicht noch mehr sehen. 03:47.780 --> 03:48.380 Saalbeleuchtung... 03:48.380 --> 03:49.340 Was ist das? 03:51.160 --> 03:52.300 Ja, so besser? 03:55.800 --> 04:00.040 Zu diesem Vogel-Strauß-Algorithmus gibt es dann auch ein Vogel-Strauß 04:00.040 --> 04:02.380 -Berechnungsmodell, das nennen wir das PSP-Modell. 04:02.380 --> 04:05.360 Das haben wir am Anfang der Vorlesung schon mal kennengelernt. 04:05.620 --> 04:08.460 Wo man eben einfach sagt, naja, das ist genau unser Modell. 04:08.520 --> 04:13.140 Wir haben diese Phasen, wo die Prozessoren unabhängig rechnen, stopfen 04:13.140 --> 04:17.900 irgendwas ins Netz und dann rufen sie die große All-to-all-Operation 04:17.900 --> 04:18.160 aus. 04:18.200 --> 04:19.460 So, jetzt liefer mal aus. 04:22.440 --> 04:26.160 Was man sich dann anguckt, ist eigentlich eine untere Schranke dessen, 04:26.360 --> 04:27.360 wie lange es dauern soll. 04:27.360 --> 04:33.020 Also es gibt offensichtlich irgendeine Art Latenz, um zum Beispiel so 04:33.020 --> 04:34.400 ein Schedule zu berechnen. 04:37.780 --> 04:41.080 Und dann eine Auslieferungszeit, die irgendwie beschränkt ist durch 04:41.080 --> 04:42.700 die Bandbreite des Netzwerks. 04:43.580 --> 04:47.120 Und da kommt es natürlich darauf an, was ist sozusagen der Bottleneck. 04:47.300 --> 04:52.160 Da gibt es so einen Parameter h, der sagt, für jeden Knoten gucke ich 04:52.160 --> 04:54.540 mir halt an, wie viel Daten muss ich senden und empfangen. 04:55.000 --> 04:59.080 Und je nachdem, ob ich Simplex-Modell oder Vollduplex-Modell habe, 05:00.700 --> 05:03.900 summiere ich dann das Gesendete und das Empfangene oder ich nehme das 05:03.900 --> 05:04.920 Maximum von beiden. 05:06.880 --> 05:09.920 Und das maximiere ich dann nochmal über alle Prozessoren und das ist 05:09.920 --> 05:10.360 mein h. 05:10.700 --> 05:13.740 Und das g ist dann sozusagen so ein Bandbreitenparameter meines 05:13.740 --> 05:14.340 Netzwerks. 05:15.020 --> 05:18.480 Das ist eine untere Schranke, aber wie ich eine obere Schranke angebe, 05:18.560 --> 05:21.660 also einen konkreten Algorithmus, der das tatsächlich erreicht, habe 05:21.660 --> 05:23.400 ich überhaupt keine Literatur darüber gefunden. 05:23.560 --> 05:24.360 Das ist ganz spannend. 05:25.200 --> 05:28.060 Also das BSP-Modell hängt eigentlich so ein bisschen in der Luft. 05:28.460 --> 05:31.380 Und wir reden jetzt darüber, wie man das jetzt wirklich implementieren 05:31.380 --> 05:31.740 würde. 05:41.500 --> 05:45.040 Also hier nochmal formale Definitionen dieser Größen. 05:46.440 --> 05:51.000 Wir haben jetzt so Bottlenecks für das Empfangen von Daten, das 05:51.000 --> 05:53.720 Ausgehen von Daten für jeden Prozessor i. 05:55.500 --> 06:01.520 Und man kann da jetzt in Bytes rechnen, das wird hier beim BSP-Modell 06:01.520 --> 06:01.940 gemacht. 06:02.340 --> 06:06.980 Oder auch in Paketen, die eher ein bisschen größer sind, also 06:06.980 --> 06:09.020 Kilobytes, vielleicht auch viele Kilobytes. 06:09.720 --> 06:14.700 Ich werde heute die meiste Zeit über diese Paketsicht reden, weil ein 06:14.700 --> 06:20.100 Algorithmus, den man verwenden kann, ist Daten paketweise zu 06:20.100 --> 06:20.760 schedulen. 06:20.760 --> 06:23.840 Wenn die Pakete einigermaßen groß sind, kann man sich am ehesten 06:23.840 --> 06:30.220 leisten, da auch in so einen Scheduling-Algorithmus ein bisschen 06:30.220 --> 06:31.780 Gehirnschmalz reinzustecken. 06:32.100 --> 06:34.560 Man kann jetzt nicht für jedes Byte irgendwelche komplizierten 06:34.560 --> 06:36.020 Scheduling -Entscheidungen treffen. 06:37.220 --> 06:41.880 Also HIN von i ist die Anzahl empfangener Pakete, HOUT von i ist die 06:41.880 --> 06:44.560 Anzahl gesendeter Pakete von Prozessor i. 06:44.560 --> 06:53.980 Und im Simplex-Modell ist jetzt unser H dann das Maximum der Summen 06:53.980 --> 06:58.640 von HIN und HOUT und im Duplex-Modell ist es das Maximum der Maxima. 07:01.400 --> 07:04.980 Also damit ist das hier natürlich kleiner, weil ich hier gleichzeitig 07:04.980 --> 07:06.280 senden und empfangen kann. 07:06.280 --> 07:09.540 Nur nützt mir das nichts, wenn ich auf irgendeinem Prozessor dann eine 07:09.540 --> 07:12.660 Asymmetrie habe in den Anzahl gesendeten und empfangenen Daten. 07:13.560 --> 07:16.280 Deshalb bilde ich hier dann nochmal dieses lokale Maximum. 07:17.800 --> 07:21.100 Und eine offensichtliche untere Schranke, wenn ich die Daten 07:21.100 --> 07:25.560 paketweise ausliefere, ist dann H mal Startup-Overhead für eine 07:25.560 --> 07:33.240 Kommunikation plus Paketgröße multibyte. 07:33.240 --> 07:37.500 Und die Frage ist, kann ich das erreichen? 07:38.940 --> 07:41.200 Jetzt kommt erstmal die gute Nachricht. 07:42.420 --> 07:47.020 Im Vollduplex-Modell gibt es dafür eine sehr elegante Lösung, die 07:47.020 --> 07:52.180 spannenderweise bereits 1916 gefunden wurde von Herrn König, einem 07:52.180 --> 07:57.260 Graph -Theoretiker, der einen graphtheoretischen Satz bewiesen hat, 07:57.400 --> 08:02.680 von dem man durch eine geeignete Modellierung zeigen kann, dass er uns 08:02.680 --> 08:05.680 sozusagen einen Scheduling-Algorithmus frei Haus liefert. 08:06.200 --> 08:07.260 Und zwar, wie sieht das aus? 08:07.680 --> 08:10.820 Wir modellieren unser Kommunikationsproblem durch einen bipartiten 08:10.820 --> 08:11.160 Graphen. 08:11.160 --> 08:16.460 Ich hatte eine spezielle Variante davon schon mal vorgestellt, oder 08:16.460 --> 08:23.420 der Jochen Speck war das wahrscheinlich, bei dem Zwei-Baum-Algorithmus 08:23.420 --> 08:24.340 für Broadcasting. 08:25.120 --> 08:32.240 Da hatte man auch so ein Kommunikationsscheduling-Problem, allerdings 08:32.240 --> 08:33.420 ein relativ spezielles. 08:34.340 --> 08:38.440 Also, es ist so, wir haben unsere P-Prozessoren. 08:39.000 --> 08:44.360 Jeder Prozessor wird durch zwei Knoten des bipartiten Graphen 08:44.360 --> 08:47.280 abgebildet, nämlich einmal als Sende-Knoten und einmal als 08:47.280 --> 08:48.260 Empfangsknoten. 08:49.100 --> 08:52.460 Jede Nachricht, die geschickt wird, ist eine Kante. 08:53.080 --> 08:57.400 Und zwar, wenn eine Kante von A nach B geschickt wird, dann ist das 08:57.400 --> 09:01.240 eine Kante zwischen Sende-Knoten A und Empfangsknoten für B. 09:04.540 --> 09:07.320 Genauer gesagt ist das jetzt ein Multigraph. 09:07.700 --> 09:09.600 Das heißt, wir erlauben parallele Kanten. 09:10.620 --> 09:14.640 Das liegt daran, dass es ja sein kann, dass mehrere Pakete zwischen 09:14.640 --> 09:16.800 zwei Prozessoren ausgeliefert werden. 09:17.640 --> 09:20.680 Aber da wir hier paketweise schedulen, fassen wir die nicht irgendwie 09:20.680 --> 09:24.120 zusammen, durch eine Kante mit einem Kantengewicht, sondern wir machen 09:24.120 --> 09:25.360 einfach mehrere Kopien. 09:26.600 --> 09:34.980 Und eine Multigraphnotation ist dann so, die Kantenmenge ist eine 09:34.980 --> 09:35.740 Multimenge. 09:35.960 --> 09:39.960 Das heißt, so ein paar Sendeempfänger kann mehrfach vorkommen. 09:40.720 --> 09:47.100 Und die Größe dieser Multimenge für ein konkretes S, I und R, J, ist 09:47.100 --> 09:48.960 dann halt die Anzahl der Pakete von I nach J. 09:50.720 --> 09:53.960 So, und was Herr König jetzt gezeigt hat, ist... 09:58.000 --> 10:01.680 Es gibt immer eine Frage, was ist H? 10:01.840 --> 10:03.260 Das steht auf der Folie gar nicht drauf. 10:03.320 --> 10:04.180 Könnte mir das jemand sagen? 10:04.280 --> 10:05.860 Was hat H mit diesem Graphen zu tun? 10:08.360 --> 10:11.160 Weil Herr König hat natürlich nichts darüber gezeigt, wie man All-to 10:11.160 --> 10:15.800 -all -Kommunikation macht, sondern er hat eine ganz fundamentale 10:15.800 --> 10:17.780 graphtheoretische Aussage gezeigt. 10:18.400 --> 10:21.180 Was ist, wenn ich jetzt diese Modellierung mache? 10:21.860 --> 10:24.920 Jetzt habe ich praktisch das Kommunikationsproblem übersetzt in einen 10:24.920 --> 10:25.960 bipartiten Graphen. 10:26.020 --> 10:28.800 Was ist dann das H in diesem bipartiten Graphen? 10:29.440 --> 10:33.340 Also das ist nichts anderes als der maximale Grad dieses Graphen. 10:34.520 --> 10:37.560 Also ich gucke mir den maximalen Grad dieses Graphen an und was Herr 10:37.560 --> 10:43.060 König gezeigt hat, ist, dass es in einem bipartiten Multigraphen immer 10:43.060 --> 10:49.060 eine Kantenfärbung gibt, wo die Anzahl Farben gleich dem maximalen 10:49.060 --> 10:50.640 Grad des Graphen ist. 10:51.080 --> 10:57.800 Und Kantenfärbung heißt, es dürfen keine zwei gleichfarbigen Kanten 10:57.800 --> 10:59.700 -Inzidenz zum gleichen Knoten sein. 11:00.500 --> 11:03.540 Dann ist H eine offensichtliche untere Schranke, dass das auch eine 11:03.540 --> 11:06.260 obere Schranke ist, da muss man ein bisschen was beweisen. 11:06.760 --> 11:07.820 Das hat Herr König getan. 11:08.750 --> 11:12.560 Und warum ist das die richtige Modellierung? 11:18.820 --> 11:23.240 Wenn ich so eine Färbung habe, kann ich auch ganz leicht daraus wieder 11:23.240 --> 11:24.300 ein Schedule ablesen. 11:24.580 --> 11:32.160 Ich mache nämlich einfach H-Schritte und sende in Iteration J alle 11:32.160 --> 11:33.920 Nachrichten mit der J-Farbe. 11:36.100 --> 11:38.700 Damit habe ich das Ganze in H-Schritten ausgeliefert. 11:38.840 --> 11:44.320 Ich habe ohnehin die triviale untere Schranke schon hier überlegt. 11:44.500 --> 11:46.720 Naja, ich brauche eben H-Schritte, mindestens. 11:47.540 --> 11:52.520 Und über diese Modellierung durch den bipartiten Graphen steht auch, 11:52.560 --> 11:53.960 ich brauche höchstens H-Schritte. 11:54.500 --> 11:55.160 Also das ist toll. 11:55.340 --> 11:58.920 Wir haben einen optimalen Scheduling-Algorithmus für dieses 11:58.920 --> 12:00.180 Datenauslieferungsproblem. 12:07.130 --> 12:09.110 Inwieweit ist das jetzt eine gute Nachricht? 12:10.230 --> 12:12.230 Bleiben wir vielleicht mal bei der guten Nachricht. 12:13.650 --> 12:19.910 Das Kantenfärben von bipartiten Graphen ist sogar relativ leicht. 12:20.070 --> 12:23.330 Das geht in polynomieller Zeit, das ist schon ganz lange bekannt. 12:24.150 --> 12:29.430 Und es gibt tatsächlich auch sequentielle Algorithmen, die das 12:29.430 --> 12:31.430 effizient machen. 12:31.430 --> 12:37.430 Ich glaube sowas wie MLogH-Zeit oder sowas. 12:38.510 --> 12:40.930 Möglicherweise sogar so Sachen in Richtung Linearzeit. 12:41.350 --> 12:44.270 Also annähernd Linearzeit-Algorithmen, um das zu machen. 12:47.150 --> 12:50.310 Aber das Problem ist so ein bisschen, das reicht uns ja noch nicht 12:50.310 --> 12:50.730 ganz. 12:51.830 --> 12:55.430 Eigentlich müsste man jetzt diese Kantenfärbung parallel berechnen. 12:55.810 --> 12:58.750 Wir bräuchten also einen parallelen Graphen-Algorithmus, der diese 12:58.750 --> 13:00.030 Kantenfärbung ausrechnet. 13:00.030 --> 13:02.870 Und das ist nicht ganz so einfach. 13:03.330 --> 13:06.430 Also es wäre ein spannendes Thema, das wirklich mal zu machen. 13:06.610 --> 13:08.130 Das wäre vielleicht ein Masterarbeitsthema. 13:08.970 --> 13:12.390 Aber ich glaube nicht, dass irgendjemand schon jemals einen 13:12.390 --> 13:15.390 allgemeinen Kantenfärbungs-Algorithmus parallel implementiert hat. 13:17.390 --> 13:21.810 Das ist nicht komplett unmöglich, aber es ist vom Komplexitätsgrad 13:21.810 --> 13:26.950 schon mehr als das, was man typischerweise in parallelen Algorithmen 13:26.950 --> 13:27.330 macht. 13:29.850 --> 13:32.870 Also im Wesentlichen sind die besten Algorithmen, die müssen dann 13:32.870 --> 13:34.270 Eulertouren ausrechnen. 13:36.670 --> 13:39.850 Und das ist übrigens wieder ein Problem, das ganz nah an diesem List 13:39.850 --> 13:42.650 -Ranking -Problem ist, über das Michael geredet hat. 13:43.330 --> 13:45.670 Also wenn man List-Ranking kann, kann man auch Eulertouren. 13:45.770 --> 13:50.210 Wenn man Eulertouren kann, dann kann man auch die wichtigste 13:50.210 --> 13:54.170 Teilberechnung in diesem Multigraph-Färbe-Algorithmus. 13:54.170 --> 13:57.790 Man benutzt dann Eulertouren im Prinzip für so eine Art Divide-and 13:57.790 --> 13:58.470 -Conquer -Schritt. 13:59.150 --> 14:03.010 Ich werde Ihnen übrigens gleich auch irgendwas erklären, wie man 14:03.010 --> 14:05.890 Eulertouren bei einer Verwandtenprobleme auch wieder braucht. 14:06.030 --> 14:08.090 Also die haben irgendwie fundamental was mit diesem 14:08.090 --> 14:09.670 Kantenfärbungsproblem zu tun. 14:13.940 --> 14:16.460 Und ich glaube, man braucht aber leider auch noch ein paar mehr Dinge 14:16.460 --> 14:17.120 als nur Eulertouren. 14:18.300 --> 14:21.480 Aber mit nur Eulertouren kann man schon ganz gute Kantenfärbungen 14:21.480 --> 14:23.320 berechnen, wenn ich mich recht erinnere. 14:23.320 --> 14:26.760 Okay, das waren weiterhin gute Nachrichten. 14:27.260 --> 14:30.740 Trotzdem, ich bin jetzt nahtlos zu den schlechten Nachrichten 14:30.740 --> 14:31.220 gekommen. 14:31.740 --> 14:37.380 Also ich müsste halt, wenn ich diesen Satz aktiv anwenden will, die 14:37.380 --> 14:38.560 Dinge online berechnen. 14:39.420 --> 14:43.680 Oder ich müsste mich jetzt auf spezielle Anwendungen stützen, wo ich 14:43.680 --> 14:46.200 ganz oft das gleiche Kommunikationsmuster habe. 14:46.200 --> 14:48.100 Die gibt es durchaus auch. 14:50.520 --> 14:53.300 Aber selbst da hat es noch keiner gemacht, soviel ich weiß. 14:53.440 --> 14:54.780 Das wäre auch ein spannendes Thema. 14:55.440 --> 15:00.180 Wir haben im Moment gerade sogar eine Massearbeit laufen, die sich mit 15:00.180 --> 15:03.880 Sparse Matrix Vector Multiplication beschäftigt. 15:03.940 --> 15:06.520 Auch ein ganz fundamentales Problem der linearen Algebra. 15:07.360 --> 15:10.900 In der Arbeit geht es vor allem darum, wie man das H reduzieren kann, 15:10.960 --> 15:12.400 das man da braucht, sage ich mal. 15:12.400 --> 15:17.240 Aber wir nehmen da dann irgendwie Out-of-the-Box-MPI-Routinen zum 15:17.240 --> 15:21.240 Ausliefern der Nachrichten oder den Vogel-Strauß-Algorithmus und 15:21.240 --> 15:23.660 beten, dass das einigermaßen funktioniert. 15:24.660 --> 15:27.520 Aber da wäre es zum Beispiel dann cool, eine Masterarbeit 15:27.520 --> 15:30.400 anzuschließen, die das dann richtig macht mit Leistungsgarantien. 15:31.600 --> 15:34.980 Und bei Sparse Matrix Vector Multiplication ist es so, es gibt ganz 15:34.980 --> 15:37.180 viele Anwendungen, da muss man das immer wieder tun. 15:37.320 --> 15:39.400 Zum Beispiel in einem iterativen Gleichungslöser. 15:41.900 --> 15:46.140 Das heißt, das wäre dann ein idealer Use-Case für so einen Offline 15:46.140 --> 15:47.400 -Kommunikationsscheduler. 15:48.320 --> 15:51.140 Das wäre also schon ein Masterarbeitsthema, das ich schon lange mal 15:51.140 --> 15:51.640 machen wollte. 15:52.220 --> 15:53.740 Wenn da jemand von Ihnen Interesse hat. 15:54.120 --> 15:57.880 Vielleicht auch Bachelorarbeit, aber das ist vielleicht nicht so 15:57.880 --> 15:58.700 einfach. 15:59.060 --> 16:01.960 Oder ja, man könnte eine abgespeckte Version finden für eine 16:01.960 --> 16:02.600 Bachelorarbeit. 16:03.600 --> 16:07.400 Ja, aber online berechnen ist teuer. 16:08.860 --> 16:16.180 Und das andere ist, dieses Aufteilen der Pakete bedeutet halt, dass 16:16.180 --> 16:20.240 die Anzahl Startups irgendwie mit diesem H ganz eng verknüpft ist. 16:20.820 --> 16:26.960 Aber es gibt eben auch viele Anwendungen, wo man vielleicht eigentlich 16:26.960 --> 16:28.940 nur wenige Pakete verschicken möchte. 16:31.140 --> 16:34.100 Aber die Nachrichtenlängen sehr stark unterschiedlich sind. 16:34.100 --> 16:37.960 Und dann möchte man nicht künstlich eine lange Nachricht in viele 16:37.960 --> 16:39.220 kleine Pakete aufteilen. 16:39.940 --> 16:42.120 Dann habe ich so einen Trade-Off, ich kann es in große Pakete 16:42.120 --> 16:45.640 aufteilen, aber dann habe ich Rundungsfehler, wo ich dann am Ende ein 16:45.640 --> 16:48.680 halb leeres Paket schicke oder ein 90% leeres Paket. 16:49.300 --> 16:53.720 Oder ich teile es in kleine Nachrichten auf, dann merke ich irgendwann 16:53.720 --> 16:54.740 die Startup-Overheads. 16:55.580 --> 16:58.420 Wir werden am Ende dann auch noch einen Algorithmus sehen, der dieses 16:58.420 --> 17:01.740 Problem umgeht, aber dann an einer anderen Stelle drauf zahlt. 17:01.740 --> 17:05.880 Also da ist wirklich eine offene Wunde noch, ein offenes 17:05.880 --> 17:06.660 Forschungsthema. 17:07.220 --> 17:10.920 Aber es gibt hier zumindest dieses schöne fundamentale Ding, sowas 17:10.920 --> 17:14.460 frage ich sehr gerne in der Prüfung. 17:14.600 --> 17:17.220 Wie geht diese Modellierung, welche Vor- und Nachteile hat die? 17:17.780 --> 17:19.820 Und es ist eigentlich auch relativ einfach. 17:20.940 --> 17:23.860 Jetzt werde ich ein bisschen exotischer. 17:25.240 --> 17:28.980 Einfach weil ich finde, dass man da überraschende und spannende 17:28.980 --> 17:29.840 Algorithmen sieht. 17:30.460 --> 17:36.120 Und man auch ein schönes Beispiel hat, warum Duplex-Kommunikation eben 17:36.120 --> 17:38.680 wirklich viel einfacher ist als Simplex-Kommunikation. 17:39.960 --> 17:42.980 Jetzt nehmen wir uns das gleiche harmlose Problem. 17:43.760 --> 17:47.620 Wie route ich H-Relationen in diesem gleichen Modell? 17:47.760 --> 17:53.240 Also paketweise, das H ist ein bisschen anders definiert, nicht die 17:53.240 --> 17:55.400 Maxima, sondern die Summen werden maximiert. 17:56.100 --> 17:59.500 Wie route ich die jetzt in einem Simplex-Modell? 17:59.660 --> 18:02.800 Das heißt, jeder Prozessor kann gleichzeitig nur senden oder 18:02.800 --> 18:03.380 empfangen. 18:03.960 --> 18:06.260 Auf den ersten Blick eine harmlose Veränderung. 18:06.740 --> 18:09.740 Man würde sich vorstellen, naja, alles dauert doppelt so lange, weil 18:09.740 --> 18:11.560 die Prozessoren nur halb so viel können. 18:12.220 --> 18:15.240 Die schlechte Nachricht ist, es dauert bis zu dreimal so lange. 18:16.380 --> 18:21.080 Hier ist ein ganz einfaches Beispiel, ein Graph mit drei Knoten und 18:21.080 --> 18:22.560 eben ganz vielen parallelen Kanten. 18:22.980 --> 18:24.760 Jetzt zähle ich mal nach, wie viele sind das? 18:25.940 --> 18:28.600 1, 2, 3, 4, 5, 6, 7 in dem Fall. 18:30.500 --> 18:32.260 Der maximale Grad ist 14. 18:37.060 --> 18:47.480 Also würde ich im Vollduplex-Modell 14 Schritte brauchen, um fertig zu 18:47.480 --> 18:47.800 werden. 18:49.040 --> 18:52.680 Was meinen Sie, wie viele Schritte brauche ich im Halbduplex-Modell? 18:53.880 --> 18:55.120 Wer kann mir das sagen? 18:55.880 --> 18:56.680 Stimmen wir ab. 18:58.440 --> 19:00.440 Also was war das im Vollduplex-Modell? 19:00.440 --> 19:01.520 Im Vollduplex-Modell waren es 14. 19:06.160 --> 19:07.620 Vielleicht doppelt so lange? 19:17.880 --> 19:20.080 Ach stimmt, das sind 7. 19:23.580 --> 19:28.240 7, 14 oder 21. 19:28.680 --> 19:31.300 Wer glaubt, es sind 7 Schritte im Halbduplex-Modell? 19:32.060 --> 19:33.260 Keiner, gut aufgebaut. 19:33.260 --> 19:34.240 Wer glaubt, es sind 14? 19:37.140 --> 19:38.420 Wer glaubt, es sind 21? 19:39.400 --> 19:41.540 Dann kann mir jemand sagen, warum 21? 19:42.740 --> 19:45.300 Wenn Sie alle aufzeigen, das haben Sie ja offenbar dann doch 19:45.300 --> 19:45.740 verstanden. 19:47.300 --> 19:48.820 Genau, also eigentlich ist es ganz einfach. 19:49.040 --> 19:51.520 In dem Ding kann immer nur eine Nachricht ausgeliefert werden. 19:51.660 --> 19:53.400 Alles andere lässt das Modell gar nicht zu. 19:53.780 --> 19:56.640 Es gibt 21 Kanten, folglich brauche ich 21 Schritte. 19:57.860 --> 20:00.300 Also ich habe einen Faktor 3 statt einen Faktor 2. 20:02.140 --> 20:04.440 Das ist natürlich jetzt ein Spezialfall. 20:04.820 --> 20:08.460 Ich meine, es gibt jetzt ein paar Aussagen darüber, auch sehr alte. 20:08.760 --> 20:12.200 Da stehen jetzt Fragezeichen dahinter, weil ich die Originalliteratur 20:12.200 --> 20:14.640 nicht wirklich im Detail gelesen habe. 20:14.720 --> 20:18.360 Die gehen dann bis 1891 zurück oder ein berühmtes Paper von Shannon 20:18.360 --> 20:24.200 von 1949, aus dem man im Endeffekt ablesen kann, naja, es sind sowas 20:24.200 --> 20:26.640 wie 3 mal h halbe. 20:28.540 --> 20:35.160 Nur dass das h im Simplexmodell auch noch doppelt so groß ist, deshalb 20:35.160 --> 20:36.040 dieser Faktor 3. 20:37.160 --> 20:39.000 Und dann so ein bisschen rumgerundet. 20:41.880 --> 20:44.020 Also man hat jetzt diesen Faktor 3. 20:46.040 --> 20:47.640 Aber schlimmer wird es auch nicht. 20:47.880 --> 20:51.680 Man kann Algorithmen angeben, die immer höchstens so viel brauchen. 20:52.880 --> 20:56.520 Ich habe in gewisser Weise auch gerade argumentiert, dass das optimal 20:56.520 --> 20:59.720 ist, weil bei dem Ding ist das tight. 21:00.440 --> 21:02.440 Das ist eine ganze Familie von Graphen. 21:03.760 --> 21:08.560 Aber witzigerweise bricht diese untere Schranke bereits zusammen, wenn 21:08.560 --> 21:11.500 ich nichts anderes mache, als diesen Graphen zu nehmen und zu 21:11.500 --> 21:11.980 kopieren. 21:12.820 --> 21:16.320 Also ich habe zwei Kreise, die nichts miteinander zu tun haben und 21:16.320 --> 21:17.260 plötzlich geht es schneller. 21:18.840 --> 21:21.100 Und das ist glaube ich ein bisschen kontraintuitiv. 21:21.680 --> 21:23.320 Da möchte ich ein bisschen mehr zu erzählen. 21:24.300 --> 21:27.780 Und insbesondere stellt das ein paar Annahmen infrage, die man als 21:27.780 --> 21:29.020 völlig natürlich nimmt. 21:29.500 --> 21:33.560 Zum Beispiel ist eine völlig natürliche Annahme, dass ein optimales 21:33.560 --> 21:37.120 Kommunikationsschedule Nachrichten direkt ausliefert. 21:38.940 --> 21:43.260 Aber wir haben letzte Woche schon gesehen, in diesen zwei Phasen 21:43.260 --> 21:46.580 -Algorithmus, dass man dieser Annahme durchaus auch aufweichen kann. 21:46.680 --> 21:49.480 Dass man nämlich die Daten auch auf Umwege leiten kann. 21:50.140 --> 21:53.780 Und man fragt sich natürlich, wieso können Umwege gut sein? 21:54.560 --> 21:56.420 Ich werde es Ihnen jetzt erklären, warum. 21:56.780 --> 22:01.140 Man kann dann mit ganz einfachen Dingen anfangen und dann schrittweise 22:01.140 --> 22:04.220 zeigen, das gibt eigentlich einen fundamental neuen Algorithmus. 22:05.300 --> 22:08.160 Und das möchte ich Ihnen jetzt zumindest in groben Zügen erklären, 22:08.980 --> 22:11.740 ohne in die hässlichen Details allzu sehr einzugehen. 22:13.700 --> 22:20.420 Also der Satz, den wir vor nunmehr 17 Jahren beweisen konnten, hat 22:20.420 --> 22:23.300 irgendwie ganz hässliche Lower-Order-Terms. 22:23.380 --> 22:27.080 Aber im Endeffekt sagen wir, statt das, was Shannon gezeigt hat, 22:27.160 --> 22:30.540 dieses 3 Halbe, können wir das mit 6 Fünftel. 22:31.680 --> 22:32.200 Ja? 22:33.340 --> 22:35.480 Plus irgendwelche Lower-Order-Terms. 22:36.380 --> 22:38.780 Und da muss man nochmal unterscheiden, ob das gerade oder ungerade 22:38.780 --> 22:39.920 Anzahl Prozessoren sind. 22:40.320 --> 22:42.520 Aber im Endeffekt geht es hier um diese 6 Fünftel h. 22:42.620 --> 22:45.120 Die tauchen hier immer wieder auf, plus weitere Terme. 22:45.120 --> 22:48.800 Und wir können aber auch zeigen, dass das dann wirklich das Ende der 22:48.800 --> 22:49.800 Fahnenstange ist. 22:50.040 --> 22:54.340 Also es gibt eine untere Schranke, die sagt, noch besser geht es dann 22:54.340 --> 22:55.080 trotzdem nicht. 22:58.840 --> 23:02.700 Und das versuche ich jetzt zu erklären, wie man da hinkommt. 23:03.480 --> 23:06.660 Und wir fangen mit etwas völlig Trivialem an, wo man den Eindruck 23:06.660 --> 23:10.560 erkennt, ja das ist ja klar, aber das ist ein super spezieller Fall, 23:10.720 --> 23:12.500 wieso belästigt der mich jetzt damit? 23:12.980 --> 23:14.660 Stellen wir uns mal folgenden Fall vor. 23:15.000 --> 23:18.160 Wir haben eigentlich nur drei Prozessoren, die sich irgendwie im Kreis 23:18.160 --> 23:20.340 diese drei Nachrichten zustellen wollen. 23:20.840 --> 23:23.780 Wenn ich jetzt sage, ja, aber was ist, wenn es einen vierten Prozessor 23:23.780 --> 23:25.120 gibt, der gar nichts zu tun hat? 23:26.800 --> 23:31.340 Ohne diesen vierten Prozessor ist es klar, das braucht drei Schritte, 23:31.440 --> 23:32.920 diese Nachrichten auszutauschen. 23:33.260 --> 23:35.440 Mit dem vierten Prozessor braucht es nur zwei. 23:36.420 --> 23:40.260 Weil was wir machen können ist, wir können die roten Nachrichten im 23:40.260 --> 23:41.600 ersten Schritt austauschen. 23:42.500 --> 23:45.100 Also A0 schickt an A1 seine Nachricht direkt. 23:45.940 --> 23:50.640 A2 schickt seine Nachricht, die für A0 bestimmt ist, nicht an A0, weil 23:50.640 --> 23:55.480 der ist beschäftigt, sondern an diesen vierten Prozessor D0, habe ich 23:55.480 --> 23:56.300 den jetzt mal genannt. 23:57.140 --> 24:01.500 Und im zweiten Schritt schickt A1 seine Nachricht direkt an A2 und der 24:01.500 --> 24:05.200 Helferprozessor D0 schickt die Nachricht, die er vorher empfangen hat, 24:05.220 --> 24:05.700 an A0. 24:07.760 --> 24:11.180 In dem Fall habe ich dann tatsächlich diesen Faktor 3,5 komplett 24:11.180 --> 24:15.620 eliminiert, aber eben nur, weil ich zusätzliche Helferprozessoren 24:15.620 --> 24:16.600 postuliert habe. 24:17.100 --> 24:19.880 Und da wird man dann mit Recht argumentieren, naja, aber die wirst du 24:19.880 --> 24:21.260 im allgemeinen Fall nicht haben. 24:21.700 --> 24:21.940 Bzw. 24:22.140 --> 24:24.480 das ist dann eine zusätzliche Ressource, die ist auch teuer. 24:25.180 --> 24:27.640 Und wenn schon, wie viele von diesen Ressourcen brauchst du denn? 24:27.820 --> 24:29.160 Das wäre eine legitime Frage. 24:29.720 --> 24:31.440 Da komme ich ganz zum Ende nochmal dazu. 24:31.440 --> 24:33.900 Aber wir haben uns gesagt, nee, wir machen was anderes. 24:34.060 --> 24:36.660 Wir sagen, wir haben eine beliebige H-Relation, wir haben keine 24:36.660 --> 24:40.460 Helferprozessoren, aber wir wollen uns angucken, ob es nicht trotzdem 24:40.460 --> 24:48.060 möglich ist, durch Leiten von Nachrichten auf Umwegen, diese Schranke 24:48.060 --> 24:49.560 von 3,5 H zu durchbrechen. 24:50.980 --> 24:53.460 Das haben Roberto Solis-Oba und ich uns angeschaut. 24:54.900 --> 24:57.740 So, jetzt wird es das erste Mal hässlich, 25:01.020 --> 25:04.120 aber eigentlich, wenn man sich ein bisschen mehr Zeit nimmt, bleibt es 25:04.120 --> 25:05.180 eigentlich relativ einfach. 25:05.340 --> 25:09.560 Also ich mache jetzt wieder ein Beispiel, das aber jetzt erstmals 25:09.560 --> 25:14.280 keine Helferprozessoren braucht, sondern sagt, naja, dieses Beispiel, 25:14.400 --> 25:15.080 das ich eben hatte. 25:15.180 --> 25:18.460 Ich sage, ich habe diesen Dreikreis und ich habe einfach zwei Kopien 25:18.460 --> 25:18.800 davon. 25:19.620 --> 25:20.060 Ja? 25:22.600 --> 25:26.740 Und jetzt ist es so, eine weitere Hässlichkeit in dem Algorithmus, die 25:26.740 --> 25:30.860 ich gerne noch loswerde, ist, dass wir eigentlich sagen, wir nehmen 25:30.860 --> 25:36.560 die Pakete, die wir eigentlich haben und teilen die in fünf Teilpakete 25:36.560 --> 25:36.880 auf. 25:37.640 --> 25:41.520 Warum, wird hier jetzt bereits an einem Spezialfall sichtbar. 25:43.060 --> 25:48.180 Also stellen wir uns vor, wir haben ein immer noch sehr spezielles 25:48.180 --> 25:48.520 Kommunikationsmuster. 25:49.860 --> 25:57.120 Sechs Prozessoren in zwei Dreiergruppen eingeteilt, die jeweils 25:57.120 --> 26:00.620 Nachrichten sozusagen im Kreis schicken. 26:00.800 --> 26:03.260 Das heißt, in dem Beispiel ist das jetzt, hier werden sie im Kreis 26:03.260 --> 26:07.120 geschickt und hier gehen die alle da dran, aber die Richtung ist da 26:07.120 --> 26:08.200 eigentlich nicht so interessant. 26:08.200 --> 26:10.340 Da kann man sich auch überlegen, warum. 26:12.820 --> 26:14.360 Vergessen Sie erstmal, was hier rechts steht. 26:14.560 --> 26:19.040 Warum ist es uninteressant, ob diese Kanten hier in die Richtung gehen 26:19.040 --> 26:20.860 oder in die andere und dann hätte ich einen Kreis? 26:21.100 --> 26:22.420 Können wir das jemandem sagen? 26:23.060 --> 26:24.300 Ja, genau. 26:24.460 --> 26:27.600 Also wenn Sie jetzt ein Schedule haben, bei dem eine Nachricht in eine 26:27.600 --> 26:31.580 Richtung gesendet wird, dann können Sie da ein äquivalentes Schedule 26:31.580 --> 26:34.940 haben, bei dem die Nachricht in die andere Richtung gesendet wird und 26:34.940 --> 26:37.600 es ändert sich im sonstigen Geschehen nichts. 26:38.200 --> 26:45.120 Deshalb sind eigentlich hier bei diesem Simplex-Nachrichtenscheduling 26:45.120 --> 26:48.200 -Problem die Pfeilrichtungen relativ uninteressant. 26:50.660 --> 26:58.120 Wir haben diese zwei Kopien, wir haben eigentlich so ein Metapaket in 26:58.120 --> 27:01.940 diesem Dreieck jeweils, haben das aber in fünf Teilpakete aufgeteilt, 27:02.320 --> 27:03.780 die nur ein Fünftel so groß sind. 27:03.780 --> 27:09.100 So, und jetzt gebe ich hier ein Schedule an. 27:09.840 --> 27:13.080 Der naive Algorithmus, da wäre es halt so, da würden die jeweils für 27:13.080 --> 27:13.820 sich agieren. 27:14.540 --> 27:21.060 Jeder der Knoten hat gerade zehn, ich bräuchte also 15 Schritte, um 27:21.060 --> 27:21.780 das auszuführen. 27:22.840 --> 27:25.980 Und hier ist jetzt ein Schedule angegeben, dass das in zwölf Schritten 27:25.980 --> 27:26.340 macht. 27:27.780 --> 27:29.900 Und jetzt erkläre ich, wie dieses Schedule funktioniert. 27:30.660 --> 27:35.140 Das kann man im Endeffekt sich aufgeteilt denken in zwei Teilschedules 27:35.140 --> 27:36.040 der Länge 6. 27:38.040 --> 27:41.400 Im ersten Teilschedule ist es im Wesentlichen so, 27:45.940 --> 27:53.120 die B-Gruppe tauscht in diesen sechs Schritten, jeder Prozessor wird 27:53.120 --> 27:54.600 zwei von seinen Paketen los. 27:54.600 --> 28:00.600 Das sind hier diese Solid Lines da. 28:01.400 --> 28:11.380 Also zum Beispiel B2 schickt das rote Paket an B1 und das blaue Paket 28:11.380 --> 28:12.600 an B1. 28:14.660 --> 28:17.920 Die beiden Dinger werden in dieser ersten Hälfte ausgeliefert. 28:18.700 --> 28:23.860 Also in der ersten Hälfte hinkt die B-Gruppe irgendwie hinterher. 28:24.600 --> 28:25.560 Das können Sie jetzt überprüfen. 28:26.840 --> 28:30.920 Diese durchgezogenen Linien der B-Gruppe, da wird jeder genau zwei von 28:30.920 --> 28:35.100 seinen Paketen los oder empfängt zwei von seinen Paketen, je nachdem. 28:37.260 --> 28:40.520 Der Trick ist, die A-Gruppe wird drei von ihren Paketen los. 28:42.200 --> 28:43.320 Was passiert jetzt? 28:43.420 --> 28:47.300 Also die B-Gruppe, da sind sechs Schritte. 28:50.260 --> 28:57.920 In jedem der Schritte sind zwei der Prozessoren damit beschäftigt, ein 28:57.920 --> 28:59.480 Paket direkt auszuliefern. 29:00.660 --> 29:04.780 Und einer wäre dann arbeitslos, wenn man nur innerhalb von B 29:04.780 --> 29:05.840 kommunizieren würde. 29:05.960 --> 29:10.580 Und dieser arbeitslose Prozessor agiert als Helfer für die A-Gruppe. 29:11.160 --> 29:13.860 Und das wird hier jetzt durchdekliniert. 29:14.120 --> 29:18.500 Also in der A-Gruppe ist es zum Beispiel so, dass A2 seine rote 29:18.500 --> 29:26.020 Nachricht an A1, das ist die hier, nicht direkt an A1 schickt, sondern 29:26.020 --> 29:27.840 erstmal an B0. 29:27.840 --> 29:40.480 Und im folgenden Schritt nimmt er seine rote Nachricht an A0. 29:40.680 --> 29:42.900 A2 nach A0. 29:45.680 --> 29:48.960 Das stimmen die Farben nicht oder sehe ich da jetzt falsch? 29:51.540 --> 29:53.380 A2 an A0. 29:53.860 --> 29:57.400 Ich glaube, ich habe die Farben einfach nicht ganz konsistent gewählt. 29:57.520 --> 29:58.420 Ist aber auch egal. 29:59.340 --> 30:02.960 Also A2 nimmt eine seiner Nachrichten, die er an A0 schicken will, 30:03.300 --> 30:04.580 schickt die erstmal an B0. 30:05.700 --> 30:10.280 Und B0 ist danach immer noch arbeitslos und kann die dann ausliefern, 30:10.360 --> 30:11.380 da wo sie eigentlich hin sollte. 30:11.380 --> 30:17.100 Das hat B nicht wirklich geschadet, weil B0 sowieso arbeitslos gewesen 30:17.100 --> 30:17.440 wäre. 30:18.460 --> 30:22.160 Nach der ersten Hälfte ist es also so, die A-Gruppe ist drei von ihren 30:22.160 --> 30:25.680 fünf Paketen losgeworden jeder und die B-Gruppe zwei. 30:26.520 --> 30:29.160 In der zweiten Hälfte drehe ich das Ganze um. 30:29.280 --> 30:31.580 Da helfen die A-Prozessoren den B-Prozessoren. 30:31.980 --> 30:34.640 Dann wird also bei B jeder drei los und bei A jeder zwei. 30:34.640 --> 30:38.640 Und nach zwölf Schritten hat damit jeder fünf Pakete losgeworden. 30:38.740 --> 30:42.480 Das sind genau diese fünf parallelen Pakete, die hier jeweils drin 30:42.480 --> 30:42.800 sind. 30:43.180 --> 30:48.740 Und damit habe ich also die Anzahl Schritte von 15 auf 12 gesenkt. 30:49.840 --> 30:53.800 So, das sieht jetzt immer noch sehr speziell aus. 30:56.560 --> 31:02.020 Jetzt gucken wir mal, ob man nicht trotzdem das allgemeine H 31:02.020 --> 31:05.820 -Relationsproblem näher an diese Situation kriegt. 31:07.140 --> 31:09.920 Der erste Schritt ist erstmal, dass wenn ich das hier auf 31:09.920 --> 31:13.900 Metapaketebene sehe, also die fünf parallelen Kanten immer zu einem 31:13.900 --> 31:21.000 zusammenfasse, dann darf hier jeder Prozessor nur ein Paket, nur ein 31:21.000 --> 31:22.360 Grad zwei eigentlich haben. 31:22.560 --> 31:25.180 Er darf nur an zwei von diesen Metapaketen beteiligt sein. 31:25.840 --> 31:27.160 Wie kann ich das erreichen? 31:28.100 --> 31:30.800 Und dann gucke ich mir erstmal eine Reduktion einer allgemeinen H 31:30.800 --> 31:34.940 -Relation an auf H halbe zwei Relationen. 31:35.080 --> 31:38.320 Also eine Zwei-Relation ist eine, wo, wie ich gerade gesagt habe, 31:38.400 --> 31:40.680 jeder Prozessor nur an zwei Nachrichten beteiligt ist. 31:41.940 --> 31:45.680 So, da habe ich jetzt kein schönes Bild zu. 31:46.620 --> 31:49.680 Da müssen Sie mir jetzt ein bisschen folgen. 31:51.260 --> 31:54.000 Ich habe eben schon gesagt, Kommunikationsrichtung interessiert mich. 31:54.100 --> 31:56.520 Also ich habe jetzt irgendwie so einen Kommunikationsgrafen 31:56.520 --> 31:58.140 umgerichtet. 32:01.880 --> 32:04.760 Und ich möchte jetzt Eulertouren verwenden. 32:06.720 --> 32:10.120 Eulertouren gibt es in Grafen, bei denen alle Knoten gerade gerade 32:10.120 --> 32:10.420 sind. 32:10.680 --> 32:12.840 Das ist hier nicht notwendigerweise der Fall. 32:13.640 --> 32:16.400 Es kann Knoten mit ungeradem Grad geben. 32:20.000 --> 32:23.260 Aber was ich machen kann, ist, ich kann mir mal jeweils zwei Knoten 32:23.260 --> 32:27.940 mit ungeradem Grad holen, die miteinander verbinden. 32:29.380 --> 32:32.760 Und dann haben die beide geraden Grad und danach sind die nie wieder 32:32.760 --> 32:33.820 an der Geschichte beteiligt. 32:34.760 --> 32:39.980 Das heißt, ich kann, indem ich die Knoten gerade aufrunde, dafür 32:39.980 --> 32:43.400 sorgen, dass am Ende alle Knoten gerade gerade sind. 32:44.820 --> 32:47.240 Dadurch kommt dieses H halber aufgerundet. 32:48.660 --> 32:49.920 Das kostet mich nicht viel. 32:50.600 --> 32:52.980 So, jetzt kann ich diese Eulertour-Technik verwenden. 32:53.140 --> 32:57.320 Also die zerlegt den Grafen in kantendisjunkte Kreise. 32:59.580 --> 33:03.080 Was kann ich da ein Beispiel für angeben? 33:08.120 --> 33:09.680 Ja, sowas hier zum Beispiel. 33:09.820 --> 33:12.460 Also diese Eulertour-Sache, die ist eigentlich ganz naiv. 33:12.820 --> 33:16.320 Ich fange irgendwo an, sagen wir mal hier bei 1 und laufe einfach 33:16.320 --> 33:16.940 immer weiter. 33:17.960 --> 33:21.100 Also ich folge so einem Pfeil, dann muss ich hier einen ausgehenden 33:21.100 --> 33:23.600 Pfeil suchen, nehme ich zum Beispiel die linke Kopie von dem. 33:24.560 --> 33:30.560 Dann gehe ich hier weiter, da weiter, da weiter und dann habe ich 33:30.560 --> 33:31.240 einen Kreis. 33:31.300 --> 33:34.820 Und das mache ich so lange, bis sich alle Kanten durch so Kreise 33:34.820 --> 33:35.560 abgedeckt haben. 33:35.960 --> 33:39.280 Ich kann halt relativ einfach zeigen, dass das eben immer aufgeht, 33:39.380 --> 33:41.880 egal wo man da anfängt. 33:42.420 --> 33:44.060 Das ist im Prinzip der Satz von Euler. 33:44.960 --> 33:47.380 Er ist, glaube ich, mehr als 200 Jahre alt. 33:53.210 --> 33:54.390 Was habe ich davon? 33:55.310 --> 33:58.290 Ich habe den in kantendisjunkte Kreise zerlegt. 33:59.950 --> 34:04.110 Und wenn ich jetzt hergehe und in jedem Kreis den Kanten eine neue 34:04.110 --> 34:07.090 Richtung gebe, das hat also nichts mehr mit der ursprünglichen 34:07.090 --> 34:08.650 Kommunikationsrichtung zu tun. 34:09.410 --> 34:12.550 Also ich laufe durch diesen Kreis rum und gebe immer konsistente 34:12.550 --> 34:12.850 Richtungspfeile. 34:14.010 --> 34:18.010 Wenn ich das mit allen Kreisen mache, bedeutet das dann am Ende, dass 34:18.010 --> 34:22.110 jeder Knoten einen Eingangsgrad höchstens halber aufgerundet hat und 34:22.110 --> 34:24.810 einen Ausgangsgrad höchstens halber aufgerundet. 34:32.550 --> 34:37.170 Jetzt mache ich wieder einen Bipartitengrafen, der genauso ist wie bei 34:37.170 --> 34:40.070 diesem Vollduplex-Ding, aber jetzt für einen anderen Zweck. 34:40.770 --> 34:43.850 Ich habe weiter Halbduplex-Kommunikation, aber niemand hindert mich, 34:43.930 --> 34:45.730 diesen Bipartitengrafen aufzubauen. 34:46.170 --> 34:47.490 Den färbe ich. 34:48.010 --> 34:51.950 Das kann ich dann nach dem Satz von König mit halber aufgerundet 34:51.950 --> 34:52.550 vielen Farben. 34:53.430 --> 34:56.610 Und jetzt nehme ich wieder diese Farbklassen. 34:58.050 --> 35:01.250 Die kann ich jetzt nicht direkt ausliefern, also bei Vollduplex könnte 35:01.250 --> 35:03.770 ich die jetzt direkt ausliefern in dem Netzwerk. 35:04.690 --> 35:07.830 Hier liefern die mir erstmal nur neue Graphen, nämlich zwei 35:07.830 --> 35:08.770 Relationen. 35:09.330 --> 35:13.770 Wenn ich also nur die Kanten einer Farbe nehme, hat jeder Knoten 35:13.770 --> 35:14.770 höchstens Grad 2. 35:17.110 --> 35:23.010 Das heißt, ich habe den Graphen mit maximalem Grad H zerlegt, in H 35:23.010 --> 35:27.390 halber aufgerundet, viele Graphen, in denen jeder der Teilgrafen nur 35:27.390 --> 35:28.730 maximalen Grad 2 hat. 35:29.610 --> 35:32.430 Das ist übrigens wieder genau dieser Spezialfall, den wir beim 35:32.430 --> 35:33.530 Broadcasting hatten. 35:36.310 --> 35:39.510 Und jetzt brauche ich eigentlich nur noch einen Scheduling 35:39.510 --> 35:42.590 -Algorithmus, der zwei Relationen schedulen kann, weil ich mache 35:42.590 --> 35:45.070 einfach alle zwei Relationen hintereinander in meinem Schedule. 35:46.610 --> 35:49.630 Das ist also eine Reduktion von einem allgemeinen Graphen auf das 35:49.630 --> 35:51.750 Problem, zwei Relationen zu ruten. 35:52.350 --> 35:53.790 Und naja, was hat das hiermit zu tun? 35:54.530 --> 36:00.850 Auf dieser Metakantenebene sind das ja spezielle zwei Relationen, 36:00.910 --> 36:04.250 nämlich in dem Fall zwei Kreise der Länge 3. 36:04.250 --> 36:07.030 Da kann man sagen, oh, da ist es ja immer noch weit weg. 36:08.810 --> 36:12.430 Wir müssen jetzt nur noch zwei Relationen ruten, aber das da ist ein 36:12.430 --> 36:17.310 sehr spezieller Fall einer zwei Relation, nämlich zwei Kreise der 36:17.310 --> 36:17.910 Größe 3. 36:19.210 --> 36:20.330 Wie gehe ich damit um? 36:26.000 --> 36:28.500 Jetzt müssen wir da tatsächlich eine Fallunterscheidung machen. 36:28.680 --> 36:32.780 Ich erkläre Ihnen nur den einfacheren Fall, nämlich mit gerade Anzahl 36:32.780 --> 36:33.480 Prozessoren. 36:34.940 --> 36:38.460 Man kann sich jetzt leicht überlegen, dass wenn ich eine gerade Anzahl 36:38.460 --> 36:42.880 Prozessoren habe, dann ist die Anzahl ungerader Kreise in der zwei 36:42.880 --> 36:44.420 Relation gerade. 36:45.480 --> 36:49.620 Das heißt, ich kann immer Paare von ungeraden Kreisen wählen. 36:50.320 --> 36:52.740 Die geraden Kreisen sind sowieso kein Problem. 36:54.120 --> 37:00.380 Die kann ich auch im Halbduplex-Modell immer in zwei Schritten, also 37:00.380 --> 37:02.640 in diesem Fall in zehn Schritten ausliefern. 37:04.120 --> 37:06.300 Warum sind gerade Kreise kein Problem? 37:06.400 --> 37:07.260 Kann mir das jemand sagen? 37:12.720 --> 37:19.840 Also jetzt habe ich zum Beispiel einen Kreis mit sechs Knoten und da 37:19.840 --> 37:24.180 sind jetzt immer diese Kanten, die aus fünf Teilpaketen bestehen und 37:24.180 --> 37:25.060 das ist gar nicht wichtig. 37:26.040 --> 37:32.200 Wie viele Schritte brauche ich, um diese Nachrichten im Halbduplex 37:32.200 --> 37:33.300 -Modell auszuliefern? 37:33.300 --> 37:34.900 Wer kann mir das sagen? 37:44.920 --> 37:45.420 Warum? 37:52.080 --> 37:53.420 Ja, so könnte ich das schon. 37:53.760 --> 37:56.060 Man kann das jetzt grafentheoretisch formulieren. 37:59.340 --> 38:03.180 Ein gerader Zweitzyklus lässt sich zweifärben. 38:09.060 --> 38:12.620 Da kann ich also im ersten Schritt die blauen, im zweiten Schritt die 38:12.620 --> 38:13.760 roten Nachrichten liefern. 38:13.880 --> 38:15.080 Perfekter Parallelismus. 38:15.220 --> 38:16.320 Niemand bleibt übrig. 38:17.040 --> 38:19.740 Dieses Problem mit den ungeraden Kreisen habe ich gar nicht. 38:20.420 --> 38:23.300 Also die geraden Kreise sind uninteressant. 38:23.380 --> 38:25.880 Die ungeraden Kreise paare ich zusammen. 38:26.480 --> 38:28.160 Die sollen sich also gegenseitig helfen. 38:29.740 --> 38:33.460 Und wie viele Paare sind es dann auch egal, weil ich das völlig 38:33.460 --> 38:34.600 unabhängig betrachte. 38:34.920 --> 38:38.260 Jetzt bin ich also doch schon ganz nah an diesem Ding dran. 38:38.660 --> 38:42.720 Ich muss immer nur zwei ungerade Kreise betrachten und dann kann man 38:42.720 --> 38:46.460 nur noch sagen, naja, aber das ist ganz speziell, das sind drei 38:46.460 --> 38:48.220 Kreise, die wird man im Allgemeinen nicht haben. 38:48.340 --> 38:52.380 Das können Eins-Kreise sein, Fünf-Kreise, whatever. 38:54.580 --> 38:56.620 Eins-Kreise sind besonders einfach. 38:58.560 --> 39:02.760 Also nehmen wir an, wir haben einen Eins-Kreis mit einem Fünf-Kreis, 39:02.860 --> 39:05.020 Drei -Kreis, Sieben-Kreis, was immer gepaart. 39:05.340 --> 39:06.740 Was ist denn ein Eins-Kreis? 39:06.820 --> 39:09.080 Der kommt mit einem Prozessor, der nichts tut. 39:10.120 --> 39:12.540 Das ist der perfekte Fall von diesem Helfer. 39:13.660 --> 39:15.620 Das heißt, der ist sowieso ganz einfach. 39:16.320 --> 39:21.660 Also der interessante Fall ist, ich habe zwei ungerade Kreise, die 39:21.660 --> 39:23.540 mindestens die Größe 3 haben. 39:24.440 --> 39:28.720 Und das ist jetzt doch ziemlich nah an diesem 2-3-Kreisen-Ding. 39:29.560 --> 39:32.820 Ich will Sie jetzt nicht mit den Details des Schedules belasten, aber 39:32.820 --> 39:37.440 im Prinzip ist es so, dieses Beispiel von 2-3-Kreisen lässt sich ganz 39:37.440 --> 39:42.460 leicht verallgemeinern auf größere Kreise. 39:43.280 --> 39:46.260 Also das Einzige, was da passiert, ist, dass dann nicht alle Knoten 39:46.260 --> 39:49.580 helfen müssen, sondern nur die, die irgendwie am Ende von einer 39:49.580 --> 39:52.840 beliebig gewählten Reihenfolge der Knoten in diesem Kreis sind. 39:53.960 --> 39:57.460 Aber die Details sind jetzt wirklich nicht so spannend. 39:58.900 --> 40:01.880 Glauben Sie mir einfach, das lässt sich problemlos machen. 40:05.900 --> 40:09.720 Es war übrigens auch ganz witzig, dass in diesem Papier, das wir dann 40:09.720 --> 40:12.880 geschrieben haben, hatten wir erst einen viel komplizierteren 40:12.880 --> 40:13.580 Algorithmus. 40:17.180 --> 40:20.100 Den hatten wir dann eingereicht, also irgendwie war ein Paper, das 40:20.100 --> 40:23.160 viel zu lang war, mit riesigen Anhängen rauf und runter. 40:26.700 --> 40:28.840 Oder war es kurz vor der Einreichung oder so. 40:30.760 --> 40:33.600 Jedenfalls, dann war es vielleicht sogar schon angenommen. 40:33.880 --> 40:39.020 Und dann habe ich halt irgendwie eines Nachts die Idee gehabt, wie man 40:39.020 --> 40:42.940 das auf ein Viertel der Komplexität drücken kann, also 40:42.940 --> 40:45.080 Beschreibungskomplexität des Algorithmus. 40:45.760 --> 40:48.160 Und dann war ich im Problem, wir hatten den Komplizierten schon 40:48.160 --> 40:48.880 aufgeschrieben. 40:48.880 --> 40:53.620 Es ist leider bekannt, dass auf Theoriekonferenzen, je komplizierter 40:53.620 --> 40:56.620 der Algorithmus, desto wahrscheinlicher, dass das Papier akzeptiert 40:56.620 --> 40:57.360 wird. 40:58.080 --> 40:59.940 Da hatten wir echt ein Gewissensproblem. 41:00.080 --> 41:03.880 Sollen wir jetzt die einfache Sache aufschreiben oder lassen wir es 41:03.880 --> 41:04.720 einfach so stehen? 41:05.740 --> 41:09.100 Und ich habe den Verdacht, dass viele meiner Kollegen diese Frage 41:09.100 --> 41:10.820 anders beantwortet hätten als ich. 41:10.960 --> 41:13.920 Also wir haben es dann einfach aufgeschrieben, aber viele 41:13.920 --> 41:16.560 Theoriepapiere frage ich, wo muss das jetzt sein? 41:18.880 --> 41:23.780 Das hier ist jetzt für ein Theoriepapier alles noch relativ einfach, 41:23.900 --> 41:24.860 was ich Ihnen hier erkläre. 41:25.580 --> 41:27.820 Da gibt es viel wildere Geschichten. 41:29.180 --> 41:35.180 Gerade auch beim Kantenfärben, da habe ich selber auch ein Papier, da 41:35.180 --> 41:37.900 war dann irgendwie so eine Folge von Papers, wo dann der 41:37.900 --> 41:40.180 Approximationsfaktor immer besser wurde. 41:40.940 --> 41:46.860 Aber mit jeder Folge von jedem neuen Papier vervielfachte sich die 41:46.860 --> 41:48.360 Algorithmenbeschreibungslänge. 41:49.420 --> 41:52.240 Es war dann hinterher so, dass da keiner mehr wirklich folgen konnte. 41:52.380 --> 41:58.780 Und dann habe ich mal so einen hochbegabten Studie im zweiten Semester 41:58.780 --> 41:59.080 gefragt. 41:59.140 --> 42:01.880 Guck dir das doch mal an, ob man diese Algorithmenverkomplizierung 42:02.940 --> 42:04.120 nicht automatisieren kann. 42:04.400 --> 42:08.340 Schreib mal ein Skript, das dann immer Papers ausspuckt. 42:08.680 --> 42:13.260 So 10 Seiten Algorithmus, 100 Seiten Algorithmus, 1000 Seiten 42:13.260 --> 42:14.180 Algorithmus. 42:14.660 --> 42:16.720 Und der kam dann aber, nee, ich kann das nicht. 42:16.720 --> 42:19.780 Aber ist es auch okay, wenn ich dir einen neuen Algorithmus gebe, der 42:19.780 --> 42:22.440 das insgesamt löst, das Problem? 42:22.600 --> 42:23.300 Und dann habe ich gesagt, ja. 42:24.080 --> 42:26.360 Aber der Algorithmus war dann auch nicht einfach. 42:26.620 --> 42:27.500 Also dagegen ist das hier. 42:28.500 --> 42:32.100 Aber der konnte eben, wie gesagt, das, was die auf 100 Seiten machen, 42:33.340 --> 42:37.380 1000 und so weiter, extrapoliert waren dann nur noch 20, sage ich mal. 42:37.620 --> 42:40.480 Und das hier sind zwei oder drei Seiten, wenn man es kompakt 42:40.480 --> 42:40.960 beschreibt. 42:41.980 --> 42:42.580 Okay. 42:44.100 --> 42:48.840 Also Sie glauben mir vielleicht, dass man dieses 2 mal 3 Kreise jetzt 42:48.840 --> 42:53.260 auf 2 mal ungerade Kreise der Länge 3 allgemeinern kann. 42:54.980 --> 42:57.460 So, zu ungeraden P sage ich auch nicht viel. 42:57.560 --> 43:00.660 Die Idee ist, dass man dann in jedem Zweifaktor irgendwie geschickt 43:00.660 --> 43:01.900 eine Kante löscht. 43:02.020 --> 43:08.100 Und zwar so, dass man dann immer Täter P von diesen Kreisen sammeln 43:08.100 --> 43:12.580 kann zu einem neuen Problem, das man dann in konstanter Zeit lösen 43:12.580 --> 43:12.880 kann. 43:13.680 --> 43:16.860 Und dann kriegt man irgendwie einen hässlichen zusätzlichen additiven 43:16.860 --> 43:19.340 Term, aber das ist ein Lower Order Term, der interessiert nicht so. 43:21.400 --> 43:24.460 Also das ist jetzt so die Skizze für dieses theoretische Ergebnis. 43:24.960 --> 43:30.420 Wir können also diese scheinbar unschlagbare Schranke von 3 Halbe 43:30.420 --> 43:37.340 lösen, in dem Sinne, dass wir zeigen, es geht mit 6 Fünftel statt 3 43:37.340 --> 43:40.700 Halbe, es gibt irgendwelche Lower Order Terms. 43:41.580 --> 43:43.620 Das ist, was wir gezeigt haben. 43:46.480 --> 43:51.380 Aber eigentlich wäre es schön, wenn man dieses Ergebnis noch ein 43:51.380 --> 43:52.660 bisschen abrunden könnte. 43:53.620 --> 43:57.200 Zum Beispiel, wir haben dann 2 Arten von Paketen. 43:57.400 --> 44:01.760 Wir haben Pakete und irgendwann werden die in 5 Teilpakete aufgeteilt. 44:02.180 --> 44:03.360 Das ist total hässlich. 44:03.860 --> 44:07.180 Es müsste eigentlich möglich sein, einen Algorithmus anzugeben, der 44:07.180 --> 44:10.440 mit einer festen Paketgröße immer arbeitet. 44:12.620 --> 44:16.160 Das würde dann wahrscheinlich bedeuten, dass man einen Algorithmus 44:16.160 --> 44:19.780 angeben muss, der dann 5 Relationen routet, statt 2 Relationen oder 44:19.780 --> 44:20.540 irgendwie sowas. 44:20.880 --> 44:22.720 Und dann wieder ein bisschen komplizierter wird. 44:23.760 --> 44:27.480 Aber wie schreibt man das so auf, dass das insgesamt korrekt ist? 44:28.340 --> 44:30.920 Und dann war ich ziemlich angepisst. 44:31.980 --> 44:36.480 Dann kam irgendwie 2 Jahre nach unserem super allgemeinen Ergebnis 44:37.160 --> 44:39.900 irgendein Papier raus und auch noch in einer total prominenten 44:39.900 --> 44:44.060 Konferenz, das im Prinzip das hier gesagt hat. 44:45.460 --> 44:47.440 Und da bin ich aus allen Wolken gefallen. 44:47.700 --> 44:49.120 Was soll denn das jetzt? 44:49.200 --> 44:50.060 Das ist ja nicht neu. 44:50.960 --> 44:56.360 Die haben sowas gesagt, wenn ich 1 Drittel P zusätzliche Prozessoren 44:56.360 --> 44:58.860 habe, dann kann ich jede H-Relation schnell routen. 44:59.660 --> 45:00.520 Big Deal! 45:00.920 --> 45:04.960 Das ist eigentlich ein Spezialfall von dem, was wir gezeigt haben, 45:05.060 --> 45:07.800 aber das wussten die nicht und die Gutachter haben es auch nicht 45:07.800 --> 45:08.020 bemerkt. 45:09.500 --> 45:10.700 Und da war ich ein bisschen sauer. 45:11.740 --> 45:16.640 Aber die wirklich spannende Frage, die man dann sicherlich auch 45:16.640 --> 45:19.680 prominent veröffentlichen können müsste, ist, wie ist das denn jetzt? 45:21.200 --> 45:25.260 Sagen wir mal, es ist nicht so, dass es einen konstanten Faktor 45:25.260 --> 45:28.740 Prozessoren gibt, die nichts zu tun haben, sondern ich habe eine H 45:28.740 --> 45:34.740 -Relation, wo die Knotengrade der Prozessoren sich so ein bisschen 45:34.740 --> 45:35.060 unterscheiden. 45:36.080 --> 45:40.460 Wo also die Gesamtzahl Kanten nicht die maximal mögliche ist für ein 45:40.460 --> 45:41.280 gegebenes H. 45:42.580 --> 45:47.120 Also in dem Fall, wenn man das ausrechnet, kommt man darauf, was ist, 45:47.200 --> 45:52.400 wenn ich eine H-Relation habe mit höchstens drei Achtel H mal P 45:52.400 --> 45:53.020 Paketen. 45:53.840 --> 45:54.500 Also Kanten. 45:56.380 --> 45:57.940 Geht es dann in H-Schritten? 45:58.380 --> 45:59.800 Statt sechs Fünftel H-Schritten? 46:02.580 --> 46:04.960 Also ich könnte mir vorstellen, dass das in vielen praktischen 46:04.960 --> 46:07.340 Anwendungen tatsächlich der Fall ist, dass da so eine gewisse 46:07.340 --> 46:11.100 Irregularität ist, dass es nur halt einzelne Prozessoren gibt, die ein 46:11.100 --> 46:14.480 Bottleneck darstellen und die anderen denen helfen könnten. 46:15.380 --> 46:18.040 Aber eben nicht so, dass die anderen gar nichts zu tun haben. 46:18.800 --> 46:21.140 Wie kann ich da den allgemeinen Fall abfackeln? 46:21.240 --> 46:25.100 Das ist meiner Meinung nach eine theoretisch sehr spannende Frage mit 46:25.100 --> 46:27.060 auch einer gewissen praktischen Rechtfertigung. 46:30.920 --> 46:34.360 Also wenn Sie dazu eine Idee haben, wird das vielleicht ein Zehn 46:34.360 --> 46:35.400 -Seiten -Algorithmus. 46:36.520 --> 46:39.260 Aber damit können Sie eine theoretische Masterarbeit schreiben. 46:39.320 --> 46:41.480 Sie müssen nichts implementieren, das haben Sie in zwei Wochen 46:41.480 --> 46:43.100 aufgeschrieben, wenn Sie Glück haben. 46:43.800 --> 46:47.580 Je nicht trivialer die Berechnung ist, die da im Hintergrund steht. 46:47.620 --> 46:48.860 Ich nenne Ihnen ein Beispiel. 46:49.720 --> 46:54.040 Ganz oft ist es so, Sie haben eigentlich einen Graphen, der Ihr 46:54.040 --> 46:55.080 Berechnungsproblem beschreibt. 46:55.880 --> 46:58.320 Zum Beispiel eine Diskretisierung von einem partiellen 46:58.320 --> 47:02.240 Differentialgleichungssystem, wo dann jeder Knoten, an dem Sie 47:02.240 --> 47:05.020 irgendwelche Näherungsrechnungen ausführen, ist ein Knoten in einem 47:05.020 --> 47:07.460 Graph und der hat halt Nachbarn. 47:07.580 --> 47:11.420 Oder Sie haben ein komplexes Netzwerk, ein soziales Netzwerk, Facebook 47:11.420 --> 47:14.800 -Graph, Web-Graph, bla bla bla, und wollen darauf irgendwelche 47:14.800 --> 47:16.300 Berechnungen durchführen. 47:16.300 --> 47:20.500 Und um das parallel zu machen, nehmen Sie einen Graph-Partitionierer 47:20.500 --> 47:25.240 oder einen Hypergraph-Partitionierer, der Ihnen das Ganze in Stücke 47:25.240 --> 47:25.800 zerlegt. 47:26.780 --> 47:29.520 Jeder Prozessor kriegt dann ein Stück von diesem Graphen. 47:30.540 --> 47:33.880 Und dann gibt es Kanten, die verlaufen zwischen mehreren Stücken. 47:34.400 --> 47:36.220 Da tritt dann Kommunikation auf. 47:37.000 --> 47:40.580 Und es ist eben tatsächlich so, je komplexer das Netzwerk ist, desto 47:40.580 --> 47:43.560 eher ist es dann so, dass es einzelne Prozessoren gibt, die sozusagen 47:43.560 --> 47:48.880 zentrale Stücke dieses Netzwerks bearbeiten müssen, wo dann mehr 47:48.880 --> 47:50.200 Kommunikation anfällt. 47:50.280 --> 47:53.100 Und andere sind irgendwo in der Peripherie, die müssen weniger 47:53.100 --> 47:53.940 kommunizieren. 47:54.700 --> 47:57.600 Und man muss sich aber insgesamt überlegen, wie schedule ich jetzt die 47:57.600 --> 47:59.640 Kommunikation zwischen den Prozessoren. 48:00.160 --> 48:03.720 Und da gibt es eben insbesondere auch viele Berechnungen, wo man dann 48:03.720 --> 48:05.320 immer wieder das Gleiche machen muss. 48:05.400 --> 48:07.700 Zum Beispiel, wenn Sie jetzt in einem Web-Graph einen Page-Rank 48:07.700 --> 48:11.500 berechnen wollen, müssen Sie im Prinzip immer eine Matrix-Vektor 48:11.500 --> 48:12.820 -Multiplikation durchführen. 48:13.880 --> 48:16.080 Irgendwie zehnmal, hundertmal oder sowas. 48:16.860 --> 48:21.620 Und wenn man da das Kommunikationsvolumen reduzieren will, muss man 48:21.620 --> 48:22.880 nämlich genau solche Dinge tun. 48:23.920 --> 48:26.100 Also es ist durchaus... tritt sowas auf. 48:30.230 --> 48:30.550 Gut. 48:32.110 --> 48:34.810 Dann habe ich schon gesagt, also diese Tatsache, dass ich künstlich 48:34.810 --> 48:38.750 meine Nachrichten in Stücke zerteile, will ich ja eigentlich in der 48:38.750 --> 48:39.310 Praxis nicht. 48:39.310 --> 48:46.110 Ich möchte lieber Algorithmen haben, die wenig Start-Ups machen. 48:46.690 --> 48:49.930 Zum Beispiel jeder hat drei Nachrichten nur oder fünf. 48:50.870 --> 48:53.350 Aber die haben halt sehr unterschiedliche Nachrichtenlängen. 48:54.550 --> 48:59.130 Dann müssten Sie die nach dem naiven Modell in ganz viele kleine 48:59.130 --> 49:03.890 Pakete zerhacken und in Größenordnung mehr Start-Ups machen, als wenn 49:03.890 --> 49:06.310 Sie irgendwie ein geschicktes Schedule haben, wo dann sagt, der 49:06.310 --> 49:10.310 schickt das Ding als Ganzes ab oder zwei Drittel seiner Nachrichten 49:10.310 --> 49:12.810 und dann irgendwann anders nochmal ein Stück oder so. 49:13.450 --> 49:17.990 Und leider ist es so, dass diese Scheduling-Algorithmen, die auf 49:17.990 --> 49:19.550 Kantenfärben beruhen, 49:23.190 --> 49:26.610 systematisch diese Nachrichten dann in kleine Stücke häckseln. 49:27.810 --> 49:29.970 Also die machen echt was kaputt. 49:30.610 --> 49:35.610 Die geben Ihnen eine elegante Lösung, wenn Sie nur diese H-Relationen 49:35.610 --> 49:40.410 betrachten, aber der Preis, den Sie bezahlen, sind viele Start-Ups. 49:41.170 --> 49:42.210 Das ist leider so. 49:45.890 --> 49:48.450 Dann Verbindungsnetzwerke, man hat vielleicht nicht überall gleich 49:48.450 --> 49:52.490 schnelle Kommunikation, will das irgendwie mit einpreisen und der 49:52.490 --> 49:54.570 Scheduling -Algorithmus sollte halt verteilt sein. 49:54.570 --> 49:59.250 Das heißt, eigentlich haben wir hier nur das, was ich Ihnen gerade 49:59.250 --> 50:01.630 erzählt habe, es ist ein schönes theoretisches Ergebnis, aber wie 50:01.630 --> 50:04.290 kriege ich den Gap zwischen Theorie und Praxis wieder raus? 50:04.490 --> 50:10.250 Also die Praxisantwort ist Vogel-Strauß-Algorithmus oder vielleicht 50:10.250 --> 50:13.350 noch diesen Zwei-Phasen-Algorithmus, den der Michael vorgestellt hat. 50:16.830 --> 50:22.510 Aber damit passieren dann halt üble Dinge, wenn man nicht triviale 50:22.510 --> 50:22.930 Fälle hat. 50:22.930 --> 50:26.250 Und da schlagen meine Mitarbeiter sich ständig gerade mit rum, weil 50:26.250 --> 50:30.250 wenn sie auf einem richtigen Super-Rechner nicht triviale Sachen 50:30.250 --> 50:34.230 machen, wo viel kommuniziert wird, dann ist völlig unvorhersagbar, wie 50:34.230 --> 50:35.990 schnell oder langsam das ist im Moment. 50:36.690 --> 50:39.710 Das heißt, da ist wirklich großer Handlungsbedarf aus meiner Sicht. 50:43.170 --> 50:48.170 Den Zwei-Phasen-Algorithmus hat der Michael vorgestellt, den will ich 50:48.170 --> 50:48.930 nicht nochmal wiederholen. 50:52.270 --> 50:54.370 Oder vielleicht nochmal kurz zur Erinnerung. 50:54.570 --> 50:56.910 Also hier habe ich jetzt zum Beispiel, wo diese Nachrichtenlängen alle 50:56.910 --> 50:57.790 unterschiedlich sind. 50:59.850 --> 51:04.470 Die werden zerhäckselt in p-Stücke, neu permutiert und oh Wunder, dann 51:04.470 --> 51:07.570 stehen lauter gleich lange Nachrichten, die ich jetzt austauschen 51:07.570 --> 51:07.870 kann. 51:08.390 --> 51:11.090 Und wenn ich die dann wieder zurücksortiere, oh Wunder, sind sie ja 51:11.090 --> 51:13.730 auch gleich lang und kann sie dann ausleichen. 51:14.110 --> 51:17.150 Das ist die Grundidee und dass das wirklich funktioniert, muss man 51:17.150 --> 51:18.870 sich dann im Detail ausrechnen. 51:19.670 --> 51:22.450 Gibt es noch Fragen zu dem Zwei-Phasen-Algorithmus? 51:23.650 --> 51:27.410 Oder zu diesem Simplex-Algorithmus mit dem Sechsfünftel? 51:28.130 --> 51:30.010 Da nochmal irgendwas erklären? 51:40.600 --> 51:44.900 Bei sehr großem p kann man dafür sorgen, dass man das nicht in ganz so 51:44.900 --> 51:46.180 viele Stücke teilen muss. 51:46.180 --> 51:48.480 Das will ich aber jetzt nicht viel dazu sagen. 51:49.380 --> 51:51.620 Was man sich auch überlegen kann, ist, wenn man jetzt ein 51:51.620 --> 51:57.740 unregelmäßiges Problem hat, das aber annähernd regelmäßig ist, dann 51:57.740 --> 52:00.720 kann man es in ein regelmäßiges Problem auflösen. 52:01.580 --> 52:02.660 Nehmen wir mal ein Beispiel. 52:02.940 --> 52:06.420 Hier ist es jetzt so, Sie könnten jetzt einfach die kürzeste Nachricht 52:06.420 --> 52:09.620 nehmen, das ist wahrscheinlich die da, und das hier überall 52:09.620 --> 52:10.420 abschneiden. 52:10.420 --> 52:16.260 Und dann tauschen Sie erstmal nur die Stücke aus, die so lang sind wie 52:16.260 --> 52:17.260 das kürzeste Problem. 52:17.960 --> 52:21.880 Da können Sie direkt ausliefern und danach kriegen Sie ein kleineres, 52:22.060 --> 52:25.660 aber noch irreguläres Problem und machen das mit dem Zwei-Phasen 52:25.660 --> 52:26.260 -Algorithmus. 52:27.280 --> 52:30.160 Der Nachteil ist, dann haben Sie statt zwei drei Phasen also nochmal 52:30.160 --> 52:34.040 mehr Startups, aber das Gesamtkommunikationsvolumen ist deutlich 52:34.040 --> 52:34.620 geschrumpft. 52:35.600 --> 52:37.480 Und da gibt es natürlich alle möglichen Kompromisse. 52:37.900 --> 52:41.580 Wer sagt mir, dass es nicht das Beste ist, nicht die kleinste 52:41.580 --> 52:45.700 Nachrichtenlänge zu nehmen, sondern vielleicht die zweitkleinste, dann 52:45.700 --> 52:50.020 kriege ich noch mehr Daten ausgeliefert, außer dass die kleinste dann 52:50.020 --> 52:52.520 so ein bisschen Dummy-Austausch stattfindet. 52:52.780 --> 52:54.700 Aber dafür ist das zweite Problem nochmal kleiner. 52:55.800 --> 52:57.740 Da muss man sich überhaupt mal überlegen, was ist denn da eigentlich 52:57.740 --> 52:58.980 die optimale Entscheidung? 52:59.080 --> 53:00.120 Wo sollte ich abschneiden? 53:00.200 --> 53:02.040 Hat auch noch keiner gemacht, soviel ich weiß. 53:02.860 --> 53:06.120 Das wäre auch eine Bachelor-Arbeit mindestens, oder vielleicht auch 53:06.120 --> 53:07.760 ein Startpunkt für eine Master-Arbeit. 53:12.240 --> 53:12.800 Genau. 53:14.560 --> 53:18.100 Dann möchte ich Ihnen ganz kurz noch einen dritten Ansatz erzählen, 53:18.160 --> 53:20.860 der nämlich dieses Startup-Problem löst. 53:21.000 --> 53:24.000 Nur zu dem Preis, dass Sie da nicht einen Faktor dreihalbe oder 53:24.000 --> 53:28.360 sechsfünftel investieren, sondern wieder einen Faktor zwei, so wie bei 53:28.360 --> 53:29.780 dem Zweiphasen-Algorithmus. 53:30.760 --> 53:33.080 Und außerdem Schedules berechnen müssen. 53:33.660 --> 53:36.000 Beim Zweiphasen-Algorithmus scannen Sie das Schedule. 53:36.000 --> 53:36.840 Ist das das Schöne? 53:37.180 --> 53:38.660 Hier müssen Sie es wirklich berechnen. 53:39.040 --> 53:43.980 Dafür ist die Anzahl Startup tatsächlich nur so groß wie die maximale 53:43.980 --> 53:46.580 Anzahl Nachrichten, an denen ein Prozessor beteiligt ist. 53:51.020 --> 53:54.380 Und die Idee dazu möchte ich Ihnen jetzt kurz vorstellen. 53:58.380 --> 54:01.300 Das ist eigentlich ein relativ simpler Greedy-Algorithmus. 54:02.200 --> 54:04.840 Also jeder Prozessor hat halt die Nachrichten, die er ausliefern will. 54:06.300 --> 54:09.540 Der Ansatz, den ich jetzt wähle, ist, nein, ich mache keine Helfer. 54:09.660 --> 54:10.540 Diesen Trick nehme ich nicht. 54:10.700 --> 54:12.020 Daten werden direkt ausgeliefert. 54:12.400 --> 54:14.460 Jetzt muss ich nur noch sagen, in welcher Reihenfolge. 54:15.340 --> 54:17.480 Was ist ein naheliegender Greedy-Algorithmus? 54:20.480 --> 54:23.220 Ja, man könnte sich vielleicht auch einen Sweep-Line-Algorithmus 54:23.220 --> 54:27.340 vorstellen, wie man ihn in Algo 2 bei den Geometrie-Algorithmen... 54:27.340 --> 54:30.140 Also ich simuliere sozusagen das, was passiert. 54:30.760 --> 54:32.900 Was sollte ich zum Zeitpunkt 0 tun? 54:34.260 --> 54:36.120 Ja, Nachrichten ausliefern. 54:36.800 --> 54:37.360 Welche? 54:38.400 --> 54:39.340 Antwort egal. 54:40.020 --> 54:40.580 Irgendwelche. 54:41.040 --> 54:44.520 Also am Anfang suche ich mir irgendwelche Nachrichten, die ich 54:44.520 --> 54:45.340 ausliefern kann. 54:46.140 --> 54:47.560 Von mir aus jetzt sequenziell. 54:47.820 --> 54:50.000 Sie gehen durch die Liste der Nachrichten. 54:50.800 --> 54:52.020 Die erste wird ausgeliefert. 54:52.200 --> 54:53.980 Also ich starte sofort, die auszuliefern. 54:54.340 --> 54:55.580 Dann gucke ich die zweite. 54:56.380 --> 54:59.560 Berührt die irgendwelche Prozessoren, die jetzt in dem Plan schon busy 54:59.560 --> 54:59.920 sind? 55:00.040 --> 55:01.820 Kann die also sofort starten, ja oder nein? 55:02.900 --> 55:04.540 Wenn ja, kommt sie ins Schedule. 55:04.860 --> 55:06.660 Wenn nein, wird sie zurückgestellt. 55:07.160 --> 55:11.940 So gehe ich durch alle Nachrichten und habe dann sozusagen eine 55:11.940 --> 55:16.260 unabhängige Menge von Nachrichten identifiziert, die unmittelbar 55:16.260 --> 55:21.420 ausgeliefert werden können und die sich gegenseitig nicht im Weg 55:21.420 --> 55:21.720 stehen. 55:22.840 --> 55:24.720 Die sind jetzt unterschiedlich lang. 55:25.820 --> 55:28.600 Vielleicht versuche ich jetzt doch mal live ein Bild dazu zu malen. 55:36.930 --> 55:40.930 Also ich habe hier so meinen Pool von Nachrichten, die ich verschicken 55:40.930 --> 55:41.270 will. 55:44.630 --> 55:46.690 Die Länge habe ich hier angegeben. 55:48.410 --> 55:49.530 Die nummeriere ich noch. 55:49.690 --> 55:52.050 1, 2, 3, 4, 5. 55:52.210 --> 55:53.350 Können Sie das hinten lesen? 55:54.330 --> 55:54.910 Ok. 55:55.830 --> 55:58.080 Sagen wir mal 4 Prozessoren. 56:02.670 --> 56:03.950 Hier ist Schritt 0. 56:04.270 --> 56:04.950 C gleich 0. 56:04.950 --> 56:11.770 Und sagen wir mal, ich kann die Nachricht 1, also nennen wir die 56:11.770 --> 56:15.570 Prozessoren A, B, C, D. 56:16.290 --> 56:18.110 Das ist von mir aus A nach B. 56:19.870 --> 56:21.550 Also steht hier die 1 drin. 56:23.070 --> 56:25.910 Und von mir aus das ist das hier C nach D. 56:28.790 --> 56:32.330 Also was ich am Anfang mache ist, dass die Nachrichten 1 und 3 56:32.330 --> 56:34.610 ausgeliefert werden und die machen die hier busy. 56:35.650 --> 56:39.570 Und jetzt sieht man, wenn ich in der Zeit weitergehe, irgendwann gibt 56:39.570 --> 56:43.070 es den erstmöglichen Zeitpunkt, wo ich wieder eine neue Nachricht 56:43.070 --> 56:44.350 losschicken kann. 56:45.530 --> 56:48.930 Und zwar frühestens ist das hier zu dem Zeitpunkt, wo die Nachricht 1 56:48.930 --> 56:51.530 ausgeliefert ist, sind A und B wieder idle. 56:56.600 --> 56:59.300 Jetzt müsste ich wahrscheinlich noch irgendwas anderes machen. 57:01.360 --> 57:03.700 Was weiß ich... 57:03.700 --> 57:04.940 Jetzt gibt es noch E und F. 57:05.760 --> 57:07.980 Und die liefern die Nachricht 4 aus. 57:12.170 --> 57:16.530 Die ist noch kürzer, also E und F sind dann irgendwann idle. 57:17.070 --> 57:20.790 Aber es gibt keine Nachricht mehr, die auch zwischen E und F ist, weil 57:20.790 --> 57:22.310 das macht ja auch keinen Sinn. 57:22.670 --> 57:24.630 Die hätte ich dann sowieso zusammengefasst schon. 57:25.730 --> 57:27.490 Das heißt, da mache ich erstmal gar nichts. 57:27.910 --> 57:31.550 Aber jetzt wäre das nächste Paar von Prozessoren frei und vielleicht 57:31.550 --> 57:35.430 ist ja jetzt die Nachricht 5 zwischen B und E. 57:39.030 --> 57:45.350 Dann würde ich sagen, jawohl, dann wird hier die 5 geschedult und hier 57:45.350 --> 57:45.670 auch. 57:47.270 --> 57:50.030 Und hier ist aber so ein Idle-Bereich, wo E nichts macht. 57:50.930 --> 57:52.050 Und so gehe ich weiter. 57:52.150 --> 57:54.610 Ich suche mir immer den frühesten Zeitpunkt, wo ich irgendeine 57:54.610 --> 57:56.570 Nachricht in dieses Schedule einfügen kann. 57:57.910 --> 58:02.270 Und dann wird die aber zu dem Zeitpunkt geschickt, und zwar komplett 58:02.270 --> 58:02.970 und direkt. 58:03.410 --> 58:04.150 Ohne Umwege. 58:05.270 --> 58:07.910 Und dann kann man sich die Frage stellen, wie lang wird dieses 58:07.910 --> 58:08.390 Schedule? 58:09.070 --> 58:12.590 Und das habe ich dann dem Kollegen Roberto Solis-Ober wieder erklärt, 58:12.690 --> 58:16.730 der halt so ein Experte für Packing-Probleme, Scheduling und sowas 58:16.730 --> 58:16.950 ist. 58:16.950 --> 58:22.090 Und der hat gesagt, ganz einfach, kann man nicht publizieren. 58:23.150 --> 58:25.080 Aber hier ist der Beweis, 5 Zeilen. 58:27.710 --> 58:32.090 Und was der dann halt gezeigt hat, dass die Gesamt-Makespan ist dann 58:32.090 --> 58:33.910 nur zweimal die untere Schranke. 58:34.570 --> 58:35.670 Und das fand ich eigentlich spannend. 58:39.030 --> 58:42.010 Ich habe hier jetzt diesen Algorithmus nochmal ein bisschen als 58:42.010 --> 58:46.090 Pseudocode formuliert. 58:47.890 --> 58:50.210 Ich habe ein Schedule, das ist am Anfang leer. 58:50.350 --> 58:54.030 Es gibt eine Menge M der Nachrichten, die noch ausgeliefert werden 58:54.030 --> 58:54.330 sollen. 58:54.650 --> 58:59.050 Solange M nicht leer ist, also solange noch was auszuliefern ist, man 58:59.050 --> 59:03.950 suche sich den ersten Zeitpunkt, sodass es eine Nachricht aus M gibt. 59:04.730 --> 59:12.510 Mit der Tatsache, dass der Start und Ziel dieser Nachricht zum 59:12.510 --> 59:15.910 Zeitpunkt T arbeitslos sind. 59:16.970 --> 59:18.630 Und zwar in dem Schedule S. 59:19.950 --> 59:23.150 Und dann erweitere ich das Schedule darüber, dass ich sage, naja, 59:23.290 --> 59:26.690 starte die Übertragung von Nachricht M zum Zeitpunkt T. 59:27.330 --> 59:30.150 Und entferne klein M aus groß M. 59:30.650 --> 59:35.550 Und das ist jetzt sehr generisch, da gibt es verschiedene Arten, wie 59:35.550 --> 59:39.470 man jetzt da die Auswahl treffen kann, wenn es mehrere gleiche 59:39.470 --> 59:40.150 Nachrichten gibt. 59:41.670 --> 59:47.910 Wir haben dann einen Algorithmus angegeben, der eine Prioritätsliste 59:47.910 --> 59:50.030 hat, die logarithmische Zeit braucht. 59:50.970 --> 59:55.150 Man braucht dann eine oder konstant viele Prioritätslisten-Operationen 59:55.150 --> 59:56.030 pro Nachricht. 59:56.830 --> 01:00:01.150 Und man hat außerdem so eine Bitvector-Operation, die auf P-Bits 01:00:01.150 --> 01:00:01.490 agiert. 01:00:01.490 --> 01:00:06.430 Wenn jetzt p klein ist, sagen wir mal kleiner 512 oder so, können Sie 01:00:06.430 --> 01:00:12.490 das mit einer Bitwise-Logical-Operation sehr schnell berechnen. 01:00:14.530 --> 01:00:18.710 Also es ist dann sowas wie für kleine p near linear, aber eigentlich 01:00:18.710 --> 01:00:19.490 ist es quadratisch. 01:00:21.790 --> 01:00:25.350 Aber mit der Konstante so klein, dass das für kleine p keine Rolle 01:00:25.350 --> 01:00:25.770 spielt. 01:00:27.650 --> 01:00:30.610 Ist aber immer noch zentralisiert, dieser Algorithmus. 01:00:30.830 --> 01:00:32.110 Das ist ein bisschen das Blöde. 01:00:32.630 --> 01:00:35.130 Wir hätten gerne einen verteilten Algorithmus, der das kann. 01:00:35.290 --> 01:00:36.910 Ist auch eine spannende, offene Frage. 01:00:45.370 --> 01:00:48.990 Und da hatte ich jetzt tatsächlich eine Studienarbeit dazu, das ist 01:00:48.990 --> 01:00:50.210 auch schon eine ganze Weile her. 01:00:50.850 --> 01:00:54.030 Der Student war jetzt nicht der beste Student, den ich je hatte. 01:00:54.210 --> 01:00:56.270 Also ich weiß nicht, ob der da irgendwelchen Mist gebaut hat. 01:00:56.990 --> 01:01:00.910 Mit unserem neuen Wissen darüber, wie schlecht MPI-Implementierungen 01:01:00.910 --> 01:01:03.670 sind, glaube ich, das größere Problem war, dass die MPI 01:01:03.670 --> 01:01:05.430 -Implementierungen irgendwie scheiße bauen. 01:01:08.970 --> 01:01:12.570 Also wir konnten da keine Vorteile entdecken gegenüber dem Vogelstrauß 01:01:12.570 --> 01:01:13.170 -Algorithmus. 01:01:13.310 --> 01:01:15.730 Das war leider die Conclusion. 01:01:15.730 --> 01:01:17.850 Oder nichts Reproduzierbares zumindest. 01:01:18.710 --> 01:01:22.830 Ein Problem ist auch, dass das hier ist jetzt erstmal im Simplex 01:01:22.830 --> 01:01:23.470 -Modell wieder. 01:01:23.930 --> 01:01:26.890 Aber die realen Netzwerke sind eher duplex. 01:01:27.670 --> 01:01:30.530 Und die Verallgemeinerung hat irgendwie erst recht nichts gebracht. 01:01:33.230 --> 01:01:36.430 Theoretiker können fragen, gibt es bessere Approximations-Algorithmen 01:01:36.430 --> 01:01:37.630 als diesen Faktor 2? 01:01:39.210 --> 01:01:40.490 Das könnte auch spannend sein. 01:01:40.550 --> 01:01:43.690 Und eben parallele Scheduling-Algorithmen für dieses Ding. 01:01:44.610 --> 01:01:50.230 Also ein paralleler Algorithmus, der diese Schranke erreicht, wäre 01:01:50.230 --> 01:01:50.630 cool. 01:01:53.440 --> 01:01:57.250 Dann würde vielleicht sowas da stehen wie K mal irgendwas 01:01:57.250 --> 01:01:58.890 Polylogarithmisches. 01:01:59.210 --> 01:02:03.610 Für jeden Schritt müssen die Prozessoren irgendwie was tun. 01:02:04.050 --> 01:02:05.010 Das wäre auch schon spannend. 01:02:11.420 --> 01:02:14.040 Also fassen wir mal zusammen, was wir über All-to-All gelernt haben. 01:02:14.040 --> 01:02:20.720 Es gibt den Vogel-Strauß-Algorithmus, also Abwälzen dieses kollektiven 01:02:20.720 --> 01:02:21.060 Kommunikationsproblems. 01:02:22.860 --> 01:02:28.260 Datenauslieferung auf einen asynchron ablaufenden Online-Algorithmus. 01:02:28.600 --> 01:02:31.160 Also im Prinzip den Routing-Algorithmus und den Flusskontroll 01:02:31.160 --> 01:02:33.900 -Algorithmus, der irgendwo unten tief im Netzwerk steckt. 01:02:34.780 --> 01:02:37.260 Auf den ich eigentlich sehr wenig Einfluss habe. 01:02:39.200 --> 01:02:43.600 Dann gibt es den Zwei-Phasen-Algorithmus mit der Verfeinerung, dass 01:02:43.600 --> 01:02:45.820 man vielleicht einen regulären Teil abspalten kann. 01:02:47.220 --> 01:02:51.600 Dann gibt es den nicht präemptiven Algorithmus, den ich Ihnen als 01:02:51.600 --> 01:02:52.900 letztes vorgestellt habe. 01:02:53.560 --> 01:02:57.660 Der minimiert die Start-Ups, erhöht das Kommunikationsvolumen um einen 01:02:57.660 --> 01:03:00.260 Faktor 2, genau wie dieser Zwei-Phasen-Algorithmus. 01:03:03.460 --> 01:03:05.260 Braucht dabei eine zentralisierte Berechnung. 01:03:06.060 --> 01:03:08.080 Im Gegensatz zu dem Zwei-Phasen-Algorithmus. 01:03:08.560 --> 01:03:11.840 Dann gibt es diese färbungsbasierten Algorithmen, die irgendwie fast 01:03:11.840 --> 01:03:15.360 optimal sind bei großen Paketen, aber relativ komplex. 01:03:15.420 --> 01:03:17.160 Wir haben keine verteilte Implementierung. 01:03:19.080 --> 01:03:21.140 Also das sind alles legitime Ansätze. 01:03:22.880 --> 01:03:26.280 Wobei der Vogel-Strauß, der ist legitimiert dadurch, dass er verwendet 01:03:26.280 --> 01:03:29.020 wird, aber für einen Theoretiker irgendwie ein rotes Tuch. 01:03:29.020 --> 01:03:33.920 Wir können nur noch keinen Ersatz angeben, der konsistent immer besser 01:03:33.920 --> 01:03:34.200 ist. 01:03:34.280 --> 01:03:35.020 Das wäre das Schöne. 01:03:36.120 --> 01:03:39.520 Der nie schlechter ist und in schwierigen Fällen besser. 01:03:39.640 --> 01:03:41.360 Das wäre das, was ich gerne hätte. 01:03:43.140 --> 01:03:46.020 Das bleibt weiterhin ein Forschungsthema. 01:03:47.620 --> 01:03:50.560 Wie gesagt, ich habe da 2000 mit angefangen und seitdem hat sich 01:03:50.560 --> 01:03:51.560 eigentlich nicht viel getan. 01:03:51.560 --> 01:03:56.860 Die Community scheint sich nicht dafür zu interessieren, weil die 01:03:56.860 --> 01:04:00.420 Praktiker, die machen einfach ihre Simulationsanwendungen und 01:04:00.420 --> 01:04:04.020 schimpfen dann auf das Betriebssystem, wenn es nicht schnell ist. 01:04:04.980 --> 01:04:07.260 Und die Theoretiker machen ganz andere Sachen. 01:04:09.140 --> 01:04:14.340 Die Library-Entwickler von MPI, die haben wahrscheinlich Probleme 01:04:14.340 --> 01:04:17.140 überhaupt irgendwie immer die neuesten Betriebssystem-Versionen zu 01:04:17.140 --> 01:04:19.300 tracken und interessieren sich auch nicht für Algorithmen. 01:04:20.020 --> 01:04:21.680 Aber ich finde es schon ziemlich wichtig. 01:04:21.980 --> 01:04:24.400 Ich glaube, man hätte damit auch Impact, wenn man da mal ein bisschen 01:04:24.400 --> 01:04:26.360 Manpower investieren würde. 01:04:29.670 --> 01:04:33.330 Es gibt noch allgemeinere Probleme irgendwie. 01:04:33.790 --> 01:04:37.990 Hier haben wir jetzt immer Punkte-Punkt-Auslieferungen und 01:04:37.990 --> 01:04:40.110 andererseits hatten wir Broadcasting-Algorithmen. 01:04:40.110 --> 01:04:44.730 Es gibt aber auch Multicast oder Multi-Commodity-Multicast. 01:04:44.910 --> 01:04:47.690 Also im Allgemeinen können viele Nachrichten unterwegs sein, aber 01:04:47.690 --> 01:04:50.630 einige davon werden an mehrere andere geschickt. 01:04:51.770 --> 01:04:54.570 Und da kann ich mir natürlich noch allgemeinere Scheduling-Algorithmen 01:04:54.570 --> 01:04:55.410 ausdenken. 01:04:56.050 --> 01:04:58.490 Sowas wird tatsächlich auch erforscht, allerdings nicht bei den 01:04:58.490 --> 01:05:02.010 Parallelrechner -Leuten, sondern bei den Storage-Area-Network-Leuten, 01:05:02.130 --> 01:05:02.910 habe ich das mal gesehen. 01:05:04.270 --> 01:05:06.310 Aber damit will ich Sie hier nicht belästigen. 01:05:06.430 --> 01:05:07.870 Nur so ein Blick über den Tellerrand. 01:05:11.930 --> 01:05:14.430 Das nächste wären parallele Prioritätslisten. 01:05:14.930 --> 01:05:17.810 Michael hat aber auch schon angefangen, MSTs zu machen. 01:05:18.490 --> 01:05:21.550 Aber in der letzten Viertelstunde möchte ich damit nicht loslegen, 01:05:21.670 --> 01:05:23.870 dann machen wir heute doch schon die Vorlesungs-Evaluation. 01:05:24.990 --> 01:05:26.730 Michael verteilt mal die Zettel. 01:05:27.450 --> 01:05:29.750 Wäre einer von Ihnen bereit, die dann abzugeben? 01:05:30.570 --> 01:05:33.150 Weil eigentlich dürfen wir die ja nicht mehr anfassen. 01:05:36.490 --> 01:05:38.490 Das steht, glaube ich, auf diesem Deckblatt da. 01:05:38.670 --> 01:05:39.810 Hast du das mit, Michael? 01:05:42.430 --> 01:05:44.950 Ja, ich glaube, inzwischen sehen die das nicht mehr so wild. 01:05:45.070 --> 01:05:46.570 Würdest du es dann einfach abgeben müssen? 01:05:46.670 --> 01:05:47.350 Mir ist das egal. 01:05:48.370 --> 01:05:51.210 Also wenn jemand nicht will, dass wir das einsammeln, dann soll er 01:05:51.210 --> 01:05:52.210 sich jetzt melden. 01:05:52.890 --> 01:05:54.670 Und sonst machen wir das. 01:05:55.590 --> 01:05:58.270 Gibt es noch weitere Fragen zur Vorlesung? 01:05:59.170 --> 01:06:00.350 Auch allgemein? 01:06:01.770 --> 01:06:02.130 Übungen? 01:06:02.310 --> 01:06:03.490 Kann ich nicht so viel dazu sagen. 01:06:03.610 --> 01:06:04.930 Ich könnte versuchen, etwas zu sagen. 01:06:08.130 --> 01:06:10.350 Ich glaube, man sitzt in der vierten Person. 01:06:34.930 --> 01:06:36.470 Wir sind dann gegen den Beginn des Semesters. 01:06:37.750 --> 01:06:42.630 Ich gebe dem Michael dann mal drei Termine mit. 01:06:44.090 --> 01:06:48.530 Schicken Sie mir dann eine E-Mail mit Ihrem Präferenztermin und ich 01:06:48.530 --> 01:06:51.670 antworte dann der und der Zeitslot. 01:06:52.710 --> 01:06:54.970 Und wenn da irgendwas nicht klappt, kriegen wir das auch gelöst.