Spice: Feingranulare Parallelisierung in Zig mit Overhead im Sub-Nanosekundenbereich

Spice: Parallelisierung mit Overhead im Sub-Nanosekundenbereich

Spice erreicht in Zig mit Heartbeat Scheduling eine hoch effiziente Parallelisierung.

• Overhead im Sub-Nanosekundenbereich: Selbst wenn einer Funktion Parallelisierung hinzugefügt wird, entsteht nur ein Overhead von weniger als einer Nanosekunde.
• Keine Konkurrenz: Threads konkurrieren nicht um dieselbe Arbeit. Auch wenn dem System weitere Threads hinzugefügt werden, wird das Programm nicht langsamer.

Leistungsvergleich

• Rayon (Rust): Bei 4 Threads entsteht ein Overhead von etwa 15 ns. Bei 16 Threads wird eine Beschleunigung von etwa dem 14-Fachen erreicht.
• Spice (Zig): Bei 16 Threads wird eine Beschleunigung von etwa dem 11-Fachen erreicht. Wegen des geringen Overheads entspricht die Leistung fast der Grundperformance.

Leistung bei kleinen Bäumen

• Kleine Bäume: Die gesamte Laufzeit des Programms beträgt 1,56 Mikrosekunden. Je mehr Threads hinzugefügt werden, desto schlechter wird die Leistung.
• Allgemeine Weisheit der Parallelisierung: Wenn nicht genügend Arbeit vorhanden ist, lohnt sich Parallelisierung nicht.

Ziele von Spice

• Ziel: Parallelisierung soll hinzugefügt werden können, ohne dass das Programm langsamer wird.
• Kurze Laufzeit: Ist die Laufzeit kurz, funktioniert Multithreading nicht. Zusätzliche Threads wechseln in den Wartezustand.

Verwendung von Spice

const spice = @import("spice");

fn sum(t: *spice.Task, node: *const Node) i64 {
    var res: i64 = node.val;

    if (node.left) |left_child| {
        if (node.right) |right_child| {
            var fut = spice.Future(*const Node, i64).init();
            fut.fork(t, sum, right_child);
            res += t.call(i64, sum, left_child);

            if (fut.join(t)) |val| {
                res += val;
            } else {
                res += t.call(i64, sum, right_child);
            }
            return res;
        }
        res += t.call(i64, sum, left_child);
    }

    if (node.right) |right_child| {
        res += t.call(i64, sum, right_child);
    }

    return res;
}

1. Alle parallelen Funktionen müssen einen Task als Parameter annehmen.
2. Die Funktion darf nicht direkt aufgerufen werden, stattdessen muss t.call verwendet werden.
3. Mit fork wird Arbeit zur Ausführung in einem anderen Thread eingerichtet.
4. Die Funktion muss selbst sinnvolle Arbeit verrichten.
5. Mit join wird auf den Abschluss der Arbeit in einem anderen Thread gewartet.
6. Wenn join null zurückgibt, muss die Arbeit direkt selbst ausgeführt werden.

Work-Stealing und Ineffizienz

• Work-Stealing: Jeder Thread hat seine eigene lokale Work Queue. Ist die Queue leer, stiehlt er Arbeit von anderen Threads.
• Ineffizienz: Dynamischer Dispatch, nicht lokale Work Queues, Spinlocks.

Implementierungsdetails

Optimierung durch statischen Dispatch

• Parallele Ausführung von Codeblöcken: Mit fork und join werden Codeblöcke parallel ausgeführt.
• Deduplizierung: Wenn ein Codeblock nicht in einem anderen Thread ausgeführt wird, läuft er sequenziell.

Heartbeat-Signale mit geringem Overhead

• Heartbeat Scheduling: Alle 100 Mikrosekunden wird die lokale Work Queue geprüft und Arbeit an andere Threads gesendet.
• Effizienz: Funktionen müssen auch dann effizient arbeiten, wenn kein Heartbeat auftritt.

Globaler Mutex

• Verwendung eines globalen Mutex: Ein globaler Mutex ist unproblematisch, solange keine Konkurrenz auftritt.

Verzweigungsfreie doppelt verkettete Liste

• Doppelt verkettete Liste: Wird zur Verwaltung der Work Queue verwendet und arbeitet ohne Verzweigungen.

Minimale Stack-Nutzung

• Optimierung der Stack-Nutzung: Der Zustand von Future wird minimiert, um den Stack-Verbrauch zu reduzieren.

Wertübergabe über Register

• Verwendung von Registern: Felder der Task-Struktur werden zur Leistungsoptimierung über Register übergeben.

Benchmarks

