Technische Zusammenfassung: SEDD – Skalierbare und effiziente Datensatz-Deduplizierung mit GPUs

1. Problemstellung

Die Deduplizierung von Datensätzen im großen Maßstab ist ein kritischer Vorverarbeitungsschritt für das Training von Large Language Models (LLMs), um Datenqualität zu gewährleisten, Rechenverschwendung zu reduzieren und Overfitting zu verhindern. Der Standardansatz zur Erkennung von Near-Duplicates in Web-Scale-Korpora ist MinHash Locality-Sensitive Hashing (LSH). Bestehende Implementierungen stoßen jedoch beim Skalieren auf Datensätze mit Billionen von Tokens auf erhebliche Engpässe:

• CPU-Einschränkungen: Traditionelle CPU-basierte Implementierungen (z. B. unter Verwendung der Bibliothek datasketch) leiden unter schlechter Parallelisierbarkeit und hohen Rechenkosten, was sie für massive Datensätze unangemessen langsam macht.
• GPU-Einschränkungen: Zwar bieten GPU-beschleunigte Frameworks wie NVIDIA NeMo Curator Verbesserungen, bleiben aber aufgrund architektonischer Ineffizienzen suboptimal. Insbesondere verlassen sie sich auf physisches Daten-Shuffling (Neupartitionierung von Daten auf der Festplatte basierend auf Bucket-IDs), was hohe I/O-Latenzen und Kommunikationsaufwand verursacht. Darüber hinaus führen ihre Strategien für sparse Buckets und sequenzielle Ausführungsmodelle oft dazu, dass GPU-Ressourcen nicht vollständig ausgelastet werden, was zu einer Unterauslastung der Hardware-Parallelität führt.

2. Methodik

Die Autoren schlagen SEDD vor, ein hochleistungsfähiges, End-to-End-GPU-beschleunigtes Deduplizierungs-Framework, das für verteilte Clusterumgebungen optimiert ist. SEDD adressiert die identifizierten Engpässe durch drei primäre technische Innovationen:

A. Rechen-effizientes Hashing

SEDD ersetzt Standard-kryptografische oder nicht-kryptografische Hash-Funktionen durch einen Rabin-Karp-Rolling-Hash für die Generierung von MinHash-Signaturen.

• Mechanismus: Im Gegensatz zur CPU-Baseline (SHA-1) oder GPU-Baseline (MurmurHash3), die Hash-Werte für jedes Shingle neu berechnen, ermöglicht der Rolling-Hash, den Hash-Wert eines Shingles aus dem vorherigen Shingle durch wenige arithmetische Operationen (Multiplikation, Addition, Division) abzuleiten.
• Vorteil: Dies ermöglicht eine partielle Wiederverwendung von Hash-Werten über benachbarte Shingles hinweg und reduziert die Rechenkosten für die Generierung von MinHash-Signaturen erheblich.

B. Streaming-basierte Datenpipeline

SEDD eliminiert die Notwendigkeit für physisches Daten-Shuffling (Schreiben von Zwischenergebnissen auf die Festplatte und Neupartitionierung) durch den Einsatz einer streaming-basierten Extraktionsstrategie.

• Mechanismus: Anstatt Daten physisch zu verschieben, um sie nach Bucket-ID neu zu organisieren, verarbeitet SEDD Zwischen-Hash-Dateien on-the-fly. Jeder GPU-Prozess erhält eine Teilmenge von Bändern (Bands) und durchsucht den Speicher, um Signaturen für spezifische Buckets zu extrahieren.
• Double Buffering: Das System nutzt Double Buffering, um Kommunikation (Datentransfer zwischen CPU und GPU) mit Berechnung (GPU-Kernel-Ausführung) zu überlappen und I/O-Latenzen effektiv zu verbergen.
• Vergleichsstrategie: Im Gegensatz zu Baselines, die $O(D)$-heuristiken auf Anchor-Basis verwenden (Vergleich nur eines Anchor-Dokuments mit anderen in einem Bucket), führt SEDD exhaustive $O(D^2)$-All-Pairs-Vergleiche innerhalb jedes Buckets durch. Dies wird durch hochoptimierte benutzerdefinierte CUDA-Kernels ermöglicht.

C. Hardware-bewusste Optimierung

• Kernel-Design: SEDD implementiert benutzerdefinierte CUDA-Kernels für die „Count-Match"-Operation (Vergleich von Signaturvektoren) unter Verwendung eines GEMM-inspirierten, geteilten Designs (Tiled Design), um Datenlokalität und die Nutzung des Shared Memory zu verbessern.
• Parameterauswahl: Das Framework enthält einen automatischen Mechanismus zur Parameterauswahl, der die optimale Anzahl von Buckets ($K$) und parallele Verarbeitungsbatches basierend auf verfügbarer CPU-/GPU-Speicher und Datensatzgröße bestimmt. Die optimale Bucket-Anzahl wird als $K \propto \sqrt{N}$ modelliert, um die Kollisionswahrscheinlichkeit gegen den Overhead des Puffermanagements abzuwägen.

