Datenrepräsentation#

Wir haben bereits die Speicherbandbreite als Performancebegrenzer in vielen Anwendungen kennengelernt. Daher betrachten wir in diesem Kapitel die Anordnung von Daten und den Einfluß auf Performance.

Ein weiteres Thema ist die Numerik. Viele Anwendungen Performancehungrige Anwendungen führen Berechnungen mit Fließkommazahlen durch. Fließkommazahlen werden in Computern mit einer hohen Bandbreite an darstellbaren Zahlen verwendet - der Preis hierfür ist eine beschränkte Genauigkeit. Insbesondere zur Performanceverbesserung werden häufig kleinere Datentypen, z.B. 32 Bit statt 64 Bit, verwendet. Dies hat Auswirkungen auf die numerische Stabilität von Algorithmen.

Daten-Oriented Design#

Speicherzugriffe sind oft der limitierende Faktor bei hochperformanten Anwendungen. Die Speicherhierachie ist aus verschiedenen Ebenen augebaut - je performanter ein Speicher, desto kleiner im Normalfall (Festplatte, SSD, Hauptspeicher, L3-, L2-, L1-Cache, Register). Speicherzugriffe und Caching umfassen meist mehrere benachbarte Datenwerte, z.B. Cache-Lines von 64 Byte. All diese - häufig architekturspezifischen - Eigenschaften können wir ausnutzen, um ein Programm mit einem gewissen Bedarf an Speicherzugriffen so zu schreiben, dass diese möglichst effizient von der Hardware bedient werden. Ein Beispiel haben wir kennengelernt, als wir ein C-Array Zeilenweise statt Spaltenweise durchlaufen sind und somit die Cache-Hit-Rate erhöht haben. Um die verschiedenen Ebenen der Speicherhierarchie gut auszunutzen werden oftmals Datenstrukturen bzw. Abarbeitungsreihenfolgen durchgeführt, die die Arbeit in Blocks auf mehreren Stufen einteilen, die jeweils in einer Ebene abgelegt werden kann. Ein Beispiel ist die geblockte Matrixmultiplikation.

In der strukturierten Programmierung und insbesondere der Objektorientierten Programmierung arbeiten wir häufig mit Arrays of Structures (AoS), die ungünstig für den Datenzugriff oder für die Parallelisierung per SIMD sind. Beispielsweise wurde unser Farbbild als Array von Pixeln abgespeichert:

struct Pixel { 
    unsigned char r;
    unsigned char g;
    unsigned char b;
};

struct Pixel image[640*480];

Bei der pixelweisen Verarbeitung ist eine gute Lokalität gegeben. Schwierig wird es, wenn

  • nur eine Farbe verarbeitet werden soll, dann sind die Cache-Lines zu 2/3 mit nicht benötigten Farbpixeln gefüllt

  • das Alignment eine Rolle spielt (z.B. für SIMD oder bzgl. Cache-Lines), jedes Pixel ist 3 Byte Groß - um ein gutes Alignment zu gewährleisten kann der Compiler es auf 4 Byte “padden”, d.h. aber 25% ungenutzter Mehrspeicher

  • per SIMD die 3 Pixel kombiniert werden sollen, z.B. bei der Graustufenberechnung. Hier müssen erst mal die Register umgeordnet werden

Eine Structure of Array (SoA) Darstellung wäre:

struct Image {
    unsigned char *r;
    unsigned char *g;
    unsigned char *b;
};

Die Lokalität beim Zugriff auf alle Farben eines Pixels leidet (R, G, B Werte eines Pixels sind für Bilder > 64 Pixel in verschiedenen Cache-Lines) aber je nach Anwendung bietet es Vorteile, z.B. für einen Algorithmus der nur Rottöne vearbeitet. Eine SIMD-Graustufenkonvertierung ist auch viel einfacher.

Beide Formate haben je nach Anwendungsfall ihre Vor- und Nachteile. Beim SoA ist zu beachten, dass es Programmierern oftmals schwerer fällt sie zu verstehen/anzuwenden und dass eine Konvertierung in AoS notwendig ist, wenn mit vielen Bibliotheken/anderen Programmen zusammengearbeitet werden soll.

Sparse Matrix / dünnbesetze Matrizen#

Viele Probleme lassen sich mathematisch mit linearer Algebra lösen. Bei vielen Anwendungen sind die zu verwendenden Matrizen nur sehr dünn besetzt, z.B.:

  • Graustufenkonvertierung per Matrix - nur 3 Werte je Spalte entlang der Diagonale; sonst nur Nullen

  • Darstellung von nicht voll/stark vernetzten Graphen, z.B. soziale Netzwerke, Kaufbeziehungen zwischen Produkten und Kunden, Links im Internet

  • Geschaltene Verbindungen von elektronischen Bauteilen

Eine vollständige Darstellung aller Elemente einer Matrix im Hauptspeicher ist ineffizient:

  • Ein Großteil des Speichers sind 0en - es wird viel Speicher für wenig Information belegt

  • Berechnungen mit 0 sind oftmals nicht notwendig - bei Addition kommt das Ursprungselement heraus, bei Multiplikation immer 0. Zu Auffinden der nicht-0-Elemente muss durch alle Elemente gegangen werden

  • Durch die Verteilung der interessanten Werte über den Hauptspeicher ist die Lokalität schlecht und somit mit vielen Cache-Misses zu rechnen

Zur effizienteren Speicherung und Verarbeitung werden daher spezielle Formate verwendet, die nur die Nicht-0-Elemente und deren Positionen in der Matrix speichern. In der folgenden Übung lernen wir das Compressed Sparse Row (CSR) Format kennen.

ÜBUNG: Sparse Matrix Repräsentation und Berechnungen

Siehe hier.

Numerik#

Fließkommazahlen werden in Computern mit einer hohen Bandbreite an darstellbaren Zahlen verwendet - der Preis hierfür ist eine beschränkte Genauigkeit. Zum Beispiel kann ein Float mit 32-Bit darstellen 1e-20, 1, 1e20. Wenn alle 3 Zahlen addiert werden kommt 1e20 raus, weil die anderen beiden Zahlen in den Ungenauigkeitsbereich der großen Zahl fallen. Dies hat Auswirkungen auf:

  • Genauigkeit von Berechnungen insbesondere bei vielen Wiederholungen und immer wieder auftretenden Rundungsfehlern

  • Assoziativität von Operatoren

Wir betrachten in der folgenden Übung ein einfaches Beispiel, wenn viele Zahlen addiert werden. Es gibt viele weitere Besonderheiten oft spezifisch für die Anwendung. Für die Summierung vieler Zahlen gibt es auch weitere komplexere Verfahren, z.B. Kahan Summation.

ÜBUNG: Genauigkeit von Fliesskommazahlen

Siehe hier.