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

 (github.com/judofyr)
2 puan yazan GN⁺ 2024-08-14 | 1 yorum | WhatsApp'ta paylaş
  • Spice, Zig'de heartbeat scheduling kullanarak işlevlere paralel çalıştırma olasılığı eklense bile ek yükü 1ns'nin altında tutmayı amaçlayan bir araştırma projesidir
  • Temel tasarım, fork ile başka bir thread'in işleyebileceği işi işaretlemek; ancak hiçbir thread bunu almazsa fallback yapısı sayesinde join sırasında mevcut thread'in işi doğrudan çalıştırmasıdır
  • 100 milyon düğümlü ikili ağaç toplama benchmark'ında Rayon'un tek thread ek yükü yaklaşık 15ns iken ve 16 thread'de baseline'a göre yaklaşık 4,5 kat performans sağlarken, Spice 16 thread'de baseline'a kıyasla neredeyse olduğu gibi yaklaşık 11 kat hızlanma elde etti
  • 1000 düğüm gibi çalışma süresi çok kısa olan işlerde Rayon'un 32 thread'de toplamda 60 kat yavaşladığı bir örnek vardı; Spice ise paralel işlemenin gerekli olmadığına karar verirse ek thread'leri uyutarak multithreading'i başlatmıyor
  • Mevcut implementasyonda testler, dokümantasyon, dizi ve slice desteği ile ek benchmark'lar eksik; ayrıca sıkça @panic kullanılıyor ve yazar, üretimde kullanmadan önce pek çok kısıtın bilinmesi gerektiğini belirtiyor

Spice'ın çözmeye çalıştığı sorun

  • Spice, Zig'de çok ince taneli paralelleştirmeyi düşük ek yükle gerçekleştirmeyi hedefleyen bir projedir
  • Amaç, paralelleştirme eklendiğinde programın yavaşlayıp yavaşlamayacağı konusunda kullanıcının sürekli endişe etmemesidir
  • En yüksek performans için ayrıntılı benchmark'lar gerekir, ancak genel olarak Spice paralellik eklense bile pratikte neredeyse hiç ek yük getirmeyecek şekilde tasarlanmıştır
  • Proje esas olarak bir araştırma projesidir; üretimde kullanmayı düşünüyorsanız önce kısıtları kontrol etmeniz gerekir
  • Eylül 2024 güncellemesiyle, bu fikrin Rust portu olan Chili tanıtıldı

Kullanım şekli ve temel API

  • Spice'ın paralel fonksiyonları, işi koordine etmek için parametre olarak *spice.Task alır
  • Özyinelemeli çağrılar veya paralelleştirilebilir fonksiyon çağrıları doğrudan değil, t.call üzerinden yapılmalıdır
  • fork, başka bir thread'in çalıştırabileceği bir işi ayarlar
  • Fonksiyon, fork sonrasında kendisi de doğrudan anlamlı bir iş yapmalıdır
  • join, başka bir thread'in işi tamamlamasını bekler, ancak null döndürebilir
    • null, başka hiçbir thread'in ilgili işi almadığı anlamına gelir
    • Bu durumda mevcut thread o işi doğrudan kendisi çalıştırmalıdır

“Tüm işler kuyruktan gelmez” tasarımı

  • Spice'ın temel fikri, tüm işlerin kuyruktan başlamamasıdır
  • fork, başka bir thread'in çalıştırabileceği bir iş olduğunu bildirir; ancak diğer thread'ler meşgulse, normal sıralı çalıştırmada olduğu gibi işi mevcut thread işler
  • Paralel çalıştırma olasılığı olmadığında, hot path üzerinde Spice'ın yaptığı iş kabaca kuyruğa push/pop yapmaktan ibarettir; kuyruk öğelerine gerçekten bakmaz
  • Diğer thread'lerle gerçek koordinasyon sabit bir heartbeat sırasında gerçekleşir
    • Yaklaşık her 100 mikrosaniyede bir thread mevcut iş kuyruğunu kontrol eder
    • Kuyruğun en üstündeki işi bekleyen başka bir thread'e aktarır
    • Heartbeat sıklığı düşük olduğu için birkaç yüz ns harcansa bile toplam ek yük küçük kalır

