======================
Zehplusplus-ifizierung
======================

In Session 8 wurde das blockweise Matrix-Produkt GEMM und der zugehörige
Benchmark bereits in C++ implementiert.  Wie folgender Benchmark zeigt,
haben wir das primäre Ziel erreicht, eine einfache GEMM-Implementierung
zu realisieren, die die CPU-Cache Hierarchie effizient ausnutzt:

---- IMAGE -------------------------
session10/step01/report.gemm_blk.svg
------------------------------------

Ab jetzt gibt es mindestens zwei Richtungen, in denen wir weiter gehen
möchten:

- Weitere Optimierungen, die nicht nur die CPU-Caches optimal ausnutzen,
  sondern auch die CPU selbst.
- Verwendung des Matrix-Produktes für numerische Verfahren.


Weitere Optimierungen
=====================
Die Hardware ist noch lange nicht ausgereizt.  Folgende Benchmarks zeigen,
wie mit einem in Assembler programmierten Micro-Kernel die Effizienz
nochmals deutlich gesteigert werden kann:


---- IMAGE ---------------------
session10/bench2.gemm.mflops.svg
--------------------------------

---- IMAGE -----------------------
session10/bench2.gemm.time.log.svg
----------------------------------

---- IMAGE ---------------------
session10/bench2.gemm.time.svg
--------------------------------

Verwendung in numerischen Verfahren
===================================
Unsere Implementierung ist noch sehr an eine reine C-Implementierung angelehnt.
Viele technische Details waren für die Effizienz notwendig, sind aber bei der
Umsetzung eines mathematischen Verfahren gleichzeitig sehr störend.  Zudem ist
unsere Implementierung sehr speziell:

- Die Elemente einer Matrix waren vom Typ `double`.
- Der Index-Typ der Matrizen waren fest codiert als `std::size_t` oder `long`.
- Puffer für Matrix-Blöcke und Matrizen für den Benchmark waren als globale
  Arrays definiert.
- Alles wurde in eine Datei gepackt.

Beim Implementieren eines numerischen Verfahren möchte man möglichst unabhängig
von technischen Details (_float_ oder _double_ oder ein kompexer Datentyp) und
Fragen der Portabilität (_long_ auf Linux oder Solaris) arbeiten.  Wir werden
die Programmiersprache C++ benutzen, um das bisher erreichte zu abstrahieren
und zu verallgemeinern.  Dabei sollte aber nicht die Effizienz leiden.  Wir
gehen deshalb sehr behutsam vor und beginnen mit folgenden Schritten:

- Die Elemente einer Matrix sollen einen beliebigen Typ besitzen können.
- Der Index-Typ einer Matrix soll beliebig sein.
- Zumindest Arrays für Puffer werden dynamisch angelegt.  Wir werden später
  sehen, dass dies für die _Thread-Sicherheit_ eine absolute Notwendigkeit ist.
- Wir zerlegen das Ganze in verschiedene Header-Dateien, um auch in Zukunft
  den Überblick zu behalten:

  - `bench.h` enthält Funktionen für Initialisierung einer Matrix mit
    Zufallszahlen und Berechnung von Matrix-Differenzen.  Für die Zeiterfassung
    werden wir in C++11 eingeführte Funktionen benutzten.
    Alle Funktionen liegen im Namensraum `bench`.
  - `ulmblas.h` enthält einige BLAS-Funktionen, die wir bereits ausreichend
    effizient implementiert haben.  Zum Beispiel: `gecopy`, `gescal` und
    `geaxpy`.  Diese können als Bausteine wiederverwendet werden und liegen im
    Namensraum `ulmBLAS`.
  - `gemm_refcolmajor.h` enthält im Namensraum `refColMajor` eine einfache
    GEMM-Implementierung `gemm`, die alle Matrizen spaltenweise durchläuft.
  - `gemm_blocked.h` enthält im Namensraum `blocked` eine geblockte
    Implementierung `gemm`, die die gesamte Cache-Hierarchie ausnutzt
    (durch Frame-Algorithmus, Pack-Funktionen, Macro-Kernel und Micro-Kernel)

- Der eigentliche Benchmark ist in `gemm_bench.cc` realisiert.

Auf den nächsten Seiten soll diese Aufteilung schrittweise durchgeführt werden.

Vorlage
=======
Als Vorlage für alle weiteren Aufgaben könnt Ihr den Lösungsvorschlag zu
Session 8 benutzen:

:import: session10/step01/gemm_blk.cc

:navigate: up    -> doc:index
           next  -> doc:session10/page02