Bend - Bahasa Tingkat Tinggi yang Berjalan di GPU (Menggunakan HVM2)

 (github.com/HigherOrderCO)
1 poin oleh GN⁺ 2024-05-18 | 1 komentar | Bagikan ke WhatsApp
  • Bend adalah bahasa pemrograman paralel tingkat tinggi yang menargetkan ekspresivitas seperti Python·Haskell sekaligus eksekusi paralel masif ala CUDA, dan berjalan di atas runtime HVM2
  • Mendukung higher-order function dengan closure, alokasi objek cepat, rekursi tanpa batas, dan continuation, sambil berjalan di hardware paralel seperti GPU tanpa notasi paralelisasi eksplisit seperti pembuatan thread, lock, mutex, atau atomic
  • Sasaran desain saat ini adalah performa yang menskalakan sesuai jumlah core, dan mendukung lebih dari 10.000 thread serentak, tetapi versi saat ini mungkin memiliki performa single-core yang rendah, sementara peningkatan code generation dan optimisasi masih berlangsung
  • Cara eksekusi terbagi menjadi bend run-rs, bend run-c, dan bend run-cu; kode yang dapat diparalelkan bisa dijalankan secara paralel di interpreter C atau interpreter CUDA hanya dengan mengganti perintah eksekusi
  • Dukungan Windows masih dalam pengerjaan sehingga WSL2 menjadi alternatif, dan eksekusi GPU saat ini hanya mendukung GPU NVIDIA

Model pemrograman yang dituju Bend

  • Bend adalah bahasa pemrograman yang berjalan di hardware paralel berskala besar sambil tetap mempertahankan pengalaman penggunaan bahasa tingkat tinggi
  • Menyediakan fitur bahasa ekspresif seperti Python dan Haskell
    • Alokasi objek cepat
    • Higher-order function dengan closure
    • Rekursi tanpa batas
    • Continuation
  • Berjalan di hardware paralel berskala besar seperti GPU layaknya CUDA, dengan target akselerasi yang hampir linear berdasarkan jumlah core
  • Untuk eksekusi paralel, tidak perlu menulis hal-hal berikut secara langsung
    • Pembuatan thread
    • Lock
    • Mutex
    • Atomic
  • Runtime menggunakan HVM2

Batasan dan hal yang perlu diperhatikan saat ini

  • Bend berfokus pada penskalaan performa sesuai jumlah core, dan dirancang untuk mendukung lebih dari 10.000 thread serentak
  • Versi saat ini mungkin memiliki performa single-core yang rendah
  • Performa diperkirakan akan meningkat seiring berkembangnya code generation dan teknik optimisasi
  • Dukungan Windows masih dalam pengerjaan, dan sebagai alternatif dapat menggunakan WSL2
  • Dukungan GPU saat ini hanya mendukung GPU NVIDIA

Instalasi dan cara menjalankan

  • Linux dan Mac sama-sama memerlukan Rust terpasang
  • Bend versi C menggunakan GCC, dan README merekomendasikan GCC 12.x atau lebih rendah
  • Untuk menggunakan runtime CUDA, perlu memasang CUDA Toolkit 12.x untuk Linux
  • HVM2 dipasang dengan cargo install hvm, dan Bend dipasang dengan cargo install bend-lang
  • Perintah untuk menjalankan program Bend dibagi berdasarkan runner
    • bend run <file.bend>: menggunakan interpreter C secara default, eksekusi paralel
    • bend run-rs <file.bend>: menggunakan interpreter Rust, eksekusi sekuensial
    • bend run-c <file.bend>: menggunakan interpreter C, eksekusi paralel
    • bend run-cu <file.bend>: menggunakan interpreter CUDA, eksekusi paralel masif
  • Dengan gen-c dan gen-cu, program dapat dikompilasi menjadi file C/CUDA mandiri yang dapat dieksekusi
  • Code generator masih tahap awal dan belum sematang compiler seperti GCC atau GHC
  • Dengan flag -s, jumlah reduction, waktu eksekusi, dan jumlah interaction per detik dapat dilihat

