Bend - GPU'da Çalışan Gelişmiş Bir Dil (HVM2 kullanır)

 (github.com/HigherOrderCO)
1 puan yazan GN⁺ 2024-05-18 | 1 yorum | WhatsApp'ta paylaş
  • Bend, Python ve Haskell benzeri ifade gücü ile CUDA tarzı büyük ölçekli paralel yürütmeyi aynı anda hedefleyen yüksek seviyeli bir paralel programlama dilidir ve HVM2 çalışma zamanı üzerinde çalışır
  • Closure içeren yüksek mertebeden fonksiyonları, hızlı nesne tahsisini, sınırsız özyinelemeyi ve continuation desteğini sunarken; thread oluşturma, lock, mutex, atomic gibi açık paralelleştirme ifadeleri olmadan GPU gibi paralel donanımlarda çalışır
  • Mevcut tasarım hedefi, çekirdek sayısına göre ölçeklenen performanstır; 10.000'den fazla eşzamanlı thread desteği vardır, ancak mevcut sürümde tek çekirdek performansı düşük olabilir ve kod üretimi ile optimizasyon iyileştirmeleri sürmektedir
  • Çalıştırma biçimleri bend run-rs, bend run-c, bend run-cu olarak ayrılır; paralelleştirilebilir kodlar yalnızca çalıştırma komutu değiştirilerek C yorumlayıcısında veya CUDA yorumlayıcısında paralel çalıştırılabilir
  • Windows desteği henüz geliştirme aşamasındadır, bu yüzden WSL2 bir alternatiftir; GPU çalıştırma ise şu anda yalnızca NVIDIA GPU destekler

Bend'in hedeflediği programlama modeli

  • Bend, yüksek seviyeli dillerin kullanım hissini korurken büyük ölçekli paralel donanımlarda çalışan bir programlama dilidir
  • Python ve Haskell gibi ifade gücü yüksek dillerin özelliklerini sunar
    • hızlı nesne tahsisi
    • closure içeren yüksek mertebeden fonksiyonlar
    • sınırsız özyineleme
    • continuation
  • CUDA gibi GPU benzeri büyük ölçekli paralel donanımlarda çalışır ve çekirdek sayısına bağlı olarak neredeyse doğrusal hızlanmayı hedefler
  • Paralel yürütme için aşağıdakileri doğrudan yazmanız gerekmez
    • thread oluşturma
    • lock
    • mutex
    • atomic
  • Çalışma zamanında HVM2 kullanılır

Mevcut kısıtlar ve dikkat edilmesi gerekenler

  • Bend, performansı çekirdek sayısına göre ölçeklendirmeye odaklanır ve 10.000'den fazla eşzamanlı thread destekleyecek şekilde tasarlanmıştır
  • Mevcut sürümde tek çekirdek performansı düşük olabilir
  • Kod üretimi ve optimizasyon teknikleri geliştikçe performansın iyileşmesi beklenmektedir
  • Windows desteği hâlâ geliştirme aşamasındadır; alternatif olarak WSL2 kullanılabilir
  • GPU desteği şu anda yalnızca NVIDIA GPU'ları desteklemektedir

Kurulum ve çalıştırma biçimleri

  • Hem Linux hem de Mac için Rust kurulumu gerekir
  • Bend'in C sürümünde GCC kullanılır ve README, GCC 12.x veya altını önerir
  • CUDA runtime'ını kullanmak için Linux üzerinde CUDA Toolkit 12.x kurulumu gerekir
  • HVM2, cargo install hvm ile; Bend ise cargo install bend-lang ile kurulur
  • Bend programlarını çalıştırma komutları yürütücüye göre ayrılır
    • bend run <file.bend>: varsayılan olarak C yorumlayıcısını kullanır, paralel çalıştırma
    • bend run-rs <file.bend>: Rust yorumlayıcısını kullanır, sıralı çalıştırma
    • bend run-c <file.bend>: C yorumlayıcısını kullanır, paralel çalıştırma
    • bend run-cu <file.bend>: CUDA yorumlayıcısını kullanır, büyük ölçekli paralel çalıştırma
  • gen-c ve gen-cu kullanılarak bağımsız çalıştırılabilir C/CUDA dosyalarına derlenebilir
  • Kod üreticisi hâlâ erken aşamadadır ve GCC veya GHC gibi derleyiciler kadar olgun değildir
  • -s bayrağıyla reduction sayısı, çalışma süresi ve saniye başına interaction sayısı görülebilir

