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