Spice: Zig’de alt nanosaniye ek yükle ince taneli paralelleştirme tekniği

Spice: Alt nanosaniyelik ek yükle paralel işleme

Spice, Zig’de heartbeat scheduling kullanarak son derece verimli paralel işleme sağlıyor.

• Alt nanosaniye ek yük: Bir fonksiyona paralel işleme özelliği eklendiğinde bile yalnızca nanosaniyenin altında bir ek yük oluşuyor.
• Çekişme yok: Thread’ler aynı iş için yarışmıyor. Sisteme thread eklense bile program yavaşlamıyor.

Performans karşılaştırması

• Rayon (Rust): 4 thread’de yaklaşık 15ns ek yük. 16 thread’de yaklaşık 14 kat hızlanma.
• Spice (Zig): 16 thread’de yaklaşık 11 kat hızlanma. Ek yük düşük olduğu için temel performansla neredeyse aynı.

Küçük ağaçlarda performans

• Küçük ağaçlar: Programın toplam çalışma süresi 1.56 mikrosaniye. Thread eklendikçe performans düşüyor.
• Paralel işlemede genel yaklaşım: Yeterli iş yoksa paralel işleme anlamlı değil.

Spice’ın hedefi

• Hedef: Paralel işleme eklense bile programın yavaşlamamasını sağlamak.
• Kısa çalışma süresi: Çalışma süresi kısa olduğunda çoklu thread işe yaramıyor. Eklenen thread’ler bekleme durumuna geçiyor.

Spice kullanımı

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. Tüm paralel fonksiyonlar parametre olarak bir task almalı.
2. Fonksiyonu doğrudan çağırmak yerine t.call kullanılmalı.
3. Başka bir thread’de iş kurmak için fork çağrılmalı.
4. Fonksiyon kendi başına anlamlı bir iş yapmalı.
5. Başka bir thread’deki işin tamamlanmasını beklemek için join çağrılmalı.
6. join null döndürürse iş doğrudan yapılmalı.

Work-stealing ve verimsizlikler

• Work-stealing: Her thread’in kendi yerel iş kuyruğu var. Kuyruk boşalınca başka thread’lerin işlerini çalıyor.
• Verimsizlikler: Dinamik dispatch, yerel olmayan iş kuyrukları, spin lock.

Uygulama ayrıntıları

Statik dispatch optimizasyonu

• Kod bloklarının paralel yürütülmesi: Kod blokları fork ve join kullanılarak paralel çalıştırılıyor.
• Tekrarın kaldırılması: Kod bloğu başka bir thread’de çalıştırılmazsa sıralı olarak yürütülüyor.

Düşük ek yüklü heartbeat sinyali

• Heartbeat scheduling: Her 100 mikrosaniyede bir yerel iş kuyruğu kontrol edilip işler başka thread’lere gönderiliyor.
• Verimlilik: Heartbeat oluşmadığında fonksiyonun da verimli çalışması gerekiyor.

Global mutex

• Global mutex kullanımı: Rekabet olmadığında global mutex sorun oluşturmuyor.

Dalsız çift bağlı liste

• Çift bağlı liste: İş kuyruğunu yönetmek için kullanılıyor. Dallanma olmadan çalışıyor.

Stack kullanımını en aza indirme

• Stack kullanım optimizasyonu: Future durumunu en aza indirerek stack kullanımı azaltılıyor.

Register üzerinden değer aktarma

• Register kullanımı: Task yapısının alanları register üzerinden aktarılıp performans optimize ediliyor.

Benchmark

• Benchmark: İlk geliştirme tek bir benchmark etrafında yapıldı.

Teşekkür

• Heartbeat scheduling araştırması: Geliştirme çeşitli araştırma makalelerine dayanıyor.

Sınırlamalar

