path: root/Presentation/transcript.md

# 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*

## EIE Implementation

- Ziel: Annäherung der Formel für jede Aktivierung $b_i = f(\sum\limits_{j=0}^{n-1} W_{ij} a_j) \overset{!}{=} \text{ReLU}(\sum\limits_{j \in X_i \cap Y} S[I_{ij}] a_j)$ möglichst effizient
- $X_i$ Menge an Spalten, wobei 0-Einträge ausgelassen werden
- $Y$ Menge an Einträgen im Inputvektor $a$, die nicht null sind
- $I_{ij}$ 4-bit Index für die Lookup-Tabelle
- $S$ Lookup-Tabelle

*nächste Folie*

- Segmentierung der Eingabematrix auf die verschiedenen processing elements
- Auf dem SRAM-Block in jedem PE ist der für das PE vorgesehene Teil der Spalte $W_j$ gespeichert, jeweils in CSC-Format, mit Zeigern auf das erste Element der jeweiligen Spalte
- Beispiel: In PE0 sind von Spalte $W_0$ die Elemente $w_{0,0}$, $w_{8,0}$, $w_{12,0}$ in $v$ gespeichert, die Nullen dazwischen für alle Elemente in PE0 in $z$, und die Zeiger die Spaltenanfänge
- Farbliche Darstellung von $a$ nur Momentaufnahme, geht durchgehend weiter, $a_j$ werden gebroadcastet
- Jedes PE multipliziert $a_j$ mit den Elementen seiner Zeile und schreibt das Ergebnis in Akkumulator-Register, worin die $b_i$'s gecached und in den SRAM geschrieben werden

*nächste Folie*

- HW Aufbau bestehend aus einem Knoten, der Nullen im Eingabevektor erkennt, und dem eigentlichen Processing Element
- PEs sind jeweils in 4er-Gruppen aufgeteilt, wobei sich alle 4 PEs eine LNZD-Einheit teilen
- PE besteht aus Pointer-Read-Unit (Für die Zeiger auf die Spalten), Sparse-Matrix-Access-Unit (Zum Lesen der Gewichtswerte aus der Matrix), Arithmetic Unit (Zur Multiplikation und Addition), und Read/Write-Unit (Puffern und Schreiben der Output-Werte)

*nächste Folie*

- LNZD-Unit
- Die LNZD-Unit erkennt Nullen im Eingabevektor und überspringt diese
- Bei nicht-null Werten werden diese zusammen mit dem Index an alle PEs gesendet

*nächste Folie*

- Pointer-Read-Unit
- Lesen der Zeiger auf Start-Elemente der Spalten $W_j$
- Elemente sind abwechselnd in zwei verschiedenen SRAM-Banken gespeichert
- Somit können sie gleichzeitig ausgelesen werden

*nächste Folie*

- Sparse-Matrix-Read-Unit
- Liest $v$ und $z$ Vektoren für die betreffende Spalte aus, auf Basis der Zeiger
- Es werden nur 64-Bit Worte gleichzeitig ausgelesen, somit 8 Einträge pro Wort (4 bit Wert, 4 bit Index)

*nächste Folie*

- Arithmetic unit
- Erhält Vektor $v$ und absoluten Zielregister-Index $x$
- Berechnet $b_x = b_x + v \cdot a_j$
- Akkumuliert Index $x$ und berechnet die tatsächliche Zieladresse

*nächste Folie*

- Beinhaltet Input und Output-Werte
- Puffer für Input- und Output-Werte tauschen Rollen nach jeder Schicht (Output-Werte einer Schicht sind die Input-Werte der nächsten Schicht)
- Puffer schreibt und liest nach Bedarf in den SRAM

*nächste Folie*

- ReLU und LNZD-Unit
- Wendet die ReLU-Funktion auf die Output-Werte an
- Führt lokale LNZD durch, und sendet das Ergebnis an die LNZD-Unit der Gruppe

*nächste Folie*

## Evaluation

*obere Grafik*

- Vergleich der Geschwindigkeit bei Berechnung verschiedener Schichten von verschiedenen Modellen
- Standardverfahren
- Alex steht für AlexNet, VGG für VGG-Net (Visual Geometry Group), NT für NeuralTalk
- Als Datensatz zum testen wird ImageNet benutzt, als Framework das Caffe deep learning framework
- Maß der Geschwindigkeit: Größe des Datensatzes geteilt durch den höchsten gemessenen Durchsatz, $[\text{Frames}/\text{s}]$
- Immer nur ein Datensatz (Batch-Size 1), da das System zur Verwendung in Echtzeitszenarien ausgelegt ist
- 1x ist CPU unkomprimiert
- EIE ist 189x (Intel Core i7 5930k), 13x (NVIDIA GeForce GTX Titan X), 307x (NVIDIA Tegra K1) so schnell wie CPU, GPU and mGPU für komprimierte DNN
- Markant ist: Kaum Verbesserung durch Komprimierung auf nicht-dedizierter Hardware (steht in keinem Verhältnis zur EIE, logarithmische Skala)
- Durchsatz: 102 GOP/s unkomprimiert entsprechen 3 TOP/s komprimiert

*untere Grafik*

- Maß für Energieverbrauch: Durchschnittliche Leistungsaufnahme mal Dauer pro Datensatz, $[\text{Frames}/\text{J}]$
- 1x ist wieder CPU unkomprimiert
- EIE ist 24.000x, 3.400x, 2.700x energieeffizienter als CPU, GPU and mGPU
- Auch hier: Kaum Verbesserung durch Komprimierung auf nicht-dedizierter Hardware
- Gründe für hohe Effizienz: Zugriff auf SRAM anstatt DRAM, Kompressionsalgorithmus und Architektur reduziert Anzahl der Speicherzugriffe, Kodierung der spärlichen Matrix durch CSC

*nächste Folie*

- Vergleich der EIE mit verschiedenen Hardware-Acceleratoren
- Modellgröße bei General Purpose Plattformen wie GPUs sehr groß, dafür in allen Effizienz-Parametern unterlegen
- Auch im Vergleich zu anderen ASIC- und FPGA-Architekturen überlegen
- A-Eye (FPGA) nutzt DDR3-DRAM für Speicherzugriffe
- TrueNorth nutzt auch SRAM, aber keine dedizierte Architektur, um komprimierte DNN zu behandeln
- Da-DianNao ist ASIC mit eingebettetem DRAM (also auf dem selben Chip)
- Dafür: Unkomprimierte Implementation, nur kleine DNNs mit 18M Parametern
- EIE besonders in 28nm Strukturbreite mit 256 PEs immer noch 3x so schnell vom Durchsatz und hat bessere Effizienz

*nächste Folie*

## Ausblick

- EIE basiert hauptsächlich auf Algorithmen für die Verarbeitung von komprimierten DNNs, die vorher auf General Purpose Hardware implementiert wurden (GPUs), nur eben als Hardware-Architektur
- Verschiedene Arten der Optimierung: Komprimierung, Kombination mit anderen (orthogonalen) Optimierungsmethoden, Optimierungen an der Hardware
- Komprimierung: Huffman-Kodierung (35-49x Komprimierungsfaktor mit Pruning, Quantisierung, Huffman), HashNets (variable Komprimierungsrate bis zu 64x, je nach Anforderung an Präzision)
- Kombination mit anderen Optimierungsmethoden: In-Memory computation (Berechnung ohne ALU direkt im Speicher), Approximierende Schaltungen (Berechnung mit Aufgabe der Exaktheit)
- Hardware-Optimierungen: Neue Speichertechnologien (z.B. Memristoren)

*nächste Folie*

Literatur

*Ende*