HN-Vorstellung: Matrixmultiplikation mit halb so vielen Multiplikationen

 (github.com/trevorpogue)
3 Punkte von GN⁺ 2024-03-17 | 1 Kommentare | Auf WhatsApp teilen
  • Dieses Repository enthält Quellcode zur Validierung von systolic-array-Architekturen, die in GEMM- und Deep-Learning-Hardwarebeschleunigern dasselbe Ergebnis einer Matrixmultiplikation mit weniger Hardware-Ressourcen oder kürzerer Laufzeit berechnen
  • Der vorgeschlagene Ansatz ersetzt einen Teil der Matrixmultiplikationen durch günstigere Additionen mit geringer Bitbreite und zielt darauf ab, die für dieselbe Leistung benötigten Multiplier zu halbieren oder die Leistung pro MAC-Einheit zu steigern
  • Die Ergebnisse erreichen gegenüber aktuellen Beschleunigern auf ähnlichen Compute-Plattformen eine bis zu 3× schnellere CNN-Inferenz, mehr als 2× Multiplikationsdurchsatz pro Multiplier/Takt sowie geringere Fläche und höhere Taktfrequenz
  • Der Anwendungsbereich umfasst dichte Matrixmultiplikation sowie stark darauf basierende Fully-Connected-Layer, CNNs, RNNs und Attention-Layer/Transformer-Modelle und erzeugt vor allem bei Fixed-Point- und quantisierter Inferenz dieselbe Ausgabe wie bestehende Verfahren
  • Die Architektur ist so ausgelegt, dass sie dieselbe Funktionalität und Schnittstelle wie bestehende systolic arrays beibehält und sich daher ohne zusätzliche Vor- oder Nachverarbeitung durch Austausch der MXU in bestehende Beschleunigersysteme integrieren lässt

Projektziel und Ergebnisse

  • Algebraic Enhancements for GEMM & AI Accelerators enthält den Quellcode für GEMM- und Deep-Learning-Hardwarebeschleunigersysteme
  • Dieses System dient zur Validierung von systolic-array-Architekturen, die effiziente Matrixmultiplikationsalgorithmen in Hardware umsetzen, die vorgeschlagen wurden oder noch nicht ausreichend erforscht sind
  • Ziel ist es, dieselbe Ausgabe mit weniger Hardware-Ressourcen oder in kürzerer Laufzeit zu berechnen
  • Die präsentierten Ergebnisse sind wie folgt
    • Bis zu 3× schnellere CNN-Inferenz gegenüber aktuellen Beschleunigern auf derselben Art von Compute-Plattform
    • Mehr als 2× mults/multiplier/clock cycle und damit über dem konventionellen Limit von 1
    • Geringere Fläche und höhere Taktfrequenz

In Papers und Dissertation validierte Architekturen

Warum die Leistung pro MAC und pro Multiplier steigt

  • Der Großteil der Rechenarbeit in Deep-Learning-Modellen lässt sich typischerweise auf Matrixmultiplikation abbilden, die aus einer Folge von Multiply-Accumulate-Operationen besteht
  • Ohne zusätzliche algebraische Innovation ist der Durchsatz eines Deep-Learning-Beschleunigers durch die maximale Zahl von MAC-Operationen begrenzt, die pro Taktzyklus ausgeführt werden können
  • Deep-Learning-Beschleuniger enthalten viele MAC-Einheiten, daher nehmen Multiplier und MAC-Einheiten in GEMM- und Deep-Learning-Beschleunigern oft einen großen Teil der Hardware-Fläche als Compute-Ressource ein
  • Der Durchsatz eines Beschleunigers kann direkt durch die Anzahl der Multiplier begrenzt sein, die das Hardware-Budget zulässt
    • Bei FPGA-Implementierungen können die DSP-Einheiten zur Instanziierung von MAC-Einheiten vor LUTs und Registern knapp werden
  • Dieses Projekt untersucht Wege, diese Grenze durch algebraic enhancements in Matrixmultiplikationsalgorithmen und Custom-Hardware-Implementierungen zu überwinden

