Video 5-4: Maschinenmodelle und word-RAM

0:03 Der nächste Abschnitt knüpft genau daran an, wenn wir jetzt uns darauf eingeschossen haben, wir wollen Algorithmen vergleichen für n gegen unendlich, dann beißt sich das so ein bisschen mit den Einschränkungen, die Java hatte, wo Arrays nur eine konstante Größe haben können. Und ich hatte schon angedeutet, wie man dem entkommt. Man sagt halt ja, wir beschreiben Algorithmen in Java, aber die Einschränkung konkret von Java an manche Dinge, die lassen wir einfach fallen, die ignorieren wir für unseren echten Algorithmus. Wir klauen sozusagen nur die Syntax und die die größten Teil der Semantik von Java. Man kann es ein bisschen konkreter fassen und um sie zu sensibilisieren, was da das Problem oder die die Fragestellung sein kann, mal eine eine harmlose Frage.

0:54 Ähm das Beispiel hier zeigt ihnen, sie wollen zwei Zahlen addieren, die fünf Stellen haben. Sagen wir mal Dezimalzahlen. macht äh an der Stelle keinen großen Unterschied, aber sie sollen das jetzt beschreiben für große Zahlen, wo wir die Anzahl Stellen vielleicht größer haben als fünf. Wie lange dauert das denn? Einfaches Problem, müssen wir ja wissen eigentlich.

1:19 Sie schreiben ja auch ständig Programme mit x + y. ein paar mehr Leute sind wir noch. Äh, ich möchte mir auch für die Frage kurz Zeit lassen, weil wenn Sie die wenn Sie die gut verinnerlichen, dann ist der Rest vom Kapitel, glaube ich, sehr natürlich bzw. sie verstehen sehr viel mehr, was da hinter steckt oder warum man warum man das, was dann kommt macht.

2:56 ist auch mustergültige Antwortverteilung, Wer ist noch aktiv am Denken oder abstimmen? Dann zeige ich Ihnen auf jeden Fall mal die die Verteilung der Antworten.

3:21 Also, wir sind uns einig, dass wir uns nicht einig sind. Ähm, keine Ahnung, gibt's wenige. Also alle sind so sind einigermaßen überzeugt von ihrer Antwort und trotzdem haben sie unterschiedliche Antworten.

3:34 Der Grund dafür ist einfach, dass dass sie ähm im großen und ganzen alle recht haben, aber die Frage ist so ein bisschen, warum? Und was genau heißt das denn?

3:53 Der Punkt ist, das ist genau der Teil, der ein Maschinenmodell eigentlich nicht wirklich beantwortet, wenn man es wage lässt. In Java können Sie zwei Ins oder auch zwei Longs oder zwei Doubles oder eine der anderen primitiven Typen in Konstantzeit addieren. Das ist eine sinnvolle Annahme, die auch in der Hardware so ähm umgesetzt ist. Da gibt's feste Hardware in der Alu die zwei Zahlen nimmt und die addiert. Und das passiert im Wesentlichen im einem Taktzyklus. Unabhängig davon, wie groß diese Zahlen selbst sind. Die haben natürlich wie alle Ints Obergrenze. Sie wissen in Java int ist 32 Bit und es ist sig und dann hat es diesen gewissen Wertebereich -2 hoch 31 bis 2 hoch 31 -1. Aber alle Zahlen in diesem Bereich addieren sie im Wesentlichen gleich schnell, also Konstantzeit. Gleichzeitig hat Java auch sowas wie Big Integer oder Big Decimal. Wer wer kennt diese Klassen?

5:05 Wer kennt sie nicht? Gegenfrage. Äh das ist ähm Wer von Ihnen kennt Python so ein bisschen? In Python ist diese Frage mehr kaputt, weil Python das nicht unterscheidet. Wenn ich in Python 2 Integer addiere, dann ähm wird unter der Haube entweder sowas wie ein int gemacht oder sowas wie ein Big Integer, was letztlich ein String ist der Ziffer. Wie mehr steckt da nicht dahinter. Und die Algorithmen in Big Integer, die da z.B. für die Addition implementiert sind, sind die, die Sie in der Grundschule gelernt haben. Vielleicht mit ein bisschen fairerweise mit ein bisschen Feinheiten, um die etwas schneller zu machen. Aber im großen und ganzen Algorithmen, die auf den Zahlen arbeiten, als wären es Strings von Zeichen von Ziffern. Und dementsprechend brauche ich für die Addition Linearzeiten der Anzahl Ziffern, denn ich muss ja es in der Schule gelernt haben, von hinten anfangen und dann immer mit dem Übertrag äh die nächste nächste Stelle berechnen, bis ich dann irgendwann angekommen bin vorne.