3. Hauptbeiträge

1. End-to-End-GPU-Framework: SEDD wird als vollständiges Framework vorgestellt, das auf einem einzelnen Knoten mit vier GPUs eine Beschleunigung von bis zu 7,8× gegenüber der GPU-Baseline des State-of-the-Art (NVIDIA NeMo Curator) und 158× gegenüber CPU-Baselines erreicht.
2. Optimiertes MinHash LSH: Die Einführung wiederverwendbarer Rolling-Hash-Funktionen und benutzerdefinierter GPU-Kernels beschleunigt die Phase der Signaturgenerierung um bis zu 375× im Vergleich zu CPU-Baselines.
3. Kommunikationseffiziente Pipeline: Durch den Ersatz von physischem Shuffling durch streaming-basierte Extraktion und Double Buffering reduziert SEDD den gesamten Kommunikationsaufwand auf etwa 20 % dessen, was in bestehenden Frameworks zu finden ist.
4. Skalierbarkeit: Das Framework verarbeitet erfolgreich 1,2 Billionen Tokens in nur 3 Stunden auf einem 8-Knoten-Cluster mit 32 GPUs vom Typ V100.

4. Experimentelle Ergebnisse

Die Autoren bewerteten SEDD gegen CPU- (SlimPajama) und GPU-Baselines (NeMo Curator) unter Verwendung der Datensätze RealNews und C4.

• Leistung:
  • Auf einem 100 GB großen RealNews-Datensatz (30 Mio. Dokumente) schloss SEDD die Deduplizierung in 135,2 Sekunden ab, verglichen mit 21.361,4 Sekunden für die CPU-Baseline und 1.048,8 Sekunden für die GPU-Baseline.
  • Allein die Phase der MinHash-Generierung verzeichnete eine Beschleunigung von 375× gegenüber der CPU-Baseline.
  • Skalierungsexperimente zeigten, dass SEDD selbst bei Erhöhung der GPU-Anzahl auf 32 mindestens eine 7× Beschleunigung gegenüber der GPU-Baseline beibehält.
• Genauigkeit:
  • Trotz der Optimierungen behält SEDD eine hohe Genauigkeit bei. Im Vergleich zu einem „Exact MinHash"-Oracle auf kleineren Datensätzen erreichte SEDD eine Jaccard-Ähnlichkeit von 0,956 (für 0,1 Mio. Docs) und 0,966 (für 1 Mio. Docs).
  • Im Vergleich zu NeMo Curator auf großen Datensätzen identifizierte SEDD über 97 % der von NeMo gefundenen Near-Duplicates und deckte zusätzliche Instanzen auf.
  • Das nachgelagerte LLM-Training (LLaMA 3.2-1B) auf SEDD-deduplizierten Daten erzielte über mehrere Benchmarks hinweg (HellaSwag, MMLU, ARC-Easy, WinoGrande) eine Leistung, die der von NeMo-deduplizierten Daten vergleichbar war, obwohl 10 % weniger Tokens verwendet wurden.
• Kommunikationseffizienz:
  • In einer 4-GPU-Umgebung reduzierte SEDD die Kommunikationslatenz von 187,7 s (GPU-Baseline) auf 35,7 s und das Kommunikationsvolumen von 3,45 TB auf 398,9 GB.

5. Bedeutung

Die Arbeit argumentiert, dass SEDD eine praktische und skalierbare Lösung für die wachsenden Anforderungen moderner LLM-Datenpipelines bietet. Indem es die spezifischen architektonischen Ineffizienzen bestehender GPU-Frameworks adressiert – nämlich übermäßiges Daten-Shuffling und schlechte Ressourcennutzung – ermöglicht SEDD die effiziente Verarbeitung von Korpora mit Billionen von Tokens innerhalb von Stunden statt Tagen. Die Autoren betonen, dass diese Effizienz erreicht wird, ohne die Genauigkeit der Duplikaterkennung zu beeinträchtigen, wodurch die resultierenden Datensätze für das Training von State-of-the-Art-Sprachmodellen von hoher Qualität bleiben. Die Arbeit unterstreicht, dass hardwarebewusste Systemoptimierungen, wie Rolling Hashes und Streaming-Pipelines, entscheidend sind, um das volle Potenzial von GPU-Clustern bei Aufgaben der Datenvorverarbeitung auszuschöpfen.