Anwendungsbereich und Einschränkungen

  • Die vorgeschlagenen systolic-array-Hardwarearchitekturen verbessern die Beschleunigung dichter Matrixmultiplikation
  • Sie sind in DNN-Modellen und Layern einsetzbar, die sich überwiegend in Matrixmultiplikation zerlegen lassen
    • Fully-Connected-Layer
    • CNN
    • RNN
    • Attention-Layer und Transformer-Modelle
  • Die meisten Beiträge konzentrieren sich auf Fixed-Point-Datentypen und die Inferenz quantisierter neuronaler Netze
    • Einige Fixed-Point-Konzepte könnten künftig auf Floating Point erweitert werden
    • Da Fixed-Point-Datentypen verwendet werden, erzeugen die vorgestellten Algorithmen und Hardwarearchitekturen dieselbe Ausgabe wie bestehende Algorithmen und Architekturen
    • Die numerische Stabilität ändert sich nicht
  • Die Ergebnisse wurden auf FPGA validiert, doch die vorgeschlagenen Architekturen sind allgemein und die meisten Verbesserungen lassen sich sowohl auf Custom-Integrated-Circuit- als auch auf FPGA-Implementierungen anwenden
  • Die Architektur basiert auf systolic arrays
    • Ein effizienter Designtyp, der in GEMM- und Deep-Learning-Beschleunigern wie Google TPU verwendet wird
    • Einige Konzepte könnten künftig auf non-systolic-array-Designs erweitert werden
    • Sie behält dieselbe Funktionalität und Schnittstelle wie bestehende systolic arrays bei
    • Die algebraic enhancement ist vollständig innerhalb des systolic array self-contained und erfordert keine zusätzlichen Vor- oder Nachverarbeitungsschritte

Vorschau auf die Performance-Ergebnisse

  • Synthese- und Performance-Ergebnisse aus der Kombination der Architekturen aus [1] und [3] erreichen im Vergleich zu aktuellen Beschleunigern auf ähnlichen Compute-Plattformen Folgendes

    • Bis zu 3× schnellere CNN-Inferenz

    • 2× höheres mults/multiplier/clock cycle

Struktur des Beschleunigersystems

  • Das im Quellcode implementierte Deep-Learning-Beschleunigersystem wird verwendet, um die in [1]-[4] vorgeschlagenen systolic arrays zu hosten und zu validieren
  • Die Systemimplementierung ist auf Fixed-Point- und quantisierte Eingabeinferenz für nicht-sparse DNN-Modelle spezialisiert
    • Convolutional-Layer
    • Fully-Connected-Layer
    • Pooling-Layer
  • Alle DNN-Layer werden vollständig in Hardware beschleunigt
  • Ein einzelnes Hardware-Design kann ML-Modelle mit beliebigen Layer-Dimensionen und Kernel-Größen beschleunigen
  • Eingabe-Bitbreite und systolic-array-Dimension lassen sich per Parameter festlegen
  • Es ist außerdem stark als allgemeiner GEMM accelerator optimiert

Hauptblöcke

  • Matrix Multiply Unit / MXU

    • Enthält die systolic-array-Architektur zur Durchführung der Matrixmultiplikation
    • Die in [1]-[4] vorgeschlagenen unterschiedlichen systolic arrays/MXUs werden jeweils an der MXU-Position des Systems ausgetauscht

  • GEMM Unit

    • Enthält MXU, SRAM und Additionslogik
    • Ermöglicht durch Akkumulation von Matrix-Tiles die Ausführung von GEMM für Matrizen beliebiger Größe

  • Post-GEMM Unit

    • Führt neuronale netzspezifische Funktionen auf den Ausgaben der Matrixmultiplikation aus
    • Umfasst Bias-Addition, Inter-Layer-Rescaling für Quantisierung, Aktivierung, Padding und Pooling

  • Memory Unit

    • Enthält On-Chip-SRAM für Layer-Aktivierungen und Logik zur Speicherzugriffssteuerung
    • Implementiert effiziente Hardwarealgorithmen für Caching und Speicherzugriff, die Convolution ohne Datenduplikation oder Verzögerung in-place auf GEMM abbilden
    • Verwendet ein Memory-Partitioning-Schema, bei dem SRAM-Speicher und Steuerung mit halber oder viertel Taktfrequenz laufen, während neue Daten mit voller Taktfrequenz ausgegeben werden, um Gesamtfrequenz und Leistungsaufnahme des Systems zu verbessern

  • Off-chip DDR DRAM

    • Wird zum Speichern der Gewichte verwendet

  • RxTx Unit

    • Zuständig für die PCIe-Schnittstelle zum Host

  • Instruction Unit

    • Dekodiert die vom Host gesendeten Beschleuniger-Instruktionen
    • Ermöglicht es, mit einem einzelnen Hardware-Design ML-Modelle mit beliebigen Layer-Dimensionen und Kernel-Größen zu beschleunigen

Aufbau des Quellcodes

  • compiler
    • Compiler, der Python-ML-Modellbeschreibungen in Beschleuniger-Instruktionen parst
    • Enthält Code zur Anbindung an den PCIe-Treiber, zum Starten der Modellausführung auf dem Beschleuniger, zum Auslesen von Ergebnissen und Performance-Countern sowie zum Testen der Korrektheit
  • rtl
    • Synthetisierbares SystemVerilog accelerator RTL
  • sim
    • Setup-Skripte für die Simulationsumgebung zur Verifikation
  • tests
    • UVM-Testbench-Quellcode, geschrieben in Python und cocotb
  • utils
    • Zusätzliche Python-Pakete und Utility-Skripte für die Entwicklung, die im Projekt verwendet wurden
  • rtl/top/define.svh und rtl/top/pkg.sv
    • Enthalten verschiedene konfigurierbare Parameter
    • FIP_METHOD definiert den systolic-array-Typ, z. B. baseline, FIP, FFIP [1]
    • SZI und SZJ definieren Höhe und Breite des systolic array
    • LAYERIO_WIDTH und WEIGHT_WIDTH definieren die Eingabe-Bitbreite
  • rtl/arith
    • Enthält mxu.sv und mac_array.sv
    • Enthält abhängig vom Wert von FIP_METHOD RTL für die Baseline sowie einige vorgeschlagene systolic-array-Architekturen wie FIP und FFIP [1]

