Neue Exponentialfunktion macht SiLU und SoftMax 2× schneller – bei voller Genauigkeit

 (github.com/ggerganov)
1 Punkte von GN⁺ 2024-05-16 | 1 Kommentare | Auf WhatsApp teilen
  • llama.cpp PR #7154 wurde am 17. Mai 2024 in master gemergt; er schreibt die Berechnung von SiLU und SoftMax für GGML auf der CPU mit einer Implementierung auf Basis von llamafiles vektorisiertem expf() neu
  • Das bisherige GGML nutzte aus Geschwindigkeitsgründen eine Lookup-Tabelle short[65536]; die neue Implementierung zielt auf genauere Berechnungen ab und hält den Worst-Case-Rundungsfehler auf aarch64 und SSE2+ bei 2 ULP
  • Im CPU-Performance-Test für SOFT_MAX wurde SSE2+FMA 1,5×, AVX2+FMA 1,9× und AVX512 2,1× schneller; auch auf AMD Ryzen 9 5950X und M2 Ultra wurden gegenüber master etwa 1,5× schnellere Ergebnisse bestätigt
  • Die Änderung umfasst das Hinzufügen von ggml_v_expf() und ggml_v_silu(), das Extrahieren von dupliziertem Code nach ggml_vec_soft_max_f32(), das Entfernen von Funktionen rund um GGML_SILU_FP16 sowie Anpassungen am bedingten SiLU-Pfad für SSE2 oder ARM NEON
  • Nach dem Merge wurden bei Serverläufen mit >1 slots nichtdeterministische Ergebnisse reproduziert; später wurde -ffinite-math-only als Ursache eingegrenzt, was zu einer Build-seitigen Einschränkung führte, dass -fno-finite-math-only erforderlich ist

Ziel der PR-Änderung und Merge-Status

  • PR #7154 trägt den Titel ggml : rewrite silu and softmax for cpu und schreibt die Berechnung von SiLU und SoftMax im GGML-CPU-Pfad von llama.cpp neu
  • Die Änderung begann als Upstreaming der vektorisierten expf()-Funktion aus llamafile
  • Die PR wurde am 17. Mai 2024 in ggml-org:master gemergt; der Merge-Commit wird als 934266c angegeben
  • Der Autor erklärte, dass die neue Methode SoftMax und SiLU genauer berechnen könne als die bisherige Lookup-Tabelle short[65536], die GGML aus Geschwindigkeitsgründen verwendete

Genauigkeit und unterstützter Bereich

  • Der neue Pfad auf Basis von expf() unterstützt aarch64 und SSE2+; der Worst-Case-Rundungsfehler wird mit 2 ULP angegeben
  • In der ursprünglichen Beschreibung hieß es, dass auch AVX2- und AVX512-Implementierungen geschrieben wurden, aber nicht enthalten seien, weil der Vorteil im Vergleich zu SSE2+FMA die zusätzliche Code-Komplexität nicht rechtfertige
  • Auf Basis späterer Benchmark-Ergebnisse wurden AVX2- und AVX512-Code dann ebenfalls aufgenommen
  • In einer separaten Testausgabe wurden 4294967296 numbers tested successfully genannt; außerdem enthielt sie Ergebnisvergleiche zwischen exp und der llamafile-Implementierung für verschiedene Eingabewerte

Umfang der Codeänderungen

  • Die von einem Reviewer zusammengefassten wichtigsten Änderungen lauten wie folgt
    • Entfernen auskommentierter #defines
    • Extrahieren von 5 duplizierten Zeilen nach ggml_vec_soft_max_f32()
    • Entfernen mehrerer Funktionen rund um GGML_SILU_FP16
    • Hinzufügen von ggml_v_expf()
    • Hinzufügen von ggml_v_silu()
    • Anpassen der Präprozessor-Anweisungen, sodass ggml_vec_silu_f32() je nach SSE2- oder __ARM_NEON-Flag eine andere Funktion verwendet
  • Die Anzahl der geänderten Dateien wird in den GitHub-Metadaten mit 1 angegeben
  • Die PR erhielt die Labels refactoring und Review Complexity : High; letzteres enthält den Hinweis, dass tiefes Wissen über LLMs oder GPUs erforderlich sein könnte