Rayon benchmark'ı ile karşılaştırma

  • 100 milyon düğümlü ikili ağaç toplama, gerçek hesaplamanın çok hızlı olduğu ve bu yüzden paralel framework ek yükünün belirginleştiği bir örnektir
  • Rust'ın Rayon kütüphanesi ile Spice, okunması ve akıl yürütmesi kolay fork/join API biçiminde karşılaştırıldı
  • Rayon benchmark'ında ek yük yaklaşık 15ns olarak ölçüldü
    • 7.48ns'den 22.99ns'ye çıktı
    • 4 thread'de sıralı performans düzeyine geri dönüyor, ancak CPU 4 kat kullanılıyor
    • 16 thread'de Rayon'un kendi bazına göre yaklaşık 14 kat, baseline'a göre ise yaklaşık 4,5 kat hızlanma sağlandı
  • Spice, 1 thread'den 16 thread'e çıkıldığında yaklaşık 11 kat hızlanma gösterdi
    • Ölçeklenmesi Rayon'dan biraz daha kötü olsa da düşük ek yük sayesinde baseline'a göre hızlanma neredeyse aynen korunuyor
  • Benchmark, Google Cloud'un c4-standard-16 instance'ında, 16 çekirdekli bir ortamda çalıştırıldı
  • Zig baseline'ının Rust baseline'ından yaklaşık 2 kat daha hızlı olmasının nedeni net değil
    • compiled assembly verisine göre Rust stack'e 5 register kaydederken Zig 3 register kaydediyor

Küçük işlerde davranış

  • 1000 düğümlü ikili ağaç toplama, toplam çalışma süresi birkaç mikrosaniye düzeyinde olan çok kısa bir iştir
  • Rayon bu durumda yaklaşık 19ns ek yük gösterdi ve daha fazla thread eklendikçe performans kötüleşti
  • 16 çekirdekli bir makinede 32 thread kullanıldığında toplam çalışma süresi 60 kat yavaşladı
    • 32 çekirdekli bir makinede de aynı yavaşlamanın olacağını kesin olarak söylemek mümkün değil
    • Yine de bu tür ölçeklenme davranışı kaygı verici olarak değerlendiriliyor
  • Geleneksel paralelleştirme kararı genelde “yalnızca yeterli iş olduğunda değerlidir” biçimindedir
    • “Yeterli iş” eşiğini girdi bazında benchmark ile belirlemek gerekebilir
    • İkili ağaç gibi yalnızca root'a bakarak toplam boyutu anlaşılamayan girdilerde bunun küçük bir iş olup olmadığını anlamak zordur
    • İş yükünün %90'ı küçük girdilerden oluşuyorsa aşırı yavaşlama ciddi bir sorun olabilir
    • Program geliştikçe “yeterli iş” eşiği de değişebilir
  • Spice, aynı 1000 düğümlü örnekte çalışma süresinin çok kısa olduğuna karar verip multithreading'i başlatmıyor
    • Ek thread'ler uyur durumda kalıyor
    • Çekirdekler başka programları çalıştırmak için kullanılabiliyor

Work-stealing ile Spice arasındaki fark

  • Spice, fork/join modelini sunar ve bu model genellikle work-stealing ile uygulanır
  • Tipik bir work-stealing yaklaşımında her thread'in yerel bir iş kuyruğu vardır; kuyruk boşalınca başka bir thread'in kuyruğunun sonundan iş çalar
  • Work-stealing verimsizlikleri üç başlıkta özetlenir
    • Tüm işler generic bir “dinamik fonksiyon çağrısı” biçimine dönüştüğü için dinamik dispatch maliyeti oluşur
    • Yerel kuyruklar fiilen tüm thread'lerin çalabildiği kuyruklar olduğundan atomik işlemler gerekir
    • Kuyruk çekişmesi sırasında spinning oluşur ve bazı koşullarda 10 ila 100 kat yavaşlama görülebilir
  • Spice bu verimsizlikleri doğrudan azaltır
    • İş kuyruğundaki dinamik dispatch yalnızca iş başka bir thread'e gönderildiğinde kullanılır
    • Tek thread içinde yapılan işler normal fonksiyon çağrılarını kullanır
    • İş kuyruğuna push işlemi stack pointer, mevcut stack frame ve register kaydıyla yapılır; diğer thread'lerle senkronizasyon gerekmez
    • wait() çağrısı olmadan dönen while döngüleri bulunmadığından spinning yoktur