• Benchmarks: Die frühe Entwicklung konzentrierte sich auf einen einzelnen Benchmark.

Danksagung

• Forschung zu Heartbeat Scheduling: Die Entwicklung basiert auf mehreren Forschungsarbeiten.

Einschränkungen

• Einschränkungen: Bei falscher Verwendung kann es zu merkwürdigem Verhalten kommen.
• Zu wenig Tests: Die Testabdeckung ist unzureichend.
• Unzureichende Unterstützung für Arrays/Slices: Die Unterstützung für Parallelisierung bei Arrays/Slices ist begrenzt.
• Mangelnde Dokumentation: Zur Verwendung gibt es zu wenig Dokumentation.
• Zu wenig zusätzliche Benchmarks: Weitere Benchmarks sind nötig.
• Fehlerbehandlung: Die Fehlerbehandlung wurde nicht ausreichend berücksichtigt.
• Zu wenig Tests in ReleaseSafe: Tests im ReleaseSafe-Modus sind erforderlich.

FAQ

• Herkunft des Namens: Der Name steht für sehr feingranulare Parallelisierung.
• Warum in Zig implementiert: Eine Implementierung ist auch in anderen Sprachen möglich.
• Sichere Parallelisierung in Rust: Wegen der strengen Semantik von Rust ist die Erkundung der ursprünglichen Idee schwierig.

Zusammenfassung von GN⁺

• Spice ist ein Forschungsprojekt, das in Zig hoch effiziente Parallelisierung bereitstellt.
• Mit Overhead im Sub-Nanosekundenbereich und konkurrenzfreier Parallelisierung wird die Leistung maximiert.
• Über Heartbeat Scheduling wird Arbeit effizient verteilt.
• Es gibt Einschränkungen wie Randbedingungen und unzureichende Tests.
• Es ist sinnvoll, ähnliche Ansätze auch in anderen Sprachen wie Rust zu untersuchen.

[GN⁺]

Hacker-News-Kommentar

• Diese Implementierung basiert auf der neueren Forschung zu „heartbeat scheduling“ und erreicht eine dynamische automatische Kontrolle der Granularität, indem der Overhead für die Erzeugung von Parallelität verteilt wird

  • Relevante Arbeiten:
    • (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism
    • (2021) Task Parallel Assembly Language for Uncompromising Parallelism
    • (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads
    • (2024) Automatic Parallelism Management

• Ich habe die Details des Codes nicht gelesen, aber „sub-nanosecond overhead“ ist irreführend und ein Marketingbegriff

  • Erstens wirkt die Messung wie eine komplexe Metrik vom Typ „Zeit pro Ding“, und die Anzahl der Threads ist viel kleiner als die Anzahl der „Dinge“

• Ich bin mit diesem Bereich nicht vertraut, aber das vorgestellte Concurrency-Modell gefällt mir

  • Das README ist gut geschrieben und machte den Inhalt leicht verständlich, auch wenn einige Teile schwer zu verstehen waren
  • Zum Glück ist der Code gut lesbar

• Interessante Forschungsarbeit, mit guter Argumentation und gut geschriebener Dokumentation zusätzlich zum Code

  • Auch die Arbeit zu heartbeat scheduling aus dem Jahr 2018 ist interessant

• Liste der Einschränkungen des Projekts:

  • Link zur Liste der Einschränkungen

• Laut Beschreibung verwendet diese Implementierung Busy-Waiting, damit die Worker Latenzen im Nanosekundenbereich erreichen

  • Ich frage mich, wie realistisch Busy-Waiting in großen Anwendungen mit Zehntausenden von Tasks ist
  • Wenn die Tasks asynchron sind (also nicht Thread-basiert), könnte es so viele Wartende geben wie die Größe des Thread-Pools des Executors
  • Der Energieverbrauch einer solchen Architektur dürfte höher sein

• Ich frage mich, ob es einen schnelleren Weg gibt, mit dem ein Task-Produzent einen Konsumenten ohne Busy-Waiting wecken kann

  • Vielleicht wäre es möglich, den Konsumenten im Zeitslice des Produzenten auszuführen
  • Vielleicht ließe sich die übliche Strafe für das Aufwecken des Konsumenten über eine User-Space-FUTEX_WAKE-Operation halbieren

• Interessant und mit großartigen Arbeiten verknüpft

  • Ein Vergleich mit OpenMP-Tasks wäre wünschenswert gewesen
  • Rayon hat den Ruf, etwas langsam zu sein

• Kooperatives Scheduling ist die Grundlage vieler Muster mit hervorragenden Metriken

• Großartig

• Siehe auch das Benchmark-README:

  • Link zum Benchmark-README