6:13 Also was denn nun? Jetzt habe ich Ihnen zwei Antworten gegeben. Das ist sehr höchst unbefriedigend, oder? Äh man kann es auch anders formulieren als die Frage, wie viel Platz brauchen denn natürliche Zahlen?

6:25 Nach der Vorarbeit oder nach dieser Vorwarnung über die Slidofrage ist ihnen klar, das wird von der Größe der Zahlen abhängen. Logisch. Also auch wieder hier die zwei Optionen. Entweder ich habe ins, dann sind es 32 x n bit, egal wie groß die Zahlen sind, solange sie in den in passen. Und mit denen kann ich äh in einer kann ich in Konstantzeit rechnen. Ich kann aber auch beliebig große Zahlen haben und mir überlegen ähm wenn sie da genauer was zu sehen wollen, müssen sie in effiziente Algorithmen kommen. ähm Werbeblockende Ende. Aber wenn Sie beliebig große Zahlen haben, die also in den Bereich von 0 bis m sind, dann brauche ich statt 32 eventuell log von m ungefähr log von m Bits, um die Zahlen darzustellen. Einfach das ist die Anzahl verschiedener Zahlen, die ich habe und der zwe Logarithmus davon gibt mir die Anzahl Bit. Dann habe ich also n mal etwas, was mit der Größe der Zahlen wächst.

7:30 Und beides ist irgendwie korrekt. Das hier hat halt die Annahme, dass die Zahlen in den in passen und das hier ist allgemeiner. Wenn jetzt dieses M nicht ähm wenn das relativ klein ist, selbst wenn es deutlich kleiner ist als 2 hoch 31, würde man in der Praxis wahrscheinlich trotzdem diese 32 Bit ins Ins nehmen, weil das schneller ist, als einzelne Bits zu speichern, selbst wenn ich dadurch Platz sparen kann. Wenn Sie das interessiert, wie man Platz sparen kann und trotzdem sinnvoll rechnen kann, dann müssen sie zu einer noch anderen Vorlesung kommen. Advancec structures, aber das ist äh Mastervertibung.

8:13 Also hängt von der Größe der Zahlen ab. Soweit so gut. Aber was machen wir denn jetzt mit Algorithmen, die Zahlen als Eingabe kriegen? Wie kann ich denn irgendwie denen sinnvolle Kosten zuordnen? Und die Lösung ähm ja, die ketzerische Frage ist so ein bisschen, was ist der Grenzwert von int, wenn ich äh wenn meine Algorithmen doch asymptotische Vergleiche machen sollen, also ich die Eingabegröße beliebig groß wählen wählen soll, sollte ich dann an den 32 Bits wie in Java festhalten oder was all sonst?

8:45 Bisschen unklar. Die Lösung dafür ist letztlich, dass wir einen zweiten Parameter für unser Maschinenmodell brauchen. Die allgemeine Version ist, dass wir eine Anzahl Bit W festhalten und Zahlen mit höchstens Wbits oder integer natürliche Zahlen mit höchstens Wbits. Auf denen kann ich in Konstanzeit arbeiten, während ähm für größere Zahlen die gleichen Algorithmen zum Einsatz kommen, wie sie es in der Grundschule lernen, wie sie Big Integer implementiert, wie sie sie auch nachbauen könnten und dann entsprechend wächst die Komplexität mit der Anzahl Bits.