Implementasyon ayrıntıları

  • Statik dispatch optimizasyonu

    • Spice, fork edilen işlerin çoğunun başka bir thread tarafından alınmayacağını varsayarak ilgili kod yolunu fonksiyon içine kopyalı şekilde yerleştirir
    • İş başka bir thread tarafından çalıştırılmazsa program, sadece birkaç tahmin edilebilir branch eklenmiş sıralı sürüm gibi davranır
    • Bu yapı, inlining gibi kod optimizasyonları ve CPU yürütmesi açısından avantajlıdır

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

    • Heartbeat scheduling, scheduling'i yerelde ve düşük frekansta gerçekleştirir
    • Yaklaşık her 100 mikrosaniyede bir thread yerel iş kuyruğuna bakar ve başka thread'lere iş gönderir
    • Her 100 mikrosaniyede 100ns harcamak toplamda yaklaşık %0,1 ek yük demektir
    • İşletim sistemi sinyalleri yerine işbirlikçi biçimde tick() çağrılır
      • t.call yardımcı fonksiyonu kullanıldığında tick() otomatik çağrılır
      • Ayrı bir heartbeat thread'i, her thread'in atomic heartbeat değerini periyodik olarak false'dan true'ya çevirir
      • tick(), bu değeri okuyup true olduğunda heartbeat kodunu çalıştırır
    • Heartbeat fonksiyonu cold olarak işaretlenmelidir; aksi halde ek yük çok daha yüksek olur

  • Çekişmesiz global mutex

    • Spice'ın thread pool'unda birden çok yerden kilitlenen tek bir mutex vardır
    • Global mutex ancak thread'ler gerçekten block olduğunda sorun yaratır
    • Spice'ta heartbeat nedeniyle genellikle bir anda yalnızca tek bir thread heartbeat çalıştırır
    • Kilit tutulurken kullanıcı kodu çalıştırılmaz; sadece sabit zamanda biten basit bellek okuma/yazmaları korunur

  • Branch'siz çift bağlı liste

    • Spice, iş kuyruğunu izlemek için çift bağlı liste kullanır
    • fork() sona append yapar, join() iş hâlâ duruyorsa sondan pop yapar, arka plan worker'a gönderirken ise baştan pop yapar
    • Normal bir append işlemi listenin boş olup olmadığını kontrol eden bir koşul gerektirir
    • Spice, her zaman var olan sentinel bir head düğümü kullanarak listenin hiç boş olmamasını sağlar ve push/pop işlemlerini branch'siz yürütür

  • Stack kullanımını en aza indirme

    • Future, queued veya executing durumlarından birindedir
    • Heartbeat, queued durumundaki future'ı executing durumuna geçirir
    • Executing durumunda gereken ek durum, ayrı bir pool-allocated struct içinde tutulur; böylece queued future'ın stack kullanımı azaltılır
    • prev_or_null adlı ilk alanın null olup olmamasına bakarak queued/executing ayrımı yapan manuel bir tagged union yapısı kullanılır

  • Değerleri register ile aktarma

    • Task, owning worker pointer'ı ile iş kuyruğu tail pointer'ını tutar
    • LLVM çoğu zaman struct aktarmayı stack üzerinden yaptığı için Spice, worker ve job_tail için ayrı fonksiyon parametreleri alan callWithContext fonksiyonunu tanımlar
    • Bu fonksiyon her zaman inline edilecek şekilde çağrılır; böylece pointer parametreleri register üzerinden aktarılır

Araştırma temeli ve ilgili çalışmalar

