Spice: Teknik pemrosesan paralel granular di Zig dengan overhead sub-nanodetik

 (github.com/judofyr)
2 poin oleh GN⁺ 2024-08-14 | 1 komentar | Bagikan ke WhatsApp

Spice: Pemrosesan paralel dengan overhead sub-nanodetik

Spice mencapai pemrosesan paralel yang sangat efisien di Zig dengan menggunakan heartbeat scheduling

  • Overhead sub-nanodetik: Menambahkan kemampuan pemrosesan paralel ke fungsi hanya menimbulkan overhead kurang dari satu nanodetik
  • Tanpa kontensi: Thread tidak saling berebut pekerjaan yang sama. Menambahkan thread ke sistem tidak membuat program melambat

Perbandingan performa

  • Rayon (Rust): Menimbulkan overhead sekitar 15ns pada 4 thread. Pada 16 thread, menghasilkan peningkatan kecepatan sekitar 14 kali
  • Spice (Zig): Pada 16 thread, menghasilkan peningkatan kecepatan sekitar 11 kali. Karena overhead-nya rendah, performanya hampir sama dengan performa dasar

Performa pada tree kecil

  • Tree kecil: Total waktu eksekusi program adalah 1,56 mikrodetik. Semakin banyak thread ditambahkan, performa justru menurun
  • Kebijaksanaan umum dalam paralelisme: Jika pekerjaannya tidak cukup besar, pemrosesan paralel tidak layak dilakukan

Tujuan Spice

  • Tujuan: Menambahkan pemrosesan paralel tanpa membuat program melambat
  • Waktu eksekusi singkat: Jika waktu eksekusi terlalu singkat, multithreading tidak akan bekerja. Thread tambahan akan beralih ke status menunggu

Cara menggunakan 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. Semua fungsi paralel harus menerima task sebagai parameter
  2. Jangan memanggil fungsi secara langsung; gunakan t.call
  3. Panggil fork untuk menyiapkan pekerjaan di thread lain
  4. Fungsi harus melakukan pekerjaan yang bermakna dengan sendirinya
  5. Panggil join untuk menunggu pekerjaan di thread lain selesai
  6. Jika join mengembalikan null, pekerjaan harus dikerjakan langsung

Work-stealing dan inefisiensi

  • Work-stealing: Setiap thread memiliki antrean pekerjaan lokalnya sendiri. Jika antrean kosong, ia mencuri pekerjaan dari thread lain
  • Inefisiensi: Dynamic dispatch, antrean pekerjaan non-lokal, spin lock

Detail implementasi

Optimisasi static dispatch

  • Eksekusi paralel blok kode: Menggunakan fork dan join untuk menjalankan blok kode secara paralel
  • Deduplikasi: Jika blok kode tidak dijalankan di thread lain, maka blok tersebut dijalankan secara berurutan

Sinyal heartbeat ber-overhead rendah

  • Heartbeat scheduling: Setiap 100 mikrodetik, memeriksa antrean pekerjaan lokal dan mengirim pekerjaan ke thread lain
  • Efisiensi: Fungsi harus tetap berjalan efisien ketika heartbeat tidak terjadi

Mutex global

  • Penggunaan mutex global: Mutex global tidak menjadi masalah saat tidak ada kontensi

Doubly linked list tanpa percabangan

  • Doubly linked list: Digunakan untuk mengelola antrean pekerjaan. Beroperasi tanpa percabangan

Meminimalkan penggunaan stack

  • Optimisasi penggunaan stack: Meminimalkan status Future untuk mengurangi penggunaan stack

Mengoper nilai melalui register

  • Penggunaan register: Mengoper field pada struct Task melalui register untuk mengoptimalkan performa

Benchmark

  • Benchmark: Pengembangan awal berpusat pada satu benchmark

Ucapan terima kasih

  • Riset heartbeat scheduling: Dikembangkan berdasarkan beberapa makalah penelitian