Zusätzliche Dokumentation

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-03-17
Meinungen auf Hacker News

  • Sieht ziemlich cool aus, aber wo ist der Haken? Ich frage mich zum Beispiel, warum das nicht längst in Beschleunigern implementiert ist.
    Ob es wirklich nur ein vergessener Algorithmus ist oder ob es Einschränkungen gibt, die sich auf die Kosten für den Bau von Beschleunigern usw. auswirken.

    • Es ist kein einfacher Software-Algorithmus, sondern eine Optimierung der Hardwarearchitektur.
      Um davon zu profitieren, muss man Hardware bauen, die zu den Dimensionen des Algorithmus passt, und das ist eine kostspielige Entscheidung.
    • Bei einem Fixed-Point-Matrixmultiplikationsbeschleuniger gibt es keinen besonderen Haken; ich würde sagen, es ist einfach ein übersehener Algorithmus.
      Er basiert auf Winograds Algorithmus, und zufällig hat Winograd später auch einen anderen Algorithmus vorgeschlagen, der bei der CNN-Beschleunigung sehr bekannt wurde, weshalb dieser Algorithmus vielleicht weniger Beachtung fand. Das ist allerdings nur eine Vermutung.
    • Es gibt viele Algorithmen für Matrixmultiplikation, und jeder hat ausgeprägte Vor- und Nachteile.
      Es geht immer um den Ausgleich zwischen Genauigkeit, Laufzeit und Skalierbarkeit; bei dieser Methode ist die Genauigkeit bei Gleitkomma möglicherweise schlecht.
    • Ganz vergessen ist er nicht.
      Er lebt in gewissem Umfang in auf Pseudo-Skalarprodukten basierenden Wegman-Carter-Authentifikatoren wie UMAC weiter. Zum Hintergrund siehe Kapitel 3 von [1].
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Ich habe es nur grob überflogen, also korrigiert mich bitte, wenn ich falschliege: Ich habe es so verstanden, dass das kein Ersatz für Matrixmultiplikation ist, sondern ein Approximationsverfahren, das für die Art linearer Systeme, wie man sie in AI/ML sieht, ziemlich gute Ergebnisse liefert.
      Für diesen Einsatzzweck scheint das doch durchaus gut genug zu sein.

  • Mir fiel wieder ein, dass ich 2018 etwas Ähnliches ausprobieren wollte, es dann aber aufgegeben habe, nachdem alle meine Bewerbungen für Promotionsprogramme abgelehnt wurden.
    https://github.com/ixaxaar/pytorch-dni
    Das Konzept hier geht noch einen Schritt weiter: Es versucht, Backpropagation mit einem externen Netzwerk zu replizieren, und behauptet, dass das Gehirn tatsächlich so arbeiten könnte.

    • Ich sehe die Verbindung nicht ganz.
      Diese Arbeit ist eine Low-Level-Optimierung der Matrixmultiplikation, während das verlinkte Repository offenbar versucht, zurückpropagierte Gradienten durch eine günstigere Schätzung zu ersetzen. Mich würde interessieren, worin die Ähnlichkeit zwischen beiden besteht.
    • Das fühlt sich eher nach einer No-free-lunch-Situation an.
      Die Zeit, die man durch diese Approximation der Gradienten spart, dürfte wegen des Genauigkeitsverlusts der Gradienten durch mehr Trainingsiterationen wieder verloren gehen, oder nicht?
    • Abseits der technischen Diskussion würde mich interessieren, womit dieses Architektur-GIF erstellt wurde. Sieht gut aus.

  • Wirklich interessant und lesenswert. Für alle, die in den Kommentaren verwirrt sind, warum das besser sein soll: In dem Paper geht es darum, Matrixmultiplikations-Pipelines für Hardware wie FPGAs oder ASICs zu synthetisieren.
    Auf CPUs oder GPUs sind Additionen und Multiplikationen zeitlich meist ähnlich teuer, sodass man den Unterschied kaum spürt; Multiplikationseinheiten belegen aber deutlich mehr Transistoren. Wenn man die Schaltungskomplexität reduziert, kann man Geschwindigkeit und parallelen Durchsatz erhöhen sowie Leistungsaufnahme und Verdrahtungskomplexität senken. Dieser Ansatz könnte besonders für effiziente Beschleuniger für dünn besetzte Matrixmultiplikation nützlich sein.
    Eine weitere elegante Methode, Multiplikationen in der Matrixmultiplikation zu eliminieren, ist die Verwendung eines anderen Halbrings (Semiring) [1]. Der Tropical Semiring [2] ersetzt zum Beispiel Multiplikation durch Addition und Addition durch min oder max. Es ist weiterhin Matrixmultiplikation, nur mit anderen binären Operationen. Die Forschung in der relativ neuen Disziplin Tropical Algebra [3] ist derzeit ziemlich aktiv und reichhaltig und wird für verschiedene Optimierungsprobleme sowie für Forschung zur Optimierung neuronaler Netze [4] eingesetzt.
    Auch diese Methode passt gut zur Hardware-Synthese, weil die meisten konfigurierbaren Logikblöcke in FPGAs add/min/max in einem Takt ausführen können, während effiziente Multiplikation feste, dedizierte On-Chip-Hardware-Multiplizierer erfordert.
    Eine andere verwandte Möglichkeit, Multiplikation mithilfe eines Halbrings effizient zu entfernen, ist der Log-Halbring (Log Semiring) [5]. Wenn man Wahrscheinlichkeiten wie in Markov-Ketten fortlaufend multiplizieren muss, werden die Zahlen schnell sehr klein, und die Gleitkommagenauigkeit leidet. Skaliert man sie zuerst durch Logarithmieren, wird Multiplikation zu Addition, und Addition wird zu x + log1p(exp(y - x)).
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • Das Paper unter [4] ist wirklich faszinierend.
      Ich bin in diesem Bereich eher Anfänger, aber es scheint zu zeigen, dass sich fast jedes ReLU-Netzwerk als tropicaler Quotient zweier tropicaler Polynome ausdrücken lässt und damit über geometrische Prinzipien wie Oberflächenvisualisierung analysiert werden kann. Es wird auch in neuerer Forschung zitiert: https://scholar.google.com/scholar?cites=1003719112553620451... Ich frage mich, ob es hier nennenswerte Fortschritte gegeben hat.
    • Wow, genau darum geht es bei Unified Algebra.
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • Bei der Aussage, dass Logarithmieren die Zahlen skaliert, sodass Multiplikation zu Addition wird und Addition zu x + log1p(exp(y - x)), ist Addition/Subtraktion im Log-Zahlensystem deutlich teurer als Multiplikation.
      Besonders wenn man auch noch korrekt gerundete Ergebnisse berücksichtigen will, werden die dafür nötigen Hardware-Lookup-Tabellen ziemlich groß.
    • Ist die Methode, durch Logarithmieren Multiplikation in Addition umzuwandeln, nicht derselbe Ansatz, der bei GF(2^x) seit Jahrzehnten verwendet wird?
      Die einzige Einschränkung, die mir einfällt, ist die Größe des Körpers.
    • In gewisser Weise verwandt ist die zahlentheoretische Transformation.
      https://ieeexplore.ieee.org/abstract/document/1451721

  • Erstaunlich, dass das tatsächlich funktioniert.
    Normalerweise ist der Aufwand, zu erkennen, ob man Multiplikation oder Addition verwenden soll, langsamer, als einfach zu multiplizieren. Besonders dann, wenn man riesige Mengen an Arbeit parallel ausführt.

    • Ich frage mich, wie es im Vergleich zu OpenBLAS und cuBLAS abschneidet.

  • Interessant, dass ein 1968 erfundenes Verfahren bis heute nicht für diesen Zweck genutzt wurde.

    • Auch bei GF(2^x) wusste bis zur Mitte des letzten Jahrhunderts niemand, wofür man es verwenden sollte.
      Ach ja, wenn man darüber nachdenkt, existierte die Informatik selbst bis zur Mitte des letzten Jahrhunderts ja auch kaum.

  • Wenn du dich für die mathematische Theorie hinter subkubischen Algorithmen für Matrixmultiplikation interessierst, kannst du hier anfangen: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Es wird vermutet, dass für jede reelle Zahl j > 0 ein n existiert, sodass zwei beliebige n-x-n-Matrizen in O(n^(2+j)) Schritten multipliziert werden können.
    Derzeit ist 2+j = w = 2.3728596 bewiesen, also für j > 0.3728596.

    • Ich bin mir nicht sicher, ob diese Formulierung stimmt.
      Wenn man mit „für jedes j existiert ein n“ beginnt, werden n und j im weiteren Satz zu Konstanten. Dann sagt man nur, dass Matrizen konstanter Größe in konstanter Zeit multipliziert werden können. Das ist technisch korrekt, aber vermutlich war eine stärkere Aussage gemeint.
    • Es scheint, als würden Fortschritte mit der Zeit immer schwieriger.
      Vielleicht gibt es bei j=1/e eine Untergrenze. Ich würde das nicht einmal eine Vermutung nennen; es ist nur eine praktische Konstante in der Nähe des aktuellen Werts. Es wäre ziemlich lustig, wenn die Mathematik uns so einen Streich spielen würde.
    • Zu prognostizieren, dass es für jedes beliebige j > 0 gilt, ist ziemlich kühn.
      Kannst du die Intuition teilen, warum man das glauben sollte?

  • Dieses README erklärt wirklich schlecht, worin die Verbesserung besteht und wie die Anzahl der Multiplikationen halbiert wird.
    Wie sieht die Big-O-Laufzeit aus? Ändert das die bekannte optimale Schranke?
    Auch die Grafiken sind unübersichtlich und erklären kaum, warum dieser Ansatz schneller oder besser sein soll. Deshalb zögere ich, überhaupt bis zum PDF weiterzuklicken.
    Wenn das Projekt Vertrauen schaffen will, sollte es ehrlich und klar erklären, was tatsächlich passiert, und statt Bildern, die Leute mit Hype anlocken sollen, klare Erklärungen und Diagramme liefern. Es ist schwer zu erkennen, ob das ein riesiger Durchbruch ist oder eher nichts Besonderes. Leider wirkt es auch wie eine bewusste Entscheidung, die KI-Welle auszunutzen. Die Alternative, der ich lieber Glauben schenken würde, ist, dass der Autor einfach nachbessern und den Kontext besser liefern muss.

    • Zur Frage „Wie sieht die Big-O-Laufzeit aus?“: Da behauptet wird, die Anzahl der Multiplikationen zu halbieren, hat das keinen Einfluss auf Big O.
      Die Mathematik im Paper (https://arxiv.org/abs/2311.12224), mit der die Zahl der Multiplikationen halbiert wird, ist nicht schwer zu verstehen. Man muss nur Gleichung 2 zur traditionellen Matrixmultiplikation und die Gleichungen 3–6 lesen.
      Es scheint klar, dass man wie beworben die Multiplikationen halbiert, dafür aber viele Additionen/Subtraktionen hinzufügt. Danach wird der Algorithmus besser vektorisiert, und wie bei solchen Arbeiten üblich wird es schnell kompliziert.
      Die Hauptsorge ist die numerische Stabilität.
    • Das README erklärt nicht besonders viel, aber die Einleitung des Papers selbst ist ziemlich zugänglich.
      Ob es bahnbrechend ist: Ich würde es als saubere Verbesserung um einen konstanten Faktor sehen, die direkt auf Fixed-Point-Beschleuniger mit Flächenbeschränkung anwendbar ist. Das wird nicht über Nacht alles verändern, ist aber auch nicht nichts. Gute Arbeit.
    • Ich will nicht elitär klingen, aber ich verstehe den Punkt dieses Kommentars überhaupt nicht.
      Wenn man die Big-O-Notation so wenig versteht, dass man nicht weiß, dass „die Multiplikationen halbieren“ Big O nicht verändert, weiß ich nicht, warum man danach fragt.