Mevcut kısıtlar

  • Spice yanlış kullanıldığında sert davranışlar sergileyebilir
    • Özellikle fork ve join kullanım biçimine karşı hassastır
    • Bunun compile-time kontroller, debug-mode assertion'lar ve API değişiklikleriyle iyileştirilmesi gerekir
  • Çok fazla concurrency kodu olmasına rağmen test kapsamı 0
  • İnce taneli paralelliğin yaygın kullanım alanı olan dizi ve slice öğelerini işlemek için yerel destek yok
  • Kullanımı açıklayan iyi dokümantasyon eksik
  • Şu anda yalnızca tek ve küçük bir benchmark etrafında test edilmiş durumda
    • İlgili benchmark'ın temsil gücü olduğu düşünülse de sonuçların doğrulanması için ek benchmark'lar gerekiyor
  • Hata işlemede yoğun biçimde @panic kullanılıyor
    • Uygun bir Zig kütüphanesi sayılabilmesi için hata durumlarının daha kapsamlı ele alınması gerekir
  • Zig'in ReleaseSafe modunda ne kadar iyi çalıştığını görmek için ek benchmark ve testler gerekiyor
  • Tüm kod tabanı yaklaşık 500 satır ve yazarın şu anda zaman yetersizliği nedeniyle Spice'ı geliştirmeye yönelik aktif bir planı yok
  • Fork'lar veya başka dillere yeniden implementasyon yoluyla iyileştirme yapılması öneriliyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-08-14