Keterbatasan

  • Batasan: Penggunaan yang salah dapat menimbulkan perilaku aneh
  • Kurangnya pengujian: Cakupan pengujian masih kurang
  • Dukungan array/slice masih kurang: Dukungan pemrosesan paralel untuk array/slice masih terbatas
  • Kurangnya dokumentasi: Dokumentasi penggunaan masih kurang
  • Kurangnya benchmark tambahan: Diperlukan benchmark tambahan
  • Penanganan error: Pertimbangan terhadap penanganan error masih kurang
  • Kurangnya pengujian ReleaseSafe: Diperlukan pengujian pada mode ReleaseSafe

FAQ

  • Asal nama: Mengacu pada pemrosesan paralel yang sangat granular
  • Alasan diimplementasikan dengan Zig: Dapat diimplementasikan dalam berbagai bahasa
  • Pemrosesan paralel aman di Rust: Semantik Rust yang ketat menyulitkan eksplorasi ide awal

Ringkasan GN⁺

  • Spice adalah proyek riset yang menyediakan pemrosesan paralel sangat efisien di Zig
  • Overhead sub-nanodetik dan pemrosesan paralel tanpa kontensi memaksimalkan performa
  • Heartbeat scheduling mendistribusikan pekerjaan secara efisien
  • Ada keterbatasan seperti batasan penggunaan dan kurangnya pengujian
  • Pendekatan serupa layak dieksplorasi di bahasa lain seperti Rust

Bacaan terkait

1 komentar

 
GN⁺ 2024-08-14
Komentar Hacker News

  • Implementasi ini didasarkan pada riset terbaru, "heartbeat scheduling", dan mencapai kontrol granulasi otomatis yang dinamis dengan menyebarkan overhead pembuatan paralelisme

    • Makalah terkait:
      • (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

  • Saya belum membaca detail kodenya, tetapi "sub-nanosecond overhead" terasa menyesatkan dan seperti istilah pemasaran

    • Pertama, pengukurannya tampak menggunakan cara yang rumit, yaitu "waktu per thing", dan jumlah thread jauh lebih sedikit daripada jumlah "thing"

  • Saya tidak terlalu paham bidang ini, tetapi saya menyukai model konkurensi yang diajukan

    • README ditulis dengan baik sehingga mudah memahami isinya, meski beberapa bagian cukup sulit dipahami
    • Untungnya, kodenya mudah dibaca

  • Ini pekerjaan riset yang menarik, dan selain kode, ada juga argumen yang bagus serta dokumentasi yang ditulis dengan baik

    • Makalah heartbeat scheduling tahun 2018 juga menarik

  • Daftar keterbatasan proyek:

  • Menurut penjelasannya, implementasi ini menggunakan busy waiting agar para worker dapat mencapai latensi pada tingkat nanodetik

    • Saya penasaran seberapa realistis busy waiting dalam aplikasi besar dengan puluhan ribu task
    • Jika task bersifat asinkron (yakni bukan berbasis thread), bisa saja ada sejumlah waiter sebesar ukuran thread pool milik executor
    • Konsumsi energi dari arsitektur semacam ini kemungkinan akan lebih tinggi

  • Saya penasaran apakah ada cara yang lebih cepat bagi produsen task untuk membangunkan konsumen tanpa busy waiting

    • Saya bertanya-tanya apakah ini bisa dilakukan dengan menjalankan konsumen dalam time slice produsen
    • Saya juga penasaran apakah penalti umum untuk membangunkan konsumen melalui operasi FUTEX_WAKE di ruang pengguna bisa dipangkas setengahnya

  • Menarik dan terhubung dengan makalah-makalah yang sangat bagus

    • Akan menarik jika ada perbandingan dengan task OpenMP
    • Rayon punya reputasi sedikit lambat

  • Penjadwalan kooperatif adalah dasar bagi banyak pola dengan metrik yang sangat baik

  • Hebat

  • Lihat juga README terkait benchmark: