WEBVTT 00:10.090 --> 00:13.230 Willkommen zur dritten Vorlesung Parallele Algorithmen. 00:13.810 --> 00:14.970 Mein Name ist Michael Axtmann. 00:15.650 --> 00:18.930 Ich bin Doktorand am Lehrstuhl von Peter Sanders. 00:20.350 --> 00:23.270 Professor Peter Sanders wird nicht alle Vorlesungen halten können, 00:23.410 --> 00:27.110 weil er ziemlich mit Antragsschreiben für den Exzellenzcluster 00:27.110 --> 00:30.230 verbucht ist. 00:30.750 --> 00:33.970 Ich werde ihm aber kurzfristig die Vorlesung übernehmen, wenn er keine 00:33.970 --> 00:34.430 Zeit hat. 00:35.170 --> 00:38.230 Ich hoffe, es kommt nicht zu häufig vor, aber ein bisschen Abwechslung 00:38.230 --> 00:41.110 für euch ist wahrscheinlich auch nicht schlecht, die Sachen immer mal 00:41.110 --> 00:43.050 wieder ein bisschen von einer anderen Seite, von einem anderen 00:43.050 --> 00:45.070 Gesichtspunkt erklärt zu bekommen. 00:46.530 --> 00:48.390 Und ihr seht immer mal wieder ein anderes Gesicht. 00:50.610 --> 00:53.910 Die Vorlesungsfolien sind, glaube ich, schon auf der Vorlesungsseite 00:53.910 --> 00:54.510 verlinkt. 00:55.050 --> 00:58.010 Die könnt ihr schon zugreifen und euch runterladen. 00:58.250 --> 01:00.050 Es gibt auch ein gutes Skript, finde ich. 01:00.210 --> 01:04.210 Ich habe damals die Vorlesung vor fünf Jahren gehört und prüfen 01:04.210 --> 01:04.470 lassen. 01:05.090 --> 01:07.790 Ich habe auch ziemlich viel mit dem Skript gearbeitet. 01:08.290 --> 01:11.770 Ich habe dann halt in der Vorlesung Notizen auf dem Ausdruck gemacht 01:11.770 --> 01:14.590 und dann irgendwie das Skript nochmal durchgearbeitet und 01:14.590 --> 01:15.910 Prüfungsprotokolle gelesen. 01:15.990 --> 01:17.310 Das hat eigentlich ganz gut gepasst. 01:18.150 --> 01:20.830 Also vom Material her, finde ich, seid ihr einigermaßen gut 01:20.830 --> 01:21.390 vorbereitet. 01:22.010 --> 01:30.950 Wenn nicht, könnt ihr auch jederzeit dem Übungsleiter Sebastian Lamb 01:30.950 --> 01:35.130 eine E-Mail schreiben oder mich einfach nach der Vorlesung fragen oder 01:35.130 --> 01:39.050 mir eine E-Mail schreiben oder bei mir im Büro vorbeikommen. 01:39.150 --> 01:40.130 Wir sitzen im zweiten Stock. 01:42.170 --> 01:47.390 Ich nehme an, dass ihr das letzte Mal an dieser Stelle hier aufgehört 01:47.390 --> 01:48.330 habt mit der Vorlesung. 01:49.990 --> 01:50.890 Liege ich da richtig? 01:51.990 --> 01:54.610 Das dürfte so die letzte Folie gewesen sein, bei der ihr wart. 01:58.780 --> 02:01.120 Okay, dann fangen wir nochmal ein bisschen weiter hinten an. 02:01.120 --> 02:04.400 Also Analyse von parallelen Algorithmen kennt ihr jetzt wahrscheinlich 02:04.400 --> 02:05.580 schon aus der letzten Vorlesung. 02:05.680 --> 02:06.440 Nehme ich mal stark an. 02:07.280 --> 02:07.900 Liege ich da richtig? 02:08.080 --> 02:08.260 Okay. 02:08.740 --> 02:09.440 Also Analyse. 02:09.900 --> 02:12.080 Letztendlich, man analysiert parallele Algorithmen. 02:12.520 --> 02:15.940 Was ist die Work, was ist der Speedup, was ist der absolute Speedup 02:15.940 --> 02:17.340 und was ist die Effizienz? 02:17.620 --> 02:19.900 Okay, allgemeines Nicken, nochmal kurz zur Wiederholung. 02:22.120 --> 02:26.420 Wir hatten schon das PRAM-Modell kennengelernt. 02:26.420 --> 02:28.000 Das war ziemlich einfach. 02:28.780 --> 02:31.800 Man hat einen globalen Speicher, auf den alle zugreifen. 02:32.560 --> 02:34.740 Das ist aber nicht wirklich realistisch. 02:35.340 --> 02:38.600 Da unter anderem, wenn man auf einen großen Speicher parallel 02:38.600 --> 02:45.440 zugreift, da eine große Congestion und sehr viele Zugriffe drauf hat. 02:45.700 --> 02:50.080 Und deswegen gibt es verschiedene andere Modelle, die in der Regel 02:50.080 --> 02:54.240 komplexer sind, aber die Realität Stückchen für Stückchen immer besser 02:54.240 --> 02:54.860 nachbilden. 02:54.860 --> 02:56.600 Umso komplexer sie werden. 02:57.820 --> 03:02.100 Und die Modelle möchte ich jetzt heute vorstellen und noch ein 03:02.100 --> 03:05.700 bisschen weitergehende, grundlegende Sachen erklären, die für die 03:05.700 --> 03:06.920 Vorlesung wichtig sein werden. 03:07.980 --> 03:13.080 Also hier zum Beispiel das Modell mit verteiltem Speicher, in dem wir 03:13.080 --> 03:16.080 P -Prozessoren haben, 0 bis P-1. 03:16.920 --> 03:21.720 Und jeder Prozessor hat eben seine eigene Recheneinheit, hat eigene 03:21.720 --> 03:26.340 Register, eine konstante Anzahl von Registern, hat einen Cache, hat 03:26.340 --> 03:30.900 einen lokalen Speicher und die verschiedenen Prozessoren kommunizieren 03:30.900 --> 03:34.200 unter anderem ausschließlich über ein Verbindungsnetzwerk. 03:35.740 --> 03:39.380 Das heißt, wenn ein Prozessor Daten von einem anderen Prozessor haben 03:39.380 --> 03:43.260 möchte, muss Nachrichtenaustausch ausgeführt werden. 03:43.860 --> 03:47.020 Prozessor I muss zum Beispiel eine Nachricht an Prozessor J schicken, 03:48.600 --> 03:54.700 damit dieser mit den Daten von Prozessor I weiter Berechnungen 03:54.700 --> 03:55.600 ausführen kann. 03:56.220 --> 04:04.700 Im Vergleich dazu das Modell mit gemeinsamen Speicher. 04:05.020 --> 04:07.160 Wir haben eben hier jetzt auch wieder P-Prozessoren. 04:07.600 --> 04:11.020 Jeder Prozessor hat aber nur seine eigene Recheneinheit, eigene 04:11.020 --> 04:16.720 Register, einen eigenen Cache und greift dann über ein Netzwerk auf 04:16.720 --> 04:19.780 ein oder mehrere Speichermodule zu. 04:20.660 --> 04:23.720 Im Vergleich zum PRAM, da hatte man ja nicht wirklich ein Netzwerk, 04:23.820 --> 04:25.940 sondern hat einfach auf den Speicher zugegriffen. 04:26.260 --> 04:29.720 Hier modelliert man den Speicher jetzt eben explizit mit und hat 04:29.720 --> 04:32.840 verschiedene oder ein oder mehrere Speichermodule. 04:34.600 --> 04:42.040 Wenn also ein Prozessor Informationen sich besorgen möchte, dann 04:42.040 --> 04:46.080 greift er in der Regel über das Netzwerk auf den Speicher zu, lädt 04:46.080 --> 04:49.980 sich dort Informationen und wenn er Daten von anderen Prozessen haben 04:49.980 --> 04:55.060 möchte, werden diese Daten von diesem anderen Prozess erst in den 04:55.060 --> 04:58.800 Speicher reingeschrieben, über das Netzwerk und vom nächsten Prozess 04:58.800 --> 05:00.720 dann wieder aus dem Speicher ausgelesen. 05:04.000 --> 05:07.780 Bei diesem Modell treten verschiedenste Schwierigkeiten auf. 05:08.920 --> 05:12.560 Zum einen ist die Ausführung asynchron, sprich die verschiedenen 05:12.560 --> 05:18.780 Prozessoren arbeiten nicht Schritt für Schritt parallel jeweils eine 05:18.780 --> 05:24.560 Instruktion ab, sondern die Ausführungspfade sind asynchron und es ist 05:24.560 --> 05:29.140 nicht klar, wann wer welche Operation ausführt aus der Sicht eines 05:29.140 --> 05:30.020 einzelnen Prozessors. 05:30.980 --> 05:35.760 Dies macht die Analyse, den Entwurf, die Implementierung schwerer und 05:35.760 --> 05:38.840 natürlich auch das Debugging, weil wenn man die Sicht von einem 05:38.840 --> 05:42.080 Prozessor jetzt gerade sieht, weiß man nicht unbedingt zu jedem 05:42.080 --> 05:43.900 Zeitpunkt, was die anderen Prozessoren machen. 05:45.920 --> 05:53.340 Zusätzlich entsteht natürlich dadurch, dass wir nicht einen globalen 05:53.340 --> 05:57.220 Speicher haben, sondern mehrere Speichermodule, kann Concession, also 05:57.220 --> 05:59.640 Stau auf einem Speichermodul auftreten. 06:00.020 --> 06:03.780 Das heißt, wenn mehrere Prozessorendaten vom kleinen Speichermodul 06:03.780 --> 06:10.860 über das Netzwerk laden, dann kann nicht jeder Prozessor ein Element 06:10.860 --> 06:16.760 laden, sondern im Worst Case kann es eben sein, dass wir eine lineare 06:16.760 --> 06:20.380 Verzögerung haben, sprich wenn P-Prozessoren zum Beispiel ein globales 06:20.380 --> 06:28.800 Ohr ausführen, also jeder ein Datum in eine bestimmte Speicherzelle 06:28.800 --> 06:33.140 reinschreiben möchte, dann kann das eben Theta von P-Zeit benötigen. 06:35.820 --> 06:39.660 Zusätzlich haben wir natürlich eine gewisse Imbalance zwischen einem 06:39.660 --> 06:44.620 globalen Speicher, der einigermaßen langsam ist, und einem lokalen 06:44.620 --> 06:46.220 Speicher, der ziemlich schnell ist. 06:47.600 --> 06:52.880 Und in der Regel führt es dazu, dass die Zugriffe in der Regel durch 06:52.880 --> 06:56.880 die Laufzeiten oder durch die Antwortzeiten vom globalen Speicher eher 06:56.880 --> 06:57.540 dominiert werden. 07:00.140 --> 07:04.200 Zusätzlich kommt hinzu, dass wir jetzt ein neues zusätzliches Netzwerk 07:04.200 --> 07:07.700 modelliert haben und wenn die Anzahl Prozessoren steigt, wird dieses 07:07.700 --> 07:10.860 Netzwerk eben immer komplizierter und komplizierter in der Realität, 07:11.380 --> 07:16.240 um eben die Zugriffszeiten auf den Speicher zu garantieren, die wir 07:16.240 --> 07:18.620 als Entwickler erwarten. 07:23.060 --> 07:26.720 Deshalb gibt es verschiedenste andere realistische Shared-Memory 07:26.720 --> 07:27.120 -Modelle. 07:28.740 --> 07:32.520 Was wir auf jeden Fall haben wollen, ist eben die Asynchronität, was 07:32.520 --> 07:39.660 man häufig in der Realität hat, ist, wenn man eben Operationen auf dem 07:39.660 --> 07:43.560 globalen Speicher ausführt, dass wir einmal einen concurrent read 07:43.560 --> 07:46.500 haben und einen queued write. 07:46.680 --> 07:49.400 Das heißt, wenn mehrere Prozessoren gleichzeitig auf eine 07:49.400 --> 07:54.680 Speicherstelle zugreifen wollen, dann werden die Zugriffe darauf 07:54.680 --> 07:59.140 irgendwie sequenziell ausgeführt und brauchen eben nicht mehr O von 1 07:59.140 --> 07:59.720 Zeit. 08:01.680 --> 08:06.020 Und deshalb muss man sich eben anderen Hilfsmitteln, anderen 08:06.020 --> 08:12.440 Programmierhilfsmitteln bedienen, insbesondere um die Speicherzugriffe 08:12.440 --> 08:18.180 zu koordinieren, benutzt man zum Beispiel atomare Instruktionen, um zu 08:18.180 --> 08:21.600 garantieren, dass wenn man selbst zwei Operationen ausführt, zum 08:21.600 --> 08:26.840 Beispiel ein bestimmtes Datum lesen und danach erhöhen, dass dies dann 08:26.840 --> 08:28.380 auch wirklich atomar geschieht. 08:29.620 --> 08:36.760 Darüber hinaus hat man in realen Implementierungen von den Modellen 08:36.760 --> 08:40.440 letztendlich immer Speicherhierarchien, die man eben auch 08:40.440 --> 08:46.340 berücksichtigen muss, insbesondere, dass man weiß, dass die Daten, die 08:46.340 --> 08:48.220 man selbst verarbeitet, konsistent bleiben. 08:48.800 --> 08:51.900 Sprich, wenn man Daten in einer bestimmten Hierarchie-Ebene speichert, 08:53.080 --> 08:56.600 kann es sein, dass andere Prozesse in einer anderen Speicherhierarchie 08:56.600 --> 09:00.560 die Daten zum gleichen Zeitpunkt verändern und die Daten, die man 09:00.560 --> 09:02.100 selbst hält, nicht mehr aktuell sind. 09:06.360 --> 09:08.280 Diese Folie hier kennt ihr auch noch nicht? 09:08.960 --> 09:09.760 Die kennt ihr schon. 09:10.360 --> 09:12.220 Okay, deswegen überspringe ich die. 09:12.300 --> 09:13.980 Das sind jetzt hier Implementierungsdetails. 09:14.120 --> 09:16.840 Es würde zu weit gehen, wenn ich das alles nochmal hier wiederhole. 09:17.440 --> 09:20.820 Wir haben dann auch noch das parallele externe Modell. 09:21.360 --> 09:26.120 Beim parallelen externen Modell haben wir wieder verschiedene 09:26.120 --> 09:32.480 Recheneinheiten, die jeweils lokale Register haben und einen eigenen 09:32.480 --> 09:34.760 lokalen Speicher der Größe M, der ist fix. 09:35.360 --> 09:39.420 Und wir haben einen globalen Speicher, und da kann jeder Prozess aus 09:39.420 --> 09:48.800 diesem globalen Speicher während einer Zeiteinheit eine Menge von B 09:48.800 --> 09:52.020 -Wörtern aus diesem Speicher lesen oder schreiben. 09:52.900 --> 09:55.860 Und das können alle zum gleichen Zeitpunkt parallel machen. 09:55.860 --> 09:59.820 Man muss natürlich darauf achten, wenn verschiedene Prozessoren auf 09:59.820 --> 10:06.000 das gleiche Element zugreifen, dass diese Zugriffe koordiniert werden. 10:06.120 --> 10:09.080 Das habt ihr ja in der letzten Vorlesung mit concurrent read, 10:09.140 --> 10:11.880 concurrent write und so weiter schon mitbekommen. 10:14.940 --> 10:20.040 Im Folgenden möchte ich mich ein bisschen weiter auf Modelle mit 10:20.040 --> 10:26.340 Verbindungsnetzwerken fokussieren, weil diese Modelle in unserer 10:26.340 --> 10:29.260 Vorlesung eigentlich das Augenmerk haben. 10:30.660 --> 10:33.160 Also nochmal Modelle mit Verbindungsnetzwerken. 10:34.120 --> 10:36.900 Wir haben wieder P-Prozessoren, 0 bis P-1. 10:37.420 --> 10:41.220 Jeder Prozessor hat seine eigene Recheneinheit, eigene Register, einen 10:41.220 --> 10:46.360 eigenen kleinen Speicher und kommuniziert wird zwischen den 10:46.360 --> 10:47.760 Prozessoren über dieses Netzwerk. 10:48.600 --> 10:51.680 Die einzelnen Prozessoren sind also eigenständige RAM-Maschinen, 10:51.680 --> 11:00.220 laufen aber untereinander asynchron und interagieren zwischen den RAM 11:00.220 --> 11:02.700 -Maschinen über Nachrichtenaustausch. 11:03.880 --> 11:09.500 Und jetzt ist eben im Folgenden zu erörtern, wie lange solche 11:09.500 --> 11:13.800 Nachrichtenaustausche dauern und das hängt natürlich vom Netzwerk ab. 11:14.020 --> 11:17.200 Es hängt vom Netzwerk ab, es hängt von verschiedenen Faktoren ab. 11:18.160 --> 11:23.340 Hier eine immer noch ziemliche Vereinfachung von einem heutigen 11:23.340 --> 11:26.100 Rechner, in dem wir Hauptspeicher haben. 11:26.200 --> 11:29.360 Wir haben Level 3 Cache, wir haben Level 2, Level 1 Cache. 11:30.200 --> 11:35.080 Wir haben verschiedenste Recheneinheiten, wir haben verschiedenste 11:35.080 --> 11:36.980 externe Speichermedien usw. 11:40.540 --> 11:44.580 Und letztendlich möchte man, wenn man Algorithmen entwirft, diese 11:44.580 --> 11:52.140 Komplexität loswerden und Algorithmen entwickeln, die in der Theorie 11:52.140 --> 11:56.560 analysierbar sind und die Laufzeiten, die man da sich berechnet hat, 11:56.880 --> 12:01.520 auf realen Maschinen mit wirklichen Implementierungen irgendwie 12:01.520 --> 12:02.220 übereinstimmen. 12:04.120 --> 12:09.160 Und was man eben mit der Zeit gesehen hat, naja, solange man flache 12:09.160 --> 12:14.160 Hierarchien hat, also flache Modelle, sprich, man nimmt jetzt einfach 12:14.160 --> 12:20.640 mal an, wir haben ein Verbindungsnetzwerk, mit dem die Prozessoren 12:20.640 --> 12:25.180 verbunden sind, über dem sie kommunizieren können und innerhalb von 12:25.180 --> 12:28.200 einer Recheneinheit, innerhalb von einem Prozessor, haben wir 12:28.200 --> 12:30.000 vielleicht noch mehrere Cores. 12:31.180 --> 12:33.780 Das ist so ein zweistufiges Netzwerk, wo die Cores untereinander 12:33.780 --> 12:38.660 kommunizieren können und die Prozessoren oder die Maschinen selbst 12:38.660 --> 12:41.280 kommunizieren über ein Verbindungsnetzwerk. 12:41.280 --> 12:45.620 Dann hat man zwei Ebenen und mit dieser Abstraktion kann man 12:45.620 --> 12:48.460 eigentlich noch ganz gut programmieren, indem man sagt, naja, auf der 12:48.460 --> 12:52.040 obersten Ebene schreiben wir einfach ein verteiltes Programm mit 12:52.040 --> 12:56.420 Nachrichtenaustausch und wenn man sein Programm noch ein bisschen 12:56.420 --> 13:01.440 tunen möchte, dann implementiert man auf der feinkranularen Ebene, 13:01.600 --> 13:06.320 also innerhalb eines Prozessors mit mehreren Cores, noch ein Shared 13:06.320 --> 13:07.280 -Memory -Unterprogramm. 13:07.280 --> 13:13.180 Gut, soviel zu der Einführung der Rechner-Modelle. 13:14.060 --> 13:17.180 Jetzt schauen wir uns im Folgenden ein bisschen genauer Netzwerk an. 13:18.840 --> 13:23.940 Zum Beginn jetzt erstmal allgemein explizites Store and Forward. 13:24.520 --> 13:28.480 Das bedeutet, wir haben einfach irgendein Verbindungsnetzwerk und wir 13:28.480 --> 13:31.860 modellieren dieses Verbindungsnetzwerk mit Hilfe von einem 13:31.860 --> 13:32.760 Verbindungskrafen. 13:33.500 --> 13:37.140 In diesem Verbindungskrafen haben wir hier Recheneinheiten, hier ist 13:37.140 --> 13:42.700 Kästchen dargestellt und Kanten zwischen diesen Recheneinheiten, wenn 13:42.700 --> 13:48.560 zwischen diesen Recheneinheiten ein Kommunikationslink besteht. 13:49.480 --> 13:54.940 Das kann man als Graf mit Kanten und Knoten modellieren. 13:56.020 --> 14:01.060 Man kann natürlich auch noch ein paar kompliziertere Sachen machen, 14:01.200 --> 14:02.820 zum Beispiel Hüberkanten einfügen. 14:02.820 --> 14:08.660 Das heißt, es ist eine Kante, die mehrere Prozessoren gleichzeitig 14:08.660 --> 14:10.300 miteinander verbindet. 14:10.700 --> 14:15.000 Also wenn man über diese Kante eine Nachricht wegsenden würde, dann 14:15.000 --> 14:19.300 würden alle Prozessoren, die auch mit dieser Kante verbunden werden, 14:19.700 --> 14:20.660 diese Nachricht empfangen. 14:21.540 --> 14:29.560 Oder man könnte in dieses einfache 2D-Grid hier zusätzliche Busse 14:29.560 --> 14:30.040 einbauen. 14:30.040 --> 14:36.940 Das heißt, wir haben zusätzliche Routerknoten, die Nachrichten 14:36.940 --> 14:42.380 speichern können und weiterleiten können, aber selbst nicht an der 14:42.380 --> 14:44.440 eigentlichen Berechnung teilnehmen. 14:46.320 --> 14:51.000 Hier kann man sich jetzt überlegen, wie kann dann auf so einem Grafen 14:51.000 --> 14:54.080 Nachrichtenaustausch stattfinden. 14:57.920 --> 15:02.400 Zuerst geht man eigentlich hin und sagt, was kann man über eine Kante 15:02.400 --> 15:03.100 eigentlich senden. 15:04.460 --> 15:08.960 Da beschränkt man letztendlich einfach die Anzahl Nachrichtenpakete 15:08.960 --> 15:12.820 konstanter Länge, die zu einem Zeitpunkt über diese Kante gesendet 15:12.820 --> 15:13.320 werden können. 15:14.200 --> 15:16.820 Also wenn man jetzt eine Verbindung zwischen Prozessor I und J hat, 15:17.940 --> 15:22.680 bedeutet K' die Anzahl Pakete, die Prozessor I an Prozessor J 15:22.680 --> 15:25.780 innerhalb von einer Zeit anhand wegsenden kann. 15:26.960 --> 15:30.960 Und in der Vorlesung nehmen wir in der Regel K' gleich 1 an, sprich zu 15:30.960 --> 15:38.480 einem Zeitpunkt kann ein Prozessor über eine Verbindung eine Nachricht 15:38.480 --> 15:39.180 senden. 15:40.340 --> 15:43.960 So jetzt ist es in diesem Netzwerk hier zum Beispiel so, dass eine 15:43.960 --> 15:48.680 Recheneinheit mit mehreren anderen Recheneinheiten gleichzeitig 15:48.680 --> 15:54.400 verbunden ist und theoretisch auch Verbindungen zu allen anderen 15:54.400 --> 15:57.560 Recheneinheiten hat, über die er Nachrichten senden könnte. 15:58.340 --> 16:01.500 Es ist natürlich so, in diesem Fall haben wir hier vier Verbindungen 16:01.500 --> 16:03.260 jeweils zu anderen Einheiten. 16:03.580 --> 16:05.500 Es können aber auch natürlich mehr Verbindungen sein. 16:06.060 --> 16:09.500 Wenn die Anzahl Verbindungen ziemlich stark wächst, kann man jetzt 16:09.500 --> 16:13.700 nicht in realen Netzwerken annehmen, dass ein Prozessor über alle 16:13.700 --> 16:16.420 Verbindungen gleichzeitig Nachrichten wegsenden kann. 16:17.360 --> 16:23.440 Und deswegen definieren wir eine K-Port-Maschine als eine Maschine, in 16:23.440 --> 16:27.900 der jeder Knoten K-Pakete gleichzeitig senden empfangen kann. 16:28.500 --> 16:31.720 Das bezieht sich jetzt nicht unbedingt auf eine Kante, sondern auf 16:31.720 --> 16:33.700 alle Ausgangskanten, die er selbst besitzt. 16:35.240 --> 16:40.460 Also wenn wir zum Beispiel K gleich 1 definieren, dann könnte hier ein 16:40.460 --> 16:45.600 Knoten in einer Einheit eine Nachricht entweder an seinen linken 16:45.600 --> 16:49.200 Nachbarn, an seinen rechten Nachbarn, an seinen oberen Nachbarn oder 16:49.200 --> 16:50.800 an seinen unteren Nachbarn senden. 16:51.360 --> 16:53.500 Nicht an mehrere Nachbarn gleichzeitig. 16:54.200 --> 16:57.880 Dieses Modell nennen wir dann auch Single Ported und wird in der Regel 16:57.880 --> 16:59.260 auch in der Vorlesung hier angenommen. 17:03.840 --> 17:09.620 Die Modellierung von solch einem Verbindungsnetzwerk ist ziemlich 17:09.620 --> 17:10.000 einfach. 17:10.120 --> 17:14.260 Man hat einfach einen Graphen, man guckt sich sein Netzwerk an, kann 17:14.260 --> 17:20.320 definieren, aufgrund des realen Aufbaus, wer mit wem kommunizieren 17:20.320 --> 17:25.620 kann, ob es vielleicht Zwischenstationen gibt, über die man eine 17:25.620 --> 17:29.720 Nachricht senden muss, damit sie bei einem Dritten ankommt oder ob es 17:29.720 --> 17:30.880 eine direkte Verbindung gibt. 17:32.660 --> 17:35.660 Das macht letztendlich die Modellierung von so einem Netzwerk ziemlich 17:35.660 --> 17:36.140 einfach. 17:37.020 --> 17:42.420 Die Frage ist natürlich, ist die Analyse von Algorithmen auf diesem 17:42.420 --> 17:43.580 Netzwerk dann auch einfach? 17:43.960 --> 17:47.180 Man hat ein ziemlich kompliziertes Modell und jetzt möchte man seinen 17:47.180 --> 17:49.460 Algorithmus damit analysieren. 17:51.380 --> 17:54.980 Das sind in der Regel Widersprüche, dass diese Analyse dann ziemlich 17:54.980 --> 17:55.660 einfach ist. 17:56.660 --> 18:00.180 Stellen wir uns vor, wir analysieren den Algorithmus jetzt für einen 18:00.180 --> 18:03.820 Graphen und wir kriegen einen neuen Graphen, der ganz anders aussieht, 18:04.420 --> 18:07.840 der zum Beispiel zwischen zwei bestimmten Prozessoren keine Verbindung 18:07.840 --> 18:08.240 mehr hat. 18:08.240 --> 18:12.080 Dann müssen wir eigentlich eine ganz neue Analyse machen, weil die 18:12.080 --> 18:18.140 Analyse speziell für dieses eine Verbindungsnetzwerkmodell entworfen 18:18.140 --> 18:18.440 wurde. 18:20.020 --> 18:22.880 Unter anderem ist es dann auch so, wenn man ein Algorithmus genau für 18:22.880 --> 18:26.060 dieses Modell entwirft, also hier zum Beispiel für dieses 18:26.060 --> 18:30.840 zweidimensionale Grid, dann ist der Algorithmus Low-Level-technisch 18:30.840 --> 18:35.920 wirklich auf dieses Netzwerk rauf implementiert und die Portierung auf 18:35.920 --> 18:39.500 ein anderes Netzwerk ist ziemlich schwierig und die Implementierung 18:39.500 --> 18:42.300 erfordert natürlich auch ziemlich viel Wissen über das Netzwerk, 18:43.020 --> 18:45.720 welches man bei der Implementierung die ganze Zeit im Hinterkopf 18:45.720 --> 18:46.280 behalten muss. 18:49.720 --> 18:53.980 Das führt letztendlich dazu, dass man ziemlich viele Aufgaben des 18:53.980 --> 18:55.220 Netzwerks selbst übernimmt. 18:55.920 --> 18:58.540 Sprich, wenn man einen Nachbarn links, rechts, oben und unten hat und 18:58.540 --> 19:02.140 man möchte dieses Modell möglichst effizient ausnutzen, dann sendet 19:02.140 --> 19:06.300 man wirklich Nachrichten an den Nachbarn links, rechts, oben und unten 19:07.260 --> 19:14.140 und dadurch implementiert man Routing-Strategien in seinem eigenen 19:14.140 --> 19:14.800 Algorithmus. 19:15.640 --> 19:19.060 Und das ist natürlich ziemlich kompliziert, zeitaufwendig und nicht 19:19.060 --> 19:24.460 portable und zusätzlich kommt hinzu, dass heutige Rechner eigentlich 19:24.460 --> 19:28.540 ein einigermaßen gutes Verbindungsnetzwerk haben, welche die Aufgaben 19:28.540 --> 19:32.920 für den Nutzer oder für den Implementierer eigentlich übernehmen und 19:32.920 --> 19:35.440 ziemlich gut umsetzen, in Anführungsstrichen. 19:36.300 --> 19:40.240 Sprich, was man eigentlich haben möchte ist, man hat eine Nachricht, 19:40.300 --> 19:44.500 man möchte die Nachricht von Prozess I an Prozess J senden und die 19:44.500 --> 19:47.640 Nachricht wird einfach gesendet über die Hardware-Router, die Hardware 19:47.640 --> 19:51.080 -Router übernehmen die Arbeit und der Implementierer möchte sich nicht 19:51.080 --> 19:55.380 damit auseinandersetzen, wie das Verbindungsnetzwerk unten drunter 19:55.380 --> 19:55.780 aussieht. 19:58.040 --> 20:02.920 Gucken wir uns jetzt mal verschiedene typische Verbindungsnetzwerke 20:02.920 --> 20:03.160 an. 20:04.520 --> 20:07.300 Dieses Mesh hier auf der linken Seite haben wir jetzt vorhin in dem 20:07.300 --> 20:08.180 Beispiel schon gesehen. 20:09.060 --> 20:12.660 Jeder Prozessor hat den linken und rechten, den oberen und unteren 20:12.660 --> 20:15.200 Nachbarn, mit dem er direkt kommunizieren kann. 20:16.800 --> 20:22.920 Die Knoten oder die Rechneinheiten an den Rändern können nur mit 20:22.920 --> 20:27.400 Prozessoren innerhalb des Grids und nicht über die Ränder hinaus 20:27.400 --> 20:28.260 kommunizieren. 20:29.620 --> 20:32.220 Das ist eben genau der Unterschied zum Torus. 20:33.220 --> 20:37.700 Beim Torus können eben die Randknoten auch wieder mit dem Knoten auf 20:37.700 --> 20:39.140 der anderen Seite kommunizieren. 20:40.120 --> 20:42.900 Dieses Beispiel hier finde ich jetzt eigentlich schon ein bisschen zu 20:42.900 --> 20:43.520 kompliziert. 20:45.360 --> 20:52.620 Wie stellen wir das eigentlich immer so zweidimensional mit neuen 20:52.620 --> 20:53.280 Knoten vor? 20:55.880 --> 21:00.120 Beim Mesh hat man eben Verbindungen zwischen den einzelnen Nachbarn. 21:02.840 --> 21:08.340 Und beim Torus, beim zweidimensionalen Torus, haben jeweils die Knoten 21:08.340 --> 21:13.980 an den Rändern noch eine Verbindung zu den Knoten auf der anderen 21:13.980 --> 21:16.300 Seite des Grids hier, in diesem Fall. 21:18.180 --> 21:21.300 Einmal horizontal und einmal vertikal. 21:23.100 --> 21:27.680 Beim dreidimensionalen Mesh hat man letztendlich einfach ein Stack von 21:27.680 --> 21:32.220 zweidimensionalen Mesh übereinander, wobei jeder Knoten mit seinen 21:32.220 --> 21:36.260 korrespondierenden Knoten im benachbarten Mesh über die dritte 21:36.260 --> 21:38.600 Dimension selbst verbunden ist. 21:38.600 --> 21:41.920 Man kann hier natürlich dann auch wieder Torit rausbauen, indem man 21:41.920 --> 21:43.460 die Randknoten miteinander verbindet. 21:45.240 --> 21:51.620 Ein ziemlich bekanntes und in der Realität auch häufig implementiertes 21:51.620 --> 21:54.700 und ziemlich schnelles Verbindungsnetzwerk ist der Hypercube. 21:55.960 --> 22:02.200 Hier gezeigt, wir haben jetzt hier einen Hypercube mit vier 22:02.200 --> 22:04.080 Dimensionen. 22:04.080 --> 22:08.160 Mit vier Dimensionen ist es schon ziemlich schwer fassbar, finde ich, 22:08.220 --> 22:09.140 was da wirklich passiert. 22:10.660 --> 22:15.300 Was wir letztendlich haben, wir haben Recheneinheiten und die werden 22:15.300 --> 22:17.520 durchnummeriert von 0 bis p-1. 22:19.340 --> 22:24.980 Und diese Nummer repräsentieren wir jetzt in Binärdarstellung. 22:24.980 --> 22:30.240 Und es existiert eine Kante zwischen zwei Recheneinheiten, wenn sich 22:30.240 --> 22:32.980 die Binärdarstellung nur in einem Bit unterscheidet. 22:35.320 --> 22:38.820 Ist jetzt so vielleicht erstmal nicht ganz so gut greifbar. 22:39.780 --> 22:41.500 Ich versuche das jetzt hier mal zu illustrieren. 22:41.900 --> 22:46.700 Wenn wir zwei Knoten haben mit Nummer 0 und 1, dann ist das eben 22:46.700 --> 22:49.080 jeweils auch die binäre Präsentation. 22:49.080 --> 22:53.400 Gut, sie unterscheiden sich nur um einen Bit, deswegen existiert hier 22:53.400 --> 22:54.400 eine Kante. 22:56.000 --> 23:00.960 Wenn wir jetzt eine Dimension hinzunehmen, kopieren wir dieses 23:00.960 --> 23:06.840 Netzwerk einfach nochmal und haben einen weiteren Knoten mit der 23:06.840 --> 23:08.580 Nummer 2 und 3. 23:09.800 --> 23:16.480 Binär repräsentiert dann 1 0 und 1 1. 23:17.340 --> 23:20.040 Und jetzt gucken wir uns wieder an, welche Kanten wir hinzufügen 23:20.040 --> 23:20.360 können. 23:20.980 --> 23:24.640 Naja, diese beiden Knoten unterscheiden sich auch nur in einem Bit. 23:26.160 --> 23:29.500 Diese beiden Knoten unterscheiden sich auch nur in einem Bit und diese 23:29.500 --> 23:30.300 beiden Knoten auch. 23:30.700 --> 23:33.700 Falls euch irgendwas auffällt, falls ihr irgendwelche Anmerkungen 23:33.700 --> 23:38.960 habt, Fragen, einfach strecken oder einfach auf euch aufmerksam 23:38.960 --> 23:39.240 machen. 23:40.000 --> 23:45.240 Ich versuche die dann weitestgehend umzusetzen, sofern nachbar. 23:45.240 --> 23:51.200 Was ihr schon seht, wir haben hier einfach das Netzwerk kopiert und 23:51.200 --> 23:57.660 jeden Knoten, der im alten Netzwerk existiert hat, haben wir mit dem 23:57.660 --> 24:00.560 korrespondierenden Knoten im neuen Netzwerk verbunden. 24:01.300 --> 24:06.280 Das können wir jetzt um eine weitere Dimension erweitern. 24:06.880 --> 24:12.180 Dann haben wir die Knoten 4, 5, 6, 7. 24:14.820 --> 24:19.480 Wenn wir dann zusätzlich die Binärdarstellung uns aufschreiben, haben 24:19.480 --> 24:27.360 wir hier 1 0 0, 1 0 1, 1 1 0 und 1 1 1. 24:27.360 --> 24:34.180 Dieses neue Teil des Netzwerks hat die gleiche Verbindung wie das alte 24:34.180 --> 24:39.380 Netzwerk, weil das dritte Bit in allen Einheiten gleich ist. 24:41.100 --> 24:45.680 Und zusätzlich hat jeder Knoten aus dem neuen Netzwerk mit seinem 24:45.680 --> 24:48.260 korrespondierenden Knoten im alten Netzwerk wieder eine Verbindung. 24:49.660 --> 24:52.320 Das kann man sich jetzt irgendwie so dreidimensional als Würfel 24:52.320 --> 24:52.840 vorstellen. 24:55.060 --> 25:00.340 Der Vorteil von diesem Netzwerk ist, dass die Anzahl Verbindungen hier 25:00.340 --> 25:04.520 ziemlich stark mit der Anzahl an Prozessoren steigt. 25:04.820 --> 25:08.580 Sprich, das ist ein ziemlich eng verbundenes Netzwerk, in dem es 25:08.580 --> 25:11.120 ziemlich viele Kommunikationslinks gibt. 25:13.560 --> 25:17.060 Zum Beispiel bei so einem 3D-Mesh, wenn wir die Anzahl Prozessoren 25:17.060 --> 25:21.120 erhöhen, hat jeder immer eine konstante Anzahl an ausgehenden Kanten 25:21.120 --> 25:23.580 nach links, rechts, oben, unten, vorne und hinten. 25:24.060 --> 25:27.400 Und beim Hypercube mit jeder neuen Dimension, also jeweils wenn wir 25:27.400 --> 25:30.920 die Anzahl Prozessoren verdoppeln, hat jeder Knoten eine zusätzliche 25:30.920 --> 25:31.360 Kante mehr. 25:32.400 --> 25:35.860 Ein drittes Verbindungsnetzwerk ist der Fat Tree. 25:36.580 --> 25:41.880 Der Fat Tree ist dahingehend interessant, dass er einigermaßen gut 25:41.880 --> 25:43.740 auch in der Realität umsetzbar ist. 25:44.320 --> 25:47.720 Er bleibt skalierbar und auf der anderen Seite ist es noch ein 25:47.720 --> 25:48.900 bezahlbares Netzwerk. 25:49.480 --> 25:53.680 Was hier beim Fat Tree passiert, wir haben Router, die eine konstante 25:53.680 --> 25:56.660 Anzahl an Knoten untereinander direkt verbinden. 25:56.820 --> 26:01.580 Die können eigentlich Punkt-zu-Punkt-Kommunikation ausführen. 26:02.660 --> 26:10.460 Und wenn man jetzt zwischen Recheneinheiten verschiedener Router 26:10.460 --> 26:16.540 kommunizieren möchte, dann muss man den Baum nach oben verfolgen, eine 26:16.540 --> 26:20.140 Nachricht an einen Parent Router schicken und der sendet die Nachricht 26:20.140 --> 26:24.000 wieder in das Netzwerk eines anderen Routers. 26:24.620 --> 26:28.100 Wenn man jetzt annimmt, dass der Baum immer und immer größer wird, 26:28.820 --> 26:33.620 umso mehr Router man im untersten Layer hat, dann kann es sein, dass 26:33.620 --> 26:37.580 wenn man einen Prozess in der rechten Ecke, eine Nachricht an einen 26:37.580 --> 26:40.620 Prozess in der linken Ecke senden möchte, dann muss er eben den ganzen 26:40.620 --> 26:43.020 Baum hochlaufen und den ganzen Baum wieder runter auf die andere 26:43.020 --> 26:43.380 Seite. 26:44.160 --> 26:49.240 Und umso mehr Prozessoren man hat, umso höher müssen die Nachrichten 26:49.240 --> 26:50.760 dann in der Regel auch wandern in den Baum. 26:51.680 --> 26:55.980 Und deswegen hat man eben so einen genannten Fat Tree. 26:56.100 --> 26:59.340 Das bedeutet, dass man auf hohen Ebenen von diesem Baum mehr 26:59.340 --> 27:02.320 Kommunikationslinks zwischen den verschiedenen Ebenen hat. 27:02.320 --> 27:06.040 Genau, eine kleine Geschichte dazu noch zu Fat Trees. 27:07.280 --> 27:11.880 Im Moment habe ich Sortieralgorithmen entwickelt auf einem Island 27:11.880 --> 27:13.380 -basierten Supercomputer. 27:13.480 --> 27:15.500 Das ist ähnlich zu so einem Baum hier. 27:15.920 --> 27:22.560 Man hat Routern, die 512 Rechner, a 16 Kerne miteinander verbinden. 27:23.060 --> 27:25.180 Die können ziemlich schnell miteinander kommunizieren. 27:25.180 --> 27:29.280 Und da sieht man auch immer konstante Latenzen in Anführungsstrichen. 27:30.580 --> 27:36.380 Und verschiedene von diesen Islands werden über ein 27:36.380 --> 27:39.560 Verbindungsnetzwerk verbunden, welches oben drüber liegt. 27:39.920 --> 27:45.120 Und es hat eine geringere durchschnittliche Bandbreite im Vergleich zu 27:45.120 --> 27:47.480 der Kommunikation innerhalb einer Island. 27:47.480 --> 27:49.460 Also es ist nicht wirklich ein Fat Tree. 27:50.240 --> 27:52.580 Und das äußert sich letztendlich dafür, dass wenn man Algorithmen 27:52.580 --> 27:57.180 entwickelt hat, die auf eine Island laufen lässt und damit einer 27:57.180 --> 28:02.480 bestimmten Rate skalieren, also man erhöht die Prozessoren, der 28:02.480 --> 28:06.920 Algorithmus wird schneller und dann führt man den Algorithmus auf 28:06.920 --> 28:11.760 mehreren Islands aus und auf einmal lässt die Effizienz nach. 28:11.760 --> 28:15.180 Sprich, der Speedup, wenn man mehr Prozessoren hinzunimmt, steigt 28:15.180 --> 28:18.340 nicht mehr mit der alten Rate, sondern mit einer ziemlich viel 28:18.340 --> 28:21.840 kleineren Rate, weil man einfach durch das obere Netzwerk nicht mehr 28:21.840 --> 28:24.940 so gut kommunizieren kann wie innerhalb einer Island. 28:30.500 --> 28:35.240 Im Vergleich zu diesen Netzwerken, die jetzt ziemlich an der Realität 28:35.240 --> 28:40.260 angeknüpft sind, also die ganzen Netzwerke werden wirklich in zum 28:40.260 --> 28:43.280 Beispiel Supercomputern so implementiert oder wurden implementiert. 28:44.400 --> 28:48.800 Im Vergleich dazu haben wir dieses Netzwerk mit einer vollständigen 28:48.800 --> 28:49.460 Verknüpfung. 28:50.440 --> 28:54.640 Dann haben wir eben wieder einen Graph und es gibt aber in dem Graph 28:54.640 --> 28:56.480 zwischen jedem Knoten eine Kante. 28:57.160 --> 29:00.760 Sprich, jede Recheneinheit kann mit jeder Recheneinheit direkt 29:00.760 --> 29:01.320 kommunizieren. 29:02.520 --> 29:06.180 Es ist natürlich klar, dass die Anzahl Knoten da ziemlich schnell 29:06.180 --> 29:09.660 explodiert, die Anzahl Kanten ziemlich schnell explodiert. 29:09.660 --> 29:16.920 Sprich, für sehr große Anzahl Prozessoren skaliert es nicht mehr 29:16.920 --> 29:18.020 wirklich, sowas zu bauen. 29:18.580 --> 29:23.300 Aber es ist eine einigermaßen gute Abstraktion, in der wir ein 29:23.300 --> 29:25.060 ziemlich geschicktes Modell definieren können. 29:25.060 --> 29:32.200 Was wir nämlich sagen ist, dass eine Kommunikation von M-Wörtern von 29:32.200 --> 29:39.500 einem Prozess zu einem anderen T-Start plus M mal T-Byte Zeit 29:39.500 --> 29:40.100 benötigt. 29:41.020 --> 29:43.140 Warum haben wir das jetzt genau so definiert? 29:45.420 --> 29:49.740 Die Definition ist letztendlich angelegt an einer realen Beobachtung. 29:50.200 --> 29:55.800 Wenn man eine Nachricht an einen anderen Prozess schicken möchte, ist 29:55.800 --> 29:59.960 die Zeit für diesen Nachrichtentransfer in der Regel in zwei Teile 29:59.960 --> 30:00.520 aufgeteilt. 30:00.520 --> 30:05.900 Der erste Teil ist definiert durch dieses T-Start, welches bedeutet, 30:06.080 --> 30:10.900 dass man zu dem anderen Prozessor eine Kommunikation aufbauen muss. 30:11.000 --> 30:14.980 Man muss einen Link aufbauen, intern im Netzwerk müssen vielleicht 30:14.980 --> 30:17.420 Verbindungspfade aufgebaut werden. 30:17.420 --> 30:26.600 Die Nachricht muss vielleicht in den Speicher von der Netzwerkkarte 30:26.600 --> 30:27.880 transformiert werden usw. 30:28.540 --> 30:31.720 oder wenigstens dort ein Togen erstellt werden für eine Nachricht. 30:32.680 --> 30:35.460 Das ist einfach ein konstanter Overhead, der pro Nachricht anfällt. 30:36.860 --> 30:40.160 Zusätzlich ist es so, wenn man die Nachricht sendet und sie wird 30:40.160 --> 30:45.160 größer und größer, dann steigt die Zeit für das Senden einer Nachricht 30:45.160 --> 30:50.300 in der Regel linear mit der Größe der Nachricht. 30:50.780 --> 30:56.380 Deswegen haben wir hier den Term M mal T-Byte, indem wir M mit der 30:56.380 --> 30:57.500 Nachrichtengröße definieren. 31:00.180 --> 31:03.660 Sprich am Anfang dominiert erstmal hier der Term von T-Start, wenn wir 31:03.660 --> 31:04.780 eine kleine Nachricht senden. 31:05.180 --> 31:07.940 Wenn wir eine bisschen größere Nachricht senden, haben wir eigentlich 31:07.940 --> 31:12.260 auch weitestgehend T-Start Zeit für diesen Transfer zu verbuchen. 31:12.800 --> 31:16.400 Und wenn wir dann mehr und mehr Elemente senden, steigt die Zeit dann 31:16.400 --> 31:19.600 irgendwann linear mit der Nachrichtengröße an. 31:20.620 --> 31:25.580 Dies erlaubt uns eben eine realistische Behandlung von den 31:25.580 --> 31:29.320 Nachrichtenlängen in einem Algorithmus und eine gute Analyse. 31:31.440 --> 31:36.380 Und viele Verbindungsnetzwerke sind auch einigermaßen nah dran an 31:36.380 --> 31:36.940 diesem Modell. 31:36.940 --> 31:40.940 Also wie gesagt, bei diesem Supercomputer, auf dem ich im Moment meine 31:40.940 --> 31:44.400 Algorithmen entwickle, solange man sich in seiner eigenen Island 31:44.400 --> 31:51.580 befindet, hat man eigentlich konstante Zeit zum Kommunikationsaufbau 31:51.580 --> 31:54.880 und eigentlich auch eine konstante Transferrate zu jedem bliebigen 31:54.880 --> 31:57.940 anderen Knoten. 31:59.220 --> 32:03.060 Wobei man hier jetzt in diesem Modell in der Regel immer nur mit einem 32:03.060 --> 32:05.600 anderen Knoten zum einen Zeitpunkt kommunizieren kann. 32:06.600 --> 32:09.560 Also es kann nicht jeder Prozess zum einen Zeitpunkt an jeden anderen 32:09.560 --> 32:12.580 was schicken, sondern ein Prozess jeweils immer an einen anderen. 32:17.860 --> 32:22.440 Und wenn ein Verbindungsnetzwerk von seiner Größe immer mehr und immer 32:22.440 --> 32:29.560 mehr steigt, dann dauert das in der Regel auch immer länger, um eine 32:29.560 --> 32:31.860 Kommunikationsverbindung aufzubauen. 32:31.860 --> 32:37.540 Und man hat noch eine bestimmte Latenz, um das erste Byte erstmal zu 32:37.540 --> 32:42.620 diesem anderen Prozess transferieren zu können. 32:43.320 --> 32:48.160 Und deswegen kann man mit diesem Term T-Start einigermaßen gut die 32:48.160 --> 32:58.180 Länge von Verbindungen modellieren und eine realistische Abbildung 32:58.180 --> 32:59.460 garantieren. 33:05.400 --> 33:09.380 Wenn wir eben schwächere Netzwerke haben, sprich man hat viele 33:09.380 --> 33:13.360 Prozessoren, aber vielleicht nicht ganz so viele Kommunikationslinks, 33:13.680 --> 33:16.640 dann kann man in der Regel mit diesem Term T-Start und T-Byte 33:16.640 --> 33:20.560 einigermaßen gut rumspielen, damit das theoretische Modell, welches 33:20.560 --> 33:24.100 man entwickelt hat und mit dem man seinen Algorithmus analysiert hat, 33:24.340 --> 33:27.420 dass die Analyse dann eben auch auf diese langsameren Netzwerke 33:27.420 --> 33:29.040 anwendbar ist. 33:29.040 --> 33:32.040 Zum Beispiel, wenn nur jeder zweite einen Link zu jemand anderem hat, 33:32.380 --> 33:35.740 können sich zwei Prozesse zum Beispiel diesen Link teilen und dann 33:35.740 --> 33:39.040 würde man eben die Transferrate in diesem Fall hier irgendwie 33:39.040 --> 33:40.120 halbieren oder sowas. 33:42.460 --> 33:44.660 Ich habe jetzt hier gerade schon ein bisschen mit den Händen gewegelt, 33:44.720 --> 33:45.780 irgendwie halbieren. 33:46.180 --> 33:49.200 Das ist natürlich alles immer noch ein Modell und zwar auch ein 33:49.200 --> 33:50.180 ziemlich abstraktes. 33:51.780 --> 33:57.260 Deswegen kann man da nicht alles immer 100% transferieren, aber die 33:57.260 --> 34:03.700 Praxis hat gezeigt, dass diese vollständige Verknüpfung einigermaßen 34:03.700 --> 34:09.760 gut Netzwerke modelliert und ein guter Trade-Off eben noch zwischen 34:09.760 --> 34:16.660 der Komplexität der Modellierung erlaubt und der Einfachheit von 34:16.660 --> 34:17.120 Analyse. 34:17.120 --> 34:19.780 Jetzt habe ich vorhin schon gesprochen, dass in der Regel in diesem 34:19.780 --> 34:22.660 Modell nicht jeder Prozess mit jedem Prozess zur gleichen Zeit 34:22.660 --> 34:23.540 kommunizieren kann. 34:23.980 --> 34:27.200 Deswegen werden Varianten für dieses Modell definiert. 34:28.380 --> 34:35.960 Was eben ein Prozess während dieser Zeit T-Comp wirklich machen kann. 34:36.880 --> 34:41.180 Und zwar haben wir drei verschiedene Varianten, einmal Halb-Duplex, 34:41.640 --> 34:47.820 einmal das Telefonmodell und das Voll-Duplex oder Duplex-Modell. 34:47.820 --> 34:52.480 Im Halb-Duplex-Modell ist es so, dass ein Prozess genau eine Nachricht 34:52.480 --> 34:54.940 senden oder empfangen kann zu einem Zeitpunkt. 34:56.240 --> 35:01.280 Also es kann nicht sein, dass ich an Prozess I und J gleichzeitig 35:01.280 --> 35:05.620 Nachricht sende, sondern wirklich nur senden oder empfangen zur 35:05.620 --> 35:06.160 gleichen Zeit. 35:07.000 --> 35:09.040 Dieses Modell wird auch Simplex genannt. 35:09.960 --> 35:14.360 Das zweite Modell, das Telefonmodell, garantiert, dass jeder Prozess 35:14.360 --> 35:20.360 eine Nachricht senden kann und eine Nachricht empfangen kann und der 35:20.360 --> 35:25.040 Sender von der einen Nachricht, mit dem ich kommuniziere und der 35:25.040 --> 35:27.460 Empfänger von meiner eigenen Nachricht, das müssen die gleichen sein. 35:27.460 --> 35:31.880 Sprich, ich kann eine Nachricht zu Prozess J schicken und er kann mir 35:31.880 --> 35:33.780 zu gleichem Zeitpunkt auch eine Nachricht schicken. 35:35.520 --> 35:39.300 Und beim Voll-Duplex-Modell haben wir die größtmögliche Freiheit, da 35:39.300 --> 35:43.020 kann ein Prozess eine Nachricht senden und eine Nachricht empfangen 35:43.020 --> 35:49.220 und die Prozessoren, mit denen er diese Operationen ausführt, können 35:49.220 --> 35:49.880 sich unterscheiden. 35:51.560 --> 35:56.740 Diese verschiedenen Modelle kann man untereinander vergleichen und 35:56.740 --> 36:07.160 sich angucken, ok, ein Algorithmus braucht Zeit T, wie schnell ist er 36:07.160 --> 36:11.500 in dem einen Modell, wenn er in dem anderen Modell Zeit T benötigt. 36:14.180 --> 36:21.920 Und dann kann man eben zeigen, dass wir diese Abschätzung definieren 36:21.920 --> 36:22.240 können. 36:23.160 --> 36:26.780 Also wenn wir einen Algorithmus haben, der im Duplex-Modell Zeit T 36:26.780 --> 36:32.480 braucht, dann ist ein Algorithmus im Telefon-Modell auf jeden Fall 36:32.480 --> 36:38.080 nicht schneller als dieser Algorithmus im Duplex-Modell, aber auf 36:38.080 --> 36:43.240 jeden Fall auch nicht langsamer als ein Algorithmus im Halb-Duplex 36:43.240 --> 36:43.780 -Modell. 36:45.400 --> 36:49.080 Und zusätzlich kann man die Laufzeiten von diesem Telefon-Modell und 36:49.080 --> 36:53.660 diesem Halb-Duplex-Modell dann mit der Laufzeit vom Duplex-Modell 36:53.660 --> 36:55.500 wiederum von oben abschätzen. 36:55.500 --> 36:59.020 Sprich, wenn man den Algorithmus im Halb-Duplex-Modell bzw. 36:59.020 --> 37:02.920 im Telefon-Modell auch einigermaßen gut und geschickt implementiert 37:02.920 --> 37:08.160 hat, dann sind diese Algorithmen auch wiederum höchstens dreimal so 37:08.160 --> 37:14.400 langsam wie der Algorithmus, der das gleiche Problem im Duplex-Modell 37:14.400 --> 37:14.740 löst. 37:14.740 --> 37:17.500 Dann machen wir weiter mit dem BSP-Modell. 37:19.120 --> 37:25.660 Das BSP-Modell, auch Bulk Synchronous Parallel-Modell, besagt, dass 37:25.660 --> 37:28.720 wir unseren Algorithmus in verschiedene Phasen aufteilen. 37:28.720 --> 37:36.020 Und in jeder Phase oder in jedem Schritt, in jedem Superschritt haben 37:36.020 --> 37:37.100 wir drei Phasen. 37:37.260 --> 37:40.400 In der ersten Phase wird nur lokale Arbeit ausgeführt. 37:40.980 --> 37:45.400 Sprich, jede Recheneinheit arbeitet nur mit den Daten, die er lokal in 37:45.400 --> 37:47.180 seinem eigenen Speicher zur Verfügung hat. 37:47.180 --> 37:54.200 Im zweiten Schritt findet ein großer, globaler Kommunikationsaustausch 37:54.200 --> 37:54.620 statt. 37:55.260 --> 38:00.420 Also die Prozesse können untereinander kommunizieren, währenddessen 38:00.420 --> 38:02.440 eigentlich keine lokalen Operationen aus. 38:04.060 --> 38:08.700 Nach dieser globalen Kommunikationsphase werden alle Prozesse 38:08.700 --> 38:12.880 synchronisiert und ein neuer Superschritt beginnt. 38:12.880 --> 38:16.860 Sprich, in der ersten Phase wieder Computation, in der zweiten Phase 38:16.860 --> 38:21.940 wieder eine globale Communication und am Schluss wieder eine 38:21.940 --> 38:22.580 Synchronisation. 38:25.940 --> 38:31.260 Eine Maschine im BSP-Modell wird durch drei Parameter beschrieben, 38:31.640 --> 38:34.120 durch den Parameter P, L und G. 38:34.540 --> 38:38.400 Den Parameter P kennt ihr schon, das sind die Anzahl Prozessoren. 38:38.400 --> 38:44.260 Parameter L ist der Startup-Overhead für einen kollektiven 38:44.260 --> 38:50.260 Nachrichtenaustausch, an dem eben ja global alle Prozesse beteiligt 38:50.260 --> 38:50.560 sind. 38:52.100 --> 38:57.280 Sprich, der tritt in jedem Superschritt während der globalen 38:57.280 --> 38:58.540 Kommunikationsphase auf. 38:59.540 --> 39:05.400 Und wir haben den Parameter G, der sogenannte Gap, welcher definiert, 39:05.560 --> 39:10.700 wie lange eine Nachricht braucht, um ausgeliefert zu werden, wenn 39:10.700 --> 39:13.480 diese Nachricht in einem kontinuierlichen Strom von Nachrichten 39:13.480 --> 39:14.440 verschickt wird. 39:15.040 --> 39:18.360 Sprich, man verschickt ein Paket, dann das nächste und wie lange dann 39:18.360 --> 39:23.300 jeweils eine Nachricht braucht, um bei einem, ja in der Theorie so 39:23.300 --> 39:28.200 definiert, zufälligen Zielprozess anzukommen. 39:29.960 --> 39:34.380 Und dieser Parameter G ist letztendlich in Zeiteinheiten definiert. 39:36.160 --> 39:41.660 Zusätzlich haben wir eine H-Relation, welche den kollektiven 39:41.660 --> 39:45.480 Nachrichtenaustausch selbst definiert, der stattfindet. 39:45.480 --> 39:50.560 Und während einem Nachrichtenaustausch einer kollektiven oder einer H 39:50.560 --> 39:56.300 -Relation kann jeder Prozess H-Nachrichten senden oder empfangen. 39:57.420 --> 40:01.540 Also die Gesamtanzahl von gesendeten und empfangenen Nachrichten eines 40:01.540 --> 40:05.520 Prozesses ist beschränkt durch den Wert H. 40:07.540 --> 40:09.980 Er kann die Nachrichten aber an beliebige Adressaten senden. 40:11.240 --> 40:16.120 Und der Aufwand von einem Superschritt ist dann definiert durch L, 40:16.280 --> 40:21.180 also den Startup-Overhead während einer parallelen Phase, plus H mal 40:21.180 --> 40:27.040 G, also letztendlich wie viele Nachrichten gesendet werden und 40:27.040 --> 40:31.700 empfangen werden, multipliziert mit dem Gap, der irgendwie besagt, wie 40:31.700 --> 40:33.720 lange ein Nachrichtenaustausch dauert. 40:36.440 --> 40:43.840 Dieses Modell ist einigermaßen abstrakt und vernachlässigt ziemlich 40:43.840 --> 40:44.600 viele Faktoren. 40:47.620 --> 40:51.480 Kann aber auch einigermaßen spezifisch modelliert werden. 40:51.880 --> 40:59.180 Dadurch, dass man diese Parameter H, L und G hat und eben P, die 40:59.180 --> 41:03.340 Anzahl Prozessoren, kann man sich einigermaßen komplexe Funktionen 41:03.340 --> 41:06.220 definieren, wie diese Parameter dann letztendlich aussehen. 41:07.080 --> 41:13.220 Zum Beispiel kann oder wird in der Regel G und L, also wie lange 41:13.220 --> 41:18.860 braucht eine Nachricht um gesendet zu werden und wie groß ist der 41:18.860 --> 41:22.280 Startup -Overhead zum Senden der Nachrichten, wird in der Regel von P 41:22.280 --> 41:23.060 irgendwie abhängen. 41:23.120 --> 41:26.040 Sprich, das ist kein fixer Wert, sondern der muss in dem Modell 41:26.040 --> 41:27.000 veränderbar sein. 41:28.640 --> 41:34.300 Wenn man sich zum Beispiel dieses lineare Gitter anschaut, in dem jede 41:34.300 --> 41:40.600 Recheneinheit nur mit einem Nachbarn links und einem Nachbarn rechts 41:40.600 --> 41:43.800 verbunden ist, kann man eben sehen, naja, wenn im einen Superschritt 41:43.800 --> 41:48.000 der Prozess ganz links mit dem Prozess ganz rechts kommunizieren 41:48.000 --> 41:52.840 möchte, dann dauert es eben seine Zeit, weil diese Nachricht eben im 41:52.840 --> 41:57.000 ersten Schritt erst mal zum zweitletzten oder zum vorletzten, dann zum 41:57.000 --> 42:00.980 drittletzten, viertletzten Prozess weitergereicht werden muss, bis 42:00.980 --> 42:03.920 diese Nachricht eben beim ersten Prozess ankommt. 42:07.800 --> 42:13.300 Insgesamt ist es aber eine einigermaßen einfache Abstraktion. 42:13.300 --> 42:17.400 Erstens eine ziemlich Abstraktion und zweitens wird dadurch ziemlich 42:17.400 --> 42:18.260 viel vereinfacht. 42:19.680 --> 42:22.740 Und wie gesagt, diese Parameter, die können ziemlich flexibel gewählt 42:22.740 --> 42:26.940 werden, sind dadurch auch ziemlich anpassbar auf die verschiedenen 42:26.940 --> 42:27.740 Architekturen. 42:29.620 --> 42:32.900 Das Modell ist einfach, das kommt natürlich auch mit verschiedensten 42:32.900 --> 42:34.280 Nachteilen einher. 42:34.760 --> 42:40.300 Zum Beispiel haben wir nur globale, synchronisierte Kommunikation. 42:40.300 --> 42:44.340 Sprich, bevor ein Superschritt beginnt, haben wir synchronisiert, dann 42:44.340 --> 42:48.060 machen wir nur lokale Arbeit, dann haben wir eine globale 42:48.060 --> 42:50.200 Kommunikation und dann wird wieder synchronisiert. 42:51.260 --> 42:55.180 Sprich, es ist nicht wirklich möglich zu modellieren, dass man 42:55.180 --> 42:58.540 irgendwie ein bisschen was berechnet und dann nur mit einem anderen 42:58.540 --> 43:02.640 Prozessor reden möchte, vielleicht ein bestimmtes Element braucht, 43:02.900 --> 43:06.520 dann weiter berechnet und dann wieder mit jemand anderem kommuniziert. 43:06.520 --> 43:10.220 Man hat immer diese Taktung in Superschritte und sobald Kommunikation 43:10.220 --> 43:13.460 stattfindet, wird eben so eine globale Kommunikationsphase gestartet 43:13.460 --> 43:15.080 und danach wird synchronisiert. 43:18.180 --> 43:21.240 Zusätzlich werden in dem Modell nicht wirklich die Nachrichtenlängen 43:21.240 --> 43:23.320 modelliert. 43:23.460 --> 43:27.300 Sprich, wir haben einfach definiert, jeder eine sendet an so viele 43:27.300 --> 43:31.440 Prozessoren eine Nachricht und dann dauert es so und so lang, aber die 43:31.440 --> 43:34.900 Nachrichtenlänge hat in dem Modell nicht wirklich eine Rolle gespielt. 43:34.900 --> 43:39.960 Deswegen gibt es einige Erweiterungen, wie zum Beispiel das BSP Stern 43:39.960 --> 43:45.000 -Modell, die solche Sachen versuchen auch noch mit zu modellieren, 43:45.800 --> 43:48.300 aber dadurch wird das Modell natürlich auch komplizierter. 43:51.640 --> 43:55.620 Zusätzlich hat man natürlich dieses globale Kommunikationsmuster 43:55.620 --> 44:00.560 ziemlich abstrakt definiert, sprich, man hat sich nicht angeschaut, 44:00.880 --> 44:04.300 wie wirklich die Kommunikation aussieht, weil je nachdem, was für eine 44:04.300 --> 44:08.320 Kommunikation man ausführt, ist die Kommunikation schnell oder 44:08.320 --> 44:08.700 langsam. 44:09.500 --> 44:16.660 Also wenn man jetzt zum Beispiel sagt, dieser Parameter hier, dieser 44:16.660 --> 44:20.080 Parameter H, die Anzahl Gesender empfangen Nachrichten, die ist jetzt 44:20.080 --> 44:23.520 mal fix, sagen wir mal drei, dann kann es in einem bestimmten Netzwerk 44:23.520 --> 44:26.420 natürlich beim unterschiedlich langen Dauern drei Nachrichten 44:26.420 --> 44:27.060 auszutauschen. 44:27.060 --> 44:31.480 Wie gesagt, in diesem Netzwerk hier oben drei Nachrichten an einen 44:31.480 --> 44:35.980 bestimmten beliebigen Prozess auszuliefern, kann eben im schlechtesten 44:35.980 --> 44:42.660 Fall hier die komplette Anzahl von Prozessoren in diesem Netzwerk 44:42.660 --> 44:43.120 bedeuten. 44:43.780 --> 44:48.320 Aber wenn man sagt, man kommuniziert jetzt in einer globalen 44:48.320 --> 44:52.160 Kommunikation eigentlich nur mit seinen lokalen Nachbarn, sprich in 44:52.160 --> 44:55.520 einem realen Computer zum Beispiel nur mit den Prozessoren, die auf 44:55.520 --> 45:00.540 seiner eigenen CPU, mit den Cores, die sich auf seiner eigenen CPU 45:00.540 --> 45:04.460 befinden, dann ist diese Kommunikation natürlich um einiges schneller. 45:06.800 --> 45:09.980 Und solche verschiedenen Kommunikationsmuster werden in diesem Modell 45:09.980 --> 45:11.120 eben nicht mit analysiert. 45:16.490 --> 45:22.790 Gut, jetzt haben wir ziemlich lang über Netzwerkmodelle diskutiert, 45:23.130 --> 45:27.590 das ist ein einigermaßen trockenes Thema, aber für die Algorithmen 45:27.590 --> 45:31.070 später selbst ziemlich wichtig, weil wir werden verschiedenste 45:31.070 --> 45:36.190 Algorithmen kennenlernen und es wird sich einfach zeigen, wenn man 45:36.190 --> 45:39.090 diese Idee von einem Algorithmus auf verschiedenen Netzwerken 45:39.090 --> 45:42.150 implementiert, dass die Laufzeiten dann auf einmal unterschiedlich 45:42.150 --> 45:46.370 sind und man diese Laufzeiten aber mit den verschiedenen Modellen und 45:46.370 --> 45:50.850 mit den verschiedenen Parametern einigermaßen geschickt modellieren, 45:50.970 --> 45:52.290 abbilden und sich ausrechnen kann. 45:54.990 --> 45:59.230 Im nächsten möchte ich ein bisschen auf ein anderes Thema eingehen, 45:59.990 --> 46:04.810 und zwar auf Graph-Darstellung und Schallkreis-Darstellung von 46:04.810 --> 46:05.390 Algorithmen. 46:07.190 --> 46:10.510 Im sequentiellen Fall hat man ja seinen Algorithmus, der läuft Schritt 46:10.510 --> 46:16.390 für Schritt sein Programm durch, und da weiß man eigentlich immer, 46:16.490 --> 46:20.150 welcher Schritt als nächstes kommt, und man hat vielleicht noch eine 46:20.150 --> 46:24.290 Verzweigung und dann hängt es natürlich von den Daten ab, welcher Teil 46:24.290 --> 46:25.730 des Programmes weiter ausgeführt wird. 46:26.210 --> 46:29.850 Im parallelen Programm ist es immer ein bisschen komplizierter, so 46:29.850 --> 46:36.710 etwas sich wirklich bildlich vorzustellen, wenn mehrere nebenläufige 46:36.710 --> 46:42.490 Recheneinheiten asynchron, nicht irgendwie synchronisiert, 46:43.010 --> 46:46.710 verschiedenste Operationen ausführen, verschiedenste Algorithmenpfade. 46:48.850 --> 46:54.650 Und eine einfache Darstellung, um bestimmte Klassen von Algorithmen zu 46:54.650 --> 47:00.270 modellieren, ist die Graph-Darstellung oder Schallkreis-Darstellung 47:00.270 --> 47:01.010 von Algorithmen. 47:02.610 --> 47:07.150 Wir sehen hier jetzt schon eine Schallkreis-Darstellung oder eine 47:07.150 --> 47:13.050 Graph -Darstellung von Algorithmen, in dem wir hier vier 47:13.050 --> 47:16.070 Eingangsknoten haben, A, B, C, D. 47:17.130 --> 47:22.410 Die Eingangsknoten haben in dieser Darstellung jeweils einen 47:22.410 --> 47:26.630 Eingangsgrad 0 und liefern uns ein bestimmtes Datum. 47:27.490 --> 47:31.910 Dann haben wir Ausgabeknoten, in dem später dann die Ausgabe von 47:31.910 --> 47:33.130 unserem Algorithmus stehen wird. 47:33.850 --> 47:36.690 Hier die vier Knoten im oberen Bereich von der Abbildung. 47:38.370 --> 47:44.570 Und wir haben innere Knoten, die letztendlich wirklich Berechnungen 47:44.570 --> 47:45.010 ausführen. 47:46.930 --> 47:53.710 Und die Anzahl eingehender Kanten von inneren Knoten ist durch eine 47:53.710 --> 47:57.630 kleine Konstante beschränkt, weil man letztendlich sagen möchte, dass 47:57.630 --> 48:00.530 eine Operation in einem inneren Knoten konstante Zeit braucht. 48:01.350 --> 48:06.370 Und wenn die Eingangskanten linear mit einem anderen Wert skalieren 48:06.370 --> 48:09.210 würden, dann kann man einfach nicht mehr wirklich annehmen, dass dann 48:09.210 --> 48:11.630 die Operation selbst in konstanter Zeit ausführbar ist. 48:15.280 --> 48:20.140 Und wenn man sich jetzt diesen Graphen hier anschaut, sieht man 48:20.140 --> 48:21.380 eigentlich ziemlich schnell, was der berechnet. 48:21.380 --> 48:25.120 Naja, wir haben vier Eingangsknoten, die kriegen Werte A, B, C, D als 48:25.120 --> 48:25.640 Eingabe. 48:26.580 --> 48:32.040 Wir haben hier vier innere Knoten, die jeweils eine Operation hier als 48:32.040 --> 48:33.260 Plus definiert ausführen. 48:35.480 --> 48:39.200 Und nach oben gerichtete Kanten bedeutet in diesem Fall jetzt einfach, 48:39.700 --> 48:45.480 dass das Datum, welches bei dem Quellknoten zu einem Zeitpunkt 48:45.480 --> 48:52.280 gespeichert wird, durch diese Operation mit den anderen Quellknoten an 48:52.280 --> 48:53.540 den Ausgang angelegt wird. 48:55.220 --> 49:01.660 Und in diesem Beispiel würde der erste Ausgabeknoten A ausgeben, der 49:01.660 --> 49:05.560 zweite Ausgabeknoten würde A, B ausnehmen, weil er hier eben die Werte 49:05.560 --> 49:06.360 A, B addiert. 49:06.740 --> 49:10.580 Der dritte Knoten würde A, B, C ausgeben, da er eben die Werte A, B 49:10.580 --> 49:16.400 als Eingabe bekommt und den Wert C und diese beiden Werte eben auch 49:16.400 --> 49:16.940 addiert. 49:20.240 --> 49:24.420 In Schaltkreisen speziell ist es eben so, dass wir annehmen, okay, wir 49:24.420 --> 49:28.420 haben keine Maschinenworte als Eingabe, sondern wir haben immer 49:28.420 --> 49:30.560 konstant viele Bits, die verarbeitet werden sollen. 49:31.040 --> 49:33.780 Und in diesem Fall spricht man dann von einem Schaltkreis. 49:33.780 --> 49:39.140 In einem Schaltkreis oder einem Schaltkreis kann man letztendlich als 49:39.140 --> 49:47.240 DEC, also gerichteten nicht-zyklischen Graph, sich definieren. 49:48.140 --> 49:52.000 Und dieser Graph hat natürlich eine Tiefe, die definieren wir als D 49:52.000 --> 49:52.420 von S. 49:55.260 --> 49:59.840 Und die Tiefe D von S, wenn man sich dann den Graph mal als Programm 49:59.840 --> 50:07.560 anschaut, ist eben die maximale Anzahl von Knoten auf dem längsten 50:07.560 --> 50:11.520 Pfad von einem Eingabeknoten zu einem Ausgabeknoten. 50:13.040 --> 50:16.560 Und wenn man sich jetzt vorstellt, dass in jedem Schritt 50:16.560 --> 50:22.860 Eingabeknoten, die eine neue Eingabe bekommen, diese Eingabe 50:22.860 --> 50:27.240 weiterverarbeiten können und dann im nächsten Schritt an den nächsten 50:27.240 --> 50:30.620 Knoten weitergeben können, dann ist die Tiefe von diesem DEC eben 50:30.620 --> 50:33.100 genau die Ausführungszeit von dem Schaltkreis. 50:35.520 --> 50:39.000 Jetzt ist es so, dass wir in dem vorigen Beispiel einen bestimmten 50:39.000 --> 50:40.140 Schaltkreis gesehen haben. 50:41.180 --> 50:45.280 Der hatte vier Eingaben und vier Ausgaben und hatte die Ausgaben 50:45.280 --> 50:48.280 jeweils präfixummäßig aufaddiert. 50:49.780 --> 50:53.760 Und das ist natürlich eine ziemlich fixe Darstellung, weil dieser 50:53.760 --> 50:59.100 Algorithmus oder dieser Schaltkreis genau dieses eine Problem von der 50:59.100 --> 51:00.600 festen Eingabekröse löst. 51:01.080 --> 51:05.000 Wenn wir jetzt aber sagen, wir möchten eine beliebige Eingabekröse und 51:05.000 --> 51:11.740 können für ein bestimmtes Problem algorithmisch für jede Eingabekröse 51:11.740 --> 51:15.720 einen Schaltkreis definieren, dann sind alle Schaltkreise, die wir 51:15.720 --> 51:19.500 eben dann definieren können, eine Schaltkreisfamilie. 51:23.320 --> 51:26.900 Jetzt haben wir uns bisher angeschaut, okay wir haben diese Graphen 51:26.900 --> 51:33.620 und wir haben Schaltkreise und wie hängt das jetzt irgendwie nicht mal 51:33.620 --> 51:37.300 mit der Realität zusammen, sondern wie kann man das auf ein Modell 51:37.300 --> 51:41.020 abbilden, welches wir wirklich definiert haben, mit dem wir bisher 51:41.020 --> 51:42.440 Operationen ausführen konnten. 51:43.920 --> 51:47.540 Weil diese Schaltkreise, klar kann man vielleicht in Hardware gießen, 51:47.540 --> 51:52.020 aber hier geht es nicht um Hardware gegossene parallele Algorithmen, 51:52.620 --> 51:55.280 auf jeden Fall nicht primär, sondern Algorithmen, die man wirklich 51:55.280 --> 51:57.020 implementieren kann, z.B. 51:57.200 --> 51:58.040 im PRAM-Modell. 51:58.620 --> 52:01.380 Und dann muss man sich natürlich überlegen, okay man hat sich jetzt 52:01.380 --> 52:04.620 hier so einen Schaltkreis oder so eine Schaltkreisfamilie aufgebaut, 52:05.040 --> 52:07.340 wie kann man die wirklich in einem bestimmten Modell ausführen. 52:08.520 --> 52:11.400 Und dann kann man sich z.B. 52:11.580 --> 52:18.900 eine Einbettung von diesem Deck in ein PRAM-Programm vorstellen oder 52:18.900 --> 52:21.060 sich überlegen, wie man das machen könnte. 52:22.560 --> 52:29.480 Und was wir eben machen ist, wir nehmen den Deck her und zerlegen den 52:29.480 --> 52:35.480 Deck in verschiedene Schichten, abhängig davon, wie weit ein Knoten 52:35.480 --> 52:41.000 von seinem am weitesten entfernten Eingabeknoten entfernt ist. 52:42.420 --> 52:44.880 Und in Schritt I führen wir einfach Schicht I aus. 52:46.220 --> 52:53.520 Und wenn wir sagen, in einer Schicht haben wir 10 verschiedene Knoten, 52:54.020 --> 52:57.920 dann brauchen wir 10 Prozessoren, um diese Schicht in einer 52:57.920 --> 52:59.120 Recheneinheit auszuführen. 53:02.160 --> 53:04.800 Ist es jedem klar, wie das funktioniert? 53:09.890 --> 53:11.930 Okay, allgemeines Schmunzeln. 53:16.330 --> 53:19.350 Dann möchte ich das nochmal ein bisschen visualisieren. 53:22.210 --> 53:26.610 Nehmen wir mal an, wir haben hier, das ist letztendlich der Deck von 53:26.610 --> 53:29.290 dem Beispiel, welches wir gerade ausgeführt hatten. 53:29.290 --> 53:33.510 Ein bisschen in kleiner, weil wir haben hier eben keine 53:33.510 --> 53:34.390 Ausgangsknoten. 53:34.650 --> 53:37.890 Könnte man sich auch noch dazu denken, man könnte hier jetzt noch 53:37.890 --> 53:40.910 einen zusätzlichen Level hinzufügen, indem man sagt, man hätten hier 53:40.910 --> 53:42.630 noch mal jeweils zwei Eingangskanten. 53:48.830 --> 53:55.950 Und wenn man hier jetzt die Operation Plus ausführt, würde, wenn das 53:55.950 --> 54:01.770 hier die Eingangsknoten sind, in diesem Ausgangsknoten die Summe von 54:01.770 --> 54:03.090 allen Eingangselementen stehen. 54:05.110 --> 54:09.310 Und jetzt unterteilen wir den Deck in Schichten. 54:09.990 --> 54:14.530 Naja, in der ersten Schicht haben wir hier jetzt die Eingabe, in der 54:14.530 --> 54:20.590 nächsten Schicht haben wir hier Berechnungen, in denen jeweils zwei 54:20.590 --> 54:21.930 Werte aufaggregiert werden. 54:23.270 --> 54:28.370 In der nächsten Schicht haben wir wieder Additionen, in denen die 54:28.370 --> 54:30.510 Werte aus der vorigen Schicht aufaggiert werden. 54:31.410 --> 54:33.150 Und dann haben wir in der letzten Schicht die Ausgabe. 54:36.310 --> 54:40.530 Und jetzt kann man sich einfach ein Programm schreiben, welches im 54:40.530 --> 54:45.970 ersten Schritt, also wirklich synchron als PRAM-Programm, diese 54:45.970 --> 54:49.730 Operation, also diese Schicht ausführt und in der nächsten Operation 54:49.730 --> 54:50.710 diese nächste Schicht. 54:51.470 --> 54:58.550 Und dann in der letzten Operation die Elemente, diese Summe hier 54:58.550 --> 54:59.570 nochmal aufsummiert. 55:00.970 --> 55:03.050 Und dann hat man am Schluss das Ergebnis. 55:04.530 --> 55:07.350 So hat man wirklich synchrone Schritte definiert, indem definiert 55:07.350 --> 55:08.470 wurde, was man gemacht hat. 55:08.950 --> 55:13.270 Wenn man sich jetzt den größten Level anschaut, also die größte 55:13.270 --> 55:19.170 Schicht mit den meisten Knoten, und man definiert für jeden Knoten 55:19.170 --> 55:23.330 einen Prozessor, dann kann man eben in jedem Schritt eine Schicht 55:23.330 --> 55:23.750 ausführen. 55:24.610 --> 55:29.630 Man kann natürlich auch Programme aus dem PRAM-Modell auf Decks 55:29.630 --> 55:30.190 abbilden. 55:30.190 --> 55:37.710 Es ist aber natürlich so, dass Probleme, die man im PRAM-Modell lösen 55:37.710 --> 55:44.950 kann, komplexer sein können, als Modelle, die man in einem Deck-Modell 55:44.950 --> 55:45.710 lösen kann. 55:47.070 --> 55:52.090 Und wenn man einen Schleifen hat, dann kann man die erstmal ausrollen. 55:53.730 --> 55:56.510 Also zum Beispiel hätte man im PRAM-Modell eine Schleife über die 55:56.510 --> 55:57.230 Schichten geschrieben. 55:57.230 --> 55:59.330 Das könnte man ausrollen. 55:59.530 --> 56:02.510 Wenn man jetzt IF-ELSE-Anweisungen hat, die nicht von der Eingabe 56:02.510 --> 56:06.550 abhängen, dann könnte man das auch ausrollen bzw. 56:07.410 --> 56:10.950 jeweils entscheiden, welche von den beiden Operationen oder 56:10.950 --> 56:13.370 nachfolgenden Pfaden man ausführt. 56:13.810 --> 56:20.890 Aber sobald die Bedingungen oder die weitere Ausführung von so einer 56:20.890 --> 56:25.610 WENDAN -Schleife, wenn diese bei der Ausführung von der Eingabe 56:25.610 --> 56:27.970 abhängt, dann kann man das mit diesem Deck nicht mehr wirklich 56:27.970 --> 56:28.390 abbilden. 56:32.030 --> 56:36.550 Jetzt kann man sich auch noch zusätzlich überlegen, was passiert, wenn 56:36.550 --> 56:39.030 man ein Deck in ein Verbindungsnetzwerk abbilden möchte. 56:39.370 --> 56:40.430 Das geht natürlich auch. 56:41.030 --> 56:44.770 Da sagt man einfach, naja, jeder Berechnungsknoden ist ein Prozessor 56:45.530 --> 56:54.710 und Kanten zwischen Knoden in der Deck-Variante ist eben eine Kante 56:54.710 --> 56:58.510 oder eine Nachricht, die im Verbindungsnetzwerk gesendet wird. 56:59.990 --> 57:01.990 Das ist eine ziemlich triviale Abbildung. 57:03.050 --> 57:06.570 Man würde einfach sagen, man hat hier keine Level, sondern jeder 57:06.570 --> 57:08.590 Knoden hier ist ein Prozessor. 57:08.590 --> 57:13.890 Hier hat man Kanten und dieser Prozessor hier braucht ein Datum von 57:13.890 --> 57:14.670 diesem Prozessor. 57:15.210 --> 57:20.090 Also muss hier eine Kante existieren, um das Datum beider reichen zu 57:20.090 --> 57:20.350 können. 57:24.010 --> 57:36.160 Es ist natürlich immer so, dass die Ausführungszeit in diesem 57:36.160 --> 57:41.420 Verbindungsnetzwerk definiert ist, wie lange es braucht, über eine 57:41.420 --> 57:42.820 Kante eine Nachricht zu senden. 57:44.020 --> 57:49.020 Wie viele Schichten hat man hier im Graph natürlich, weil zu einem 57:49.020 --> 57:53.680 Zeitpunkt ist zum Beispiel diese Schicht hier aktiv, diese 57:53.680 --> 57:56.160 Prozessoren, im nächsten Zeitpunkt die anderen Prozessoren. 57:56.760 --> 58:01.400 Also sprich, die Laufzeit hängt dann immer noch von der Tiefe des 58:01.400 --> 58:01.980 Decks ab. 58:03.340 --> 58:06.640 Und zu verschiedensten Zeitpunkten sind verschiedene Prozessoren aktiv 58:06.640 --> 58:09.560 und wahrscheinlich auch viele Prozessoren nicht aktiv. 58:12.340 --> 58:19.220 Schauen wir uns Deckabbildungen oder Decks in einem Beispiel mal an. 58:19.320 --> 58:22.360 Zum Beispiel, jetzt hier eigentlich schon exemplarisch ein bisschen 58:22.360 --> 58:24.820 angeschnitten, assoziative Operationen. 58:24.880 --> 58:29.600 Zum Beispiel die Reduce-Operation, wobei wir als Operand-Operator 58:29.600 --> 58:34.280 beliebigen, in diesem Fall jetzt auf jeden Fall, assoziativen 58:34.280 --> 58:36.020 Kommunikator wählen können. 58:36.020 --> 58:39.320 Dieser Kommunikator muss jetzt erstmal in konstanter Zeit ausgeführt 58:39.320 --> 58:42.360 werden können, das haben wir einfach in unserem Modell so definiert. 58:44.100 --> 58:51.000 Und wir haben jetzt Eingaben x0 bis xn-1 und die möchten wir 58:51.000 --> 58:55.280 reduzieren zu einer einzelnen Ausgabe. 58:57.440 --> 59:07.460 Und im PRAM-Modell lässt sich dies in Log-N-Zeit berechnen, mit der 59:07.460 --> 59:12.120 Voraussetzung, dass man eben n Prozessoren zur Verfügung hat. 59:13.560 --> 59:22.500 Wenn man ein lineares Array hat, kann man die Berechnung auch in T 59:22.500 --> 59:24.000 -Start Log-N-Zeit ausführen. 59:25.400 --> 59:30.040 Also T-Start haben wir jetzt neuerdings für dieses lineare Array im 59:30.040 --> 59:32.440 Vergleich zum PRAM-Modell, weil wir uns jetzt wirklich auf einem 59:32.440 --> 59:35.640 Verbindungsnetzwerk befinden, in dem Nachrichten ausgetauscht werden 59:35.640 --> 59:35.900 können. 59:35.900 --> 59:41.680 Im PRAM-Modell hatten wir ja nicht definiert, wie lange der Transfer 59:41.680 --> 59:45.940 dauert von einem selbst in den gemeinsamen Speicher. 59:47.240 --> 59:51.500 Und beim linearen Array ist es natürlich so, wenn man nur ein lineares 59:51.500 --> 59:52.080 Array hat... 59:52.700 --> 59:54.760 Ich zeichne es euch nochmal kurz auf. 59:56.860 --> 01:00:03.000 Sprich, man hat hier Recheneinheiten und die Recheneinheiten sind 01:00:03.000 --> 01:00:05.020 immer nur mit dem linken und rechten Nachbarn verbunden. 01:00:06.480 --> 01:00:08.960 Wenn man in einem Zeitschritt immer nur mit dem linken und rechten 01:00:08.960 --> 01:00:12.100 Nachbarn kommunizieren darf, dann ist die Implementierung natürlich 01:00:12.100 --> 01:00:12.920 nicht so einfach. 01:00:14.720 --> 01:00:21.040 Oder braucht ziemlich viel Zeit, weil man immer nur mit seinem Nachbar 01:00:21.040 --> 01:00:25.040 reden kann und hier die Daten aufakkumulieren würde. 01:00:26.200 --> 01:00:30.080 Und im nächsten Schritt müsste man, anstatt seine Daten einen Hop 01:00:30.080 --> 01:00:34.220 weiter zu senden, müsste man seine Daten zwei Hops weiter senden. 01:00:42.840 --> 01:00:44.550 Jetzt fehlen mir hier noch ein paar... 01:00:51.560 --> 01:00:55.600 Dieses Datum hier würde man dann an diesen Prozess schicken. 01:00:56.340 --> 01:01:03.440 Der hat schon sein eigenes Datum und würde das mit dem Ergebnis aus 01:01:03.440 --> 01:01:06.480 diesen beiden Elementen vereinigen. 01:01:07.480 --> 01:01:10.520 Und dann würde die Anzahl Hops immer weiter steigen. 01:01:11.860 --> 01:01:14.440 In diesem Fall hier, wenn wir jetzt annehmen, dass wir ein lineares 01:01:14.440 --> 01:01:21.660 Array mit Hardware-Routern haben, sprich, wenn wir von einem Prozessor 01:01:21.660 --> 01:01:27.800 von einer Recheneinheit im linearen Array mit diesem Router eine 01:01:27.800 --> 01:01:32.060 Nachricht senden, können wir eben zum Beispiel von diesem Prozessor 01:01:32.060 --> 01:01:37.500 oder von dieser Recheneinheit zu dieser Recheneinheit in konstanter 01:01:37.500 --> 01:01:40.960 Zeit oder in einem Schritt eine Nachricht senden. 01:01:42.940 --> 01:01:47.440 Falls diese Prozessoren hier diese Verbindung selbst nicht brauchen. 01:01:48.240 --> 01:01:52.340 Und das ist eben genau in diesem Fall hier, in dieser Berechnung der 01:01:52.340 --> 01:01:52.580 Fall. 01:01:54.020 --> 01:01:57.000 Wenn dieser Prozess im zweiten Schritt eine Nachricht an diesen 01:01:57.000 --> 01:02:01.880 Prozess schickt, sendet dieser Prozess keine eigenen Nachrichten 01:02:01.880 --> 01:02:02.920 weiter. 01:02:02.920 --> 01:02:09.560 Und deswegen kann er hier sein Element in T-Start-Zeit durch 01:02:09.560 --> 01:02:11.420 weiterleiten. 01:02:14.540 --> 01:02:17.260 Jetzt können wir uns das nochmal genauer ein bisschen theoretisch 01:02:17.260 --> 01:02:17.820 analysieren. 01:02:18.200 --> 01:02:21.020 Ich habe das jetzt versucht, erstmal skizzenmäßig ein bisschen zu 01:02:21.020 --> 01:02:21.340 zeigen. 01:02:23.620 --> 01:02:25.640 Und zwar machen wir den Beweis induktiv. 01:02:26.340 --> 01:02:31.600 Wir nehmen an, dass wir zwei Hoch-K-Elemente und Prozessoren haben. 01:02:34.840 --> 01:02:41.760 Und mit der Induktionsannahme nehmen wir an, es gibt einen Scheißkreis 01:02:41.760 --> 01:02:49.740 mit Tiefe K, welcher die Summe von zwei Hoch-K-Elementen schon 01:02:49.740 --> 01:02:50.120 berechnet. 01:02:51.160 --> 01:02:58.300 Und jetzt geben wir eben eine Tiefe weiter, also K plus 1, sprich wir 01:02:58.300 --> 01:03:00.760 haben dann zwei N-Eingabe-Elemente. 01:03:00.760 --> 01:03:08.360 Und klar natürlich, wir haben dann am Schluss von jedem Schaltkreis 01:03:08.360 --> 01:03:10.700 der Tiefe K jeweils eine Ausgabe. 01:03:11.280 --> 01:03:18.160 Und die müssen wir in einem Schritt konkretisieren mit dem Operator 01:03:18.160 --> 01:03:23.620 und haben dann den Schritt von K nach K plus 1 gezeigt. 01:03:24.260 --> 01:03:28.260 Und da K eben logarithmisch von N abhängt, haben wir eben eine 01:03:28.260 --> 01:03:29.420 Laufzeit von Log N. 01:03:34.370 --> 01:03:39.090 Jetzt können wir uns diese Überlegung, die wir gemacht haben, wie man 01:03:39.090 --> 01:03:43.450 sowas ausrechnet, wirklich mal als Code oder als Programm in den 01:03:43.450 --> 01:03:45.770 verschiedensten Modellen implementieren. 01:03:46.370 --> 01:03:48.510 Und fangen jetzt erstmal im Pre-RAM-Modell an. 01:03:49.930 --> 01:03:55.670 Im Pre-RAM-Modell haben wir dann eben unsere Prozessoren mit Indizes 01:03:55.670 --> 01:03:57.530 von 0 bis N-1. 01:03:58.570 --> 01:04:01.410 Und am Anfang ist jeder Prozessor aktiv. 01:04:03.370 --> 01:04:06.770 Wir haben hier das Beispiel im rechten oberen Bereich des Bildes. 01:04:07.250 --> 01:04:13.510 Hier haben wir die Prozessoren und jeder hat seine Eingabe XI auf 01:04:13.510 --> 01:04:15.810 Prozess oder auf PEI. 01:04:17.050 --> 01:04:27.090 Und im ersten Schritt würde hier diese erste Phase aus diesem Baum 01:04:27.090 --> 01:04:28.010 ausgeführt werden. 01:04:28.310 --> 01:04:36.170 Sprich, die Prozessoren oder die PEs mit ungeradem Index schicken ihr 01:04:36.170 --> 01:04:40.330 Element an den Prozessor links von sich und dieser Prozessor empfängt 01:04:40.330 --> 01:04:44.230 die Nachricht und addiert sein eigenes Element darauf. 01:04:44.970 --> 01:04:47.910 Es ist so, dass wir im Pre-RAM-Modell ja eigentlich nicht wirklich 01:04:47.910 --> 01:04:50.710 Nachrichten an einen anderen Prozess senden und empfangen. 01:04:50.710 --> 01:05:01.950 Was wir letztendlich machen, dieses Array hier liegt im globalen 01:05:01.950 --> 01:05:04.010 Speicher, also ein durchgehendes Array. 01:05:05.930 --> 01:05:12.070 Und Prozessor oder PEI 0 greift einfach auf X1 zu und auf X0 zu, 01:05:12.530 --> 01:05:17.310 addiert diese beiden Elemente und schreibt das Ergebnis wieder in X0. 01:05:18.770 --> 01:05:25.690 Ein bisschen komplexer als der Schleife implementiert, ist der Code 01:05:25.690 --> 01:05:26.210 hier zu sehen. 01:05:26.870 --> 01:05:35.470 Wir haben diese Log N-Schritte und haben eine Laufvariable K, welche 01:05:35.470 --> 01:05:38.810 uns sagt, in welchem Level wir uns gerade befinden. 01:05:38.990 --> 01:05:42.690 Und die geht eben von 0 bis Log N-1. 01:05:43.670 --> 01:05:49.970 Am Anfang sind alle Prozessoren aktiv und wenn in der eigenen Bit 01:05:49.970 --> 01:05:54.970 -Darstellung des Indexes das Kade-Bit gesetzt ist, dann werden wir 01:05:54.970 --> 01:05:55.510 inaktiv. 01:05:55.750 --> 01:05:56.490 Also wir machen nichts. 01:05:58.530 --> 01:06:00.550 Das sieht man hier schon auf dem ersten Level. 01:06:00.550 --> 01:06:27.130 Bei den ungeraden Prozessen ist das Kade-Bit gesetzt und deswegen 01:06:27.130 --> 01:06:27.910 werden sie aktiv. 01:06:27.910 --> 01:06:38.950 Die Prozesse mit geradem Index addieren das Element, welches den 01:06:38.950 --> 01:06:42.590 gleichen Index hat wie sie selbst, mit dem Element mit einem Index 01:06:42.590 --> 01:06:43.330 höher. 01:06:44.370 --> 01:06:46.110 Das ist hier definiert. 01:06:46.110 --> 01:06:52.090 Und diese Abfrage I plus 2 hoch K kleiner N ist dafür da, dass wenn 01:06:52.090 --> 01:06:59.590 die Anzahl Prozessoren keine Zweierpotenz ist, dass wir eben 01:06:59.590 --> 01:07:02.890 frühzeitig abbrechen und nicht über das Array hinauslaufen. 01:07:05.790 --> 01:07:08.330 Wir führen eben so Level für Level aus. 01:07:09.370 --> 01:07:13.790 In jedem Level fällt die Hälfte der noch aktiven Prozessoren aus und 01:07:13.790 --> 01:07:17.130 wird inaktiv und die andere Hälfte der Prozessoren berechnet was. 01:07:19.550 --> 01:07:28.070 Jetzt haben wir zwei verschiedene Darstellungen von diesem Programm, 01:07:28.230 --> 01:07:29.110 welches wir definiert haben. 01:07:29.110 --> 01:07:33.950 Hier einmal im oberen Bereich definiert als Schaltkreis, in dem hier 01:07:33.950 --> 01:07:36.290 ganz oben links das Ergebnis am Schluss steht. 01:07:37.750 --> 01:07:42.190 Wir können das Programm aber auch in so einem Graph darstellen. 01:07:43.510 --> 01:07:48.190 Das ist letztendlich ein Binomialbaum, in dem im Vergleich zu diesem 01:07:48.190 --> 01:07:52.330 Schaltkreis nicht die Operationen die Knoten sind, sondern hier in 01:07:52.330 --> 01:07:58.390 diesem Binomialbaum sind die Prozesse oder die Prozessoren die Knoten. 01:07:59.230 --> 01:08:01.310 Hier oben haben wir den 0. 01:08:01.510 --> 01:08:06.350 Prozessor, der an dieser Stelle diese Operationen ausführen würde. 01:08:10.010 --> 01:08:16.590 Im ersten Schritt lädt er eben die Daten hier, im zweiten Schritt 01:08:16.590 --> 01:08:19.570 hier, im dritten und vierten Schritt die Daten von hier und ist 01:08:19.570 --> 01:08:25.010 natürlich auf die Daten in den Berechnungen unter sich angewiesen. 01:08:28.670 --> 01:08:34.030 Jetzt haben wir hier natürlich im PRAM-Modell eine ziemlich geschickte 01:08:34.030 --> 01:08:37.130 Festlegung, die wir vorhin gemacht haben. 01:08:37.290 --> 01:08:39.970 Und zwar, dass alle Schritte synchron ausgeführt werden. 01:08:40.610 --> 01:08:45.370 Das führt dazu, dass man einfach auf den Speicher zugreifen kann und 01:08:45.370 --> 01:08:50.230 man weiß, wenn man jetzt zum Beispiel die letzte Operation hier in dem 01:08:50.230 --> 01:08:55.290 Schaltkreis ausführt, dass die Elemente, die man für diese Operation 01:08:55.290 --> 01:09:01.390 braucht, die eben aus den beiden Operationen unten drunter als 01:09:01.390 --> 01:09:06.530 Ergebnis rausfallen, dass diese Elemente oder diese Ergebnisse 01:09:06.530 --> 01:09:07.750 wirklich in dem Speicher stehen. 01:09:09.310 --> 01:09:14.010 Weil eben jeder Algorithmus das gleiche Programm ausführt, Schritt für 01:09:14.010 --> 01:09:22.030 Schritt, wirklich synchron und dann eben gewähr sein kann, dass das 01:09:22.030 --> 01:09:25.770 Element, auf welches er zugreifen möchte, schon wirklich da steht. 01:09:26.990 --> 01:09:30.410 In realen Maschinen ist das natürlich um einiges komplizierter, weil 01:09:30.410 --> 01:09:37.530 da hat man in der Regel nicht synchron rechnende Prozesse, die man 01:09:37.530 --> 01:09:39.170 dann natürlich irgendwie synchronisieren muss. 01:09:40.850 --> 01:09:44.310 Jetzt können wir uns mal den Speedup und die Effizienz in diesem 01:09:44.310 --> 01:09:50.630 einfachen Modell anschauen und ohne Bedenken der Allgemeinheit 01:09:50.630 --> 01:09:57.210 definieren wir uns den Lock von X als den Lock von X zu Basis 2. 01:10:01.770 --> 01:10:07.650 Und die Analyse sagt uns letztendlich, wir haben hier einen Prozessor 01:10:07.650 --> 01:10:13.630 oder eine Rechneinheit PE, dieser braucht die Elemente von diesen 01:10:13.630 --> 01:10:18.110 Kinnknoten und die Kinnknoten brauchen wieder die Ergebnisse von 01:10:18.110 --> 01:10:19.250 diesen Kinnknoten usw. 01:10:19.250 --> 01:10:26.250 Und wir haben eine Tiefe von Lock N und in jedem Schritt werden Daten 01:10:26.250 --> 01:10:30.650 oder Ergebnisse auf den nächsthöheren Level weitergereicht, also haben 01:10:30.650 --> 01:10:32.830 wir letztendlich eine Laufzeit von Lock N. 01:10:34.150 --> 01:10:37.410 Und der Speedup ist dadurch definiert, dass wir die Laufzeit vom 01:10:37.410 --> 01:10:41.770 sequentiellen Algorithmus, also N, durch die Laufzeit vom parallelen 01:10:41.770 --> 01:10:45.990 Algorithmus teilen, also haben wir einen Speedup von N durch Lock N. 01:10:46.610 --> 01:10:51.170 Und die Effizienz, da teilen wir jetzt nochmal durch die Anzahl 01:10:51.170 --> 01:10:55.650 Prozessoren und wenn wir N, Lock N nochmal durch N teilen, haben wir 1 01:10:55.650 --> 01:10:56.250 durch N. 01:10:57.010 --> 01:11:02.030 Und 1 durch N ist jetzt nicht so super effizient. 01:11:04.050 --> 01:11:06.750 Und kann mir jemand von euch sagen, was für eine Effizienz man im 01:11:06.750 --> 01:11:08.450 Idealfall haben möchte? 01:11:08.450 --> 01:11:10.490 Ja, auf jeden Fall O von 1, genau. 01:11:11.070 --> 01:11:14.870 Also eine Effizienz von O von 1, das bedeutet, dass man ein Speedup 01:11:14.870 --> 01:11:19.970 von O von P hätte, wenn P die Anzahl Prozessoren ist. 01:11:20.690 --> 01:11:24.450 Und in der Regel, auf jeden Fall in der Theorie, hat man nie einen 01:11:24.450 --> 01:11:28.670 besseren Speedup als ein Speedup, der linear mit der Anzahl 01:11:28.670 --> 01:11:29.530 Prozessoren steigt. 01:11:31.430 --> 01:11:35.390 Es gibt natürlich Spezialfälle, dass wenn man mehr Prozessoren hat, 01:11:35.870 --> 01:11:39.590 dass das Programm dann auf einmal mehr als linear schneller wird. 01:11:39.910 --> 01:11:45.090 Zum Beispiel wenn man auf einem Rechner oder auf einer Maschine mit 5 01:11:45.090 --> 01:11:48.470 Rechnern gearbeitet hat und die Daten nicht in den Arbeitsspeicher 01:11:48.470 --> 01:11:51.530 gepasst haben, also man die externe Festplatte benutzen muss. 01:11:52.890 --> 01:11:55.270 Und der Zugriff darauf ist natürlich langsam, sprich die 01:11:55.270 --> 01:11:57.390 Ausführungszeit vom Algorithmus ist auch langsam. 01:11:57.390 --> 01:12:01.970 Wenn man jetzt auf einmal 10 Rechner hat, wobei jeder Rechner die 01:12:01.970 --> 01:12:07.390 gleiche Arbeitsspeichergröße wie der vorige Rechner hat, da hat man 01:12:07.390 --> 01:12:09.610 natürlich doppelt so viel Arbeitsspeicher und dann kann sein, dass man 01:12:09.610 --> 01:12:13.170 sein Problem auf einmal im Arbeitsspeicher speichern kann und dadurch 01:12:13.170 --> 01:12:16.210 nicht mehr Zugriff auf die langsame Platte hat und dann der 01:12:16.210 --> 01:12:18.550 Algorithmus überproportional schneller wird. 01:12:19.230 --> 01:12:23.210 Aber in der Regel hat man sowas im allgemeinen Fall nicht wirklich. 01:12:25.670 --> 01:12:30.150 Wir haben jetzt gesehen, dass eine Effizienz von 1 durch log n 01:12:30.150 --> 01:12:34.790 ziemlich schlecht ist, weil die Effizienz sinkt sogar und konvergiert 01:12:34.790 --> 01:12:39.130 gegen 0, obwohl man eigentlich eine konstante Effizienz haben möchte. 01:12:40.610 --> 01:12:43.130 Und deswegen möchte man eigentlich ein bisschen bessere Algorithmen 01:12:43.130 --> 01:12:43.530 schreiben. 01:12:44.890 --> 01:12:48.230 Und jetzt auch nochmal ein PRAM-Modell, wie könnte man sowas machen? 01:12:48.930 --> 01:12:52.990 Wir sagen jetzt einfach, wir haben immer noch n Elemente als Eingabe 01:12:52.990 --> 01:12:57.330 und aber p Prozessoren, wobei in unserem Fall jetzt einfach mal p 01:12:57.330 --> 01:12:58.270 kleiner als n ist. 01:12:59.730 --> 01:13:11.870 Und dann haben wir eine Eingabe hier, also diese Kästchen hier, in 01:13:11.870 --> 01:13:13.910 diesem Bereich sind die Eingaben. 01:13:13.910 --> 01:13:21.250 Also wir haben eine Eingabe-Matrix der Größe p kreuz n durch p, also 01:13:21.250 --> 01:13:22.910 wieder n Eingabe-Elemente. 01:13:24.370 --> 01:13:36.090 Und p ist, die hier eben in dem ersten Teil des Arrays jeweils den 01:13:36.090 --> 01:13:37.810 zweiten Teil des Arrays aufaddieren. 01:13:37.810 --> 01:13:50.030 Also ein Prozess i würde Element i plus p addieren und Element 0 würde 01:13:50.030 --> 01:14:00.250 Element 0 und Element p miteinander reduzieren und Element 1 würde 01:14:00.250 --> 01:14:04.790 Element 1 mit p plus 1 reduzieren und so weiter. 01:14:05.910 --> 01:14:10.430 Und das führt letztendlich dazu, dass jeder Prozess erstmal n durch p 01:14:10.430 --> 01:14:19.010 Elemente reduziert auf ein Element und dann haben wir p reduzierte 01:14:19.010 --> 01:14:25.110 Elemente übrig, jeder Prozess hält ein Element und diese p Elemente, 01:14:25.110 --> 01:14:29.770 die reduzieren wir dann nochmal mit dem Algorithmus, den wir vorher 01:14:29.770 --> 01:14:30.250 gesehen haben. 01:14:32.310 --> 01:14:35.530 Also ich finde die Darstellung hier ehrlich gesagt nicht wirklich so 01:14:35.530 --> 01:14:36.330 toll, muss ich sagen. 01:14:37.270 --> 01:14:42.650 Also ich stelle mir das eigentlich eher so vor, dass wir hier ein 01:14:42.650 --> 01:14:43.610 Eingabe -Array haben. 01:14:45.690 --> 01:14:48.370 Nehmen wir an, wir haben vier Prozessoren, wir unterteilen das in vier 01:14:48.370 --> 01:14:49.030 Teile. 01:14:51.290 --> 01:14:57.570 Der Prozessor 0 reduziert diese Elemente hier, Prozessor 1 diese 01:14:57.570 --> 01:15:01.330 Elemente, Prozessor 2 diese Elemente, Prozessor 3 diese Elemente. 01:15:02.170 --> 01:15:09.010 Hier haben wir jeweils ein Stripe von n durch p und die Reduzierung 01:15:09.010 --> 01:15:12.710 von n durch p Elementen benötigt n durch p Laufzeit. 01:15:14.210 --> 01:15:18.890 Und am Schluss haben wir ein reduziertes Element pro Prozess übrig, 01:15:19.630 --> 01:15:22.110 welches wir dann eben wieder baumartig reduzieren können. 01:15:26.720 --> 01:15:29.500 Und ihr seht schon, dass wir in der ersten Phase eigentlich ziemlich 01:15:29.500 --> 01:15:30.180 effizient sind. 01:15:30.920 --> 01:15:36.180 Also wir haben irgendwie das Array in p Teile aufgeteilt und haben n 01:15:36.180 --> 01:15:37.620 durch p Arbeit verrichtet. 01:15:38.740 --> 01:15:40.520 Das hört sich schon mal ziemlich gut an. 01:15:40.900 --> 01:15:43.820 Und dann haben wir eben noch einen logarithmischen Term, der von der 01:15:43.820 --> 01:15:44.900 Anzahl Prozessoren abhängt. 01:15:46.200 --> 01:15:50.820 Und im sequentiellen Fall würde ein Algorithmus, der einfach über alle 01:15:50.820 --> 01:15:56.160 Elemente drüber sweept, Tsec-Zeit brauchen. 01:15:56.720 --> 01:16:01.820 Und ein paralleler Algorithmus würde eben Tsec von n durch p Zeit 01:16:01.820 --> 01:16:02.140 brauchen. 01:16:02.300 --> 01:16:06.120 Also jeder Prozess verarbeitet sequentiell n durch p Elemente. 01:16:06.440 --> 01:16:09.140 Und dann hat man eben noch eine Baumtiefe von log p. 01:16:09.860 --> 01:16:13.120 Und wenn wir uns jetzt die Effizienz angucken, würde man eben den 01:16:13.120 --> 01:16:16.820 sequentiellen Teil durch den parallelen Teil teilen und dann nochmal 01:16:16.820 --> 01:16:20.580 zusätzlich durch die Anzahl Prozessoren teilen, um die Effizienz zu 01:16:20.580 --> 01:16:20.920 bekommen. 01:16:23.120 --> 01:16:27.900 Und wenn man dann jetzt für Tsec n durch p, äh, wenn man jetzt für T 01:16:27.900 --> 01:16:33.220 sequentiell n einsetzt, für n Elemente, braucht man n Zeit für die 01:16:33.220 --> 01:16:33.760 Reduktion. 01:16:34.480 --> 01:16:39.300 Und für Tsec n durch p, n durch p einsetzt und dieses log p stehen 01:16:39.300 --> 01:16:45.700 lässt, dann kann man die Formel vereinfachen als auf 1 durch 1 plus 01:16:45.700 --> 01:16:48.560 Theta p log p durch n. 01:16:50.080 --> 01:16:55.160 Und aus der Mathematik wisst ihr vielleicht noch, wenn dieser Term 01:16:55.160 --> 01:17:01.820 hier klein wird, also dieses p log p klein ist im Vergleich zum n, 01:17:03.120 --> 01:17:11.120 dann können wir diesen Term abschätzen durch 1 minus p log p durch n. 01:17:12.320 --> 01:17:15.180 Also genauso in diesem Fall haben wir eben diese Effizienz. 01:17:16.020 --> 01:17:18.360 Und jetzt können wir uns anschauen, wenn die Anzahl Elemente immer 01:17:18.360 --> 01:17:20.740 größer wird, was für eine Effizienz haben wir da? 01:17:21.200 --> 01:17:26.220 Wenn wir einfach mal annehmen, die Anzahl Prozessoren p wäre konstant. 01:17:26.920 --> 01:17:30.100 Also hier hätten wir eine Konstante und dieser Nenner würde immer 01:17:30.100 --> 01:17:30.780 weiter steigen. 01:17:30.780 --> 01:17:35.300 Sprich wir superhieren von der 1 immer einen kleineren Wert und dann 01:17:35.300 --> 01:17:40.940 haben wir eine Effizienz, die immer weiter steigt und gegen 1 01:17:40.940 --> 01:17:41.500 konvergiert. 01:17:43.880 --> 01:17:46.440 Jetzt haben wir uns das natürlich ziemlich einfach gemacht mit der 01:17:46.440 --> 01:17:49.080 Implementierung, indem wir das PRAM-Modell angenommen haben. 01:17:49.080 --> 01:17:53.600 Und im PRAM-Modell haben wir eben wirklich synchrone Schritte, sprich 01:17:53.600 --> 01:17:56.980 wenn man hier den nächsten Level ausführt, weiß man, dass der vorige 01:17:56.980 --> 01:18:00.320 Level wirklich berechnet wurde und das Ergebnis im gemeinsamen 01:18:00.320 --> 01:18:00.900 Speicher steht. 01:18:02.360 --> 01:18:07.120 Wenn man den Algorithmus jetzt verteilt ausführen möchte, hat man 01:18:07.120 --> 01:18:10.560 keinen gemeinsamen Speicher mehr, sondern muss sich seine Elemente 01:18:10.560 --> 01:18:17.220 selbst vom anderen Prozessor schicken lassen und empfangen. 01:18:19.320 --> 01:18:22.180 Aber letztendlich ist es in diesem Problem gar nicht so schwer, das in 01:18:22.180 --> 01:18:23.420 den alten Code einzubauen. 01:18:23.860 --> 01:18:31.380 Der Code hier, welcher das Problem im verteilten Fall löst, sieht 01:18:31.380 --> 01:18:34.380 eigentlich fast genauso aus wie der Code für die PRAM-Maschine. 01:18:34.380 --> 01:18:40.380 Nur, dass wir jetzt diesen Code auf jedem Prozess ausführen und jeder 01:18:40.380 --> 01:18:45.560 Prozess hier eben sein eigenes Element S als Eingabe hat. 01:18:46.160 --> 01:18:55.780 Also PEI hat das I-Element der Eingabe und mit diesem Element führt er 01:18:55.780 --> 01:18:57.600 eben den Algorithmus aus. 01:18:57.600 --> 01:19:02.180 Es ist allgemein so, dass wenn wir über verteilte Algorithmen 01:19:02.180 --> 01:19:06.880 sprechen, dass wir in der Regel annehmen, dass die Eingabe in unserem 01:19:06.880 --> 01:19:11.500 Algorithmus verteilt vorliegt und die Problemstellung so ist, dass wir 01:19:11.500 --> 01:19:13.920 die Ausgabe auch wieder verteilt ausgeben sollen. 01:19:14.920 --> 01:19:18.560 Also wenn wir zum Beispiel, was wir uns später anschauen, N-Elemente 01:19:18.560 --> 01:19:23.820 sortieren wollen, können wir als Eingabe annehmen, dass jeder Prozess 01:19:23.820 --> 01:19:29.340 bei P-Prozessen N durch P-Elemente als Eingabe bekommt und als Ausgabe 01:19:29.340 --> 01:19:33.280 auch wieder mehr oder weniger N durch P-Elemente ausgeben soll. 01:19:35.580 --> 01:19:40.180 Also hier nehmen wir jetzt einfach mal an, wir haben N-Prozesse, also 01:19:40.180 --> 01:19:46.260 wir haben für jedes Element einen Prozess, jeder Prozess hat sein 01:19:46.260 --> 01:19:50.740 Element in der Variable S gespeichert und wir führen den gleichen 01:19:50.740 --> 01:19:57.380 Algorithmus aus wie vorher, nur dass wir, wenn wir inaktiv werden, das 01:19:57.380 --> 01:20:01.040 Element, welches wir zu dem Zeitpunkt noch gespeichert haben, an den 01:20:01.040 --> 01:20:02.740 Prozess schicken, der das gebraucht. 01:20:03.280 --> 01:20:08.260 Das ist genau der Prozess, der in der vorigen Variante hier in der S 01:20:08.260 --> 01:20:11.520 -Schleife aus einer bestimmten Speicherstelle geladen hat. 01:20:12.480 --> 01:20:16.440 Also im ersten Schritt würden zum Beispiel die Prozessoren mit 01:20:16.440 --> 01:20:23.160 ungeratem Index ihre Elemente an den Prozessor 1 weiter links an sich 01:20:23.160 --> 01:20:23.400 schicken. 01:20:24.000 --> 01:20:31.380 Im nächsten Schritt würde jeder zweite Prozess sein Element an den 01:20:31.380 --> 01:20:32.920 Prozess 2 links von sich schicken. 01:20:33.540 --> 01:20:38.420 Und im nächsten Schritt die Hälfte der aktiven Prozesse sein Element 01:20:38.420 --> 01:20:42.940 an die Prozesse 4 links von sich, 8 links von sich und so weiter 01:20:42.940 --> 01:20:43.600 schicken. 01:20:43.680 --> 01:20:47.120 Man sieht hier diese Pfade, wie weit die Elemente hier nach links 01:20:47.120 --> 01:20:51.400 geschickt werden, die werden mit jedem Level größer. 01:20:52.500 --> 01:20:56.500 Also wir wissen jetzt, was der Prozess macht, der inaktiv wird, er 01:20:56.500 --> 01:20:57.560 sendet seine Elemente weg. 01:20:57.560 --> 01:21:02.940 Und genauso wie vorher im PRAM-Modell laden wir unser Element, falls 01:21:02.940 --> 01:21:06.700 wir aktiv bleiben und die Reduktionsoperation ausführen. 01:21:07.040 --> 01:21:11.460 Aber wir haben jetzt im Vergleich zur vorigen Variante keinen 01:21:11.460 --> 01:21:15.080 Speicherzugriff, sondern wir haben wirklich eine Revisiv-Operation, 01:21:15.160 --> 01:21:16.100 die wir aufrufen müssen. 01:21:16.860 --> 01:21:23.740 Und wir müssen nicht die Position im Speicher definieren, die wir 01:21:23.740 --> 01:21:27.140 laden oder auf die wir zugreifen wollen, sondern wir müssen einen 01:21:27.140 --> 01:21:31.380 wirklichen Prozess definieren über seinen Index, von dem wir wirklich 01:21:31.380 --> 01:21:32.140 etwas empfangen wollen. 01:21:33.360 --> 01:21:39.420 Und am Schluss hat der erste Prozess, also PE0, das Datum in seine 01:21:39.420 --> 01:21:40.560 Variable S gespeichert. 01:21:46.620 --> 01:21:50.740 Natürlich kann man dann in diesem Maschinenmodell den Algorithmus auch 01:21:50.740 --> 01:21:51.500 wieder analysieren. 01:21:52.740 --> 01:21:57.180 Man hat log p Schritte, wir hatten p gleich n, also auch log n 01:21:57.180 --> 01:21:57.500 Schritte. 01:21:58.140 --> 01:22:03.540 Und in jedem Schritt sendet jeder Prozess eine Nachricht, also auf 01:22:03.540 --> 01:22:05.160 jeden Fall alle noch aktiven Prozesse. 01:22:07.580 --> 01:22:11.320 Die Hälfte der aktiven Prozesse sendet eine Nachricht und die andere 01:22:11.320 --> 01:22:12.700 Hälfte empfängt eine Nachricht. 01:22:15.120 --> 01:22:20.960 Sprich in jedem Schritt haben wir genaue Tstart plus Tbyte Zeit, die 01:22:20.960 --> 01:22:21.660 wir verbrauchen. 01:22:21.800 --> 01:22:26.100 Tstart für das Senden und Tbyte, da wir nur ein Element schicken. 01:22:26.420 --> 01:22:28.940 Wenn wir mehr Elemente schicken würden, würde es dann eben auch 01:22:28.940 --> 01:22:30.660 dementsprechend länger dauern. 01:22:31.540 --> 01:22:36.840 Wenn wir ein lineares Array haben, dann würden wir eben Theta von p 01:22:36.840 --> 01:22:44.300 Zeit brauchen, da Schritt 2 auf k Zeit Schritte benötigen würde. 01:22:44.820 --> 01:22:48.480 Angenommen, dass wir eben hier nicht diesen Router haben, über den wir 01:22:48.480 --> 01:22:53.200 in einem Schritt ein Element über verschiedene Prozesse schicken 01:22:53.200 --> 01:22:55.080 können, sondern immer nur an den direkten Nachbarn. 01:22:59.120 --> 01:23:06.080 Und bei der Variante mit dem linearen Array mit dem Router, haben wir 01:23:06.080 --> 01:23:07.800 eben wieder eine logarithmische Anzahl an Schritten. 01:23:09.000 --> 01:23:12.700 Und im BSP-Modell haben wir eben auch Log p Superschritte. 01:23:13.820 --> 01:23:16.300 Und hier sieht man eben jetzt schon eine Schwäche vom BSP-Modell. 01:23:16.840 --> 01:23:20.360 Wir haben einen Superschritt dadurch definiert, dass wir wirklich eine 01:23:20.360 --> 01:23:21.720 globale Kommunikation machen. 01:23:21.720 --> 01:23:25.360 Sprich, jeder kann an jeden was senden und in der Regel ist das 01:23:25.360 --> 01:23:26.400 ziemlich teuer. 01:23:28.640 --> 01:23:31.560 Wir haben jetzt hier natürlich das Glück, dass jeder nur eine 01:23:31.560 --> 01:23:32.240 Nachricht sendet. 01:23:32.740 --> 01:23:37.920 Sprich, h ist 1 und deswegen haben wir eine Laufzeit auf jedem Level 01:23:37.920 --> 01:23:39.600 von L plus G. 01:23:45.140 --> 01:23:48.920 Ich denke an der Stelle machen wir dann auch Schluss. 01:23:48.920 --> 01:23:53.320 Noch eine Anmerkung hier, wenn man jetzt mehr Elemente hat. 01:23:54.080 --> 01:23:59.520 Wir haben im PRAM-Beispiel gesehen, wir können die Effizienz steigern, 01:24:00.320 --> 01:24:06.320 wenn wir von einem Prozess mehrere Elemente erstmal lokal aggregieren 01:24:06.320 --> 01:24:06.860 lassen können. 01:24:06.860 --> 01:24:12.160 Dann in allen Fällen natürlich auch für das verteilte Modell hier, 01:24:12.860 --> 01:24:19.140 dass wir jeweils zusätzlich T sequentiell von N durch P verbrauchen würden.