Hacker News yorumları

  • Bu uygulama, son dönemdeki araştırma akımlarından heartbeat scheduling üzerine kurulu; paralellik oluşturma maliyetini amorti ederek bir tür dinamik otomatik iş birimi kontrolü sağlıyor
    İlgili makaleler:
    (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
    (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

    • Bu gerçekten ilginç; Spice'ı yazarken yalnızca ilk iki makaleden haberdardım
      Son iki makaleye de mutlaka bakmayı düşünüyorum

  • Kodu ayrıntılı okumadım ama 1 nanosaniyenin altında overhead ifadesi yanıltıcı bir pazarlama cümlesi gibi görünüyor
    İlk bakışta, thread sayısının “iş” sayısından çok daha az olduğu bir durumda hesaplanmış karmaşık bir “iş başına süre” ölçümü gibi duruyor

    • Yazarıyım
      Bazılarının bu ifadeye olumsuz tepki vereceğini biliyordum; ama niyetim Spice ve Rayon'un tam olarak ne zaman ve nasıl kullanılması gerektiğini daha iyi anlaşılır kılmaktı
      Benchmark belgesini okumanızı öneririm: https://github.com/judofyr/spice/blob/main/bench/README.md
      Paralel kodları karşılaştırırken genelde yalnızca sıralı/referans uygulama ile tüm thread'leri (16 adet) kullanan paralel uygulama karşılaştırılır. 100M vakasında Rayon değerleri sıralı sürüm için 7.48ns, Rayon için 1.64ns idi; bu durumda “Rayon bu problemde 4,5 kat daha hızlıydı ama 16 thread kullandı, dolayısıyla pek adil değil” deyip bitirmek kolay. Bu doğru, ama bunu başka tür problemlere nasıl uygulayacağınızı öğrenmek zor
      Aynı benchmark'ı farklı thread sayılarıyla çalıştırınca daha ilginç noktalar görülüyor. Rayon'un scheduler'ı işi ayrı thread'lere bölmekte epey iyi; ancak tüm iş yürütme mekanizmasının yaklaşık 15ns overhead'i var. Bu program tamamen işe yaramaz bir örnek olsa bile sonradan uygulayabileceğimiz bir gerçeği öğreniyoruz: Rayon kullanmak için en küçük iş biriminin muhtemelen kabaca 7ns'den büyük olması gerekir. Ancak toplam throughput'tan feragat edilse bile toplam latency'yi azaltmak daha önemliyse bu bir istisna
      Rayon dokümantasyonu herhangi bir sayı vermiyor; yalnızca “kavramsal olarak join() çağrısı, iki thread oluşturup her birinde bir closure çalıştırmaya benzer; ancak uygulama oldukça farklıdır ve çok düşük overhead'e sahiptir” diyor: https://docs.rs/rayon/latest/rayon/fn.join.html
      Yanıltıcı olmak isteseydim “Spice 10 kat hızlanma sağlıyor, Rayon 4,5 kat; yani Spice Rayon'dan iki kat hızlı” derdim
    • “1 nanosaniyenin altında overhead” ifadesinin yanıltıcı bir pazarlama cümlesi olabilmesi için 1 thread Spice - paralel olmayan referans uygulama farkının 1ns'den büyük olması gerekir
      Test sonuçları iddiayı destekliyor: https://github.com/judofyr/spice/tree/main/bench
    • Bu, alıntılanan Rayon'un ekosistemdeki konumu ile de aynı değil mi diye düşünüyorum
      Binlerce ila milyonlarca işi işlemeniz gerekiyor, onlarca çekirdek içinde mümkün olduğunca paralelleştirmek istiyorsunuz ve scheduling overhead'i tarafından yenip bitirilmek istemiyorsunuz; bu yüzden iş başına overhead'e bakan bir yapı
    • Dün Reddit'e geldiğinde benchmark konusunda kaygılarımı dile getirmiştim
      Benchmark çağrı başına 0.36ns overhead iddia ediyor, ancak yalnızca hesaplama fonksiyonunu içeriyor. Scheduling yapan ikinci bir thread var ama overhead değerine dahil edilmiyor. Hyper-threading'li 8 çekirdekli, yani 16 thread'li bir makinede çalıştırılmış gibi görünüyor; 3GHz varsayarsak bu kelimenin tam anlamıyla bir çevrim overhead demek
      Her ek thread ile kilit çekişmesi nedeniyle overhead artıyor. 16 thread'de 3.6ns'ye çıkıp 10 kat artıyor. Tahminim doğruysa bu, 0.36ns overhead'in çekişmesiz bir kilidi içerdiği anlamına gelir ki bu imkansız. Benchmark verilerinde başka tuhaflıklar da var. Ya gerçekte neyi ölçtüğünü ben anlamıyorum ya da benchmark kodunda bir hata olabilir
      Tüm değerleri çarptığınızda süreyi milisaniye düzeyinde ölçüyor gibi görünüyor. Çalışma süresi hesaplanıp milisaniyeye dönüştürüldüğünde tam sayıya yuvarlanıyor. Benchmark araçları genelde bundan daha iyi hassasiyet kullanmaz mı? Yalnızca time prog kullanıldığı için veri çok gürültülü olabilir ya da bu amaç için tamamen işe yaramaz bir metrik seçilmiş olabilir
    • README'yi okursanız başlıktaki iddianın tam olarak ne anlama geldiğinin çok hassas biçimde açıklandığını düşünüyorum
      Hiç yanlış anlaşılma payı olmayan bir başlık yoktur; bu başlık bence gayet iyi. Benim anladığım, belirli bir ölçüte göre son derece düşük latency'ye sahip bir kütüphane olduğuydu; README'de de o ölçütün ne olduğunu doğrulayabildim. Gayet net

  • Bu alana çok aşina değilim ama burada önerilen eşzamanlılık modeli hoşuma gitti
    README de çok iyi yazılmış; sadece okuyarak bile neler olup bittiğine dair fikir ediniliyor. Yine de birkaç yerde kafam karıştı. Neyse ki kod oldukça okunabilir

    • Debug modunda zig build ile derleyince Baseline,3.92809172, Spice 1 thread,19.1012624 çıktı
      ReleaseSafe modunda zig build --release=safe ile derleyince Baseline,3.264224280000001, Spice 1 thread,3.78043278 çıktı
      Yani Spice, release derlemesi değilse performansta epey büyük bir düşüş yaşıyor. Referans uygulama Zig’in Debug derleme modunda aynı ölçüde yavaşlamıyor
      Kullanılan sürüm zig 0.13.0

  • İlginç bir araştırma çalışması; yalnızca kodun kendisi değil, gerekçelendirmesi de iyi ve dokümantasyonu da iyi yazılmış
    2018 tarihli heartbeat scheduling makalesi de okunmaya değer: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

  • Projenin sınırlamalar listesi: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

    • Bu proje harika ve yazarın zaman ayırıp bunu çalışır hale getirmesi ve HN topluluğuyla paylaşması büyük takdiri hak ediyor
      HN genel olarak aşırı eleştirel veya kötümser tepkileriyle de bilinen bir yer
      Yazarın kendi projesinin sınırlarını kabul etmesi de güzel; bu sayede alışıldık alaycılığın çoğunu baştan boşa çıkarıyor
      “Test eksikliği: Spice’ta zorlu eşzamanlılık kodu çok, ancak test kapsamı 0. Spice’ı önemli işlerde sorumlu biçimde kullanmak için bunun iyileştirilmesi gerekir” kısmında, önemli işlerin yürütme doğruluğunu test etmek ayrı bir konu olsa da, zorlu eşzamanlılık kodu uygulayan bir kütüphanede en azından regresyon testleri olması gerektiğini düşünüyorum
      Son kullanıcı olarak bugün çalışan bir özelliğin yarın ince ve kötü niyetli bir regresyonla bozulmayacağının garantisinin ne olduğunu merak ediyorum
      SQLite’ta saf C kaynak kodundan 590 kat fazla test kodu ve test betiği var https://www.sqlite.org/testing.html. Kararlılık ve taşınabilirliğin yanı sıra bu da SQLite’ın dünya çapında fiilî standart gömülü veritabanı haline gelmesinin çeşitli nedenlerinden biri
      Elma ile portakalı zorla karşılaştıran bir örnek ama genel fikir hâlâ geçerli. Regresyon testleri projenin kararlılığına ve güvenilirliğine katkı sağlar
      Benim çalıştığım yerde temel regresyon testleri mutlaka ertelenecekse, genellikle aynı epic içinde bir takip bileti açıp özellik/epic yayınlanmadan önce en azından yazılmasını sağlarız

  • Açıklamaya göre nanosaniye düzeyinde gecikme elde etmek için worker’larda busy waiting kullanılıyor
    On binlerce görevi olan büyük uygulamalarda busy waiting’in ne kadar gerçekçi olduğunu merak ediyorum. Görevler thread tabanlı değil de asenkron ise, executor thread pool boyutu N kadar bekleyen olacağı için mümkün olabilir. Her durumda bu yapı enerji tüketimini daha yüksek hale getirecektir
    Bununla bağlantılı olarak, iş üreticisinin busy waiting olmadan tüketiciyi daha hızlı uyandırmasının bir yolu olup olmadığını uzun zamandır merak ediyorum. Örneğin tüketiciyi üreticinin time slice’ı içinde çalıştırmak mümkün olabilir mi diye düşünüyorum
    Yine bununla ilgili olarak, kullanıcı alanında FUTEX_WAKE işlemi mümkün hale gelip tüketiciyi uyandırma maliyetini normalin yarısına, yani yalnızca tüketici tarafı maliyetine düşürebilir mi diye de merak ediyorum

  • Temiz ve iyi makaleler de linklenmiş
    Ancak karşılaştırma hedefinin OpenMP task olmasını isterdim. Rayon’un biraz yavaş olduğuna dair bir şöhreti olduğunu duymuştum

  • Kooperatif zamanlama, harika metrikler veren birçok örüntünün temelidir

    • Ancak bu, görevlerin birbirine yield ettiği anlamda kooperatif zamanlama değil
      Daha çok bazı işleri başka thread’lere devredebilmek için işbirliği yapma biçimi; üstelik bu her zaman olmuyor, yalnızca her heartbeat’te bir kez gerçekleşiyor. Zamanlama seyrek gerçekleştiği için amortize maliyeti düşük

  • bench altındaki README de incelenmeye değer: https://github.com/judofyr/spice/blob/main/bench/README.md