Contoh penjumlahan sekuensial dan penjumlahan paralel

  • Contoh penjumlahan di README membandingkan dua cara kode yang menjumlahkan angka dari start hingga target
  • Versi sekuensial memiliki struktur yang menambahkan start saat ini ke hasil Sum(start + 1, target)
    • Perhitungan berikutnya bergantung pada hasil penjumlahan sebelumnya
    • Sebelum perhitungan saat ini selesai, proses tidak bisa lanjut ke tahap berikutnya sehingga tidak dapat diparalelkan
    • Contohnya memanggil Sum(1, 1_000_000), dan mencakup komentar bahwa nilai tersebut bisa melampaui nilai maksimum angka Bend
  • Versi yang dapat diparalelkan membagi rentang menjadi dua, lalu menghitung jumlah sisi kiri dan kanan secara rekursif
    • Perhitungan (3 + 4) tidak bergantung pada perhitungan (1 + 2)
    • Kedua perhitungan dapat terjadi bersamaan sehingga eksekusi paralel dimungkinkan
  • Di Bend, jika kode dapat berjalan secara paralel, eksekusi paralel bisa dilakukan hanya dengan mengganti perintah eksekusi

Contoh performa Bitonic Sorter

  • README menyajikan bitonic sorter yang diimplementasikan dengan rotasi pohon immutable sebagai contoh kecepatan
  • Algoritme ini termasuk tipe yang tidak mudah diharapkan cepat di GPU, tetapi Bend menjalankannya di banyak thread dengan pendekatan divide-and-conquer
  • Tidak perlu pembuatan thread atau pengelolaan lock secara eksplisit
  • Hasil benchmark adalah sebagai berikut
    • bend run-rs: CPU, Apple M3 Max, 12,15 detik
    • bend run-c: CPU, Apple M3 Max, 0,96 detik
    • bend run-cu: GPU, NVIDIA RTX 4090, 0,21 detik
  • Algoritme lain dapat dilihat di folder examples

Referensi

  • Teknologi dasar Bend dapat dilihat di paper HVM2
  • Dokumentasi resmi masih dalam pengerjaan, dan penjelasan lebih mendalam ada di GUIDE.md
  • Daftar fitur dapat dilihat di FEATURES.md
  • Bend dikembangkan oleh HigherOrderCO

Bacaan terkait