Benchmarks und Performance-Ergebnisse

  • ggerganov bestätigte, dass SOFT_MAX auf AMD Ryzen 9 5950X und M2 Ultra etwa 1,5× schneller als master ist
  • Der verwendete Testbefehl lautete wie folgt
make -j tests && ./tests/test-backend-ops -o SOFT_MAX -b CPU perf
  • Später erklärte der Autor, dass der Performance-Vorteil mit demselben Befehl wie folgt steigt
    • SSE2+FMA: 1,5×
    • AVX2+FMA: 1,9×
    • AVX512: 2,1×
  • In einem separaten Entwicklungsskript wurden folgende Werte genannt
    • run_expf(): 2.98601 ns
    • run_llamafile_expf_sse2(): 1.35154 ns
    • run_llamafile_expf_avx2(): 1.16659 ns
    • run_llamafile_expf_avx512(): 1.18844 ns
  • Der Benchmark für llama.cpp server in GitHub Actions verzeichnete auf Standard_NC4as_T4_v3 mit der Konfiguration phi-2 q4_0 543 Iterationen
    • Gleichzeitige Nutzer: 8
    • Dauer: 10 Minuten
    • Durchschnittliche HTTP-Anfrage: 8626.19 ms
    • p95: 21696.44 ms
    • Durchschnittliche Prompt-Verarbeitung: 94.59 tk/s
    • Durchschnittliche Token-Generierung: 33.43 tk/s

Diskussion zur AVX512-Optimierung

  • chriselrod schlug vor, auf AVX512 vscalefps zu verwenden
    • vscalefps berechnet zmm0 = zmm1 * 2^{zmm2}
    • Es könne overflow und underflow korrekt behandeln und dadurch checks und blends entfernen
  • Ein Julia-Implementierungsbeispiel und eine Assembly-Schleife wurden geteilt; falls der Test korrekt sei, habe der maximale Fehler bei x=47.483456f unter 1 ULP gelegen
  • Der vscalefps-Ansatz nutzt keine Lookup-Tabelle; für Float64/double-Implementierungen werde eine Lookup-Tabelle mit 16 Elementen über vpermi2pd verwendet
  • Später wurde auch ein Link zu einer C++-Implementierung geteilt
    • ExpAVX512
    • Der Quellcode befindet sich in include/ExpAVX512.hpp
    • Laut README enthält es Benchmarks, aber keine Vergleichsbenchmarks mit anderen Implementierungen

Nichtdeterminismus nach dem Merge

  • Nach dem Merge wurde ein reproduzierbarer Fall gemeldet, bei dem der Server bei Nutzung von >1 slots nichtdeterministische Ergebnisse ausgab
  • Die minimale Reproduktion sah wie folgt aus
make clean && make server
./server -m models/opt/llama_2-7b-q4_0.gguf --parallel 2 --threads 1
  • Die in einer anderen Shell ausgeführte Anfrage lautete wie folgt
curl --request POST --url http://localhost:8080/completion --header "Content-Type: application/json" --data '{"prompt": "", "n_predict":10, "n_probs": 2, "temperature": -1}' | python3 -m json.tool
  • Die Token-Wahrscheinlichkeiten des letzten Tokens wechselten bei jedem curl-Aufruf zwischen zwei Werten; bei 4 slots wechselten sie zwischen vier möglichen Werten

