===============
Geblocktes GEMM
===============

Implementiert den geblockten GEMM Algorithmus aus der Vorlesung.  Als Vorlage
könnt ihr folgenden Code verwenden oder den eigenen Code entsprechend ergänzen.
Zu implementieren sind:

 - Den Micro-Kernel `ugemm`
 - Den Macro-Kernel `mgemm`
 - Den Frame-Algorithmus `gemm`
 - Die Pack-Funktionen `pack_A` und `pack_B`

Die verschiedenen GEMM Algorithmen
==================================

Alle Algorithmen berechnen die Operation

---- LATEX ---------------------------------------------------------------------
C \leftarrow \beta\,C + \alpha\, A B
\quad\text{mit}\;
A \in \mathbb{M}^{m \times k},\;
B \in \mathbb{M}^{k \times n}
\;\text{und}\;
C \in \mathbb{M}^{m \times n}.
--------------------------------------------------------------------------------

Unterschiede ergeben sich aus verschiedenen Gründen:

- Speicherformat

  Der Frame-Algorithmus erhält Matrizen, die zeilen- oder spaltenweise im Speicher
  liegen können.  Beim Macro- und Micro-Kernel ist das Speicherformat aber nicht
  beliebig.

- Matrix-Dimensionen

  Beim Frame-Algorithmus können die Dimensionen beliebig groß sein.  Beim Macro-Kernel
  sind die Dimensionen nach oben beschränkt.  Und beim Micro-Kernel sind gewisse
  Dimensionen sogar fest vorgegeben.

Die Algorithmen werden also immer spezieller.

Micro-Kernel
------------

- Für die Dimensionen gilt

  ---- LATEX -------------------------------------------------------------------
  A \in \mathbb{M}^{M_r \times k},\;
  B \in \mathbb{M}^{k \times N_r}
  \;\text{und}\;
  C \in \mathbb{M}^{M_r \times N_r}.
  ------------------------------------------------------------------------------

  wobei $M_r$ und $N_r$ bekannte Konstanten sind.

- Für das Speicherformat gilt:

  - $A$ ist spaltenweise und $B$ ist zeilenweise gespeichert.  Zudem sind die
    Elemente in einem zusammenhängenden Speicherbereich.

  - Bezüglich $C$ werden
    keine Annahmen gemacht.

Macro-Kernel
------------

- Für die Dimensionen gilt

  ---- LATEX -------------------------------------------------------------------
  A \in \mathbb{M}^{m \times k},\;
  B \in \mathbb{M}^{k \times n}
  \;\text{und}\;
  C \in \mathbb{M}^{m \times n}.
  ------------------------------------------------------------------------------

  dabei gilt

  ---- LATEX -------------------------------------------------------------------
  m \leq M_C,\quad
   k \leq K_C,\quad
   n \leq N_C
  ------------------------------------------------------------------------------

  wobei $M_C$, $K_C$ und $N_r$ bekannte Konstanten sind.

- Für das Speicherformat gilt:

  - Bezüglich $C$ wird keine Annahme gemacht

  - Matrix $A$ liegt so im Speicher, dass bei der Partitionierung in Paneele
    der Höhe $M_r$, d.h.

    ---- LATEX -----------------------------------------------------------------
    A = \left(\begin{array}{c}
        A_0 \\
        \hline
        A_1 \\
        \hline
        \vdots \\
        A_{m_b-1}
        \end{array}\right),
    \quad m_b = \lceil m/M_r \rceil
    ----------------------------------------------------------------------------

    die einzelnen Paneele in aufeinanderfolgenden, zusammenhängenden Blöcken im
    Speicher liegen.  Die letzte Paneele $A_{m_b-1}$ wurde eventuell mit Nullen
    auf die Höhe $M_r$ aufgefüllt (_Zero Padding_).

  - Matrix $B$ liegt so im Speicher, dass bei der Partitionierung in Paneele
    der Breite $N_r$, d.h.

    ---- LATEX -----------------------------------------------------------------
    B = \left(\begin{array}{c|c|c|c}
        B_0   &
        B_1   &
        \dots &
        B_{n_b-1}
        \end{array}\right),
    \quad n_b = \lceil n/N_r \rceil
    ----------------------------------------------------------------------------

    die einzelnen Paneele in aufeinanderfolgenden, zusammenhängenden Blöcken im
    Speicher liegen.  Die letzte Paneele $B_{n_b-1}$ wurde eventuell mit Nullen
    auf die Breite $N_r$ aufgefüllt (_Zero Padding_).



Vorlage
=======

:import:session8/gemm_blk.cc

:navigate: up    -> doc:index
           back  -> doc:session8/page02