1 komentar

 
GN⁺ 2024-05-18
Pendapat Hacker News

  • Saya mencoba memindahkan contoh sum ke Python murni; dengan pypy3 butuh 4,478 detik di satu thread, sedangkan Python 3.12 butuh 1 menit 42,148 detik
    Sebaliknya, versi Bend satu thread masih berjalan di laptop saya setelah 42 menit dan belum selesai meski memakai memori 6 GB. Lingkungannya 12th Gen Intel(R) Core(TM) i7-1270P, Ubuntu 24.04
    Kalau selambat ini pada contoh yang sangat sederhana, sulit berharap banyak untuk tugas yang kompleks, dan saya penasaran apakah sudah diuji atau dikembangkan di lingkungan selain Mac/aarch64. Nanti saya berencana menjalankannya lagi dengan argumen -s

    • Berjalan selama 42 menit kemungkinan besar adalah bug. Kami belum banyak mengujinya di lingkungan selain M3 Max, dan kami tahu bahwa pada CPU non-Apple performanya 2x lebih lambat, jadi itu akan kami perbaiki
      Pada contoh sum, Bend punya kerugian besar karena mengalokasikan 2 node IC untuk setiap operasi angka, sementara Python tidak. Seperti HVM1, ini akan segera bisa dihindari, tetapi belum diimplementasikan di HVM2
      Sebagian besar pekerjaan Bend dihabiskan untuk membuat evaluator paralel bekerja dengan benar, dan menjalankan closure serta rekursi tanpa batas di GPU itu sangat sulit. Karena bagian itu baru saja selesai, hampir belum ada upaya untuk optimasi mikro, dan pembuatan kode HVM2 juga masih buruk
      Jika dibandingkan dengan kasus seperti contoh Bitonic Sort, di mana kedua sisi melakukan jumlah alokasi yang sama, performa sebenarnya bisa dilihat dengan lebih adil. HVM1 hanya sekitar 3x lebih lambat dari GHC pada satu core, dan saya rasa HVM2 juga bisa segera mencapai level itu
      Saya paham bahwa ucapan “masih buruk, tapi akan membaik” bisa terasa mengecewakan. Namun, karena fondasinya sudah ada, optimasi mikro adalah bagian yang paling mudah, dan saya yakin performanya akan naik besar dari sini
    • Saya tidak punya kepentingan dalam perdebatan ini, tetapi rekursi lebih dekat ke pengujian efisiensi compiler/interpreter dalam membuat dan menghapus call stack daripada performa komputasi
      Bahasa ini menargetkan aplikasi GPU yang intensif komputasi dan masih berada pada tahap awal. Rekursi bukan aplikasi targetnya, dan menurut saya sulit dianggap sebagai benchmark yang relevan
    • Thread di GPU dan CPU punya makna berbeda; di GPU, itu lebih dekat ke SIMD lane
      Mirip dengan bagaimana ISPC dapat mengompilasi agar 32 pemanggilan fungsi dijalankan bersamaan untuk setiap thread CPU. Misalnya, jika memakai data 16-bit di AVX512, 32 core × 2 thread SMT per core × 32 eksekusi compiler dapat menghasilkan 2048 eksekusi berjalan bersamaan
    • Python sangat lemah dalam rekursi, yang merupakan salah satu alasan mengapa ia tidak cocok untuk pemrograman fungsional, jadi ini mungkin bukan benchmark yang adil
      Implementasi yang Pythonic kemungkinan akan memakai loop dan state yang dapat diubah
    • Saya tidak mengerti mengapa +0 diperlukan. Bukankah itu operasi yang tidak melakukan apa-apa?

  • Ada banyak reaksi negatif di thread ini, tetapi saya ingin memberi kudos kepada penulisnya hanya karena sudah membangun sampai sejauh ini
    Untuk proyek serupa, saya hanya tahu Futhark, tetapi sintaksnya bergaya Haskell, sehingga bisa cukup sulit dipahami bagi developer umum yang terbiasa dengan C/C++/Python/JS/Java dan sebagainya
    Kekurangan terbesarnya adalah, tidak seperti Futhark, targetnya hanya CUDA atau multicore. Futhark dapat menargetkan OpenCL, CUDA, ISPC, HIP, CPU single-core, dan CPU multicore. Menurut saya masalah performa yang ditunjukkan orang lain sangat mungkin diselesaikan

  • OP sering membawa hal-hal paling keren yang baru-baru ini muncul di HN, jadi sayang rasanya ia hanya mendapat kritik panjang meski jelas ini masih versi awal

    • HN lebih seperti komunitas yang ingin memposting hal-hal baru atau orisinal. Jika seseorang ingin memuji, mereka sering menekan upvote pada komentar yang sudah ada daripada menulis komentar “keren” lagi
      Sebaliknya, cara untuk tepat dalam kritik itu terbatas, sedangkan cara untuk keliru banyak, sehingga kritik bisa bervariasi tanpa henti. Akibatnya komentar positif hanya beberapa, sementara sebagian besar terlihat seperti kritik atau “seharusnya juga melakukan ini”. Ini bukan kesalahan individu tertentu, melainkan lebih merupakan budaya teknolog masa kini
    • Kalau itu proyek saya, saya akan cukup berterima kasih jika orang-orang mengkritiknya. Dengan begitu proyek bisa tumbuh
      Jika orang hanya menyembunyikan kebenaran pahit di balik tepuk tangan, dunia akan runtuh
    • Mendapat 905 upvote berarti respons positifnya juga sudah cukup banyak
      Kritik juga berarti orang tertarik dan terlibat dengan ide serta pendekatannya, jadi sering kali itu merupakan sinyal positif
    • Tidak mengkritik proyek baru dan ambisius adalah norma sosial yang baik. Upaya seperti itu perlu didorong dan tidak boleh dipatahkan
      Namun, mengkritik proyek yang membuat klaim yang menyesatkan, kurang berdasar, atau palsu juga merupakan norma sosial yang baik. Karena itu membuat klaim semacam itu berkurang
    • Hal-hal paling keren biasanya juga yang paling sulit dipahami
      Sesuatu yang sulit dipahami sering terasa mengancam, dan kritik adalah reaksi umum terhadap ancaman sekaligus bentuk respons yang dapat dilakukan dengan pemahaman paling sedikit

  • Situs webnya benar-benar dibuat dengan sangat baik. Langsung jelas terlihat apa yang dilakukannya
    Orang-orang yang menangani “combinator” biasanya ingin memakai banyak istilah teknis yang menakutkan, tetapi OP benar-benar menunjukkan ide sederhana di balik alat ini. Saya suka karena ini kebalikan dari pendekatan akademis yang memperlihatkan sampai detail terakhir tetapi tidak mengatakan apa yang sebenarnya terjadi. Semestinya lebih banyak yang memakai cara seperti ini

  • Secara teori keren dan saya memahami proposisi nilainya, tetapi jujur saja saya tidak merasa ini akan menjadi alat yang relevan di dunia nyata
    Ini catatan setelah kesan pertama dan membaca sekilas makalahnya. Saya tahu ini perangkat lunak yang masih sangat awal
    Bend terlihat seperti DSL yang sangat terbatas. Tidak ada FFI, tidak ada cara berinteraksi dengan buffer mentah, dan format floating-point 24-bit juga aneh
    Ada alasan mengapa IC tidak menjadi arus utama. Performa kemungkinan besar akan tetap buruk, dan penelusuran graf tidak cocok dengan hardware
    Premis optimal reduction memang valid, tetapi pada akhirnya kernel harus ditulis dengan cara yang bisa diparalelkan. Artinya tidak boleh ada dependensi data, dan penggunaan rekursi juga perlu dipertimbangkan
    Tidak ada contoh serius yang membandingkan langsung kode Bend/HVM dengan program OMP/CUDA yang setara. Sulit menilai seberapa besar kompleksitas implementasi berkurang dan seperti apa performanya
    Dalam komputasi paralel berkinerja tinggi di dunia nyata, struktur berbentuk pohon hampir tidak ada dan array adalah raja. Ini karena sifat fisik memori yang bekerja di level hardware. Yang paling cocok untuk buffer memori kontigu yang dapat diubah adalah loop. Kalau HVM mengimplementasikan ini, saya akan mengamatinya
    Saat ini tampak hampir sepenuhnya terisolasi dari data eksternal, sangat lambat, dan seperti bahasa setengah matang yang menaruh abstraksi raksasa di atas hardware. Ia juga tidak bisa memanfaatkan fitur seperti cache bertingkat, tensor core, SIMD, dan operasi atomik
    Maaf kalau terdengar kasar, tetapi saya tetap menganggap implementasi teknis dan latar teorinya sangat menarik. Hanya saja saya belum yakin dengan kegunaannya di dunia nyata

    • Terima kasih atas masukannya. Untuk meluruskan beberapa hal, kami menggunakan cache bertingkat, dan jika digunakan dengan benar bisa menghasilkan performa 5x lebih tinggi
      FFI sudah diimplementasikan, tetapi belum kami rilis. Alasannya karena kami ingin merilisnya bersama rendering grafis, dan saya rasa hasilnya akan cukup keren
      Haskell/GHC juga memakai graf dan pohon, tetapi tidak ada yang akan mengatakan itu tidak praktis. Memang benar array adalah raja, tetapi cukup banyak algoritma modern yang tidak cocok dengan array—seperti compiler, type checker, solver, dan sebagainya—diimplementasikan dengan Haskell
      Alasan utama IC tidak cepat adalah karena belum ada yang benar-benar melakukan optimasi level rendah di atasnya. Semua implementasi lama sangat tidak efisien, dan pekerjaan saya sejauh ini pun menghabiskan waktu untuk membuatnya berjalan dengan benar di GPU
      Seperti halnya fakta bahwa loop pun belum ada, solusinya ya tinggal menambahkan loop. Jika Anda mengira ada batasan mendasar di sana, Anda mungkin akan terkejut
      HVM2 akhirnya menjadi algoritma yang benar dan dapat diskalakan, dan sekarang saatnya mengoptimalkan performa level rendah yang sebenarnya
    • Untuk poin 5, pohon memang berbeda dari implementasi ilmu komputer yang umum, tetapi penggunaannya cukup luas
      Dalam algoritma Fast Multipole atau Barnes-Hut, urutan Morton atau urutan H-index digunakan untuk menurunkan operasi berpasangan O(n²) masing-masing menjadi O(n), O(n log n). Barnes-Hut lebih umum di astrofisika, sedangkan Fast Multipole lebih sering terlihat di dinamika molekuler kimia

  • Saya mengikuti 15-210, mata kuliah algoritma paralel di CMU, 10 tahun lalu. Mereka menjelaskan bahwa ketika Hukum Moore mencapai batasnya, paralelisme akan menjadi masa depan komputasi, dan saya cukup diyakinkan oleh argumen itu sehingga ingin bereksperimen
    Namun tidak banyak pilihan pemrograman paralel serbaguna. Bahkan SML yang dipakai di kelas pun tidak paralel, dan di bagian akhir ada seksi yang memakai ekstensi dan CUDA, tetapi seingat saya itu terbatas
    Setelah itu, Rust membuat saya bisa sedikit bereksperimen dengan multithreading, dan Shadertoy memungkinkan saya melakukan pekerjaan kreatif dengan shader. Tetapi bahasa paralel serbaguna di atas GPU—saya sangat antusias untuk mencobanya langsung

    • Sekarang 210 benar-benar paralel. Dengan MaPLe(https://github.com/MPLLang/mpl), Anda bisa menjalankan kode gaya 210 dan mendapatkan performa yang kompetitif dibanding C/C++
      Jika Anda menyukai 210, Anda mungkin juga akan menyukai https://futhark-lang.org/. Itu bahasa keluarga ML, dikompilasi ke GPU, dan performanya juga bagus
    • Arah mesin menuju multicore adalah salah satu alasan saya memutuskan mempelajari Elixir

  • Idenya sangat keren, tetapi kalau bukan saya yang melewatkan sesuatu, ini terlihat sangat lambat
    Saya menulis loop sederhana di C++ yang menjumlahkan dari 0 sampai 2³⁰, dan tanpa optimasi, single-thread di laptop saya butuh 1,7 detik, kira-kira mirip dengan performa Bend di RTX 4090. Dengan -O3, loop itu divektorisasi dan berjalan di bawah 80 ms

    • Bend belum punya tail call optimization. Ia mengalokasikan stack sepanjang 1 miliar, sedangkan C hanya menjalankan loop
      Jika dibandingkan dengan program C yang benar-benar melakukan alokasi, Bend mungkin lebih cepat bahkan hanya dengan beberapa thread
      Code generation Bend memang masih buruk, tetapi ini termasuk low-hanging fruit. Sebagian besar pekerjaan sejauh ini dihabiskan untuk membuat evaluator paralel yang sangat sulit itu benar
      Saya tahu ini terdengar seperti “percaya saja”, tetapi begitu kami mulai melakukan kompilasi prosedural, pembuatan loop, dan sebagainya, performa single-thread akan jauh membaik. Hanya saja belum kami lakukan
      Saya juga sempat berpikir mungkin seharusnya menunggu sedikit lebih lama sebelum benar-benar mempublikasikannya
    • Sebaiknya cek dengan objdump apakah loop itu benar-benar divektorisasi, atau justru compiler mengoptimalkannya habis-habisan
      Loop tersebut menyebabkan signed integer overflow, dan di C++ itu adalah undefined behavior. Compiler secara sah boleh menghasilkan hasil apa pun
      Untuk menghindarinya, sum harus dideklarasikan sebagai unsigned. Overflow integer unsigned terdefinisi dengan baik, dan optimasi tetap terjadi, tetapi setidaknya kebenarannya terjamin
    • Jika dikompilasi dengan -O3 di clang, loop-nya dihapus sepenuhnya: https://godbolt.org/z/M1rMY6qM9
      Mungkin itu bukan perbandingan yang adil
    • Sepertinya poin utamanya adalah Bend jauh lebih high-level daripada C++
      Tentu saja, saya juga mungkin melewatkan maksudnya

  • Saya ingin mengucapkan selamat kepada penulisnya. Ini benar-benar pekerjaan yang keren
    Membuat automatic parallelization yang benar sama sekali bukan hal mudah, dan Anda pantas merasa bangga. Saya menantikan bagaimana proyek ini akan berkembang

  • Saya tidak paham kenapa reaksinya begitu banyak yang negatif. Rasanya seperti massa yang marah, seperti bot yang mengorek celah di README sambil mencoba mengubah konteks dan maksud tulisannya
    Berdebat berjam-jam tanpa meluangkan bahkan 2 menit untuk membaca dengan benar itu bodoh dan kejam. OP sudah sampai sejauh ini sebagai proyek satu orang, jadi saya harap ia terus maju

  • Saya penasaran apakah HVM2 mengompilasi interaction net, misalnya ke SPIR-V, atau seperti HVM asli, ia adalah interpreter yang berjalan di GPU
    Dulu saya pernah mencoba mengompilasi interaction net ke C dengan cara mereduksi program sebanyak mungkin lalu tidak mereduksi input, memperlakukannya seperti optimisasi seluruh program. Menargetkan bahasa shader sepertinya juga tidak akan terlalu sulit
    Dari repositorinya, tertulis bahwa mereka menyediakan bahasa IR level rendah untuk mendeskripsikan net HVM2 dan compiler ke C/CUDA: https://github.com/HigherOrderCO/HVM
    Namun setelah saya lihat lagi, runtime CUDA HVM2 tampak seperti interpreter yang menelusuri graf di memori dan menerapkan reduksi: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
    Yang saya maksud adalah pendekatan yang menelusuri interaction net untuk memulihkan term yang mendekati ekspresi kalkulus lambda, lalu menurunkannya menjadi potongan-potongan kecil C guna meminimalkan overhead runtime
    Motivasi jujurnya adalah bahwa dengan Bend, sulit untuk mengalahkan kernel GPU yang ditulis tangan pada beban kerja seperti ML. Secara teori HVM bisa berperan sebagai perekat yang menyambungkan kernel-kernel komputasi dan memparalelkan urutan eksekusinya, tetapi untuk itu dibutuhkan FFI yang baik
    Interaction net sulit diterjemahkan melintasi batas FFI, tetapi jika node kernel komputasi FFI ditempatkan di dalam jaringan interaksi dan net-nya dikompilasi ke C, FFI yang masuk akal dapat dipulihkan tanpa overhead penerjemahan
    Pilihan lain adalah mengimplementasikan HVM di hardware, dan saya sedang sedikit mengutak-atiknya di FPGA yang menganggur

    • Ia adalah interpreter yang berjalan di GPU, sekaligus compiler ke C dan CUDA native
      Belum menargetkan SPIR-V secara langsung, tetapi itu menjadi tujuan
      Compiler C menghasilkan peningkatan kecepatan seperti yang diharapkan, yaitu 3–4x dan segera lebih dari itu, tetapi runtime CUDA tidak memperoleh peningkatan kecepatan besar dibandingkan versi yang tidak dikompilasi
      Saya menduga penyebabnya adalah divergensi warp. Pada prosedur yang tidak dikompilasi, semua pemanggilan fungsi dapat digabungkan ke dalam satu ekspander fungsi bergaya interpreter yang “generik”, dan thread-thread warp dapat melakukan reduksi tanpa percabangan. Ke depan, bagian ini akan diteliti lebih mendalam