Energieeffiziente Sprachmodelle brauchen nur Addition

 (arxiv.org)
2 Punkte von GN⁺ 2024-10-10 | 1 Kommentare | Auf WhatsApp teilen
  • L-Mul ist ein Multiplikationsalgorithmus mit linearer Komplexität, der darauf abzielt, Multiplikation durch Ganzzahl-Addition zu approximieren, ausgehend von der Beobachtung, dass die hohen Energiekosten von LLMs aus Gleitkomma-Multiplikationen stammen
  • fp32-Multiplikation hat 37-mal höhere Energiekosten als int32-Addition; wenn L-Mul auf Tensor-Verarbeitungshardware angewendet wird, hat es das Potenzial, 95 % der Energie für elementweise Gleitkomma-Tensor-Multiplikation und 80 % der Energie für Dot Products einzusparen
  • Die Berechnung lässt Mantissenmultiplikation und Rundung aus, verarbeitet das Vorzeichen per XOR, und die übrigen Bits werden als Addition der Form x[1:] + y[1:] - offset aufgebaut
  • In Experimenten zeigte L-Mul mit 4-bit mantissa eine ähnliche Genauigkeit wie float8-e4m3-Multiplikation, und L-Mul mit 3-bit mantissa erzielte bessere Ergebnisse als float8 e5m2
  • Bei Anwendung von L-Mul-Attention auf vortrainierte LLMs ohne zusätzliches Training betrug der durchschnittliche Verlust bei Aufgaben zur natürlichen Sprachinferenz 0,07 %, während sich die durchschnittliche Genauigkeit bei Vision-Aufgaben um 0,12 % verbesserte

Der Engpass, auf den L-Mul zielt

  • Große neuronale Netze verwenden einen großen Teil der Berechnung für Gleitkomma-Tensor-Multiplikation, und diese Operation hat höhere Energiekosten als Addition
  • L-Mul ist ein linear-complexity multiplication-Algorithmus, der die Multiplikation von Gleitkommazahlen durch Ganzzahl-Addition approximiert
  • Die Einsatzbereiche erstrecken sich über mehrere Rechenschritte
    • Multiplikationen innerhalb des Attention-Mechanismus
    • Matrixmultiplikation
    • Elementweise Multiplikation
  • In Transformer-basierten LLMs hat Attention in Bezug auf die Eingabe-Kontextlänge N eine Komplexität von O(N²) und wird zusammen mit hochdimensionaler Tensor-Multiplikation zu einem zentralen Engpass für die Recheneffizienz

Energiekosten nach arithmetischer Operation

  • Die Tabelle der Operationskosten von Horowitz (2014) zeigt direkt den Energieunterschied zwischen Addition und Multiplikation
    • int8-Addition: 0,03 pJ
    • int32-Addition: 0,1 pJ
    • fp16-Addition: 0,4 pJ
    • fp32-Addition: 0,9 pJ
    • int8-Multiplikation: 0,2 pJ
    • int32-Multiplikation: 3,1 pJ
    • fp16-Multiplikation: 1,1 pJ
    • fp32-Multiplikation: 3,7 pJ
  • fp32-Multiplikation verbraucht 4-mal mehr Energie als fp32-Addition und 37-mal mehr als int32-Addition
  • Die standardmäßige Akkumulationspräzision für Tensor-Multiplikationsergebnisse in PyTorch ist auf fp32 gesetzt
  • Ohne I/O- und Steueroperationen liegt der Energieverbrauch bei Approximation von fp32-Multiplikation durch int32-Addition bei etwa 1/37 ≈ 2,7 %
  • Selbst wenn die Akkumulationspräzision auf fp16 reduziert wird, verbraucht Ganzzahl-Addition nur etwa 4,7 % der Energie einer Gleitkomma-Multiplikation

Wie L-Mul rechnet

  • Normale Gleitkomma-Multiplikation hat für zwei Zahlen x, y die folgende Form
    • (1 + xm) · 2^xe · (1 + ym) · 2^ye
    • Das Ergebnis besteht aus (1 + xm + ym + xm · ym) · 2^(xe+ye) und einem Vorzeichen-XOR
  • Der Rechenengpass ist die O(m²)-Mantissenmultiplikation für die m-bit mantissa
  • L-Mul entfernt xm · ym und approximiert dies in folgender Form
    • (1 + xm + ym + 2^-l(m)) · 2^(xe+ye)
  • l(m) hängt von der Anzahl der Mantissenbits ab
    • wenn m ≤ 3, dann m
    • wenn m = 4, dann ein separater Wert
    • wenn m > 4, dann ein separater Wert
  • Die Implementierung auf Bitebene lässt sich zu einer einfacheren Formel zusammenfassen
    • Vorzeichenbit: x[0] ⊕ y[0]
    • übrige Bits: x[1:] + y[1:] - offset
  • Da das Gleitkommaformat 1 + xm implizit behandelt, kann L-Mul in der tatsächlichen Implementierung aus einem einzigen adder bestehen
  • Wenn die Mantissensumme 2 überschreitet, wird der Carry automatisch an den Exponenten weitergegeben
  • Durch das Überspringen der Mantissenmultiplikation und Rundung, die bei herkömmlicher Gleitkomma-Multiplikation nötig sind, wird der Rechenaufwand reduziert