Sıralı toplama ve paralel toplama örneği

  • README'deki toplama örneği, start ile target arasındaki sayıları toplama kodunu iki yöntemle karşılaştırır
  • Sıralı sürüm, Sum(start + 1, target) sonucuna mevcut start değerini ekleyen bir yapıdır
    • Bir sonraki hesaplama, önceki toplama sonucuna bağlıdır
    • Mevcut hesaplama bitmeden sonraki adıma geçilemediği için paralelleştirilemez
    • Örnek, Sum(1, 1_000_000) çağrısını yapar ve Bend sayılarının azami değerinin aşılabileceğine dair bir not içerir
  • Paralelleştirilebilir sürüm, aralığı ikiye bölüp sol ve sağ toplamları özyinelemeli olarak hesaplar
    • (3 + 4) hesabı, (1 + 2) hesabına bağlı değildir
    • İki hesap aynı anda yapılabildiği için paralel yürütme mümkündür
  • Bend'de kod paralel çalışabilecek durumdaysa, yalnızca çalıştırma komutunu değiştirerek paralel yürütme yapılabilir

Bitonic Sorter performans örneği

  • README, hız örneği olarak bitonic sorter'ı değiştirilemez ağaç rotasyonu ile uygulanmış şekilde sunar
  • Bu algoritma, normalde GPU'da hızlı olması beklenen bir tür değildir; ancak böl ve yönet yaklaşımı sayesinde Bend bunu birçok thread üzerinde çalıştırır
  • Açıkça thread oluşturma veya lock yönetimi gerekmez
  • Benchmark sonuçları şöyledir
    • bend run-rs: CPU, Apple M3 Max, 12.15 saniye
    • bend run-c: CPU, Apple M3 Max, 0.96 saniye
    • bend run-cu: GPU, NVIDIA RTX 4090, 0.21 saniye
  • Diğer algoritmalar examples folder içinde görülebilir

