============================
Einfache Cache-Optimierungen
============================

Ziele:

    - Bei einigen numerischen Verfahren haben wir mehrere
      ineinander verschachtelte Schleifen mit Array-Zugriffen,
      die frei permutiert werden können. Eine einfache
      Cache-Optimierung könnte darin bestehen, die Schleifen
      einer günstigen Weise anzuordnen.
    - Die Anordnung kann auch zur Laufzeit vorgenommen werden.


Beispiel aus der letzten Session
================================

In der vorherigen Session wurde demonstriert, dass die Laufzeit
der Initialisierung einer größeren Matrix je nach Zugriffsart
deutlich schwanken kann:

---- IMAGE ------------------
session3/bench.initmatrix.svg
-----------------------------

Hier lohnt sich noch einmal ein genauer Blick auf die Funktion
`initMatrix`:

:import:session3/bench_initmatrix.c

Aufgabe 1
---------

 - Im Benchmark wird zunächst `initMatrix(m, n, buffer, 1, m)`
   aufgerufen? Wenn Sie davon ausgehen, dass `sizeof(double) == 8`,
   wie groß ist dann der Abstand in Bytes in Abhängigkeit von
   `m` und `n` bei den Zugriffen auf
   die Matrix `A` zwischen zwei Iterationen der innersten Schleife
   von `initMatrix`?
 - Wie sieht das beim Aufruf von `initMatrix(m, n, buffer, n, 1)`
   aus?
 - Gibt es eine einfache Änderung, nach der Row-Major in der
   Auswertung besser abschneidet?

Aufgabe 2
---------

Gegeben sei folgende Vorlage:

:import:session4/gemv.c

Die Funktion `dgemv` (steht für `double`, _general matrix_,
matrix vector) soll

---- LATEX ----------------------
y \leftarrow \alpha A x + \beta y
---------------------------------

berechnen. Sie ist so mit Cache-Optimierung zu implementieren,
dass es für die Laufzeit keine Rolle spielt, ob die
Matrix $A$ in _row_ oder _column major_ organisiert ist.

:navigate: up    -> doc:index