Das ist auch ein bisschen wichtiger, das zu einer Schleife zu vereinen, wenn ich vor allem die eine Variable,

auf die hier Lesen zugegriffen wird, bzw. Schreiben zugegriffen wird, auf die hier wird Lesen zugegriffen,

später gleich auch wieder brauche. Weil dann, wenn ich da ein paar Mal durchlaufe, dann kann ich davon ausgehen,

dass das A00 nicht mehr im Cache drin ist und dann muss ich es hier wieder reinladen. Das gleiche gilt für C, E, J.

Gut, okay, Sie merken sich dann auch, je nachdem, ob man von der zeitlichen oder von der räumlichen Lokalität profitiert

bei diesen Maßnahmen. Okay, dann sind wir zum Cash-Blogging gekommen. Das sollen Sie dann auch in der Rechnerübung

mal programmieren. Und wie sieht das aus? Also, das ist beispielsweise eben wichtig für eine Matrix-Motiplikation.

Ich hätte jetzt z ist gleich x mal y und ich nehme natürlich wie immer an, also ich habe eine zahlenweise Ablage

der Matrix im Speicher, so wie das üblich ist. Und hier sehen wir also normal, sehen wir die normale

Programm, ein normales Programm, was ebenso eine solche Matrix-Motipikation macht.

Üblicherweise brauche ich dazu drei Schleifen. Und hier laufe ich entlang den Zeilen und hier entlang

den Spalten. Und in der dritten Zeile muss ich dann halt jeweils die einzelnen Elemente hier,

Zeile mal Spalte, also das ist jetzt hier horizontal gezeigt, weil die Matrix eben dann hier

vertikal abgelegt sein soll. Naja, und dann muss ich dann halt hier das richtige Element mit der richtigen Spalte,

mit dem richtigen Zeilen-Element, mit dem richtigen Spalten-Element multiplizieren. Und dann halte ich

erst mal hier das Zeilen-Element fest und gehe dann die Spalte durch und sammle das Ganze dann eben auf.

Ja, das sieht man eigentlich sofort. Ich habe hier drei Schleifen. Jede Schleife wird einmal durchlaufen,

also die Schleifen sind ineinander verschachtelt. Folglicherweise werde ich hier unten N hoch 3

Durchläufe haben. Also ich brauche N hoch 3 Zugriffe auf Z und Y und N Quadratzugriffe auf X.

Und ja, jetzt kann man versuchen, das Ganze so clever zu machen, dass ich die Bereiche von X und von Z und Y

nicht immer nachladen muss, sondern dass ich einen Bereich, das heißt, ich schneide jetzt von dieser Matrix Z und Y,

noch gehen wir gleich aufs nächste Pütchen, von der Matrix Z und Y schneide ich im Prinzip so einen Block raus.

Und bei der Multiplikation gehe ich entlang dieses Blocks in der Hoffnung, dass ich dann immer diesen Block

mehrfach verwenden kann und nicht ein paar Mal im Gegensatz zum Nicht-Blocking-Verfahren nachladen muss.

Okay, das sieht jetzt ein bisschen verwirrend aus, weil wir hier jetzt insgesamt fünf Vorschleifen haben.

Was ist jetzt unterschiedlich? Also fangen wir erst mal hier auf dieses Bild hier.

Wir wandern hier also die Zeile entlang und hier dann den Spalten. Jetzt ist es aber so, dass wir,

wenn wir die Zeile hier entlang wandern, versuchen wir hier so eine Submatrix aus Y da reinzuladen,

also in den Cache-Speicher zu laden und dann marschieren wir eben hier entlang, dass wir hier so einen bestimmten Block

hinnehmen, multiplizieren das da drauf, dann gehen wir da wieder weiter, multiplizieren das da drauf und so weiter und so fort.

Dann gehen wir wieder nach vorne und multiplizieren das mit dem nächsten Spaltenabschnitt und steigen das dann auch gleich immer

in den richtigen Bereich von Z rein. Und da ist dann also eben die Hoffnung, dass wir diesen Ausschnitt sowohl von Y als auch von Z

der Größe B, das ist dann unser Blocking-Faktor, möglichst häufig immer im Cache halten können.

So, und das sehen wir also hier, also farblich markiert, das ist jetzt der Laufindex KK Y, Y und hier I.

Und jetzt habe ich also hier diese fünf Schleifen und hier gehe ich jeweils immer einen Schritt, jetzt immer um die Schrittweite B entlang.

Das sehe ich in der oberen Schleife, ich laufe natürlich bis zur N, aber immer da oben, wenn ich ankomme, springe ich um ein Stück B weiter.

Das heißt also, erstmal will ich hier einen bestimmten Bereich in meinem Cache halten.

Das Gleiche mache ich auch hier für die Spalten und dann komme ich zu dieser Schleife hier, die wir dann N-mal durchlaufen.

Und dann bei der Schleife, gucken wir da mal, dieses Minimum ist einfach KK plus B minus 1,

komme N einfach dazu da, dass ich nicht über die Matrix-Grenze hinauslaufe, also B, falls das so gewählt ist,

dass KK plus B ebenso ein Wert größer N gibt und N ist ja die Gesamtlänge breiter der Matrix, dann sollte es halt entsprechend abgeschnitten werden.

Ok, naja, und dann haben wir, genau, dann laufen wir hier also insgesamt dann B-mal entlang und hier eben auch B-mal entlang.

Also das heißt, wenn wir einmal in dieser Schleife rangekommen sind am Anfang, dann gehen wir genau B-Schritte.

Und jetzt können wir uns mal überlegen, was dann da so passiert, also beispielsweise jetzt für die Matrix,

ich schreibe mal, wie machen wir das jetzt, erstmal machen wir Licht.

So, um jetzt nochmal ein bisschen anzudeuten, also die äußere Schleife, die ist das KK, dann haben wir blau,

und grün haben wir nicht, dann nehmen wir jetzt mal gelb, ok, also wir haben auf jeden Fall diese 1, 2, 3, 4, 5 Schleifen,

machen wir mal Schleife 1, das ist die da außen mit dem Laufindex KK, die wird also insgesamt N durch B-mal durchlaufen.

Dann habe ich die zweite Schleife, da ist der Laufindex, das J, J, auch die wird N durch B-mal durchlaufen.

Dann habe ich die dritte Schleife, das wäre jetzt die mit dem Index I und die wird eben genau N-mal durchlaufen.