• Kısıtlar: Yanlış kullanılırsa garip davranışlar ortaya çıkabilir.
• Yetersiz test: Test kapsamı yetersiz.
• Dizi/dilim desteği eksikliği: Diziler/dilimler için paralel işleme desteği yetersiz.
• Belgeleme eksikliği: Kullanıma dair dokümantasyon yetersiz.
• Ek benchmark eksikliği: Daha fazla benchmark gerekiyor.
• Hata işleme: Hata işleme yeterince ele alınmamış.
• ReleaseSafe testi eksikliği: ReleaseSafe modunda test gerekli.

SSS

• İsmin kökeni: Çok ince taneli paralelleştirmeyi ifade ediyor.
• Neden Zig ile uygulandı: Farklı dillerde de uygulanabilir.
• Rust’ta güvenli paralel işleme: Rust’ın katı semantiği nedeniyle ilk fikirleri keşfetmek zor.

GN⁺ özeti

• Spice, Zig’de son derece verimli paralel işleme sunan bir araştırma projesi.
• Alt nanosaniyelik ek yük ve çekişmesiz paralel işleme ile performansı en üst düzeye çıkarıyor.
• Heartbeat scheduling ile işleri verimli biçimde dağıtıyor.
• Kısıtlar ve yetersiz test gibi sınırlamaları var.
• Rust gibi diğer dillerde de benzer yaklaşımları araştırmak değerli olabilir.

[GN⁺]

Hacker News görüşleri

• Bu uygulama, paralellik üretiminin ek yükünü dağıtarak dinamik otomatik ayrıntılandırma kontrolü sağlayan, yakın tarihli "heartbeat scheduling" araştırmasına dayanıyor

  • İlgili makaleler:
    • (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

• Kodun ayrıntılarını okumadım ama "sub-nanosecond overhead" ifadesi yanıltıcı ve pazarlama dili gibi görünüyor

  • İlk olarak, ölçüm karmaşık bir "şey başına zaman" yöntemi gibi görünüyor ve iş parçacığı sayısı "şey" sayısından çok daha az

• Bu alana aşina değilim ama sunulan eşzamanlılık modelini beğendim

  • README iyi yazılmış, bu yüzden içeriği anlamak kolaydı, ancak bazı kısımlarını anlamak zordu
  • Neyse ki kod okunabilir

• İlginç bir araştırma çalışması; kodun yanı sıra iyi bir mantık ve iyi yazılmış belgeler de var

  • 2018 tarihli heartbeat scheduling makalesi de ilgi çekici

• Projenin sınırlamaları listesi:

  • Sınırlamalar listesi bağlantısı

• Açıklamaya göre bu uygulama, çalışanların nanosaniye düzeyinde gecikme elde etmesi için busy-wait kullanıyor

  • On binlerce göreve sahip büyük uygulamalarda busy-wait'in ne kadar gerçekçi olduğunu merak ediyorum
  • Görevler asenkron ise (yani iş parçacığı tabanlı değilse), yürütücünün iş parçacığı havuzu boyutu kadar bekleyen olabilir
  • Bu mimarinin enerji tüketimi daha yüksek olacaktır

• Görev üreticisinin, busy-wait olmadan tüketiciyi uyandırmasının daha hızlı bir yolu olup olmadığını merak ediyorum

  • Bunun, üreticinin zaman diliminde tüketiciyi çalıştırarak mümkün olup olmadığını merak ediyorum
  • Kullanıcı alanı FUTEX_WAKE işlemiyle tüketiciyi uyandırmanın olağan cezasını yarıya indirmenin mümkün olup olmadığını merak ediyorum

• İlginç ve harika makalelerle bağlantılı

  • OpenMP görevleriyle bir karşılaştırma olmasını isterdim
  • Rayon'un biraz yavaş olduğuna dair bir ünü var

• İşbirlikçi zamanlama, harika metriklere sahip birçok örüntünün temelidir

• Harika

• Benchmark ile ilgili README'ye de bakın:

  • Benchmark README bağlantısı