9:30 Wenn man da ein bisschen drüber nachdenkt, dann fällt einem auf, dass Java ähm ins in zwei Arten verwendet oder beschränkt. Das eine ist, was die Alu in einem Schritt berechnen kann. Das andere ist aber auch als Speicheradressen verwenden wir die gleichen Ins. In Java nicht so direkt, weil wir keine Pointer direkt bearbeiten. Das sieht man in C++ noch expliziter. Aber auch als Indizs der Arrays verwenden den Java int und das hat genau den Grund, dass ja ein Array Zugriff letztlich ein eine Speicherzelle auslesen ist. Das heißt, wie viele Speicherzellen ich ansteuern kann, hängt auch an diesem in. Wenn ich also hier für meinen äh Inttyp W Bits zur Verfügung habe, dann kann ich nur Eingaben bis zur Größe 2 hoch w sinnvoll lesen unter der Annahme, dass die Eingabe quasi ein Array von Zahlen ist.

10:29 Das heißt, ich habe jetzt ein Obergrenze für meine Eingabegröße. War das nicht genau das, was wir vermeiden wollten, dass wir nur bestimmte beste Größen von n haben können? Das ist das, was wir aus was wir vermeiden wollen. Das heißt, der Ausweg ist diese Wortgröße, die Wortbreite, die wächst mit der Eingabegröße oder unsere Maschine wird größer, je größer die Eingabe wird. Das klingt erstmal ziemlich widersinnig. Ich möchte aber kurz motivieren, dass das tatsächlich das richtige Modell ist. Das ist das Modell, mit dem die Welt am meisten Sinn ergibt in der Algorithmik. Einerseits wächst natürlich nicht die eine Maschine mit der Eingabe mit, sondern wenn wir merken, wir kommen an die Grenzen der aktuellen Maschine, dann bauen wir eine neue und dann können wir die größere Eingabe verarbeiten. Und diesen Schritt könnten wir so oft wiederholen, wie halt nötig. Theoretisch Ressourcen endlich und so ignorieren wir hier. Und wenn Sie sich anschauen, was über die Zeit passiert ist und hier ein paar Zahlen dazu, dann ist es in im Wesentlichen genau das, was passiert ist. Also eine Vereinfachung hier, ich habe einfach die Größe des Arbeitsspeichers von verschiedenen Computersystemen von ganz weit zurück ähm mal geplottet.

11:48 Das ist ein logarithmischer Plot. Das ist sehen hier, das wächst wächst eigentlich exponentiell über die Zeit, weil es so ungefähr, sag wir mal ungefähr so eine Gerade als Regressionsgerade könnte man gelten lassen. Das ist eine Gerade in einem Linearenplot über die Zeit, aber logarithmisch auf der Y-Achse. Das heißt, diese Gerade ist eigentlich eine exponentielle Kurve. Murslaw, all diese Sachen, das ist ja nichts Neues. Ähm, der Arbeitsspeicher ist eine ganz gute Näherung für die typische Eingabegröße, die man verarbeitet. Und ich glaube, das ist äh nicht von ungefähr, das ist einfach die Größe von Daten, auf denen ich mit sinnvoller Effizienz arbeiten kann. Und wann immer man eben größeres braucht, hatte man größere Maschinen gebaut oder umgekehrt. Da ist die Kausalität nicht klar, aber die Korrelation ist da. Das ist Arbeitsspeicher oder Eingabegröße.

12:44 Sie können sich auch die Wortbreite über die Zeit angucken. Da ist das Bild etwas durchwachsener, ein bisschen weniger ein klarer Trend über die Zeit, aber sie sehen zumindest, dass hier dieses untere Dreieck quasi leer ist. Also, man hat auch früh schon mal Maschinen gebaut mit großen Wortbreiten, die also große Zahlen in einem Schritt verarbeiten konnten, wenn auch den der Schritt viel langsamer war. Aber was man nicht mehr baut, ist Maschinen mit kleiner Wortbreite und der Grund ist, ich möchte die Wortbreite so wählen, dass ich meinen ganzen Arbeitsspeicher adressieren kann. Und ähm im Wesentlichen sehen Sie natürlich hier diese zwei diese zwei Stufen. 32 Bit und 64 Bit ist eigentlich alles, was wir in jüngerer Zeit noch äh sinnvoll verwendet haben. Und es gab sehr viel mehr Experimentierfreude in der frühen Zeit äh der Informatik und 64 Bit ist für sinnvoll große Eingaben ein Limit. Das wird man wahrscheinlich nicht noch mal verdoppeln müssen. Insofern ist unklar, wie da die Ausgleichsgerade wächst, aber wenn man so ein bisschen die untere Schlanke nimmt, dann kann man auch hier sagen, das ist exponentiell gewachsen.

