Added basics and compression to transcript

1 files changed, 180 insertions, 0 deletions

diff --git a/Presentation/transcript.md b/Presentation/transcript.md
new file mode 100644
index 0000000..a6d87bf
--- /dev/null
+++ b/Presentation/transcript.md
@@ -0,0 +1,180 @@
+# EIE: Efficient Inference Engine on Compressed Deep Neural Network
+
+## Vorstellung
+
+- Titel
+- Vorstellung der Person
+
+*nächste Folie*
+
+## Inhaltsangabe
+
+- Recap über wichtige Teile der DNN, die für effiziente Inferenz und Kompression wichtig sind
+- Motivation: Warum ist effiziente Inferenz wichtig und was heißt überhaupt effizient
+- Kompression: Verschiedene Komprimierungsmethoden für neuronale Netze
+- Implementation: Eigentliche Implementation der EIE
+- Evaluation: Vergleich der EIE mit anderen Hardware-Acceleratoren
+- Ausblick: Optmierungsmöglichkeiten und mögliche Implementation anderer Komprimierungsmethoden
+
+*nächste Folie*
+
+## Deep Neural Networks
+
+- Recap
+- Beispiel: LeNet
+- Convolutional Layer (Faltungsoperationen mit Filtern)
+- Fully Connected Layer (Alle Neuronen verbunden, für Klassifizierung)
+- FC benötigt in den meisten Netzen 90-95% des Speichers
+- Jede Schicht: Input vector $a$, Gewichtsmatrix $W$, Multiplikation und Addition, Aktivierungsfunktion in jedem Neuron, Output vector $b$
+
+*nächste Folie*
+
+- Formal: Berechnung von $b_i = f(\sum\limits_{j=0}^{n} W_{ij} a_j)$ für jedes Element im Output-Vektor
+- $W_{ij}$ Eintrag in der Gewichtsmatrix
+- $a_j$ Element im Input-Vektor
+- Multiplikation und Summation (Multiply-Accumulate MAC) über die Elemente im Input-Vektor bzw. Zeile in der Gewichtsmatrix
+- $f$ Aktivierungsfunktion
+- Matrix $W$ kann spärlich besetzt sein (englisch: sparse)
+
+*nächste Folie*
+
+## Motivation
+
+- Metriken: Was bedeutet Effizienz?
+- Durchsatz (Throughput): Wie viel Daten können pro Zeiteinheit verarbeitet werden?
+- Latenz (Latency): Wie lange dauert es, einen einzelnen Datensatz zu verarbeiten?
+- Modellgröße: Wie viel Speicher wird zum Speichern des Modells benötigt (hauptsächlich Gewichte, bei komplexeren Modellen auch Parameter für Aktivierungsfunktion)
+- Energieverbrauch: Wie viel Energie wird benötigt, um eine bestimmte Anzahl an Daten zu verarbeiten
+
+*nächste Folie*
+
+## Memory access
+
+- Klassischer Aufbau eines Hardware-Accelerators
+- Energieverbrauch der einzelnen Speichertypen in der Hierarchie
+- Energieverbrauch korrelliert mit Zugriffszeiten und somit mit Latenz und Durchsatz, da so bei Abfragen aus dem Speicher jedes Mal gewartet werden muss
+- DRAM ist bei Acceleratoren der Stand der Technik, um große DNN zu speichern (bisher ohne Komprimierung)
+- DRAM hat 200x Energieverbrauch im Vergleich zu Registerzugriffen
+- DRAM hat 33x Energieverbrauch im Vergleich zu SRAM-Buffer
+
+*nächste Folie*
+
+- Art und Anzahl der Speicherzugriffe variieren je nach Datenfluss-Modell
+- Acceleratoren können nicht immer eindeutig einem Modell zugeordnet werden, EIE ist eine Mischung aus a) und b)
+- Im Detail werden die einzelnen Modelle nicht vorgestellt
+
+*nächste Folie*
+
+- Hier sind die einzelnen Speicherzugriffe markiert
+- Jeder einzelne Speicherzugriff kostet Zeit und Energie, es ist also eines der Hauptmerkmale zur Optimierung
+
+*nächste Folie*
+
+## Komprimierung
+
+- Welche verschiedenen Speicherarten haben wir in einem Accelerator?
+- Dynamisch: Eingabedaten
+- Statisch: Gewichte, Parameter für Aktivierungsfunktionen
+
+*nächste Folie*
+
+## AlexNet
+
+- Um sich die Größenordnung des benötigten Speichers zu vergegenwärtigen
+- Populäres neuronales Netz, benannt nach designer Alex Krizhevsky
+- 5 convolutional layers
+- 3 fully connected layers
+- $\sim 62$ million parameters
+- $\sim 240$ MB with 32-bit float representation
+- Häufig für Benchmarking von Acceleratoren verwendet
+
+*nächste Folie*
+
+## Basis projection
+
+- Standardmäßig sind die kanonischen Einheitsvektoren die Basisvektoren für die Gewichtsmatrizen
+- Meistens produzieren jedoch andere Basisvektoren, auf die die Zeilenvektoren der Gewichtsmatrizen projiziert werden, bessere Werte
+- Besser = Geringere Werte (ungefähr 0 oder gleich 0)
+- Genau das wird hier gemacht
+- Gewichte als Linearkombination der Basisvektoren darstellbar
+- Beispiel: Von 7% Nullen auf 56% Nullen
+
+*nächste Folie*
+
+## Pruning
+
+- Entferne unwichtige Gewichte, die kaum Einfluss auf die Genauigkeit des neuronalen Netzes haben
+- 3-Schritt-Verfahren: Training, Pruning (Gewichte werden auf 0 gesetzt oder ganze Output-Neuronen in einer Schicht weggelassen), Retraining (ohne die entfernten Gewichte)
+- Wiederholung so lange, bis je nach Verfahren nichts mehr entfernt werden kann oder ein unterer Grenzwert der Genauigkeit unterschritten worden ist
+
+*nächste Folie*
+
+- Mehrere Pruning-Verfahren möglich
+- Betrags-Grenzwert-Verfahren (englisch: magnitude threshold based pruning):  
+    Entferne Gewichte, deren Betrag unter einem bestimmten Grenzwert liegen
+- Optimal Brain Damage / Optimal Brain Surgeon (ja, so heißen die Verfahren wirklich):  
+    - Entfernt Gewichte basierend auf ihrem Einfluss auf die Zielfunktion (Fehlerfunktion, z.B. Quadratische Fehlerfunktion)
+    - Gewichte mit geringem Einfluss werden entfernt
+    - Optimal Brain Damage berechnet die Sensitivitätswerte basierend auf dem Gradienten, Optimal Brain Surgeon basierend auf der Hesse-Matrix
+- Biased weight decay
+    - Entfernen von Gewichten durch Hinzufügen eines Terms im Update-Schritt beim Backpropagation-Algorithmus
+    - Große Gewichte bleiben länger, kleine Gewichte konvergieren zu Null
+    - Während des Trainings, Details außerhalb des Scopes, hier geht es nur um Inferenz, bei der bereits ein vollständig trainiertes NN vorliegt
+
+*nächste Folie*
+
+## Weight quantization
+
+- Gewichtsquantisierung
+- Grob: Floating point Gewichte werden als Ganzzahl-Werte kodiert
+- Wird durch Clustering gelöst
+- Ähnliche Gewichte werden in Clustern gruppiert
+- Jeder Cluster hat einen Mittelwert (centroid), durch den dann jedes Gewicht des Clusters ersetzt wird
+- Am Ende gespeichert werden nur die Cluster indices und die Mittelwerte der Cluster in einem extra Array, welche mit den indizes indiziert werden
+- Durch den Gradienten der Gewichtsmatrix lassen sich die Werte der centroids fine-tunen
+
+*nächste Folie*
+
+- Wie weise ich die Gewichte den Clustern zu?
+- Minimierung der Varianz innerhalb aller Cluster
+- k-means clustering: 1. Initialisiere k cluster centroids, 2. Für alle Gewichte: Füge Gewicht dem Cluster hinzu, dessen Mittelwert am nächsten dran ist, berechne Mittelwerte aller Cluster neu (weil sich der Mittelwert durch das Hinzufügen ja ändert)
+
+*nächste Folie*
+
+- Die Initialisierung der Mittelwerte macht einen entscheidenden Unterschied bezüglich der Genauigkeit der Quantisierung und damit der Genauigkeit des gesamten NN
+- In vielen Anwendungen des k-means clusterings wird die CDF (kumulative Verteilungsfunktion) betrachtet, die Anzahl der Vorkommnisse (y-Achse) äquidistant abgetastet, und die dazugehörigen Werte als Mittelwerte genommen
+- Das führt allgemein dazu, dass die durchschnittliche Abweichung von den eigentlichen Werten am geringsten ist
+- Im Kontext NN: Höhere Werte haben größere Auswirkung auf Ergebnis als niedrige, sind aber selten und somit im CDF-Verfahren unterrepräsentiert, wodurch hohe Abweichungen in solchen Werten entstehen
+- Daher: Lineare Initialisierung
+
+*nächste Folie*
+
+## Huffman encoding
+
+- Zählung und Sortierung der vorkommenden Gewichtswerte
+- Erstellen des Huffman-Baumes: Am seltendsten vorkommende Gewichte unten, je häufiger, desto weiter oben am Wurzelknoten
+- Binärbaum: Kodierung über Kanten 1 und 0
+- Gespeichert werden muss nur der Baum, die Daten können somit z.B. von 1,58 Megabits auf 1,17 Megabits reduziert werden
+
+*nächste Folie*
+
+## HashNets
+
+- Idee: Es müssen keine Indexwerte in der Matrix gespeichert werden
+- Stattdessen: Es existiert eine sog. Hashfunktion $h^{\ell}(i, j)$: Einweg-Funktion, welche den Matrix-Koordinaten $(i,j)$ einen Indexwert für das Lookup-Array $w^{\ell}$ zuweist
+- Somit existiert keine tatsächliche Matrix, sondern sie ist nur virtuell, gespeichert werden muss nur die größe der Matrix, die Hashfunktion und das Lookup-Array
+
+*nächste Folie*
+
+## Speicherformat
+
+- Etabliert hat sich das Compressed Sparse Column (CSC) / Compressed Sparse Row (CSR) Format
+- Je nach dem, ob man PEs des Accelerators nach Spalten oder Zeilen segmentieren und input oder output lokal bleiben möchte
+- EIE nutzt das CSC Format
+- Jede Spalte wird als Vektoren $v$ und $z$ kodiert
+- $v$ enthält alle Gewichte, die nicht null sind
+- $z$ enthält die Anzahl der Nullen vor dem jeweiligen Eintrag in $v$
+- Beispiel: $W_j = [0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3]$ wird zu $v = [1, 2, 0, 3]$, $z = [2, 0, 15, 2]$
+- EIE: $v$'s und $z$'s aller Spalten werden zusammen als ein großes Array-Paar gespeichert, zusammen mit Vektor $p$, wobei $p_j$ ein Zeiger auf das erste Element der Spalte $W_j$ ist
+
+*nächste Folie*
\ No newline at end of file