Anwendung auf Transformer-Attention

  • L-Mul-basierte Attention erzeugt Q, K, V und ersetzt anschließend die Matrixmultiplikation in der Attention-Berechnung durch L-matmul
  • Die Berechnungsform ist wie folgt
    • K = H · Wk
    • Q = H · Wq
    • V = H · Wv
    • A = softmax[L-matmul(Q, Kᵀ) / √d]
    • H′ = L-matmul(A, H)
  • L-matmul ist eine Matrixmultiplikation, bei der alle normalen Gleitkomma-Multiplikationen mit L-Mul umgesetzt werden
  • Diese Struktur senkt die Nutzung von Rechenressourcen, indem sie Gleitkomma-Multiplikation durch Ganzzahl-Addition ersetzt

Analyse von Präzision und Komplexität sowie experimentelle Ergebnisse

  • Die Präzisionsanalyse ist so aufgebaut, dass bewertet wird, bis zu wie vielen Bits sie dem Erhalt der fraction einer Gleitkommazahl entspricht
  • In einer Analyse auf Basis gleichverteilter Operanden ist L-Mul genauer als fp8 e5m2
  • In einer praxisnahen Analyse auf Basis der kombinierten Gewichtsverteilung von fünf vortrainierten LLMs kann bei 5-bit mantissa operands eine höhere Präzision als mit fp8 e4m3 erreicht werden
  • Die experimentellen Ergebnisse stimmen mit der theoretischen Fehlerschätzung überein
    • L-Mul mit 4-bit mantissa hat eine ähnliche Genauigkeit wie float8-e4m3-Multiplikation
    • L-Mul mit 3-bit mantissa hat eine höhere Präzision als float8 e5m2
  • Bei vortrainierten LLMs wurde die Standard-Attention-Implementierung direkt durch L-Mul-Attention ersetzt; zusätzliches Training wurde nicht verwendet
    • durchschnittlicher Leistungsverlust bei Aufgaben zu commonsense, structured reasoning und language understanding: 0,07 %
    • durchschnittliche Genauigkeitsänderung bei visual question answering, object hallucination und free-form visual instruction: 0,12 % Verbesserung
  • In Fine-Tuning-Experimenten erzielte ein Modell, bei dem alle Multiplikationen in Attention, linear transformation und elementweiser Multiplikation durch 3-bit mantissa L-Mul ersetzt wurden, eine ähnliche Leistung wie ein Standardmodell mit float8-e4m3-Akkumulationspräzision
  • Die Schätzung des Rechenaufwands auf Gate-Ebene liegt bei normaler Multiplikation auf folgendem Niveau
    • fp16-Multiplikation: etwa 584
    • fp8-e4m3-Multiplikation: etwa 325
    • fp8-e5m2-Multiplikation: etwa 296
  • Die Schätzung des Rechenaufwands von L-Mul auf Gate-Ebene ist niedriger
    • fp16 L-Mul: etwa 256
    • fp8 L-Mul: etwa 157
  • Da es auf GPUs keine native Implementierung von L-Mul gibt, ist es schwierig, die Effizienz vollständig auszuschöpfen; für L-Mul-basierte Modelle wird empfohlen, sie auf Geräten zu trainieren und zu hosten, in die ein spezielles Architekturdesign integriert ist
  • Die Technik ist patent pending

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-10
Meinungen auf Hacker News

  • Ich erinnere mich noch daran, dass es früher, als Gleitkommaberechnungen auf Intel-CPUs teuer waren, mehrere Methoden gab, mit denen Programmierer das über Integer-Tricks umgingen.
    Chuck Moore, bekannt durch Forth, zeigte eine Methode, bei der Werte wie 1,6 × 4,1 in Zwischenschritten als Integer wie 16 × 41 verarbeitet wurden; erst bei der Ausgabe wurde das Dezimalkomma wieder an die „richtige Stelle“ gesetzt. Wenn der Wertebereich der Gleitkommazahlen auch nach Multiplikation mit 10 nicht über 65536 hinausging, funktionierte das sogar mit 16-Bit-Integern gut und passte gut zu Embedded-Chips, die analoge Werte mit 10-Bit-Genauigkeit mehrmals pro Sekunde schnell berechnen mussten.
    Vor langer Zeit sprach ich auch einmal mit einem Microsoft-Ingenieur, der an Microsoft Streets and Trips gearbeitet hatte. Er sagte, dass sie Zahlen und Berechnungen, die normalerweise Gleitkomma gewesen wären, in ein gepacktes Integer-Format steckten, das nur die tatsächlich benötigte Genauigkeit enthielt, um es auf damaligen CPUs schneller auszuführen und leichter so zu komprimieren, dass es auf eine CD-ROM passte. Screenshots gibt es unter https://archive.org/details/3135521376_qq_CD1

    • Diese Technik nennt man Festkommaarithmetik, und sie ist eine großartige Methode, die mehr Programmierer kennen sollten.
      Korrekt geschriebener Finanzcode sollte sie verwenden, aber in der Finanzbranche habe ich sie, außer auf Mainframes, nicht besonders häufig gesehen. Interessanterweise habe ich Festkommaarithmetik deutlich häufiger in Software-Rasterizern wie FreeType, GDI, WPF und WARP (D3D11-Referenzrasterizer) gesehen.
    • Ich erinnere mich, mit dem Fraktalgenerator FRACTINT aus der Zeit herumgespielt zu haben, als Gleitkomma-Coprozessoren noch nicht verbreitet waren. Er berechnete und zeigte Fraktale mit Festkomma-Mathematik an; damals sahen Fraktale unglaublich cool aus, alle wollten ins Fraktalgeschäft einsteigen, und sämtliche Nobelpreise gingen an Fraktalforscher.
    • Ozaki hat fp64-Matrixmultiplikation mit int8-Tensor-Cores gemacht.
      https://arxiv.org/html/2306.11975v4
      Wirklich interessant.
    • Soweit ich weiß, ist das auch heute noch die beste Art, mit Geld oder Finanzzahlen umzugehen.
    • Dieser konkrete Trick ist als Festkommaarithmetik bekannt. Das ist etwas anderes als Fixpunkte von Funktionen.

  • Die Behauptung lautet in etwa, dass man „bei elementweisen Gleitkomma-Tensor-Multiplikationen potenziell 95 % und bei Skalarprodukten 80 % der Energiekosten einsparen“ könne. Wenn es hier um Convolutional Neural Networks ginge, wäre Rechenoptimierung viel bedeutsamer.
    Transformer sind jedoch eher leicht bei der Berechnung und schwer beim Speicher. Der Flaschenhals liegt darin, die Modellgewichte in die Cores zu bringen, und die zitierten 95 % bzw. 80 % Energieeinsparung beziehen sich nur isoliert auf die Multiplikationsoperationen, nicht auf den gesamten Inferenzprozess.

    • Prefill ist selbst bei einem einzelnen Batch weiterhin compute-bound, ebenso Multi-Batch-Decoding.
      Die ständig wiederholte Aussage „bei Decoder-only-Transformer-Inferenz ist die Speicherbandbreite der Flaschenhals“ ist streng genommen nur beim Decoding mit Batchgröße 1 korrekt. Dann macht man nämlich größtenteils Vektor-Matrix-Multiplikationen.
    • Es ist sogar noch schlimmer. Der Energiegewinn wird im Vergleich zu fp32-Berechnungen angegeben; bei fp8 sind Multiplikatoren aber wirklich klein, sodass Addierer und Shifter bei Energie und Fläche einen größeren Teil der Recheneinheit ausmachen. Der Gewinn dieses Papers dürfte daher kleiner sein.
      Für fp8 liegt die geschätzte Gate-Zahl bei 296 für einen normalen fp8-Multiplikator und bei 157 für diese Technik, der Leistungsgewinn beim Multiplikator wäre also deutlich niedriger. Etwa 50 % ist eine plausiblere Schätzung, und noch einmal: Bei fp8 macht die Addition in Skalarprodukten einen großen Teil der Operationen aus.
      Insgesamt wirkt es ziemlich unehrlich, einen Leistungsgewinn von 80 % und nur geringe Genauigkeitsverluste zu behaupten. Denn der Leistungsgewinn gilt nur für fp32-Operationen, während die geringen Genauigkeitsverluste nur für fp8-Operatoren gelten. Die Genauigkeitsverluste bei fp32 wurden nicht analysiert, und die eingesparte Leistung bei fp8-Skalarprodukten wurde ebenfalls nicht angegeben.
    • fp8 ist klein genug, dass man Multiplikation vermutlich mit deutlich einfacheren Schaltungen als bei größeren Gleitkommaformaten umsetzen kann.
      Bei noch kleineren Formaten wie fp4 könnte man einfach eine Lookup-Tabelle verwenden; damit nähert man sich im Grunde einer einigermaßen standardisierten Quantisierungsmethode an.
    • Eine wirklich gute Architektur für Transformer scheint eine Ko-Lokalisierung von Speicher und Rechenlogik zu sein.
    • Das gilt nur für Einzelnutzer oder leichte Inferenz. Beim Training und bei Batch-Inferenz kann man schnell compute-bound werden.

  • [2023] GradIEEEnt half decent: The hidden power of imprecise lines
    http://tom7.org/grad/murphy2023grad.pdf
    Es gibt auch ein Video: https://www.youtube.com/watch?v=Ae9EKCyI1xU

  • Ich habe es nicht gelesen, aber ich vermute, dass hier in irgendeiner Form Logarithmentafeln verwendet werden.
    Das ist nicht abwertend gemeint; ich frage, weil ich das Gefühl habe, Logarithmen auf einer grundlegenderen Ebene wie Logikgattern nicht richtig zu verstehen. Wenn man Multiplikation in Tabellenzugriffe und Addition umwandeln kann, müsste es umgekehrt doch auch Schaltungen geben, die schwierige Addition und einfache Multiplikation bieten, oder Kombinationen solcher Kompromisse.

    • Log-Raum ist gut, weil man Multiplikation durch Addition ersetzen kann.
      Dieser Teil ist einfach und kann von jedem in Hardware umgesetzt werden. Der schwierige Teil ist die Akkumulation, besonders wenn man über einen großen Bereich akkumuliert und dabei im Log-Raum bleiben will.
    • Genau, so funktioniert ein logarithmisches Zahlensystem.

  • Ich finde es merkwürdig, dass das Paper offenbar keine saubere Herleitung und Diskussion des Fehlerterms enthält. Alles wird nur indirekt über Inferenzergebnisse behandelt.

    • Mir kam dieses Paper auch etwas seltsam vor. Wenn Gate-Schätzungen nur textlich beschrieben werden, ohne Diagramm, übersieht man sehr leicht notwendige Teile.
      Es hätte zumindest eine Abbildung mit Block-Labels wie „Addierer“ geben sollen, auch wenn es keine vollständige Beschreibung auf Gate-Ebene ist. Dass im ersten Absatz der Name de Vries auftauchte, half dem Vertrauen ebenfalls nicht.

  • In einer Fußnote im Methodenteil steht: „Es wird empfohlen, L-Mul-basierte Modelle auf Geräten zu trainieren und zu hosten, in die ein spezielles Architekturdesign integriert ist. Patent angemeldet.“

  • Der Rechenaufwand dürfte sinken, aber da pro Wert weiterhin 8 Bit verwendet werden, verringert sich der für Inferenzläufe benötigte Speicherbedarf nicht.
    Daher ist schwer zu sagen, dass Modelle dadurch für Inferenz zugänglicher werden. Wenn dieses Speicherformat auch fürs Training geeignet ist, könnte das ein potenziell interessanter Anwendungsfall sein.

    • Tatsächlich ist es im Hinblick auf Genauigkeit und Wertebereich um etwa 0,5 Bit pro Gewicht weniger effizient, aber das Paper betont diesen Punkt überhaupt nicht.

  • Das Bewegen von Bytes verbraucht mehr als zehnmal so viel Energie wie Rechnen. Recheneffizienz ist kein so großes Problem, wie viele glauben.
    Im Moment befindet sich die Berechnung nur am falschen Ort; zumindest die anfängliche Aggregation für Skalarprodukte sollte den Speicherbus umgehen und direkt neben der Speicherzelle stattfinden.

    • Könnte es für Geräte mit begrenzter Batteriekapazität trotzdem nützlich sein?

  • Meiner Erfahrung nach waren die wahren Magier der Festkomma-Mathematik die Entwickler von 8-Bit- und 16-Bit-Videospielen.
    Ihre Optimierungen waren erstaunlich und ermöglichten es zum Beispiel, 3D-Matrixmathematik in Echtzeit zu berechnen, um die ersten Flugsimulatoren und Ego-Shooter zu bauen.

    • Den Winkel als 2π = 256 neu zu definieren, war ein ziemlich cleverer Trick.