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