Referanslar

  • Bend'in temel teknolojisi, HVM2 paper içinde incelenebilir
  • Resmî dokümantasyon hazırlanmaktadır; daha derin açıklamalar GUIDE.md içinde yer alır
  • Özellik listesi FEATURES.md içinde görülebilir
  • Bend, HigherOrderCO tarafından geliştirilmektedir

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-18
Hacker News yorumları

  • sum örneğini saf Pythona taşıyıp denediğimde pypy3 tek iş parçacığında 4,478 saniye, Python 3.12 ise 1 dakika 42,148 saniye sürdü.
    Buna karşılık Bend'in tek iş parçacıklı sürümü dizüstü bilgisayarımda 42 dakikadır çalışıyor; 6 GB bellek kullanmasına rağmen hâlâ bitmedi. Ortam: 12th Gen Intel(R) Core(TM) i7-1270P, Ubuntu 24.04.
    Bu kadar basit bir örnekte böyle yavaşsa karmaşık işlerde ne beklenebileceğini tahmin etmek zor; Mac/aarch64 dışındaki ortamlarda test ya da geliştirme yapılıp yapılmadığını merak ediyorum. Daha sonra -s argümanıyla tekrar çalıştırmayı düşünüyorum.

    • 42 dakika çalışması büyük olasılıkla bir bug. Henüz M3 Max dışındaki ortamlarda pek test etmedik; Apple dışı CPU'larda 2 kat yavaş olduğunu biliyoruz ve bunu iyileştirmeyi planlıyoruz.
      sum örneğinde Bend'in her sayısal işlem için 2 IC düğümü ayırması gibi büyük bir dezavantajı var; Python'da bu yok. HVM1'de olduğu gibi yakında bundan kaçınabilir hâle getirmeyi planlıyoruz, ancak HVM2'de henüz uygulanmış değil.
      Bend üzerindeki çalışmaların çoğu paralel değerlendiriciyi doğru yapmak için harcandı; GPU'da closure'ları ve sınırsız özyinelemeyi çalıştırmak çok zordu. Bu kısmı daha yeni bitirdiğimiz için mikro optimizasyona neredeyse hiç emek verilmedi ve HVM2'nin kod üretimi de hâlâ berbat durumda.
      Bitonic Sort örneği gibi iki tarafın da aynı miktarda allocation yaptığı durumlarla karşılaştırırsanız gerçek performansı daha adil görebilirsiniz. HVM1 tek çekirdekte GHC'den yaklaşık 3 kat yavaştı; HVM2'nin de çok geçmeden o seviyeye ulaşabileceğini düşünüyorum.
      “Şimdilik kötü ama iyileşecek” demenin heves kırıcı olabileceğini anlıyorum. Yine de temel oturdu; mikro optimizasyon en kolay kısım ve performansın burada ciddi biçimde artacağına inanıyorum.
    • Bu tartışmada bir çıkarım yok ama özyineleme, hesaplama performansından çok derleyicinin/yorumlayıcının çağrı yığınını oluşturup yok etme verimliliğini sınamaya daha yakın.
      Bu dil, hesaplama yoğun GPU uygulamalarını hedefliyor ve hâlâ erken aşamada. Özyineleme hedef uygulama değil; ilgili bir benchmark olarak görmek zor bence.
    • GPU ve CPU'da iş parçacığı denince kastedilen şey farklıdır; GPU'da SIMD lane'e daha yakındır.
      ISPC'nin CPU iş parçacığı başına 32 fonksiyon çağrısını aynı anda çalıştıracak şekilde derleyebilmesine benzer. Örneğin AVX512'de 16 bit veri kullanırsanız 32 çekirdek × çekirdek başına 2 SMT iş parçacığı × derleyicinin 32 yürütmesiyle aynı anda 2048 yürütme ilerleyebilir.
    • Python özyineleme konusunda çok zayıftır; fonksiyonel programlamaya uygun olmamasının nedenlerinden biri de budur, bu yüzden adil bir benchmark olmayabilir.
      Python'a özgü bir uygulama olsaydı döngüler ve değiştirilebilir durum kullanılırdı.
    • +0 neden gerekli, anlamadım. Hiçbir şey yapmayan bir işlem değil mi?

  • Bu başlıkta çok olumsuz tepki var, ama buraya kadar getirdiği için yazara kudos demek istiyorum.
    Benzer projeler olarak yalnızca Futhark'ı biliyorum; Haskell tarzı söz dizimi olduğu için C/C++/Python/JS/Java vb. dillere alışkın genel geliştiriciler için epey anlaşılması zor olabilir.
    En büyük eksik, Futhark'ın aksine yalnızca CUDA ya da çok çekirdeği hedeflemesi. Futhark OpenCL, CUDA, ISPC, HIP, tek çekirdek CPU ve çok çekirdek CPU'yu hedefleyebiliyor. Başkalarının işaret ettiği performans sorunlarının yeterince çözülebilir olduğunu düşünüyorum.

  • OP, son dönemde HN'ye gelen en havalı şeylerden bazılarını getiriyor; belli ki hâlâ erken sürüm olmasına rağmen sadece uzun eleştiriler alıyor gibi görünmesi üzücü.

    • HN, yeni ya da özgün şeyler paylaşmak isteyen bir topluluğa daha yakın. Birisi övmek isterse, çoğu zaman bir “harika” yorumu daha yazmak yerine mevcut yoruma upvote verir.
      Buna karşılık eleştiride isabetli olmanın yolları sınırlı, yanılmanın yolları ise çoktur; bu yüzden sonsuz çeşitlilikte olabilir. Bu nedenle olumlu yorumlar birkaç tane kalır, çoğu ise eleştiri ya da “şunu da yapsaydınız” gibi görünür. Belirli bir kişinin hatasından ziyade günümüz mühendis kültürü biraz bu yönde.
    • Benim projem olsaydı, insanların eleştirmesini epey takdir ederdim. Büyüme böyle olur.
      İnsanlar acı gerçekleri yalnızca alkışların arkasına saklasa dünya çökerdi.
    • 905 upvote aldığına göre yeterince olumlu tepki de almış sayılır.
      Eleştiri de fikre ve yaklaşıma ilgi duyup katılım gösterildiği anlamına gelir; bu yüzden çoğu zaman olumlu bir sinyaldir.
    • Yeni ve iddialı projeleri eleştirmemek iyi bir toplumsal normdur. Böyle girişimler teşvik edilmeli, hevesleri kırılmamalı.
      Ancak yanlış anlaşılmaya yol açan, dayanağı zayıf ya da yanlış iddialarda bulunan projeleri eleştirmek de iyi bir toplumsal normdur. Çünkü bu tür iddiaları azaltır.
    • En havalı şeyler genellikle anlaşılması en zor olanlardır.
      Anlaşılması zor olan şeyler çoğu zaman tehditkâr hissettirir; eleştiri de tehdide verilen yaygın bir tepki ve en az anlayışla verilebilecek cevap biçimidir.

  • Ana sayfa gerçekten çok iyi hazırlanmış. Ne yaptığı hemen açıkça anlaşılıyor
    “Combinator”larla uğraşan kişiler genelde bolca ürkütücü uzmanlık jargonu kullanmak ister, ama OP aracın arkasındaki basit fikri gerçekten gösteriyor. Son ayrıntısına kadar gösterip asıl meselenin ne olduğunu söylemeyen akademik yaklaşımın tersi olduğu için iyi. Bu tür yaklaşımlar daha çok olmalı

  • Teorik olarak harika ve değer önerisini de anlıyorum, ama açıkçası bunun pratikte ilgili bir araç haline geleceğini sanmıyorum
    İlk izlenimim ve makaleyi hızlıca gözden geçirdikten sonraki notlarım bunlar. Bunun çok erken aşamada bir yazılım olduğunun farkındayım
    Bend çok sınırlı bir DSL gibi görünüyor. FFI yok, ham buffer’larla etkileşmenin yolu yok ve 24 bit kayan nokta biçimi de garip
    IC’nin ana akım olmamasının bir nedeni var. Performansın bundan sonra da berbat olma ihtimali yüksek ve graph traversal donanımla iyi örtüşmüyor
    Optimal reduction önermesi geçerli, ama sonuçta kernel’ları paralelleştirilebilir şekilde yazmak gerekiyor. Yani veri bağımlılığı olmamalı ve recursion kullanımı da hesaba katılmalı
    Bend/HVM kodu ile eşdeğer OMP/CUDA programlarını doğrudan karşılaştıran ciddi bir örnek yok. Uygulama karmaşıklığının ne kadar azaldığını ve performansın ne düzeyde olduğunu değerlendirmek zor
    Gerçek dünyadaki yüksek performanslı paralel hesaplamada ağaç yapıları neredeyse yoktur; diziler kraldır. Bunun nedeni belleğin donanım düzeyinde çalışma biçiminin fiziksel özellikleridir. Değiştirilebilir, bitişik bellek buffer’larında en iyi çalışan şey döngülerdir. HVM bunu uygularsa izlerim
    Şu anda dış veriden neredeyse tamamen yalıtılmış, çok yavaş ve donanımın üstüne devasa bir soyutlama koyan yarı pişmiş bir dil gibi görünüyor. Çok kademeli cache, tensor core’lar, SIMD, atomik işlemler gibi özelliklerden de yararlanamıyor
    Sert geldiyse kusura bakmayın, ama teknik uygulamanın ve teorik arka planın hâlâ çok ilginç olduğunu düşünüyorum. Yine de gerçek dünyadaki faydasına henüz ikna olmuş değilim

    • Geri bildirim için teşekkürler. Birkaç şeyi düzelteyim: çok kademeli cache kullanıyoruz ve doğru kullanıldığında 5 kat daha yüksek performans sağlayabiliyor
      FFI zaten uygulanmış durumda ama henüz yayımlamadık. Çünkü grafik render etme ile birlikte çıkarmak istiyoruz ve bunun oldukça havalı olacağını düşünüyorum
      Haskell/GHC de graph ve tree kullanıyor, ama kimse pratik olmadığını söylemez. Dizilerin kral olduğu doğru; ancak compiler’lar, type checker’lar, solver’lar gibi dizilere pek uymayan modern algoritmaların önemli bir kısmı Haskell ile uygulanıyor
      IC’nin hızlı olmamasının ana nedeni, onun üzerinde düşük seviyeli optimizasyon işini gerçekten iyi yapan kimsenin olmamasıydı. Mevcut implementasyonların hepsi fena halde verimsizdi; benim çalışmamda da şimdiye kadar zaman, GPU’da doğru çalışmasını sağlamaya gitti
      Henüz döngülerin bile olmaması gibi, çözüm sadece döngü eklemek. Burada özsel bir sınır olduğunu düşünüyorsanız şaşıracaksınız
      HVM2 sonunda ölçeklenebilir ve doğru bir algoritma haline geldi; şimdi gerçek düşük seviyeli performansı optimize etme zamanı
      1. maddeye ilişkin olarak, ağaçlar klasik bilgisayar bilimi tarzı implementasyonlardan farklı olsa da oldukça yaygın kullanılır
        Fast Multipole veya Barnes-Hut algoritmalarında, O(n²) ikili işlemleri sırasıyla O(n) ve O(n log n)’e düşürmek için Morton sırası ya da H-index sırası kullanılır. Barnes-Hut astrofizikte daha yaygındır; Fast Multipole ise kimyasal moleküler dinamikte daha sık görülür

  • 10 yıl önce CMU’nun paralel algoritmalar dersi olan 15-210’u almıştım. Moore yasası sınıra dayandıkça paralelliğin bilişimin geleceği olacağını anlatıyordu; bu bana ikna edici gelmişti ve denemek istemiştim
    Ama genel amaçlı paralel programlama seçenekleri pek fazla değildi. Derste kullandığımız SML bile paralel değildi; sonunda extension ve CUDA kullanan bir bölüm vardı ama hatırladığım kadarıyla sınırlıydı
    Sonrasında Rust sayesinde multithreading’i biraz denedim, Shadertoy sayesinde de shader’larla yaratıcı işler yapabildim. Ama GPU üzerinde genel amaçlı paralel bir dil fikri, bizzat kurcalamak için beni çok heyecanlandırıyor

    • Bugünlerde 210 gerçekten paralel. MaPLe (https://github.com/MPLLang/mpl) kullanarak 210 tarzı kod çalıştırabilir ve C/C++’a kıyasla rekabetçi performans da elde edebilirsiniz
      210 hoşunuza gittiyse https://futhark-lang.org/ da hoşunuza gidebilir. ML ailesinden bir dil, GPU’ya derleniyor ve performansı da iyi
    • Makinelerin çok çekirdekli hale gelmesi, Elixir öğrenmeye karar vermemin nedenlerinden biriydi

  • Fikir çok havalı, ama bir şeyi kaçırmıyorsam çok yavaş görünüyor
    C++ ile 0’dan 2³⁰’a kadar toplayan basit bir döngü yazdım; optimizasyon olmadan tek thread’de dizüstü bilgisayarımda 1,7 saniye sürdü, bu da RTX 4090’daki Bend performansına benzer. -O3 verince döngü vektörize edilip 80 ms’nin altında çalışıyor

    • Bend’de henüz tail call optimization yok. 1 milyar uzunlukta bir stack ayırıyor; C ise sadece döngü çalıştırıyor
      Gerçekten allocation yapan bir C programıyla karşılaştırıldığında Bend’in birkaç thread ile bile daha hızlı olma ihtimali yüksek
      Bend’in code generation’ı henüz berbat, ama bunlar kolay kazanımlar. İşin çoğu, çok zor olan paralel evaluator’ı doğru hale getirmeye gitti
      “Bana güvenin” gibi duyulduğunu biliyorum, ama procedure compilation, döngü üretimi vb. başladığında tek thread performansı çok daha iyi olacak. Sadece henüz yapılmadı
      Aslında bunu yayımlamadan önce biraz daha beklemeli miydim diye de düşünüyorum
    • Döngünün gerçekten vektörize edilip edilmediğini, yoksa compiler’ın tamamını optimize edip atıp atmadığını objdump ile kontrol etmek iyi olur
      Söz konusu döngü signed integer overflow oluşturuyor ve C++’ta bu undefined behavior’dır. Compiler yasal olarak herhangi bir sonuç üretebilir
      Bunu önlemek için sum’ı unsigned olarak tanımlamak gerekir. Unsigned integer overflow iyi tanımlıdır; optimizasyon yine gerçekleşir ama en azından doğruluk garanti edilir
    • clang’de -O3 ile derleyince döngü tamamen kaldırılıyor: https://godbolt.org/z/M1rMY6qM9
      Muhtemelen adil bir karşılaştırma değil
    • Asıl nokta Bend’in C++’tan çok daha yüksek seviyeli olması gibi görünüyor
      Tabii ben de meseleyi kaçırıyor olabilirim

  • Yazarı tebrik etmek istiyorum. Gerçekten harika bir iş
    Doğru otomatik paralelleştirme yapmak hiç de kolay değil ve bununla fazlasıyla gurur duyabilirsiniz. Projenin bundan sonra nasıl gelişeceğini merakla bekliyorum

  • Neden bu kadar çok olumsuz tepki olduğunu anlamıyorum. Öfkeli bir kalabalık, README’deki açıkları kurcalayıp yazının bağlamını ve niyetini değiştirmeye çalışan botlar gibi görünüyordu.
    Düzgün okumaya 2 dakika bile ayırmadan saatlerce tartışmak cahilce ve acımasızca. OP buraya kadar tek kişilik bir projeyle gelmiş; umarım devam eder.

  • HVM2’nin etkileşim ağlarını örneğin SPIR-V’ye derleyip derlemediğini, yoksa orijinal HVM gibi GPU’da çalışan bir yorumlayıcı mı olduğunu merak etmiştim.
    Daha önce programı mümkün olduğunca çok indirgedikten sonra girdiyi indirgemeden bırakan bir yöntemle etkileşim ağlarını C’ye derleyip bunu tüm program optimizasyonu gibi ele almayı denemiştim. Shader dillerini hedeflemek de çok zor olmaz gibi görünmüştü.
    Depoya bakınca HVM2 ağlarını belirtmek için düşük seviyeli bir IR dili ve C/CUDA’ya giden bir derleyici sunduğu yazıyor: https://github.com/HigherOrderCO/HVM
    Ama tekrar bakınca HVM2 CUDA runtime’ı, bellekteki grafı dolaşıp indirgemeleri uygulayan bir yorumlayıcı gibi görünüyor: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
    Benim kastettiğim, etkileşim ağını dolaşıp lambda calculus ifadelerine yakın terimleri geri oluşturmak ve küçük parçalar halinde C’ye indirerek runtime overhead’ini en aza indiren bir yöntemdi.
    Dürüst olmak gerekirse motivasyonum, Bend ile ML iş yükleri gibi yerlerde elle yazılmış GPU kernel’larını yenmenin zor olması. Teorik olarak HVM, hesaplama kernel’larını birbirine bağlayan ve yürütme sırasını paralelleştiren bir yapıştırıcı görevi görebilir; ama bunun için iyi bir FFI gerekir.
    Etkileşim ağlarını FFI sınırından geçirip çevirmek zordur; fakat FFI hesaplama kernel düğümlerini etkileşim ağı içinde tutup ağı C’ye derlerseniz, çeviri overhead’i olmadan makul bir FFI’yi geri kazanabilirsiniz.
    Diğer seçenek HVM’i donanımda uygulamak; boşta duran bir FPGA üzerinde biraz kurcalıyorum.

    • GPU’da çalışan bir yorumlayıcı olduğu gibi, yerel C ve CUDA’ya giden bir derleyici de.
      SPIR-V’yi doğrudan hedeflemiyor ama hedefler arasında.
      C derleyicisi beklenen hız artışını, yani 3–4 katı ve yakında daha fazlasını sağlıyor; ancak CUDA runtime’ı, derlenmemiş sürüme kıyasla büyük bir hız artışı elde edemedi.
      Bunun nedeninin warp dallanması olduğunu düşünüyoruz. Derlenmemiş prosedürlerde tüm fonksiyon çağrılarını tek bir “genel amaçlı” yorumlayıcı tarzı fonksiyon genişleticisinde birleştirebiliyor ve warp thread’leri dallanma olmadan indirgeme yapabiliyor. İleride bu kısmı daha derinlemesine araştıracağız.