-ffinite-math-only und Build-Einschränkungen

  • Spätere zugehörige Commits verweisen darauf, dass -ffinite-math-only als Ursache des Problems eingegrenzt wurde
  • Das Problem wurde laut Aufzeichnung darauf zurückgeführt, dass SiLU kleine Werte nicht auf 0 flusht, sondern NaN oder andere Garbage-Werte zurückgibt
  • Der Fix prüft, ob -fno-finite-math-only gesetzt ist, und erzwingt eine Prüfung, dass der Kompilierungsmodus nicht im finite-math-Modus läuft
  • Die Fehlermeldung weist darauf hin, dass einige GGML-Routinen non-finite math arithmetic benötigen, und fordert dazu auf, dem Compiler -fno-finite-math-only zu übergeben
  • Später teilten Nutzer ihre Erfahrungen, dass -Ofast oder -ffast-math -ffinite-math-only enthalten und den Build beschädigen können
    • Bis GCC 13.2 konnte -Ofast verwendet werden, aber ab GCC 14 wurden laut einem Bericht Garbage-Ergebnisse erzeugt
    • In einigen Tests war neben -fno-finite-math-only auch -fmath-errno erforderlich
    • Mehrere Folge-Commits in verschiedenen Repositories verwiesen darauf, dass das Entfernen von -ffast-math oder das explizite Setzen von -fno-finite-math-only ggml-Kompilierungsfehler behob

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-16
Meinungen auf Hacker News

  • Als ich vor etwa 20 Jahren für einen Hughes-Radarsignalprozessor programmierte, musste ich e^x für den Bereich 0 < x < 1 berechnen.
    Der Prozessor hatte Multiplikation, also erstellte ich vier e^x-Tabellen mit jeweils 256 möglichen Werten für jeden der vier 8-Bit-Blöcke eines 32-Bit-Worts und multiplizierte sie, um den Endwert zu erhalten.
    Das war etwa 5-mal schneller als die zuvor beste e^x-Routine. Heute ist das veraltet, aber es war eine interessante Maschine, die Radarsignale eine Zeit lang schneller verarbeitete als Prozessoren, die nominell deutlich schneller waren.

    • Falls das schwer nachzuvollziehen war: Die Idee scheint ungefähr e^x = e^(a+b+c+d) zu sein, wobei a/b/c/d die einzelnen Bytes von x sind; daraus wird e^a * e^b * e^c * e^d, und für jedes davon wird eine Lookup Table für e^a, e^b usw. erstellt.
      Streng genommen hat a eine Form wie high byte << 24, sodass die e^a-Tabelle eine Abbildung a => e^(a<<24) ist; die anderen Bytes werden ähnlich behandelt.

  • Ich frage mich, wie stark sich solche Verbesserungen an SiLU und Softmax auf die gesamte Inferenzgeschwindigkeit von LLMs auswirken.
    Korrigiert mich, wenn ich falsch liege, aber da der Großteil der Zeit für Matrixmultiplikationen draufgeht, dürfte der Effekt dieser Änderung eher klein sein.

    • Es stimmt zwar, dass die meisten Gleitkommaoperationen auf Matrixmultiplikationen entfallen, aber Softmax nutzt unverhältnismäßig viel Speicherbandbreite und dauert deshalb normalerweise deutlich länger, als man allein anhand der Rechenmenge erwarten würde.

  • Etwas off-topic, aber beim Überfliegen dachte ich: „Das wirkt wie eine ziemlich verrückte Optimierung. Komplexer Code, den schon viele Leute gesehen haben.“ Dann sah ich den Contributor und dachte: „Klar, jart. Irre gute Lösungen sind immer jart.“

    • Der Hauptgrund, warum das so einschüchternd aussieht, ist, dass die Intrinsic-Syntax von C/C++ eben so ist.
      Wie bei vielem in diesem Bereich ist dieser Schmerz ziemlich selbstverschuldet.
      Soweit ich weiß, gibt es auch C++-Bibliotheken, die SIMD im Stil von C# und Hardware-Intrinsic-Syntax ermöglichen, aber der Nachteil ist, dass sich die Mnemonics aus den Dokumenten der Befehlssätze nicht direkt nachschlagen lassen.
      Ich will die Bedeutung der Arbeit hier nicht kleinreden, sondern nur sagen, dass sie für ein breiteres Publikum vielleicht zugänglicher hätte sein können. Allerdings will ich damit noch nicht den Vorschlag machen, den hier wohl alle absurd fänden, Inferenz-Backends in C# neu zu schreiben.
    • adapted from arm limited optimized routine — am Ende steht man also doch auf den Schultern von Giganten.
    • Ich glaube nicht, dass so etwas in Vorlesungen zur asymptotischen Analyse gelehrt wird.
      Ich erinnere mich an einen Professor, der sinngemäß berühmt sagte: „Diese Konstante, die alle ignorieren, kann einem im Engineering den ganzen Kopf auffressen.“

  • Es soll eine short[65536]-Lookup Table ersetzen; war das nicht von Anfang an eine etwas plumpe Wahl?
    Das ist im Grunde eine Lookup Table in der Größe des gesamten L1-Caches. Passt das probabilistisch grob zusammen und funktioniert deshalb überraschend gut?

    • Der Grund, warum Lookup Tables überraschend gut funktionieren, ist, dass der Workload selbst extrem cache-unfreundlich ist.
      Es ist ziemlich egal, wenn man den L1-Cache verdrängt; die Daten, die durch die LUT verdrängt wurden, wären ohnehin kaum wiederverwendet worden.
      Machine-Learning-Lasten sind meist Streaming Loads, bei denen in jeder Iteration der gesamte Datensatz linear gelesen wird.
    • Dieser Artikel darüber, warum man Lookup Tables vermutlich nicht verwenden sollte, behandelt allgemein, wann sie angemessen sind: https://specbranch.com/posts/lookup-tables/
      Nach meiner begrenzten Erfahrung kann man ziemlich viel in Echtzeit berechnen, bevor man schneller ist als ein Lookup.

  • Bei llama.cpp geht es um CPU.

    • Ursprünglich wurde es für llamafile entwickelt und ist in den letzten zwei Releases enthalten: https://github.com/Mozilla-Ocho/llamafile/releases/tag/0.8.2
      Jetzt wird es in das llama.cpp-Projekt upstreamed.
      Es gibt weitere Performance-Verbesserungen, die man derzeit nur in llamafile bekommt, zum Beispiel Kawrakows Arbeit, die K quants deutlich schneller gemacht hat.

  • Vielleicht etwas off-topic, aber weiß jemand, wie sich etwas wie ggml im Vergleich zu Runtimes wie tensorflow lite oder onnxruntime schlägt?

    • Ich maintainiere ONNX- und llama.cpp-Flutter-Bibliotheken auf allen 6 True Platforms und kenne mich damit ziemlich gut aus.
      Kurz gesagt: Für LLMs ist llama.cpp richtig, und mit GGML als Kernabhängigkeit geht auch Whisper.
      Für alles andere nimmt man ONNX.
      TF ist wie Apple in der Machine-Learning-Welt: großartig, wenn man vollständig im Google-ML-Ökosystem gefangen ist, aber außerhalb davon praktisch tot. Ein absurder Anteil der HF-Modelle, etwa 94 %, ist PyTorch.
      Ein direkter Inferenz-Performance-Vergleich lohnt sich eigentlich nur zwischen ONNX Whisper und GGML; jemand hat meine llama.cpp-Bibliothek mit Whisper laufen lassen und keinen nennenswerten Performance-Unterschied gemeldet.
    • Entscheidend ist, von welcher Hardware genau die Rede ist.

  • Ist gguf/llama.cpp derzeit für ungebatchte Inferenz auf CUDA-Geräten die performantere Lösung, oder liegt weiterhin exllamav2+flashattention vorne?

    • Auf 2x 4090 ist der Unterschied vernachlässigbar.
      Es gibt wichtigere Unterschiede, etwa einen 4-Bit-KV-Cache.

  • Auch LUTs lassen sich vektorisieren.
    https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
    Ich habe früher auch einmal über Dinge geschrieben, die mit LUTs möglich sind: https://darkcephas.blogspot.com/2018/10/validating-utf8-stri...

    • Stimmt, aber wenn man exp direkt implementiert, reichen je nach gewünschter Genauigkeit etwa 10–20 FMAs.
      Gather oder Permutationen können nur schwer mit reiner Berechnung konkurrieren.

  • In einem ähnlichen Zusammenhang gibt es auch ein schnelleres tanh: https://github.com/microsoft/onnxruntime/pull/20612

    • Gute Arbeit.
      Aber was ist das Ziel? Soll diese GeLU-Approximation schneller werden?
      Wenn man zu erff() zurückgeht, wäre es wahrscheinlich deutlich schneller.

  • Hilft das auch bei ggufs Anwendungsfall des partiellen GPU-Offloadings?
    Wird auch die CPU-Seite schneller?