14:02 Überzeugender ist vielleicht der Vergleich direkt, wenn man aus diesen gleichen Daten oder eine Auswahl der Maschinen so ein Skatterplot macht. Also jetzt habe ich auf der X-Achse die Größe vom Arbeitsspeicher, aber logarithmisch.

14:16 Also das hier hieße eben was smer das dann ist äh 2 hoch 27 weit Arbeitsspeicher und auf der y-Achse ist die Wortbreite und auch da ist ein bisschen bisschen messig, aber so ungefähr ist das schon eine Korrelation, die steigt. Sprich, wenn eine Maschine mehr Eingabe verarbeitet, hat sie auch eine größere Wortbreite.

14:42 Und natürlich ist keine dieser Maschinen irgendwie mitgewachsen. Die wurden halt über die Zeit gebaut. Sie sehen so ein bisschen von blau zu rot ist die Zeit. Also die neuen Maschinen sind alle da oben und dann gab's mal so Experimentierfreude. Im Prinzip ist über die Zeit der Trend auch dieser Linie nach oben folgen.

15:02 Prognosen, die die Zukunft betreffen, sind ja bekanntlich schwierig. ob es noch mal einen Sprung gibt für die für die Wortbreite ist nicht so klar, ob wir den brauchen oder ob es da ähm andere Trends gibt, aber vielleicht ist ihnen ja SIMD in Begriff SD single instruction multiple data könnte man sehen als eine noch größere Wortbreite für manche Operationen. Frage.

15:30 Ähm hier ist es effektiv exponentiell und hier ist es linear. Und das passt ja dazu, dass wir hier auch ähm also linear die Wortbreite ist logarithmisch in der Speicher oder Eingabegröße. Das würde geraden hier entsprechen. Also ich fand tatsächlich ähm überraschend, wie gut das so zu den historischen Daten passt. äh ist natürlich das hier ist asymptotisch gemeint für beliebig große Eingaben. So so ein bisschen ähm ein bisschen die Augen zupzen muss man dabei, aber das ist die Annahme, die auch die Theorie sauber macht und da will ich nicht so tief eintauchen, als dass sie da dann die Details verstehen würden. Das führt uns viel zu weit weg. Aber sozusagen mein Versprechen an Sie ist, wenn Sie die Algorithmen Literatur anschauen, dann ist das so das Credo. Wenn man ein Modell machen möchte, wo die Wortbreite berücksichtigt ist, dann sollte die mit der Eingabe wachsen und etwa logarithmisch.

16:33 Man kann daraus jetzt noch ein detailliertes Maschinenmodell machen, also genau sagen, welche Befehle kann ich ausführen. Das ist so ein bisschen eine hypothetische Rechnerarchitektur. wollen wir nicht im Detail machen, weil wir so detailliert dann die Analysen eh nicht machen. Ähm festhalten möchte ich, dass das die richtige Annahme ist und das bedeutet eben diese zwei Antworten von am Anfang, wie lange dauert jetzt eine Addition? Na ja, hängt halt davon, ob die Zahlen in ein Wort, ein Maschinenwort passen oder nicht. Ja, das äh legt sozusagen diesen Konflikt bei. Äh man kann das dann zu einem konkreten Modell ausformulieren, was so ein bisschen ähnlich ist wie ein Reduced Instruction Set äh Computer ähm der aber unbegrenzten Speicher hat und eben die Wortbreite mit der Eingabegröße mitwächst. Und neben den üblichen arithmetischen Operationen brauchen wir auch bitweise Operationen, um die die volle Power auszuschöpfen. Also Bitweises und bitweises oder alles Dinge, die Java auch kann. Das ist alles äh danach letztlich ähm modelliert.

17:42 Und in der in der Forschung ist das die übliche Annahme. Wenn man genauer wissen will, wie lange dauern Dinge, dann schaut man sich dieses Modell an. Und ich wollte Ihnen diesen Begriff einmal nennen, damit Sie, falls Sie das irgendwo sehen, wissen, was wie das einzuordatmen ist. Ansonsten wie hier angedeutet, brauchen Sie diesen Teil natürlich nicht genauer wissen, als wir es besprochen haben. Insbesondere kein Prüfungsstoff.